Combinatorial Optimization & Graph Algorithms

Approximation Algorithms for Machine Scheduling

Participants:	Rolf H. Möhring, Markus Schäffter, Andreas S. Schulz, Martin Skutella
Cooperation with:	Leslie A. Hall, The Johns Hopkins University, Baltimore, David B. Shmoys, Cornell University, Ithaca, Joel Wein, Polytechnic University, Brooklyn
Supported by:	German National Science Foundation (DFG), grant Mo 446/3-1.

Project description:
In the last thirty years, there has been a great deal of work on approximation algorithms for NP-hard optimization problems, and in particular, for scheduling problems with min-max objective functions. However, until recently much less was known about approximation algorithms for NP-hard scheduling problems with min-sum objective functions.

Figure 1: Sequencing in order of job dependent -points: conversion of preemptive to non-preemptive schedules.

Inspired by the work of Phillips, Stein, and Wein (Scheduling jobs that arrive over time, Proceedings of the Fourth Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science 955, Springer: Berlin, 1995, pp. 86-97) and Hall, Shmoys, and Wein (Scheduling to minimize average completion time: off-line and on-line algorithms, Proceedings of the 7th ACM-SIAM Symposium on Discrete Algorithms, 1996, pp. 142-151) we have started to design and analyze approximation algorithms for NP-hard scheduling problems in which the goal is to minimize the average weighted completion time. For that, we use several techniques:

• We often guide our heuristics by optimum solutions to appropriate LP relaxations; for instance, we list schedule in order of non-decreasing LP completion times. In the analysis we then use the LP lower bound as a surrogate for the optimum; consequently, we also get worst-case bounds for the quality of the respective LP relaxations. From time to time, we also interpret LP solutions as probabilities, which leads us to the next point.
• Most often, the best performance guarantees are achieved by utilizing randomness in one or the other way. That is, we design randomized approximation algorithms whose output is expected to be within a constant factor of the optimum. The underlying insight of this approach is that an instance which is a worst-case instance for one value of certain parameters is not a worst-case instance for many other values of the very same parameters.
• By converting preemptive schedules to non-preemptive schedules (see Figure 1) we not only use relaxations which are different from LP's (though often related) but also establish bounds on the power of preemption.
• Another technique is a general framework for designing on-line algorithms in scheduling environments with release dates. In this setting, we are scheduling jobs that intermittently arrive to be processed and, for each time t, we must construct the schedule until time t without any knowledge of the jobs that will arrive after time t. Our on-line algorithms rely only on the existence of a dual (off-line) approximation algorithm for a problem that is closely related to finding a minimum-length schedule in that environment.

References:

• A. S. Schulz, Scheduling to Minimize Total Weighted Completion Time: Performance Guarantees of LP-Based Heuristics and Lower Bounds
  in William H. Cunningham, S. Tom McCormick, and Maurice Queyranne (eds.): Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science 1084, Springer: Berlin, 1996, pp. 301-315, Proceedings of the 5th International IPCO Conference
• L. A. Hall, A. S. Schulz, D. B. Shmoys, and J. Wein, Scheduling to minimize average completion time: off-line and on-line approximation algorithms, Preprint 516/1996, Department of Mathematics, TU Berlin, to appear in Mathematics of Operations Research
• S. Chakrabarti, C. A. Phillips, A. S. Schulz, D. B. Shmoys, C. Stein, and J. Wein, Improved Scheduling Algorithms for Minsum Criteria, in F. Meyer auf der Heide, B. Monien, editors, Automata, Languages and Programming, 23rd International Colloquium (ICALP'96), Paderborn, Germany, Springer Lecture Notes in Computer Science 1099 (1996), 646-657
• A. S. Schulz and M. Skutella, Scheduling-LPs Bear Probabilities: Randomized Approximations for Min-Sum Criteria, to appear in Springer Lecture Notes in Computer Science, Proceedings of the 5th Annual European Symposium on Algorithms (ESA'97)
• A. S. Schulz and M. Skutella, Random-Based Scheduling: New Approximations and LP Lower Bounds, to appear in Springer Lecture Notes in Computer Science, Proceedings of the 1st International Symposium on Randomization and Approximation Techniques in Computer Science (Random'97)

• Scheduling Jobs with Communication Delays
• Approximation in Stochastic Scheduling