A unified approach to scheduling on unrelated parallel machines

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 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 < p < ∞; and (iii) the first constant-factor multicriteria approximation algorithms that can handle the weighted completion-time and 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].

REFERENCES

• 1: Noga Alon , Yossi Azar , Gerhard J. Woeginger , Tal Yadid, Approximation schemes for scheduling, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.493-500, January 05-07, 1997, New Orleans, Louisiana, United States
• 2: Javed Aslam , April Rasala , Cliff Stein , Neal Young, Improved bicriteria existence theorems for scheduling, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.846-847, January 17-19, 1999, Baltimore, Maryland, United States
• 3: B. Awerbuch , Y. Azar , E. F. Grove , Ming-Yang Kao , P. Krishnan , J. S. Vitter, Load balancing in the L/sub p/ norm, Proceedings of the 36th Annual Symposium on Foundations of Computer Science, p.383, October 23-25, 1995
• 4: Yossi Azar , Amir Epstein, Convex programming for scheduling unrelated parallel machines, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060639]
• 5: Yossi Azar , Leah Epstein , Yossi Richter , Gerhard J. Woeginger, All-norm approximation algorithms, Journal of Algorithms, v.52 n.2, p.120-133, August 2004 [doi>10.1016/j.jalgor.2004.02.003]
• 6: Yossi Azar , Leah Epstein , Yossi Richter , Gerhard J. Woeginger, All-Norm Approximation Algorithms, Proceedings of the 8th Scandinavian Workshop on Algorithm Theory, p.288-297, July 03-05, 2002
• 7: Chandra, A. K., and Wong, C. K. 1975. Worst-case analysis of a placement algorithm related to storage address. SIAM J. Comput. 4, 3, 249--263.
• 8: Rajiv Gandhi , Samir Khuller , Srinivasan Parthasarathy , Aravind Srinivasan, Dependent rounding and its applications to approximation algorithms, Journal of the ACM (JACM), v.53 n.3, p.324-360, May 2006 [doi>10.1145/1147954.1147956]
• 9: Goel, A., and Meyerson, A. 2002. Simultaneous optimization via approximate majorization for concave profits or convex costs. Tech. Rep. CMU-CS-02-203, Carnegie-Mellon University, Pittsburgh.
• 10: Michel X. Goemans , David P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM (JACM), v.42 n.6, p.1115-1145, Nov. 1995 [doi>10.1145/227683.227684]
• 11: Grigoriev, A., Sviridenko, M., and Uetz, M. 2005. Unrelated parallel machine scheduling with resource dependent processing times. In Proceedings of the Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science. Springer-Verlag, Berlin, Germany, 182--195.
• 12: Alexander Grigoriev , Maxim Sviridenko , Marc Uetz, Machine scheduling with resource dependent processing times, Mathematical Programming: Series A and B, v.110 n.1, p.209-228, March 2007 [doi>10.1007/s10107-006-0059-3]
• 13: Karp, R. M., Leighton, F. T., Rivest, R. L., Thompson, C. D., Vazirani, U. V., and Vazirani, V. V. 1987. Global wire routing in two-dimensional arrays. Algorithmica 2, 113--129.
• 14: Jon Kleinberg , Yuval Rabani , Éva Tardos, Fairness in routing and load balancing, Journal of Computer and System Sciences, v.63 n.1, p.2-20, August 2001 [doi>10.1006/jcss.2001.1752]
• 15: V. S. Anil Kumar , Madhav V. Marathe , Srinivasan Parthasarathy , Aravind Srinivasan, Approximation Algorithms for Scheduling on Multiple Machines, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.254-263, October 23-25, 2005 [doi>10.1109/SFCS.2005.21]
• 16: Ron Lavi , Chaitanya Swamy, Truthful mechanism design for multi-dimensional scheduling via cycle monotonicity, Proceedings of the 8th ACM conference on Electronic commerce, June 11-15, 2007, San Diego, California, USA [doi>10.1145/1250910.1250947]
• 17: Lawler, E. L., Lenstra, J. K., Rinnooy Kan, A. H. G., and Shmoys, D. B. 1993. Sequencing and Scheduling: Algorithms and Complexity. Elsevier, Amsterdam, The Netherlands.
• 18: J. K. Lenstra , D. B. Shmoys , É. Tardos, Approximation algorithms for scheduling unrelated parallel machines, Mathematical Programming: Series A and B, v.46 n.3, p.259-271, February 1990 [doi>10.1007/BF01585745]
• 19: Prabhakar Raghavan , Clark D. Tompson, Randomized rounding: a technique for provably good algorithms and algorithmic proofs, Combinatorica, v.7 n.4, p.365-374, Dec, 1987 [doi>10.1007/BF02579324]
• 20: Schuurman, P., and Woeginger, G. J. 1999. Polynomial-time approximation algorithms for machine scheduling: Ten open problems. J. Scheduling 2, 203--213.
• 21: David B. Shmoys , Éva Tardos, An approximation algorithm for the generalized assignment problem, Mathematical Programming: Series A and B, v.62 n.3, p.461-474, Dec. 8, 1993 [doi>10.1007/BF01585178]
• 22: Martin Skutella, Convex quadratic and semidefinite programming relaxations in scheduling, Journal of the ACM (JACM), v.48 n.2, p.206-242, March 2001 [doi>10.1145/375827.375840]
• 23: Smith, W. E. 1956. Various optimizers for single-stage production. Nav. Res. Log. Q. 3, 59--66.
• 24: Stein, C., and Wein, J. 1997. On the existence of schedules that are near-optimal for both makespan and total weighted completion-time. Oper. Res. Lett. 21, 115--122.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

General Terms:
Algorithms, Theory

Keywords:
Approximation algorithms, randomized rounding, scheduling under multiple criteria