建設プロジェクトのスケジューリング問題の最適化 PuLP

建設プロジェクトのスケジューリング問題の最適化

建設プロジェクトのスケジューリング問題を考えてみます。

ある建設プロジェクトにおいて、以下の6つの作業が必要です。

🔹作業A: 2週間かかる
🔹作業B: 3週間かかる
🔹作業C: 4週間かかる
🔹作業D: 2週間かかる
🔹作業E: 3週間かかる
🔹作業F: 4週間かかる

作業が開始されたら中断することはできません。さらに、以下の制約があります。

🔹作業A, B, Cは同時に開始することができます。
🔹作業Bが完了した後、作業Dを開始することができます。
🔹作業Cが完了した後、作業Eを開始することができます。
🔹作業DとEは同時に開始するることができます。
🔹作業DとEが完了した後、作業Fを開始できます。

解き方・ソースコード

この問題をPuLPで解いてみます。

問題の設定や解法の詳細はコメントを確認して下さい。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
# 必要なライブラリをインポートする
import pulp

# 問題を定義する
problem = pulp.LpProblem('Construction Project', pulp.LpMinimize)

# 変数を定義する
a = pulp.LpVariable('a', lowBound=0, cat='Continuous')
b = pulp.LpVariable('b', lowBound=0, cat='Continuous')
c = pulp.LpVariable('c', lowBound=0, cat='Continuous')
d = pulp.LpVariable('d', lowBound=0, cat='Continuous')
e = pulp.LpVariable('e', lowBound=0, cat='Continuous')
f = pulp.LpVariable('f', lowBound=0, cat='Continuous')

# 制約式を定義する

# 各作業の所要日数
problem += a >= 2
problem += b >= 3
problem += c >= 4
problem += d >= 2
problem += e >= 3
problem += f >= 4

# 作業A, B, Cは同時に開始することができる
# a + 2 <= dは、作業Dを開始する前に、作業Aが完了している必要があることを表している
# b + 3 <= cは、作業Cを開始する前に、作業Bが完了している必要があることを表している
problem += a + 2 <= d
problem += b + 3 <= c

# 作業Cが完了した後、作業Eを開始する
# c + 4 <= eは、作業Eを開始する前に、作業Cが完了している必要があることを表している
problem += c + 4 <= e

# 作業DとEは同時に開始することができる
# d + 2 <= fは、作業Fを開始する前に、作業Dが完了している必要があることを表している
# e + 3 <= fは、作業Fを開始する前に、作業Eが完了している必要があることを表している
problem += d + 2 <= f
problem += e + 3 <= f

# 目的関数を定義する
problem += f

# 問題を解く
status = problem.solve()

# 結果を表示する
print(f"Status: {pulp.LpStatus[status]}")
print(f"Optimal Solution:")
print(f"\ta: {a.value():.2f}")
print(f"\tb: {b.value():.2f}")
print(f"\tc: {c.value():.2f}")
print(f"\td: {d.value():.2f}")
print(f"\te: {e.value():.2f}")
print(f"\tf: {f.value():.2f}")

# それぞれの作業の開始時期を計算する
start_a = a.value()
start_b = b.value()
start_c = c.value()
start_d = d.value()
start_e = e.value()
start_f = f.value()

# 結果を表示する
print("Task Schedule:")
print(f"\tTask A starts at day {start_a:.2f}")
print(f"\tTask B starts at day {start_b:.2f}")
print(f"\tTask C starts at day {start_c:.2f}")
print(f"\tTask D starts at day {start_d:.2f}")
print(f"\tTask E starts at day {start_e:.2f}")
print(f"\tTask F starts at day {start_f:.2f}")

[実行結果]

Status: Optimal

Optimal Solution:

    a: 2.00

    b: 3.00

    c: 6.00

    d: 11.00

    e: 10.00

    f: 13.00

Task Schedule:

    Task A starts at day 2.00

    Task B starts at day 3.00

    Task C starts at day 6.00

    Task D starts at day 11.00

    Task E starts at day 10.00

    Task F starts at day 13.00

最適解は、作業の完了までの日数を最小化するようにスケジュールが設定された結果であり、最適なスケジュールでの各タスクの開始日を示しています。