Scheduling UET-UCT series-parallel graphs on two processors

The scheduling of task graphs on two identical processors is considered. It is assumed that tasks have unit-execution-time, and arcs are associated with unit-communication-time delays. The problem is to assign the tasks to the two processors and schedule their execution in order to minimize the make...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 1996-08, Vol.162 (2), p.323-340
Main Authors: Finta, Lucian, Liu, Zhen, Mills, Ioannis, Bampis, Evripidis
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The scheduling of task graphs on two identical processors is considered. It is assumed that tasks have unit-execution-time, and arcs are associated with unit-communication-time delays. The problem is to assign the tasks to the two processors and schedule their execution in order to minimize the makespan. A quadratic algorithm is proposed to compute an optimal schedule for a class of series-parallel graphs, called SP1 graphs, which includes in particular in-forests and out-forests.
ISSN:0304-3975
1879-2294
DOI:10.1016/0304-3975(96)00035-7