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

Benchmarks Manufacturing Scheduling

Julien Head of Science July 23, 2026

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 specified processing time that depends on the chosen machine, and each machine can process only one task at a time (non-overlapping 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 achieves an average gap of 0.6% relative to the best known solutions in the research literature (BKS) in 1 minute of runtime. This page illustrates how Hexaly outperforms traditional general-purpose optimization solvers, such as 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 with up to 500 tasks and up to 60 machines. 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 [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 as continuous. The model relies on a Big M to express some constraints. We set it to the sum over all tasks of the maximum possible processing time, which matches 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. Assignment of all tasks is ensured by a partition constraint. The scheduled times of the tasks are modeled using interval variables. 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 by applying the and operator to all 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 made are the task sequences on machines and the task execution times. List variables, combined with lambda expressions, enable simple and intuitive modeling of the problem without limiting 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 the performance of both solvers within 1 minute of runtime. At the end of the running time, we measure the gap in % to the best solution known in the research literature (BKS). Note that the BKS have been computed using dedicated algorithms with arbitrary runtime on arbitrary computers. We use Hexaly 15.0 and Gurobi 11.0. Both are used with default parameters. We performed this experiment on a server equipped with an AMD Ryzen 7 7700 processor (8 cores, 3.8 GHz, 8 MB cache) and 32 GB of RAM. The table below presents the results. The average gap to BKS is grouped by the number of tasks to be scheduled.

Across all instances, Hexaly delivers state-of-the-art solutions in under 1 minute, with an average gap to BKS of 0.6% within 1 minute. On the other hand, Gurobi, with an average gap to BKS of 16% 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 when using traditional Mixed-Integer Linear Programming (MILP). The resulting model for the FJSP is compact while providing much better results, particularly for large-scale instances and limited running times.

Our Code Templates include the Flexible Job Shop Scheduling Problem (FJSP) model and many other Scheduling problems written using Hexaly Modeler or programming languages such as Python, Java, C#, and C++.

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