Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Abstract Given a set @@@@ = ${\textit{T}1,\textit{T}2,···,\textit{T}n}$ of tasks, with each $\textit{T}i$ having execution time 1 and a deadline $\textit{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. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1976-07-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 23 Issue Number 3 Page Count 7 Starting Page 461 Ending Page 467