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

Benchmark Manufacturing Production Scheduling

Léa Optimization Scientist November 1, 2021

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.

Hexaly Optimizer reaches an average gap of 0.4% after 60 seconds of running time on Simple Assembly Line Balancing Problem instances with 1,000 tasks. This page illustrates how Hexaly Optimizer outperforms traditional general-purpose optimization solvers, like Gurobi 9.1 and IBM ILOG CP Optimizer 20.1.0, 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 29% of the best solutions in the literature in the “large” dataset and 59% 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 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;
}

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

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 Hexaly 10.5, Gurobi 9.1, and IBM ILOG CP Optimizer 20.1.0, respectively 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 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% for both datasets in 1 minute and 10 minutes. Hexaly and IBM ILOG CP Optimizer reach feasibility very quickly, whereas Gurobi cannot find any feasible solution on the “very large” dataset.

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 on 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 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) 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 discuss your optimization problems.