An exact constraint programming based procedure for the multi-manned assembly line balancing problem

Unlike the Simple Assembly Line Balancing Problem (SALBP), the Multi-manned Assembly Line Balancing Problem (MALBP) allows the assignment of multiple workers at the same station. This study proposes a novel Constraint Programming (CP) model to evaluate the satisfiability of a type-F MALBP. Given a cycle time limit, the number of workers and the number of stations are set as parameters in each iteration. We adopt an exact lexicographical procedure as the solution method for this multi-objective optimization problem, performing a lower-bound search to minimize the number of workers as the primary objective. Such an assumption is common for real-world applications, in which the total cost of a worker is usually several orders of magnitude higher than the cost of a station. When dealing with hard instances, we adopt the task-worker assignment solution for SALBP as input to an auxiliary Mixed-Integer Linear Programming (MILP) model, which provides an initial condition for the task scheduling portion of the CP model. Strong tasks' scheduling bounds are also provided to tighten the search space, and mathematical similarities with SALBP are exploited to support our solution method. The integrated MILP-CP procedure yielded 126 optimal solutions from a 140-instance dataset, including nine new optimality proofs. Moreover, twelve additional instances were improved compared to the literature, enhancing the solution quality. Considering the best-found primal bounds, the maximum gap for the still-open instances is just 0.32%. These results demonstrated the effectiveness of the proposed procedure in solving MALBP when combined with solid bounds.

Automated summary

This study proposes a novel constraint programming model to solve the Multi-manned Assembly Line Balancing Problem and improves the solution quality compared to existing literature. The model found 126 optimal solutions from a dataset of 140 instances.