Using beam search techniques for sequencing mixed-model assembly lines

This paper introduces a beam search approach to sequencing mixed-model assembly lines and compares that approach to existing sequencing heuristics. The comparison study consists of over 400 test problems that vary in terms of number of product models, quantity of assembly, and degree of component commonality. The results show that beam search techniques are clearly superior to both the goal chasing algorithm (GCA) and Miltenburg and Sinnamon’s look ahead heuristic. The second half of this paper extends the beam search approach to allow two scheduling objectives: (1) minimizing parts consumption variation, and (2) minimizing workload variation. Termed filtered beam, this variation uses a filter to eliminate alternatives that exceed a predetermined threshold according to one objective, and then proceeds with the beam search for the second objective. As in the first case, optimization is not guaranteed; however, the filtered beam search provides a frontier of good trade-off solutions from which the decision maker can choose an acceptable sequence.