On scheduling with the non-idling constraint

On scheduling with the non-idling constraint

0.00 Avg rating0 Votes
Article ID: iaor2014646
Volume: 12
Issue: 2
Start Page Number: 101
End Page Number: 121
Publication Date: Jun 2014
Journal: 4OR
Authors:
Keywords: job shop
Abstract:

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 m ‐machine non idling scheduling problem. We show that a few basic problems may be solved by rather easy extensions of the algorithm solving their classical counterpart. However, the complexity status of the non idling version of quite easy polynomial basic problems remains an open question. We finally consider a more constrained version of non‐idling, called the ‘homogeneously non idling’ constraint, where for any subset of machines, the union of their busy intervals must make an interval and we present the structural property that leads to a polynomial algorithm for unit time jobs and a weak precedence. We conclude by giving some research directions that seem quite interesting to study both for theoretical and practical issues.

Reviews

Required fields are marked *. Your email address will not be published.