スケジューリング最適化システム OptSeq (Colabデモ）

Scheduling Solver OptSeq

はじめに

スケジューリング（scheduling）とは，稀少資源を諸活動へ（時間軸を考慮して）割り振るための方法に対する理論体系である．スケジューリングの応用は，工場内での生産計画，計算機におけるジョブのコントロール，プロジェクトの遂行手順の決定など，様々である．

ここで考えるのは，以下の一般化資源制約付きスケジューリングモデルであり，ほとんどの実際問題をモデル化できるように設計されている．

複数の作業モードをもつ作業
時刻依存の資源使用可能量上限
作業ごとの納期と重み付き納期遅れ和
作業の後詰め
作業間に定義される一般化された時間制約
モードごとに定義された時刻依存の資源使用量
モードの並列処理
モードの分割処理
状態の考慮

OptSeq（オプトシーク）は，一般化スケジューリング問題に対する最適化ソルバーである．スケジューリング問題は，通常の混合整数最適化ソルバーが苦手とするタイプの問題であり，実務における複雑な条件が付加されたスケジューリング問題に対しては，専用の解法が必要となる． OptSeqは，スケジューリング問題に特化したメタヒューリスティクス(metaheuristics)を用いることによって，大規模な問題に対しても短時間で良好な解を探索することができるように設計されている．

このモジュールは，すべてPythonで書かれたクラスで構成されている． OptSeqのトライアルバージョンは， http://logopt.com/optseq/ からダウンロードもしくは

pip install optseq-trial

とする。

また，テクニカルドキュメントは https://scmopt.github.io/moai-manual/optseq.html にある．

OptSeqモジュール (optseq.py) の基本クラス

行うべき仕事（ジョブ，作業，タスク）を作業(activity；活動)とよぶ．スケジューリング問題の目的は作業をどのようにして時間軸上に並べて遂行するかを決めることであるが，ここで対象とする問題では作業を処理するための方法が何通りかあって，そのうち1つを選択することによって処理するものとする．このような作業の処理方法をモード(mode)とよぶ．

納期や納期遅れのペナルティ（重み）は作業ごとに定めるが，作業時間や資源の使用量はモードごとに決めることができる．

作業を遂行するためには資源(resource)を必要とする場合がある．資源の使用可能量は時刻ごとに変化しても良いものとする．また，モードごとに定める資源の使用量も作業開始からの経過時間によって変化しても良いものとする．通常，資源は作業完了後には再び使用可能になるものと仮定するが，お金や原材料のように一度使用するとなくなってしまうものも考えられる．そのような資源を再生不能資源(nonrenewable resource)とよぶ．

作業間に定義される時間制約(time constraint)は，ある作業（先行作業）の処理が終了するまで，別の作業（後続作業）の処理が開始できないことを表す先行制約を一般化したものであり，先行作業の開始（完了）時刻と後続作業の開始（完了）時刻の間に以下の制約があることを規定する．

先行作業の開始（完了）時刻 \(+\) 時間ずれ \(\leq\) 後続作業の開始（完了）時刻

ここで，時間ずれは任意の整数値であり負の値も許すものとする．この制約によって，作業の同時開始，最早開始時刻，時間枠などの様々な条件を記述することができる．

OptSeqでは，モードを作業時間分の小作業の列と考え，処理の途中中断や並列実行も可能であるとする．その際，中断中の資源使用量や並列作業中の資源使用量も別途定義できるものとする．

また，時刻によって変化させることができる状態(state)が準備され，モード開始の状態の制限やモードによる状態の推移を定義できる．

注意

OptSeqでは作業，モード，資源名を文字列で区別するため重複した名前を付けることはできない．なお，使用できる文字列は, 英文字 (a–z, A–Z), 数字 (0–9), 大括弧 ([ ]), アンダーバー (_), および @ に限定される．また，作業名は source, sink以外，モードは dummy 以外の文字に限定される．

それ以外の文字列はすべてアンダーバー (_)に置き換えられる．

例題

最初にOptSeqの諸クラスをインポートしておく。

from optseq import *

もしくは

from optseq_trial import Model, Mode, State

とする。

以下の例題は、トライアルバージョンでは解けないものは省いてある。

完全な例題と練習問題集はアナリティクス練習問題集のサポートページにある。

例題１ PERT

あなたは航空機会社のコンサルタントだ．あなたの仕事は，着陸した航空機をなるべく早く離陸させるためのスケジュールをたてることだ．航空機は，再び離陸する前に幾つかの作業をこなさなければならない．まず，乗客と荷物を降ろし，次に機内の掃除をし，最後に新しい乗客を搭乗させ，新しい荷物を積み込む．当然のことであるが，乗客を降ろす前に掃除はできず，掃除をした後でないと新しい乗客を入れることはできず，荷物をすべて降ろし終わった後でないと，新しい荷物は積み込むことができない．また，この航空機会社では，乗客用のゲートの都合で，荷物を降ろし終わった後でないと新しい乗客を搭乗させることができないのだ．作業時間は，乗客降ろし \(13\) 分，荷物降ろし \(25\) 分，機内清掃 \(15\) 分，新しい乗客の搭乗 \(27\) 分，新しい荷物の積み込み \(22\) 分とする．さて，最短で何分で離陸できるだろうか？

これは，PERT(Program Evaluation and Review Technique)とよばれるスケジューリング理論の始祖とも言える古典的なモデルである．ちなみに，PERTは，第2次世界大戦中における米国海軍のポラリス潜水艦に搭載するミサイルの設計・開発時間の短縮に貢献したことで有名になり，その後オペレーションズ・リサーチの技法の代表格となった．

この問題は，資源制約なしのスケジューリングモデルになる．使うのは作業と時間制約だけである．

まず，モデルのインスタンスmodelを生成する．作業名は1から6の整数で表し，キーを作業名，値を作業時間とした辞書durationを準備する．

model = Model()
duration = {1: 13, 2: 25, 3: 15, 4: 27, 5: 22}

作業には必ず1つ以上のモード（作業の仕方）を定義する必要があるので，各作業に対して1つのモードを定義し，それを作業に追加する．作業とモードはそれぞれ辞書actとmode に保管するものとする．作業はモデルインスタンスmodelのaddActivityメソッドで追加し，モードはモードクラスModeから生成してから作業インスタンスにaddModesメソッドで追加する．

act = {}
mode = {}
for i in duration:
    act[i] = model.addActivity(f"Act[{i}]")
    mode[i] = Mode(f"Mode[{i}]", duration[i])
    act[i].addModes(mode[i])

時間制約はmodelのaddTemporalメソッドで定義する．引数は先行する作業のインスタンスと後続する作業のインスタンスである．

model.addTemporal(act[1], act[3])
model.addTemporal(act[2], act[4])
model.addTemporal(act[2], act[5])
model.addTemporal(act[3], act[4])

モデルが構築できたら，modelのパラメータParamsで制限時間TimeLimitを1（秒）に設定し，最大完了時刻（メイクスパン）を最小化することを表すMakespanをTrueに設定する．最後にmodelのoptimizeメソッドで最適化を行う．

model.Params.TimeLimit = 1
model.Params.Makespan = True
model.optimize()

プログラム全体を以下に示す．

from optseq_trial import Model, Mode, State

model = Model()
duration = {1: 13, 2: 25, 3: 15, 4: 27, 5: 22}
act = {}
mode = {}
for i in duration:
    act[i] = model.addActivity(f"Act[{i}]")
    mode[i] = Mode(f"Mode[{i}]", duration[i])
    act[i].addModes(mode[i])

model.addTemporal(act[1], act[3])
model.addTemporal(act[2], act[4])
model.addTemporal(act[2], act[5])
model.addTemporal(act[3], act[4])

model.Params.TimeLimit = 1
model.Params.Makespan = True
model.optimize()

最短で\(55\)分で離陸できることが分かる．結果をガントチャートに示す．

例題２資源制約付きPERT

あなたは航空機会社のコンサルタントだ．リストラのため作業員の大幅な削減を迫られたあなたは，例題1と同じ問題を1人の作業員で行うためのスケジュールを作成しなければならなくなった．作業時間や時間制約は同じであるが，各々の作業は作業員を1人占有する（すなわち2つの作業を同時にできない）ものとする．どのような順序で作業を行えば，最短で離陸できるだろうか？

この問題は資源制約付きプロジェクトスケジューリング問題とよばれ， \(NP\)-困難であるが， OptSeqを用いれば容易に解くことができる．

資源制約はmodelインスタンスのaddResourceメソッドで定義する．引数は資源名と容量（資源量上限である）．ここでは，1人の作業員を資源制約として定義する．

res=model.addResource("worker",capacity=1)

作業はモードごとに使用する資源を定義できる．したがって，モードのインスタンスに対してaddResourceメソッドで資源を追加する．引数は資源オブジェクトと使用量requirementであり，ここでは1と指定する．

for i in duration:
    act[i]=model.addActivity(f"Act[{i}]")
    mode[i]=Mode(f"Mode[{i}]",duration[i])
    mode[i].addResource(res,requirement=1)
    act[i].addModes(mode[i])

また， modelのパラメータParamsのOutputFlagをTrueに設定することによって，最適化の詳細ログを出力する．

コード全体は以下のようになる．

model=Model()
duration ={1:13, 2:25, 3:15, 4:27, 5:22 }
res=model.addResource("worker",capacity=1)

act={}
mode={}
for i in duration:
    act[i]=model.addActivity(f"Act[{i}]")
    mode[i]=Mode(f"Mode[{i}]",duration[i])
    mode[i].addResource(res,requirement=1)
    act[i].addModes(mode[i])

#temporal (precedense) constraints
model.addTemporal(act[1],act[3])
model.addTemporal(act[2],act[4])
model.addTemporal(act[2],act[5])
model.addTemporal(act[3],act[4])

model.Params.TimeLimit=1
model.Params.OutputFlag=True
model.Params.Makespan=True
model.optimize()

今度は\(102\)分かかることが分かる．結果をガントチャートに示す．

例題３並列ショップスケジューリング

あなたはF1のピットクルーだ． F1レースにとってピットインの時間は貴重であり，ピットインしたレーシングカーに適切な作業を迅速に行い，なるべく早くレースに戻してやることが，あなたの使命である．

作業1：給油準備 (3秒)
作業2：飲料水の取り替え　 (2秒)
作業3：フロントガラス拭き (2秒)
作業4：ジャッキで車を持ち上げ (2秒)
作業5：タイヤ (前輪左側) 交換 (4秒)
作業6：タイヤ (前輪右側) 交換 (4秒)
作業7：タイヤ (後輪左側) 交換 (4秒)
作業8：タイヤ (後輪右側) 交換 (4秒)
作業9：給油 (11秒)
作業10：ジャッキ降ろし (2秒)

各作業には，作業時間のほかに，この作業が終わらないと次の作業ができないといったような時間制約がある．作業時間と時間制約は，以下の図のようになっている．

いま，あなたを含めて3人のピットクルーがいて，これらの作業を手分けして行うものとする．作業は途中で中断できないものとすると，なるべく早く最後の作業を完了させるには，誰がどの作業をどういう順番で行えばよいのだろうか？

3人の作業員に区別がない場合には，容量（資源上限）が \(3\) の資源workerを定義すれば良い．

res=model.addResource("worker",capacity=3)

後の手順は例題2と同じである．以下にプログラムを示す．

model=Model()
duration ={1:3, 2:2, 3:2, 4:2, 5:4, 6:4, 7:4, 8:4, 9:11, 10:2 }
res=model.addResource("worker",capacity=3)
act={}
mode={}
for i in duration:
    act[i]=model.addActivity(f"Act[{i}]")
    mode[i]=Mode(f"Mode[{i}]", duration[i])
    mode[i].addResource(res,1)
    act[i].addModes(mode[i])

model.addTemporal(act[1],act[9])
for i in range(5,9):
    model.addTemporal(act[4],act[i])
    model.addTemporal(act[i],act[10])

model.Params.TimeLimit=1
model.Params.Makespan=True
model.optimize()

最短で\(14\)分で作業が完了することが分かる．以下にガントチャートと資源チャートを示す．

例題４複数モードの利用

上と同じ例題において、作業１が以下の３つのモード（作業方法）で処理できるものとする。

1人の作業員で行い３秒かかる。
2人の作業員で行い２秒かかる。
3人の作業員で行い１秒かかる。

さて、どのモードを採用し、どのようなスケジュールで作業を行えば、最短で終了するだろうか？

作業１に対して３つのモードを準備して，モードごとに異なる作業時間durationと資源の使用量requirementを設定すれば良い．

if i==1:
    mode[1,1]=Mode("Mode[1_1]",duration=3)
    mode[1,1].addResource(res,requirement=1)
    mode[1,2]=Mode("Mode[1_2]",duration=2)
    mode[1,2].addResource(res,requirement=2)
    mode[1,3]=Mode("Mode[1_3]",duration=1)
    mode[1,3].addResource(res,requirement=3)
    act[i].addModes(mode[1,1],mode[1,2],mode[1,3])

プログラム全体は以下のように書ける．

model=Model()
duration ={1:3, 2:2, 3:2, 4:2, 5:4, 6:4, 7:4, 8:4, 9:11, 10:2 }
res=model.addResource("worker", capacity=3)
act={}
mode={}

for i in duration:
    act[i]=model.addActivity(f"Act[{i}]")
    if i==1:
        mode[1,1]=Mode("Mode[1_1]",duration=3)
        mode[1,1].addResource(res,requirement=1)
        mode[1,2]=Mode("Mode[1_2]",duration=2)
        mode[1,2].addResource(res,requirement=2)
        mode[1,3]=Mode("Mode[1_3]",duration=1)
        mode[1,3].addResource(res,requirement=3)
        act[i].addModes(mode[1,1],mode[1,2],mode[1,3])
    else:
        mode[i]=Mode(f"Mode[{i}]", duration[i])
        mode[i].addResource(res,1)
        act[i].addModes(mode[i])

model.addTemporal(act[1],act[9])
for i in range(5,9):
    model.addTemporal(act[4],act[i])
    model.addTemporal(act[i],act[10])

model.Params.TimeLimit=1
model.Params.Makespan=True
model.optimize()

作業1をモード3（3人同時で1秒）で実行することにより，\(13\)分に完了時刻を短縮できることが分かる．

例題５一般化資源制約付きスケジューリング

あなたは1階建てのお家を造ろうとしている大工さんだ．あなたの仕事は，なるべく早くお家を完成させることだ．お家を造るためには，幾つかの作業をこなさなければならない．まず，土台を造り，1階の壁を組み立て，屋根を取り付け，さらに１階の内装をしなければならない．ただし，土台を造る終える前に1階の建設は開始できず，内装工事も開始できない．また，1階の壁を作り終える前に屋根の取り付けは開始できない．

各作業とそれを行うのに必要な時間（単位は日）は，以下のようになっている．

土台： 2人の作業員で1日
１階の壁：最初の1日目は2人，その後の2日間は1人で，合計3日
内装： 1人の作業員で2日
屋根：最初の1日は1人，次の１日は2人の作業員が必要で，合計2日

いま，作業をする人は，あなたをあわせて2人いるが，相棒は作業開始3日目に休暇をとっている．さて，最短で何日でお家を造ることができるだろうか？

この例題では，資源の容量（資源量上限）と作業の資源使用量が一定でない（日によって変わる）．

最初に作業員資源インスタンスworkerをcapacity引数を省略して生成する．次に，資源インスタンスresのaddCapacityメソッドで開始時刻，終了時刻，容量を入力する．

res=model.addResource("worker")
res.addCapacity(0,2,2)
res.addCapacity(2,3,1)
res.addCapacity(3,"inf",2)

これで時刻ごとに異なる資源の容量が定義できた．実は資源容量は内部的には，辞書で保管されている．資源インスタンスresのcapacity属性を出力すると，以下のようになる．

print(res.capacity)

>  {(0, 2): 2, (2, 3): 1, (3, 'inf'): 2}

したがって，資源インスタンスを生成する際にcapacity引数で上の辞書を与えても同じである．

作業モードごとの資源の必要量を入力するには，辞書を用いる．作業ごとに必要量を表す辞書を準備し，モードインスタンスのaddResourceメソッドのrequirement引数に準備した辞書を渡すことによって，時刻によって異なる資源必要量が定義できる．

req={}
req[1]={(0,1):2}
req[2]={(0,1):2, (1,3):1}
req[3]={(0,2):1}
req[4]={(0,1):1, (1,2):2 }

act={}
mode={}
for i in duration:
    act[i]=model.addActivity(f"Act[{i}]")
    mode[i]=Mode(f"Mode[{i}]", duration[i])
    mode[i].addResource(res,requirement=req[i])
    act[i].addModes(mode[i])

プログラム全体を以下に示す．

model=Model()
duration ={1:1,2:3,3:2,4:2}

#res=model.addResource("worker", capacity = {(0,2):2, (2,3):1, (3,"inf"): 2} )
res=model.addResource("worker")
res.addCapacity(0,2,2)
res.addCapacity(2,3,1)
res.addCapacity(3,"inf",2)

req={}
req[1]={(0,1):2 }
req[2]={(0,1):2 ,(1,3):1}
req[3]={(0,2):1 }
req[4]={(0,1):1,(1,2):2 }

act={}
mode={}
for i in duration:
    act[i]=model.addActivity(f"Act[{i}]")
    mode[i]=Mode(f"Mode[{i}]", duration[i])
    mode[i].addResource(res,requirement=req[i])
    act[i].addModes(mode[i])

model.addTemporal(act[1],act[2])
model.addTemporal(act[1],act[3])
model.addTemporal(act[2],act[4])

model.Params.TimeLimit=1
model.Params.Makespan=True
model.optimize()

例題６納期遅れ最小化スケジューリング

あなたは売れっ子連載作家だ．あなたは，A, B, C, D の4社から原稿を依頼されており，それぞれどんなに急いで書いても \(1\) 日，\(2\) 日，\(3\) 日，\(4\) 日かかるものと思われる．各社に約束した納期は，それぞれ \(5\) 日後，\(9\) 日後，\(6\) 日後，\(4\) 日後であり，納期から \(1\) 日遅れるごとに \(1\) 万円の遅延ペナルティを払わなければならない．

どのような順番で原稿を書けば，支払うペナルティ料の合計を最小にできるだろうか？

今までの例では，すべて最大完了時刻（メイクスパン）を最小化していた．ここでは，作業ごとに決められた納期からの遅れの和を最小化することを考える．

各社の仕事を \(1,2,3,4\) とし，その作業時間をduration，納期をdueに保管しておく．作業を追加するためのaddActivityメソッドのduedate引数で納期を表す \(0\) 以上の整数値（もしくは無限大を表す文字列”inf”）を指定する．また，引数weightで納期遅れに対する重みを設定できる．重みweightの既定値は \(1\) であるので省略しても良い．作業によって納期遅れのペナルティが異なる場合には，この引数を用いる．

duration={1:1, 2:2, 3:3, 4:4}
due={1:5,2:9,3:6,4:4}
   
for i in duration:
    act[i]=model.addActivity(f"Act[{i}]", duedate=due[i], weight=1)

さらにmodelのパラメータParamsで最大完了時刻を最小化することを表すMakespanをFalseに設定する（既定値はFalseであるので省略しても良い）．

プログラム全体を以下に示す．

model=Model()
due={1:5,2:9,3:6,4:4}
duration={1:1, 2:2, 3:3, 4:4 }

res=model.addResource("writer")
res.addCapacity(0, "inf", 1)

act={}
mode={}

for i in duration:
    act[i]=model.addActivity(f"Act[{i}]", duedate=due[i], weight=1)
    mode[i]=Mode(f"Mode[{i}]", duration[i])
    mode[i].addResource(res,1)
    act[i].addModes(mode[i])

model.Params.TimeLimit=1
model.Params.Makespan=False
model.optimize()

例題７クリティカルパス法（再生不能資源の使用法）

あなたは，航空機会社のコンサルタントだ．今度は，作業時間の短縮を要求されている（ただし，資源制約（人の制限）はないものとする）．いま，航空機の離陸の前にする作業の時間が，費用をかけることによって短縮でき，各作業の標準時間，新設備導入によって短縮したときの時間，ならびにそのときに必要な費用は，以下のように推定されているものとする．

作業1：乗客降ろし \(13\) 分．\(10\) 分に短縮可能で，\(1\) 万円必要．
作業2：荷物降ろし \(25\) 分．\(20\) 分に短縮可能で，\(1\) 万円必要．
作業3：機内清掃 \(15\) 分．\(10\) 分に短縮可能で， \(1\) 万円必要．
作業4：新しい乗客の搭乗 \(27\) 分．\(25\) 分に短縮可能で， \(1\) 万円必要．
作業5：新しい荷物積み込み \(22\) 分．\(20\) 分に短縮可能で， \(1\) 万円必要．

さて，いくら費用をかけると，どのくらい離陸時刻を短縮することができるだろうか？

これは， クリティカルパス法 (Critical Path Method; CPM)とよばれる古典的な問題である． CPMは，作業時間を費用（お金）をかけることによって短縮できるという仮定のもとで，費用と作業完了時刻のトレードオフ曲線を求めることを目的としたPERTの変形で，資源制約がないときには効率的な解法が古くから知られているが，資源制約がつくと困難な問題になる．ここでは，この問題が「モード」と「再生不能資源」を用いて，OptSeqでモデル化できることを示す．

作業は通常の作業時間と短縮時の作業時間をもつが，これは作業に付随するモードで表現することができる．問題となるのは，作業時間を短縮したときには，費用がかかるという部分である．費用は資源の一種と考えられるが，いままで考えていた資源とは異なる種類の資源である．

いままで考えていた資源は，機械や人のように，作業中は使用されるが，作業が終了すると，再び別の作業で使うことができるようになる．このような，作業完了後に再び使用可能になる資源を， 再生可能資源 (renewable resource)とよぶ．一方，費用（お金）や原材料のように，一度使うとなくなってしまう資源を， 再生不能資源 (nonrenewable resource)とよぶ．

CPMの例題に対して，再生不能資源（お金）の上限を色々変えて最短時間を求める．まず，各々の作業に対して，通常の作業時間をもつ場合と，短縮された作業時間をもつ場合の 2つのモードを追加し，さらに短縮モードを用いた場合には，再生不能資源を \(1\)単位使用するという条件を付加する．

再生不能資源は，modelインスタンスのaddResoureメソッドで追加できる．このとき，右辺定数rhsと制約の方向directionを定義する必要がある．左辺の項は再生不能資源インスタンスresのaddTermsメソッドで追加する．引数は順に，係数，作業インスタンス，モードインスタンスである．

res=model.addResource("money",rhs=5,direction="<=")

for i in Jobs:
    res.addTerms(1,act[i],mode[i,2])

再生不能資源は制約最適化ソルバーSCOPの線形制約と同じ構造で入力する．これは，OptSeqがSCOPを利用して最適化しているためである．再生不能資源とは，作業を変数，モードを変数のとる値とした制約最適化の線形制約に他ならない．

プログラム全体を以下に示す．

model=Model()
Jobs=[1,2,3,4,5]
durationA = {1:13, 2:25, 3:15, 4:27, 5:22 }
durationB = {1:10, 2:20, 3:10, 4:25, 5:20 }

act={}
mode={}
for i in Jobs:
    mode[i,1]=Mode(f"Mode[{i}][1]",durationA[i])
    mode[i,2]=Mode(f"Mode[{i}][2]",durationB[i])
    act[i]=model.addActivity(f"Act[{i}]")
    act[i].addModes(mode[i,1],mode[i,2])

res=model.addResource("money",rhs=5,direction="<=")

for i in Jobs:
    res.addTerms(1,act[i],mode[i,2])

model.addTemporal(act[1],act[3])
model.addTemporal(act[2],act[4])
model.addTemporal(act[2],act[5])
model.addTemporal(act[3],act[4])

model.Params.TimeLimit=1
model.Params.Makespan=True
model.optimize()

例題８時間制約

OptSeqでは，完了後に開始できるという通常の時間制約の他に，様々なタイプの時間制約を定義できる．この一般化された時間制約を用いることによって，実際問題で発生する様々な付加条件をモデル化することができる．

一般化した時間制約の適用例として，例題1に以下のような時間制約を追加することを考える．

作業3と作業5の開始時刻が一致しなければならない．
作業5の開始時刻は，（開始時刻を \(0\) としたとき）　ちょうど \(50\)分でなければならない．
作業2は作業1の終了後 \(5\)分～\(10\)分の間に開始しなければならない．

時間制約には以下の引数を定義することができる．

type: 時間制約のタイプを表す文字列であり，‘SS’（開始-開始）,‘SC’（開始-完了）,‘CS’（完了-開始）,‘CC’（完了-完了）のいずれかを指定する．既定値は ‘CS’ （開始，完了）
delay: 時間制約の時間ずれを表す整数値である．既定値は \(0\)

作業3と作業5の開始時刻を一致させるためには，制約タイプを ‘SS’（開始-開始の関係），時間ずれを \(0\) と設定した2本の制約「作業3の開始時刻 \(\leq\) 作業5の開始時刻」，「作業5の開始時刻 \(\leq\) 作業3の開始時刻」を追加すれば良い．

model.addTemporal(act[3],act[5],"SS",0)
model.addTemporal(act[5],act[3],"SS",0)

作業の開始時間の固定も，同様である． OptSeqでは，すべての作業に先行するダミーの作業sourceが準備されている．この作業は必ず時刻 \(0\) に処理されるので，開始時刻に相当する時間ずれをもつ時間制約を2本追加することによって，開始時刻を固定することができる．

作業5の開始時刻を \(50\)分に固定するには，

model.addTemporal('source', act[5],'SS',delay=50)
model.addTemporal(act[5], 'source','SS',delay=-50)

と2本の時間制約を追加する．

作業2は作業1の終了後 \(5\)分～\(10\)分の間に開始しなければならないことを表すには，以下の2本の時間制約を使う．

作業1の完了後に時間遅れ \(5\) で作業2が開始できる．
作業2の開始後に時間遅れ \(-10\) で作業1が完了できる．

model.addTemporal(act[1],act[2],'CS',5)
model.addTemporal(act[2],act[1],'SC',-10)

上のプログラムを追加したコード全体は以下のようになる．

model=Model()
durationA = {1:13, 2:25, 3:15, 4:27, 5:22 }

act={}
mode={}

for i in durationA:
    act[i]=model.addActivity(f"Act[{i}]")
    mode[i]=Mode(f"Mode[{i}]", durationA[i])
    act[i].addModes(mode[i])

model.addTemporal(act[1],act[3])
model.addTemporal(act[2],act[4])
model.addTemporal(act[2],act[5])
model.addTemporal(act[3],act[4])

#作業3と作業5の開始時刻が一致しなければならない
model.addTemporal(act[3],act[5],"SS",0)
model.addTemporal(act[5],act[3],"SS",0)

#作業5の開始時刻を  50 分に固定
model.addTemporal("source",act[5],"SS",delay=50)
model.addTemporal(act[5],"source","SS",delay=-50)

#作業2は作業1の終了後5分～10分の間に開始しなければならない
model.addTemporal(act[1],act[2],'CS',5)
model.addTemporal(act[2],act[1],'SC',-10)
    
model.Params.TimeLimit=1
model.Params.Makespan=True
model.optimize()

例題９作業の途中中断

多くの実際の現場では，緊急の作業が入ってくると，いま行っている作業を途中で中断して，別の（緊急で行わなければならない）作業を行った後に，再び中断していた作業を途中から行うことがある．このように，途中で作業を中断しても，再び（一から作業をやり直すのではなく）途中から作業を続行することを「作業の途中中断」とよぶ．

OptSeqでは，これを作業を分割して処理することによって表現する．たとえば，作業時間が\(3\)時間の作業があったとする．途中中断可能な場合には，時間の基本単位を\(1\)時間としたとき，この作業は，\(1\) 時間の作業時間をもつ \(3\) つの小作業に分割して処理される．

しかし，実際問題では，中断可能なタイミングが限られている場合もある．たとえば，料理をするときに，材料を切ったり，混ぜたりするときには，途中で中断することも可能だが，いったんオーブンレンジに入れたら，途中でとめたりすることはできない．

OptSeqでは作業のモードに対して，区間ごとの最大中断可能時間を設定することによって，様々な作業の中断(break)を表現する．

モードの途中中断は，

addBreak(区間の開始時刻,区間の終了時刻,最大中断時間)

を用いて追加する．

たとえば，例題６の納期遅れ最小化問題において，いつでも最大1日だけ中断できる場合は，

mode[i].addBreak(0,"inf",1)

とし，作業開始の1日後までなら1日だけ中断できる場合は，

mode[i].addBreak(0,1,1)

とすれば良い．

また，段取りを伴う生産現場においては，中断の途中で他の作業を行うことが禁止されている場合がある．これは，中断中に異なる作業を行うと，再び段取りなどの処理を行う必要があるため，作業を一からやり直さなければならないからである．これは，作業の中断中でも資源を使い続けていると表現することによって回避することができる．

中断中に資源を使用する場合も，通常の資源を追加するのと同様にaddResourceメソッドに “break” を追加する．

addResource( 資源,{(区間):資源使用量},"break")

例題６において作家が執筆中に休暇をとることができない場合には，

mode[i].addResource(res,1,"break")

とする．

例題６で，すべての作業がいつでも最大1日だけ中断できる場合を考える．ただし，作家は \(4\) 日目と \(7\) 日目と \(11\) 日目に休暇をとるものとする．

中断中に資源を使わない場合と，使う場合のプログラムを以下に示す．

model=Model()

due={1:5,2:9,3:6,4:4}
duration={1:1, 2:2, 3:3, 4:4 }

res=model.addResource("writer")
res.addCapacity(0,3,1)
res.addCapacity(4,6,1)
res.addCapacity(7,10,1)
res.addCapacity(11,"inf",1)

act={}
mode={}

for i in duration:
    act[i]=model.addActivity(f"Act[{i}]",duedate=due[i])
    mode[i]=Mode(f"Mode[{i}]",duration[i])
    mode[i].addResource(res,1)
    mode[i].addBreak(0,"inf",1)    
    #mode[i].addBreak(0,1,1) #開始後１日までしか中断を入れられない合はここを生かす．
    #mode[i].addResource(res,1,"break") #中断中も資源を使う場合にはここを生かす。
    act[i].addModes(mode[i])

model.Params.TimeLimit=1
model.Params.OutputFlag=True
model.Params.Makespan=False
model.optimize()

結果のログに

Act[3],---, 8 9--10 11--13 13
Act[4],---, 0 1--3 4--6 6

とあるので，作業3と作業4は途中中断しており，作業3は９日から10日までと11日から13日に，作業4は1日から3日と4日から６日に分割して処理されていることが分かる．

また，作業が行われている時間の情報は，作業インスタンスのexecute属性に辞書として保管されているので，以下のコードで確認することもできる．

for i in act:
    print(i, act[i].execute) # (開始時刻,終了時刻): 並列数

例題10 作業の並列実行

例題4の並列ショップスケジューリング問題の拡張では，複数の機械（作業員）によって作業時間が短縮されることを，複数のモードを用いることによって表現していた．ここでは，複数資源による作業の並列処理を，より簡単に表現するための方法を紹介する．

作業の途中中断と同じように，作業を単位時間の作業時間をもつ小作業に分解して考える．いま，資源使用量の上限が \(1\) より大きいとき，分解された小作業は，並列して処理できるものとする．ただし実際問題においては，無制限に並列処理ができない場合もある． OptSeqでは，これを最大並列数とよばれるパラメータを用いて表現する．

並列処理は，作業モードに対するaddParallelメソッドを用いて定義される．書式は，

addParallel(開始小作業番号,終了小作業番号,最大並列数)

である．

たとえば，

mode.addParallel(1,1,3)
mode.addParallel(2,3,2)

は, 最初の小作業は最大3個， 2番目と3番目の小作業は最大2個の小作業を並列処理可能であることを意味する.

並列実行中に資源を使用する量は，標準（省略するか引数がNone）だと，各資源の資源使用量の総和になる．総和でなく，並列実行中の資源の「最大量」を指定したい場合には，以下のようにaddResourceメソッドの引数に “max” を追加する．

addResource( 資源,{(区間):資源使用量},"max")

例題3の並列ショップスケジューリング問題において，給油作業（作業時間3秒）を，最初の（1番目の）小作業を最大3個並列可能とした場合を考える．資源使用量を総和としたときと，最大量としたときのプログラムを以下に示す．

model=Model()
duration ={1:3, 2:2, 3:2, 4:2, 5:4, 6:4, 7:4, 8:4, 9:11, 10:2 }

res=model.addResource("worker")
res.addCapacity(0,"inf",3)

act={}
mode={}

for i in duration:
    act[i]=model.addActivity(f"Act[{i}]")

    if i==1:
        mode[i]=Mode(f"Mode[{i}]", duration[i])
        mode[i].addParallel(1,1,3)
        mode[i].addResource(res,1)       #並列実行中の資源量が各作業の使用量の総和のときはこちらを生かす
        #mode[i].addResource(res,1,'max') #並列実行中で使用する資源量が最大1のときはこちらを生かす
    else:
        mode[i]=Mode(f"Mode[{i}]", duration[i])
        mode[i].addResource(res,1)
    act[i].addModes(mode[i])

model.addTemporal(act[1],act[9])
for i in range(5,9):
    model.addTemporal(act[4],act[i])
    model.addTemporal(act[i],act[10])

model.Params.TimeLimit=1
model.Params.OutputFlag=True
model.Params.Makespan=True
model.optimize()

結果のログに

Act[1],---, 0 0--1[2] 1--2 2

とあるので，作業1は最初の1秒は2人で並列に実行し，2秒目は1人で実行していることが分かる．

for i in act:
    print(i, act[i].execute) # (開始時刻,終了時刻): 並列数

例題11 実務的な機械スケジューリング問題

例として，4作業3機械のスケジューリング問題を考える．各作業はそれぞれ 3つの子作業（これを以下では作業とよぶ）\(1\), \(2\), \(3\) から成り, この順序で処理しなくてはならない．各作業を処理する機械, および処理日数は，以下の表の通りである．

	小作業1	小作業2	小作業3
作業1	機械1: 7日	機械2: 10日	機械3: 4日
作業2	機械3: 9日	機械1: 5日	機械2 : 11日
作業3	機械1 : 3日	機械3: 9日	機械2 : 12日
作業4	機械2 : 6日	機械3: 13日	機械1 : 9日

このように，作業によって作業を行う機械の順番が異なる問題は，ジョブショップ(job shop)とよばれ，スケジューリングモデルの中でも難しい問題と考えられている．

目的は最大完了時刻最小化とする．ここでは，さらに以下のような複雑な条件がついているものと仮定する．

各作業の初めの 2日間は作業員資源を必要とする操作がある．この操作は平日のみ, かつ 1日あたり高々2個しか行うことができない．
各作業は，1日経過した後だけ，中断が可能．
機械1での作業は，最初の1日は2個まで並列処理が可能．
機械2に限り, 特急処理が可能．特急処理を行うと処理日数は4日で済むが, 全体で1度しか行うことはできない．
機械1において, 作業1を処理した後は作業2を処理しなくてはならない.

この問題は，機械および作業員資源を再生可能資源とした12作業のスケジューリングモデルとしてOptSeqで記述できる．

model = Model()
# resource declaration
machine = {}  # define three machines
for j in range(1, 4):
    machine[j] = model.addResource(f"machine[{j}]", capacity={(0, "inf"): 1})

# CAP={} #capacity of human resources; two workers are available on weekdays
# for t in range(9):
#    CAP[(t*7,t*7+5)]=2
# manpower=model.addResource("manpower",capacity=CAP)
# we may write ...
manpower = model.addResource("manpower")
for t in range(9):
    manpower.addCapacity(t*7, t*7+5, 2)

# budget constraint
budget = model.addResource("budget_constraint", rhs=1)

# activity declaration (4 activities are processed on three machines)
# JobInfo containes the info. of operations (activity,1..3):-> machine ID and proc. time
JobInfo = {(1, 1): (1, 7), (1, 2): (2, 10), (1, 3): (3, 4),
           (2, 1): (3, 9), (2, 2): (1, 5), (2, 3): (2, 11),
           (3, 1): (1, 3), (3, 2): (3, 9), (3, 3): (2, 12),
           (4, 1): (2, 6), (4, 2): (3, 13), (4, 3): (1, 9)
           }
act = {}
express = Mode("Express", duration=4)
express.addResource(machine[2], {(0, "inf"): 1}, "max")
express.addResource(manpower, {(0, 2): 1})
express.addBreak(1, 1)

mode = {}
for (i, j) in JobInfo:  # for each job and machine
    act[i, j] = model.addActivity(f"Act[{i}][{j}]")
    mode[i, j] = Mode(f"Mode[{i}][{j}]", duration=JobInfo[i, j][1])
    mode[i, j].addResource(machine[JobInfo[i, j][0]], {
                           (0, "inf"): 1}, "max")
    mode[i, j].addResource(manpower, {(0, 2): 1})
    mode[i, j].addBreak(1, 1)
    if JobInfo[i, j][0] == 1:
        mode[i, j].addParallel(1, 1, 2)

    if JobInfo[i, j][0] == 2:
        # activities processed on machine 2 have two modes, Express and Normal.
        act[i, j].addModes(mode[i, j], express)
        # Express mode needs one budget
        budget.addTerms(1, act[i, j], express)
    else:
        act[i, j].addModes(mode[i, j])  # single mode activity
    # print act[i,j]
# temporal (precedense) constraints
for i in range(1, 5):
    for j in range(1, 3):
        model.addTemporal(act[i, j], act[i, j+1])

# Define that Act[2][2] must be processed just after Act[1][1] on machine 1
# introduce dummy with duration 0 and can break at time 0
# it requires machine 1 during the break,
#  completion of Act[1][1]=start of dummy and completaion of dummy=start of Act[2][2]
d_act = model.addActivity("dummy_activity")
d_mode = Mode("dummy_mode")
d_mode.addBreak(0, 0)
d_mode.addResource(machine[1], {(0, 0): 1}, "break")
d_act.addModes(d_mode)
model.addTemporal(act[1, 1], d_act, tempType="CS")
model.addTemporal(d_act, act[1, 1], tempType="SC")
model.addTemporal(d_act, act[2, 2], tempType="CS")
model.addTemporal(act[2, 2], d_act, tempType="SC")

model.Params.TimeLimit = 1
model.Params.Makespan = True
model.optimize()

例題12 状態変数

状態変数とは，時間の経過とともに状態とよばれる非負整数の値が変化する変数である．作業のモードが，特定の状態でないと開始できないという制約を付加することによって，通常のスケジューリングモデルでは表現しきれない，様々な付加条件をモデル化することが可能になる．

まず，状態を定義するには，モデルクラスのaddStateメソッドを用いる． addStateメソッドの引数は，状態の名称を表す文字列であり，返値は状態インスタンスである．たとえば，無名の状態stateをモデルインスタンスmodelに追加するには，以下のようにする．

state = model.addState()

状態は，基本的には1つ前の時刻の値を引き継ぎ，ユーザーの指定によって特定の時刻にその値を変化させることができる変数である．状態が，ある時間においてある値に変化することを定義するためには， addValueメソッドを用いる．たとえば，状態インスタンスstateが時刻0に値1になることを定義するには，次のように記述する．

state.addValue( time=0, value=1 )

状態は，モードで開始された直後に変化させることができる．そのためには，モードインスタンスのaddStateメソッドを用いて定義する． addStateメソッドの引数は，状態インスタンスstate，開始時の状態（fromValue; 非負整数），開始直後に変化する状態（toValue; 非負変数）である．

モードインスタンス.addState(state, fromValue, toValue)

これによって，モード開始時の状態 stateが値 fromValue でなくてはならず，開始直後（開始時刻が \(t\) であれば \(t+1\) に）状態が値 toValue に変化することになる．

これによって，処理モードに「ある状態のときしか開始できない」といった制約を加えることが可能になる．

この記述は，状態のとる値を変えて，任意の回数行うことができる．たとえば，状態変数 state の取り得る値が \(1, 2, 3\) の3種類としたとき，

mode.addState( state, 1, 2)
mode.addState( state, 2, 3)
mode.addState( state, 3, 1)

とすれば，開始時点での状態に関係なく処理は可能で，状態は巡回するように1つずつ変化することになる．

また，これを利用して「あるタイプのモード（以下のmode）は1週間（7日間）に高々3回しか処理できない」ことは，以下のように表すことができる．

state = model.addState()
state.addValue( time=0,  value=0 ) 
state.addValue( time=7,  value=0 ) 
state.addValue( time=14, value=0 ) 
    ...
mode = Mode('mode')
mode.addState( state, 0, 1)
mode.addState( state, 1, 2)
mode.addState( state, 2, 3)

状態は7日ごとに0にリセットされ，モードmodeは状態stateが0,1,2のときだけ開始でき，状態が3のときには開始できない．したがって7日の間に3回だけ開始できることになる．

上述のような「開始時状態が指定された処理モード」を与える場合，通常，そのモードを含む作業の定義において，モードを自動選択(autoselect)にしておくことが推奨される.

OptSeqでは，「まず各作業の処理モードをそれぞれ選び，その後，ある順序にしたがって作業を前づめにスケジュールしていく」ということの繰り返しを行う．したがって，「開始時状態が指定された処理モード」が存在すると，処理モードの選び方によっては，「スケジュールを生成していくとき，割り付け不可能」ということが頻繁に起こりえる．これを防ぐため，「あらかじめ処理モードを指定せず，前づめスケジュールしながら適切な処理モードを選択する」ことが必要になり，これを実現するのがモードの自動選択なのである．

作業に対してモードを自動選択に設定するには，作業クラスのコンストラクタの引数 autoselect を用いるか，作業インスタンスの属性 autoselectを用いる．具体的には，以下の何れの書式でも，自動選択に設定できる．

act1=model.addActivity('Act1', autoselect=True)
act1.autoselect = True

注意作業の定義に autoselect を指定した場合には，その作業に制約を逸脱したときの重みを無限大とした（すなわち絶対制約とした）再生不能資源を定義することはできない．かならず重みを既定値の無限大 ‘inf’ ではない正数値と設定し直す必要がある．

model = Model()
n = 9 #number of activities

state = model.addState("state")
state.addValue( time=0,  value=0 )
state.addValue( time=7,  value=0 )
state.addValue( time=14, value=0 )

mode = Mode('mode', 1)
mode.addState( state, 0, 1)
mode.addState( state, 1, 2)
mode.addState( state, 2, 3)

act ={}
for i in range(n):
    act[i] = model.addActivity(f"act{i}", duedate = i, autoselect= True)
    act[i].addModes(mode)

model.Params.TimeLimit = 1
model.Params.Makespan = False
model.optimize()

例題13 順序依存の段取り時間

D,E,Fの3つの作業（作業時間は全部30）を１つのライン上で生産する問題を考える。初期状態startからは、いずれの作業も段取り時間0で作業開始できるが、D,E,Fの間には、以下の表のような順序に依存した作業時間がかかるものとする。

	D	E	F
D	-	10	0
E	50	-	10
F	0	10	-

これを表現するためには、状態変数を用いる。状態は start, D,E,F であり、それぞれ 0,1,2,3という整数で表すものとする。各段取りに対して、段取りモード mode_setup[i,j] を準備し、状態がiでないと開始できず、開始すると状態をjに移すものとする。各作業 act[j] に対して段取り作業 act_setup[j] を準備し、モードmode_setup[i,j]を追加する。また、段取り作業の終了時刻と、作業act[j]の開始時刻が一致するようにしておく。

model = Model()
duration = {"D": 30, "E": 30, "F": 30}
setup = {("D", "E"): 10, ("E", "D"): 50, ("E", "F"): 10, ("F", "E"): 10,
         ("start", "D"): 0, ("start", "E"): 10, ("start", "F"): 0,
         ("D", "F"): 0, ("F", "D"): 0}
s = {"D": 1, "E": 2, "F": 3, "start": 0}

rs = model.addResource("line1", 1)

act = {}
mode = {}
for i in duration:
    act[i] = model.addActivity(f"Act_{i}")
    mode[i] = Mode(f"Mode_{i}", duration[i])
    mode[i].addResource(rs, {(0, "inf"): 1})
    act[i].addModes(mode[i])

s1 = model.addState("Setup_State")
s1.addValue(time=0, value=s["start"])
# setup mode
mode_setup = {}
for (i, j) in setup:
    mode_setup[i, j] = Mode(f"Mode_setup_{i}_{j}", setup[i, j])
    mode_setup[i, j].addState(s1, s[i], s[j])
    if setup[i, j] != 0:
        mode_setup[i, j].addResource(rs, {(0, setup[i, j]): 1})

    #print (i,j,s[i],s[j],mode_setup[i,j])

act_setup = {}
for k in duration:
    act_setup[k] = model.addActivity(f"Setup_{k}", autoselect=True)
    for (i, j) in setup:
        if k == j:
            act_setup[k].addModes(mode_setup[i, j])

# temporal (precedense) constraints
for j in act_setup:
    model.addTemporal(act_setup[j], act[j], "CS")
    model.addTemporal(act[j], act_setup[j], "SC")

model.Params.TimeLimit = 1
model.Params.Makespan = True
model.optimize()

例題14 貯蔵資源の表現方法

2つの作業（13時間と25時間の作業時間）を考える。作業１の開始後、３時間後に作業２が開始できる。作業１で製造された半製品は２つのタンク（Tank１,２）のいずれかに保管する必要がある。タンク１は常に使用可能であるが、タンク２は１０時間後にメンテナンスが予定されているため、使うことができない。

半製品はダミーの作業(dummy)で表現され、タンク1,2の使用を表す2つのモード (modeDumodel,2)をもつ。これらのモードは作業時間は0だが、開始後に休憩可能 (breakable) とし、開始は作業１の開始時、終了は作業２の終了時と設定する。

半製品は長時間保管すると劣化するので、休憩は最大10時間と設定すると、実行不能になり、最大30時間と設定すると実行可能になる。

model = Model()
duration = {1: 13, 2: 25}
act = {}
mode = {}
for i in duration:
    act[i] = model.addActivity(f"Act[{i}]")
    mode[i] = Mode(f"Mode[{i}]", duration[i])
    act[i].addModes(mode[i])

r1 = model.addResource("Tank1", 1)
r2 = model.addResource("Tank2", {(0, 10): 1})

dummy = model.addActivity("actDum")
modeDumodel = Mode("DumMode1", 0)
modeDum2 = Mode("DumMode2", 0)
#modeDumodel.addBreak(0, 0, 10)  # infeasible
modeDumodel.addBreak(0,0,30) #feasible
modeDumodel.addResource(r1, 1, rtype="break")
modeDum2.addBreak(0, 0, "inf")
modeDum2.addResource(r2, 1, rtype="break")
dummy.addModes(modeDumodel, modeDum2)

model.addTemporal(act[1], dummy, "SS", 0)
model.addTemporal(dummy, act[1], "SS", 0)
model.addTemporal(act[2], dummy, "CC", 0)
model.addTemporal(dummy, act[2], "CC", 0)

model.addTemporal(act[1], act[2], "SS", 3)

model.Params.TimeLimit = 1
model.optimize()

例題16: 後ろ詰めの表現方法

例題６の納期遅れ最小化問題において，作業1の納期を15とし，後ろ詰めで最適化を行う．

（後ろ詰めの場合には状態変数は使えない．実際問題を解く際には，実行不可能にならないように，開始時刻を過去の時点にするなどの工夫が必要になる．）

model=Model()
due={1:15,2:9,3:6,4:4}
duration={1:1, 2:2, 3:3, 4:4 }

res=model.addResource("writer")
res.addCapacity(0,"inf",1)

act={}
mode={}

for i in duration:
    if i==1:
        act[i]=model.addActivity(f"Act[{i}]", duedate=due[i], backward=True)
    else:
        act[i]=model.addActivity(f"Act[{i}]", duedate=due[i])
    mode[i]=Mode(f"Mode[{i}]", duration[i])
    mode[i].addResource(res,{(0,"inf"):1})
    act[i].addModes(mode[i])

model.addTemporal(act[4],act[1])

model.Params.TimeLimit=1
model.Params.Makespan=False
model.optimize()

例題17: リリース時刻

例題１のモデルで，作業１の開始時刻を，ちょうど10に設定する．

ダミーの始点’source’は時刻 \(0\) に開始するので，それとの時間制約を付加する．

model = Model()
duration = {1: 13, 2: 25, 3: 15, 4: 27, 5: 22}
act = {}
mode = {}
for i in duration:
    act[i] = model.addActivity(f"Act[{i}]")
    mode[i] = Mode(f"Mode[{i}]", duration[i])
    act[i].addModes(mode[i])

# temporal (precedense) constraints
model.addTemporal(act[1], act[3])
model.addTemporal(act[2], act[4])
model.addTemporal(act[2], act[5])
model.addTemporal(act[3], act[4])

#リリース時刻
model.addTemporal("source",act[1],tempType="SS",delay=10)
model.addTemporal(act[1],"source",tempType="SS",delay=-10)

model.Params.TimeLimit = 1
model.Params.Makespan = True
model.optimize()

例題18: 平準化

例題2のモデルで，先行制約がない場合を考える．納期は52日であり，資源制約をなるべく平準化したい．

平準化を行うためには，資源の上限を1から順に増やしていき，納期を満たす最小の資源量を求めれば良い．

for ub in range(1,10):
    model=Model()
    duration ={1:13, 2:25, 3:15, 4:27, 5:22 }
    res=model.addResource("worker",capacity=ub)

    act={}
    mode={}
    for i in duration:
        act[i]=model.addActivity(f"Act[{i}]", duedate=52)
        mode[i]=Mode(f"Mode[{i}]",duration[i])
        mode[i].addResource(res,requirement=1)
        act[i].addModes(mode[i])

    model.Params.TimeLimit=1
    model.optimize()
    completion = 0
    for a in act:
        completion = max(completion, act[a].completion)
    if completion <= 52:
        break

例題19: モード間の関係

以下のようなモード間の制約は，再生不能資源で表現できる．

作業Aがモード0で行われるなら，作業Bもモード0で行わなければならない．また，作業Bがモード0で行われるなら，作業Aがモード0で行わなければならない．

作業Aをモード0で行うとき1，それ以外のとき0の変数を用いると，制約は以下のように書ける． \[ x[A,0] = x[B,0] \]

作業Aをモード1で行ったときは，作業Bはモード1で実行できない．また，作業Bをモード1で行ったときは，作業Aはモード1で実行できない．

\[ x[A,1] + x[B,1] \leq 1 \]

作業Aをモード2で行ったときは，作業Bはモード2かモード3で行わなければならない．

\[ x[A,2] \leq x[B,2] + x[B,3] \]

model=Model()
duration ={ ("A",0) :10, ("A",1) :13, ("A",2) :12,
            ("B",0) :15, ("B",1) :11, ("B",2) :12, ("B",3) :14 }
act={}
mode={}
for i,j in duration:
    mode[i,j] = Mode(f"Mode[{i},{j}]", duration[i,j])
act["A"] = model.addActivity("Act[A]")
act["B"] = model.addActivity("Act[B]")
act["A"].addModes(mode["A",0], mode["A",1], mode["A",2])
act["B"].addModes(mode["B",0], mode["B",1], mode["B",2], mode["B",3] )

con1 = model.addResource("constraint_1",rhs=0,direction = "=")
con1.addTerms(coeffs=[1,-1], vars= [act["A"], act["B"]], values =[mode["A",0],mode["B",0]])

con2 = model.addResource("constraint_2",rhs=1,direction = "<=")
con2.addTerms(coeffs=[1,1], vars= [act["A"], act["B"]], values =[mode["A",1],mode["B",1]])

con3 = model.addResource("constraint_3",rhs=0,direction = "<=")
con3.addTerms(coeffs=[1,-1,-1], vars= [act["A"], act["B"], act["B"]], values =[mode["A",2], mode["B",2], mode["B",3]])

model.Params.TimeLimit=1
model.Params.Makespan = True
model.optimize()

例題20: 納期遅れをしない範囲でなるべく多くの仕事をこなす方法

例題6の納期遅れ最小化問題で，納期遅れは許されないという条件で，なるべく多くの仕事をこなすにはどうすれば良いだろうか？

仕事を引き受けない場合には，作業時間が0になるモードを定義し，そのモードをなるべく選択しないことを再生不能資源で定義する．ただし，再生不能資源の制約は，重み1の考慮制約とし，できるだけ満たすものとする．なお，納期遅れのペナルティは大きく設定しておく．

model = Model()
due = {1:5, 2:9, 3:6, 4:4}
duration = {1:1, 2:2, 3:3, 4:4 }
res=model.addResource("writer")
res.addCapacity(0,"inf",1)
act={}
mode={}
for i in duration:
    act[i]=model.addActivity(f"Act[{i}]", duedate=due[i], weight = 100 )
    mode[i]=Mode(f"Mode[{i}]",duration[i])
    mode[i,0] = Mode(f"Mode[{i}0]", 0 )
    mode[i].addResource(res,1)
    act[i].addModes(mode[i], mode[i,0])

con1 = model.addResource("constraint_1",rhs=0,direction = "<=", weight=1)
con1.addTerms(coeffs=[1,1,1,1], vars= [act[1],act[2],act[3],act[4]], values =[mode[1,0],mode[2,0],mode[3,0],mode[4,0]])

model.Params.TimeLimit=1
model.Params.OutputFlag=True
model.Params.Makespan=False
model.optimize()

例題21: 資源の優先利用の設定法

例題3の並列ショップスケジューリング問題で，3人のクルーに優先順位をつけたい．クルー1,2,3の順で優先度を1,2,3とする．

各クルーに割り振る作業数に1,2,3を乗じた値の合計を最小にする再生不能資源（制約）を付加する．

#資源の優先利用の設定法
model=Model()
duration ={1:3, 2:2, 3:2, 4:2, 5:4, 6:4, 7:4, 8:4, 9:11, 10:2 }
res={}
for r in range(1,4):
    res[r] = model.addResource(f"worker{r}", capacity=1)
act={}
mode={}

for i in duration:
    act[i]=model.addActivity(f"Act[{i}]")
    for r in range(1,4):
        mode[i,r]=Mode(f"Mode[{i}{r}]", duration[i])
        mode[i,r].addResource(res[r],1)
        act[i].addModes(mode[i,r])
con={}
weight={1:1, 2:2, 3:3}
for r in range(1,4):
    con[r] = model.addResource(name=f"Constraint{r}", rhs=0, direction="<=", weight=weight[r])
    for i in duration:
        con[r].addTerms(1,act[i],mode[i,r])
        
model.addTemporal(act[1],act[9])
for i in range(5,9):
    model.addTemporal(act[4],act[i])
    model.addTemporal(act[i],act[10])
model.Params.TimeLimit=1
model.Params.OutputFlag=True
model.Params.Makespan=True
model.optimize()

例題23: モードに依存した段取り時間

時間制約に対してモードに依存した時間制約を定義できる．この例では，先行作業と後続作業のモードに依存した時間遅れを入力する．

model = Model()
duration = {1: 13, 2: 25, 3: 15, 4: 27, 5: 22}
act = {}
mode = {}
res=model.addResource("worker",capacity=1)
for i in duration:
    act[i] = model.addActivity(f"Act[{i}]")
    mode[i,1] = Mode(f"Mode[{i},{1}]", duration[i])
    mode[i,2] = Mode(f"Mode[{i},{2}]", duration[i])
    mode[i,1].addResource(res,requirement=1)
    act[i].addModes(mode[i,1], mode[i,2])
        
# temporal constraints
model.addTemporal(act[1], act[2], delay = 20, pred_mode = mode[1,1], succ_mode =mode[2,1])
model.addTemporal(act[1], act[2], delay = 30, pred_mode = mode[1,2], succ_mode =mode[2,2])
model.addTemporal(act[1], act[2], delay = 40, pred_mode = mode[1,1], succ_mode = mode[2,2])
model.addTemporal(act[1], act[2], delay = 50, pred_mode = mode[1,2], succ_mode = mode[2,1])
model.addTemporal(act[1], act[2], delay = 20)
model.addTemporal(act[1], act[3], delay = 20)
model.addTemporal(act[2], act[4], delay=10)
model.addTemporal(act[2], act[5], delay = 8)
model.addTemporal(act[3], act[4], delay =10)
model.addTemporal("source", act[1], delay =5, succ_mode = mode[1,1])
model.addTemporal(act[4], "sink",  delay =5, pred_mode = mode[4,1])
model.addTemporal(act[4], "sink",  delay =15, pred_mode = mode[4,2])

model.Params.TimeLimit = 1
model.Params.Makespan = True
model.optimize(cloud=False)

例題24: 納期遅れに対する2次のペナルティ

納期遅れの例題（例題６）において，作業3の納期遅れペナルティを2乗関数にする．

model=Model()
due={1:5,2:9,3:6,4:4}
duration={1:1, 2:2, 3:3, 4:4 }

res=model.addResource("writer")
res.addCapacity(0, "inf", 1)

act={}
mode={}

for i in duration:
    if i==3:
        act[i]=model.addActivity(f"Act[{i}]", duedate=due[i], quadratic= True)
    else:
        act[i]=model.addActivity(f"Act[{i}]", duedate=due[i])
    mode[i]=Mode(f"Mode[{i}]", duration[i])
    mode[i].addResource(res,1)
    act[i].addModes(mode[i])

model.Params.TimeLimit=1
model.Params.OutputFlag=True
model.Params.Makespan=False
model.optimize()

例題25: 実践例 (1)

https://production-scheduling.com/education/tutorials/ からダウンロードした例題 (Section 1) を解く．

以下、問題の要約を示す。

容量計画と有限スケジューリングの本質的な違い

明日のこの時間までに、次の5つの作業を完了しなければならないと想定する。

作業	時間 (時間)
作業A	7
作業B	12
作業C	4
作業D	5
作業E	8

合計：36時間

1日の作業時間は24時間であるのに対し、合計36時間分の作業があるため問題が発生する。
容量計画は、「1日あたり36÷24＝150%の負荷がかかっている」という事実を指摘するのみであり、追加のリソースを投入するか、納期を再調整する必要があるという結論を導く。

一方、有限スケジューリングは資源の容量が有限であることを認識し、いくつかの作業が遅延することを明示する。また、次のような情報も提供することができる。

どの作業が遅れるのか
どれくらい遅れるのか
重要な作業か、あるいは重要な顧客向けの作業であるのか
新しい納期をどのように設定できるのか
作業の順序を変更した場合、これら全てがどのように変化するのか

容量計画と比較して、有限スケジューリングはより豊富な管理情報を提供する。

以下のように、納期を24に設定してOptSeqで最適化すると、作業B (プログラムでは作業1) だけが11時間遅れのスケジュールが得られる。

durations = [7, 12, 4, 5, 8]
model = Model()
machine = model.addResource(capacity = 1)
act, mode = {},{}
for i,d in enumerate(durations):
    act[i] = model.addActivity(f"act[{i}]", duedate =24)
    mode[i] = Mode(f"Mode[{i}]", duration =d)
    mode[i].addResource(machine, 1)
    act[i].addModes(mode[i])
#print(model)
model.Params.TimeLimit=1
model.Params.OutputFlag = True
model.optimize()

例題26: 実践例 (2)

https://production-scheduling.com/education/tutorials/ からダウンロードした例題 (Section 14) を解く。

以下、問題の要約を示す。

4つの作業を2つの作業センターのいずれかで処理する．作業センター１より作業センター2の方が処理時間が短い．また，順序依存の段取り時間がかかり，段取りは作業センター1の方が高速である．初期状態は製品0を生産したものと仮定したとき，最大完了時刻を最小にする．

作業センターの段取り時間は、前の作業に依存することが多い。例えば、黒い塗料を作った後でミキサーを洗浄し白い塗料を作る場合には多くの時間を要するが、白い塗料を作った後に灰色の塗料に切り替える場合はそれほど時間を要しない。このような例は印刷や食品加工、またはプレス機の高さ調整においても見られる。これらの産業では、作業の順序が作業センターの段取りにかかる時間に影響を与え、その結果、作業センターの生産性にも影響を及ぼす。

製品または製品グループ間の段取り時間は、以下の行列で表される：

作業センター1 - 段取り時間 (分)

	製品A	製品B	製品C	製品D
製品A	0.00	0.50	0.50	1.25
製品B	2.00	0.00	0.75	1.00
製品C	2.00	2.00	0.00	0.75
製品D	2.10	1.75	1.50	0.00

作業センター2 - 段取り時間 (分)

	製品A	製品B	製品C	製品D
製品A	0.00	1.25	1.25	2.75
製品B	4.25	0.00	1.75	2.50
製品C	4.25	4.25	0.00	1.75
製品D	5.00	4.50	3.50	0.00

作業センターごとに状態変数を準備し，作業の番号を状態とする．段取り作業と本作業の両者を定義し，その間を時間制約でつなぐ．

Excelで試行錯誤するのと比べて格段に簡単に最適解を得ることができることが分かる。

model = Model()
n, m = 4, 2 #number of jobs and number of work centers
setup1 = [
    [0.00, 0.50, 0.50, 1.25],
    [2.00, 0.00, 0.75, 1.00],
    [2.00, 2.00, 0.00, 0.75],
    [2.10, 1.75, 1.50, 0.00]
]

setup2 = [
    [0.00, 1.25, 1.25, 2.75],
    [4.25, 0.00, 1.75, 2.50],
    [4.25, 4.25, 0.00, 1.75],
    [5.00, 4.50, 3.50, 0.00]
]

units_per_hour =[
    [80, 140],
    [55, 105],
    [72, 135],
    [65, 110]
]

quantity = [450, 650, 1500, 1300]

duration ={}
for i, q in enumerate(quantity):
    for j in range(m):
        duration[i,j] = int(q/units_per_hour[i][j] * 60)

act, mode, res, state= {},{},{},{}
for j in range(m):
    res[j] = model.addResource(name=f"wc[{j}]", capacity = 1)
    state[j] = model.addState(name=f"state[{j}]") 
    state[j].addValue(time=0, value=0) #both work centers are now producing A
    
mode_setup = {}
for j in range(m):    
    for i in range(n):
        for k in range(n):
            if j==0:
                setuptime = int(setup1[i][k]*60)
            else:
                setuptime = int(setup2[i][k]*60)
            mode_setup[i, k, j] = Mode(f"Mode_setup[{i},{k},{j}]", setuptime )
            mode_setup[i, k, j].addState(state[j], i, k)
            if setuptime >0:
                mode_setup[i, k, j].addResource(res[j], 1 )

act_setup = {}
for k in range(n):
    act_setup[k] = model.addActivity(f"Setup[{k}]", autoselect=True)
    for i in range(n):
        for j in range(m):
            act_setup[k].addModes(mode_setup[i, k, j])

for i in range(n):
    act[i] = model.addActivity(f"act[{i}]")
    for j in range(m):
        mode[i,j] = Mode(f"Mode[{i},{j}]", duration= duration[i,j])
        mode[i,j].addResource(res[j], 1)
        mode[i, j].addState(state[j], i, i)
    act[i].addModes(*[mode[i,j] for j in range(m)])    

for i in range(n):
   model.addTemporal(act_setup[i], act[i], "CS")
   model.addTemporal(act[i], act_setup[i], "SC")
#print(model)
model.Params.TimeLimit=1
model.Params.OutputFlag = True
model.Params.Makespan = True
model.optimize()

例題27: 配送計画問題

運搬車の現在地点を状態とすることによって，（最大完了時刻の最小化を目的とした）配送計画問題を解くことができる．この問題は， 巡回修理人問題 (traveling repairman problem)の拡張と考えられる．このテクニックを使うことによって，資源が地点間を移動するタイプのスケジューリング問題のモデル化が可能になる．

以下の例では，運搬車の容量は考慮していないが，各作業の前に伸び縮みするダミーの作業を配置し，開始時刻を \(0\) に，終了時刻を作業の開始時刻に固定し，ダミーの作業が資源を使用すると定義することによってモデル化することができる．

5つの地点（0,1,2,3,4）を2台の運搬車で巡回することを考える．点 \(0\) をデポとする．最後の顧客への訪問時刻を最小化するための，各運搬車の巡回順を求める．

n = 5 #number of nodes
m = 2 #number of vehicles
# travel time
D = [ [0,1,1,1,1],
      [1,0,1,2,3],
      [1,1,0,1,2],
      [1,2,1,0,1],
      [1,3,2,1,0] ]
model = Model()
state = {}    #状態
resource ={ }
for k in range(m):
    state[k] = model.addState(f"State{k}")
    state[k].addValue(time=0, value =0) #開始時刻には点 0 （デポ）にいる
    resource[k] = model.addResource(f"vehicle{k}", 1)
act = {}
mode_move = {}
for j in range(n):
    if j==0:
        continue
    act[j] = model.addActivity(f"Act[{j}]", autoselect=True)
    for i in range(n):
        if i==j: 
            continue
        for k in range(m):
            mode_move[i, j, k] = Mode(f"Mode_move[{i},{j},{k}]", D[i][j] )
            mode_move[i, j, k].addState(state[k], i, j)
            mode_move[i, j, k].addResource(resource[k], 1)
            act[j].addModes(mode_move[i,j,k])
model.optimize()

はじめに

OptSeqモジュール (optseq.py) の基本クラス

注意

例題

例題１ PERT

例題２ 資源制約付きPERT

例題３ 並列ショップスケジューリング

例題４ 複数モードの利用

例題５ 一般化資源制約付きスケジューリング

例題６ 納期遅れ最小化スケジューリング

例題７ クリティカルパス法（再生不能資源の使用法）

例題８ 時間制約

例題９ 作業の途中中断

例題10 作業の並列実行

例題11 実務的な機械スケジューリング問題

例題12 状態変数

例題13 順序依存の段取り時間

例題14 貯蔵資源の表現方法

例題16: 後ろ詰めの表現方法

例題17: リリース時刻

例題18: 平準化

例題19: モード間の関係

例題20: 納期遅れをしない範囲でなるべく多くの仕事をこなす方法

例題21: 資源の優先利用の設定法

例題23: モードに依存した段取り時間

例題24: 納期遅れに対する2次のペナルティ

例題25: 実践例 (1)

例題26: 実践例 (2)

例題27: 配送計画問題

例題２資源制約付きPERT

例題３並列ショップスケジューリング

例題４複数モードの利用

例題５一般化資源制約付きスケジューリング

例題６納期遅れ最小化スケジューリング

例題７クリティカルパス法（再生不能資源の使用法）

例題８時間制約

例題９作業の途中中断