Scheduling Problems
本章ではいくつかの典型的スケジューリング問題の例とその定式化について扱います。
from amplify_sched import *
token = "xxxxxxxxxxxxxxxxxxxxxxxxx"
Flow Shop Scheduling
Flow Shop Scheduling はスケジューリング問題の一種で以下のように定義されます
定義
m 台の Machine(M_1, M_2, …, M_m)で n 個の Job(J_1, J_2, …, J_n)を処理する
各 Job は m 台すべての Machine を\(M_1\)から順に処理し、これらの Machine の処理順序はすべての Job で同一である
各 Job の各 Machine における処理時間はそれぞれ与えられる
このとき与えられた評価尺度を最適にするような Job の処理順序を求める問題
定式化例
下記の Flow Shop Scheduling の定式化とメイクスパンの最適化を Amplify Sched で行います。
Job name |
Process |
Machine name |
Processing Time |
|---|---|---|---|
J1 |
0 |
M1 |
10 |
J1 |
1 |
M2 |
15 |
J1 |
2 |
M3 |
20 |
J2 |
0 |
M1 |
15 |
J2 |
1 |
M2 |
20 |
J2 |
2 |
M3 |
10 |
J3 |
0 |
M1 |
10 |
J3 |
1 |
M2 |
20 |
J3 |
2 |
M3 |
15 |
model = Model()
model.jobs.add("J1")
model.jobs.add("J2")
model.jobs.add("J3")
model.machines.add("M1")
model.machines.add("M2")
model.machines.add("M3")
model.jobs["J1"].append(Task())
model.jobs["J1"][0].processing_times["M1"] = 10
model.jobs["J1"].append(Task())
model.jobs["J1"][1].processing_times["M2"] = 15
model.jobs["J1"].append(Task())
model.jobs["J1"][2].processing_times["M3"] = 20
model.jobs["J2"].append(Task())
model.jobs["J2"][0].processing_times["M1"] = 15
model.jobs["J2"].append(Task())
model.jobs["J2"][1].processing_times["M2"] = 20
model.jobs["J2"].append(Task())
model.jobs["J2"][2].processing_times["M3"] = 10
model.jobs["J3"].append(Task())
model.jobs["J3"][0].processing_times["M1"] = 10
model.jobs["J3"].append(Task())
model.jobs["J3"][1].processing_times["M2"] = 20
model.jobs["J3"].append(Task())
model.jobs["J3"][2].processing_times["M3"] = 15
gantt = model.solve(token=token, timeout=1)
gantt.timeline(machine_view=True)
Job Shop Scheduling
Job Shop Scheduling はスケジューリング問題の一種で以下のように定義されます。
定義
m 台の Machine(M_1, M_2, …, M_m)で n 個の Job(J_1, J_2, …, J_n)を処理する。
各 Job はすべての Machine で一度ずつ処理されるが、その処理順序は Job ごとに異なってもよい
各 Job の各 Machine における処理時間はそれぞれ与えられる
このとき与えられた評価尺度を最適にするような各 Task の開始時刻を求める問題
定式化例
下記の Job Shop Scheduling の定式化とメイクスパンの最適化を Amplify Sched で行います。
Job name |
Process |
Machine name |
Processing Time |
|---|---|---|---|
Job A |
0 |
Machine X |
10 |
Job A |
1 |
Machine Y |
20 |
Job A |
2 |
Machine Z |
15 |
Job B |
0 |
Machine Y |
10 |
Job B |
1 |
Machine Z |
20 |
Job B |
2 |
Machine X |
15 |
Job C |
0 |
Machine Z |
10 |
Job C |
1 |
Machine X |
20 |
Job C |
2 |
Machine Y |
15 |
Job D |
0 |
Machine Z |
10 |
Job D |
1 |
Machine Y |
20 |
Job D |
2 |
Machine X |
15 |
model = Model()
model.jobs.add("Job A")
model.jobs.add("Job B")
model.jobs.add("Job C")
model.jobs.add("Job D")
model.machines.add("Machine X")
model.machines.add("Machine Y")
model.machines.add("Machine Z")
model.jobs["Job A"].append(Task())
model.jobs["Job A"][0].processing_times["Machine X"] = 10
model.jobs["Job A"].append(Task())
model.jobs["Job A"][1].processing_times["Machine Y"] = 20
model.jobs["Job A"].append(Task())
model.jobs["Job A"][2].processing_times["Machine Z"] = 15
model.jobs["Job B"].append(Task())
model.jobs["Job B"][0].processing_times["Machine Y"] = 10
model.jobs["Job B"].append(Task())
model.jobs["Job B"][1].processing_times["Machine Z"] = 20
model.jobs["Job B"].append(Task())
model.jobs["Job B"][2].processing_times["Machine X"] = 15
model.jobs["Job C"].append(Task())
model.jobs["Job C"][0].processing_times["Machine Z"] = 10
model.jobs["Job C"].append(Task())
model.jobs["Job C"][1].processing_times["Machine X"] = 20
model.jobs["Job C"].append(Task())
model.jobs["Job C"][2].processing_times["Machine Y"] = 15
model.jobs["Job D"].append(Task())
model.jobs["Job D"][0].processing_times["Machine Z"] = 10
model.jobs["Job D"].append(Task())
model.jobs["Job D"][1].processing_times["Machine Y"] = 20
model.jobs["Job D"].append(Task())
model.jobs["Job D"][2].processing_times["Machine X"] = 15
gantt = model.solve(token=token, timeout=1)
gantt.timeline(machine_view=True)
Flexible Job Shop Scheduling
Flexible Job Shop Scheduling はスケジューリング問題の一種で以下のように定義されます
定義
m 台の Machine(M_1, M_2, …, M_m)で n 個の Job(J_1, J_2, …, J_n)を処理する
各 Job の各 Process は指定されたの Machine で処理される。このときその Process を処理できる Machine の候補を複数定義できる
各 Job の各 Machine における処理時間はそれぞれ与えられる
このとき与えられた評価尺度を最適にするような各 Task の開始時刻と Machine の割り当てを求める問題
定式化例
下記の Flexible Job Shop Scheduling の定式化とメイクスパンの最適化を Amplify Sched で行います。
Job name |
Process |
Machine name |
Processing Time |
|---|---|---|---|
Job A |
0 |
Machine X |
10 |
Job A |
0 |
Machine Y |
5 |
Job B |
0 |
Machine X |
15 |
Job B |
0 |
Machine Y |
2 |
Job C |
0 |
Machine Z |
10 |
Job C |
0 |
Machine Y |
1 |
Job A |
1 |
Machine X |
20 |
Job A |
1 |
Machine Y |
10 |
Job B |
1 |
Machine Z |
20 |
Job B |
1 |
Machine Y |
10 |
Job C |
1 |
Machine X |
20 |
Job C |
1 |
Machine Z |
10 |
Job A |
2 |
Machine Z |
15 |
Job B |
2 |
Machine X |
15 |
Job C |
2 |
Machine Y |
15 |
model = Model()
model.jobs.add("Job A")
model.jobs.add("Job B")
model.jobs.add("Job C")
model.machines.add("Machine X")
model.machines.add("Machine Y")
model.machines.add("Machine Z")
model.jobs["Job A"].append(Task())
model.jobs["Job A"][0].processing_times["Machine X"] = 10
model.jobs["Job A"][0].processing_times["Machine Y"] = 5
model.jobs["Job B"].append(Task())
model.jobs["Job B"][0].processing_times["Machine X"] = 15
model.jobs["Job B"][0].processing_times["Machine Y"] = 2
model.jobs["Job C"].append(Task())
model.jobs["Job C"][0].processing_times["Machine Z"] = 10
model.jobs["Job C"][0].processing_times["Machine Y"] = 1
model.jobs["Job A"].append(Task())
model.jobs["Job A"][1].processing_times["Machine X"] = 20
model.jobs["Job A"][1].processing_times["Machine Y"] = 10
model.jobs["Job B"].append(Task())
model.jobs["Job B"][1].processing_times["Machine Z"] = 20
model.jobs["Job B"][1].processing_times["Machine Y"] = 10
model.jobs["Job C"].append(Task())
model.jobs["Job C"][1].processing_times["Machine X"] = 20
model.jobs["Job C"][1].processing_times["Machine Z"] = 10
model.jobs["Job A"].append(Task())
model.jobs["Job A"][2].processing_times["Machine Z"] = 15
model.jobs["Job B"].append(Task())
model.jobs["Job B"][2].processing_times["Machine X"] = 15
model.jobs["Job C"].append(Task())
model.jobs["Job C"][2].processing_times["Machine Y"] = 15
gantt = model.solve(token=token, timeout=1)
gantt.timeline(machine_view=True)