最適化セミナーのご案内

2.25.2 フローショップ問題

例題 フローショップ問題

 前節のオープンショップ問題の条件の下,各仕事は,作業1, 作業2, 作業3 の順で処理されなければならないとします.この場合の最後の作業の完了時刻が最小となるようにするには,どのように機械を割り振ればよいでしょうか.

 この問題を記述するには,各作業の処理順序を制約する以下の先行制約を加える必要があります.なお,以下で用いている$\prec$は先行関係を表す記号とします.

先行制約
$act_{a,1} \prec act_{a,2}$ 仕事aの作業1は,仕事aの作業2に先行する
$act_{a,2} \prec act_{a,3}$ 仕事aの作業2は,仕事aの作業3に先行する
$act_{b,1} \prec act_{b,2}$ 仕事bの作業1は,仕事bの作業2に先行する
$act_{b,2} \prec act_{b,3}$ 仕事bの作業2は,仕事bの作業3に先行する
$act_{c,1} \prec act_{c,2}$ 仕事cの作業1は,仕事cの作業2に先行する
$act_{c,2} \prec act_{c,3}$ 仕事cの作業2は,仕事cの作業3に先行する

 上記の先行制約を加えたSIMPLEのモデルは以下の様になります.尚,各仕事の各作業を同時に2つ以上処理出来ない事は,先行制約で表現されている事に注意してください.

// 作業集合
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;

// 先行制約
act[j,s-1] < act[j,s], 1 < s;

// 求解最大時間の設定
options.maxtim = 15;

// 求解
solve();

// 結果の標準出力
simple_printf("act[%s,%d] = %d\n", j, s, act[j,s].startTime);

 先行制約を設けた事により,ダミー資源を用いる必要が無くなった為,データファイルの1つが以下の様に修正されます.

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
; 

 実行すると,各作業の開始時刻が以下のように出力されます.

act[a,1] = 11
act[a,2] = 16
act[a,3] = 24
act[b,1] = 6
act[b,2] = 11
act[b,3] = 16
act[c,1] = 0
act[c,2] = 6
act[c,3] = 11

 


 

 

上に戻る