スケジューリング最適化システム OptSeq II Pythonモジュールの使い方 補助資料：OptSeq II によるスケジューリング入門 トライアルバージョン http://www.logopt.com/OptSeq/OptSeq.htm

スケジューリングモデルとは 作業（activity；活動）：遂行すべき仕事のこと．別名，オペレーション（operation），ジョブ，仕事(job)，タスク(task)．作業時間や納期の情報が付加される． 先行（時間）制約（precedence (time) constraint）：ある作業（ジョブ，活動）がある作業（ジョブ，活動）の前に処理されなければならないことを表す制約． 資源（resource）：作業を行うときに必要とされるもので，その量に限りがあるもの．機械(machine）はジョブによって占有される資源．その他，人員，材料，お金なども全部資源．

optseq2.pyモジュールとは スケジューリングソルバーOptSeqを，超高級言語Pythonから直接呼び出して，求解するためのモジュール すべてPythonで書かれたクラスで構成 ソースコード（すべてPythonで記述）も公開されているので，ユーザが書き換え可能

Pythonモジュールのクラス 作業クラス ー Activity モードクラス ー Mode モデルクラス ー Model パラメータクラス　ー　Parameters 資源クラス　ー　Resource 先行制約クラス　ー　Temporal

作業クラス ー Activity 作業の定義を行う activityの引数と引数のデフォルト値 activity. (name=‘’, dudate=‘inf’, weight=1) name ：　作業の名前，文字列で入力 dudate ：　作業の納期，非負の整数または‘inf’で入力 weight ：　作業が納期遅れした時のペナルティ，positive 整数 activityのaddModesメソッド activity.addModes(modes) modes：　モードクラスで作成 作業にモード（一つまたは複数のモード）を追加する時に使用 例：　activity.addModes(mode1,mode2)

モードクラス ー Mode（１） モードの定義を行う modeの引数と引数のデフォルト値 mode(name=‘ ’, duration=0) name：　モードの名前，文字列で入力 duration：　このモードを選択した場合の作業時間 modeのメソッド　（次のページで詳しく） addBreak(start=0, finish=0, maxtime=‘inf’) 休憩に関する情報をモードに追加   addParallel(start=1, finish=1, maxparallel=‘inf’) 並列処理に関する情報をモードに追加   addResource(resource, requirement={}, rtype=None) 資源に関する情報をモードに追加

モードクラス ー Mode（２） モードメソッド（１） addBreak メソッド addBreak(start=0, finish=0, maxtime=‘inf’) start，finish：　休憩開始時間，休憩終了時間 maxtime：　最大休憩可能時間 addParallel メソッド addParallel(start=1, finish=1, maxparallel=‘inf’) start，finish：　並列開始小作業番号，並列終了小作業番号 maxparallel：　最大並列数

モード名.addBreak(中断開始時刻,中断終了時刻,最大中断時間) 作業の途中中断 　Pythonインターフェイスによる記述 モード名.addBreak(中断開始時刻,中断終了時刻,最大中断時間) 作業Aが，0から3の区間でそれぞれ最大1中断可能： モード名.addBreak(0,3,1) 開始から2時刻で中断した例

モード名.addParallel(開始小作業番号,終了小作業番号, 最大並列数) 作業の並列処理 　Pythonインターフェイスによる記述 モード名.addParallel(開始小作業番号,終了小作業番号, 最大並列数) 作業１（作業時間は３秒）を最大３単位並列可能： モード名.addParallel(1,1,3) 作業１ 小作業1,小作業1

並列処理の結果 　1番目の小作業を3単位並列可能： 1 2 3

モードクラス ー Mode（３） モードメソッド（２） addResource メソッド addResource(resource, requirement={}, rtype=None) resource：　資源オブジェクト requirement：　資源必要量 資源を必要とする開始時刻と終了時刻を辞書で表す 例：　mode.addResource(worker,{(0,10):1}) 時刻0から時刻10までworkerという資源を１単位必要 rtype：　リソースのタイプ ----- break と max がある 例：　mode.addResource(machine,{(0,"inf"):1},"break") break は休憩中も資源を１単位使用 例：　mode.addResource(machine,{(0,"inf"):1},"max") max は並列処理を行う時も資源は１単位使用

モデルクラス ー Model モデルを作成 モデルクラスのメソッド モデルクラスのメソッド　　 addActivity(name=‘’, duedate=‘inf’, weight=1) モデルに作業を追加　　（括弧内の引数説明はactivityクラス参照） addResource(name=‘’, capacity={}, rhs=0, direction=‘<=’) モデルに資源を追加　　（括弧内の引数説明はresourceクラス参照） addTemporal(pred, succ, tempType=‘CS’, delay=0) モデルに先行制約を追加　（括弧内の引数説明はtemporalクラス参照） optimize() モデルの最適化を行う write(filename=‘optseq.txt’) テキスト形式のガントチャートを書く

パラメータクラス ー Parameters よく使うパラメータ TimeLimit：求解する時の制限時間；単位は秒；既定値=600秒 OutputFlag：モデルを出力する場合True，出力しない場合False ；　既定値=False Makespan：最大完了時刻最小化の時はTrue，それ以外の時はFalse ；　既定値=False 　 RandomSeed – random seedを設定；整数；既定値=1

資源クラス ー Resource（１） 資源の定義を行う resourceの引数と引数のデフォルト値 resource. (name=' ', capacity=0, rhs=0, direction='<=') name ：　資源の名前，文字列で入力 capacity ：　再生可能資源の最大容量; 区間と容量の辞書で入力 rhs ：　再生不能資源の制約 direction ：　再生不能資源制約の向き"<=" or ">=" or "=" resourceのメソッド　（次のページで詳しく） addCapacity(start=0, finish=0, amount=1) 資源に容量を追加 addTerms(coeffs=[], vars=[], values=[]) 再生不能資源に関する制約の左辺追加 printConstraint( ) 再生不能資源に関する制約を展開 setRhs(rhs=0) 再生不能資源に関する制約の右辺追加

資源クラス ー Resource（２） 資源メソッド resourceのメソッド addCapacity(start=0, finish=0, amount=1) start, finish ：　資源使用開始と終了時刻 amount ：　資源の使用量 例：　manpower.addCapacity(0,5,2) 時刻0から時刻5の間に資源 (manpower) を2単位使用 addTerms(coeffs=[], vars=[], values=[]) coeffs ：　 追加する項；　リストで入力可 vars ：　作業オブジェクト；　リストで入力可 values ：　モードオブジェクト；　リストで入力可 例：　budget.addTerms(1,act,express) 　act と言う作業が express と言うモードで行う時再生不能資源を1単位追加

時間制約クラス ー Temporal 時間制約の定義を行う Temporal の引数と引数のデフォルト値 Temporal(pred, succ, tempType, delay) pred ：　先行作業のオブジェクト succ ：　後続作業のオブジェクト tempType ：　時間制約のタイプ；　規定値= "CS" "CS"=Completion-Start, "SS"=Start-Start, "SC"= Start-Completion, "CC"=Completion-Completion 先行作業の終了 (開始)時刻+delay <= 後続作業の開始 (終了) 時刻 delay ：　先行作業と後続作業の時間ずれ；　負の数も可

時間制約 時間制約オブジェクトの生成法 Temporal(pred=A, succ=B, tempType=“CS”, delay=0) Completion Start A B 後続作業 先行作業 作業Aの完了後に作業Bの開始 Temporal(pred=A, succ=B, tempType=“CS”, delay=0)

制約タイプ（type） type SS type SC type CC Start Start A B Start Completion A

時間ずれ（delay） delay 10 delay -10 Completion Start A B 10 作業Bの開始可能時間帯

時間制約の応用 1（同時開始） Pythonインターフェイスによる記述 モデル名.addTemporal(A,B,"SS",0) モデル名.addTemporal(B,A,"SS",0) AとBの同時開始 Aの開始+0 ≦ Bの開始 Aの開始=Ｂの開始 Bの開始+0 ≦ Aの開始

時間制約の応用 2（開始時間固定） モデル名.addTemporal(source,A,"SS",50) モデル名.addTemporal(A, source,"SS",-50) Aの開始を50に 固定 ダミーの始点（source）の開始+50 ≦ Aの開始 Aの開始-50 ≦ダミーの始点（source）の開始 sourceの開始時刻は0 Aの開始=50

時間制約の応用 3 （最大・最小段取り時間） モデル名.addTemporal(A,B,"CS",10) 10分最大30分で Bを開始 モデル名.addTemporal(A,B,"CS",10) モデル名.addTemporal(B,A,"SC",-30) Aの終了+10 ≦ Bの開始 Bの開始-30 ≦Aの終了 Bの開始≦ Aの終了+30 Bの開始はAの終了+[10,30]

航空機を早く離陸させよう！ PERT: Program Evaluation and Review Technique,第二次世界大戦のポラリス潜水艦の建造で利用．（ORの古典） 13分 15分 27分 作業1 作業2 作業3 作業4 完了時刻最小化 22分 25分 ダミー作業 先行制約 作業5 作業１：乗客降ろし（１３分） 作業２：荷物降ろし（２５分） 作業３：機内清掃（１５分） 作業４：乗客搭乗（２７分） 作業５：荷物積み込み（２２分） 点が作業（活動）のグラフ->点上活動図式

航空機を早く離陸させよう！ 完了時刻最小化 先行制約 作業１：乗客降ろし（１３分） 作業２：荷物降ろし（２５分） 作業３：機内清掃（１５分） 22分 25分 13分 15分 27分 作業1 作業2 作業3 作業4 作業5 ダミー作業 先行制約 完了時刻最小化 開始時刻 終了時刻 作業１：乗客降ろし（１３分） 作業２：荷物降ろし（２５分） 作業３：機内清掃（１５分） 作業４：乗客搭乗（２７分） 作業５：荷物積み込み（２２分）

Pythonインターフェイスによる記述（１） OptSeqⅡのモジュールを読み込む モデルオブジェクトm1 を作成　 作業時間を作業をキー，作業時間を値とする辞書duration に保管 from optseq2 import *　　　 m1=Model()　　　　　　　　　 duration ={1:13, 2:25, 3:15, 4:27, 5:22 }　　 　　　　キー　　　値

Pythonインターフェイスによる記述（２） 作業を保管するための空の辞書actを作成 モードを保管するための空の辞書mode を作成　 act={} mode={}

Pythonインターフェイスによる記述（３） モデルオブジェクトm1 のaddActivity(“作業名”) メソッドを用いてモデルに作業を追加 モードクラスMode(“モード名”, 作業時間) を用いてモードに必要な作業時間を入力 addModes メソッドを用いて作業にモードを追加 for i in duration: act[i]=m1.addActivity("Act[%s]"%i) mode[i]=Mode("Mode[%s]"%i,duration[i]) act[i].addModes(mode[i])

Pythonインターフェイスによる記述（４） モデルに addTemporal (先行作業, 後続作業) メソッドを用いて時間制約を追加 m1.addTemporal(act[1],act[3]) m1.addTemporal(act[2],act[4]) m1.addTemporal(act[2],act[5]) m1.addTemporal(act[3],act[4])

Pythonインターフェイスによる記述（５） m1.optimize() を入力して求解 m1.Params.TimeLimit=1　　　　求解時の制限時間 m1.Params.OutputFlag=True　 モデルを出力する場合True 　　 m1.Params.Makespan=True　　最大完了時刻最小化の時はTrue m1.optimize()

Pythonインターフェイスによる記述（６） from optseq2 import * m1=Model() duration ={1:13, 2:25, 3:15, 4:27, 5:22 } act={} mode={} for i in duration: act[i]=m1.addActivity("Act[%s]"%i) mode[i]=Mode("Mode[%s]"%i,duration[i]) act[i].addModes(mode[i]) m1.addTemporal(act[1],act[3]) m1.addTemporal(act[2],act[4]) m1.addTemporal(act[2],act[5]) m1.addTemporal(act[3],act[4]) m1.Params.TimeLimit=1 m1.Params.OutputFlag=True m1.Params.Makespan=True m1.optimize()

Pythonインターフェイスによる記述（７） 実行結果（一部） source ---: 0 0 　　　 　　　　　　　　　ダミーの始点の開始時刻が０ sink ---: 55 55 　　　　　　　　 ダミーの終点の開始時刻が５５（完了時刻） activity[1] ---: 0 0--13 13 　　　 作業１は０に開始されて１３に終了 activity[2] ---: 0 0--25 25 　　　 作業２は０に開始されて２５に終了 activity[3] ---: 13 13--28 28 　　　　 作業３は１３に開始されて２８に終了 activity[4] ---: 28 28--55 55 　　　 作業４は２８に開始されて５５に終了 activity[5] ---: 25 25--47 47 　　　　 作業５は２５に開始されて４７に終了 objective value = 55　　　　　　　　　　目的関数 cpu time = 0.00/1.00(s)　　　　 　　　　計算時間 iteration = 1/15962 反復回数

航空機を早く離陸させよう！最適解

航空機を早く離陸させよう！ 作業員１人 完了時刻最小化 先行制約 作業１：乗客降ろし（１３分） 作業２：荷物降ろし（２５分） 22分 25分 13分 15分 27分 作業1 作業2 作業3 作業4 作業5 ダミー作業 先行制約 完了時刻最小化 開始時刻 終了時刻 作業１：乗客降ろし（１３分） 作業２：荷物降ろし（２５分） 作業３：機内清掃（１５分） 作業４：乗客搭乗（２７分） 作業５：荷物積み込み（２２分） 作業員１人

Pythonインターフェイスによる記述（１） 資源（この例題の場合は作業員）制約の記述： モデル名.addResource（“資源名”,( 時刻1, 時刻2):供給量) モードに資源使用量追加： モード名.addResource （資源,(資源使用可能区間):使用量) r e s=m1. addResource ( "worker " , (0 , " i n f " ) : 1 ) for i in duration: act[i]=m1.addActivity("Act[%s]"%i) mode[i]=Mode("Mode[%s]"%i,duration[i]) mode[i].addResource(res,{(0,"inf"):1}) act[i].addModes(mode[i])

