Lower Bounds and Efficient Algorithms for Multiprocessor Scheduling of Dags with Communication Delays.
Hermann JungLefteris M. KirousisPaul G. SpirakisPublished in: SPAA (1989)
Keyphrases
- communication delays
- lower bound
- np hard
- directed acyclic graph
- control theory
- upper bound
- execution times
- precedence relations
- directed networks
- multiprocessor systems
- processing times
- objective function
- branch and bound
- branch and bound algorithm
- lower and upper bounds
- optimal solution
- scheduling problem
- worst case
- integer programming
- approximation algorithms
- np complete
- resource constrained project scheduling problem
- lagrangian relaxation
- minimum cost
- linear programming
- multi objective