スケジューリング最適化
スケジューリング最適化の例題を考えます。
複数のジョブを複数のマシンで実行する場合のスケジューリングを最適化する問題です。
各ジョブには処理を実行するために必要な時間があり、各マシンには同時に実行できるジョブの数に制限があります。
目的は、すべてのジョブを完了するのに必要な最小時間を見つけることです。
例えば、4つのジョブと2つのマシンがあり、以下のような情報が与えられたとします。
| ジョブ | 時間 | 必要なマシン数 |
|---|
| A | 2 | 1 |
| B | 3 | 1 |
| C | 2 | 2 |
| D | 4 | 2 |
解き方・ソースコード
この問題を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
| import pulp
problem = pulp.LpProblem("Job Scheduling", pulp.LpMinimize)
A_1 = pulp.LpVariable("A_1", lowBound=0, cat='Binary')
A_2 = pulp.LpVariable("A_2", lowBound=0, cat='Binary')
B_1 = pulp.LpVariable("B_1", lowBound=0, cat='Binary')
B_2 = pulp.LpVariable("B_2", lowBound=0, cat='Binary')
C_1 = pulp.LpVariable("C_1", lowBound=0, cat='Binary')
C_2 = pulp.LpVariable("C_2", lowBound=0, cat='Binary')
D_1 = pulp.LpVariable("D_1", lowBound=0, cat='Binary')
D_2 = pulp.LpVariable("D_2", lowBound=0, cat='Binary')
problem += 2*A_1 + 2*A_2 + 3*B_1 + 3*B_2 + 2*C_1 + 2*C_2 + 4*D_1 + 4*D_2
problem += A_1 + A_2 == 1
problem += B_1 + B_2 == 1
problem += C_1 + C_2 == 1
problem += D_1 + D_2 == 1
problem += A_1 + B_1 + C_1 + D_1 <= 2
problem += A_2 + B_2 + C_2 + D_2 <= 2
status = problem.solve()
print("Status:", pulp.LpStatus[status])
print("Minimum Time:", pulp.value(problem.objective))
print("A_1:", pulp.value(A_1))
print("A_2:", pulp.value(A_2))
print("B_1:", pulp.value(B_1))
print("B_2:", pulp.value(B_2))
print("C_1:", pulp.value(C_1))
print("C_2:", pulp.value(C_2))
print("D_1:", pulp.value(D_1))
print("D_2:", pulp.value(D_2))
|
①problemオブジェクトを作成し、最小化問題であることを示します。
②各ジョブをどのマシンで実行するかを決定する変数を作成します。
各変数は、0または1の2値をとります。
③目的関数を定義します。
すべてのジョブが完了するのに必要な時間を最小化するように設定しています。
④制約条件(1)を定義します。
各ジョブは1つのマシンで実行されなければならず、各マシンは同時に実行できます。
⑤制約条件(2)を定義します。
ジョブの数に制限があることを示します。
⑥問題を解きます。
⑦結果を表示します。
最適なスケジュールを決定するための変数の値と、最小化された時間を表示します。
このコードを実行すると、以下のような結果が得られます。
[実行結果]
Status: Optimal
Minimum Time: 11.0
A_1: 1.0
A_2: 0.0
B_1: 1.0
B_2: 0.0
C_1: 0.0
C_2: 1.0
D_1: 0.0
D_2: 1.0
この結果から、最小時間は11であり、次のようなスケジュールが最適であることがわかります。
🔹ジョブAをマシン1で、ジョブBをマシン1で、ジョブCをマシン2で、ジョブDをマシン2で実行する。
