A 3/2-Approximation algorithm for two-machine flow-shop sequencing subject to release dates
K.N. Kashyrskikh ()
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.
Entry Submitted: 02/22/2001
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|