はじめに
スケジューリング（scheduling）とは，稀少資源を諸活動へ（時間軸を考慮して）割り振るための方法に対する理論体系である． スケジューリングの応用は，工場内での生産計画，計算機におけるジョブのコントロール，プロジェクトの遂行手順の決定など，様々である．
ここで考えるのは，以下の一般化資源制約付きスケジューリングモデルであり，ほとんどの実際問題をモデル化できるように設計されている．
- 複数の作業モードをもつ作業
- 時刻依存の資源使用可能量上限
- 作業ごとの納期と重み付き納期遅れ和
- 作業の後詰め
- 作業間に定義される一般化された時間制約
- モードごとに定義された時刻依存の資源使用量
- モードの並列処理
- モードの分割処理
- 状態の考慮
OptSeq（オプトシーク）は，一般化スケジューリング問題に対する最適化ソルバーである． スケジューリング問題は，通常の混合整数最適化ソルバーが苦手とするタイプの問題であり， 実務における複雑な条件が付加されたスケジューリング問題に対しては，専用の解法が必要となる． OptSeqは，スケジューリング問題に特化したメタヒューリスティクス(metaheuristics)を用いることによって， 大規模な問題に対しても短時間で良好な解を探索することができるように設計されている．
このモジュールは， すべてPythonで書かれたクラスで構成されている． OptSeqのトライアルバージョンは， http://logopt.com/optseq/ からダウンロード，もしくは github https://github.com/mikiokubo/optseqtrial からクローンできる． また，テクニカルドキュメントは，https://scmopt.github.io/manual/07optseq.html にある．
OptSeqが有効なケース
OptSeqはスケジューリング最適化に特化したソルバーである． ここでは，数理最適化や量子計算（無制約2次最適化）では，実務的なスケジューリング問題を解くことが難しい場合があることを， 最近コンサルティングをした案件を例として解説する．
$2000$の作業を$100$台の機械に割り当てるスケジューリング問題を考える． 計画期間は$30$日であり，時間は分単位とする．
この問題を数理最適化（もしくは無制約2次最適化）で組合せ最適化問題として定式化するには， $\{ 0,1 \}$ （もしくは $\{ -1,1 \}$） の領域をもつ変数を用いる． 実務で発生する様々な付加条件を表現するためには， 作業 $i$ を機械 $j$ に時刻 $t$ に割り当てることを 表す変数 $x_{ijt}$ を考えるのが自然である． しかし，$30$日分を分単位で計画するには， $2000 \times 100 \times 30 \times 24 \times 60 = 86.4$億の変数が必要になる． 当然，既存のソルバーでは計算不能になる．
一方，OptSeqでは作業に対して割り当てる機械を表す $100$ のモードを用いるだけで良い． モードは制約最適化の領域として定義されるので， 変数の数は作業数の $2000$ となる． OptSeqでは，時間は任意の単位で表されるので，分単位でも秒単位でも計算量は変わらない．
OptSeqはメタヒューリスティクスに基づくソルバーであるので，現実的な時間で，現実的な解を算出することができるのである．
OptSeqモジュール (optseq.py) の基本クラス
行うべき仕事（ジョブ，作業，タスク）を作業(activity；活動)とよぶ． スケジューリング問題の目的は作業をどのようにして時間軸上に並べて遂行するかを決めることであるが， ここで対象とする問題では作業を処理するための方法が何通りかあって，そのうち1つを選択することによって 処理するものとする．このような作業の処理方法をモード(mode)とよぶ．
納期や納期遅れのペナルティ（重み）は作業ごとに定めるが， 作業時間や資源の使用量はモードごとに決めることができる．
作業を遂行するためには資源(resource)を必要とする場合がある． 資源の使用可能量は時刻ごとに変化しても良いものとする． また，モードごとに定める資源の使用量も作業開始からの経過時間によって変化しても良いものとする． 通常，資源は作業完了後には再び使用可能になるものと仮定するが， お金や原材料のように一度使用するとなくなってしまうものも考えられる． そのような資源を再生不能資源(nonrenewable resource)とよぶ．
作業間に定義される時間制約(time constraint)は， ある作業（先行作業）の処理が終了するまで，別の作業（後続作業）の処理が開始できないことを表す 先行制約を一般化したものであり， 先行作業の開始（完了）時刻と後続作業の開始（完了）時刻の間に以下の制約があることを規定する．
先行作業の開始（完了）時刻 $+$ 時間ずれ $\leq$ 後続作業の開始（完了）時刻
ここで，時間ずれは任意の整数値であり負の値も許すものとする． この制約によって，作業の同時開始，最早開始時刻，時間枠などの様々な条件を記述することができる．
OptSeqでは，モードを作業時間分の小作業の列と考え，処理の途中中断や並列実行も可能であるとする．その際，中断中の資源使用量や並列作業中の資源使用量も別途定義できるものとする．
また，時刻によって変化させることができる状態(state)が準備され，モード開始の状態の制限やモードによる状態の推移を定義できる．
クラス間の関係を以下に示す．
from optseq import *
例題１ 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()
プログラム全体を以下に示す．
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$分で離陸できることが分かる． 結果をガントチャートに示す．
資源制約は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()
今までの例では，すべて最大完了時刻（メイクスパン）を最小化していた． ここでは，作業ごとに決められた納期からの遅れの和を最小化することを考える．
各社の仕事を $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人で実行していることが分かる．
また， 作業が行われている時間の情報は，作業インスタンスのexecute属性に辞書として保管されているので，以下のコードで確認することもできる．
for i in act:
print(i, act[i].execute) # (開始時刻,終了時刻): 並列数
以上，例題を用いてOptSeqの基本的な使用法を解説した． OptSeqには，他にも様々な機能があり，工夫次第でほとんどの実際のスケジューリング問題を解決できる． 詳細については， テクニカルドキュメント https://scmopt.github.io/manual/07optseq.html を参照されたい．
問題 楽観値と悲観値
以下ような作業に対して，問いに答えよ．
| 作業名 | 先行作業 | 楽観値 | 平均値 | 悲観値 |
|---|---|---|---|---|
| A | なし | 1 | 2 | 3 |
| B | なし | 2 | 3 | 4 |
| C | A | 1 | 2 | 3 |
| D | B | 2 | 4 | 6 |
| E | C | 1 | 4 | 7 |
| F | C | 1 | 2 | 3 |
| G | D,E | 3 | 4 | 5 |
| H | F,G | 1 | 2 | 3 |
- 作業時間の楽観値に対して作業 H が完了する最早時刻を求めよ．
- 作業時間の平均値に対して作業 H が完了する最早時刻を求めよ．
- 作業時間の悲観値に対して作業 H が完了する最早時刻を求めよ．
- 作業時間が楽観値と悲観値の間の一様分布と仮定したときの，作業 H が完了する最早時刻の分布をmatplotlibを用いて描け．
問題 クリティカルパス法（改）
例題７で，作業時間と短縮したときの費用が，以下のように設定されている場合を考え，予算が $0$ から $4$万円に 変化したときの最早完了時刻を求めよ．
- 作業1： 乗客降ろし $13$ 分．$12$ 分に短縮可能で，$1$ 万円必要．$11$ 分に短縮するには，さらに $1$ 万円必要．
- 作業2： 荷物降ろし $25$ 分．$23$ 分に短縮可能で，$1$ 万円必要．$21$ 分に短縮するには，さらに $1$ 万円必要．
- 作業3： 機内清掃 $15$ 分．$13$ 分に短縮可能で， $1$ 万円必要．$11$ 分に短縮するには，さらに $1$ 万円必要．
- 作業4： 新しい乗客の搭乗 $27$ 分．$26$ 分に短縮可能で， $1$ 万円必要．$25$ 分に短縮するには，さらに $1$ 万円必要．
- 作業5： 新しい荷物の積み込み $22$ 分．$21$ 分に短縮可能で，$1$ 万円必要．$20$ 分に短縮するには，さらに $1$ 万円必要．
問題 日本食レストラン
あなたは日本食レストランのオーナーだ． あなたは，明日の元旦に向けて，3人のお客様に特製おせち料理を出さなければならない． この特製おせちは，3人の料理人の流れ作業によって作られる． 最初の料理人は包丁担当で，これは彼ならではのテクニックで材料を切り刻む． 2番目の料理人は煮込み担当で，3番目の料理人は飾り付け担当だ． 当然，流れ作業なので，切りの後に煮込み，煮込みの後に飾り付けが行われ， 作業の途中中断はできないものと仮定する． それぞれの工程の作業時間は，以下のようになっている． さて，どのようにしたらなるべく早く料理を終えることができるだろうか？
| お客さんの番号 | 1 | 2 | 3 |
|---|---|---|---|
| 包丁担当の作業時間 | 2 | 4 | 1 |
| 煮込み担当の作業時間 | 3 | 2 | 4 |
| 飾り付け担当の作業時間 | 1 | 3 | 1 |