On single-machine scheduling without intermediate delays

This paper introduces the non-idling machine constraint where no intermediate idle time between the operations processed by a machine is allowed. In its first part, the paper considers the non-idling single-machine scheduling problem. Complexity aspects are first discussed. The “Earliest Non-Idling” property is then introduced as a sufficient condition so that an algorithm solving the original problem also solves its non-idling variant. Moreover it is shown that preemptive problems do have that property. The critical times of an instance are then introduced and it is shown that when their number is polynomial, as for equal-length jobs, a polynomial algorithm solving the original problem has a polynomial variant solving its non-idling version.