14  時間とコストのトレードオフ

14.1 学習目標

  • 時間とコストのトレードオフ問題を理解する．
  • 作業の開始時刻と短縮時間を決定変数として，この問題を線形計画問題として定式化できる．
  • 定式化した線形計画問題をソルバーで解き，結果を解釈できる．

14.2 時間とコストのトレードオフとは

プロジェクトの所要時間を短縮するために，追加のコストをかけて作業時間を短縮することができる場合がある．このような場合，決められた期限までに最小のコストでプロジェクトを完了するには，どの作業をどれだけ短縮すればよいかを決定する問題を考える．

14.3 問題の定式化

プロジェクト・ネットワーク G = (V, E) の各作業点 i \in V に対して，次のパラメータが与えられるとする．

  • \tau_i: 作業 i の標準所要時間
  • c_i: 作業 i の単位時間あたりの短縮コスト
  • M_i: 作業 i の最大短縮時間

始点 s と終点 t については，\tau_s = \tau_t = 0，c_s = c_t = 0，M_s = M_t = 0 とする．また，プロジェクトの完了時刻の上限を T とする．

決定変数は次の通りである．

  • y_i: 作業 i の開始時刻
  • x_i: 作業 i の短縮時間

プロジェクトの所要時間を短縮するためのコストは

\sum_{i \in V} c_i x_i

で与えられる．j が i の後続作業である場合，作業 j は作業 i が終了するまで開始できない．作業 i の終了時刻は y_i + \tau_i - x_i であるから，

y_j \geq y_i + \tau_i - x_i, \quad \forall (i, j) \in E

が成り立つ．また，各作業の最大短縮時間 M_i により，すべての作業 i \in V について，

0 \leq x_i \leq M_i

である．プロジェクト全体の完了時刻は終点 t の開始時刻 y_t であり，これが上限 T 以下である必要があるから，

y_t \leq T

である．始点 s の開始時刻は 0 とするから，

y_s = 0

である．

以上より，この問題は次の線形計画問題として定式化できる．

\begin{alignedat}{2} \text{minimize} \quad & \sum_{i \in V} c_i x_i \\ \text{subject to} \quad & y_j \geq y_i + \tau_i - x_i, &\qquad& \forall (i, j) \in E \\ & 0 \leq x_i \leq M_i, && \forall i \in V \\ & y_t \leq T \\ & y_s = 0 \end{alignedat}

例 14.1 プロジェクト・ネットワークはグラフ G = (V, E) で表す．点の集合は

V = \{s, t, \mathrm{A}, \mathrm{B}, \mathrm{C}, \mathrm{D}, \mathrm{E}\}

であり，辺の集合は

E = \{(s, \mathrm{A}), (s, \mathrm{C}), (\mathrm{A}, \mathrm{B}), (\mathrm{C}, \mathrm{D}), (\mathrm{B}, \mathrm{E}), (\mathrm{D}, \mathrm{E}), (\mathrm{E}, t)\}

である．ここで，s は始点，t は終点である．時間の単位は日とし，プロジェクト全体の所要時間の上限を T = 10 日とする．

各作業の標準所要時間 \tau_i，単位時間あたりの短縮コスト c_i，最大短縮時間 M_i は 表 14.1 のように与えられる．

表 14.1: 各作業の標準所要時間，単位時間あたりの短縮コスト，最大短縮時間
作業 \tau_i c_i M_i
A 7 100 3
B 3 150 1
C 6 200 2
D 3 200 2
E 2 250 1

この問題を次のように定式化できる．

\begin{aligned} \text{minimize} \quad & 100 x_{\mathrm{A}} + 150 x_{\mathrm{B}} + 200 x_{\mathrm{C}} + 200 x_{\mathrm{D}} + 250 x_{\mathrm{E}} \\ \text{subject to} \quad & y_{\mathrm{A}} \geq 0 \\ & y_{\mathrm{C}} \geq 0 \\ & y_{\mathrm{B}} \geq y_{\mathrm{A}} + 7 - x_{\mathrm{A}} \\ & y_{\mathrm{D}} \geq y_{\mathrm{C}} + 6 - x_{\mathrm{C}} \\ & y_{\mathrm{E}} \geq y_{\mathrm{B}} + 3 - x_{\mathrm{B}} \\ & y_{\mathrm{E}} \geq y_{\mathrm{D}} + 3 - x_{\mathrm{D}} \\ & y_t \geq y_{\mathrm{E}} + 2 - x_{\mathrm{E}} \\ & 0 \leq x_{\mathrm{A}} \leq 3 \\ & 0 \leq x_{\mathrm{B}} \leq 1 \\ & 0 \leq x_{\mathrm{C}} \leq 2 \\ & 0 \leq x_{\mathrm{D}} \leq 2 \\ & 0 \leq x_{\mathrm{E}} \leq 1 \\ & y_t \leq 10 \\ & y_s = 0 \end{aligned}

