Hexaly, Gurobi, CP Optimizer on the Simple Assembly Line Balancing Problem (SALBP)

Benchmark Manufacturing Scheduling

Léa Optimization Scientist October 3, 2024

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 so that all tasks are assigned.

On the Simple Assembly Line Balancing Problem (SALBP), Hexaly reaches an average gap of 0.3% after 1 minute of running time. This article illustrates how Hexaly outperforms traditional general-purpose optimization solvers, like Gurobi 11.0, a state-of-the-art Mixed-Integer Linear Programming solver, and IBM ILOG CP Optimizer 20.1.0, a state-of-the-art Constraint Programming solver, on this 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”) dataset. For each instance, our performance metric is the gap in % to the best known solution in the literature. Hexaly improves 30% of the best solutions in the literature in the “large” dataset and 61% in the “very large” dataset.

Mathematical models of the Simple Assembly Line Balancing Problem (SALBP)

Mixed-Integer Linear Programming (MILP) model

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.

Constraint Programming (CP) model

The Constraint Programming (CP) model used to evaluate IBM ILOG 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.

Hexaly model

The Hexaly model uses one set variable per workstation representing the tasks assigned to the station. The processing time of each task is retrieved using 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 linear, and we will show how 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;
}

Hexaly, Gurobi, CP Optimizer results on the Simple Assembly Line Balancing Problem (SALBP)

We compare the three 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 literature, also called State Of The Art (SOTA). The comparison is made between Hexaly 13.0, Gurobi 11.0, and IBM ILOG CP Optimizer 20.1.0, considered 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 AMD Ryzen 7 7700 processor (8 cores, 3.8GHz, 8MB cache) and 32GB 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% for both datasets in 1 minute. Hexaly and IBM ILOG CP Optimizer reach feasibility very quickly, whereas Gurobi cannot find any feasible solution on the “very large” dataset, even within 1 hour of computation time.

In addition, below is a chart detailing the results of Hexaly 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 Hexaly and CP Optimizer is particularly noticeable for the most combinatorial instances, for which the best known solution involves more than 500 workstations for 1,000 tasks. In these instances, the gap found by Hexaly falls below 0.2% in 10 minutes.

Conclusion

Set modeling with Hexaly provides a compact model for the Simple Assembly Line Balancing Problem (SALBP), which yields a vast 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-scale instances.

You can find the complete model of the Simple Assembly Line Balancing Problem (SALBP) and many other Scheduling problems in Python, Java, C#, and C++ in our Example Tour.