Approximation Algorithms for Scheduling on Multiple Machines

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. We obtain the following applications for the general setting of unrelated parallel machines: (i) a bicriteria algorithm for a schedule whose weighted completion-time and makespan simultaneously exhibit the current-best individual approximations for these criteria (3/2 and 2, respectively); (ii) better-than-two approximation guarantees for scheduling under the L/sub p/ norm for all 1 < p < /spl infin/, improving on the 2-approximation algorithms of Azar & Epstein; and (iii) the first constant-factor multicriteria approximation algorithms that handle the weighted completion-time and any given collection of integer L/sub p/ norms. Our algorithm yields a common generalization of rounding theorems due to Karp et al and Shmoys & Tardos; among other applications, this yields an improved approximation for scheduling with resource-dependent processing times studied by Grigoriev et al.

Authors

• V. S. Anil Kumar 0001
• Madhav V. Marathe
• Srinivasan Parthasarathy 0002
• Aravind Srinivasan

Keywords

• Approximation algorithms
• Scheduling algorithm
• Processor scheduling
• Computer science
• Educational institutions
• Parallel machines
• Cost function
• Laboratories
• Linear programming
• Application software
• Estimation Algorithm
• Objective Function
• Quadratic Programming
• L1-norm
• Makespan
• Multi-objective Optimization
• Multiple Objects
• Convex Optimization
• Additional Error
• Probability 1
• Convex Combination
• Real Vector
• End Of Each Iteration
• Integral Solution
• Beginning Of Iteration
• Job Assignment
• Parallel Machine Scheduling