オペレーションズ・リサーチの問題
あるプロジェクトは作業 の つからなる。各作業の所要日数と先行作業（その作業を始める前にすべて終わっていなければならない作業）は次のとおりである。
| 作業 | 所要日数 | 先行作業 |
|---|---|---|
| なし | ||
| なし | ||
さらに、作業の開始時刻について次の つの制約がある。
- 制約 ：作業 は、作業 の開始から 日以上たってから開始する。
- 制約 ：作業 は、作業 の開始から 日以内に開始する（ の開始時刻は の開始時刻に を足した値以下である）。
プロジェクトの開始時刻を とし、各作業 の開始時刻を とする。各作業は開始したら中断せずに所要日数で終わり、作業は同時にいくつでも並行して行える。上の先行関係と制約 、 をすべて満たすスケジュールのうち、すべての作業が終わる時刻が最も早いものを考え、その時刻を最短完了日数 とする。
また、作業 の最早開始時刻を「すべての条件を満たすスケジュールにおける の最小値」、最遅開始時刻を「すべての条件を満たし、かつすべての作業が時刻 までに終わるスケジュールにおける の最大値」とし、全余裕を（最遅開始時刻）（最早開始時刻）と定める。
最短完了日数 と、作業 の全余裕を、この順に組で求めよ。
この問題で使うもの
- PERT の最早・最遅開始時刻とクリティカルパス（説明と入口の問題）
ヒント
行き詰まったら、上から順に 1 つずつ開いてください。
ヒント 1
先行関係も制約 、 も、すべて の形の不等式に直し、重み の辺 をもつネットワークの最長路問題として考えよう。
ヒント 2
制約 は と書けるので、重み の辺 になる。制約 は重み の辺 。前進計算は の順に行うとよい。
ヒント 3
前進計算で となる。後退計算では の上限が だけでなく からも決まることに注意する。
答えと解説
答えを見る
どこでつまずきましたか？（選ぶと、戻る場所を案内します）
解説を読む
定式化
すべての条件は の形の不等式（差分制約）で書ける。
- 先行関係 ：（ は の所要日数）
- 制約 ：
- 制約 ：、すなわち
これを「 から へ重み の辺」とみなしたネットワークで考えると、最早開始時刻は始点（時刻 ）からの最長路の長さになる。制約 は重み の辺 に対応する。 から へ到る路はないので正の閉路はなく、実行可能である。 の順に処理すれば、各点に入るすべての辺の始点が先に処理される。
前進計算（最早開始時刻）
このスケジュールは制約 も満たす（）。完了時刻は各作業の終了時刻の最大値で、 の終了 が最大（他の作業は の先行作業を通じて の開始までに終わる）。各 は最長路の長さなので、どの実行可能スケジュールでもこれ以上早くはできず、
である。最長路（クリティカルパス）は で、長さは 。比較のため、負の辺を通る路 の長さは である。
後退計算（最遅開始時刻）
完了時刻を 以下とする条件 から出発し、各不等式 を と読んで、逆順 に上限を求める（ の上限には の上限が必要なので、 を より先に処理する）。
これらの上限をそのまま開始時刻にしたスケジュール は、すべての先行関係と制約 、 を満たし（例：、、）、時刻 に完了する。よって作業 の最遅開始時刻は である。
制約 がなければ の上限は だが、 と の遅れの限界 によって に抑えられている点に注意する。
作業 の全余裕
したがって、答えは である。
別解
先行関係と制約から、開始時刻について次の不等式が成り立つ。
。
制約 (1) は 、制約 (2) は 。
【最短完了日数】
より 。
(2) より 。
よって 、。
(1) より 。
、かつ 。
よって で、 の所要日数は 3 なので完了は 20 日以上。
下記のスケジュールがすべての条件を満たすので 。
【 の最早開始時刻】
上で を示した。上のスケジュールで が達成されるので、最早開始時刻は 9。
【 の最遅開始時刻】
全作業を時刻 20 までに終えるには 。
すると 、、。
(2) より 。
が実現できることを確かめる。
とする。
- 、：成立
- ：成立
- (1) ：成立
- (2) ：成立
- ：成立
- 、：成立
- の完了は 20：成立
よって最遅開始時刻は 10。
【 の全余裕】
。
答え：