Hexaly vs CP Optimizer, OR-Tools, Gurobi, Cplex on large-scale instances of the Job Shop Scheduling Problem (JSSP)
In the Job Shop Scheduling Problem (JSSP), a set of jobs has to be processed on every machine in the shop. Each job consists of an ordered sequence of tasks, called activities, each representing the processing of the job by one of the machines. Each job has one activity per machine. Each activity can start when the previous activity is completed. Activities have a given processing time, and each machine can only process one activity at a time. The goal is to schedule the activities to minimize the makespan: the time when all jobs have been processed.
Hexaly improves the research’s best known solution by an average of 7.4% within 60 seconds on large-scale instances of the Job Shop Scheduling Problem (JSSP). This page illustrates how Hexaly Optimizer outperforms traditional general-purpose optimization solvers, like IBM ILOG CP Optimizer, Google OR-Tools, Gurobi, and IBM ILOG Cplex, on this challenging problem.
Input data
In this benchmark, we focus on large-scale instances by Da Col and Teppan in 2022 [1] for the Job Shop Scheduling Problem (JSSP): 1,000 jobs and 1,000 machines, for a total of 1,000,000 activities.
Hexaly model for the Job Shop Scheduling Problem (JSSP)
The Hexaly model relies on interval variables representing the time span of each activity and on list variables representing the sequence of jobs on each machine. The no-overlap constraints on the machines are ensured by using the and operator over all the consecutive elements of the machine sequences using a lambda expression. Compared to a classical MIP 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() {
// Interval decisions: time range of each task
// tasks[j][m] is the interval of time of the task of job j which is processed
// on machine m
tasks[j in 0...nbJobs][m in 0...nbMachines] <- interval(0, maxStart);
// Task duration constraints
for [j in 0...nbJobs][m in 0...nbMachines]
constraint length(tasks[j][m]) == processingTime[j][m];
// Precedence constraints between the tasks of a job
for [j in 0...nbJobs][k in 0...nbMachines-1]
constraint tasks[j][machineOrder[j][k]] < tasks[j][machineOrder[j][k + 1]];
// Sequence of tasks on each machine
jobsOrder[m in 0...nbMachines] <- list(nbJobs);
for [m in 0...nbMachines] {
// Each job has a task scheduled on each machine
constraint count(jobsOrder[m]) == nbJobs;
// Disjunctive resource constraints between the tasks on a machine
constraint and(0...nbJobs-1,
i => tasks[jobsOrder[m][i]][m] < tasks[jobsOrder[m][i + 1]][m]);
}
// Minimize the makespan: end of the last task of the last job
makespan <- max[j in 0...nbJobs] (end(tasks[j][machineOrder[j][nbMachines - 1]]));
minimize makespan;
}Hexaly, CP Optimizer, OR-Tools, Gurobi, and Cplex results on the Job Shop Scheduling Problem (JSSP)
We compare Hexaly Optimizer 12.5’s performance with that of four other optimization solvers: IBM ILOG CP Optimizer 12.10.0, Google OR-Tools CP-SAT 7.7.7810, Gurobi 11.0.1, and IBM ILOG Cplex 22.1.0. Hexaly Optimizer’s results were obtained after 1 minute of running time on a server equipped with an Intel i7-12700H (14 cores, 2.3 GHz, 20 threads) and 32GB RAM. For the other solvers, we use the results given in [1] (six hours of computation on a system equipped with a 2 GHz AMD EPYC 7551P 32 Cores CPU and 256 GB of RAM).
Hexaly Optimizer’s results after 1 minute of computation are, on average, 7.4% better than CP Optimizer’s after 6 hours. OR-Tools, Gurobi, and Cplex, fail to deliver feasible solutions within 6 hours of running time. The table below presents each solver’s results on the ten large instances forming our benchmark.
| Hexaly (60s) | Hexaly (60s) vs CP Optimizer (6h) | CP Optimizer (6h) | OR-Tools (6h) | Gurobi (6h) | Cplex (6h) | |
|---|---|---|---|---|---|---|
| tai_j1000_ m1000_1 | 886891 | -7.2% | 959945 | – | – | – |
| tai_j1000_ m1000_2 | 886765 | -7.8% | 961924 | – | – | – |
| tai_j1000_ m1000_3 | 888831 | -7.2% | 957455 | – | – | – |
| tai_j1000_ m1000_4 | 888902 | -7.5% | 961039 | – | – | – |
| tai_j1000_ m1000_5 | 886469 | -8.1% | 964267 | – | – | – |
| tai_j1000_ m1000_6 | 888019 | -7.2% | 957143 | – | – | – |
| tai_j1000_ m1000_7 | 887761 | -7.2% | 956978 | – | – | – |
| tai_j1000_ m1000_8 | 888776 | -7.0% | 955338 | – | – | – |
| tai_j1000_ m1000_9 | 887196 | -7.3% | 956860 | – | – | – |
| tai_j1000_ m1000_10 | 889042 | -7.4% | 955693 | – | – | – |
Conclusion
Hexaly offers an innovative modeling approach based on interval and list variables, making the Job Shop Scheduling Problem (JSSP) modeling compact and straightforward. With this model, Hexaly Optimizer greatly outperforms traditional general-purpose optimization solvers like CP Optimizer, OR-Tools, Gurobi, and Cplex on large-scale JSSP instances.
You can find the complete Hexaly model of the Job Shop Scheduling Problem (JSSP) and many other scheduling problems written using Hexaly Modeler, or 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 gladly discuss your optimization problems.
[1] Giacomo Da Col, Erich C. Teppan, Industrial-size job shop scheduling with constraint programming, Operations Research Perspectives, Volume 9, 2022.