LoginSignup
11

More than 5 years have passed since last update.

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

Posted at

お題

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

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

定式化して汎用ソルバーで解けますが、大変なので、スケジューリング専用ソルバー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分で全工程が終了することがわかります。
また、個別に見ても、下記の先生の結果とほぼ同じような答えであることがわかります。

以上

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
11