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: alpha-point scheduling Figure 1: Sequencing in order of job dependent alpha-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:

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.


See also: