2.25.1 オープンショップ問題
例題 オープンショップ問題
3つの作業から構成される，3つの仕事があるとします．各作業を処理する機械と処理時間は以下のように与えられています．
| 作業1（機械1） | 作業2（機械2） | 作業3（機械3） | |
|---|---|---|---|
| 仕事a | 5時間 | 8時間 | 4時間 |
| 仕事b | 5時間 | 4時間 | 6時間 |
| 仕事c | 6時間 | 5時間 | 5時間 |
各機械が作業を処理している間は，他の作業を処理する事は出来ません．また，各作業を処理する順番に制限はありません．この場合の最後の作業の完了時刻が最小となるようにするには，各仕事をどのように機械に割り振ればいいでしょうか．なお，すべての仕事を終えるまでの所要時間は最大で30時間までとします．
この問題を資源制約付きスケジューリング問題で定式化すると，例えば以下の様になります．
各仕事の各作業は同時には2つ以上処理出来ない事を，ダミー資源を用いて表現している事に注意してください．
| 資源 | |
| machine1 | 機械1，供給量:常に1 |
| machine2 | 機械2，供給量:常に1 |
| machine3 | 機械3，供給量:常に1 |
| d1 | ダミー資源1，供給量:常に1 |
| d2 | ダミー資源2，供給量:常に1 |
| d3 | ダミー資源3，供給量:常に1 |
| モード | |
| mode_a_1 | 処理時間:5 必要量：machine1, d1を処理時間中常に1 |
| mode_a_2 | 処理時間:8 必要量：machine2, d1を処理時間中常に1 |
| mode_a_3 | 処理時間:4 必要量：machine3, d1を処理時間中常に1 |
| mode_b_1 | 処理時間:5 必要量：machine1, d2を処理時間中常に1 |
| mode_b_2 | 処理時間:4 必要量：machine2, d2を処理時間中常に1 |
| mode_b_3 | 処理時間:6 必要量：machine3, d2を処理時間中常に1 |
| mode_c_1 | 処理時間:6 必要量：machine1, d3を処理時間中常に1 |
| mode_c_2 | 処理時間:5 必要量：machine2, d3を処理時間中常に1 |
| mode_c_3 | 処理時間:5 必要量：machine3, d3を処理時間中常に1 |
| アクティビティ | |
 |
仕事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 |
| 目的関数（最小化） | |
| completionTime | 最後の作業の完了時刻 |
| スケジュール期間 | |
| T | 最大で30時間とする |
これをC++SIMPLEで記述すると次のようになります．
なお，アクティビティの引数に渡すモード集合ですが，仕事・作業の各組み合わせに対してどのモードが対応するかという集合AvailModeを用意し，それを引数として渡します．
// 作業集合
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;
// 目的関数
Objective f(type = minimize);
f = completionTime; // 最後の作業の完了時刻最小化
// 求解最大時間の設定
options.maxtim = 15;
// 求解
solve();
// 結果の標準出力
simple_printf("act[%s, %d] = %d\n", j, s, act[j, s].startTime);データファイルは次のようになります．
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 ;
req =
[mode_a_1, machine1, 1] 1 [mode_a_2, machine2, 1] 1 [mode_a_3, machine3, 1] 1
[mode_a_1, machine1, 2] 1 [mode_a_2, machine2, 2] 1 [mode_a_3, machine3, 2] 1
[mode_a_1, machine1, 3] 1 [mode_a_2, machine2, 3] 1 [mode_a_3, machine3, 3] 1
[mode_a_1, machine1, 4] 1 [mode_a_2, machine2, 4] 1 [mode_a_3, machine3, 4] 1
[mode_a_1, machine1, 5] 1 [mode_a_2, machine2, 5] 1
[mode_a_2, machine2, 6] 1
[mode_a_2, machine2, 7] 1
[mode_a_2, machine2, 8] 1
[mode_b_1, machine1, 1] 1 [mode_b_2, machine2, 1] 1 [mode_b_3, machine3, 1] 1
[mode_b_1, machine1, 2] 1 [mode_b_2, machine2, 2] 1 [mode_b_3, machine3, 2] 1
[mode_b_1, machine1, 3] 1 [mode_b_2, machine2, 3] 1 [mode_b_3, machine3, 3] 1
[mode_b_1, machine1, 4] 1 [mode_b_2, machine2, 4] 1 [mode_b_3, machine3, 4] 1
[mode_b_1, machine1, 5] 1 [mode_b_3, machine3, 5] 1
[mode_b_3, machine3, 6] 1
[mode_c_1, machine1, 1] 1 [mode_c_2, machine2, 1] 1 [mode_c_3, machine3, 1] 1
[mode_c_1, machine1, 2] 1 [mode_c_2, machine2, 2] 1 [mode_c_3, machine3, 2] 1
[mode_c_1, machine1, 3] 1 [mode_c_2, machine2, 3] 1 [mode_c_3, machine3, 3] 1
[mode_c_1, machine1, 4] 1 [mode_c_2, machine2, 4] 1 [mode_c_3, machine3, 4] 1
[mode_c_1, machine1, 5] 1 [mode_c_2, machine2, 5] 1 [mode_c_3, machine3, 5] 1
[mode_c_1, machine1, 6] 1
[mode_a_1, d1, 1] 1 [mode_a_2, d1, 1] 1 [mode_a_3, d1, 1] 1
[mode_a_1, d1, 2] 1 [mode_a_2, d1, 2] 1 [mode_a_3, d1, 2] 1
[mode_a_1, d1, 3] 1 [mode_a_2, d1, 3] 1 [mode_a_3, d1, 3] 1
[mode_a_1, d1, 4] 1 [mode_a_2, d1, 4] 1 [mode_a_3, d1, 4] 1
[mode_a_1, d1, 5] 1 [mode_a_2, d1, 5] 1
[mode_a_2, d1, 6] 1
[mode_a_2, d1, 7] 1
[mode_a_2, d1, 8] 1
[mode_b_1, d2, 1] 1 [mode_b_2, d2, 1] 1 [mode_b_3, d2, 1] 1
[mode_b_1, d2, 2] 1 [mode_b_2, d2, 2] 1 [mode_b_3, d2, 2] 1
[mode_b_1, d2, 3] 1 [mode_b_2, d2, 3] 1 [mode_b_3, d2, 3] 1
[mode_b_1, d2, 4] 1 [mode_b_2, d2, 4] 1 [mode_b_3, d2, 4] 1
[mode_b_1, d2, 5] 1 [mode_b_3, d2, 5] 1
[mode_b_3, d2, 6] 1
[mode_c_1, d3, 1] 1 [mode_c_2, d3, 1] 1 [mode_c_3, d3, 1] 1
[mode_c_1, d3, 2] 1 [mode_c_2, d3, 2] 1 [mode_c_3, d3, 2] 1
[mode_c_1, d3, 3] 1 [mode_c_2, d3, 3] 1 [mode_c_3, d3, 3] 1
[mode_c_1, d3, 4] 1 [mode_c_2, d3, 4] 1 [mode_c_3, d3, 4] 1
[mode_c_1, d3, 5] 1 [mode_c_2, d3, 5] 1 [mode_c_3, d3, 5] 1
[mode_c_1, d3, 6] 1
;実行すると，各作業の開始時刻
act[a, 1] = 0 act[a, 2] = 5 act[a, 3] = 13 act[b, 1] = 6 act[b, 2] = 13 act[b, 3] = 0 act[c, 1] = 11 act[c, 2] = 0 act[c, 3] = 6
が出力されます．
上に戻る