Scheduling interval-ordered tasks with non-uniform deadlines subject to non-zero communication delays
✍ Scribed by Jacques Verriet
- Publisher
- Elsevier Science
- Year
- 1999
- Tongue
- English
- Weight
- 268 KB
- Volume
- 25
- Category
- Article
- ISSN
- 0167-8191
No coin nor oath required. For personal study only.
✦ Synopsis
We study the problem of scheduling unit-length interval-ordered tasks subject to unitlength communication delays with the objective of minimising the maximum tardiness. Without communication delays, this problem can be solved by a generalisation of an algorithm presented by Garey and Johnson. In this paper, an algorithm is presented that considers unit-length communication delays and constructs minimum-tardiness schedules in O(n 2 ) time. Like the algorithm of Garey and Johnson, it computes smaller deadlines and uses these to assign a starting time to every task. Unlike the algorithm of Garey and Johnson, calculating a deadline for individual tasks is not sucient: to fully use the knowledge of the communication delays, the algorithm computes deadlines for pairs of tasks.