Scheduling to Minimize Average Completion Time: Off-line and On-line Approximation Algorithms

Leslie A. Hall, Andreas S. Schulz, David B. Shmoys, and Joel Wein

not available

not available

In this paper we introduce two general techniques for the design and analysis of approximation algorithms for NP-hard scheduling problems in which the objective is to minimize the weighted sum of the job completion times. For a variety of scheduling models, these techniques yield the first algorithms that are guaranteed to find schedules that have objective function value within a constant factor of the optimum. In the first approach, we use an optimal solution to a linear programming relaxation in order to guide a simple list-scheduling rule. Consequently, we also obtain results about the strength of the relaxation. Our second approach yields on-line algorithms for these problems: in this setting, we are scheduling jobs that continually 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 afterwards. Our on-line technique yields constant performance guarantees for a variety of scheduling environments, and in some cases essentially matches the performance of our off-line LP-based algorithms.

The report may be requested from our secretary Gabriele Klink, email: klink@math.tu-berlin.de