Pythonインターフェイスによる記述（２） from optseq2 import * m1=Model() duration ={1:13, 2:25, 3:15, 4:27, 5:22 } res=m1.addResource("worker",capacity={(0,"inf"):1}) act={} mode={} for i in duration: act[i]=m1.addActivity("Act[%s]"%i) mode[i]=Mode("Mode[%s]"%i,duration[i]) mode[i].addResource(res,{(0,"inf"):1}) act[i].addModes(mode[i]) m1.addTemporal(act[1],act[3]) m1.addTemporal(act[2],act[4]) m1.addTemporal(act[2],act[5]) m1.addTemporal(act[3],act[4]) m1.Params.TimeLimit=1 m1.Params.OutputFlag=True m1.Params.Makespan=True m1.optimize()

Pythonインターフェイスによる記述（３） 　実行結果（一部） source ---: 0 0 sink ---: 102 102 activity[1] ---: 47 47--60 60 activity[2] ---: 0 0--25 25 activity[3] ---: 60 60--75 75 activity[4] ---: 75 75--102 102 activity[5] ---: 25 25--47 47 objective value = 102 cpu time = 0.00/3.00(s) iteration = 0/64983

並列ショップスケジューリング ピットイン時間を短縮せよ！ ３人のピットクルー （資源制約） 資源（機械）制約 があると難しい！

