Posted at

最適な調理の順番を求める

More than 1 year has passed since last update.


お題

国立情報学研究所の宇野先生のスケジューリング問題を解いてみましょう。


たくさんある工程(スープ、焼鳥、…)を、いろいろなリソース(人、コンロ、包丁、オーブン)を使って、なるべく早く完成させます。


定式化して汎用ソルバーで解けますが、大変なので、スケジューリング専用ソルバー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分で全工程が終了することがわかります。

また、個別に見ても、下記の先生の結果とほぼ同じような答えであることがわかります。

以上