Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-14311
For citation please use:
Main Title: Improved Scheduling Algorithms for Minsum Criteria
Author(s): Chakrabarti, Soumen
Phillips, Cynthia A.
Schulz, Andreas S.
Shmoys, David B.
Stein, Cliff
Wein, Joel
Type: Research Paper
URI: https://depositonce.tu-berlin.de/handle/11303/15538
http://dx.doi.org/10.14279/depositonce-14311
License: http://rightsstatements.org/vocab/InC/1.0/
Abstract: We consider the problem of finding near-optimal solutions for a variety of cal NP-hard scheduling problems for which the objective is to minimize the total weighted completion time. Recent work has led to the development of several techniques that yield constant worst-case bounds in a number of settings. We continue this line of research by providing improved performance guarantees for several of the most basic scheduling models, and by giving the first constant performance guarantee for a number of more realistically constrained scheduling problems. For example, we give an improved performance guarantee for minimizing the total weighted completion time subject to release dates on a single machine, and subject to release dates and/or precedence constraints on identical parallel machines. We also give improved bounds on the power of preemption in scheduling jobs with release dates on parallel machines. We give improved on-line algorithms for many more realistic scheduling models, including environments with parallelizable jobs, jobs contending for shared resources, tree precedence-constrained jobs, as well as shop scheduling models. In several of these cases, we give the first constant performance guarantee achieved on-line. Finally, one of the consequences of our work is the surprising structural property that there are schedules that simultaneously approximate the optimal makespan and the optimal weighted completion time to within small constants. Not only do such schedules exist, but we can find approximations to them with an on-line algorithm.
Subject(s): scheduling algorithms
minsum criteria
NP-hard scheduling problems
Issue Date: 1996
Date Available: 17-Dec-2021
Language Code: en
DDC Class: 510 Mathematik
Series: Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Series Number: 1996, 509
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:
Report-509-1996.pdf
Format: Adobe PDF | Size: 11.02 MB
DownloadShow Preview
Thumbnail
Report-509-1996.ps
Format: Postscript | Size: 194.19 kB
Download

Item Export Bar

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