最適化セミナーのご案内

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
 
アクティビティ
$act_{a,1}$ 仕事aの作業1
処理モード:mode_a_1
$act_{a,2}$ 仕事aの作業2
処理モード:mode_a_2
$act_{a,3}$ 仕事aの作業3
処理モード:mode_a_3
$act_{b,1}$ 仕事bの作業1
処理モード:mode_b_1
$act_{b,2}$ 仕事bの作業2
処理モード:mode_b_2
$act_{b,3}$ 仕事bの作業3
処理モード:mode_b_3
$act_{c,1}$ 仕事cの作業1
処理モード:mode_c_1
$act_{c,2}$ 仕事cの作業2
処理モード:mode_c_2
$act_{c,3}$ 仕事cの作業3
処理モード:mode_c_3
 
目的関数(最小化)
completionTime 最後の作業の完了時刻
 
スケジュール期間
T 最大で30時間とする

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

が出力されます.


 

 

上に戻る