技能一覧 › 大学数学 オペレーションズ・リサーチ

プロジェクトの工期短縮（クラッシング）

各作業の 1 日あたり短縮費用と短縮上限から、すべてのクリティカルパスを同時に短くする最も安い組合せを選び、目標工期を達成するための追加費用の最小値を求められる

前提

• PERT の最早・最遅開始時刻とクリティカルパス （大学数学 オペレーションズ・リサーチ）

説明

なぜそうしてよいのか

手順

1. 前提の技能ですべてのパスの長さを求め、最短完了時刻とすべてのクリティカルパス（最長のパス）を求める。

2. 1 日縮める候補を挙げる。すべてのクリティカルパスが正味 1 日以上短くなるように、短縮上限に達していない作業を 1 日短くする組合せを考える。すでに短縮した作業を 1 日戻す変更（費用はマイナスとして数える）を含めた組合せも候補にする。

3. 候補のうち費用の合計が最小のものを選んで実行し、各作業の所要日数・短縮上限の残り・費用の累計を更新する。

4. 更新後の所要日数でパスの長さを計算し直し、新しいクリティカルパスを求める。

5. 完了時刻が目標工期になるまで手順 2〜4 をくり返す。途中でどの候補も作れなくなったら、その目標工期は達成できない。

6. 確認として、各作業の短縮日数を $x_{\text{作業}}$ とおき、各パスについて $(\text{短縮日数の合計})\ge (\text{パスの長さ})-(\text{目標工期})$ を立てる。短縮上限の範囲で場合分けして費用の最小値を求め、手順 5 の累計と一致することを確かめる。

例題

よくある誤り

• クリティカルパスが複数あるのに、1 本だけを縮めてしまう誤り。例題の 2 回目に最も安い C（1 万円）だけを縮めると、$A\to C$ は 8 日になりますが $A\to D$ は 9 日のままで、完了時刻は縮みません。正しくは、すべてのクリティカルパスを縮める組合せ（C と D、または A）の中から最も安いものを選びます。

• クリティカルパス上にない作業を、費用が安いからといって短くしてしまう誤り。例題のはじめに B（2 万円）を縮めても $B\to D$ が 8 日になるだけで、完了時刻は 10 日のままです。正しくは、クリティカルパス上の作業だけを候補にします。

• 何日分もまとめて縮めてしまい、新しく生じるクリティカルパスを見落とす誤り。例題で D を一度に 2 日縮めれば 10 日から 8 日になると考えても、$A\to C$ が 9 日のまま残り、完了時刻は 9 日にしかなりません（費用は 4 万円）。正しくは、1 日ずつ縮めて、そのたびにクリティカルパスを求め直します。

• 必要な条件を一部のパスだけで考え、最小性の確認を誤る誤り。たとえば「A を 2 日縮めれば 8 日になる」と考えても、$B\to D$ は 9 日のまま残ります。正しくは、$x_A+x_C\ge 1,x_A+x_D\ge 2,x_B+x_D\ge 1$ のようにすべてのパスについて条件を立て、短縮上限 $0\le x\le 2$ も守って比べます（A を 2 日縮める場合は B か D も縮める必要があり、10 万円以上かかります）。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

• 難易度 1（教科書の例題レベル）

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

  作業	先行作業	通常の所要日数	短縮できる最大日数	1日あたりの短縮費用（万円）
  $A$	なし	$3$	$1$	$3$
  $B$	なし	$5$	$2$	$2$
  $C$	$A$	$4$	$2$	$5$
  $D$	$B$	$2$	$1$	$4$
  $E$	$C,D$	$3$	$1$	$8$

  各作業は $1$ 日単位で短縮でき、短縮費用は短縮した日数に比例する。プロジェクト全体の完了までの日数を $8$ 日にするために必要な追加費用の最小値は何万円か。

• 難易度 1（教科書の例題レベル）

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

  作業	通常の所要日数	先行作業	短縮できる最大日数	1日あたりの短縮費用（万円）
  $A$	$4$	なし	$1$	$3$
  $B$	$6$	なし	$2$	$2$
  $C$	$5$	$A$	$2$	$5$
  $D$	$3$	$B$	$1$	$4$
  $E$	$2$	$C,D$	$1$	$6$

  各作業は $1$ 日単位で短縮でき、短縮費用は短縮日数に比例するものとする。プロジェクトの完了までの日数を $9$ 日にするために必要な追加費用の最小値は何万円か。

• 難易度 1（教科書の例題レベル）

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

  作業	通常の所要日数	先行作業	短縮できる最大日数	$1$ 日あたりの短縮費用（万円）
  $A$	$3$	なし	$1$	$4$
  $B$	$5$	なし	$2$	$3$
  $C$	$4$	$A$	$2$	$2$
  $D$	$2$	$B$	$1$	$2$
  $E$	$3$	$C,D$	$1$	$6$

  短縮は $1$ 日単位で行い、短縮費用は短縮した日数に比例するものとする。プロジェクト全体の完了までの日数を $8$ 日にするために必要な追加費用の最小値は何万円か。

この技能を使う問題

• 難易度 4（大学院入試の標準レベル）

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

  作業	通常の所要日数	先行作業	1 日短縮あたりの追加費用（万円）	短縮できる最大日数
  $A$	$4$	なし	$5$	$1$
  $B$	$6$	なし	$2$	$2$
  $C$	$5$	$A$	$3$	$2$
  $D$	$3$	$A$	$4$	$1$
  $E$	$4$	$B,D$	$6$	$2$
  $F$	$3$	$C,E$	$10$	$1$

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

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

• 難易度 4（大学院入試の標準レベル）

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

  作業	通常の所要日数	先行作業	最大短縮日数	$1$ 日あたりの短縮費用
  $A$	$4$	なし	$1$	$30$
  $B$	$6$	なし	$2$	$20$
  $C$	$5$	$A$	$2$	$25$
  $D$	$3$	$A$	$1$	$10$
  $E$	$4$	$B,D$	$2$	$15$
  $F$	$3$	$C,E$	$1$	$40$

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