### A unified approach to scheduling on unrelated parallel machinesA unified approach to scheduling on unrelated parallel machines

Access Restriction
Subscribed

 Author Kumar, V. S Anil ♦ Marathe, Madhav V. ♦ Parthasarathy, Srinivasan ♦ Srinivasan, Aravind Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2009 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Approximation algorithms ♦ Randomized rounding ♦ Scheduling under multiple criteria Abstract We develop a single rounding algorithm for scheduling on unrelated parallel machines; this algorithm works well with the known linear programming-, quadratic programming-, and convex programming-relaxations for scheduling to minimize completion time, makespan, and other well-studied objective functions. This algorithm leads to the following applications for the general setting of unrelated parallel machines: (i) a bicriteria algorithm for a schedule whose weighted completion-time and makespan $\textit{simultaneously}$ exhibit the current-best individual approximations for these criteria; (ii) better-than-two approximation guarantees for scheduling to minimize the $L_{p}$ norm of the vector of machine-loads, for all 1 < $\textit{p}$ < ∞; and (iii) the first constant-factor multicriteria approximation algorithms that can handle the weighted completion-time and $\textit{any}$ given collection of integer $L_{p}$ norms. Our algorithm has a natural interpretation as a melding of linear-algebraic and probabilistic approaches. Via this view, it yields a common generalization of rounding theorems due to Karp et al. [1987] and Shmoys & Tardos [1993], and leads to improved approximation algorithms for the problem of scheduling with resource-dependent processing times introduced by Grigoriev et al. [2007]. 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 2009-08-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 56 Issue Number 5 Page Count 31 Starting Page 1 Ending Page 31

#### Open content in new tab

Source: ACM Digital Library