並列ビルドの時間の上下界

依存グラフが DAG であるビルドの記述で、各タスク $t$ の所要時間を $w_t > 0$ とする。$W = \sum_{t \in T} w_t$ を仕事量、タスクだけを通る有向の道 $(t_1, \ldots, t_k)$ についての $\sum_j w_{t_j}$ の最大値 $L$ を最長の依存鎖（クリティカルパス）の長さとする。

$p \ge 1$ 台のワーカーによるスケジュールとは、各タスク $t$ に開始時刻 $\beta_t \ge 0$ を割り当て、$t$ が区間 $[\beta_t, \beta_t + w_t)$ の間 1 台を占有し、(i) どの時刻にも実行中のタスクは $p$ 個以下、(ii) $u \in D(t) \cap T$ ならば $\beta_u + w_u \le \beta_t$、を満たすものをいう。完了時刻を $\Theta = \max_t (\beta_t + w_t)$ とする。

(a) どのスケジュールも $\Theta \ge \max(W/p,\ L)$ を満たす。

(b) スケジュールが貪欲である、すなわち「依存がすべて完了していてまだ開始されていないタスクがある時刻には、$p$ 台すべてが実行中である」ならば、

が成り立つ。

(c) 貪欲なスケジュールの完了時刻は、最適なスケジュールの完了時刻の $(2 - 1/p)$ 倍以下である。