2.24 セミナー割当問題

C++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日とする

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

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

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

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

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

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

// 各モード中の最大開催期間までの期間集合
Set TT(name = "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] 2 [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$ において，メイン会場でのセミナーを終えた後にメイン以外の会場でのセミナーに移行する

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

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

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

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

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

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

// 各モード中の最大開催期間までの期間集合
Set TT(name = "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 ジョブショップスケジューリング問題

上に戻る

Nuorium Optimizer C++SIMPLE例題集 V27

2.24 セミナー割当問題

Nuorium Optimizer SITE MAP