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

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日目一杯まで）と解釈してください．このように解釈すると，作業所要時間は作業終了時刻から作業開始時刻を引いたものになります．

　

　なお，この例題は作業完了時刻最小化問題ですので，制約に重みを設定することが可能です．いま，各モードで仕事を行った際にコストが発生するとします．そのもとで，コストが0を超過した分に制約の重みをかけたペナルティと完了時刻の値を足した全体を最小化することを考えます．

　

　先程のモデルのsolve()以前に，

Parameter cost(index = m);
cost["A_does"] =  5; cost["B_does"] =  2; cost["C_does"] =  1;
Expression costTotal;
costTotal = sum(Boolean(act[j] == m) * cost[m], (j, m)); // 全コスト
softConstraint(1); // 制約式の重み
costTotal <= 0; // コストの最小化に対応する制約式

を追加します．A_does，B_does，C_does各々のモードを選択したときにコストは各々5，2，1かかるものとし，コスト全体をcostTotalで表現しています．

　この実行結果は次のようになります．

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

　先程の問題は作業完了時刻が18であったのに対し，今回の問題の完了時刻は24となり，完了するまでに時間を要するようになりました．その分，コストの小さいモードC_doesで行う仕事が増加し，コストの大きいモードA_doesで行う仕事が減少しております．

　

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

　これは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

---

 

 

上に戻る