2.24 セミナー割当問題

SIMPLE例題集
2. 例題の紹介
2.24 セミナー割当問題

2.24 セミナー割当問題

　資源制約付きスケジューリング問題の例として，本節ではセミナー会場提供会社におけるスケジュール計画を以下で考えていきます．

例題1

　あるセミナー会場提供会社は，以下の1～6までのセミナーに対し，会場を提供するものとします．

セミナー名	各セミナーのコマ数
1	4
2	6
3	5
4	3
5	10
6	7

　例題1では，各セミナーにおいて1日あたりに消化できるコマ数は1つとします．別のセミナーを同一の会場で行うことはできないものとし，1日あたりの会場使用数の最大を4とするとき，これらすべてのセミナーが完了する時刻が最小となるようなスケジュールを求めてください．

　なお，すべてのセミナーが終了するまでの日数は最大でも20日までとします．

　この問題を定式化すると，以下のようになります．なお，セミナー会場に関しては区別がないので，一つの資源とみなすことに注意してください．

セミナー集合
$Se$	セミナー名1～6

資源
1	セミナー会場，供給量:常に4

モード
$A_1$	セミナー1のコマ数消化方法処理時間:4 必要量：資源1を処理時間中常に1
$A_2$	セミナー2のコマ数消化方法処理時間:6 必要量：資源1を処理時間中常に1
$A_3$	セミナー3のコマ数消化方法処理時間:5 必要量：資源1を処理時間中常に1
$A_4$	セミナー4のコマ数消化方法処理時間:3 必要量：資源1を処理時間中常に1
$A_5$	セミナー5のコマ数消化方法処理時間:10 必要量：資源1を処理時間中常に1
$A_6$	セミナー6のコマ数消化方法処理時間:7 必要量：資源1を処理時間中常に1

モード集合族
$MM_{i}, i \in Se$	セミナーiがとりうるモード集合

アクティビティ
$act_{i}, i \in Se$	セミナーiをこなす作業処理モード： $A_i$

目的関数（最小化）
completionTime	最後の作業の完了時刻

スケジュール期間
T	最大で20日とする

　定式化した結果をSIMPLEで記述すると以下のようになります．

// 全体のスケジューリング期間
Set T(name="T");
Element t(set=T);

// 作業(セミナー)集合
Set Se(name="Se");
Element se(set=Se);

// モード集合
Set M(name="M");
Element m(set=M);
// 各セミナーがとりうるモード
Set MM(name="MM", index=se);

// 資源(部屋)集合
Set Ro(name="Ro");
Element ro(set=Ro);

// 各モード中の最大開催期間までの期間集合
Set TT(name="TT");
Element tt(set=TT);

// 必要資源
ResourceRequire req(name="req", mode=M, resource=Ro, duration=TT);

// 資源供給量
ResourceCapacity cap(name="cap", resource=Ro, timeStep=T);

// アクティビティ
Activity act(name="セミナー", index=se, mode=MM[se]);

// 目的関数（すべてのセミナーの完了時刻の最小化）
Objective f(name="最小完了日数", type=minimize);
f = completionTime;

// 求解最大時間
options.maxtim = 5;

// 求解
solve();

// 結果の出力
f.val.print();
simple_printf("セミナー[%s] = %d\n", se, act[se].startTime);

　入力データ（dat形式）は，以下のようになります．

cap = [1,0] 4 [1,1] 4 [1,2] 4 [1,3] 4 [1,4] 4 [1,5] 4 [1,6] 4 
      [1,7] 4 [1,8] 4 [1,9] 4 [1,10] 4 [1,11] 4 [1,12] 4 
      [1,13] 4 [1,14] 4 [1,15] 4 [1,16] 4 [1,17] 4 [1,18] 4 
      [1,19] 4 [1,20] 4;
