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 Li ne Balancing Problem Type 2 (SALBP-2) is described. This NP-hard probl em 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 conside red. Existing solution procedures for SALBP-2 are mainly based on repe atedly solving instances of the closely related SALBP-1, which is to m inimize the number of stations for a given production rate. The propos ed branch and bound procedure directly solves SALBP-2 by using a new e numeration technique, the Local Lower Bound Method, which is complemen ted by a number of bounding and dominance rules. Computational results indicate that the new procedure is very efficient.