スケジューリング最適化システム
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： 最大並列数
作業の途中中断
• Pythonインターフェイスによる記述
モード名.addBreak(中断開始時刻,中断終了時刻,最大中断時間)
作業Aが，0から3の区間でそれぞれ最大1中断可能：
モード名.addBreak(0,3,1)
開始から2時刻で中断した例
作業の並列処理
• 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 (先行作業 , 後続作業 , “制約タイプ” , 時間ずれ)
Completion
Start
A
B
先行作業
後続作業
作業Aの完了後に作業Bの開始
Temporal(pred=A, succ=B, tempType=“CS”, delay=0)
制約タイプ（type）
Start
Start
A
B
Start
type SS
Completion
A
B
Completion
A
type SC
Completion
B
type CC
時間ずれ（delay）
Completion
A
Start
B
10
Completion
A
作業Bの開始可能時間帯
Start
B
作業Bの開始可能時間帯
10
delay 10
delay -10
時間制約の応用 1（同時開始）
• Pythonインターフェイスによる記述
モデル名.addTemporal(先行作業,後続作業,“制約タイプ”,時間ずれ)
AとBの同時開始
モデル名.addTemporal(A,B,"SS",0)
モデル名.addTemporal(B,A,"SS",0)
Aの開始+0 ≦ Bの開始
Aの開始=Ｂの開始
Bの開始+0 ≦ Aの開始
時間制約の応用 2（開始時間固定）
Aの開始を50に モデル名.addTemporal(source,A,"SS",50)
固定
モデル名.addTemporal(A, source,"SS",-50)
ダミーの始点（source）の開始+50 ≦ Aの開始
Aの開始-50 ≦ダミーの始点（source）の開始
sourceの開始時刻は0
Aの開始=50
時間制約の応用 3
（最大・最小段取り時間）
Aの完了後最小
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の古典）
作業1
作業3
作業4
13分
15分
27分
完了時刻最小化
ダミー作業
先行制約
作業2
25分
作業5
22分
点が作業（活動）のグラフ->点上活動図式
作業１：乗客降ろし（１３分）
作業２：荷物降ろし（２５分）
作業３：機内清掃（１５分）
作業４：乗客搭乗（２７分）
作業５：荷物積み込み（２２分）
航空機を早く離陸させよう！
作業1
作業3
作業4
完了時刻最小化
開始時刻
15分
13分
27分
終了時刻
先行制約
作業2
ダミー作業
作業5
ダミー作業
25分
作業１：乗客降ろし（１３分）
22分 作業２：荷物降ろし（２５分）
作業３：機内清掃（１５分）
作業４：乗客搭乗（２７分）
作業５：荷物積み込み（２２分）
Pythonインターフェイスによる記述
（１）
• OptSeqⅡのモジュールを読み込む
from optseq2 import *
• モデルオブジェクトm1 を作成
m1=Model()
• 作業時間を作業をキー，作業時間を値とする辞
書duration に保管
duration ={1:13, 2:25, 3:15, 4:27, 5:22 }
キー
値
Pythonインターフェイスによる記述
（２）
• 作業を保管するための空の辞書actを作成
act={}
• モードを保管するための空の辞書mode を作成
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
m1.optimize()
最大完了時刻最小化の時はTrue
Pythonインターフェイスによる記述
（６）
• Pythonコードまとめ
from optseq2 import *
m1.addTemporal(act[1],act[3])
m1=Model()
m1.addTemporal(act[2],act[4])
duration ={1:13, 2:25, 3:15, 4:27, 5:22 }
m1.addTemporal(act[2],act[5])
act={}
m1.addTemporal(act[3],act[4])
mode={}
m1.Params.TimeLimit=1
for i in duration:
m1.Params.OutputFlag=True
act[i]=m1.addActivity("Act[%s]"%i)
m1.Params.Makespan=True
m1.optimize()
mode[i]=Mode("Mode[%s]"%i,duration[i])
act[i].addModes(mode[i])
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
反復回数
航空機を早く離陸させよう！最適解
作 業 1
作 業 3
13分
15分
作 業 2
25分
０
作 業 4
27分
作 業 5
22分
55
時 間
航空機を早く離陸させよう！
作業1
作業3
作業4
完了時刻最小化
15分
13分
開始時刻
27分
終了時刻
先行制約
作業2
ダミー作業
作業5
ダミー作業
25分
作業員１人
作業１：乗客降ろし（１３分）
22分 作業２：荷物降ろし（２５分）
作業３：機内清掃（１５分）
作業４：乗客搭乗（２７分）
作業５：荷物積み込み（２２分）
Pythonインターフェイスによる記述（１）
•資源（この例題の場合は作業員）制約の記述：
モデル名.addResource（“資源名”,( 時刻1, 時刻2):供給量)
r e s=m1. addResource ( "worker " , (0 , " i n f " ) : 1 )
•モードに資源使用量追加：
モード名.addResource （資源,(資源使用可能区間):使用
量)
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インターフェイスによる記述
（２）
• Pythonコードまとめ
from optseq2 import *
m1.addTemporal(act[1],act[3])
m1=Model()
m1.addTemporal(act[2],act[4])
duration ={1:13, 2:25, 3:15, 4:27, 5:22 }
m1.addTemporal(act[2],act[5])
res=m1.addResource("worker",capacity={(0,"inf"):1}
)
m1.addTemporal(act[3],act[4])
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.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
並列ショップスケジューリング
ピットイン時間を短縮せよ！
gas
3秒
作業１
作業９
11
秒
３人のピットクルー
（資源制約）
WA
TE
R
2
作業２
秒
作業５
2秒
4
作業６
作業３
作業７
作業８
作業４
2
秒
秒
4
秒
4秒
4
秒
2
秒
作業１０
資源（機械）制約
があると難しい！
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})
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インターフェイスによる記述
（３）
• Pythonコードまとめ
from optseq2 import *
m1.addTemporal(act[1],act[9])
m1=Model()
for i in range(5,9):
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[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
１人
２人
３人
3 秒
作業１
作業２
2 秒
３秒
２秒
１秒
３人のピットクルー
（資源制約）
作業９ 11 秒
作業５
2秒
作業６
作業３
作業７
作業８
2秒
作業４
4秒
4秒
4秒
4 秒
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インターフェイスによる記述
（２）
• Pythonコードまとめ（１）
for i in duration:
act[i]=m1.addActivity("Act[%s]"%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={}
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インターフェイスによる記述
（３）
• 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
資源制約付きスケジュールング
お家を早く造ろう！
作業時間＝２日
１日目１人，２日目２人の資源
が必要！
１階
屋根
土台
完成！
１人の作業員休暇
資源量（人）
内装
２人
0
3
時間（日）
最適解
資源量（人）
時間（日）
資源制約付きスケジューリングは一般的なモデル
（ジョブショップ，並列ショップスケジューリングを特殊形として含む．）
Pythonインターフェイスによる記述
（１）
• 資源の必要量入力
{(0,1):2 }
m1=Model()
duration ={1:1,2:3,3:2,4:2}
{(開始時刻，終了時刻):資源必要
量}
土台造り（ req[1] ）は１日目に
資源（人）が２単位必要
• 資源の容量制約入力
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 }
(0,2,2)
res=m1.addResource("worker")
（開始時刻，終了時刻，資源容量）
最初の２日間は資源（人）が
２単位使用可能
res.addCapacity(0,2,2)
res.addCapacity(2,3,1)
res.addCapacity(3,"inf",2)
Pythonインターフェイスによる記述
（２）
• Pythonコードまとめ
from optseq2 import *
for i in duration:
m1=Model()
act[i]=m1.addActivity("Act[%s]"%i)
duration ={1:1,2:3,3:2,4:2}
mode[i]=Mode("Mode[%s]"%i,duration[i])
req={}
mode[i].addResource(res,req[i])
req[1]={(0,1):2 }
act[i].addModes(mode[i])
req[2]={(0,1):2 ,(1,3):1}
m1.addTemporal(act[1],act[2])
req[3]={(0,2):1 }
m1.addTemporal(act[1],act[3])
req[4]={(0,1):1,(1,2):2 }
m1.addTemporal(act[2],act[4])
res=m1.addResource("worker")
res.addCapacity(0,2,2)
m1.Params.TimeLimit=1
res.addCapacity(2,3,1)
m1.Params.OutputFlag=True
res.addCapacity(3,"inf",2)
m1.Params.Makespan=True
act={}
m1.optimize()
mode={}
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日
納期
9日後
6日後
4日後
5日後
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インターフェイスによる記述
（２）
• Pythonコードまとめ
from optseq2 import *
m1=Model()
due={1:5,2:9,3:6,4:4}
req={1:1, 2:2, 3:3, 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])
res=m1.addResource("writer")
res.addCapacity(0,"inf",1)
m1.Params.TimeLimit=1
m1.Params.OutputFlag=True
act={}
mode={}
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
• 実行結果（一部）
会社名 A社
B社
C社
D社
作業時 1日
間
2日
3日
4日
納期
9日後
5日後
作業4（D社）
6日後
4日後
作業1(A社）
--- tardy activity --Act[2]: 1
Act[3]: 2
作業3（C社）
納期遅れ
作業2（B社）
納期遅れ
時間（日）
０
10
A社納期
C社納期
D社納期
B社納期
航空機をもっと早く離陸させよう!
クリティカルパス法 （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インターフェイスによる記述
（２）
• Pythonコードまとめ
from optseq2 import *
m1.addTemporal(act[1],act[3])
m1=Model()
m1.addTemporal(act[2],act[4])
durationA = {1:13, 2:25, 3:15, 4:27, 5:22 }
m1.addTemporal(act[2],act[5])
durationB = {1:10, 2:20, 3:10, 4:25, 5:20 }
m1.addTemporal(act[3],act[4])
act={}
mode={}
print m1
res=m1.addResource("money",rhs=4,direction="<=")
for i in durationA:
m1.Params.TimeLimit=1
act[i]=m1.addActivity("Act[%s]"%i)
m1.Params.OutputFlag=True
mode[i,1]=Mode("Mode[%s][1]"%i,durationA[i])
m1.Params.Makespan=True
mode[i,2]=Mode("Mode[%s][2]"%i,durationB[i])
m1.optimize()
act[i].addModes(mode[i,1],mode[i,2])
res.addTerms(1,act[i],mode[i,2])
結果
作業1
4万 円
作業3
作業4
10分
10分
25分
作業5
作業2
20分
2 2分
０
45
作業1
1万 円
作業3
作業4
27分
10分
13分
作業5
作業2
25分
2 2分
０
0万 円
時間
52
作業1
作業3
作業4
15分
13分
時間
27分
作業5
作業2
25分
2 2分
０
時間
55
並列ショップスケジューリング
複数モード
gas
複数資源による作業の並列処理
１人
２人
３人
3 秒
作業１
作業２
2 秒
３秒
２秒
１秒
３人のピットクルー
（資源制約）
作業９ 11 秒
作業５
2秒
作業６
作業３
作業７
作業８
2秒
4秒
4秒
4秒
4 秒
2秒
作業１０
資源（機械）制約
があると難しい！
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})
1番目の小作業を
3単位並列可能
if i==1:
mode[i].addParallel(1,1,3)
act[i].addModes(mode[i])
Pythonインターフェイスによる記述
（２）
• Pythonコードまとめ
from optseq2 import *
m1.addTemporal(act[1],act[9])
m1=Model()
for i in range(5,9):
duration ={1:3, 2:2, 3:2, 4:2, 5:4, 6:4, 7:4, 8:4, 9:11, 10:2 }
m1.addTemporal(act[4],act[i])
res=m1.addResource("worker")
res.addCapacity(0,"inf",3)
m1.addTemporal(act[i],act[10])
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.Params.TimeLimit=1
m1.Params.OutputFlag=True
m1.Params.Makespan=True
m1.optimize()
ジョブショップスケジューリンング
ジョブ（作業）ごとに機械（工程）順が異なっても良い！
作業
機械
機械2
機械1
7
小作業1
小作業2
機械3
10
機械3
4
小作業3
機械2
機械1
作業2
９
11
5
機械1
3
機械2
6
機械2
機械3
９
機械3
13
作業1
作業3
12
機械1
9
作業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インターフェイスによる記述
（２）
• 作業と機械
7
小作業１
10
4
小作業３
小作業２
作業１
JobInfo={ (1,1):(1,7), (1,2):(2,10), (1,3):(3,4),
(1,1): (1,7) は作業１の子作業１の機
械１での作業時間が７日であること
(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)
}
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)
budget.addTerms(1,act[i,j],express)
else:
act[i,j].addModes(mode[i,j])
# 機械２にexpressモードを追加
# expressモードは最大１回しか使用できない
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])
小作業１
小作業３
小作業２
7
小作業１
10
4
小作業３
小作業２
９
11
5
小作業１
小作業１
９
12
作業３
小作業３
小作業２
6
作業２
小作業３
小作業２
3
作業１
13
9
作業４
Pythonインターフェイスによる記述
（６）
機械１での作業２は，作業１が完了した直後に行う
（他の作業が間に入らない）
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)
資源使用量
# 作業にモードを追加
作業時間 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) が開始できない
(2) ダミー作業 (d_act) が開始しないと作業1の小作業1 (act[1,1]) が終了できない
(3) , (4) も (1) , (2) と同様
結論： 作業1の小作業1 はダミー作業の直後に開始
ダミー作業は作業1の小作業1 の直後に開始
ダミー作業
資源使用量
act[1,1]
ダミー作業は休憩中にも資源を使用
act[2,2]
期
Pythonインターフェイスによる記述
（７）
• 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:
• Pythonコードまとめ
（２）
act[i,j]=m1.addActivity("Act[%s][%s]"%(i,j))
mode[i,j]=Mode("Mode[%s][%s]"%(i,j),
express=Mode("Express",duration=4)
duration=JobInfo[i,j][1])
express.addResource(machine[2],{(0,"i
nf"):1},"max")
mode[i,j].addResource（
express.addResource(manpower,{(0,2):
1})
mode[i,j].addResource(manpower,{(0,2):1})
express.addBreak(1,1)
mode[i,j].addBreak(1,1)
mode={}
if JobInfo[i,j][0]==1:
machine[JobInfo[i,j][0]],{(0,"inf"):1},"max")
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インターフェイスによる記述
（９）
• Pythonコードまとめ（３）
for i in range(1,5):
for j in range(1,3):
m1.addTemporal(act[i,j],act[i,j+1])
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")
d_act=m1.addActivity("dummy_activity")
m1.addTemporal(act[2,2],d_act,tempType="SC")
d_mode=Mode("dummy_mode")
m1.Params.TimeLimit=1
d_mode.addBreak(0,0)
m1.Params.OutputFlag=True
d_mode.addResource(machine[1],{(0,0):1},"break"
)
m1.Params.Makespan=True
d_act.addModes(d_mode)
m1.optimize()
© Copyright 2024 ExpyDoc
