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

各作業の最早開始時刻 $ES$ は、先行作業の最早終了時刻 $EF$（$=ES+$所要日数）の最大値で決まる（先行作業がなければ $0$）。プロジェクトの最短完了日数は、全作業の $EF$ の最大値であり、これは開始から終了までの最長経路（クリティカルパス）の長さに等しい。

当初の計画

• $A$: $ES=0$, $EF=4$
• $B$: $ES=0$, $EF=6$
• $C$: $ES=4$, $EF=7$
• $D$: $ES=4$, $EF=9$
• $E$: $ES=\max (6,7)=7$, $EF=14$
• $F$: $ES=6$, $EF=10$
• $G$: $ES=\max (9,14)=14$, $EF=20$
• $H$: $ES=\max (9,10)=10$, $EF=15$
• $I$: $ES=\max (20,15)=20$, $EF=23$

よって $T_1=23$ である。クリティカルパスは $A\to C\to E\to G\to I$（$4+3+7+6+3=23$）である。

変更後

$B$ は時刻 $3$ に始まり、$F$ の所要日数は $9$ 日になる。

• $A$: $ES=0$, $EF=4$
• $B$: $ES=3$, $EF=9$
• $C$: $ES=4$, $EF=7$
• $D$: $ES=4$, $EF=9$
• $E$: $ES=\max (9,7)=9$, $EF=16$
• $F$: $ES=9$, $EF=18$
• $G$: $ES=\max (9,16)=16$, $EF=22$
• $H$: $ES=\max (9,18)=18$, $EF=23$
• $I$: $ES=\max (22,23)=23$, $EF=26$

よって $T_2=26$ である。このときクリティカルパスは、時刻 $3$ に始まる $B\to F\to H\to I$（$3+6+9+5+3=26$）に変わる。

経路ごとに確かめると、変更後の各経路の長さは
- $A\to C\to E\to G\to I$: $4+3+7+6+3=23$
- $B\to E\to G\to I$: $3+6+7+6+3=25$
- $B\to F\to H\to I$: $3+6+9+5+3=26$
- $A\to D\to G\to I$: $4+5+6+3=18$
- $A\to D\to H\to I$: $4+5+5+3=17$

であり、最大は $26$ である。

答えは $(T_1,T_2)=(23,26)$ である。

各作業の最早開始時刻 (ES) と最早終了時刻 (EF) を前から順に求める。

元の計画 ($T_1$)
- $A$: ES $0$, EF $4$
- $B$: ES $0$, EF $6$
- $C$: ES $4$, EF $7$
- $D$: ES $4$, EF $9$
- $E$: ES $\max (6,7)=7$, EF $14$
- $F$: ES $6$, EF $10$
- $G$: ES $\max (9,14)=14$, EF $20$
- $H$: ES $\max (9,10)=10$, EF $15$
- $I$: ES $\max (20,15)=20$, EF $23$

よって $T_1=23$（クリティカルパス $A\to C\to E\to G\to I$: $4+3+7+6+3=23$）。

変更後 ($T_2$): $B$ の開始は時刻 $3$ 以降、$F$ は $9$ 日。
- $A$: $0\to 4$
- $B$: $3\to 9$
- $C$: $4\to 7$
- $D$: $4\to 9$
- $E$: ES $\max (9,7)=9$, EF $16$
- $F$: ES $9$, EF $18$
- $G$: ES $\max (9,16)=16$, EF $22$
- $H$: ES $\max (9,18)=18$, EF $23$
- $I$: ES $\max (22,23)=23$, EF $26$

よって $T_2=26$（クリティカルパス: $B$(開始3)$\to F\to H\to I$: $3+6+9+5+3=26$）。

検算: 変更後の各経路長 $ACEGI$: $23$、$BEGI$: $3+6+7+6+3=25$、$ADGI$: $18$、$ADHI$: $17$、$BFHI$: $26$。最大は $26$。

答え: $T_1=23,T_2=26$