最適化セミナーのご案内

2.25.3 ジョブショップ問題

例題 ジョブショップ問題

 前節のオープンショップ問題の条件の下,各仕事は以下の順に処理されなければならないものとします.

  作業1(機械1) 作業2(機械2) 作業3(機械3)
仕事a 1 3 2
仕事b 1 2 3
仕事c 2 1 3

 

 この場合の最後の作業の完了時刻が最小となるようにするには,どのように機械を割り振ればよいでしょうか.

 この問題は,先行制約が以下の様に変更されます.

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

 上記の先行制約をデータから与えられるように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);

 データファイルの1つが以下の様に修正されます.

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

 


 

 

上に戻る