Nuorium Optimizer C++SIMPLE例題集 V27

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

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

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

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

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

　これをC++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);

　データファイルは「2.25.2フローショップ問題」で使用したreq.datと次のdata.datを使用します．

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

　

---

 

 

上に戻る