Pythonインターフェイスによる記述（１） ３人の作業員記述：資源制約モデル名.addResource（"資源名",( 時刻1, 時刻2):供給量) の供給量を3 に設定 from optseq2 import * m1=Model() duration ={1:3, 2:2, 3:2, 4:2, 5:4, 6:4, 7:4, 8:4, 9:11, 10:2 } res=m1.addResource("worker",capacity={(0,"inf"):3}) act={} mode={} for i in duration: act[i]=m1.addActivity("Act[%s]"%i) mode[i]=Mode("Mode[%s]"%i,duration[i]) mode[i].addResource(res,{(0,"inf"):1}) act[i].addModes(mode[i])

Pythonインターフェイスによる記述（２） 時間制約 求解実行 m1.addTemporal(act[1],act[9]) for i in range(5,9): m1.addTemporal(act[4],act[i]) m1.addTemporal(act[i],act[10]) m1.Params.TimeLimit=1 m1.Params.OutputFlag=True m1.Params.Makespan=True m1.optimize()

Pythonインターフェイスによる記述（３） from optseq2 import * m1=Model() duration ={1:3, 2:2, 3:2, 4:2, 5:4, 6:4, 7:4, 8:4, 9:11, 10:2 } res=m1.addResource("worker",capacity={(0,"inf"):3}) act={} mode={} for i in duration: act[i]=m1.addActivity("Act[%s]"%i) mode[i]=Mode("Mode[%s]"%i,duration[i]) mode[i].addResource(res,{(0,"inf"):1}) act[i].addModes(mode[i]) m1.addTemporal(act[1],act[9]) for i in range(5,9): m1.addTemporal(act[4],act[i]) m1.addTemporal(act[i],act[10]) m1.Params.TimeLimit=1 m1.Params.OutputFlag=True m1.Params.Makespan=True m1.optimize()

