オペレーションズ・リサーチの問題

あるプロジェクトは作業 $A,B,C,D,E$ の $5$ つからなる。各作業の所要時間（単位は時間）と先行作業（その作業を始める前にすべて終わっていなければならない作業）は次のとおりである。

プロジェクトは時刻 $0$ に開始する。どの作業も、先行作業がすべて終わればすぐに始められ、同時に進められる作業の数に制限はないものとする。プロジェクトの最短完了時刻（時間）と、作業 $C$ の全余裕（時間）を、この順に組で答えよ。

あるプロジェクトは作業 $A,B,C,D,E$ の $5$ つからなる。各作業の所要日数と先行作業は次の表のとおりである。先行作業とは、その作業を始める前にすべて終わっていなければならない作業のことである。

プロジェクトは時刻 $0$ に始まり、すべての作業が終わった時点で完了する。各作業は、先行作業がすべて終わればすぐに始められる。また、同時に進められる作業の数に制限はないものとする。

このプロジェクトの最短完了時刻（日）と、作業 $D$ の全余裕（日）を、この順に組で求めよ。

あるプロジェクトは作業 $1$ から作業 $8$ までの $8$ つの作業からなる。各作業の所要日数と先行作業（その作業を始める前にすべて終わっていなければならない作業）は次のとおりである。

各作業は、先行作業がすべて終わればすぐに始めることができ、同時に進められる作業の数に制限はない。プロジェクトは時刻 $0$ に始まり、すべての作業が終わった時点で完了する。プロジェクトの完了時刻を最も早い値にしたとき、全余裕（最遅開始時刻と最早開始時刻の差）が $0$ である作業の番号の集合を求めよ。

あるプロジェクトは作業 $A,B,C,D,E,F,G,H,I$ の $9$ つからなる。各作業の所要日数と先行作業（その作業を始める前にすべて終わっていなければならない作業）は次のとおりである。

プロジェクトは時刻 $0$ に始まり、各作業は先行作業がすべて終わればすぐに始められ、同時に進められる作業の数に制限はないものとする。

この計画どおりのときのプロジェクトの最短完了日数を $T_1$ とする。次に、作業 $B$ は時刻 $3$ より前には始められず、さらに作業 $F$ の所要日数が $9$ 日に増えたとする（ほかの条件は変わらない）。このときのプロジェクトの最短完了日数を $T_2$ とする。$T_1,T_2$ をこの順に求めよ。

あるプロジェクトは作業 $A,B,C,D,E,F,G,H$ の $8$ つからなる。各作業の所要日数と先行作業（その作業を始める前にすべて終わっていなければならない作業）は次のとおりである。

さらに、作業の開始時刻について次の $2$ つの制約がある。

• 制約 $(1)$：作業 $G$ は、作業 $D$ の開始から $10$ 日以上たってから開始する。
• 制約 $(2)$：作業 $F$ は、作業 $C$ の開始から $3$ 日以内に開始する（$F$ の開始時刻は $C$ の開始時刻に $3$ を足した値以下である）。

プロジェクトの開始時刻を $0$ とし、各作業 $X$ の開始時刻を $s_X(\geqq 0)$ とする。各作業は開始したら中断せずに所要日数で終わり、作業は同時にいくつでも並行して行える。上の先行関係と制約 $(1)$、$(2)$ をすべて満たすスケジュールのうち、すべての作業が終わる時刻が最も早いものを考え、その時刻を最短完了日数 $T$ とする。

また、作業 $X$ の最早開始時刻を「すべての条件を満たすスケジュールにおける $s_X$ の最小値」、最遅開始時刻を「すべての条件を満たし、かつすべての作業が時刻 $T$ までに終わるスケジュールにおける $s_X$ の最大値」とし、全余裕を（最遅開始時刻）$-$（最早開始時刻）と定める。

最短完了日数 $T$ と、作業 $F$ の全余裕を、この順に組で求めよ。