お題

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

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

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

以上