Inhalt des Dokuments
Preprint 516-1996
Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)- Title
- Scheduling to Minimize Average Completion Time: Off-line and On-line Approximation Algorithms
- Authors
- Leslie A. Hall, Andreas S. Schulz, David B. Shmoys, and Joel Wein
- Classification
-
not available
- Keywords
-
not available
- Abstract
-
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.
- Source
-
The report may be requested from our secretary Gabriele Klink, email: klink@math.tu-berlin.de
Zusatzinformationen / Extras
Direktzugang
Schnellnavigation zur Seite über Nummerneingabe