Height-priority Schedule (HPS)
Input
A directed, outforest $G = (V, E)$ specifying the precedence constraints among the $|V|$ unit time tasks that are represented by the vertices of $G$, a nondecreasing profile $\mu$, a designated task $j$, and a time slot $t$.
Problem
Is task $j$ scheduled in time slot $t$ by the height-priority schedule?
Definitions
A graph is an outforest if every task has at most one incoming edge. The profile $\mu$ is a function from $\N$ to $\N - \{0\}$, where $\mu(i)$ denotes the number of machines available at the $i^\text{th}$ time slot, that is, the interval $[i, i + 1)$. If a profile has only one value, $m$, then it is called straight.
A schedule $s$ for a graph $G$ and a profile $\mu$ is a function from vertices of $G$ onto an initial segment $\{0, \ldots, l - 1\}$ of $\N$, such that
- $|s^{-1}(r)| \leq \mu(r)$, for all $r$ in $\{0, \ldots, l - 1\}$ and
- if $y$ is a successor of $x$ in $G$, then $s(x) < s(y)$.
Value $l$ denotes the length of the schedule. A minimum length schedule is called optimal. A schedule is greedy if the maximum number of tasks is scheduled at every slot, that is, $|s^{-1}(k)| < \mu(k)$ implies that every $y$ such that $s(y) > k$ is a successor of some vertex $s$ in $s^{-1}(k)$.
A priority $q$ is a function from the set of tasks into $\N$. A schedule $s$ is a $q$-priority schedule if vertices of higher priority are preferred over vertices of lower priority. Among the vertices of the same priority ties are broken arbitrarily. A $q$-priority schedule also has the property that $s(x) > s(y)$ and $q(x) > q(y)$ imply that $x$ is a successor of some vertex $z$ with $s(z) = s(y)$. Height is typically used as a priority function. Vertices without successors have a height of zero. A profile is called nondecreasing if $\mu(k) \leq \mu(k + 1)$ for every slot $k$.
Status
$\P$-complete (Dolev, Upfal, and Warmuth [1]).
Remarks
The reduction to show hardness is from a variant of the TopCVP. Dolev, Upfal, and Warmuth show several other problems are $\P$-complete. We mention a few of them here. Consult [1] for terms that are not defined here. Height-priority schedule for an opposing forest and a straight line profile, height-priority schedule for a level order and straight line profile, weight-priority (using only three different weights) schedule for an outforest and a straight profile, greedy schedule, and the lexicographically first schedule for an outforest and a straight line profile are all $\P$-complete [1].
When the number of machines $m$ is fixed and does not vary with time, and when the precedence constraints are given by a collection of outtrees; Dolev, Upfal, and Warmuth give EREW-PRAM algorithms for computing optimal schedules. In the former case the algorithm runs in $O(\log n)$ time using $n^2$ processors and in the latter case the algorithm runs in $O((\log n)^2)$ time using $n$ processors. Also see GLS for additional scheduling results.