Groupe d’études et de recherche en analyse des décisions


Branch and Bound Algorithms for the Multi-Product Assembly Line Balancing Problem

, et

This paper considers a flexible manufacturing system for several products, each requiring a number of sequential non-preemptive 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.

, 17 pages

Ce cahier a été révisé en octobre 1990