Pythonインターフェイスによる記述（４） 　実行結果（一部） source ---: 0 0 sink ---: 14 14 prepare ---: 0 0--3 3 water ---: 0 0--2 2 front ---: 0 0--2 2 jackup ---: 2 2--4 4 tire1 ---: 8 8--12 12 tire2 ---: 4 4--8 8 tire3 ---: 8 8--12 12 tire4 ---: 4 4--8 8 oil ---: 3 3--14 14 jackdown ---: 12 12--14 14 objective value = 14 cpu time = 0.00/3.00(s) iteration = 0/37644

並列ショップスケジューリング - 複数モード - gas W A T E R 4 2 3 11 作業１ 作業２ 作業３ 作業４ 作業５ 作業６ 作業７ 作業８ 作業９ 作業１０ 秒 １人　　　３秒 ２人　　　２秒 ３人　　　１秒 ３人のピットクルー （資源制約） 資源（機械）制約 があると難しい！

並列ショップスケジューリング 2 - モードの概念と使用法 - 並列ショップスケジューリング 2 　- モードの概念と使用法 - モード：作業を行うための処理方法 例： 作業 「ジュースを買う」 コンビニモード： 作業時間 20 分，お金資源 120 円，人資源 1人 自販機モード： 作業時間 5 分，お金資源 120 円，人資源 1人 スーパーモード： 作業時間 40 分，お金資源 100 円，人資源 1人，車資源 1 台

