A 3/2-Approximation algorithm for two-machine flow-shop sequencing subject to release dates

K.N. Kashyrskikh ()
C.N. Potts (cnpmaths.soton.ac.uk)
S.V. Sevastianov (sevamath.nsc.ru)

Abstract: The two-machine flow shop sequencing problem with arbitrary release dates of jobs and the minimum makespan criterion is considered. The problem is known to be NP-hard, and the best known approximation algorithms are those of Potts (1985) with a worst-case performance ratio of 5/3 and running time $O(n^3 \log n)$, and a polynomial time approximation scheme of Hall (1995) that can generate solutions arbitrary close to the optimum but with a high time requirement. In this paper, we modify Potts' algorithm so that its worst-case performance ratio is reduced to 3/2, but its running time remains $O(n^3\log n)$.

Keywords: Scheduling; Flow shop; Release dates; Approximation algorithm

Category 1: Applications -- OR and Management Sciences (Scheduling )

Citation: Discrete Appl. Math., 114 (2001), 255-271.

Download:

Entry Submitted: 02/22/2001
Entry Accepted: 02/23/2001
Entry Last Modified: 11/01/2001

Modify/Update this entry