Hexaly vs Gurobi on the Car Sequencing Problem with Paint-Shop Batching Constraints

Benchmark Automotive Manufacturing Scheduling

Lucile Senior Optimization Scientist May 22, 2023

The Car Sequencing Problem with Paint-Shop Batching Constraints was initially submitted by the car manufacturer Renault at the 2005 Challenge of the French Society of Operations Research and Decision Support (ROADEF). The problem is to schedule the production of cars along production lines while respecting the assembly line and paint shop requirements. Cars with the most complicated options must be evenly distributed throughout the set of processed cars. Spray guns must be washed with paint solvent regularly and in-between two different car colors.

Hexaly Optimizer reaches near-optimal solutions within 60 seconds of running time on the Car Sequencing Problem with Paint-Shop Batching Constraints. This page illustrates how Hexaly Optimizer outperforms traditional general-purpose optimization solvers like Gurobi 9.1.

Input data

The instances are given on the challenge’s website in three sets A, B, and X. In this benchmark, we compare the results obtained by Hexaly and Gurobi for different solving times, on each of the 80 instances. The objective values are confronted to the best know solutions for these instances.

Mathematical models of the Car Sequencing Problem with Paint-Shop Batching Constraints

Mixed-Integer Linear Programming (MILP) model

The results reported for Gurobi are obtained using the standard Mixed-Integer Programming (MIP) modeling approach. The main decision is assigning a vehicle class to each position in the production line. Due to the workshop specificities, the MIP model requires many auxiliary binary and integer decisions. These decisions track the positions of the different classes of cars, their options along the production line, and the number of violations of the even distribution of complicated options. All decision variables must be linked to their corresponding constraint, resulting in a vast constrained model.

Hexaly model

Within the data is given an initial production sequence, respecting the constraints on the number of classes produced. The problem can then be considered a permutation problem based on this initial sequence. With Hexaly, this translates into the use of a list variable, combined with a partition constraint, ensuring that everything will be produced as expected. Everything else can be deduced from these decisions and is therefore defined as LSExpression in the Hexaly model as recommended in our Modeling Guide.

function model() {
    sequence <- list(nbPositions);

    constraint partition(sequence);
    for[p in 0..startPosition-1]
        constraint sequence[p] == p;

    nbCarsWindows[o in 0..nbOptions-1][j in startPosition-windowSize[o]+1..nbPositions-1] 
            <- sum[k in 0..windowSize[o]-1 : j + k >= 0 && j + k < nbPositions]
            (options[initialSeq[sequence[j + k]]][o]);

    nbViolationsWindows[o in 0..nbOptions-1] 
            <- sum[j in startPosition-windowSize[o]+1..nbPositions-1]
            (max(0, nbCarsWindows[o][j] - maxCarsPerWindow[o]));

    objectiveHigh <- sum[o in 0..nbOptions-1 : isPriorityOption[o]](nbViolationsWindows[o]);
    objectiveLow <- sum[o in 0..nbOptions-1 : !isPriorityOption[o]](nbViolationsWindows[o]);

    colorChange[p in startPosition-1..nbPositions-2] 
            <- colorClass[initialSeq[sequence[p]]] != colorClass[initialSeq[sequence[p+1]]];

    objectiveColor <- sum[p in startPosition-1..nbPositions-2](colorChange[p]);

    for[p in startPosition..nbPositions-paintBatchLimit-2]
        constraint or[p2 in 0..paintBatchLimit-1](colorChange[p + p2]);

    objectives[COLOR] <- objectiveColor;
    objectives[HIGH] <- objectiveHigh;
    objectives[LOW] <- objectiveLow;

    objective <- COEF_0 * objectives[0] + COEF_1 * objectives[1] + COEF_2 * objectives[2];
}

Gurobi and Hexaly results on the Car Sequencing Problem with Paint-Shop Batching Constraints

We compare the performance of both solvers with the solving time used in the competition: 10 minutes. We also add results obtained within 1 minute to illustrate the solver’s behavior with short running times. The objective is a linear combination of lexicographic goals. For the sake of readability, we only compare the first objective which is different from the best known solution for at least one solver. The comparison is made between Hexaly 11.0 and Gurobi 9.1, known as a state-of-the-art MIP solver. Both are used without any tuning. The best known solutions are those found during the competition using dedicated algorithms.

With up to 400 cars to assemble, Hexaly reaches the best known value for the first differentiating objective. Gurobi, however, struggles to approach the best known value even for small instances and even more as the size increases. Hexaly scales up, with solutions still close to the best known on the largest instances with up to 1500 cars. Increasing the running time is insufficient for Gurobi to catch up, while Hexaly keeps descending toward the best known solutions.

Conclusion

Hexaly’s modeling is straightforward and more manageable than classical MILP formulations. It results in high-quality solutions after only 1 minute of running time, even on large-scale instances, which is not the case with state-of-the-art MILP solvers like Gurobi.

You can find the complete model of the Car Sequencing Problem with Paint-Shop Batching Constraints and many other Scheduling problems in Python, Java, C#, and C++ in our Example Tour.