### Exact and Approximate Algorithms for Scheduling Nonidentical ProcessorsExact and Approximate Algorithms for Scheduling Nonidentical Processors

Access Restriction
Subscribed

 Author Horowitz, Ellis ♦ Sahni, Sartaj 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 Exact and approximate algorithms are presented for scheduling independent tasks in a multiprocessor environment in which the processors have different speeds. Dynamic programming type algorithms are presented which minimize finish time and weighted mean flow time on two processors. The generalization to $\textit{m}$ processors is direct. These algorithms have a worst-case complexity which is exponential in the number of tasks. Therefore approximation algorithms of low polynomial complexity are also obtained for the above problems. These algorithms are guaranteed to obtain solutions that are close to the optimal. For the case of minimizing mean flow time on $\textit{m}-processors$ an algorithm is given whose complexity is $O(\textit{n}$ log $\textit{mn}).$ 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-04-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 23 Issue Number 2 Page Count 11 Starting Page 317 Ending Page 327

#### Open content in new tab

Source: ACM Digital Library