An assembly line currently has five workstations and the time required for each is shown below

Abstract

In this paper, we consider the problem of assigning operations to an ordered sequence of non-identical workstations, observing precedence relationships and cycle time restrictions. The objective is to minimize the cost of the workstations. We first present a dynamic programming algorithm, and introduce several fathoming rules in order to reduce the number of states in the dynamic program. A characterization of a wide class of polynomially solvable instances is given, and computational results are reported.

Keywords

Assembly line balancing

Dynamic programming

Branch and bound

Computational complexity

Copyright © 2002 Elsevier Science B.V. All rights reserved.