2.24 セミナー割当問題
資源制約付きスケジューリング問題の例として,本節ではセミナー会場提供会社におけるスケジュール計画を以下で考えていきます.
例題1
あるセミナー会場提供会社は,以下の1~6までのセミナーに対し,会場を提供するものとします.
セミナー名 | 各セミナーのコマ数 |
---|---|
1 | 4 |
2 | 6 |
3 | 5 |
4 | 3 |
5 | 10 |
6 | 7 |
例題1では,各セミナーにおいて1日あたりに消化できるコマ数は1つとします.別のセミナーを同一の会場で行うことはできないものとし,1日あたりの会場使用数の最大を4とするとき,これらすべてのセミナーが完了する時刻が最小となるようなスケジュールを求めてください.
なお,すべてのセミナーが終了するまでの日数は最大でも20日までとします.
この問題を定式化すると,以下のようになります.なお,セミナー会場に関しては区別がないので,一つの資源とみなすことに注意してください.
セミナー集合 | |
セミナー名1~6 | |
資源 | |
1 | セミナー会場,供給量:常に4 |
モード | |
セミナー1のコマ数消化方法 処理時間:4 必要量:資源1を処理時間中常に1 |
|
セミナー2のコマ数消化方法 処理時間:6 必要量:資源1を処理時間中常に1 |
|
セミナー3のコマ数消化方法 処理時間:5 必要量:資源1を処理時間中常に1 |
|
セミナー4のコマ数消化方法 処理時間:3 必要量:資源1を処理時間中常に1 |
|
セミナー5のコマ数消化方法 処理時間:10 必要量:資源1を処理時間中常に1 |
|
セミナー6のコマ数消化方法 処理時間:7 必要量:資源1を処理時間中常に1 |
|
モード集合族 | |
セミナーiがとりうるモード集合 | |
アクティビティ | |
セミナー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コマのみしか利用することができないものとするとき,すべてのセミナーが完了する時刻が最小となるようなスケジュールを求めてください.
定式化としては以下のように,各セミナーともに,メイン会場でセミナーを行った後にサブ会場で行うという先行制約が加わります.なお先行関係はにより表すものとします.
資源 | |
0 | メイン会場,供給量:常に1 |
1 | サブ会場,供給量:常に4 |
先行制約 | |
任意のセミナー |
上記定式化の追加を反映した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
上に戻る