Pythonインターフェイスによる記述（１） for i in duration: act[i]=m1.addActivity("Act[%s]"%i) if i==1: mode[1,1]=Mode("Mode[1_1]",3) mode[1,1].addResource(res,{(0,"inf"):1}) mode[1,2]=Mode("Mode[1_2]",2) mode[1,2].addResource(res,{(0,"inf"):2}) mode[1,3]=Mode("Mode[1_3]",1) mode[1,3].addResource(res,{(0,"inf"):3}) act[i].addModes(mode[1,1],mode[1,2],mode[1,3]) else: mode[i]=Mode("Mode[%s]"%i,duration[i]) mode[i].addResource(res,{(0,"inf"):1}) act[i].addModes(mode[i]) 　多モードの記述 作業１のモード１ 作業１のモード１に 資源を追加 作業１にモード１， モード２，モード３ を追加

Pythonインターフェイスによる記述（２） for i in duration: act[i]=m1.addActivity("Act[%s]"%i) if i==1: mode[1,1]=Mode("Mode[1_1]",3) mode[1,1].addResource(res,{(0,"inf"):1}) mode[1,2]=Mode("Mode[1_2]",2) mode[1,2].addResource(res,{(0,"inf"):2}) mode[1,3]=Mode("Mode[1_3]",1) mode[1,3].addResource(res,{(0,"inf"):3}) 　　 act[i].addModes(mode[1,1],mode[1,2],mode[1,3]) else: mode[i]=Mode("Mode[%s]"%i,duration[i]) mode[i].addResource(res,{(0,"inf"):1}) act[i].addModes(mode[i]) from optseq2 import * m1=Model() duration ={1:3, 2:2, 3:2, 4:2, 5:4, 6:4, 7:4, 8:4, 9:11, 10:2 } res=m1.addResource("worker",capacity={(0,"inf"):3}) act={} mode={}

Pythonインターフェイスによる記述（３） m1.addTemporal(act[1],act[9]) for i in range(5,9): m1.addTemporal(act[4],act[i]) m1.addTemporal(act[i],act[10]) m1.Params.TimeLimit=1 m1.Params.OutputFlag=True m1.Params.Makespan=True m1.optimize()

Pythonインターフェイスによる記述（４） objective value = 13 cpu time = 0.00/1.00(s) iteration = 7/7343 source --- 0 0 sink --- 13 13 Act[1] Mode[1_3] 0 1 Act[2] --- 1 3 Act[3] --- 11 13 Act[4] --- 1 3 Act[5] --- 7 11 Act[6] --- 3 7 Act[7] --- 7 11 Act[8] --- 3 7 Act[9] --- 1 12 Act[10] --- 11 13 planning horizon= 13 計算結果とガントチャート

資源制約付きスケジュールング お家を早く造ろう！ 土台 １階 内装 屋根 完成！ 時間（日） 資源量（人） 3 ２人 １人の作業員休暇 作業時間＝２日 １日目１人，２日目２人の資源 が必要！

最適解 資源制約付きスケジューリングは一般的なモデル （ジョブショップ，並列ショップスケジューリングを特殊形として含む．）

Pythonインターフェイスによる記述（１） 　資源の必要量入力 m1=Model() duration ={1:1,2:3,3:2,4: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 } res=m1.addResource("worker") res.addCapacity(0,2,2) res.addCapacity(2,3,1) res.addCapacity(3,"inf",2) {(0,1):2 } {(開始時刻，終了時刻):資源必要量 } 土台造り（ req[1] ）は１日目に 資源（人）が２単位必要 　資源の容量制約入力 (0,2,2)　　　 （開始時刻，終了時刻，資源容量）　 最初の２日間は資源（人）が ２単位使用可能

