제목

국립정보학연구소 우노 선생님스케줄링 문제을 풀어보세요.



많은 공정 (스프, 야키토리, ...)을 다양한 리소스 (사람, 스토브, 부엌칼, 오븐)를 사용하여 가능한 한 빨리 완성합니다.

정식화하고 범용 솔버로 풀 수 있지만 힘들기 때문에 스케줄링 전용 솔버 OptSeq를 사용합니다. 유료이지만 변수 15까지는 무료 평가판으로 풀 수 있습니다.

설치 및 사용법은 스케줄링 최적화 솔버 OptSeq II을 참조하십시오.

파이썬으로 풀기

이름을 지정하지 않아도 되도록 보조 함수를 정의합니다.

파이썬

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은 작업 시간(분)입니다.

파이썬

# 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

두 숫자는 프로세스의 시작 시간과 종료 시간을 나타냅니다.
sink가 70이므로 70분 만에 모든 공정이 종료된다는 것을 알 수 있습니다.
또한 개별적으로 봐도 아래 선생님의 결과와 거의 같은 대답임을 알 수 있습니다.



이상