数理最適化セミナーのご案内

7.1 rcpspの構成要素

 資源制約付きスケジューリング問題ソルバrcpspを利用する際には,必ず次の3つの構成要素Activity, ResourceRequire, ResourceCapacityを定義しなければなりません.この3つの構成要素の関係を表すと,以下のような図になります.

 作業集合は,「必ず実施しなければならない作業」から構成される集合です.作業集合の要素には,実施する必要の無い作業が含まれてはいけません.モード集合は,「作業に対する対処方法」から構成される集合です.「作業に対する対処方法」の事を,rcpspではモードと呼びます.資源集合は,「モードの利用に必要な資源」から構成される集合です.rcpspを利用する際には,まずこの3種類の集合を定義する必要があります.

 次に,「どの作業をどのモードで処理するか」に相当する変数Activityを定義します.rcpspが決定するのは,このActivityの値です.さらに,「各モードはどの資源をどの程度必要とするか」に相当する定数ResourceRequireを定めます.最後に,「資源はどれだけ利用できるか」に相当する定数ResourceCapacityを定めます.

 

 なお,rcpspでは完了時刻最小化問題と,納期遅れ最小化問題を扱うことができます.どちらを扱うかは,目的関数で指定します.

 rcpspで利用することのできる構成要素は以下の通りです.

構成要素名 C++SIMPLE内の名称 機能
目的関数 Objective 目的関数を表す
制約式 Constraint 制約式を表す
定数 Parameter 定数を表す
範囲演算関数 sum $\displaystyle\sum$に相当する
Expression 頻出する数式に対して,簡単な別の表現を与える
添字 Element 添字を表す
集合 Set 添字の動く範囲を表す
順序集合 OrderedSet 要素間に順序を持つ集合を表す
数列集合 Sequence 等差数列からなる集合を表す
条件式   制約式や代入文を制限する
ソフト制約関数 softConstraint ソフト制約を表す
アクティビティ Activity 必要な作業がどのモードを用いるかという変数
必要資源 ResourceRequire モードの利用に必要な資源を表す
資源供給量 ResourceCapacity 利用可能な資源の限界値を表す
モード順序関数 modeOrder モード順序を同一に設定する
アクティビティ固定関数 fixActivity アクティビティを固定する
アクティビティ固定解除関数 unfixActivity アクティビティの固定を解除する

 

 以降,rcpspでのみ利用可能な構成要素,あるいはrcpspで用いる場合に注意を要する構成要素に関してのみ説明します.


 

 

上に戻る