ISSN:
1436-4646
Keywords:
Scheduling
;
Approximation algorithm
;
Approximation scheme
;
Worst-case analysis
;
Open shop
;
Makespan
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01585871
Permalink