Approximation Algorithms for the Parallel Flow Shop Problem

Xiandong Zhang, Steef van de Velde

Research output: Contribution to journalArticleAcademicpeer-review

44 Citations (Scopus)

Abstract

We consider the -hard problem of scheduling n jobs in m two-stage parallel flow shops so as to minimize the makespan. This problem decomposes into two subproblems: assigning the jobs to parallel flow shops; and scheduling the jobs assigned to the same flow shop by use of Johnson¿s rule. For m =2, we present a -approximation algorithm, and for m =3, we present a -approximation algorithm. Both these algorithms run in O(n log n) time. These are the first approximation algorithms with fixed worst-case performance guarantees for the parallel flow shop problem.
Original languageEnglish
Pages (from-to)544-552
Number of pages9
JournalEuropean Journal of Operational Research
Volume216
Issue number3
DOIs
Publication statusPublished - 2012
Externally publishedYes

Fingerprint

Dive into the research topics of 'Approximation Algorithms for the Parallel Flow Shop Problem'. Together they form a unique fingerprint.

Cite this