2.25.3 ジョブショップ問題
例題 ジョブショップ問題
前節のオープンショップ問題の条件の下，各仕事は以下の順に処理されなければならないものとします．
| 作業1（機械1） | 作業2（機械2） | 作業3（機械3） | |
|---|---|---|---|
| 仕事a | 1 | 3 | 2 |
| 仕事b | 1 | 2 | 3 |
| 仕事c | 2 | 1 | 3 |
この場合の最後の作業の完了時刻が最小となるようにするには，どのように機械を割り振ればよいでしょうか．
この問題は，先行制約が以下の様に変更されます．
| 先行制約 | |
 |
仕事aの作業1は，仕事aの作業3に先行する |
 |
仕事aの作業3は，仕事aの作業2に先行する |
 |
仕事bの作業1は，仕事bの作業2に先行する |
 |
仕事bの作業2は，仕事bの作業3に先行する |
 |
仕事cの作業2は，仕事cの作業1に先行する |
 |
仕事cの作業1は，仕事cの作業3に先行する |
上記の先行制約をデータから与えられるように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;
// 目的関数(最後の作業の完了時刻の最小化)
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;
// 求解最大時間の設定
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 ;
実行すると，各作業の開始時刻が以下のように出力されます．
act[a, 1] = 0 act[a, 2] = 14 act[a, 3] = 5 act[b, 1] = 5 act[b, 2] = 10 act[b, 3] = 14 act[c, 1] = 10 act[c, 2] = 0 act[c, 3] = 20
上に戻る