Two-Processor Scheduling with Start-Times and Deadlines

Given a set T = \ T₁ ,T₂ , ⋯ ,Tₙ \ of tasks, each Tᵢ having execution time 1, an integer start-time sᵢ 0 and a deadline dᵢ > 0, along with precedence constraints among the tasks, we examine the problem of determining whether there exists a schedule on two identical processors that executes each task in the time interval between its start-time and deadline. We present an O(n³) algorithm that constructs such a schedule whenever one exists. The algorithm may also be used in a binary search mode to find the shortest such schedule or to find a schedule that minimizes maximum “tardiness”. A number of natural extensions of this problem are seen to be $NP$ complete and hence probably intractable.