ON THE COMPLEXITY OF SCHEDULING WITH LARGE COMMUNICATION DELAYS

Authors
BAMPIS E GIANNAKOS A KONIG JC
Citation
E. Bampis et al., ON THE COMPLEXITY OF SCHEDULING WITH LARGE COMMUNICATION DELAYS, European journal of operational research, 94(2), 1996, pp. 252-260
Citations number
15
Categorie Soggetti
Management,"Operatione Research & Management Science","Operatione Research & Management Science
Journal title
European journal of operational research → ACNP
ISSN journal
03772217
Volume
94
Issue
2
Year of publication
1996
Pages
252 - 260
Database
ISI
SICI code
0377-2217(1996)94:2<252:OTCOSW>2.0.ZU;2-S
Abstract
Given a directed acyclic graph (dag) with unit execution time tasks an d constant communication delays c greater than or equal to 2, we are i nterested in deciding if there is a schedule for the dag of length at most L. We prove that the problem is polynomial when L is equal to (c + 1), or (c + 2) for the special case of c = 2, and that it is NP-comp lete forte (c + 3) for any value of c, even in the case of a bipartite dag of depth one.