LocalSolver


Benchmark — Assembly Line Balancing Problem (SALBP)

The Simple Assembly Line Balancing Problem (SALBP) is defined as follows. A set of tasks must be gathered in groups called workstations. Each task requires some time to be processed. For each station, the sum of tasks' processing times must not exceed a given limit, namely the cycle time. In addition, tasks should be processed according to their precedence relationships. Finally, the objective is to minimize the number of workstations used such that all tasks are assigned. Here we show how LocalSolver outperforms traditional general-purpose optimization solvers, like Gurobi 9.1 and CP Optimizer 20.1.0, on this simple yet challenging problem.

Input data

The instances of this benchmark come from the Assembly Line Balancing website, maintained by researchers in the field. We use the instances of the "large" and "very large" datasets proposed by Otto et al. (2013). Both datasets include 525 instances with 100 (resp. 1,000) tasks to assign for the "large" (resp. "very large"). For each instance, our performance metric is the gap in % to the best-known solution in the literature. LocalSolver improves 29% of the best solutions known in the literature in the "large" dataset and 59% in the "very large" dataset.

Mathematical models

The results reported below for Gurobi 9.1 are obtained using the standard Mixed-Integer Linear Programming (MILP) model for the Assembly Line Balancing Problem, as described by Pastor et al. (2007) in "Evaluating optimization models to solve SALBP". This formulation consists of a quadratic number of binary variables representing the assignment of a task to a workstation and an additional binary variable per workstation representing whether the station is used or not.

The Constraint Programming (CP) model used to evaluate CP Optimizer's performance on SALBP is described by Laborie (2020) in the blog post "Solving the simple assembly line balancing problem with CP Optimizer". This formulation relies on a linear number of interval variables representing the tasks, over which a global "no overlap" constraint is posted to ensure that the tasks do not overlap each other and do not overlap the station boundaries.

The LocalSolver model uses one set variable per workstation representing the tasks assigned to the station. The processing time of each task is retrieved by the at operator. The precedence constraints between the tasks are written thanks to the find operator, which gives the index of the task's chosen workstation. This formulation is more compact and versatile than the MILP formulation. The number of variables is only linear, and we will show that it scales much better to large instances.


function model() {
    // Decisions: station[s] is the set of tasks assigned to station s
    station[s in 0..maxNbStations-1] <- set(nbTasks);
    constraint partition[s in 0..maxNbStations-1](station[s]);

    // Objective: nbUsedStations is the total number of used stations
    nbUsedStations <- sum[s in 0..maxNbStations-1](count(station[s]) > 0);

    // Stations must respect the cycleTime constraint
    timeInStation[s in 0..maxNbStations-1] <- sum(station[s], i => processingTime[i]);
    for [s in 0..maxNbStations-1]
        constraint timeInStation[s] <= cycleTime;

    // Stations must respect the succession's order of the tasks
    taskStation[i in 0..nbTasks-1] <- find(station, i);
    for[i in 0..nbTasks-1][j in successors[i]]
        constraint taskStation[i] <= taskStation[j];

    // Minimize the number of active stations
    minimize nbUsedStations;
}

Results

We compare the three 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 %. The comparison is made between LocalSolver 10.5, Gurobi 9.1, and CP Optimizer 20.1.0, respectively considered as state-of-the-art MILP and CP solvers. All three solvers are used with default parameters. We ran our experiments on a server equipped with an Intel Core i7-6700k processor (4 cores, 4.0GHz, 8MB cache) and 64GB RAM. We use the "large" and "very large" datasets proposed by Otto et al. (2013), which both contain 525 instances with 100 and 1,000 tasks respectively.

In the table below, we give the number and percentage of instances for which each solver finds a feasible solution, or reaches a feasible solution with a gap lower than 1%, in 1 minute and 10 minutes, for both datasets. LocalSolver and CP Optimizer both reach feasibility very quickly, whereas Gurobi cannot find any feasible solution on the "very large" dataset.

LocalSolver CP Optimizer Gurobi
60 sec 600 sec 60 sec 600 sec 60 sec 600 sec
Nb feasible 525 525 525 525 459 510
% feasible 100% 100% 100% 100% 87% 97%
Nb <1% gap 487 497 447 492 326 406
% <1% gap 93% 95% 85% 94% 62% 77%

Results on the "large" dataset.

LocalSolver CP Optimizer Gurobi
60 sec 600 sec 60 sec 600 sec 60 sec 600 sec
Nb feasible 525 525 525 525 0 0
% feasible 100% 100% 100% 100% 0% 0%
Nb <1% gap 500 521 310 338 0 0
% <1% gap 95% 99% 59% 64% 0% 0%

Results on the "very large" dataset.

In addition, below is a chart detailing the results of LocalSolver and CP Optimizer on the "very large" dataset. Since all instances have the same number of tasks, we chose to display the value of the objective in the corresponding best-known solution, that is, the number of used workstations, on the horizontal axis and the gap to this best-known solution on the vertical axis. Results for different time limits can be selected with the slider. The performance gap between LocalSolver and CP Optimizer is particularly noticeable on the most combinatorial instances, for which the best-known solution involves more than 500 workstations for 1,000 tasks. On these instances, the gap found by LocalSolver falls below 0.2% in 10 minutes.


Conclusion

Set modeling with LocalSolver provides a compact model for the Simple Assembly Line Balancing Problem (SALBP) which yields a huge performance advantage: near-optimal solutions are delivered in seconds for instances with 1,000 tasks to assign. On the other hand, traditional Mixed-Integer Linear Programming (MILP) solvers like Gurobi struggle to find feasible solutions to the problem, even for moderate-size instances, and Constraint Programming (CP) solvers like CP Optimizer remain behind on the larger instances.

You can find the complete model of the Simple Assembly Line Balancing Problem (SALBP) 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.

Contact us - Disclaimer - Privacy policy - Copyright 2021 LocalSolver