Please use this identifier to cite or link to this item:
For citation please use:
Main Title: Single Machine Scheduling with Release Dates
Author(s): Goemans, Michel X.
Queyranne, Maurice
Schulz, Andreas S.
Skutella, Martin
Wang, Yaoguang
Type: Research Paper
Abstract: We consider the scheduling problem of minimizing the average weighted completion time of n jobs with release dates on a single machine. We first study two linear programming relaxations of the problem, one based on a time-indexed formulation, the other on a completion-time formulation. We show their equivalence by proving that a bigO(nlog n) greedy algorithm leads to optimal solutions to both relaxations. The proof relies on the notion of mean busy times of jobs, a concept which enhances our understanding of these LP relaxations. Based on the greedy solution, we describe two simple randomized approximation algorithms, which are guaranteed to deliver feasible schedules with expected objective function value within factors of 1.7451 and 1.6853, respectively, of the optimum. They are based on the concept of common and independent α-points, respectively. The analysis implies in particular that the worst-case relative error of the LP relaxations is at most 1.6853, and we provide instances showing that it is at least `e/(e-1) approx 1.5819`. Both algorithms may be derandomized; their deterministic versions run in bigO(n2) time. The randomized algorithms also apply to the on-line setting, in which jobs arrive dynamically over time and one must decide which job to process without knowledge of jobs that will be released afterwards.
Subject(s): approximation algorithm
randomized algorithm
LP relaxation
online algorithm
Issue Date: 1999
Date Available: 17-Dec-2021
Language Code: en
DDC Class: 510 Mathematik
MSC 2000: 90C27 Combinatorial optimization
68Q25 Analysis of algorithms and problem complexity
90B35 Scheduling theory, deterministic
68M20 Performance evaluation; queueing; scheduling
90C59 Approximation methods and heuristics
Series: Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Series Number: 1999, 654
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: 381.62 kB
DownloadShow Preview
Format: Unknown | Size: 163.9 kB

Item Export Bar

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