MM  = [1] A1 [2] A2 [3] A3 [4] A4 [5] A5 [6] A6;
req = [A1,1,1] 1 [A1,1,2] 1 [A1,1,3] 1 [A1,1,4] 1 
      [A2,1,1] 1 [A2,1,2] 1 [A2,1,3] 1 [A2,1,4] 1 [A2,1,5] 1 
      [A2,1,6] 1 
      [A3,1,1] 1 [A3,1,2] 1 [A3,1,3] 1 [A3,1,4] 1 [A3,1,5] 1 
      [A4,1,1] 1 [A4,1,2] 1 [A4,1,3] 1 
      [A5,1,1] 1 [A5,1,2] 1 [A5,1,3] 1 [A5,1,4] 1 [A5,1,5] 1 
      [A5,1,6] 1 [A5,1,7] 1 [A5,1,8] 1 [A5,1,9] 1 [A5,1,10] 1 
      [A6,1,1] 1 [A6,1,2] 1 [A6,1,3] 1 [A6,1,4] 1 [A6,1,5] 1 
      [A6,1,6] 1 [A6,1,7] 1;

　結果は，以下のようになります．

最小完了日数=10
セミナー[1] = 0
セミナー[2] = 4
セミナー[3] = 0
セミナー[4] = 5
セミナー[5] = 0
セミナー[6] = 0

　上記結果のセミナーの値は，各セミナーの開始日時を表しています．

　例題1では，各セミナーにおけるモードは1種類（一日一コマずつ消化していく）のみでしたが，続く例題2では，各セミナーに対していくつかのモードを用意し，例題1からの結果の推移を検証します．

例題2

　例題1の条件のもと，各セミナーにおいて，コマ数の消化方法の選択肢をいくつか与えるものとします．具体的には，以下の表の通りです．

セミナー名	モード	セミナーコマ数の消化方法
1	A1_1	1-1-1-1
2	A2_1	1-1-1-1-1-1
	A2_2	2-2-2
	A2_3	1-1-2-2
3	A3_1	1-1-1-1-1
	A3_2	2-2-1
4	A4_1	1-1-1
5	A5_1	1-1-1-1-1-1-1-1-1-1
	A5_2	1-2-2-2-2-1
	A5_3	2-2-2-2-2
6	A6_1	1-1-1-1-1-1-1
	A6_2	1-2-2-2
	A6_3	2-2-2-1

　表の見方ですが，例えばA2_2でしたら，セミナー2が全コマ数6を3日に渡って各々2ずつ消化する，ということになります．各セミナーは，そのセミナー特有に用意されたモードのうちどれか一つを選択しなければなりません．例えばセミナー3に対するモードはA3_1，A3_2の2つがあるので，それらのうちのどちらかを選択してセミナーのコマ数を消化するということになります．

　すべてのセミナーが完了する時刻が最小となるように，適切なモードを選択してスケジュールを求めてください．

　定式化に関しましては，例題1と同様です．ですので，モデルファイルの記述も例題1と同一になります．

　入力データ（dat形式）は，以下のようになります．

cap = [1,0] 4 [1,1] 4 [1,2] 4 [1,3] 4 [1,4] 4 [1,5] 4 [1,6] 4
      [1,7] 4 [1,8] 4 [1,9] 4 [1,10] 4 [1,11] 4 [1,12] 4
      [1,13] 4 [1,14] 4 [1,15] 4 [1,16] 4 [1,17] 4 [1,18] 4 
      [1,19] 4 [1,20] 4
;
MM  = [1] A1_1 [2] A2_1 A2_2 A2_3 [3] A3_1 A3_2 [4] A4_1 
      [5] A5_1 A5_2 A5_3 [6] A6_1 A6_2 A6_3 