Pythonインターフェイスによる記述（２） from optseq2 import * m1=Model() duration ={1:1,2:3,3:2,4: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 } res=m1.addResource("worker") res.addCapacity(0,2,2) res.addCapacity(2,3,1) res.addCapacity(3,"inf",2) act={} mode={} for i in duration: act[i]=m1.addActivity("Act[%s]"%i) mode[i]=Mode("Mode[%s]"%i,duration[i]) mode[i].addResource(res,req[i]) act[i].addModes(mode[i]) m1.addTemporal(act[1],act[2]) m1.addTemporal(act[1],act[3]) m1.addTemporal(act[2],act[4]) m1.Params.TimeLimit=1 m1.Params.OutputFlag=True m1.Params.Makespan=True m1.optimize()

Pythonインターフェイスによる記述（３） 　実行結果（一部） objective value = 6 cpu time = 0.00/1.00(s) iteration = 1/6936 source --- 0 0 sink --- 6 6 Act[1] --- 0 1 Act[2] --- 1 4 Act[3] --- 3 5 Act[4] --- 4 6 planning horizon= 6

１機械スケジュールング 納期遅れを最小にしよう！ 完了時刻最小化（メイクスパン）以外の目的関数の例 納期遅れ最小化 納期ずれ最小化 納期遅れした作業（ジョブ）数最小化 納期遅れの最大値の最小化 上の指標の重み付きの尺度最小化 ．．．． 会社名 A社 B社 C社 D社 作業時間 1日 2日 3日 4日 納期 5日後 9日後 6日後 4日後

Pythonインターフェイスによる記述（１） 　納期に関する入力 　納期を辞書に保管 due={1:5,2:9,3:6,4:4} ．．．．．．． for i in req: act[i]=m1.addActivity("Act[%s]"%i,duedate=due[i]) mode[i]=Mode("Mode[%s]"%i,req[i]) mode[i].addResource(res,{(0,"inf"):1}) act[i].addModes(mode[i]) 　納期を作業に追加

Pythonインターフェイスによる記述（２） from optseq2 import * m1=Model() due={1:5,2:9,3:6,4:4} req={1:1, 2:2, 3:3, 4:4 } res=m1.addResource("writer") res.addCapacity(0,"inf",1) act={} mode={} for i in req: act[i]=m1.addActivity("Act[%s]"%i,duedate=due[i]) mode[i]=Mode("Mode[%s]"%i,req[i]) mode[i].addResource(res,{(0,"inf"):1}) act[i].addModes(mode[i]) m1.Params.TimeLimit=1 m1.Params.OutputFlag=True m1.Params.Makespan=False m1.optimize()

Pythonインターフェイスによる記述（３） --- best solution --- source,---, 0 0 sink,---, 10 10 Act[1],---, 4 4--5 5 Act[2],---, 8 8--10 10 Act[3],---, 5 5--8 8 Act[4],---, 0 0--4 4 --- tardy activity --- Act[2]: 1 Act[3]: 2 　実行結果（一部） 会社名 A社 B社 C社 D社 作業時間 1日 2日 3日 4日 納期 5日後 9日後 6日後 4日後

航空機をもっと早く離陸させよう! クリティカルパス法 （critical path method，略してCPM） 作業時間を費用をかけることによって短縮できる 作業1：乗客降ろし 13分．10分に短縮可能で，1 万円必要． 作業2：荷物降ろし 25分．20 分に短縮可能で，1万円必要． 作業3：機内清掃 15 分．10分に短縮可能で， 1万円必要． 作業4：新しい乗客の搭乗 27 分．25分に短縮可能で，1万円必要． 作業5： 新しい荷物積み込み 22 分．20分に短縮可能で， 1万円必要． 再生不能資源（使用可能なお金）4 万万円以下

再生可能資源と再生不能資源 再生可能資源 作業完了後に再び使用可能になる資源 機械や作業員など 再生不能資源 一度使うとなくなってしまう資源（計画期間内での合計に制約を設ける） お金や原材料など クリティカルパス法の予算を再生不能資源として扱う！

Pythonインターフェイスによる記述（１） 　再生不能資源に関する入力（１） m1=Model() durationA = {1:13, 2:25, 3:15, 4:27, 5:22 } durationB = {1:10, 2:20, 3:10, 4:25, 5:20 } act={} mode={} res=m1.addResource("money",rhs=4,direction="<=") 通常時の 作業時間 再生不能 資源使用時の作業時間 　再生不能資源 使用可能量制約

