We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
THE TIME COMPLEXITY OF SCHEDULING INTERVAL ORDERS WITH COMMUNICATION IS POLYNOMIAL.
- Authors
ALI, HESHAM H.; EL-REWINI, HESHAM
- Abstract
Papadimitrjou and Yannakakis showed that unit execution time tasks in interval orders can be scheduled in linear time on N processors when communication cost is ignored. The objective function was to minimize the schedule length. They have also shown that the generalization of this problem to arbitrary execution times is NP-. In this paper, we study the problem of scheduling task graphs with communication on N processors when the task graph is an interval order. We prove that this scheduling problem can be solved in polynomial time when the execution cost of the system tasks is identical and equal to the communication cost between any pair of processors. We introduce an algorithm of O(Ne) to minimize the schedule length, where e is the number of arcs in the interval order.
- Publication
Parallel Processing Letters, 1993, Vol 3, Issue 1, p53
- ISSN
0129-6264
- Publication type
Article
- DOI
10.1142/S0129626493000083