A note on the two-stage assembly flow shop scheduling problem with uniform parallel machines

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2006.07.027 Byline: Christos Koulamas, George J. Kyparisis Keywords: Scheduling; Flow shop; Uniform machines; Absolute performance bound; Approximation algorithms Abstract: We study the problem of minimizing the makespan in a two-stage assembly flow shop scheduling problem with uniform parallel machines. This problem is a generalization of the assembly flow shop problem with concurrent operations in the first stage and a single assembly operation in the second stage. We propose a heuristic with an absolute performance bound which becomes asymptotically optimal as the number of jobs becomes very large. We show that our results slightly improve earlier results for the simpler assembly flow shop problem (without uniform machines) and for the two-stage hybrid flow shop problem with uniform machines. Author Affiliation: Department of Decision Sciences and Information Systems, Florida International University, Miami, FL 33199, USA Article History: Received 10 March 2006; Accepted 20 July 2006