TY - GEN

T1 - Scheduling interval orders in parallel

AU - Mayr, E. W.

N1 - Publisher Copyright:
© 1995 IEEE.

PY - 1995

Y1 - 1995

N2 - Interval orders are partial orders defined by having interval representations. It is well known that a transitively oriented digraph G is an interval order iff its (undirected) complement G~ is chordal. We investigate parallel algorithms for the following scheduling problem: Given a system consisting of a set Tscr/of n tasks (each requiring unit execution time) and an interval order < over Tscr/, and given m identical parallel processors, construct an optimal (i.e. minimal length) schedule for (Tscr/,<). Our algorithm is based on a subroutine for computing so-called scheduling distances, i.e. the minimal number of time steps needed to schedule all those tasks succeeding some given task t and preceding some other task t'. For a given interval order with n tasks, these scheduling distances can be computed using n3 processors and O(log2n) time on a CREW-PRAM. We then give an incremental version of the scheduling distance algorithm, which can be used to compute the empty slots in an optimal schedule. From these, we derive the optimal schedule, using no more resources than for the initial scheduling distance computation and considerably improving on previous work by Sunder and He (1993). The algorithm can also be extended to handle task systems which, in addition to interval order precedence constraints, have individual deadlines and/or release times for the tasks. Our algorithm is the first NC-algorithm for this problem. As another application. It also provides NC-algorithms for some graph problems on interval graphs (which are NP-complete in general).

AB - Interval orders are partial orders defined by having interval representations. It is well known that a transitively oriented digraph G is an interval order iff its (undirected) complement G~ is chordal. We investigate parallel algorithms for the following scheduling problem: Given a system consisting of a set Tscr/of n tasks (each requiring unit execution time) and an interval order < over Tscr/, and given m identical parallel processors, construct an optimal (i.e. minimal length) schedule for (Tscr/,<). Our algorithm is based on a subroutine for computing so-called scheduling distances, i.e. the minimal number of time steps needed to schedule all those tasks succeeding some given task t and preceding some other task t'. For a given interval order with n tasks, these scheduling distances can be computed using n3 processors and O(log2n) time on a CREW-PRAM. We then give an incremental version of the scheduling distance algorithm, which can be used to compute the empty slots in an optimal schedule. From these, we derive the optimal schedule, using no more resources than for the initial scheduling distance computation and considerably improving on previous work by Sunder and He (1993). The algorithm can also be extended to handle task systems which, in addition to interval order precedence constraints, have individual deadlines and/or release times for the tasks. Our algorithm is the first NC-algorithm for this problem. As another application. It also provides NC-algorithms for some graph problems on interval graphs (which are NP-complete in general).

UR - http://www.scopus.com/inward/record.url?scp=27744521959&partnerID=8YFLogxK

U2 - 10.1109/HICSS.1995.375481

DO - 10.1109/HICSS.1995.375481

M3 - Conference contribution

AN - SCOPUS:27744521959

T3 - Proceedings of the Annual Hawaii International Conference on System Sciences

SP - 20

EP - 28

BT - Proceedings of the 28th Annual Hawaii International Conference on System Sciences, HICSS 1995

PB - IEEE Computer Society

T2 - 28th Annual Hawaii International Conference on System Sciences, HICSS 1995

Y2 - 3 January 1995 through 6 January 1995

ER -