Hexaly vs Gurobi on the Flexible Job Shop Scheduling Problem (FJSP)

Benchmark Manufacturing Scheduling

Victor Senior Optimization Scientist September 23, 2024

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 (non-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.

On large-scale instances of the Flexible Job Shop Scheduling Problem (FSJP), Hexaly reaches an average gap of 0.5% within 1 minute of running time. This page illustrates how Hexaly outperforms traditional general-purpose optimization solvers, like Gurobi, 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 most advanced 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;
}

Hexaly and Gurobi results on the Flexible Job Shop Scheduling Problem (FJSP)

We compare both solvers’ performance within 1 minute of running time. At the end of the running time, we measure the gap in % to the best solution known in the research literature. Note that these state-of-the-art (SOTA) solutions have been computed by dedicated algorithms with arbitrary running times on arbitrary computers. We use Hexaly 13.0 and Gurobi 11.0, known as a state-of-the-art Mixed-Integer Linear Programming (MILP) solver. Both are used with default parameters. We performed this experiment on a server equipped with an AMD Ryzen 7 7700 processor (8 cores, 3.8GHz, 8MB cache) and 32GB RAM. The table below presents the results. The average gap to the best known solutions are grouped according to the number of tasks to schedule.

For all instances, Hexaly delivers state-of-the-art solutions in less than 1 minute, with an average gap to the SOTA of 0.5% in 1 minute. On the other hand, Gurobi, with an average gap to the SOTA of 12% in 1 minute, struggles to find quality solutions to large instances.

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 Mixed-Integer Linear Programming (MILP) solvers. The resulting model for the FJSP is compact while providing much better results, particularly for large-scale 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.

[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.