296. HLF optimality for scheduling a delayed precedence tree on m processors
Invited abstract in session MB-7: Advances in scheduling: From theory to practice, stream Scheduling and Project Management.
Monday, 10:30-12:00Room: Clarendon GR.01
Authors (first author is the speaker)
| 1. | Djamal Rebaine
|
| Informatique et mathématique, Université du Québec à Chicoutimi | |
| 2. | Alain Quilliot
|
| IT, LIMOS |
Abstract
In a valid schedule of delayed precedence task graph, if there is an arc between task i and task j, then the start time of task j is at least d time apart from the completion time of task i. We consider n unit execution time tasks, linked by a delayed precedence intree, to schedule on m processors so as to minimize the makespan. It is known in the literature the Highest Level First rule is optimal for m=1. We prove in this study this rule remains optimal even if m is greater than 1.
Keywords
- Scheduling
- Combinatorial Optimization
- Algorithms
Status: accepted
Back to the list of papers