;
req = [A1_1,1,1] 1 [A1_1,1,2] 1 [A1_1,1,3] 1 [A1_1,1,4] 1
      [A2_1,1,1] 1 [A2_1,1,2] 1 [A2_1,1,3] 1 [A2_1,1,4] 1 [A2_1,1,5] 1 
      [A2_1,1,6] 1
      [A2_2,1,1] 2 [A2_2,1,2] 2 [A2_2,1,3] 2
      [A2_3,1,1] 1 [A2_3,1,2] 1 [A2_3,1,3] 2 [A2_3,1,4] 2
      [A3_1,1,1] 1 [A3_1,1,2] 1 [A3_1,1,3] 1 [A3_1,1,4] 1 [A3_1,1,5] 1
      [A3_2,1,1] 2 [A3_2,1,2] 2 [A3_2,1,3] 1
      [A4_1,1,1] 1 [A4_1,1,2] 1 [A4_1,1,3] 1 
      [A5_1,1,1] 1 [A5_1,1,2] 1 [A5_1,1,3] 1 [A5_1,1,4] 1 [A5_1,1,5] 1 
      [A5_1,1,6] 1 [A5_1,1,7] 1 [A5_1,1,8] 1 [A5_1,1,9] 1 [A5_1,1,10] 1
      [A5_2,1,1] 1 [A5_2,1,2] 2 [A5_2,1,3] 2 [A5_2,1,4] 2 [A5_2,1,5] 2 
      [A5_2,1,6] 1
      [A5_3,1,1] 2 [A5_3,1,2] 2 [A5_3,1,3] 2 [A5_3,1,4] 2 [A5_3,1,5] 2
      [A6_1,1,1] 1 [A6_1,1,2] 1 [A6_1,1,3] 1 [A6_1,1,4] 1 [A6_1,1,5] 1 
      [A6_1,1,6] 1 [A6_1,1,7] 1 
      [A6_2,1,1] 1 [A6_2,1,2] 2 [A6_2,1,3] 2 [A6_2,1,4] 2 
      [A6_3,1,1] 1 [A6_3,1,2] 2 [A6_3,1,3] 2 [A6_3,1,4] 1;

　例題1と比較すると，各セミナーにおいてとりうるモードの数が増えたことがおわかりになると思います．

　結果は，以下のようになります．

最小完了日数=9
セミナー[1] = 0
セミナー[2] = 5
セミナー[3] = 0
セミナー[4] = 4
セミナー[5] = 0
セミナー[6] = 5

　結果から明らかなように，例題1に比べて，例題2ではセミナー完了時刻を短縮できるようなスケジュール計画を立てることができました．これは，各セミナーがとりうるモードの数が例題1と比較して増えたことによるためです．

　この節の最後に，今までは資源となる会場は一つのみでしたが，もう一つ資源となる会場を追加してみましょう．セミナーを実施するメイン会場（大部屋）とサブ会場（小部屋）のようなものを想定していただければ，おわかりになるかと思います．

例題3

　例題2の条件のもと，さらにメイン会場を用意します．

　各セミナーともにメイン会場で1日セミナーを行った後，その他の会場（以下では，サブ会場と呼ぶことにします）において各個別のセミナーを行うものとします．サブ会場でのセミナー実施方法は，例題2と同一とします．1日あたりのサブ会場使用数の最大に関しましても，例題1・例題2同様，4とします．

　メイン会場では1日1種類のセミナーしか行うことができず，しかもメイン会場は各セミナーのはじめの1コマのみしか利用することができないものとするとき，すべてのセミナーが完了する時刻が最小となるようなスケジュールを求めてください．

　定式化としては以下のように，各セミナーともに，メイン会場でセミナーを行った後にサブ会場で行うという先行制約が加わります．なお先行関係は $\prec$ により表すものとします．

資源
0	メイン会場，供給量:常に1
1	サブ会場，供給量:常に4

先行制約
$act_{i,0} \prec act_{i,1}, \forall i\in Se$	任意のセミナー $i$ において，メイン会場でのセミナーを終えた後にメイン以外の会場でのセミナーに移行する

　上記定式化の追加を反映したSIMPLEでのモデル記述は，以下のようになります．

// 全体のスケジューリング期間
Set T(name="T");
Element t(set=T);

// 作業(セミナー)集合
Set Se(name="Se");
Element se(set=Se);

// モード集合
Set M(name="M");
Element m(set=M);

// 資源(部屋)集合
Set Ro(name="Ro");
Element ro(set=Ro);

// 各セミナーがとりうるモード
Set MM(name="MM", index=(se,ro));

// 各モード中の最大開催期間までの期間集合
Set TT(name="TT");
Element tt(set=TT);

// 資源供給量
ResourceCapacity cap(name="cap", resource=Ro, timeStep=T);

// 必要資源
ResourceRequire req(name="req", mode=M, resource=Ro, duration=TT);

// アクティビティ
Activity act(name="セミナー", index=(se,ro), mode=MM[se,ro]);
// 先行制約
act[se,ro-1] < act[se,ro], ro > 0;

// 目的関数（すべてのセミナーの完了時刻の最小化）
Objective f(name="最小完了日数", type=minimize);
f = completionTime;

// 求解最大時間
options.maxtim = 5;

// 求解
solve();

