An linear programming based lower bound for the simple assembly line balancing problem |
| |
Institution: | 1. IMT Atlantique, LS2N-CNRS, La Chantrerie, 4, rue Alfred Kastler - B.P. 20722, F-44307 Nantes Cedex 3, France;2. INSEEC School of Business & Economics, 25 rue de l''Université, 69007 Lyon, France |
| |
Abstract: | The simple assembly line balancing problem is a classical integer programming problem in operations research. A set of tasks, each one being an indivisible amount of work requiring a number of time units, must be assigned to workstations without exceeding the cycle time. We present a new lower bound, namely the LP relaxation of an integer programming formulation based on Dantzig–Wolfe decomposition. We propose a column generation algorithm to solve the formulation. Therefore, we develop a branch-and-bound algorithm to exactly solve the pricing problem. We assess the quality of the lower bound by comparing it with other lower bounds and the best-known solution of the various instances from the literature. Computational results show that the lower bound is equal to the best-known objective function value for the majority of the instances. Moreover, the new LP based lower bound is able to prove optimality for an open problem. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|