Please use this identifier to cite or link to this item:
For citation please use:
Main Title: A Simple Approximation Algorithm for Scheduling Forests with Unit Processing Times and Zero-One Communication Delays
Author(s): Möhring, Rolf H.
Schäffter, Markus W.
Type: Research Paper
Abstract: In the last few years, scheduling jobs due to communication delays has received a great deal of attention. We consider the problem of scheduling forests due to unit processing times and zero-one communication delays and focus on the approximation algorithm of Hanen and Munier and on the algorithm of Guinand, Rapine and Trystram. These algorithms and their analysis are quite complex. In contrast, we present a very simple list scheduling algorithm for the problem P| prec=tree},pj=1,cij&;{0,1}|Cmax of scheduling trees subject to unit processing times and zero-one communication delays. For sufficiently many machines, e.g. `mgeq |V|`, the resulting schedule is optimal. For a restricted number of machines, the presented algorithm has the same absolute worst case performance as the algorithm of Guinand, Rapine and Trystram: m-1}{2}. It's relative worst case performance ratio turns out to be bounded by left(2- 1}{m} ight) even for arbitrary processing times. This simplifies an argument by Hanen and Munier for the case that an optimal schedule on an infinite number of machines can be constructed.
Subject(s): approximation algorithm
unit processing
communication delays
scheduling forests
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, 506
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: 16 MB
DownloadShow Preview
Format: Postscript | Size: 421.03 kB

Item Export Bar

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