最適化セミナーのご案内

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

 

 

上に戻る