Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-14622
For citation please use:
Main Title: Approximation Bounds for a General Class of Precedence Constrained Parallel Machine Scheduling Problems
Author(s): Munier, Alix
Queyranne, Maurice
Schulz, Andreas S.
Type: Research Paper
URI: https://depositonce.tu-berlin.de/handle/11303/15849
http://dx.doi.org/10.14279/depositonce-14622
License: http://rightsstatements.org/vocab/InC/1.0/
Abstract: A well studied and difficult class of scheduling problems concerns parallel machines and precedence constraints. In order to model more realistic situations, we consider precedence delays, asso ciating with each precedence constraint a certain amount of time which must elapse between the completion and start times of the corresponding jobs. Release dates, among others, may be modeled in this fashion. We provide the first constant-factor approximation algorithms for the makespan and the total weighted completion time objectives in this general class of problems. These algorithms are rather simple and practical forms of list scheduling. Our analysis also unifies and simplifies that of a number of special cases heretofore separately studies, while actually improving some of the former approximation results.
Subject(s): approximation bounds
scheduling
scheduling problems
parallel machines
precedence constraints
Issue Date: 1998
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: 1998, 584
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-584-1998.pdf
Format: Adobe PDF | Size: 17.34 MB
DownloadShow Preview
Thumbnail
Report-584-1998.ps
Format: Postscript | Size: 537.39 kB
Download

Item Export Bar

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