Hexaly, CP Optimizer, OR-Tools, Gurobi, Cplex on very large-scale instances of the Job Shop Scheduling Problem (JSSP)

Benchmark Manufacturing Scheduling

Léa Optimization Scientist September 4, 2024

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.

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.

[1] Giacomo Da Col, Erich C. Teppan, Industrial-size job shop scheduling with constraint programming, Operations Research Perspectives, Volume 9, 2022.