Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6894442 | European Journal of Operational Research | 2018 | 33 Pages |
Abstract
The paper considers the two-machine flow shop and open shop scheduling problems to minimize the makespan, provided that one of the machines is subject to maintenance, which has to start within a prescribed time window. In the case of the flow shop, maintenance is performed on the second machine. A non-resumable setting is considered, i.e., if a job cannot be completed prior to the maintenance, it must restart from scratch after the maintenance. For each of these NP-hard problems we develop a 3/2-approximation algorithm.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Gur Mosheiov, Assaf Sarig, Vitaly A Strusevich, Jonathan Mosheiff,