SCHEDULING UET-UCT SERIES-PARALLEL GRAPHS ON 2 PROCESSORS

Authors
FINTA L LIU Z MILIS I BAMPIS E
Citation
L. Finta et al., SCHEDULING UET-UCT SERIES-PARALLEL GRAPHS ON 2 PROCESSORS, Theoretical computer science, 162(2), 1996, pp. 323-340
Citations number
16
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
Journal title
Theoretical computer science → ACNP
ISSN journal
03043975
Volume
162
Issue
2
Year of publication
1996
Pages
323 - 340
Database
ISI
SICI code
0304-3975(1996)162:2<323:SUSGO2>2.0.ZU;2-0
Abstract
The scheduling of task graphs on two identical processors is considere d. It is assumed that tasks have unit-execution-time, and arcs are ass ociated 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.