Hexaly vs Gurobi on the Flexible Job Shop Scheduling Problem (FJSP)
In the Flexible Job Shop Scheduling Problem (FJSP), a set of tasks grouped into jobs must be processed by a set of machines. Each job consists of an ordered sequence of tasks, and each task must be performed by one of the machines compatible with it. A task cannot begin until the previous task in the job is completed. Each task has a given processing time that depends on the chosen machine, and each machine can only process one task at a time (no-overlap constraint). Given a set of jobs, machines, and processing times, the objective is to assign to each machine a sequence of tasks along with their scheduled start times minimizing the makespan, which is the time when all jobs have been processed.
Hexaly Optimizer reaches an average gap of 1.47% within 60 seconds on large instances of the Flexible Job Shop Scheduling Problem. This page illustrates how Hexaly Optimizer outperforms traditional general-purpose optimization solvers, like Gurobi 9.1, on this challenging problem.
Input data
In this benchmark, we use classical instances from the literature, originally introduced in the following papers [1], [2], [3], [4], [5], [6], [7]. They have been summarized along with best known lower and upper bounds in the research report [7]. They form a large and varied collection of instances for the Flexible Job Shop Problem (FJSP), representing different kinds of situations and configurations for a number of tasks up to 500 and a number of machines up to 60. All of these instances are available here.
Mathematical models of the Flexible Job Shop Scheduling Problem (FJSP)
Mixed-Integer Linear Programming (MILP) model
The results reported for Gurobi are obtained with the last Mixed-Integer Linear Programming (MILP) formulation presented in the paper [10] and referenced in the latest research survey [9] on the Flexible Job Shop Problem (FJSP). This formulation outperforms its predecessors, notably the formulation presented in [8]. Binary variables model the assignments of operations to machines. The sequencing decisions are modeled using binary variables as well, one for each possible operation transition on a machine. Finally, the scheduling variables (start times) are modeled using continuous variables. The model relies on a Big M to express some constraints. We set it to the sum over each task of the max possible processing time, which is the same as the horizon used in the Hexaly model.
Hexaly model
The Hexaly model relies on list variables representing both the assignments and the sequences of tasks on machines. The assignment of all tasks is ensured through a partition constraint. The scheduled times of the tasks are modeled using interval variables representing the tasks. The selected machine for a task can be computed using the find operator, and is used to constrain the durations of the tasks. The no-overlap constraint for each machine is ensured through the use of the and operator over all the consecutive elements of the machine sequences, using a lambda expression. Compared to the MILP model, the Hexaly model is much more compact, as the only decisions to be taken are the sequences of tasks on machines and the execution times of the tasks. List variables combined with lambda expressions enable simple and intuitive modeling of the problem without limiting the possible extensions.
function model() {
// Sequence of tasks on each machine
jobsOrder[m in 0...nbMachines] <- list(nbTasks);
// Each task is scheduled on a machine
constraint partition[m in 0...nbMachines](jobsOrder[m]);
// Only compatible machines can be selected for a task
for [i in 0...nbTasks][m in 0...nbMachines : taskProcessingTime[i][m] == INFINITE]
constraint contains(jobsOrder[m], i) == false;
// For each task, the selected machine
taskMachine[i in 0...nbTasks] <- find(jobsOrder, i);
// Interval decisions: time range of each task
tasks[i in 0...nbTasks] <- interval(0, maxStart);
// The task duration depends on the selected machine
duration[i in 0...nbTasks] <- taskProcessingTime[i][taskMachine[i]];
for [i in 0...nbTasks]
constraint length(tasks[i]) == duration[i];
// Precedence constraints between the operations of a job
for [j in 0...nbJobs][o in 0...nbOperations[j]-1] {
local i1 = jobOperationTask[j][o];
local i2 = jobOperationTask[j][o + 1];
constraint tasks[i1] < tasks[i2];
}
// Disjunctive resource constraints between the tasks on a machine
for [m in 0...nbMachines] {
local sequence <- jobsOrder[m];
constraint and(0...count(sequence)-1,
i => tasks[sequence[i]] < tasks[sequence[i + 1]]);
}
// Minimize the makespan: end of the last task
makespan <- max[i in 0...nbTasks](end(tasks[i]));
minimize makespan;
}Gurobi and Hexaly results on the Flexible Job Shop Scheduling Problem (FJSP)
We compare both solvers’ performance with two solving times: 1 minute and 10 minutes. At the end of the running time, we measure the gap to the best known solution in %. We use Hexaly 12.0 and Gurobi 9.1, known as a state-of-the-art MIP solver. Both are used with default parameters. We ran them on a server equipped with an Intel Xeon 8375 (8 cores, 2.9 GHz, 54MB cache) and 32GB RAM.
The chart below presents the results. The instance size is on a horizontal scale, and the gap to the best known value is on the vertical axis. For each instance, you can check out the gap found by Hexaly or Gurobi by passing your mouse cursor over the corresponding points displayed on the chart.
For small instances of up to 100 tasks, Hexaly delivers near-optimal solutions in less than 1 minute. For larger instances, ranging from 100 to 500 tasks, Hexaly keeps producing high-quality solutions in short running times with an average gap of 1.47% in 1 minute and 1.08% in 10 minutes. On the other hand, Gurobi, with an average gap of 89% in 1 minute and 26% in 10 minutes, struggles to find quality solutions to these larger instances, even with longer running times.
Conclusion
Hexaly offers an innovative modeling approach based on interval and list variables, which makes the Flexible Job Shop Scheduling Problem (FJSP) much simpler to formulate than traditional MIP solvers. The resulting model for the FJSP is compact while providing much better results, particularly for large instances and limited running times.
You can find the complete model of the Flexible Job Shop Scheduling Problem (FJSP) and many other Scheduling problems in Python, Java, C#, and C++ in our Example Tour.
Are you interested in trying it out? Get free trial licenses here. In the meantime, feel free to contact us; we will be glad to discuss your optimization problems.
[1] P. Brandimarte (1993). Routing and scheduling in a flexible job shop by tabu search. Annals of Operations Research 22, 157-183.
[2] E. Hurink, B. Jurisch, M. Thole (1994). Tabu search for the job-shop scheduling problem with multi-purpose machine. Operations Research Spektrum 15, 205-215.
[3] J.W. Barnes, J.B. Chambers (1996). Flexible job shop scheduling by tabu search. Graduate Program in Operations Research and Industrial Engineering, The University of Texas at Austin, Technical Report Series, ORP96-09.
[4] S. Dauzère-Pérès, J. Paulli (1994). Solving the general multiprocessor job-shop scheduling problem. Management Report Series No. 182, Rotterdam School of Management, Erasmus Universiteit Rotterdam, The Netherlands.
[5] I. Kacem, S. Hammadi, P. Borne (2002). Pareto-optimality approach for flexible job-shop scheduling problems: hybridization of evolutionary algorithms and fuzzy logic. Mathematics and Computers in Simulation, 60(3-5), 245–276.
[6] P. Fattahi, M.S. Mehrabad, F. Jolai. (2007). Mathematical modeling and heuristic approaches to flexible job shop scheduling problems. Journal of Intelligent Manufacturing, 18(3), 331–342.
[7] D. Behnke, M.J. Geiger (2012). Test instances for the flexible job shop scheduling problem with work centers. Technical report, Helmut-Schmidt-Universität, Lehrstuhl für Betriebswirtschaftslehre, insbes. Logistik-Management, RR 12-01-01.
[8] C. Özgüven, L. Özbakir, Y. Yavuz (2010). Mathematical models for job-shop scheduling problems with routing and process plan flexibility. Applied Mathematical Modelling 34(6), 1539-1548.
[9] I.A. Chaudhry, A.A. Khan (2015). A research survey: review of flexible job shop scheduling techniques. International Transactions in Operational Research, 23(3), 551-591.
[10] V. Roshanaei, A. Azab, H. Elmaraghi (2013). Mathematical modeling and a meta-heuristic for flexible job shop scheduling. International Journal of Production Research, 51(20), 6247-6274.