Nuorium Optimizer C++SIMPLEマニュアル V27

7.11 資源制約付きスケジューリング問題記述例

　ここでは，資源制約付きスケジューリング問題の一種である人員スケジューリング問題を，C++SIMPLEを用いて記述する方法を紹介します．

　具体的には，次のような人員スケジューリング問題を考えます．

　この問題に対するC++SIMPLEの定式化は以下のようになります．

//
//  例題1 (全体の作業完了時刻最小化)
//
Set M = "A_does B_does C_does"; // モード
Element m(set = M);
Set R = "A B C";   // 資源
Element r(set = R);
Set D = "1 .. 11"; // 各モードの作業時間(日単位で最大が11日である)
Element d(set = D);
// モードと資源消費の連関
ResourceRequire  req(mode = M, resource = R, duration = D);
req["A_does, A", d] = 1, 1 <= d <= 6;
req["B_does, B", d] = 1, 1 <= d <= 8;
req["C_does, C", d] = 1, 1 <= d <= 11;
// アクティビティ
Set J = "1 .. 6";
Element j(set = J);
Activity act(name = "act", index = j, mode = M); // 作業(j = 1, …, 6)
// 利用可能な資源の定義
Set T = "0 .. 40"; // スケジューリング全体の時間(日単位で最大40日とする)
Element t(set = T);
ResourceCapacity cap(resource = R, timeStep = T);
cap[r, t] = 1;
Objective f(type = minimize);
f = completionTime; // 最後の作業の完了時刻最小化
options.maxtim = 2;
// 求解
solve();
// 解の表示
simple_printf("job = %d %s %2d %2d %2d\n", j, act[j], act[j].startTime, act[j].endTime,
  act[j].processTime);

　それでは，このモデルに対する定式化の手順を見ていきましょう．

　例題において実施しなければならない作業は6つの仕事です．そこでこれらを作業集合Jとして定義します．

Set J = "1 .. 6";

　それぞれの作業には，｛Aに任せる，Bに任せる，Cに任せる｝の三種類のモード（対処方法）が存在します．そこでこれらをモード集合Mとして定義します．

Set M = "A_does B_does C_does";

　モードが利用する資源は，A, B, Cの3人のみですから，これらを資源集合Rとして定義します．

Set R = "A B C";

　上記を整理すると次のようになります．

　次に，これら3つの集合の関連付けを行います．

　全ての作業は，モード集合のいずれかのモードで行われる事を示します．そのため，Activityの引数には作業集合Jの添字と，モード集合Mを与えます．

Set J = "1 .. 6";
Element j(set = J);
Set M = "A_does B_does C_does";
Activity act(index = j, mode = M);

　モードに対応する資源を与える定数ResourceRequireは次のように定義されます．引数には，モード集合Mと資源集合R以外に，新たに作業時間集合Dを定義する必要があります．今回の例では資源を用いる最大期間が11日なので，D = "1 .. 11"と定めています．

Set M = "A_does B_does C_does";
Set R = "A B C";
Set D = "1 .. 11";
Element d(set = D);
ResourceRequire req(mode = M, resource = R, duration = D);

　モードA_doesは資源Aを6日間，モードB_doesは資源Bを8日間，モードC_doesは資源Cを11日間用いるので，各々のResourceRequireの値は，次のように設定します．

ResourceRequire req(mode = M, resource = R, duration = D);
req["A_does, A", d] = 1, 1 <= d <= 6;
req["B_does, B", d] = 1, 1 <= d <= 8;
req["C_does, C", d] = 1, 1 <= d <= 11;

　次は資源供給量ResourceCapacityの設定です．各人は同時に2つ以上の仕事をすることはできないので，資源の上限値は，最後の期間まで全て1です．スケジューリングの期間は全体で40日なので，期間集合TはT = "0 .. 40"で定めます．なお，期間集合は0はじまりでなければなりません．これらをまとめると，次のように設定されます．

Set R = "A B C";
Element r(set = R);
Set T = "0 .. 40";
Element t(set = T);
ResourceCapacity cap(resource = R, timeStep = T);
cap[r, t] = 1; // 資源の上限値

