Scheduling UET trees with communication delays on two processors

Authors
Guinand, F Trystman, D
Citation
F. Guinand et D. Trystman, Scheduling UET trees with communication delays on two processors, RAIRO RE OP, 34(2), 2000, pp. 131-144
Citations number
14
Categorie Soggetti
Engineering Mathematics
Journal title
RAIRO-RECHERCHE OPERATIONNELLE-OPERATIONS RESEARCH
ISSN journal
03990559 → ACNP
Volume
34
Issue
2
Year of publication
2000
Pages
131 - 144
Database
ISI
SICI code
0399-0559(200004/06)34:2<131:SUTWCD>2.0.ZU;2-4
Abstract
In this paper, we present a new linear time algorithm Sor scheduling user ( Unit Execution and Communication Time) trees on two identical processors. T he chosen criterion is the makespan. The used strategy is based on clusteri ng of tasks. We show that this algorithm builds optimal schedules. Some ext ensions are discussed for non UECT tasks.