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

Simple item page
dc.contributor.authorHall, Leslie A.
dc.contributor.authorSchulz, Andreas S.
dc.contributor.authorShmoys, David B.
dc.contributor.authorWein, Joel
dc.date.accessioned2022-05-11T12:11:42Z
dc.date.available2022-05-11T12:11:42Z
dc.date.issued1996
dc.description.abstractIn 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.en
dc.identifier.issn2197-8085
dc.identifier.urihttps://depositonce.tu-berlin.de/handle/11303/16898
dc.identifier.urihttp://dx.doi.org/10.14279/depositonce-15676
dc.language.isoen
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/
dc.subject.ddc510 Mathematiken
dc.subject.otherapproximation algorithmsen
dc.subject.otherNP-hard scheduling problemsen
dc.subject.otherweighted sum of the job completion timesen
dc.titleScheduling to Minimize Average Completion Time: Off-line and On-line Approximation Algorithmsen
dc.typeResearch Paperen
dc.type.versionsubmittedVersionen
tub.accessrights.dnbfree
tub.affiliationFak. 2 Mathematik und Naturwissenschaften::Inst. Mathematikde
tub.affiliation.facultyFak. 2 Mathematik und Naturwissenschaftende
tub.affiliation.instituteInst. Mathematikde
tub.publisher.universityorinstitutionTechnische Universität Berlinen
tub.series.issuenumber1996, 516en
tub.series.namePreprint-Reihe des Instituts für Mathematik, Technische Universität Berlinen
tub.subject.msc200090B35 Deterministic scheduling theory in operations researchen
tub.subject.msc200090C27 Combinatorial optimizationen
tub.subject.msc200090C05 Linear programmingen

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Preprint_516-1996.pdf
Size:
32.15 MB
Format:
Adobe Portable Document Format
Download

Collections

Publications