Key points are not available for this paper at this time.
Given a set @@@@ = T 1, T 2, ···, T n of tasks, with each T i having execution time 1 and a deadline d i > 0, and a set of precedence constraints which restrict allowable schedules, the problem of determining whether there exists a schedule using two processors in which each task is completed before its deadline is examined. An efficient algorithm for finding such a schedule, whenever one exists, is given. The algorithm may also be used to find the shortest such schedule. In addition it is shown that the problem of finding a one-processor schedule which minimizes the number of tasks failing to meet their deadlines is NP-complete and, hence, is likely to be computationally intractable.
Garey et al. (Thu,) studied this question.