Pythonインターフェイスによる記述（２） from optseq2 import * m1=Model() durationA = {1:13, 2:25, 3:15, 4:27, 5:22 } durationB = {1:10, 2:20, 3:10, 4:25, 5:20 } act={} mode={} res=m1.addResource("money",rhs=4,direction="<=") for i in durationA: act[i]=m1.addActivity("Act[%s]"%i) mode[i,1]=Mode("Mode[%s][1]"%i,durationA[i]) mode[i,2]=Mode("Mode[%s][2]"%i,durationB[i]) act[i].addModes(mode[i,1],mode[i,2]) res.addTerms(1,act[i],mode[i,2]) m1.addTemporal(act[1],act[3]) m1.addTemporal(act[2],act[4]) m1.addTemporal(act[2],act[5]) m1.addTemporal(act[3],act[4]) print m1 m1.Params.TimeLimit=1 m1.Params.OutputFlag=True m1.Params.Makespan=True m1.optimize()

結果

並列ショップスケジューリング 複数モード 複数資源による作業の並列処理 １人 ３秒 ２人 ２秒 ３人のピットクルー ３人 １秒 （資源制約） gas W A T E R 4 2 3 11 作業１ 作業２ 作業３ 作業４ 作業５ 作業６ 作業７ 作業８ 作業９ 作業１０ 秒 １人　　　３秒 ２人　　　２秒 ３人　　　１秒 ３人のピットクルー （資源制約） 資源（機械）制約 があると難しい！

Pythonインターフェイスによる記述（１） 　並列処理入力 for i in duration: act[i]=m1.addActivity("Act[%s]"%i) mode[i]=Mode("Mode[%s]"%i,duration[i]) mode[i].addResource(res,{(0,"inf"):1}) if i==1: mode[i].addParallel(1,1,3) act[i].addModes(mode[i]) 1番目の小作業を3単位並列可能

Pythonインターフェイスによる記述（２） from optseq2 import * m1=Model() duration ={1:3, 2:2, 3:2, 4:2, 5:4, 6:4, 7:4, 8:4, 9:11, 10:2 } res=m1.addResource("worker") res.addCapacity(0,"inf",3) act={} mode={} for i in duration: act[i]=m1.addActivity("Act[%s]"%i) mode[i]=Mode("Mode[%s]"%i,duration[i]) mode[i].addResource(res,{(0,"inf"):1}) if i==1: mode[i].addParallel(1,1,3) act[i].addModes(mode[i]) m1.addTemporal(act[1],act[9]) for i in range(5,9): m1.addTemporal(act[4],act[i]) m1.addTemporal(act[i],act[10]) m1.Params.TimeLimit=1 m1.Params.OutputFlag=True m1.Params.Makespan=True m1.optimize()

ジョブショップスケジューリンング ジョブ（作業）ごとに機械（工程）順が異なっても良い！ 作業 機械 作業1 作業2 作業3 作業4 機械2 機械3 機械1 作業1 小作業1 小作業2 小作業3 機械3 機械2 機械1 作業2 機械1 機械3 機械2 作業3 機械2 機械3 機械1 作業4

ジョブショップスケジューリンング 各作業は，最初の２日間は作業員の作業が必要 各作業は小作業1,2,3の順に処理される 各作業は１日目の作業後休むことが可能 作業員は平日（週５日間）のみ作業可能 作業員は１日最大２人作業可能 機械１の最初の２日間分の作業は並列処理可能 機械２はexpressモードで処理可能；処理時間は４日間に短縮可能 expressモードは最大１回しか使用できない 機械１での作業２は，作業１が完了した直後に行う （他の作業が間に入らない）

Pythonインターフェイスによる記述（１） 　機械に関する制約 machine={} for j in range(1,4): 　machine[j]=m1.addResource("machine[%s]"%j,capacity={(0,"inf"):1})　　# ３種類の機械；各機械は１つの作業しか処理できない 　作業員に関する制約 manpower=m1.addResource("manpower") for t in range(9): manpower.addCapacity(t*7,t*7+5,2)　　#　作業員は平日のみ作業可能；平日の作業可能な作業員上限２人

Pythonインターフェイスによる記述（２） 　作業と機械 10 4 7 小作業１ 小作業２ 小作業３ 作業１ 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) } (1,1): (1,7) は作業１の子作業１の機械１での作業時間が７日であること

