Solving the Simple Assembly Line Balancing Problem with CP Optimizer

The problem

The Simple Assembly Line Balancing Problem (SALBP) is the basic optimization problem in assembly line balancing research. Given is a set of operations each of which has a deterministic duration. The operations are partially ordered by precedence relations defining a precedence graph. The paced assembly line consists of a sequence of (work) stations. In each station a subset of the operations is performed by a single operator. The resulting station time (sum of the respective operation times) must not exceed the cycle time. Concerning the precedence relations, no task is allowed to be executed in an earlier station than any of its predecessors. We consider the version where the cycle time is given and we want to minimize the number of stations (SALBP-1).

Here is an example of precedence graph with 20 operations. The length of the rectangle representing the operations is proportional to the operation's duration given above the rectangle.

Assuming a cycle time of 1000, an example of optimal solution is shown below. The minimal number of stations is 4.

About CP Optimizer

CP Optimizer is available in CPLEX Optimization Studio. It provides a modeling language for Combinatorial Optimization Problems that extends Integer Linear Programming (and classical Constraint Programming) with some algebra on intervals and functions allowing compact and maintainable formulations for complex scheduling problems.

CP Optimizer has an automatic solution search process. This search of CP Optimizer is :

• Complete : it provides optimality proofs and lower bounds
• Anytime : feasible solutions are in general produced quickly
• Efficient : it is usually competitive with problem-specific algorithms on classical problems, and the performance improves from version to version
• Scalable: the engine can handle problems involving up to several hundreds of thousands of tasks
• Parallel: it can exploit all the compute cores available on the machine
• Deterministic: solving the same problem twice on the same machine will produce the same result

You can get a free and unlimited version of IBM ILOG CPLEX Optimization Studio, including CP Optimizer, through Academic Initiative if you are in academia. CP Optimizer is available in Python, Java, C++ (native code) and OPL. I will use Python and OPL here for illustration.

An overview of CP Optimizer (modeling concepts, applications, examples, tools, performance, etc.) is available here.

You can get an idea how CP Optimizer is used in the academia or the industry by searching for the references on GoogleScholar.

The CP Optimizer formulation for SALBP

Here is all the Python code you need to write in order to (1) read the data, (2) formulate the SALBP in CP Optimizer and (3) solve the problem using the automatic search. The explanation of the formulation is given after the code.

Yes, that's all!

The model creates one interval variable op[i] per operation. There are at most n stations. The time boundaries of stations is modeled by fixed interval variables of length 1 (the value 1 could be any positive integer, it represents the time taken to move from one station to the next one, the value of this duration has no impact on the problem). Precedence relations are posted using end_before_start constraints between operations and a global no_overlap constraint is posted to ensure that operations do not overlap each other and do not overlap station boundaries. Finally, the objective function is to minimize the makespan (end time of the last operation) as the number of stations is directly related with the makespan: nstations = ceil(makespan/(1+c)).

The instance file "instance.json" of the introductory example above reads like this:

Here is the same model formulated in OPL:

Note that there are several ways to formulate the fact the operations do not overlap the stations boundaries. We will use a slightly different one with similar efficiency in an extension of the problem in the end of the article.

Results

We run CP Optimizer on instances of the largest instance sets 'large' and 'very large' for respectively 100 and 1000 operations, from the benchmark data sets of [Otto & al, 2013] considering that the small problems with 50 operations or less are not really representative of realistic problem size.

Experiments were run on a MacBook Pro, Processor 2.5 GHz Quad-Core Intel Core i7, 16 GB RAM Memory.

Results on problems with 100 operations

We run all the 525 instances with 100 operations of [Otto & al, 2013] with the above CP Optimizer formulation with a time limit of 30 sec. and performed a similar comparison as the one done with LocalSolver in a recent post. The average gap to the best known solutions is -0.67%, it is compared to the gaps of LocalSolver on Table 1.

On this benchmark with 100 operations, LocalSolver reported improving 37 best known solutions over the results of [Otto & al, 2013]. Using the same reference, the CP Optimizer model (with a time limit of 30 sec.) improves 131 solutions. If we take into account the 37 improvements by LocalSolver, CP Optimizer still enhances 115 solutions. The new solutions are reported on Table 2, the ones enhancing LocalSolver solutions are in yellow. Column 'PB' is the problem instance number. Column 'S+L' is the number of stations in the best solution from [Otto & al, 2013] taking into account LocalSolver improvements. Column 'CPO' is the solution found by CP Optimizer within the 30 sec. time limit.

Results on problems with 1000 operations

Problems with 1000 operations are probably more representative of the size of actual industrial problems. On these problems, we ran CP Optimizer on all the 525 instances with a time limit of 2 min. The average gap to best known solutions is -0.05%. A total of 180 solutions were improved. These new solutions are reported on Table 3. Column 'PB' is the problem instance number. Column 'S' is the best solution from [Otto & al, 2013]. Column 'CPO' is the solution found by CP Optimizer within the 2 min. time limit.

Note that LocalSolver did not report any result on this benchmark with 1000 operations.

Flexibility of the CP Optimizer formulation

Toward more complex stations

In fact, the CP Optimizer formulation we have seen does more than just allocating operations to stations (which turns out to be sufficient in the simple version of the problem): it computes actual start and end times of each operation within each station. In many industrial line balancing problems, this is necessary because the resources available at the stations are more complex that just a single operator: there may be several available operators, some equipments or renewable resources can be used by the operations, there may be constraints due to the limited space at the station, incompatibilities between some pairs of operations to run in parallel, etc. Stated otherwise, finding the right timing of operations within a given station may be a complex scheduling problem in itself (somehow similar to the Resource Constrained Project Scheduling Problem, see my article on a formulation of this problem with CP Optimizer).

Because the CP Optimizer model also consider the scheduling of operations within the work stations, it can be very easily extended to more realistic versions of the problem.

Let's see a simple extension where we suppose that there is more than a single operator at a given station. Let W denote the number of operators at each station. The CP Optimizer model can easily be adapted to use a cumul function instead of a no-overlap constraint. The extended formulation is given below in Python.

This formulation does not need the fixed interval variables for the station boundaries. Instead, it uses a cumul function 'load' that represents the evolution over time t of the number of operations currently executing at time t. Constraints are posted on the possible values of this function 'load': it must be lower than the number of workers W and it must be 0 at stations boundaries.

An optimal solution for a version of the example using two operators (W=2) is shown below. It only uses 2 stations.

Toward other objective functions

It is also pretty easy to extend the model to handle different objective functions. For instance a classical variant (SALBP-2) is to minimize the cycle time c given a fixed number of stations m. If M denotes the range {0,..., m}, the model can be adapted as follows:

The main different with the original model is that the interval variables representing the station boundaries 'sb' are now not fixed but constrained to execute at some multiple of the cycle time. And the objective is to minimize cycle time 'c'.

An optimal solution for an SALBP-2 version of the example using three stations (m=3) is shown below. The optimal cycle time is c=1329.

References

[Otto & al, 2013] Otto, A.; Otto, C.; Scholl, A. (2013): Systematic data generation and test design for solution algorithms on the example of SALBPGen for assembly line balancing. European Journal of Operational Research 228/1, 33-45.