Maximizing the production rate in simple assembly line balancing – a branch and bound procedure

In this paper, a branch and bound procedure for the Simple Assembly Line Balancing Problem Type 2 (SALBP-2) is described. This NP-hard problem consists of assigning tasks to a given number of work stations of a paced assembly line so that the production rate is maximized. Besides, possible precedence constraints between the tasks have to be considered. Existing solution procedures for SALBP-2 are mainly based on repeatedly solving instances of the closely related SALBP-1, which is to minimize the number of stations for a given production rate. The proposed branch and bound procedure directly solves SALBP-2 by using a new enumeration technique, the Local Lower Bound Method, which is complemented by a number of bounding and dominance rules. Computational results indicate that the new procedure is very efficient.