Access Restriction

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

   Open content in new tab
Source: ACM Digital Library