Article ID: | iaor2014646 |
Volume: | 12 |
Issue: | 2 |
Start Page Number: | 101 |
End Page Number: | 121 |
Publication Date: | Jun 2014 |
Journal: | 4OR |
Authors: | Chrtienne Philippe |
Keywords: | job shop |
In this paper, we give an overview of the main results obtained on the complexity of scheduling under the non‐idling constraint, i.e, when the jobs assigned to each machine must be processed with no intermediate delay. That constraint is met in practice when the cost of intermediate idle time is too high due to the idle time itself and/or the machine restarting. The non idling constraint is a strong constraint that often needs a new solving approach and most results about classical scheduling problems do not easily extend to the non‐idling variant of the problem. In this survey, we mainly consider the non‐idling variants of the basic scheduling problems. So, we first present basic properties, complexity results and some algorithms concerning the one‐machine non‐idling scheduling problem. Then we consider the