Key points are not available for this paper at this time.
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.
Garey et al. (Thu,) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: