Improved approximation algorithms for scheduling with fixed jobs

ABSTRACT

We study two closely related problems in non-preemptive scheduling of sequential jobs on identical parallel machines. In these two settings there are either fixed jobs or non-availability intervals during which the machines are not available; in either case, the objective is to minimize the makespan. Both formulations have different applications, e.g. in turnaround scheduling or overlay computing. For both problems we contribute approximation algorithms with an improved ratio of 3/2 + ε, respectively. For scheduling with fixed jobs, a lower bound of 3/2 on the approximation ratio has been obtained by Scharbrodt, Steger & Weisser; for scheduling with non-availability we provide the same lower bound. In total, our approximation ratio for both problems is essentially tight via suitable inapproximability results. We use dual approximation, creation of a gap structure and job configurations, and a PTAS for the multiple subset sum problem. However, the main feature of our algorithms is a new technique for the assignment of large jobs via flexible rounding. Our new technique is based on an interesting cyclic shifting argument in combination with a network flow model for the assignment of jobs to large gaps.

REFERENCES

• 1: Alberto Caprara , Hans Kellerer , Ulrich Pferschy, A PTAS for the Multiple Subset Sum Problem with different knapsack capacities, Information Processing Letters, v.73 n.3-4, p.111-118, Feb.29.2000 [doi>10.1016/S0020-0190(00)00010-7]
• 2: Chandra Chekuri , Sanjeev Khanna, A PTAS for the multiple knapsack problem, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.213-222, January 09-11, 2000, San Francisco, California, United States
• 3: Chandra Chekuri , Sanjeev Khanna, A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem, SIAM Journal on Computing, v.35 n.3, p.713-728, 2005 [doi>10.1137/S0097539700382820]
• 4: F. Diedrich, K. Jansen, F. Pascual, and D. Trystram. Approximation algorithms for scheduling with reservations. In S. Aluru, M. Parashar, R. Badrinath, and V. K. Prasanna, editors, HiPC, volume 4873 of LNCS, pages 297--307. Springer, 2007.
• 5: L. Eyraud-Dubois, G. Mounie, and D. Trystram. Analysis of scheduling algorithms with reservations. In IPDPS, pages 1--8. IEEE, 2007.
• 6: W. Fernandez de la Vega and G. S. Lueker. Bin packing can be solved within 1+ε in linear time. Combinatorica, 1(4):349--355, 1981.
• 7: Dorit S. Hochbaum, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 8: Dorit S. Hochbaum , David B. Shmoys, Using dual approximation algorithms for scheduling problems theoretical and practical results, Journal of the ACM (JACM), v.34 n.1, p.144-162, Jan. 1987 [doi>10.1145/7531.7535]
• 9: Dorit s. Hochbaum , David B. Shmoys, A polynomial approximation scheme for scheduling on uniform processors: Using the dual approximation approach, SIAM Journal on Computing, v.17 n.3, p.539-551, June 1988 [doi>10.1137/0217033]
• 10: H.-C. Hwang and S. Y. Chang. Parallel machines scheduling with machine shutdowns. Computers and Mathematics with Applications, 36(3):21--31, 1998.
• 11: Hark-Chin Hwang , Kangbok Lee , Soo Y. Chang, The effect of machine availability on the worst-case performance of LPT, Discrete Applied Mathematics, v.148 n.1, p.49-61, 30 April 2005 [doi>10.1016/j.dam.2004.12.002]
• 12: Oscar H. Ibarra , Chul E. Kim, Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems, Journal of the ACM (JACM), v.22 n.4, p.463-468, Oct. 1975 [doi>10.1145/321906.321909]
• 13: Klaus Jansen, Parameterized approximation scheme for the multiple knapsack problem, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.665-674, January 04-06, 2009, New York, New York
• 14: I. Kacem. Approximation algorithms for the makespan minimization with positive tails on a single machine with a fixed non-availability interval. Journal of Combinatorial Optimization, 2007.
• 15: H. Kellerer. Algorithms for multiprocessor scheduling with machine release times. IIE Transactions, 30(11), 1998.
• 16: H. Kellerer, U. Pferschy, and D. Pisinger. Knapsack Problems. Springer, 2004.
• 17: E. Remila, Approximate strip packing, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.31, October 14-16, 1996
• 18: Claire Kenyon , Eric Rémila, A Near-Optimal Solution to a Two-Dimensional Cutting Stock Problem, Mathematics of Operations Research, v.25 n.4, p.645-656, November 2000 [doi>10.1287/moor.25.4.645.12118]
• 19: E. L. Lawler. Fast approximation algorithms for knapsack problems. Mathematics of Operations Research, 4(4):339--356, 1979.
• 20: Chung-Yee Lee, Parallel machines scheduling with nonsimultaneous machine available time, Discrete Applied Mathematics, v.30 n.1, p.53-61, Jan. 7, 1991 [doi>10.1016/0166-218X(91)90013-M]
• 21: C.-Y. Lee. Machine scheduling with an availability constraint. Journal of Global Optimization, Special Issue on Optimization of Scheduling Applications, 9:363--384, 1996.
• 22: Chung-Yee Lee , Yong He , Guochun Tang, A note on “parallel machine scheduling with non-simultaneous machine available time”, Discrete Applied Mathematics, v.100 n.1-2, p.133-135, March 2000 [doi>10.1016/S0166-218X(99)00201-2]
• 23: J. Y.-T. Leung, editor. Handbook of Scheduling. Chapman & Hall, 2004.
• 24: C.-J. Liao, D.-L. Shyur, and C.-H. Lin. Makespan minimization for two parallel machines with an availability constraint. European Journal of Operational Research, 160:445--456, 2003.
• 25: Silvano Martello , Paolo Toth, Knapsack problems: algorithms and computer implementations, John Wiley & Sons, Inc., New York, NY, 1990
• 26: N. Megow, R. H. Möhring, and J. Schulz. Turnaround scheduling in chemical manufacturing. In In Proceedings of the 8th Workshop on Models and Algorithms for Planning and Scheduling Problems, MAPSP 2007, Istanbul, Turkey, 2007.
• 27: E. Sanlaville and G. Schmidt. Machine scheduling with availability constraints. Acta Informatica, 35(9):795--811, 1998.
• 28: M. Scharbrodt. Produktionsplanung in der Prozessindustrie: Modelle, effiziente Algorithmen und Umsetzung. PhD thesis, Fakultät für Informatik, Technische Universität München, 2000.
• 29: Mark Scharbrodt , Angelika Steger , Horst Weisser, Approximability of scheduling with fixed jobs, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.961-962, January 17-19, 1999, Baltimore, Maryland, United States
• 30: M. Scharbrodt, A. Steger, and H. Weisser. Approximability of scheduling with fixed jobs. Journal of Scheduling, 2:267--284, 1999.

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