Premium
An absolute approximation algorithm for scheduling unrelated machines
Author(s) -
Shchepin Evgeny,
Vakhania Nodari
Publication year - 2006
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/nav.20157
Subject(s) - rounding , multiprocessing , scheduling (production processes) , computer science , time complexity , multiprocessor scheduling , algorithm , approximation error , parallel computing , job shop scheduling , mathematics , mathematical optimization , flow shop scheduling , schedule , operating system
Non‐preemptive scheduling of n independent jobs on m unrelated machines so as to minimize the maximal job completion time is considered. A polynomial algorithm with the worst‐case absolute error of min{(1 − 1/ m ) p max , p max ′ } is presented, where p max is the largest job processing time and p max ′is the m th element from the non‐increasing list of job processing times. This is better than the earlier known best absolute error of p max . The algorithm is based on the rounding of acyclic multiprocessor distributions. An O ( n m 2 ) algorithm for the construction of an acyclic multiprocessor distribution is also presented. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006