　次に問題の種類を指定します．rcpspで扱う事の出来る問題は，

• 幾つかの作業が存在し，一定の資源下で最後の作業の完了時刻を最小化する問題
• 納期のある幾つかの作業が存在し，一定の資源下でそれらの納期遅れを最小化する問題

の二種類ですが，ここで扱う問題は前者です．これは目的関数で以下のように指定します．

Objective f(type = minimize);
f = completiontime; // 完了時刻最小化を示す

　最後に，終了条件を指定します．今回は終了条件として，計算時間2秒を設定します．

options.maxtim = 2;

　以上をまとめると，本例題の定式化が完了します．

　C++SIMPLEモデルを実行させると，次のような実行結果が得られます．

job = 1 "A_does"  6 12  6
job = 2 "B_does"  8 16  8
job = 3 "A_does" 12 18  6
job = 4 "C_does"  0 11 11
job = 5 "A_does"  0  6  6
job = 6 "B_does"  0  8  8

　この出力は，最適化の実行（直前のsolve ()呼び出し）が終わった後の

// 解の表示
simple_printf("job = %d %s %2d %2d %2d\n", j, act[j], act[j].startTime, act[j].endTime,
  act[j].processTime[j]);

に対応するもので，rcpspが求めた各仕事についてのモード，作業開始時刻，終了時刻，作業所要時間が表示されています．この表示から，例えば仕事1はAに実施させ（A_doesというモードを適用），作業開始は6日目，終了は12日目で，作業所要時間は6という解となっていることがわかります．細かな点ですが，仕事1の場合，作業開始は6日目のスタートで，作業終了は12日目が始まる直前（すなわち11日目一杯まで）と解釈してください．このように解釈すると，作業所要時間は作業終了時刻から作業開始時刻を引いたものになります．

　

　次に，納期遅れ最小化問題を考えます．実際のプロジェクトスケジューリングにおいては，「各仕事に納期が設定されており，納期遅れを最小化したい」という問題も多く存在します．

　これはActivityの定義に納期情報を設定し，目的関数に納期遅れ最小化を定義することによって可能です．

Set J = "1 .. 6";
Element j(set = J);
Parameter due(index = j);
Activity act(index = j, mode = M, duedate = due[j]); 

　目的関数には次のようにして納期遅れを設定します．

// 納期遅れ最小化
Objective f(type = minimize);
f = tardiness;

　これらを反映した例題2のC++SIMPLEモデルは次のようになります．

//
//  例題 2 (納期遅れ最小化)
//
Set M = "A_does B_does C_does"; // モード
Element m(set = M);
Set R = "A B C";   // 資源
Element r(set = R);
Set D = "1 .. 11"; // 各モードの作業時間の最大
Element d(set = D);
ResourceRequire  req(mode = M, resource = R, duration = D);
req["A_does, A", d] = 1, 1 <= d <= 6;
req["B_does, B", d] = 1, 1 <= d <= 8;
req["C_does, C", d] = 1, 1 <= d <= 11;
Set J = "1 .. 6";
Element j(set = J);
Parameter due(index = j);
due[j] = 10, 1 <= j <= 3;
due[j] = 17, 4 <= j <= 5;
due[j] = 6, j == 6;
Activity act(name = "act", index = j, mode = M, duedate = due[j]);
Set T = "0 .. 40"; // スケジューリング全体の時間(日単位)
Element t(set = T);
ResourceCapacity cap(resource = R, timeStep = T);
cap[r, t] = 1;
Objective f(type = minimize);
f = tardiness; // 納期遅れ最小化
options.maxtim = 2;
solve();
// 解の表示
simple_printf("job = %d %s %2d %2d %2d\n", j, act[j], act[j].startTime, act[j].endTime,
  act[j].processTime);

　実行結果は，以下のようになります．

job = 1 "A_does"  6 12  6
job = 2 "C_does"  0 11 11
job = 3 "B_does"  0  8  8
job = 4 "B_does"  8 16  8
job = 5 "A_does" 12 18  6
job = 6 "A_does"  0  6  6

---

 

 

上に戻る