スケジューリング

設例を最後まで解いてみましょう。5つのジョブがすべて工程1→工程2の順に処理されます。

順序を決める

• ① 全部で最小はJ4の工程2＝2。後工程なので、J4を最後尾に決定
• ② 次に小さいのはJ5の工程2＝3。後工程なので、最後尾から2番目に決定
• ③ 次はJ1の工程1＝4。前工程なので、先頭に決定
• ④ 次はJ2の工程2＝5。後工程なので、最後尾から3番目に決定
• ⑤ 残ったJ3が、空いている先頭から2番目に決定

求められた順序は J1 → J3 → J2 → J5 → J4 です。

ガントチャートで総所要時間を出す

最後のJ4が工程2を終えるのが27時間後なので、総所要時間は27です。

J3の工程2に注目してください。J3の工程1は10時間後に終わっていますが、工程2ではJ1の作業が9時間後まで続いています。したがってJ3の工程2は、遅いほうである10時間後から始まります。このように「前の工程が終わった時刻」と「その機械が空く時刻」の遅いほうが開始時刻になる、という読み方が計算の肝です。

2機械のジョブショップの設例を、LPT（最長作業時間）ルールで解いてみます。

LPTなので、それぞれの機械で「待っているなかで作業時間が最長のもの」を選びます。

• ① 機械1を先に使うのはジョブ1とジョブ2。作業時間が長いジョブ1（6）から着手
• ② 機械2を先に使うのはジョブ3とジョブ4。長いジョブ3（4）から着手
• ③ 機械2でジョブ3が終わると、着手できるのはジョブ4だけなのでジョブ4
• ④ 機械1でジョブ1が終わると、着手可能なのはジョブ2とジョブ3。長いジョブ2（5）
• ⑤ 機械2でジョブ4が終わると、着手できるのはジョブ1だけなのでジョブ1
• ⑥ 機械1でジョブ2が終わると、着手可能なのはジョブ3とジョブ4。長いジョブ3（4）
• ⑦ 最後に機械1でジョブ4、機械2でジョブ2

時間軸に並べるとこうなります。

総所要時間は18となります。2台の機械が最初から最後までほぼ空きなく埋まっていることが読み取れます。

ダミー作業の要否は、作業一覧表を見た時点でだいたい判断できます。チェックの勘どころは次の2つです。

• 同じ先行作業をもつ作業が2つ以上あり、それらの後続作業も同じ → 並行を避けるダミーが要る
• ある作業の先行作業の集合が、別の作業の先行作業の集合を含んでいる（たとえばCの先行はA、Dの先行はA・B）→ 順序関係を正すダミーが要る

試験では「このプロジェクトのアローダイアグラムを作成するにはダミーが何本必要か」と直接聞かれることがあります。一覧表の先行作業の欄を縦に眺めて、同じ組み合わせや包含関係を探す、という手順を決めておくと迷いません。

次の設例を最後まで計算してみましょう。作業一覧は次のとおりです。

ノードは、①開始、②Aの完了、③Bの完了、④Cの完了、⑤DとEの完了、⑥Fの完了、⑦全体の完了、の7つになります。

最早結合点時刻（左から加算、合流は大きいほう）

• ①＝0
• ②＝ ①0 ＋ A5 ＝ 5
• ③＝ ①0 ＋ B5 ＝ 5
• ④＝ ②5 ＋ C2 ＝ 7
• ⑤＝ ②5＋D3＝8 と ③5＋E6＝11 のうち大きいほうで 11
• ⑥＝ ③5 ＋ F1 ＝ 6
• ⑦＝ ④7＋G4＝11、⑤11＋H6＝17、⑥6＋I4＝10 のうち最大で 17

ノード⑤が11になるのは、そこから出ていくHがDとEの両方の完了を待つためです。Dは8日後に終わっていても、Eが終わるのは11日後。Hは11日後からしか始められません。

最遅結合点時刻（右から減算、分岐は小さいほう）

• ⑦＝最早と同じで 17
• ④＝ ⑦17 − G4 ＝ 13
• ⑤＝ ⑦17 − H6 ＝ 11
• ⑥＝ ⑦17 − I4 ＝ 13
• ②＝ ④13−C2＝11 と ⑤11−D3＝8 のうち小さいほうで 8
• ③＝ ⑤11−E6＝5 と ⑥13−F1＝12 のうち小さいほうで 5

先ほどの設例（作業A〜I）で、すべての経路の所要日数を出してみます。

最長は17日の B → E → H で、これがクリティカルパスです。プロジェクト全体の所要日数も17日になります。

もう一つの見つけ方でも確かめてみましょう。最早と最遅が一致するノードを拾うと、①（0・0）、③（5・5）、⑤（11・11）、⑦（17・17）です。①→③はB、③→⑤はE、⑤→⑦はH。やはり B → E → H が出てきました。

一方、ノード④は最早7・最遅13で6日間の余裕があります。つまりCやGが多少遅れても全体には響きません。現場の管理者が毎朝いちばんに確認すべきなのは、CやGの進み具合ではなく、B・E・Hが予定どおり進んでいるかということになります。

例1：どの作業を縮めるのが得か

先ほどのプロジェクト（全体17日、クリティカルパスはB→E→H）について、次の3つの案が出てきたとします。

①は効果ゼロです。Aはクリティカルパス上にないので、4日縮めても全体の17日は変わりません。

②は30万円で3日の短縮にとどまります。Eを6日から2日に縮めると、B→E→Hは5＋2＋6＝13日になりますが、そのときA→D→Hが5＋3＋6＝14日となり、クリティカルパスがA→D→Hに乗り換わって全体は14日で止まります。4日短縮したのに、全体は3日しか縮みません。1日あたり7万5千円の計算です。

③は25万円で3日の短縮です。Hを6日から3日に縮めると、B→E→Hは5＋6＋3＝14日、A→D→Hは5＋3＋3＝11日、A→C→Gは11日、B→F→Iは10日となり、全体は14日になります。②と同じ3日の短縮を5万円安く実現できるので、③が最も費用対効果が高いという結論になります。

例2：最短工期を達成する最小費用を求める

次のプロジェクトで、最短のプロジェクト遂行期間を達成するときの最小費用を考えます。

手順1：最短所要期間でアローダイアグラムを描く

全作業を限界まで縮めたとき、経路は A→B→D が 5＋3＋3＝11日、A→C→D が 5＋2＋3＝10日。したがって最短のプロジェクト遂行期間は11日です。

手順2：クリティカルパスを見つける

11日を決めているのは A→B→D です。

手順3：クリティカルパス以外の作業の余裕を確かめる

ここが勝負どころです。Cはクリティカルパス上にないので、限界の2日まで縮める必要がありません。A→C→D が 11日以内に収まればよいので、5＋C＋3 ≦ 11、つまりCは3日まで縮めれば十分です。余計に1日縮めても工期は変わらないのに、50万円だけ余計にかかってしまいます。

手順4：必要短縮期間×単位当たり短縮費用を合計する

答えは790万円です。Cを最短の2日まで縮めて計算すると840万円になってしまいます。「クリティカルパス以外は、必要な分だけ縮めればよい」という手順3を飛ばさないことが、この問題を落とさないための唯一のコツです。