PERT の最早・最遅開始時刻とクリティカルパス

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

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

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

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

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

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

計画の開始時刻を $0$ とし、各作業は先行作業がすべて終わればすぐに始められ、作業どうしは同時に並行して進められるものとする。また、計画全体を最短完了時刻までに終えるものとして最遅開始時刻を考える。この計画の最短完了時刻と、作業 $C$ の最遅開始時刻を、この順に組で求めよ。

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

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

$n\ge 2$ を整数とし、頂点集合 $\{1,2,\dots ,n\}$ と有向辺の集合 $\mathcal{A}$ からなる有向グラフ（PERT のアローダイアグラム）を考える。各辺 $(i,j)\in \mathcal{A}$ は $i<j$ を満たし、作業時間 $d_{ij}$（実数）をもつ。また、$j=2,3,\dots ,n$ のどの頂点 $j$ にも、$j$ に入る辺 $(i,j)\in \mathcal{A}$ が少なくとも 1 本あるとする。

最早結合点時刻 $E(1),E(2),\dots ,E(n)$ を
$$E(1)=0,E(j)=\underset{i:(i,j)\in \mathcal{A}}{\max }(E(i)+d_{ij})(j=2,3,\dots ,n)$$
により $j$ の小さい順に定める。また、頂点 $1$ から頂点 $j$ への有向路（辺を 0 本以上つないだもの。$1$ から $1$ へは辺を 1 本も含まない路だけを考える）について、含まれる辺の作業時間の和をその路の長さとよぶ。

各 $j=1,2,\dots ,n$ について、頂点 $1$ から頂点 $j$ への有向路が存在し、$E(j)$ はそれらの有向路の長さの最大値に等しいことを証明せよ。

あるプロジェクトは作業 $A,B,C,D,E,F,G$ の $7$ つからなる。各作業の所要日数には、楽観値 $a$、最可能値 $m$、悲観値 $b$ の $3$ つの見積もりが与えられている。先行作業とは、その作業を始める前にすべて終わっていなければならない作業のことである。

PERT の手法に従い、各作業の所要日数の期待値 $t_e$ と分散 ${\sigma }^2$ を
$$t_e=\frac{a+4m+b}{6},{\sigma }^2={\left(\frac{b-a}{6}\right)}^2$$
で定める。各作業の所要日数を $t_e$ として最早開始時刻を計算し、プロジェクトの完了時刻（期待値）$T$ とクリティカルパスを求める。さらに、クリティカルパス上の作業の所要日数は互いに独立であるとして、クリティカルパス上の作業の分散の和 $V$ を求める。

$T$ と $V$ をこの順に組 $(T,V)$ で答えよ。なお、プロジェクトは時刻 $0$ に開始し、先行作業がすべて終わればその作業はすぐに開始できるものとする。

あるプロジェクトは作業 $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$ の全余裕を、この順に組で求めよ。

あるプロジェクトは作業 $A,B,C,D,E,F$ の $6$ つからなる。各作業の通常の所要日数、先行作業（その作業を始める前にすべて終わっていなければならない作業）、および短縮のデータは次のとおりである。

各作業は、先行作業がすべて終わればすぐに始められ、同時に進められる作業の数に制限はない。各作業の所要日数は $1$ 日単位で、表の「短縮できる最大日数」まで短縮でき、追加費用は短縮した日数に比例する。

プロジェクト全体の所要日数（すべての作業が終わるまでの日数）を $11$ 日以下にするために必要な追加費用の合計の最小値は何万円か。

あるプロジェクトは作業 $A,B,C,D,E,F$ の $6$ つからなる。各作業の通常の所要日数、先行作業（その作業を始める前にすべて終わっていなければならない作業）、短縮できる最大日数、$1$ 日短縮するごとにかかる追加費用（千円）は次のとおりである。

各作業について短縮日数 $s$ を $0$ 以上その作業の最大短縮日数以下の整数から作業ごとに独立に選ぶ。このとき、その作業の所要日数は（通常の所要日数）$-s$ 日になり、追加費用は（$1$ 日あたりの短縮費用）$\times s$ 千円かかる。各作業は先行作業がすべて終わりしだい直ちに開始でき、同時に進められる作業の数に制限はない。プロジェクトの開始からすべての作業が完了するまでの日数を $11$ 日以下にするとき、$6$ つの作業の追加費用の合計の最小値（千円）を求めよ。

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

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

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