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)