Please use this identifier to cite or link to this item:
For citation please use:
Main Title: Scheduling to Minimize Average Completion Time: Off-line and On-line Approximation Algorithms
Author(s): Hall, Leslie A.
Schulz, Andreas S.
Shmoys, David B.
Wein, Joel
Type: Research Paper
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.
Subject(s): approximation algorithms
NP-hard scheduling problems
weighted sum of the job completion times
Issue Date: 1996
Date Available: 11-May-2022
Language Code: en
DDC Class: 510 Mathematik
MSC 2000: 90B35 Deterministic scheduling theory in operations research
90C27 Combinatorial optimization
90C05 Linear programming
Series: Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Series Number: 1996, 516
ISSN: 2197-8085
TU Affiliation(s): Fak. 2 Mathematik und Naturwissenschaften » Inst. Mathematik
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Format: Adobe PDF | Size: 32.93 MB
DownloadShow Preview

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.