Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-14227
For citation please use:
Main Title: Stochastic Machine Scheduling with Precedence Constraints
Author(s): Skutella, Martin
Uetz, Marc
Type: Research Paper
URI: https://depositonce.tu-berlin.de/handle/11303/15454
http://dx.doi.org/10.14279/depositonce-14227
License: http://rightsstatements.org/vocab/InC/1.0/
Abstract: We consider parallel, identical machine scheduling problems where the jobs are subject to precedence constraints, release dates, and the processing times of jobs are governed by independent probability distributions. The objective is to minimize the expected value of the total weighted completion time `&; w_j C_j, where w_jgeq 0`. Building upon a linear programming relaxation by Moehring, Schulz, and Uetz, and an idle time charging scheme by Chekuri, Motwani, Natarajan, and Stein, we derive the first constant-factor approximation algorithms for this model.
Subject(s): stochastic scheduling
approximation
worst-case performance
LP-relaxation
Issue Date: 2002
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: 2002, 756
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-756-2002.pdf
Format: Adobe PDF | Size: 82.47 kB
DownloadShow Preview
Thumbnail
Report-756-2002.ps.gz
Format: Unknown | Size: 62.63 kB
Download

Item Export Bar

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