A branch and bound algorithm for the two-stage assembly scheduling problem

A branch and bound algorithm for the two-stage assembly scheduling problem

0.00 Avg rating0 Votes
Article ID: iaor19991981
Country: Netherlands
Volume: 103
Issue: 3
Start Page Number: 547
End Page Number: 556
Publication Date: Dec 1997
Journal: European Journal of Operational Research
Authors: ,
Keywords: scheduling
Abstract:

This paper develops a branch and bound algorithm for the two-stage assembly scheduling problem. In this problem, there are m machines at the first stage, each of which produces a component of a job. When all m components are available, a single assembly machine at the second stage completes the job. The objective is to schedule the jobs on the machines so that the maximum completion time, or makespan, is minimized. A lower bound based on solving an artificial two-machine flow shop problem is derived. Also, several dominance theorems are established and incorporated into the branch and bound algorithm. Computational experience with the algorithm is reported for problems with up to 8000 jobs and 10 first-stage machines.

Reviews

Required fields are marked *. Your email address will not be published.