最適化セミナーのご案内

2.25.4 リスケジューリング問題

 実際の現場では,ある時機械が故障した等の突発事故が起こる事がしばしばあります.その場合,過去のスケジュールを固定し,条件を変更した後,再度スケジュールを組み直します.このような問題をリスケジューリング問題と呼ぶ事にします.

例題 リスケジューリング問題

 前節のジョブショップ問題を解いた結果,各作業の開始時刻は,

  作業1(機械1) 作業2(機械2) 作業3(機械3)
仕事a 0 14 5
仕事b 5 10 14
仕事c 10 0 20

 

となりました.このスケジュールに基づいて機械を運転していた所,10時間が過ぎた所で,機械2が故障し,5時間停止する事になりました.この場合の最後の作業の完了時刻が最小となるようにはどのようにスケジュールを組み直せばよいでしょうか.

 この問題を記述するには,過去のスケジュールを固定する為,アクティビティ固定関数(fixActivity)を使用する必要があります.また,未来のスケジュールが過去に来ないようにする為,全ての作業に先行するsourceActivity(自動で定義されている)という先行制約を記述する必要があります.

 以上のことを踏まえると,制約としては新たに以下のものが加わります.

アクティビティの開始時刻固定
$fixActivity(act_{a,1}.startTime)$ 仕事aの作業1の開始時刻を0に固定する
$fixActivity(act_{a,3}.startTime)$ 仕事aの作業3の開始時刻を5に固定する
$fixActivity(act_{b,1}.startTime)$ 仕事bの作業1の開始時刻を5に固定する
$fixActivity(act_{c,2}.startTime)$ 仕事cの作業2の開始時刻を0に固定する
 
アクティビティのモード固定
$fixActivity(act_{a,1})$ 仕事aの作業1のモードをmode_a_1に固定する
$fixActivity(act_{a,3})$ 仕事aの作業3のモードをmode_a_3に固定する
$fixActivity(act_{b,1})$ 仕事bの作業1のモードをmode_b_1に固定する
$fixActivity(act_{c,2})$ 仕事cの作業2のモードをmode_c_2に固定する
 
先行制約
$sourceActivity \prec act_{a,2}, 10$ 仕事aの作業2は,時刻10以前には処理されない
$sourceActivity \prec act_{b,2} ,10$ 仕事bの作業2は,時刻10以前には処理されない
$sourceActivity \prec act_{b,3}, 10$ 仕事bの作業3は,時刻10以前には処理されない
$sourceActivity \prec act_{c,1}, 10$ 仕事cの作業1は,時刻10以前には処理されない
$sourceActivity \prec act_{c,3}, 10$ 仕事cの作業3は,時刻10以前には処理されない

 また,機械2は,時刻10から5時間停止するので,資源が以下の様に修正されます.

資源
machine1 機械1,供給量:常に1
machine2 機械2,供給量:時刻10以上15未満0,その他常に1
machine3 機械3,供給量:常に1

 これをSIMPLEで記述すると以下の様になります.

// 作業集合
Set J; // 仕事
Element j(set=J);
Set S; // 作業
Element s(set=S);
// モード集合
Set M;
Element m(set=M);
Set AvailMode(name="AvailMode", index=(j,s)); // 各仕事のオペレーションにおいて処理されるモード
// 資源集合
Set R;
Element r(set=R);
// 作業時間集合
Set D; // 各モードの作業時間の最大
Element d(set=D);
// 期間集合
Set T; // スケジュール期間
T = "0 .. 30";
Element t(set=T);
// アクティビティ(変数)
Activity act(name="act", index=(j,s), mode=AvailMode[j,s]);

// 必要資源量(定数)
ResourceRequire req(name="req", mode=M, resource=R, duration=D);
// 資源供給量(定数)
ResourceCapacity cap(name="cap", resource=R, timeStep=T);
cap[r,t] = 1;
cap["machine2", t] = 0, 10<=t<=14; // 故障に対応

// 目的関数(最後の作業の完了時刻の最小化)
Objective f(type=minimize);
f = completionTime;

// 先行制約
Set Prec(name="Prec", dim=3);
Element u(set=S);
Element v(set=S);
act[j,u] < act[j,v], (j,u,v)<Prec;

/* --- リスケジューリングの為の制約 --- */
// 過去(0 .. 10) のスケジュールを固定
Set FixAct(name="FixAct", dim=2);
Parameter fixTime(name="fixTime", index=(j,s));
act[j,s].startTime = fixTime[j,s], (j,s) < FixAct;
Parameter fixMode(name="fixMode", index=(j,s));
act[j,s] = fixMode[j,s], (j,s) < FixAct;
fixActivity(act[j,s].startTime, (j,s) < FixAct);
fixActivity(act[j,s], (j,s) < FixAct);
// 過去のジョブ以外はステップ 10 以前に来てはならない
Set NotFixAct(name="NotFixAct", dim=2);
NotFixAct = setOf((j,s), (j < J, s < S)) - FixAct;
sourceActivity < act[j,s], (j,s) < NotFixAct, 10;
/* ------------------------------------ */

options.maxtim = 15;
solve();

simple_printf("act[%s,%d] = %d\n", j, s,  act[j,s].startTime);

 データファイルの1つが以下の様に修正されます.

AvailMode =
[a,1] mode_a_1
[a,2] mode_a_2
[a,3] mode_a_3
[b,1] mode_b_1
[b,2] mode_b_2
[b,3] mode_b_3
[c,1] mode_c_1
[c,2] mode_c_2
[c,3] mode_c_3
;

Prec =
a 1 3
a 3 2
b 1 2
b 2 3
c 2 1
c 1 3
;

FixAct =
a 1
a 3
b 1
c 2
;

fixTime = [a,1] 0 [a,3] 5 [b,1] 5 [c,2] 0;
fixMode = [a,1] mode_a_1 [a,3] mode_a_3 [b,1] mode_b_1 [c,2] mode_c_2;

 実行すると,各作業の開始時刻が以下のように出力されます.

act[a,1] = 0
act[a,2] = 19
act[a,3] = 5
act[b,1] = 5
act[b,2] = 15
act[b,3] = 21
act[c,1] = 10
act[c,2] = 0
act[c,3] = 16

 


 

 

上に戻る