|
Published Articles >> Table of Contents >> Abstract
28th Hawaii International Conference on System Sciences (HICSS'95)
p. 20
Scheduling interval orders in parallel
E.W. Mayr, Inst. fur Inf., Tech. Univ. Munchen, Germany
Full Article Text:
 
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/HICSS.1995.375481
Send link to a friend
| Abstract |
|
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 /spl Tscr/ of n tasks (each requiring unit execution time) and an interval order > over /spl Tscr/, and given m identical parallel processors, construct an optimal (i.e. minimal length) schedule for (/spl 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 n/sup 3/ processors and O(log/sup 2/n) 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).
|
 Additional Information
|
Index Terms- scheduling; parallel algorithms; computational complexity; directed graphs; minimisation; concurrency control; interval order scheduling; parallel algorithm; partial orders; interval representations; transitively oriented digraph; undirected chordal complement; execution time; identical parallel processors; optimal schedule; minimal length schedule; scheduling distance computation subroutine; CREW-PRAM; incremental version; empty slots; interval order precedence constraints; deadlines; release times; task systems; NC-algorithm; interval graphs; NP-complete problems
Citation:
E.W. Mayr,
"Scheduling interval orders in parallel,"
hicss,
p. 20,
28th Hawaii International Conference on System Sciences (HICSS'95),
1995
|
|
