A BRANCH-AND-BOUND ALGORITHM FOR THE 2-STAGE ASSEMBLY SCHEDULING PROBLEM

This paper develops a branch and bound algorithm for the two-stage ass embly scheduling problem. In this problem, there are m machines at the first stage, each of which produces a component of a job. When all pn components are available, a single assembly machine at the second sta ge completes the job. The objective is to schedule the jobs on the mac hines so that the maximum completion time, or makespan, is minimized. A lower bound based on solving an artificial two-machine flow shop pro blem is derived. Also, several dominance theorems are established and incorporated into the branch and bound algorithm. Computational experi ence with the algorithm is reported for problems with up to 8000 jobs and 10 first-stage machines. (C) 1997 Published by Elsevier Science B. V.