この線形計画問題は，最適化ソルバーを用いて解くことができる．以下に Gurobi を用いた実装例を示す．Gurobi のインストール方法と基本的な使い方は チャプター 3 を参照されたい．

import gurobipy as gp
from gurobipy import GRB

# データ：各点の [tau, c, M]（始点 s と終点 t はすべて 0）
V, tau, c, M = gp.multidict(
    {
        "s": [0, 0, 0],
        "A": [7, 100, 3],
        "B": [3, 150, 1],
        "C": [6, 200, 2],
        "D": [3, 200, 2],
        "E": [2, 250, 1],
        "t": [0, 0, 0],
    }
)
E = [("s", "A"), ("s", "C"), ("A", "B"), ("C", "D"), ("B", "E"), ("D", "E"), ("E", "t")]
T = 10

# モデルの作成
m = gp.Model("Project_Crashing")

# 決定変数（0 <= x_i <= M_i は x の下限と上限で表す）
y = m.addVars(V, name="y")
x = m.addVars(V, ub=M, name="x")

# 目的関数
m.setObjective(x.prod(c), GRB.MINIMIZE)

# 先行関係の制約
m.addConstrs((y[j] >= y[i] + tau[i] - x[i] for i, j in E), name="prec")

# 完了時刻の上限
m.addConstr(y["t"] <= T, name="deadline")

# 始点の開始時刻
m.addConstr(y["s"] == 0, name="start")

# 最適化
m.optimize()

# 結果の表示
if m.Status == GRB.OPTIMAL:
    print(f"Obj: {m.ObjVal:g}")
    for i in V:
        print(f"{i}: y = {y[i].X:g}, x = {x[i].X:g}")
else:
    print("No optimal solution found")

実行すると，ソルバーのログに続いて次のように出力される．

Obj: 350
s: y = 0, x = 0
A: y = 0, x = 1
B: y = 6, x = 0
C: y = 0, x = 0
D: y = 6, x = 0
E: y = 9, x = 1
t: y = 10, x = 0

この結果から，作業 A を 1 日，作業 E を 1 日短縮することで，最小コスト 350 でプロジェクトを 10 日以内に完了できることがわかる．

14.4 まとめ

  • 追加のコストをかけて作業時間を短縮できる場合に，期限 T までにプロジェクトを完了する最小コストを求める問題を考える．
  • 決定変数は，作業 i の開始時刻 y_i と短縮時間 x_i である．
  • 目的関数は短縮コストの合計 \sum_{i \in V} c_i x_i であり，制約条件は先行関係 y_j \geq y_i + \tau_i - x_i，短縮時間の範囲 0 \leq x_i \leq M_i，期限 y_t \leq T，および始点の開始時刻 y_s = 0 である．
  • 目的関数と制約条件がすべて線形であるため，この問題は線形計画問題であり，ソルバーで解くことができる．

14.5 練習問題

練習 14.1 表 14.2 は，練習 12.1 のプロジェクトの各作業について，単位時間あたりの短縮コストと最大短縮時間を与えたものである．時間の単位は日とし，プロジェクト全体の所要時間の上限を T = 20 日とする．以下の問いに答えよ．

表 14.2: 作業 A〜H の先行作業，標準所要時間，単位時間あたりの短縮コスト，最大短縮時間
作業 先行作業 \tau_i c_i M_i
A - 5 150 2
B - 3 150 1
C A 7 50 2
D A 6 100 1
E B 7 100 2
F D, E 3 200 1
G E 10 100 3
H C, F 8 300 2
  1. 例 14.1 にならって，この問題を線形計画問題として定式化せよ．
  2. 始点 s から終点 t までのすべてのパスとその長さを求めよ．また，プロジェクトを 20 日以内に完了するために，各パスを少なくとも何日短縮する必要があるか答えよ．
  3. 最小のコストでプロジェクトを 20 日以内に完了するには，どの作業を何日短縮すればよいかを，2. の結果を用いて手計算で求めよ．また，そのときのコストを求めよ．