A Three-Stage Optimization Method for Assembly Line Balancing Problem

Abstract

Considering the characteristics of multimodels production pattern on assembly line, the assembly line balancing problem which is non-deterministic polynomial hard becomes more challenging to complete. In this article, we propose a reformulation of simple assembly line balancing problem based on Dantzig-Wolfe decomposition. New models of the master problem and subproblems in this algorithm are built. We implement a branching rule which is suited to seeking integer solutions of the problem. A new three-stage branch-and-price algorithm is designed to accelerate the process of searching the branch-and-bound tree. Extensive computational experiments on benchmark data sets, as well as a real industry case are conducted. The numerical results validate the feasibility and effectiveness of the proposed method which performs efficiently on various cases. Effects on optimization results considering the characteristics of the instance sets are analyzed. Results show that the three-stage branch-and-price algorithm is superior to the classic branch-and-price algorithm in terms of solution quality and computing time.

Keywords

• Assembly process planning
• line balancing
• branch and price algorithm
• column generation