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

Benchmarks Manufacturing Scheduling

Léa, Ph.D. Senior Optimization Scientist July 22, 2026

The Simple Assembly Line Balancing Problem (SALBP) is defined as follows. A set of tasks must be grouped into workstations. Each task requires some time to be processed. For each station, the sum of the processing times of the tasks 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 achieves an average gap of 0.2% relative to the best-known solutions in the research community (BKS) after 1 minute of runtime. This article illustrates how Hexaly outperforms traditional general-purpose optimization solvers, like Gurobi 11.0, a Mixed-Integer Linear Programming solver, and IBM ILOG CP Optimizer 20.1.0, a Constraint Programming solver, on this challenging problem.

Input data

The instances of this benchmark come from the Assembly Line Balancing repository, 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 relative to the best known solution in the research 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 indicating whether the station is used.

Constraint Programming (CP) model

The Constraint Programming (CP) model used to evaluate IBM ILOG CP Optimizer’s performance on SALBP is described in the blog post “Solving the simple assembly line balancing problem with CP Optimizer” by Laborie (2020). This formulation relies on a linear number of interval variables representing the tasks, over which a global “no-overlap” constraint is imposed to ensure that the tasks do not overlap with each other or with 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 using 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 over 1 minute of runtime. At the end of the runtime, we measure the gap as a percentage relative to BKS. The comparison is made between Hexaly 15.0, Gurobi 11.0, and IBM ILOG CP Optimizer 20.1.0. 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.8 GHz, 8 MB cache) and 32 GB of 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 report the number and percentage of instances for which each solver finds a feasible solution or reaches one with a gap below 1% for both datasets within 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.

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.

Our Code Templates contain the Simple Assembly Line Balancing Problem (SALBP) model and many other Scheduling problems written using Hexaly Modeler or programming languages like Python, Java, C#, and C++.