Hexaly, CP Optimizer, OR-Tools, Gurobi, Cplex on very 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.
On large-scale instances of the Job Shop Scheduling Problem (JSSP), Hexaly improves the best known solutions by the research by an average of 8.6% within 10 minutes of running time. This page illustrates how Hexaly 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
Here, we focus on very 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 the classical Mixed Integer Linear Programming (MILP) modeling, 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 problem modeling 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 13.0 with 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. The Hexaly results are obtained within 10 minutes (10m) of running time on a server equipped with an AMD Ryzen 7 7700 processor (8 cores, 3.8GHz, 8MB cache) and 32GB RAM. For the other solvers, we use the results given in [1] (6 hours of computation on a system equipped with a 2 GHz AMD EPYC 7551P 32 Cores CPU and 256 GB of RAM).
Hexaly’s results after 10 minutes of computation are, on average, 8.5% better than CP Optimizer’s after 6 hours (6h). OR-Tools, Gurobi, and Cplex fail to deliver feasible solutions within 6 hours (6h) of running time. The table below presents each solver’s results on the ten large-scale instances forming our benchmark.
Hexaly (10m) | Hexaly (10m) vs CP Optimizer (6h) | CP Optimizer (6h) | OR-Tools (6h) | Gurobi (6h) | Cplex (6h) | |
---|---|---|---|---|---|---|
tai_j1000_ m1000_1 | 877042 | -8.6% | 959945 | – | – | – |
tai_j1000_ m1000_2 | 877064 | -8.8% | 961924 | – | – | – |
tai_j1000_ m1000_3 | 878786 | -8.2% | 957455 | – | – | – |
tai_j1000_ m1000_4 | 876565 | -8.8% | 961039 | – | – | – |
tai_j1000_ m1000_5 | 877610 | -9.0% | 964267 | – | – | – |
tai_j1000_ m1000_6 | 876067 | -8.5% | 957143 | – | – | – |
tai_j1000_ m1000_7 | 876502 | -8.4% | 956978 | – | – | – |
tai_j1000_ m1000_8 | 876503 | -8.3% | 955338 | – | – | – |
tai_j1000_ m1000_9 | 876443 | -8.4% | 956860 | – | – | – |
tai_j1000_ m1000_10 | 875312 | -8.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 greatly outperforms traditional general-purpose optimization solvers like CP Optimizer, OR-Tools, Gurobi, and Cplex on very 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.