SINGLE-MACHINE SCHEDULING SUBJECT TO PRECEDENCE DELAYS

A single-machine scheduling problem with precedence delays is analyzed . A set of n tasks is to be scheduled on the machine in such a way tha t the makespan is minimized. The executions of the tasks are constrain ed by precedence delays, i.e., a task can start its execution only aft er any of its predecessors has completed and the delay between the two tasks has elapsed. In the case of unit execution times and integer le ngths of delays, the problem is shown to be NP-hard in the strong sens e. In the case of integer execution times and unit length of delays, t he problem is polynomial, and an O(n(2)) optimal algorithm is provided . Both preemptive and non-preemptive cases are considered.