Premium
Polynomial‐time approximation scheme for concurrent open shop scheduling with a fixed number of machines to minimize the total weighted completion time
Author(s) -
Edwin Cheng T.C.,
g Qingqin,
Ng Chi To
Publication year - 2011
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/nav.20484
Subject(s) - scheduling (production processes) , open shop , job shop scheduling , conjecture , time complexity , scheme (mathematics) , mathematical optimization , computer science , polynomial time approximation scheme , mathematics , due date , flow shop scheduling , algorithm , discrete mathematics , mathematical analysis , schedule , operating system , queue , programming language
In this article, we consider the concurrent open shop scheduling problem to minimize the total weighted completion time. When the number of machines is arbitrary, the problem has been shown to be inapproximable within a factor of 4/3 ‐ ε for any ε > 0 if the unique games conjecture is true in the literature. We propose a polynomial time approximation scheme for the problem under the restriction that the number of machines is fixed. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011