We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
On the Complexity of Non-preemptive Shop Scheduling with Two Jobs.
- Authors
Kis, Tamás
- Abstract
In this note, we investigate the time complexity of non-preemptive shop scheduling problems with two jobs. First we study mixed shop scheduling where one job has a fixed order of operations and the operations of the other job may be executed in arbitrary order. This problem is shown to be binary NP-complete with respect to all traditional optimality criteria even if distinct operations of the same job require different machines. Moreover, we devise a pseudo-polynomial time algorithm which solves the problem with respect to all non-decreasing objective functions. Finally, when the job with fixed order of operations may visit a machine more than once, the problem becomes unary NP-complete.Then we discuss shop scheduling with two jobs having chain-like routings. It is shown that the problem is unary NP-complete with respect to all traditional optimality criteria even if one of the jobs has fixed order of operations and the jobs cannot visit a machine twice.
- Subjects
PRODUCTION scheduling; POLYNOMIALS; COMPUTATIONAL complexity
- Publication
Computing, 2002, Vol 69, Issue 1, p37
- ISSN
0010-485X
- Publication type
Article
- DOI
10.1007/s00607-002-1455-z