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

In the Flexible Job Shop Scheduling Problem (FJSP), a set of tasks grouped by 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 (no 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. We illustrate on this page how LocalSolver outperforms traditional general-purpose optimization solvers, like Gurobi 9.1, on this challenging problem.

Input data

In this benchmark, we have used 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, 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 last 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 by binary variables as well, one for each possible operation transition on a machine. Finally, the scheduling variables (start times) are modeled by 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 LocalSolver model.

LocalSolver model

The LocalSolver 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 by integer variables representing the start time of the tasks. The selected machine for a task can be computed using the find operator, and it allows to compute the end time of the tasks as well. 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 LocalSolver model is much more compact, as the only decisions to be taken are the sequences of tasks on machines and the start 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() {
    // List variables: sequence of tasks on each machine
    jobsOrder[m in 0..nbMachines-1] <- list(nbTasks);

    // Each task is scheduled on a machine
    constraint partition[m in 0..nbMachines-1](jobsOrder[m]);

    // Only compatible machines can be selected for a task
    for[t in 0..nbTasks-1][m in 0..nbMachines-1] {
        if (taskProcessingTime[t][m] == INFINITE) {
            constraint not(contains(jobsOrder[m], t));
        }
    }

    // For each task, the selected machine
    taskMachine[t in 0..nbTasks-1] <- find(jobsOrder, t);

    // Integer variables: start time of each task
    start[t in 0..nbTasks-1] <- int(0, maxStart);

    // The task duration depends on the selected machine
    duration[t in 0..nbTasks-1] <- taskProcessingTime[t][taskMachine[t]];
    end[t in 0..nbTasks-1] <- start[t] + duration[t];

    // Precedence constraints between the operations of a job
    for [j in 0..nbJobs-1][o in 0..nbOperations[j]-2] {
        local t1 = jobOperationTask[j][o];
        local t2 = jobOperationTask[j][o + 1];
        constraint start[t2] >= end[t1];
    }

    // Disjunctive resource constraints between the tasks on a machine
    for [m in 0..nbMachines-1] {
        local sequence <- jobsOrder[m];
        constraint and(0..count(sequence) - 2, t => start[sequence[t + 1]] >= end[sequence[t]]);
    }

    // Minimize the makespan: end of the last task
    makespan <- max[t in 0..nbTasks-1] (end[t]);
    minimize makespan;
}

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

We compare both solvers’ performance with two solving times: 1 minute, and 10 minutes. At the end of the running time, we measure the gap to the best-known solution in %. We use LocalSolver 11.5 and Gurobi 9.1, known as a state-of-the-art MIP solver. Both are used with default parameters. We ran them on a server equipped with an Intel i7-7700K (4 cores, 4.2 GHz, 8MB cache) and 64GB RAM.

The chart below presents the results. The instance size is on a horizontal scale and the gap to the best-known value is on the vertical axis. For each instance, you can check out the gap found by LocalSolver or Gurobi by passing your mouse over the corresponding points displayed on the chart.

For small instances, up to 100 tasks, LocalSolver delivers near-optimal solutions in less than 1 minute. For larger instances, ranging from 100 to 500 tasks, LocalSolver keeps producing high-quality solutions in short running times with an average gap of 3.1% in 1 minute and 1.9% in 10 minutes. On the other side, Gurobi, with an average gap of 154% in 1 minute and 42% in 10 minutes, is struggling to find quality solutions in these larger instances, even with longer running times.

Conclusion

LocalSolver offers an innovative modeling approach based on list variables, which made the Flexible Job Shop Scheduling Problem (FJSP) much simpler to formulate than traditional MIP solvers. The resulting model for the FJSP is compact while providing much better results, particularly for large 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.

Are you interested in trying it out? Get free trial licenses here. In the meantime, feel free to contact us; we will be glad to exchange about your optimization problems.


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

Share