(ア)
A,B,CのうちでBが一番時間がかかる。
D,EではEの方が時間がかかるが、EはCが終わっていればよい。
F,GではGが時間がかかる。
よって
B+D+G = 66
である。
所要時間が10分延びるとTminが長くなる作業はCとE。
所要時間が15分延びるとTminが長くなる作業はA。
(イ)
処理Aは、「遅れがない場合の最短時間を計算」する処理である。
このため、Uをすべての作業の集合とし、Uが空集合でない間処理Aを繰り返す。
処理Aは、
かつ
「すべての
についてM(y)がすでに決まっている(P(x)が空集合の場合も含む)」
という条件を満たすxを一つ選ぶ
M(x)の値を、
「すべてのに対するM(y)の中の最大値(P(x)が空集合の場合は0)」
にT(x)を加えたものと決める
集合Uからxを取り除く
である。
処理Bは、「作業wの遅れを1分ずつ増やしながら最短時間が延びるかどうかを判定する」処理である。
だから出力としては変数Dを出力する。初期値は0である。
変数Dは「最短時間が延びないぎりぎりの作業wの遅れ」である。
zは全体の完成に対応する作業である。
(ア)で言ったらHである。
TminをM(z)にする。
TdelayをTminとする。
条件Tmin=Tdelayが成り立つ間、処理Bを繰り返す。
Tmin=Tdelayが成り立つなら、最短時間は延びていない。
処理B
変数Dの値を1増やす。
変数T(w)の値を1増やす。
すべての作業xについて、M(x)の値を決まっていない状態にする。
集合Uをすべての作業の集合とし、Uが空集合でない間処理Cを繰り返す。
処理Cは、
かつ
「すべてのについてM(y)がすでに決まっている(P(x)が空集合の場合も含む)」
という条件を満たすxを一つ選ぶ
M(x)の値を、
「すべてのに対するM(y)の中の最大値(P(x)が空集合の場合は0)」
にT(x)を加えたものと決める
集合Uからxを取り除く
である。
ここでTdelayをM(z)とするのである。
以上が処理B。
コメントを残す