A two-stage multiple-machine assembly scheduling problem for minimizing sum of completion times

This paper considers a two-stage multiple-machine assembly scheduling problem for minimizing the sum of completion times. The first stage consists of two independent machines, each of which produces its own type of components. The second stage consists of two identical and independent parallel machines. The processing of the second stage cannot begin until the processing of the first stage is finished. Minimizing the sum of completion times at the second stage is considered as the scheduling measure. A lower bound based on the SPT rule is derived, which is then used to develop a branch-and-bound algorithm. An efficient simple heuristic algorithm is also developed. (C) 2008 Elsevier B.V. All rights reserved.