An MILP-based makespan minimization model for single-machine scheduling problem with splitable jobs and availability constraints

摘要

This paper investigates the performance of several solvers for mixed-integer linear programming (MILP) on a scheduling problem with job splitting properties and availability constraints. The jobs are splitable and lower bound on the size of each sub-job is imposed. The scheduling objective aims to find a feasible schedule that minimizes the makespan. This scheduling problem is known as NP-hard in the strong sense [9]. In this paper, a mixed-integer linear mathematical model is constructed based on some structurally optimal properties. Some solvers such as GLPK, COIN-OR CBC and Gurobi are used to test the performance of the proposed model. For solving the considered scheduling problem, the best implemented MILP solver with its branch-and-cut parameters will be determined through computational results.