Name
Abstract | ||
|---|---|---|
In this paper, we demonstrate the existence of a polynomial time approximation scheme for makespan minimization in the open shop scheduling problem with an arbitrary fixed numberm of machines. For the variant of the problem where the number of machines is part of the input, it is known that the existence of an approximation scheme would implyP = NP. Hence, our result draws a precise separating line between approximable cases (i.e., withm fixed) and non-approximable cases (i.e., withm part of the input) of this shop problem. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V. |
Year | DOI | Venue |
|---|---|---|
1998 | 10.1007/BF01585871 | Math. Program. |
Keywords | Field | DocType |
Scheduling, Approximation algorithm, Approximation scheme, Worst-case analysis, Open shop, Makespan | Open shop,Approximation algorithm,Mathematical optimization,Job shop scheduling,Scheduling (computing),Open-shop scheduling,Minimisation (psychology),Time complexity,Mathematics,Polynomial-time approximation scheme | Journal |
Volume | Issue | ISSN |
82 | 1-2 | 1436-4646 |
Citations | PageRank | References |
48 | 3.41 | 8 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sergey V. Sevastianov | 1 | 66 | 7.09 |
| Gerhard Woeginger | 2 | 4176 | 384.37 |