Thumbnail
Access Restriction
Subscribed

Author Garey, M. R. ♦ Johnson, D. S.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1976
Language English
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


Open content in new tab

   Open content in new tab
Source: ACM Digital Library