Pythonインターフェイスによる記述（３） 　機械２はexpressモードで処理可能 budget=m1.addResource(“budget_constraint”,rhs=1)　　#　expressモードが１回しか使え ないことを資源（budget）の使用可能量(rhs) =1で表現 express=Mode("Express",duration=4)　#　 express の作業時間は４日 express.addResource(machine[2],{(0,"inf"):1},"max")　#　 express は機械２を１単位使用 express.addResource(manpower,{(0,2):1})　　#　最初の２期の間は作業員が１人必要 express.addBreak(1,1)　　　　#　各作業は１日目作業後休憩可能 express.addResource(machine[2],{(0,"inf"):1},"max") 資源タイプ 資源タイプ“max”：並列作業時も機械は１単位しか使用しない

Pythonインターフェイスによる記述（４） 　作業にモード追加 for (i,j) in JobInfo: act[i,j]=m1.addActivity(“Act[%s][%s]”%(i,j))　　　 　#　（作業名） mode[i,j]=Mode(“Mode[%s][%s]”%(i,j),duration=JobInfo[i,j][1])＃モード名,作業時間追加　 　 mode[i,j].addResource(machine[JobInfo[i,j][0]],{(0,“inf”):1},“max”) 　mode[i,j].addResource(manpowe):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: act[i,j].addModes(mode[i,j],express)　　　　 # 機械２にexpressモードを追加 budget.addTerms(1,act[i,j],express)　　　 # expressモードは最大１回しか使用できない else: act[i,j].addModes(mode[i,j])

Pythonインターフェイスによる記述（５） 　各作業は子作業1,2,3の作業順で処理される for i in range(1,5): for j in range(1,3): m1.addTemporal(act[i,j],act[i,j+1])　 小作業１ 小作業２ 小作業３ 作業１ 小作業１ 小作業２ 小作業３ 作業２ 小作業１ 小作業２ 小作業３ 作業３ 小作業１ 小作業２ 小作業３ 作業４

Pythonインターフェイスによる記述（６） 機械１での作業２は，作業１が完了した直後に行う （他の作業が間に入らない） ダミーの作業を生成 d_act=m1.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)　　　　　　　　　 #　作業にモードを追加 作業時間 0 のダミーの作業 資源使用量 休憩中にも資源を使用 作業開始時刻から無限に休憩可能 期

Pythonインターフェイスによる記述（６） 2.　時間制約追加 m1.addTemporal(act[1,1],d_act,tempType=“CS”)　#(1) m1.addTemporal(d_act,act[1,1],tempType="SC") #(2) m1.addTemporal(d_act,act[2,2],tempType="CS") #(3) m1.addTemporal(act[2,2],d_act,tempType="SC") #(4) (1)　作業1の小作業1(act[1,1]) が終了しないとダミー作業 (d_act) が開始できない ダミー作業 (d_act) が開始しないと作業1の小作業1 (act[1,1]) が終了できない (3) , (4) も (1) , (2) と同様 結論：　作業1の小作業1 はダミー作業の直後に開始 　　　　　ダミー作業は作業1の小作業1 の直後に開始 資源使用量 ダミー作業 　　　act[2,2] act[1,1] ダミー作業は休憩中にも資源を使用 期

Pythonインターフェイスによる記述（７） from optseq2 import * m1=Model() machine={} for j in range(1,4): 　 machine[j]=m1.addResource("machine[%s]"%j,capacity={(0,"inf"):1}) manpower=m1.addResource("manpower") for t in range(9): manpower.addCapacity(t*7,t*7+5,2) budget=m1.addResource("budget_constraint",rhs=1) 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={}

Pythonインターフェイスによる記述（８） for (i,j) in JobInfo: act[i,j]=m1.addActivity("Act[%s][%s]"%(i,j)) mode[i,j]=Mode("Mode[%s][%s]"%(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: act[i,j].addModes(mode[i,j],express) budget.addTerms(1,act[i,j],express) else: act[i,j].addModes(mode[i,j]) 　Pythonコードまとめ（２） express=Mode("Express",duration=4) express.addResource(machine[2],{(0,"inf"):1},"max") express.addResource(manpower,{(0,2):1}) express.addBreak(1,1) mode={}

Pythonインターフェイスによる記述（９） for i in range(1,5): for j in range(1,3): m1.addTemporal(act[i,j],act[i,j+1]) d_act=m1.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) m1.addTemporal(act[1,1],d_act,tempType="CS") m1.addTemporal(d_act,act[1,1],tempType="SC") m1.addTemporal(d_act,act[2,2],tempType="CS") m1.addTemporal(act[2,2],d_act,tempType="SC") m1.Params.TimeLimit=1 m1.Params.OutputFlag=True m1.Params.Makespan=True m1.optimize()