### Heuristic Algorithms for Scheduling Independent Tasks on Nonidentical ProcessorsHeuristic Algorithms for Scheduling Independent Tasks on Nonidentical Processors

Access Restriction
Subscribed

 Author Ibarra, Oscar H. ♦ Kim, Chul E. Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1977 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Abstract The finishing time properties of several heuristic algorithms for scheduling $\textit{n}$ independent tasks on $\textit{m}$ nonidentical processors are studied. In particular, for $\textit{m}$ = 2 an $\textit{n}$ log $\textit{n}$ time-bounded algorithm is given which generates a schedule having a finishing time of at most (√5 + 1)/2 of the optimal finishing time. A simplified scheduling problem involving identical processors and restricted task sets is shown to be P-complete. However, the LPT algorithm applied to this problem yields schedules which are near optimal for large $\textit{n}.$ 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 1977-04-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 24 Issue Number 2 Page Count 10 Starting Page 280 Ending Page 289

#### Open content in new tab

Source: ACM Digital Library