### 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.

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.

These techniques yield the first constant performance guarantees for a variety of scheduling models ranging from single machine as well as identical and unrelated parallel machine scheduling to flowshop scheduling and scheduling networks of unrelated machines, including constraints such as release dates, precedence constraints, and communication delays.

**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)

**See also:**