A polynomial algorithm for the homogeneously non-idling scheduling problem of unit-time independent jobs on identical parallel machines

摘要

In this paper, we consider the homogeneous m-machine scheduling problem where unit time jobs have to be scheduled within their time windows so that, for any subset of machines, the set of the time units at which at least one machine is busy, is an interval. For this problem, a time assignment of the jobs satisfying the time windows constraints is a schedule if it has a pyramidal profile and is a k-schedule if this profile property is satisfied up to level k only. We develop a generic algorithm to solve the problem and show it is correct using a proof that mainly relies on a necessary and sufficient condition for a schedule to exist proved in a previous paper. We finally show that the generic algorithm is polynomial. We conclude by giving the directions of ongoing works and by bringing open questions related to different variants of the basic non-idling m-machine scheduling problem. (C) 2018 Elsevier B.V. All rights reserved.