// 結果の出力
f.val.print();
simple_printf("セミナー[%s,%s] = %d\n", se, ro, act[se,ro].startTime);

　入力データ（dat形式）は，以下のようになります．

cap = [0,0] 1 [0,1] 1 [0,2] 1 [0,3] 1 [0,4] 1 [0,5] 1 [0,6] 1 
      [0,7] 1 [0,8] 1 [0,9] 1 [0,10] 1 [0,11] 1 [0,12] 1 
      [0,13] 1 [0,14] 1 [0,15] 1 [0,16] 1 [0,17] 1 [0,18] 1 
      [0,19] 1 [0,20] 1
      [1,0] 4 [1,1] 4 [1,2] 4 [1,3] 4 [1,4] 4 [1,5] 4 [1,6] 4 
      [1,7] 4 [1,8] 4 [1,9] 4 [1,10] 4 [1,11] 4 [1,12] 4 
      [1,13] 4 [1,14] 4 [1,15] 4 [1,16] 4 [1,17] 4 [1,18] 4 
      [1,19] 4 [1,20] 4
;
MM  =
[1,0] large_room [1,1] A1_1 
[2,0] large_room [2,1] A2_1 A2_2 A2_3
[3,0] large_room [3,1] A3_1 A3_2 
[4,0] large_room [4,1] A4_1 
[5,0] large_room [5,1] A5_1 A5_2 A5_3 
[6,0] large_room [6,1] A6_1 A6_2 A6_3 
;
req = [large_room,0,1] 1
      [A1_1,1,1] 1 [A1_1,1,2] 1 [A1_1,1,3] 1 [A1_1,1,4] 1
      [A2_1,1,1] 1 [A2_1,1,2] 1 [A2_1,1,3] 1 [A2_1,1,4] 1 [A2_1,1,5] 1 
      [A2_1,1,6] 1
      [A2_2,1,1] 2 [A2_2,1,2] 2 [A2_2,1,3] 2
      [A2_3,1,1] 1 [A2_3,1,2] 1 [A2_3,1,3] 2 [A2_3,1,4] 2
      [A3_1,1,1] 1 [A3_1,1,2] 1 [A3_1,1,3] 1 [A3_1,1,4] 1 [A3_1,1,5] 1
      [A3_2,1,1] 2 [A3_2,1,2] 2 [A3_2,1,3] 1
      [A4_1,1,1] 1 [A4_1,1,2] 1 [A4_1,1,3] 1 
      [A5_1,1,1] 1 [A5_1,1,2] 1 [A5_1,1,3] 1 [A5_1,1,4] 1 [A5_1,1,5] 1 
      [A5_1,1,6] 1 [A5_1,1,7] 1 [A5_1,1,8] 1 [A5_1,1,9] 1 [A5_1,1,10] 1
      [A5_2,1,1] 1 [A5_2,1,2] 2 [A5_2,1,3] 2 [A5_2,1,4] 2 [A5_2,1,5] 2 
      [A5_2,1,6] 1
      [A5_3,1,1] 2 [A5_3,1,2] 2 [A5_3,1,3] 2 [A5_3,1,4] 2 [A5_3,1,5] 2
      [A6_1,1,1] 1 [A6_1,1,2] 1 [A6_1,1,3] 1 [A6_1,1,4] 1 [A6_1,1,5] 1 
      [A6_1,1,6] 1 [A6_1,1,7] 1 
      [A6_2,1,1] 1 [A6_2,1,2] 2 [A6_2,1,3] 2 [A6_2,1,4] 2 
      [A6_3,1,1] 2 [A6_3,1,2] 2 [A6_3,1,3] 2 [A6_3,1,4] 1;

　結果は，以下のようになります．

最小完了日数=11
セミナー[1,0] = 2
セミナー[1,1] = 3
セミナー[2,0] = 4
セミナー[2,1] = 5
セミナー[3,0] = 1
セミナー[3,1] = 2
セミナー[4,0] = 5
セミナー[4,1] = 7
セミナー[5,0] = 0
セミナー[5,1] = 1
セミナー[6,0] = 3
セミナー[6,1] = 4

2.23 隣接行列（最大カット問題）

2.25 ジョブショップスケジューリング問題

上に戻る

Numerical Optimizer SIMPLE例題集 V19

2.24 セミナー割当問題

Numerical Optimizer SITE MAP