LocalSolver


Benchmark — 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 litterature, 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 kind 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

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.

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;
}

Results

We compare both solvers' performance with two solving times: 1 minute, 10 minutes. At the end of the running time, we measure the gap to the best-known solution in %. We use LocalSolver 10.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 Core i5-6500 processor (4 cores, 3.6GHz, 6MB cache) and 16GB RAM.

The chart below presents the results. The instance size is on a horizontal scale and the gap to the best-known value 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.5% in 1 minute and 2.0% in 10 minutes. On the other side, Gurobi, with an average gap of 147% in 1 minute and 36% in 10 minutes, is struggling to find quality solutions on 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) in Python, Java, C#, C++, and LSP in our Example Tour.

We are at your disposal to accompany you in the discovery of LocalSolver. Don't hesitate to contact us for any further information or support.


[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 modelling and a meta-heuristic for flexible job shop scheduling. International Journal of Production Research, 51(20), 6247-6274.

Contact us - Disclaimer - Privacy policy - Copyright 2021 LocalSolver