お題
国立情報学研究所の宇野先生のスケジューリング問題を解いてみましょう。
たくさんある工程(スープ、焼鳥、…)を、いろいろなリソース(人、コンロ、包丁、オーブン)を使って、なるべく早く完成させます。
定式化して汎用ソルバーで解けますが、大変なので、スケジューリング専用ソルバーOptSeqを使います。有料ですが、変数15までは無料の試用版で解けます。
インストールや使い方は、スケジューリング最適化ソルバー OptSeq IIを見てください。
Pythonで解く
一々名前を指定しなくてもいいように、補助関数を定義します。
python
from more_itertools import pairwise
from optseq import *
def addResource(m, capacity=1, name=None, addResource_count=[0]):
if name is None:
addResource_count[0] += 1
name = f'R{addResource_count[0]}'
return m.addResource(name, capacity=capacity)
def addMode(dur, res=[], name=None, addMode_count=[0]):
if name is None:
addMode_count[0] += 1
name = f'M{addMode_count[0]}'
md = Mode(name, dur)
for r in res:
md.addResource(r, requirement=1)
return md
def addActivity(m, dur, res=[], name=None, addActivity_count=[0]):
if name is None:
addActivity_count[0] += 1
name = f'A{addActivity_count[0]}'
ac = m.addActivity(name)
md = addMode(dur, res)
ac.addModes(md)
return ac
実際にモデルを作って解いてみましょう。
4つのリソース(人、コンロ、包丁、オーブン)の組合せを1つの数字で表せるように、それぞれ 1,2,4,8 とします。「'スープ': [(5,10),…]」の5は、1(人)と4(包丁)の両方を使うことを表します。10は、作業時間(分)です。
python
# 1:人, 2:コンロ, 4:包丁, 8:オーブン
prm = {'スープ': [(5,10),(3,10),(0,20),(0,20)],
'焼鳥': [(5,10),(9,20),(3,10)],
'魚料理': [(3,10),(9,30)],
'温野菜': [(5,20),(3,10)],
'茶': [(3,10)]} # リソースフラグ,時間
m = Model() # モデル
# リソース
res = {i:addResource(m,j) for i,j in zip([1,2,4,8],[2,2,2,1])}
# 工程
act = {k:[addActivity(m, d, [r for j,r in res.items() if f&j], f'{k}{i+1}')
for i,(f,d) in enumerate(l)] for k,l in prm.items()}
for l in act.values():
for i,j in pairwise(l):
m.addTemporal(i,j) # 同一料理内では順番に
m.addTemporal('sink',act['魚料理'][1],'CC') # 魚料理2は最後に
m.addTemporal('sink',act['茶'][0],'CC') # 茶1は最後に
m.Params.TimeLimit = 1 # 計算時間は1秒まで
m.Params.Makespan = True # 全工程の終了時刻を最小化
m.optimize() # ソルバー実行
結果
================ Now solving the problem ================
Solutions:
source --- 0 0
sink --- 70 70
スープ1 --- 0 10
スープ2 --- 10 20
スープ3 --- 20 40
スープ4 --- 40 60
焼鳥1 --- 0 10
焼鳥2 --- 10 30
焼鳥3 --- 30 40
魚料理1 --- 20 30
魚料理2 --- 40 70
温野菜1 --- 30 50
温野菜2 --- 50 60
茶1 --- 60 70
2つの数字は、その工程の開始時刻と終了時刻を表しています。
sink が 70 なので、70分で全工程が終了することがわかります。
また、個別に見ても、下記の先生の結果とほぼ同じような答えであることがわかります。
以上