Branch-and-bound algorithms for the multi-product assembly line balancing problem

This paper considers a flexible manufacturing system for several products, each requiring a number of sequential nonpreemptive tasks, some of which may be common to many products, Work stations are capable of handling any task. The objective is to minimize the number of work stations necessary to manufacture all products so that tasks are performed in the proper order and so that all tasks assigned to any given station can be executed within a prescribed time frame. A new branch-and-bound approach for this problem is presented. It contains two main improvements over previously published tree search algorithms: an improved lower-bounding procedure and a more powerful partitioning scheme. The algorithm can be used either as a heuristic (in its truncated version) or as an exact method (in its full version). Tests performed on randomly generated problems confirm the effectiveness of the proposed improvements.