第3章 Red Hat Business Optimizer で提供される例

3.1. 例のダウンロードおよび実行
リンクのコピー

Red Hat Software Downloads の Web サイトから Red Hat Business Optimizer の例をダウンロードして、実行できます。

3.1.1. Red Hat Business Optimizer の例のダウンロード
リンクのコピー

Red Hat Decision Manager のアドオンパッケージの一部として例をダウンロードできます。

手順

Software Downloads ページから rhdm-7.1.0-add-ons.zip ファイルをダウンロードします。
ファイルを展開します。
rhdm-7.1-planner-engine.zip ファイルを展開先のディレクトリーに、展開します。

結果

展開した rhdm-7.1-planner-engine ディレクトリーの以下のサブディレクトリーに、サンプルのソースコードが含まれています。* examples/sources/src/main/java/org/optaplanner/examples * examples/sources/src/main/resources/org/optaplanner/examples * webexamples/sources/src/main/java/org/optaplanner/examples * webexamples/sources/src/main/resources/org/optaplanner/examples

「Business Optimizer サンプルの表」のサンプルの表では、各サンプルで使用するディレクトリーの名前を記載しています。

3.1.2. Business Optimizer サンプルの実行
リンクのコピー

Red Hat Business Optimizer には、さまざまなユースケースのデモとして多数のサンプルが含まれています。

前提条件/事前作業

例をダウンロードして展開しました。ダウンロードおよび展開の方法は、「Red Hat Business Optimizer の例のダウンロード」を参照してください。

手順

rhdm-7.1.0-planner-engine フォルダーで examples ディレクトリーを開き、適切なスクリプトを使用してサンプルを実行します。
Linux または Mac の場合:
```
$ cd examples
$ ./runExamples.sh
```
Windows の場合:
```
$ cd examples
$ runExamples.bat
```

GUI アプリケーションウィンドウからサンプルを選択して実行します。

注記

Red Hat Business Optimizer 自体は GUI に依存していません。サーバーまたはモバイル JVM 上でも、デスクトップとまったく同じように動作します。

3.1.3. IDE (IntelliJ、Eclipse、または Netbeans) での Red Hat Business Optimizer サンプルの実行
リンクのコピー

IntelliJ、Eclipse または Netbeans など統合開発環境 (IDE) を使用する場合には、お使いの開発環境にダウンロードした Red Hat Business Optimizer の例を実行できます。

前提条件/事前作業

例をダウンロードして展開しました。ダウンロードおよび展開の方法は、「Red Hat Business Optimizer の例のダウンロード」を参照してください。

手順

新規プロジェクトとして Red Hat Business Optimizer の例を開きます。
1. IntelliJ または Netbeans の場合は、新規プロジェクトとして examples/sources/pom.xml を開きます。Maven 統合の指示に従い、インストールを進めてください。この手順では、残りのステップは省略します。
2. Eclipse の場合は、examples/sources ディレクトリーで新規プロジェクトを開きます。
binaries ディレクトリーおよび examples/binaries ディレクトリーにあるすべての JAR を、クラスパスに追加します (examples/binaries/optaplanner-examples-*.jar ファイルを除く)。
Java のソースディレクトリー src/main/java と Java のリソースディレクトリー src/main/resources を追加します。
実行設定を作成します。
- メインクラス: org.optaplanner.examples.app.OptaPlannerExamplesApp
- VM パラメーター (オプション): -Xmx512M -server -Dorg.optaplanner.examples.dataDir=examples/sources/data
- 作業ディレクトリー: examples/sources
実行設定を実行します。

3.1.4. Web のサンプルの実行
リンクのコピー

GUI のサンプル以外に、Red Hat Decision Manager には、以下のような Red Hat Business Optimizer 用の一連の Web サンプルが含まれます。

配送経路: Leaflet または Google Maps の視覚化機能どちらかを使用して、さまざまな多数の顧客が必要とするアイテムをすべて回収する最短経路を計算します。
クラウドバランシング: 異なる使用およびコストのコンピューターにプロセスを割り当てます。

前提条件

Red Hat Decision Manager アドオンパッケージのから Red Hat Business Optimizer のサンプルをダウンロードして、展開しました。方法については、「Red Hat Business Optimizer の例のダウンロード」を参照してください。

Web のサンプルは、以下の API など、複数の JEE API を実行する必要があります。

Servlet
JAX-RS
CDI

これらの API は、Bussiness Optimizer 自体には必要ありません。

手順

JBoss EAP または WildFly などの JEE アプリケーションサーバーをダウンロードして、展開します。
展開した rhdm-7.1.0-planner-engine ディレクトリーで、webexamples/binaries サブディレクトリーを開き、JEE アプリケーションサーバーで optaplanner-webexamples-*.war ファイルを開きます。
スタンドアロンモードで JBoss EAP を使用する場合には、optaplanner-webexamples-*.war ファイルを JBOSS_home/standalone/deployments フォルダーに追加して実行可能です。
Web ブラウザーで http://localhost:8080/optaplanner-webexamples/ のアドレスを開きます。

3.2. Business Optimizer サンプルの表
リンクのコピー

Business Optimizer サンプルには、教育関連のコンテストで出題された問題を解決するものもあります。以下の表の Contest コラムでは、このようなコンテストを掲載しています。また、コンテストを目的として、現実的 か、非現実的 かの識別をしています。現実的なコンテスト は 独立した公式コンテストを指します。

現実的なコンテスト とは、以下の基準を満たす、独立した公式コンテストを指します。

明確に定義された実際のユースケースであること
実際に制約があること
実際のデータセットが複数あること
特定のハードウェアで特定の時間内に結果を再現できること
教育機関および/または企業の運用研究コミュニティーが真剣に参加していること

現実的なコンテストでは、競合のソフトウェアや教育研究と Business Optimizer を客観的に比較できます。

Expand

表3.1 サンプルの概要
例	ドメイン	Size	コンテスト	ディレクトリー名
N クィーン	エンティティークラス 1 つ変数 1 つ	エンティティー ⇐ `256` 値 ⇐ `256` 探索空間 ⇐ `10^616`	意味がない (不正が可能)	`nqueens`
クラウドバランシング	エンティティークラス 1 つ変数 1 つ	エンティティー ⇐ `2400` 値 ⇐ `800` 探索空間 ⇐ `10^6967`	いいえ弊社が定義	`cloudbalancing`
巡回セールスマン	エンティティークラス 1 つ連鎖変数 1 つ	エンティティー ⇐ `980` 値 ⇐ `980` 探索空間 ⇐ `10^2504`	現実的でない TSP web	`tsp`
ディナーパーティー	エンティティークラス 1 つ変数 1 つ	エンティティー ⇐ `144` 値 ⇐ `72` 探索空間 ⇐ `10^310`	現実的でない	`dinnerParty`
テニスクラブのスケジュール	エンティティークラス 1 つ変数 1 つ	エンティティー ⇐ `72` 値 ⇐ `7` 探索空間 ⇐ `10^60`	いいえ弊社が定義	`tennis`
会議のスケジュール	エンティティークラス 1 つ変数 2 つ	エンティティー ⇐ `10` 値 ⇐ `320` および ⇐ `5` 探索空間 ⇐ `10^320`	いいえ弊社が定義	`meetingscheduling`
コースの時間割	エンティティークラス 1 つ変数 2 つ	エンティティー ⇐ `434` 値 ⇐ `25` および ⇐ `20` 探索空間 ⇐ `10^1171`	現実的 ITC 2007 track 3	`curriculumCourse`
マシンの再割当て	エンティティークラス 1 つ変数 1 つ	エンティティー ⇐ `50000` 値 ⇐ `5000` 探索空間 ⇐ `10^184948`	ほぼ現実的 ROADEF 2012	`machineReassignment`
配送経路	エンティティークラス 1 つ連鎖変数 1 つシャドウエンティティークラス 1 つ自動シャドウ変数 1 つ	エンティティー ⇐ `2740` 値 ⇐ `2795` 探索空間 ⇐ `10^8380`	現実的でない VRP web	`vehiclerouting`
時間枠がある中での配送経路	配送経路すべてシャドウ変数 1 つ	エンティティー ⇐ `2740` 値 ⇐ `2795` 探索空間 ⇐ `10^8380`	現実的でない VRP web	`vehiclerouting`
プロジェクトジョブのスケジュール	エンティティークラス 1 つ変数 2 つシャドウ変数 1 つ	エンティティー ⇐ `640` 値 ⇐ `?` および ⇐ `?` 探索空間 ⇐ `?`	ほぼ現実的 MISTA 2013	`projectjobscheduling`
タスクの割り当て	エンティティークラス 1 つ連鎖変数 1 つシャドウ変数 1 つシャドウエンティティークラス 1 つ自動シャドウ変数 1 つ	エンティティー ⇐ `500` 値 ⇐ `520` 探索空間 ⇐ `10^1168`	いいえ弊社が定義	`taskassigning`
試験の時間割	エンティティークラス 2 つ (同じ階層) 変数 2 つ	エンティティー ⇐ `1096` 値 ⇐ `80` および ⇐ `49` 探索空間 ⇐ `10^3374`	現実的 ITC 2007 track 1	`examination`
看護師の勤務表	エンティティークラス 1 つ変数 1 つ	エンティティー ⇐ `752` 値 ⇐ `50` 探索空間 ⇐ `10^1277`	現実的 INRC 2010	`nurserostering`
巡回トーナメント	エンティティークラス 1 つ変数 1 つ	エンティティー ⇐ `1560` 値 ⇐ `78` 探索空間 ⇐ `10^2301`	現実的でない TTP	`travelingtournament`
コストを抑えるスケジュール	エンティティークラス 1 つ変数 2 つ	エンティティー ⇐ `500` 値 ⇐ `100` および ⇐ `288` 探索空間 ⇐ `10^20078`	ほぼ現実的 ICON Energy	`cheaptimescheduling`
投資	エンティティークラス 1 つ変数 1 つ	エンティティー ⇐ `11` 値 = `1000` 探索空間 ⇐ `10^4`	いいえ弊社が定義	`investment`
会議のスケジュール	エンティティークラス 1 つ変数 2 つ	エンティティー ⇐ `216` 値 ⇐ `18` および ⇐ `20` 探索空間 ⇐ `10^552`	いいえ弊社が定義	`conferencescheduling`
ロックバンドのツアー	エンティティークラス 1 つ連鎖変数 1 つシャドウ変数 4 つシャドウエンティティークラス 1 つ自動シャドウ変数 1 つ	エンティティー ⇐ `47` 値 ⇐ `48` 探索空間 ⇐ `10^59`	いいえ弊社が定義	`rocktour`
航空機乗務員のスケジュール	エンティティークラス 1 つ変数 1 つシャドウエンティティークラス 1 つ自動シャドウ変数 1 つ	エンティティー ⇐ `4375` 値 ⇐ `750` 探索空間 ⇐ `10^12578`	いいえ弊社が定義	`flightcrewscheduling`

3.3. N クィーン
リンクのコピー

n サイズのチェスボードで、他のクィーンに取られない位置に n 個のクィーンを置きます。最も一般的な n クィーンパズルは、n = 8 の 8 個のクィーンパズルです。

制約:

n 行および n 列のチェスボードを使用します。
チェスボードに n 個のクィーンを置きます。
クィーンが他のクィーンに取られないように配置します。クィーンは、同じ水平線上、垂直線上、対角線上にある他のクィーンを取ることができます。

本書の例では、クィーン 4 個のパズルを主に使用します。

以下が提案された解です。

図3.1 クィーン 4 個のパズルの誤った解

上記の解は、A1 と B0 (および B0 と D0) のクィーンがお互いに駒を取れるので間違っています。B0 のクィーンをどかせば「他のクィーンに取られないようにする」という制約は順守できますが、「n 個のクィーンを置く」という制約に違反します。

以下は正しい解です。

図3.2 クィーン 4 個のパズルの正しい解

すべての制約が満たされているので、これが正解です。

n クィーンパズルでは、正解が複数存在する場合が多々あります。各 n に対して、考えられるすべての解を見つけるのではなく、指定の n に対する正しい解を 1 つ導き出すことにフォーカスします。

問題の規模

4queens   has   4 queens with a search space of    256.
8queens   has   8 queens with a search space of   10^7.
16queens  has  16 queens with a search space of  10^19.
32queens  has  32 queens with a search space of  10^48.
64queens  has  64 queens with a search space of 10^115.
256queens has 256 queens with a search space of 10^616.

n クィーンは、初心者用のサンプルとして実装されているため、最適化はされていませんが、クィーンが 64 個になっても簡単に処理できます。何点か変更を加えると、クィーンが 5000 個以上になっても簡単に対応できることが立証されています。

3.3.1. N クィーンのドメインモデル
リンクのコピー

この例では、4 つのクィーンの問題を解決するドメインモデルを使用します。

ドメインモデルの作成

適切なドメインモデルを使用すると、プランニングの問題をより簡単に理解し、解決することができます。

以下は、n クィーンの例のドメインモデルです。

public class Column {

    private int index;

    // ... getters and setters
}

public class Row {

    private int index;

    // ... getters and setters
}

public class Queen {

    private Column column;
    private Row row;

    public int getAscendingDiagonalIndex() {...}
    public int getDescendingDiagonalIndex() {...}

    // ... getters and setters
}

探索空間の計算
Queen インスタンスには Column (例: 0 は列 A、1 は列 B) および Row (例: 0 は行 0、1 は行 1) が含まれます。
列と行をもとに、昇順の対角線、降順の対角線を計算することができます。
列と行のインデックスは、チェスボードの左上隅から数えています。
```
public class NQueens {

    private int n;
    private List<Column> columnList;
    private List<Row> rowList;

    private List<Queen> queenList;

    private SimpleScore score;

    // ... getters and setters
}
```
1. 解の求め方
  1 つの NQueens インスタンスには Queen インスタンスの一覧が含まれています。これが Solution 実装として提供され、Solver が解決して読み出します。

たとえば、4 クイーンの例では、NQueens の getN() メソッドが常に 4 を返します。

図3.3 クィーン 4 個の解

Expand

表3.2 ドメインモデルの解の詳細
	columnIndex	rowIndex	ascendingDiagonalIndex (columnIndex + rowIndex)	descendingDiagonalIndex (columnIndex - rowIndex)
A1	0	1	1 ()**	-1
B0	1	*0 ()**	1 ()**	1
C2	2	2	4	0
D0	3	*0 ()**	3	3

(*) や (**) のように、クィーン 2 つが同じ行、列、対角線を共有する場合は、2 つの駒が互いを取ることができます。

3.4. クラウドバランシング
リンクのコピー

この例に関する詳細は、2章スタートガイド: クラウドバランシングの例を参照してください。

3.5. 巡回セールスマン (TSP - 巡回セールスマン問題)
リンクのコピー

都市の一覧をもとに、セールスマンが最短距離で、各都市を 1 度だけ訪問するルートを探します。

この問題はウィキペディアに定義されています。これは、計算数学で最も熱心に研究された問題の 1 つです。大概は、従業員のシフト勤務など、その他の制約と一緒に計画の問題の一部として使用されます。

問題の規模

dj38     has  38 cities with a search space of   10^43.
europe40 has  40 cities with a search space of   10^46.
st70     has  70 cities with a search space of   10^98.
pcb442   has 442 cities with a search space of  10^976.
lu980    has 980 cities with a search space of 10^2504.

問題の難易度

TSP の定義は単純ですが、問題の解決は驚くほど難しくなります。これは NP 困難問題と呼ばれ、多くの計画の問題と同様、特定の問題のデータセットに対する最適な解は、その問題のデータセットが少しでも変更すると、大幅に変化する可能性があります。

3.6. ディナーパーティー
リンクのコピー

マナーズさんがディナーパーティを再度開催することにしました。

今回は、ゲスト 144 名を招待し、円卓を 12 個用意し、各テーブルに椅子を 12 席用意しました。
座席は、同じ性別の人が隣同士にならないようにします。
また、隣の人とは必ず、同じ趣味を 1 つ持つようにします。
各テーブルには、政治家、医者、著名人、コーチ、教師、そしてプログラマーを 2 名ずつ配置します。
政治家、医者、コーチ、プログラマーは、それぞれ同じ業種の人が同じテーブルにならないようにします。

Drools Expert にも、(サイズがはるかに小さい) 一般的なミスマナーズの例が含まれており、包括的なヒューリスティックを採用して解を導き出しています。Planner の実装は、ヒューリスティックを使用して最適解を見つけ、Drools Expert を使用して各解のスコアを計算するため、スケーラビリティーがはるかに高くなっています。

問題の規模

wedding01 has 18 jobs, 144 guests, 288 hobby practicians, 12 tables and 144 seats with a search space of 10^310.

3.7. テニスクラブのスケジュール
リンクのコピー

テニスクラブでは、毎週 4 チームが総あたりで試合をします。4 つの対戦枠を公平にチームに割り当てます。

ハード制約:

制約: チームは 1 日に 1 回だけ試合ができる。
参加不可: 日程によって参加できないチームがある。

中程度の制約:

公平な割り当て: 各チームが試合をする回数を (ほぼ) 同じにする。

ソフト制約:

均等に対戦: 各チームが、各対戦相手と対戦する回数を同じにする。

問題の規模

munich-7teams has 7 teams, 18 days, 12 unavailabilityPenalties and 72 teamAssignments with a search space of 10^60.

図3.4 ドメインモデル

3.8. 会議のスケジュール
リンクのコピー

各会議に、開始時間と会議室を割り当てます。会議の長さは異なります。

ハード制約:

部屋の制約: 2 つの会議が、同じ時間に同じ会議室を使用することはできない。
必須の出席者: 同じ時間に開催される必須の会議を 2 つ割り当てることはできない。
必要とされる部屋の収容人数: 会議の出席者全員を収容できない部屋では会議を行ってはいけない。
同日中に開始して終了: 会議は複数の日にちにわたってスケジュールされないようにする。

中程度の制約:

任意の出席者: 同じ時間に開催される任意の会議を 2 つ割り当てることはできない。また、任意の会議、および必須の会議をそれぞれ 1 つ割り当てることはできない。

ソフト制約:

早い段階でスケジュール: すべての会議をできるだけ早くスケジュールする。
会議と会議の間の休憩時間: 会議と会議の間には、最低でも時間枠 1 つ分、休憩を入れる必要がある。
会議の重複: 並行して行われる会議の数を最小限に抑えて、どちらかの会議を選択しなければならない状況をなくす。
先に大きい部屋から割り当てる: 参加者がまだ登録していない場合でも、できるだけ多数の参加者を収容するために、大きい部屋が空いている場合にはその部屋から割り当てていく必要がある。
部屋の不変性: 会議が連続して行われ、休憩の時間枠が 2 つ分より少ない場合には、会議は同じ部屋で行う方が良い。

問題の規模

50meetings-160timegrains-5rooms  has  50 meetings, 160 timeGrains and 5 rooms with a search space of 10^145.
100meetings-320timegrains-5rooms has 100 meetings, 320 timeGrains and 5 rooms with a search space of 10^320.
200meetings-640timegrains-5rooms has 200 meetings, 640 timeGrains and 5 rooms with a search space of 10^701.
400meetings-1280timegrains-5rooms has 400 meetings, 1280 timeGrains and 5 rooms with a search space of 10^1522.
800meetings-2560timegrains-5rooms has 800 meetings, 2560 timeGrains and 5 rooms with a search space of 10^3285.

3.9. コースの時間割 (ITC 2007 Track 3 - カリキュラムのスケジュール)
リンクのコピー

各授業を、時間枠および講義室に割り当ててスケジュールを組みます。

ハード制約:

講師の制約: 各講師は、同じ時間に授業を 2 つ受け持つことはできない。
カリキュラムの制約: 1 つのカリキュラムに、2 つの授業を同じ時間に設定することはできない。
部屋の占有: 同じ時間 (Period) の同じ講義室に、2 つの授業を割り当てることはできない。
利用不可の時間 (データセットごとに指定): 授業には割り当てられない時間がある。

ソフト制約:

講義室の収容人数: 講義室の収容人数は、その授業を受ける学生の数よりも多くなければならない。
最小限の就業日数: 同じコースの授業の開講期間は、最短になるようにする。
カリキュラムの緊密さ: 同じカリキュラムに含まれる授業は、時間帯を近く (連続した時間に) 設定する。
講義室の不変性: 同じコースの授業は同じ講義室を割り当てる必要がある。

この問題は International Timetabling Competition 2007 track 3 で定義されています。

問題の規模

comp01 has 24 teachers,  14 curricula,  30 courses, 160 lectures, 30 periods,  6 rooms and   53 unavailable period constraints with a search space of  10^360.
comp02 has 71 teachers,  70 curricula,  82 courses, 283 lectures, 25 periods, 16 rooms and  513 unavailable period constraints with a search space of  10^736.
comp03 has 61 teachers,  68 curricula,  72 courses, 251 lectures, 25 periods, 16 rooms and  382 unavailable period constraints with a search space of  10^653.
comp04 has 70 teachers,  57 curricula,  79 courses, 286 lectures, 25 periods, 18 rooms and  396 unavailable period constraints with a search space of  10^758.
comp05 has 47 teachers, 139 curricula,  54 courses, 152 lectures, 36 periods,  9 rooms and  771 unavailable period constraints with a search space of  10^381.
comp06 has 87 teachers,  70 curricula, 108 courses, 361 lectures, 25 periods, 18 rooms and  632 unavailable period constraints with a search space of  10^957.
comp07 has 99 teachers,  77 curricula, 131 courses, 434 lectures, 25 periods, 20 rooms and  667 unavailable period constraints with a search space of 10^1171.
comp08 has 76 teachers,  61 curricula,  86 courses, 324 lectures, 25 periods, 18 rooms and  478 unavailable period constraints with a search space of  10^859.
comp09 has 68 teachers,  75 curricula,  76 courses, 279 lectures, 25 periods, 18 rooms and  405 unavailable period constraints with a search space of  10^740.
comp10 has 88 teachers,  67 curricula, 115 courses, 370 lectures, 25 periods, 18 rooms and  694 unavailable period constraints with a search space of  10^981.
comp11 has 24 teachers,  13 curricula,  30 courses, 162 lectures, 45 periods,  5 rooms and   94 unavailable period constraints with a search space of  10^381.
comp12 has 74 teachers, 150 curricula,  88 courses, 218 lectures, 36 periods, 11 rooms and 1368 unavailable period constraints with a search space of  10^566.
comp13 has 77 teachers,  66 curricula,  82 courses, 308 lectures, 25 periods, 19 rooms and  468 unavailable period constraints with a search space of  10^824.
comp14 has 68 teachers,  60 curricula,  85 courses, 275 lectures, 25 periods, 17 rooms and  486 unavailable period constraints with a search space of  10^722.

図3.5 ドメインモデル

3.10. マシンの再割当て (Google ROADEF 2012)
リンクのコピー

各プロセスをマシンに割り当てます。全プロセスには、すでに元の (最適化されていない) 割り当てがあります。プロセスにはそれぞれ、各リソース (CPU、メモリーなど) が一定量必要です。これは、クラウドのバランスの例の応用です。

ハード制約:

最大容量: マシンに割り当てる各リソースはこの量を超えてはいけない。
制約: 同じサービスのプロセスは別のマシンで実行する必要がある。
分散: 同じサービスのプロセスは複数の場所に分散させる必要がある。
依存関係: 他のサービスに依存するサービスのプロセスは、そのサービスの近くで実行する必要がある。
一時的な使用: リソースによっては一時的なものがあり、元のマシンと、新たに割り当てられたマシンの両方の最大容量にカウントされる。

ソフト制約:

負荷: 各マシンの各リソースの安全容量を超えてはいけない。
負荷分散: 各マシンで利用可能なリソースを分散させて、今後の割り当てに対応できるように容量を空ける。
プロセスの移動コスト: プロセスには移動コストが発生する。
サービスの移動コスト: サービスには移動コストが発生する。
機械の移動コスト: マシン A からマシン B にプロセスを移動すると、A から B に固有の移動コストが別途発生する。

この問題は the Google ROADEF/EURO Challenge 2012 で定義されています。

図3.6 価値提案

問題の規模

model_a1_1 has  2 resources,  1 neighborhoods,   4 locations,    4 machines,    79 services,   100 processes and 1 balancePenalties with a search space of     10^60.
model_a1_2 has  4 resources,  2 neighborhoods,   4 locations,  100 machines,   980 services,  1000 processes and 0 balancePenalties with a search space of   10^2000.
model_a1_3 has  3 resources,  5 neighborhoods,  25 locations,  100 machines,   216 services,  1000 processes and 0 balancePenalties with a search space of   10^2000.
model_a1_4 has  3 resources, 50 neighborhoods,  50 locations,   50 machines,   142 services,  1000 processes and 1 balancePenalties with a search space of   10^1698.
model_a1_5 has  4 resources,  2 neighborhoods,   4 locations,   12 machines,   981 services,  1000 processes and 1 balancePenalties with a search space of   10^1079.
model_a2_1 has  3 resources,  1 neighborhoods,   1 locations,  100 machines,  1000 services,  1000 processes and 0 balancePenalties with a search space of   10^2000.
model_a2_2 has 12 resources,  5 neighborhoods,  25 locations,  100 machines,   170 services,  1000 processes and 0 balancePenalties with a search space of   10^2000.
model_a2_3 has 12 resources,  5 neighborhoods,  25 locations,  100 machines,   129 services,  1000 processes and 0 balancePenalties with a search space of   10^2000.
model_a2_4 has 12 resources,  5 neighborhoods,  25 locations,   50 machines,   180 services,  1000 processes and 1 balancePenalties with a search space of   10^1698.
model_a2_5 has 12 resources,  5 neighborhoods,  25 locations,   50 machines,   153 services,  1000 processes and 0 balancePenalties with a search space of   10^1698.
model_b_1  has 12 resources,  5 neighborhoods,  10 locations,  100 machines,  2512 services,  5000 processes and 0 balancePenalties with a search space of  10^10000.
model_b_2  has 12 resources,  5 neighborhoods,  10 locations,  100 machines,  2462 services,  5000 processes and 1 balancePenalties with a search space of  10^10000.
model_b_3  has  6 resources,  5 neighborhoods,  10 locations,  100 machines, 15025 services, 20000 processes and 0 balancePenalties with a search space of  10^40000.
model_b_4  has  6 resources,  5 neighborhoods,  50 locations,  500 machines,  1732 services, 20000 processes and 1 balancePenalties with a search space of  10^53979.
model_b_5  has  6 resources,  5 neighborhoods,  10 locations,  100 machines, 35082 services, 40000 processes and 0 balancePenalties with a search space of  10^80000.
model_b_6  has  6 resources,  5 neighborhoods,  50 locations,  200 machines, 14680 services, 40000 processes and 1 balancePenalties with a search space of  10^92041.
model_b_7  has  6 resources,  5 neighborhoods,  50 locations, 4000 machines, 15050 services, 40000 processes and 1 balancePenalties with a search space of 10^144082.
model_b_8  has  3 resources,  5 neighborhoods,  10 locations,  100 machines, 45030 services, 50000 processes and 0 balancePenalties with a search space of 10^100000.
model_b_9  has  3 resources,  5 neighborhoods, 100 locations, 1000 machines,  4609 services, 50000 processes and 1 balancePenalties with a search space of 10^150000.
model_b_10 has  3 resources,  5 neighborhoods, 100 locations, 5000 machines,  4896 services, 50000 processes and 1 balancePenalties with a search space of 10^184948.

図3.7 ドメインモデル

3.11. 配送経路
リンクのコピー

複数の車両を使用して、各顧客の品物を回収し、倉庫まで運びます。1 つの車両で複数の顧客から品物を回収することはできますが、収容できる容量には限りがあります。

基本例 (CVRP) のほかに、時間枠の設定が加わった例 (CVRPTW) もあります。

ハード制約:

車両の容量: 車両は、車載容量を超えて品物を運ぶことができない。
時間枠 (CVRPTW のみ):
- 移動時間: 別の場所に移動する場合には時間がかかる。
- 顧客対応の時間: 車両は顧客に対応している時間、顧客先にとどまる必要がある。
- 顧客の準備が整う時間: 顧客の準備が整う前に車両が到着する可能性があるが、準備ができるまで待機してから顧客に対応する必要がある。
- 顧客が設定した締め切り時間: 車両は、顧客が設定した締め切り時間までに到着する必要がある。

ソフト制約:

合計距離: 車両が移動する合計距離 (ガソリンの消費量) を最小限に抑える。

CVRP (Capacitated Vehicle Routing Problem) と CVRPTW (Capacitated Vehicle Routing Problem with Time Window) は、VRP web で定義されています。

図3.8 価値提案

問題の規模

CVRP インスタンス (時間枠なし):

belgium-n50-k10             has  1 depots, 10 vehicles and   49 customers with a search space of   10^74.
belgium-n100-k10            has  1 depots, 10 vehicles and   99 customers with a search space of  10^170.
belgium-n500-k20            has  1 depots, 20 vehicles and  499 customers with a search space of 10^1168.
belgium-n1000-k20           has  1 depots, 20 vehicles and  999 customers with a search space of 10^2607.
belgium-n2750-k55           has  1 depots, 55 vehicles and 2749 customers with a search space of 10^8380.
belgium-road-km-n50-k10     has  1 depots, 10 vehicles and   49 customers with a search space of   10^74.
belgium-road-km-n100-k10    has  1 depots, 10 vehicles and   99 customers with a search space of  10^170.
belgium-road-km-n500-k20    has  1 depots, 20 vehicles and  499 customers with a search space of 10^1168.
belgium-road-km-n1000-k20   has  1 depots, 20 vehicles and  999 customers with a search space of 10^2607.
belgium-road-km-n2750-k55   has  1 depots, 55 vehicles and 2749 customers with a search space of 10^8380.
belgium-road-time-n50-k10   has  1 depots, 10 vehicles and   49 customers with a search space of   10^74.
belgium-road-time-n100-k10  has  1 depots, 10 vehicles and   99 customers with a search space of  10^170.
belgium-road-time-n500-k20  has  1 depots, 20 vehicles and  499 customers with a search space of 10^1168.
belgium-road-time-n1000-k20 has  1 depots, 20 vehicles and  999 customers with a search space of 10^2607.
belgium-road-time-n2750-k55 has  1 depots, 55 vehicles and 2749 customers with a search space of 10^8380.
belgium-d2-n50-k10          has  2 depots, 10 vehicles and   48 customers with a search space of   10^74.
belgium-d3-n100-k10         has  3 depots, 10 vehicles and   97 customers with a search space of  10^170.
belgium-d5-n500-k20         has  5 depots, 20 vehicles and  495 customers with a search space of 10^1168.
belgium-d8-n1000-k20        has  8 depots, 20 vehicles and  992 customers with a search space of 10^2607.
belgium-d10-n2750-k55       has 10 depots, 55 vehicles and 2740 customers with a search space of 10^8380.

A-n32-k5  has 1 depots,  5 vehicles and  31 customers with a search space of  10^40.
A-n33-k5  has 1 depots,  5 vehicles and  32 customers with a search space of  10^41.
A-n33-k6  has 1 depots,  6 vehicles and  32 customers with a search space of  10^42.
A-n34-k5  has 1 depots,  5 vehicles and  33 customers with a search space of  10^43.
A-n36-k5  has 1 depots,  5 vehicles and  35 customers with a search space of  10^46.
A-n37-k5  has 1 depots,  5 vehicles and  36 customers with a search space of  10^48.
A-n37-k6  has 1 depots,  6 vehicles and  36 customers with a search space of  10^49.
A-n38-k5  has 1 depots,  5 vehicles and  37 customers with a search space of  10^49.
A-n39-k5  has 1 depots,  5 vehicles and  38 customers with a search space of  10^51.
A-n39-k6  has 1 depots,  6 vehicles and  38 customers with a search space of  10^52.
A-n44-k7  has 1 depots,  7 vehicles and  43 customers with a search space of  10^61.
A-n45-k6  has 1 depots,  6 vehicles and  44 customers with a search space of  10^62.
A-n45-k7  has 1 depots,  7 vehicles and  44 customers with a search space of  10^63.
A-n46-k7  has 1 depots,  7 vehicles and  45 customers with a search space of  10^65.
A-n48-k7  has 1 depots,  7 vehicles and  47 customers with a search space of  10^68.
A-n53-k7  has 1 depots,  7 vehicles and  52 customers with a search space of  10^77.
A-n54-k7  has 1 depots,  7 vehicles and  53 customers with a search space of  10^79.
A-n55-k9  has 1 depots,  9 vehicles and  54 customers with a search space of  10^82.
A-n60-k9  has 1 depots,  9 vehicles and  59 customers with a search space of  10^91.
A-n61-k9  has 1 depots,  9 vehicles and  60 customers with a search space of  10^93.
A-n62-k8  has 1 depots,  8 vehicles and  61 customers with a search space of  10^94.
A-n63-k9  has 1 depots,  9 vehicles and  62 customers with a search space of  10^97.
A-n63-k10 has 1 depots, 10 vehicles and  62 customers with a search space of  10^98.
A-n64-k9  has 1 depots,  9 vehicles and  63 customers with a search space of  10^99.
A-n65-k9  has 1 depots,  9 vehicles and  64 customers with a search space of 10^101.
A-n69-k9  has 1 depots,  9 vehicles and  68 customers with a search space of 10^108.
A-n80-k10 has 1 depots, 10 vehicles and  79 customers with a search space of 10^130.
F-n45-k4  has 1 depots,  4 vehicles and  44 customers with a search space of  10^60.
F-n72-k4  has 1 depots,  4 vehicles and  71 customers with a search space of 10^108.
F-n135-k7 has 1 depots,  7 vehicles and 134 customers with a search space of 10^240.

CVRPTW インスタンス (時間枠あり):

belgium-tw-d2-n50-k10    has  2 depots, 10 vehicles and   48 customers with a search space of   10^74.
belgium-tw-d3-n100-k10   has  3 depots, 10 vehicles and   97 customers with a search space of  10^170.
belgium-tw-d5-n500-k20   has  5 depots, 20 vehicles and  495 customers with a search space of 10^1168.
belgium-tw-d8-n1000-k20  has  8 depots, 20 vehicles and  992 customers with a search space of 10^2607.
belgium-tw-d10-n2750-k55 has 10 depots, 55 vehicles and 2740 customers with a search space of 10^8380.
belgium-tw-n50-k10       has  1 depots, 10 vehicles and   49 customers with a search space of   10^74.
belgium-tw-n100-k10      has  1 depots, 10 vehicles and   99 customers with a search space of  10^170.
belgium-tw-n500-k20      has  1 depots, 20 vehicles and  499 customers with a search space of 10^1168.
belgium-tw-n1000-k20     has  1 depots, 20 vehicles and  999 customers with a search space of 10^2607.
belgium-tw-n2750-k55     has  1 depots, 55 vehicles and 2749 customers with a search space of 10^8380.

Solomon_025_C101       has 1 depots,  25 vehicles and   25 customers with a search space of   10^40.
Solomon_025_C201       has 1 depots,  25 vehicles and   25 customers with a search space of   10^40.
Solomon_025_R101       has 1 depots,  25 vehicles and   25 customers with a search space of   10^40.
Solomon_025_R201       has 1 depots,  25 vehicles and   25 customers with a search space of   10^40.
Solomon_025_RC101      has 1 depots,  25 vehicles and   25 customers with a search space of   10^40.
Solomon_025_RC201      has 1 depots,  25 vehicles and   25 customers with a search space of   10^40.
Solomon_100_C101       has 1 depots,  25 vehicles and  100 customers with a search space of  10^185.
Solomon_100_C201       has 1 depots,  25 vehicles and  100 customers with a search space of  10^185.
Solomon_100_R101       has 1 depots,  25 vehicles and  100 customers with a search space of  10^185.
Solomon_100_R201       has 1 depots,  25 vehicles and  100 customers with a search space of  10^185.
Solomon_100_RC101      has 1 depots,  25 vehicles and  100 customers with a search space of  10^185.
Solomon_100_RC201      has 1 depots,  25 vehicles and  100 customers with a search space of  10^185.
Homberger_0200_C1_2_1  has 1 depots,  50 vehicles and  200 customers with a search space of  10^429.
Homberger_0200_C2_2_1  has 1 depots,  50 vehicles and  200 customers with a search space of  10^429.
Homberger_0200_R1_2_1  has 1 depots,  50 vehicles and  200 customers with a search space of  10^429.
Homberger_0200_R2_2_1  has 1 depots,  50 vehicles and  200 customers with a search space of  10^429.
Homberger_0200_RC1_2_1 has 1 depots,  50 vehicles and  200 customers with a search space of  10^429.
Homberger_0200_RC2_2_1 has 1 depots,  50 vehicles and  200 customers with a search space of  10^429.
Homberger_0400_C1_4_1  has 1 depots, 100 vehicles and  400 customers with a search space of  10^978.
Homberger_0400_C2_4_1  has 1 depots, 100 vehicles and  400 customers with a search space of  10^978.
Homberger_0400_R1_4_1  has 1 depots, 100 vehicles and  400 customers with a search space of  10^978.
Homberger_0400_R2_4_1  has 1 depots, 100 vehicles and  400 customers with a search space of  10^978.
Homberger_0400_RC1_4_1 has 1 depots, 100 vehicles and  400 customers with a search space of  10^978.
Homberger_0400_RC2_4_1 has 1 depots, 100 vehicles and  400 customers with a search space of  10^978.
Homberger_0600_C1_6_1  has 1 depots, 150 vehicles and  600 customers with a search space of 10^1571.
Homberger_0600_C2_6_1  has 1 depots, 150 vehicles and  600 customers with a search space of 10^1571.
Homberger_0600_R1_6_1  has 1 depots, 150 vehicles and  600 customers with a search space of 10^1571.
Homberger_0600_R2_6_1  has 1 depots, 150 vehicles and  600 customers with a search space of 10^1571.
Homberger_0600_RC1_6_1 has 1 depots, 150 vehicles and  600 customers with a search space of 10^1571.
Homberger_0600_RC2_6_1 has 1 depots, 150 vehicles and  600 customers with a search space of 10^1571.
Homberger_0800_C1_8_1  has 1 depots, 200 vehicles and  800 customers with a search space of 10^2195.
Homberger_0800_C2_8_1  has 1 depots, 200 vehicles and  800 customers with a search space of 10^2195.
Homberger_0800_R1_8_1  has 1 depots, 200 vehicles and  800 customers with a search space of 10^2195.
Homberger_0800_R2_8_1  has 1 depots, 200 vehicles and  800 customers with a search space of 10^2195.
Homberger_0800_RC1_8_1 has 1 depots, 200 vehicles and  800 customers with a search space of 10^2195.
Homberger_0800_RC2_8_1 has 1 depots, 200 vehicles and  800 customers with a search space of 10^2195.
Homberger_1000_C110_1  has 1 depots, 250 vehicles and 1000 customers with a search space of 10^2840.
Homberger_1000_C210_1  has 1 depots, 250 vehicles and 1000 customers with a search space of 10^2840.
Homberger_1000_R110_1  has 1 depots, 250 vehicles and 1000 customers with a search space of 10^2840.
Homberger_1000_R210_1  has 1 depots, 250 vehicles and 1000 customers with a search space of 10^2840.
Homberger_1000_RC110_1 has 1 depots, 250 vehicles and 1000 customers with a search space of 10^2840.
Homberger_1000_RC210_1 has 1 depots, 250 vehicles and 1000 customers with a search space of 10^2840.

3.11.1. 配送経路のドメインモデル
リンクのコピー

時間枠ありの配送経路のドメインモデルでは、シャドウ変数の機能を多用します。こうすることで、arrivalTime や departureTime などのプロパティーがドメインモデルで直接利用できるため、より自然に制約を表現することができます。

直線距離ではなく道路の距離

車は、直線距離を移動するのではなく、道路や高速道路を使用する必要があります。ビジネスの観点からすると、これは非常に重要です。

最適化アルゴリズムでは、2 点の距離を検索できている (できれば、事前に計算されている) 場合には、これは特に重要ではありません。移動のコストについては、距離の代わりに移動時間、ガソリン代、またはこれらの重み関数をベースにすることも可能です。GraphHopper (埋め込み可能なオフライン Java エンジン)、Open MapQuest (web サービス)、Google Maps Client API (web サービス) など、移動コストを事前に計算する技術があります。

また、Leaflet や Google Maps for developers など、移動コストをレンダリングする技術もあります。optaplanner-webexamples-*.war には、このようなレンダリングのデモ例が含まれています。

GraphHopper または Google Map Directions を使用して実際の経路をレンダリングすることも可能ですが、高速道路で経路が重なるため、停止する順番を確認するのが困難になります。

2 点間の移動コストは、Planner で使用したのと同じ最適化条件を使用する点に注意してください。たとえば、GraphHopper はデフォルトで、最短ではなく、最速の経路を返します。「最速」の GPS 経路の km (またはマイル) の距離を使用して、Planner で「最短」の移動を最適化しないようにしてください。以下のように、準最適な解が導き出される可能性があります。

一般的な考え方とは異なり、多くのユーザーは最短の経路ではなく、最速の経路を使用したいと考えます。通常の道路よりも高速道路の使用を、舗装されていない道よりも舗装されている道路を好みます。実際には、最速の経路と、最短の経路が同じであることはほぼありません。

3.12. プロジェクトジョブのスケジュール
リンクのコピー

プロジェクトの遅延を最小限に抑えるために、すべてのジョブを時間内に実行できるようにスケジュールを設定します。各ジョブは、プロジェクトに含まれます。ジョブは、異なる方法で実行でき、方法ごとに期間や使用するリソースが異なります。これは、柔軟な ジョブショップスケジューリング (JSP) の応用です。

ハード制約:

ジョブの優先順位: ジョブは、先行のジョブがすべて完了するまで開始しない。
リソースの容量: 利用可能な量を超えるリソースを使用しない。
- リソースはローカル (同じプロジェクトのジョブ間で共有)、またはグローバル (全ジョブ間で共有) とする。
- リソースは更新可能 (1 日に利用可能な容量) または更新不可 (全日で利用可能な容量) とする。

中程度の制約:

プロジェクトの合計遅延時間: 各プロジェクトの所要時間 (メイクスパン) を最短にする。

ソフト制約:

メイクスパン合計: 複数のプロジェクトスケジュールの合計所要時間を最短にする。

この問題は MISTA 2013 challenge で定義されています。

問題の規模

Schedule A-1  has  2 projects,  24 jobs,   64 execution modes,  7 resources and  150 resource requirements.
Schedule A-2  has  2 projects,  44 jobs,  124 execution modes,  7 resources and  420 resource requirements.
Schedule A-3  has  2 projects,  64 jobs,  184 execution modes,  7 resources and  630 resource requirements.
Schedule A-4  has  5 projects,  60 jobs,  160 execution modes, 16 resources and  390 resource requirements.
Schedule A-5  has  5 projects, 110 jobs,  310 execution modes, 16 resources and  900 resource requirements.
Schedule A-6  has  5 projects, 160 jobs,  460 execution modes, 16 resources and 1440 resource requirements.
Schedule A-7  has 10 projects, 120 jobs,  320 execution modes, 22 resources and  900 resource requirements.
Schedule A-8  has 10 projects, 220 jobs,  620 execution modes, 22 resources and 1860 resource requirements.
Schedule A-9  has 10 projects, 320 jobs,  920 execution modes, 31 resources and 2880 resource requirements.
Schedule A-10 has 10 projects, 320 jobs,  920 execution modes, 31 resources and 2970 resource requirements.
Schedule B-1  has 10 projects, 120 jobs,  320 execution modes, 31 resources and  900 resource requirements.
Schedule B-2  has 10 projects, 220 jobs,  620 execution modes, 22 resources and 1740 resource requirements.
Schedule B-3  has 10 projects, 320 jobs,  920 execution modes, 31 resources and 3060 resource requirements.
Schedule B-4  has 15 projects, 180 jobs,  480 execution modes, 46 resources and 1530 resource requirements.
Schedule B-5  has 15 projects, 330 jobs,  930 execution modes, 46 resources and 2760 resource requirements.
Schedule B-6  has 15 projects, 480 jobs, 1380 execution modes, 46 resources and 4500 resource requirements.
Schedule B-7  has 20 projects, 240 jobs,  640 execution modes, 61 resources and 1710 resource requirements.
Schedule B-8  has 20 projects, 440 jobs, 1240 execution modes, 42 resources and 3180 resource requirements.
Schedule B-9  has 20 projects, 640 jobs, 1840 execution modes, 61 resources and 5940 resource requirements.
Schedule B-10 has 20 projects, 460 jobs, 1300 execution modes, 42 resources and 4260 resource requirements.

3.13. タスクの割り当て
リンクのコピー

従業員のキューのスポットに各タスクを割り当てます。タスクごとに、従業員のアフィニティーレベルから影響を受ける期間と、タスクの顧客が含まれます。

ハード制約:

スキル: タスクごとに 1 つ以上のスキルが必要である。従業員には、これらの全スキルが必要です。

ソフトレベル 0 の制約:

極めて重要なタスク: マイナーなタスクおよび、主要なタスクの前に、先に極めて重要なタスクを完了する。

ソフトレベル 1 の制約:

メークスパンの最小化: 全タスクを完了するまでの時間を短縮する。
- 勤務歴の長い従業員から順番に進めていき、公平性やロードバランシングを作成します。

ソフトレベル 2 の制約:

主要なタスク: マイナーなタスクの前に、主要なタスクをできるだけ早く完了する。

ソフトレベル 3 の制約:

マイナーなタスク: できるだけ早くマイナーなタスクを完了する。

図3.9 価値提案

問題の規模

24tasks-8employees   has  24 tasks, 6 skills,  8 employees,   4 task types and  4 customers with a search space of   10^30.
50tasks-5employees   has  50 tasks, 5 skills,  5 employees,  10 task types and 10 customers with a search space of   10^69.
100tasks-5employees  has 100 tasks, 5 skills,  5 employees,  20 task types and 15 customers with a search space of  10^164.
500tasks-20employees has 500 tasks, 6 skills, 20 employees, 100 task types and 60 customers with a search space of 10^1168.

図3.10 ドメインモデル

3.14. 試験の時間割 (ITC 2007 track 1 - 試験)
リンクのコピー

すべての試験に、時間と部屋を割り当てます。同じ時間帯に同じ部屋で、複数の試験を行うことができるものとします。

ハード制約:

試験の制約: 同じ学生が受ける 2 つの試験は、同じ時間帯に実施できないものとする。
教室の収容人数: 教室の座席数は、常に受験者数よりも多くなければならない。
期間: 期間は、すべての試験に対応できる長さでなければならない。
期間関連のハード制約 (データセットごとに指定):
- 一致: 特定の 2 つの試験を同じ時間帯に設定する必要がある (別の教室を使用することも可能)。
- 除外: 特定の 2 つの試験を同じ時間帯に設定できない。
- 以降: 特定の試験を、特定の試験の後に行う必要がある。
教室関連の制約 (データセット毎ごとに指定):
- 排他的: 特定の試験を、他の試験と同じ教室で行うことはできない。

ソフト制約 (パラメーター化されたペナルティーがそれぞれ設定されている):

同じ学生が、続けて試験を 2 つ受けてはいけない。
同じ学生が、同じ日に試験を 2 つ受けてはいけない。
時間帯の分散: 同じ学生が受ける 2 つの試験は、時間をある程度あける。
異なる試験の長さ: 教室を共有する 2 つの試験の長さは、同じにする。
前倒し: 規模の大きい試験は、スケジュールを早めに決定する。
期間のペナルティー (データセットごとに指定): 期間によっては、使用されるとペナルティーが発生する。
部屋のペナルティー (データセットごとに指定): 部屋によっては、使用されるとペナルティーが発生する。

大学から取得した試験の大規模データセットを使用します。

この問題は International Timetabling Competition 2007 track 1 で明示されました。Geoffrey De Smet 氏は、ごく初期段階の Planner を使用して、このコンペティションで 4 位を獲得しました。このコンペティション以降、多くの改良点が加えられています。

問題の規模

exam_comp_set1 has  7883 students,  607 exams, 54 periods,  7 rooms,  12 period constraints and  0 room constraints with a search space of 10^1564.
exam_comp_set2 has 12484 students,  870 exams, 40 periods, 49 rooms,  12 period constraints and  2 room constraints with a search space of 10^2864.
exam_comp_set3 has 16365 students,  934 exams, 36 periods, 48 rooms, 168 period constraints and 15 room constraints with a search space of 10^3023.
exam_comp_set4 has  4421 students,  273 exams, 21 periods,  1 rooms,  40 period constraints and  0 room constraints with a search space of  10^360.
exam_comp_set5 has  8719 students, 1018 exams, 42 periods,  3 rooms,  27 period constraints and  0 room constraints with a search space of 10^2138.
exam_comp_set6 has  7909 students,  242 exams, 16 periods,  8 rooms,  22 period constraints and  0 room constraints with a search space of  10^509.
exam_comp_set7 has 13795 students, 1096 exams, 80 periods, 15 rooms,  28 period constraints and  0 room constraints with a search space of 10^3374.
exam_comp_set8 has  7718 students,  598 exams, 80 periods,  8 rooms,  20 period constraints and  1 room constraints with a search space of 10^1678.

3.14.1. 試験の時間割のドメインモデル
リンクのコピー

以下の図では、主な試験のドメインクラスを紹介しています。

図3.11 試験のドメインクラスの図

試験のコンセプトを、Exam クラスと Topic クラスに分けた点に注意してください。期間または教室のプロパティーを変更し、ソリューション (プランニングエンティティークラス) を求めると、Exam インスタンスが変化します。このとき、Topic インスタンス、Period インスタンス、および Room インスタンスは変化しません (他のクラスと同様、これらも問題ファクトです)。

3.15. 看護師の勤務表 (INRC 2010)
リンクのコピー

各シフトに看護師を割り当てます。

ハード制約:

未割り当てのシフトなし (組み込み): すべてのシフトを従業員に割り当てる必要がある。
シフトの制約: 従業員には 1 日に 1 シフトだけ割り当てることができる。

ソフト制約:

契約上の義務: この業界では、頻繁に契約上の義務に違反するため、ハード制約ではなく、ソフト制約として定義することに決定しました。
- 割り当ての下限および上限: 各従業員は、(それぞれの契約に合わせて) x より多く、y よりも少ないシフト数を勤務する必要がある。
- 連続勤務日数の下限および上限: 各従業員は、(それぞれの契約に合わせて) 連続で x 日から y 日間、勤務する必要がある。
- 連続公休日数の下限および上限: 各従業員は、(それぞれの契約に合わせて) 連続で x 日から y 日間、休む必要がある。
- 週末に連続勤務する回数の下限および上限: 各従業員は、(それぞれの契約に合わせて) 連続で x 回から y 回、週末勤務する必要がある。
- 週末の勤務有無を同じにする: 各従業員は、週末の両日を勤務する、または休む必要がある。
- 週末のシフトタイプを同じにする: 各従業員に、同じ週末のシフトタイプは、同じにする必要がある。
- 好ましくないシフトパターン: 遅番＋早番＋遅番など、好ましくないシフトタイプを連続で組み合わせたパターン。
従業員の希望:
- 勤務日のリクエスト: 従業員は、特定の勤務希望日を申請できる。
- 公休日のリクエスト: 従業員は、特定の公休希望日を申請できる。
- 勤務するシフトのリクエスト: 従業員は特定のシフトへの割り当てを希望できる。
- 勤務しないシフトのリクエスト: 従業員は特定のシフトに割り当てられないように希望できる。
他のスキル: シフトに割り当てられた従業員は、そのシフトで必要な全スキルに堪能である必要がある。

この問題は International Nurse Rostering Competition 2010 で定義されています。

図3.12 価値提案

問題の規模

以下のように、データセットの種類は 3 つあります。

sprint: 数秒で問題を解決する必要があります。
medium: 数分で問題を解決する必要があります。
long: 数時間で問題を解決する必要があります。

toy1          has 1 skills, 3 shiftTypes, 2 patterns, 1 contracts,  6 employees,  7 shiftDates,  35 shiftAssignments and   0 requests with a search space of   10^27.
toy2          has 1 skills, 3 shiftTypes, 3 patterns, 2 contracts, 20 employees, 28 shiftDates, 180 shiftAssignments and 140 requests with a search space of  10^234.

sprint01      has 1 skills, 4 shiftTypes, 3 patterns, 4 contracts, 10 employees, 28 shiftDates, 152 shiftAssignments and 150 requests with a search space of  10^152.
sprint02      has 1 skills, 4 shiftTypes, 3 patterns, 4 contracts, 10 employees, 28 shiftDates, 152 shiftAssignments and 150 requests with a search space of  10^152.
sprint03      has 1 skills, 4 shiftTypes, 3 patterns, 4 contracts, 10 employees, 28 shiftDates, 152 shiftAssignments and 150 requests with a search space of  10^152.
sprint04      has 1 skills, 4 shiftTypes, 3 patterns, 4 contracts, 10 employees, 28 shiftDates, 152 shiftAssignments and 150 requests with a search space of  10^152.
sprint05      has 1 skills, 4 shiftTypes, 3 patterns, 4 contracts, 10 employees, 28 shiftDates, 152 shiftAssignments and 150 requests with a search space of  10^152.
sprint06      has 1 skills, 4 shiftTypes, 3 patterns, 4 contracts, 10 employees, 28 shiftDates, 152 shiftAssignments and 150 requests with a search space of  10^152.
sprint07      has 1 skills, 4 shiftTypes, 3 patterns, 4 contracts, 10 employees, 28 shiftDates, 152 shiftAssignments and 150 requests with a search space of  10^152.
sprint08      has 1 skills, 4 shiftTypes, 3 patterns, 4 contracts, 10 employees, 28 shiftDates, 152 shiftAssignments and 150 requests with a search space of  10^152.
sprint09      has 1 skills, 4 shiftTypes, 3 patterns, 4 contracts, 10 employees, 28 shiftDates, 152 shiftAssignments and 150 requests with a search space of  10^152.
sprint10      has 1 skills, 4 shiftTypes, 3 patterns, 4 contracts, 10 employees, 28 shiftDates, 152 shiftAssignments and 150 requests with a search space of  10^152.
sprint_hint01 has 1 skills, 4 shiftTypes, 8 patterns, 3 contracts, 10 employees, 28 shiftDates, 152 shiftAssignments and 150 requests with a search space of  10^152.
sprint_hint02 has 1 skills, 4 shiftTypes, 0 patterns, 3 contracts, 10 employees, 28 shiftDates, 152 shiftAssignments and 150 requests with a search space of  10^152.
sprint_hint03 has 1 skills, 4 shiftTypes, 8 patterns, 3 contracts, 10 employees, 28 shiftDates, 152 shiftAssignments and 150 requests with a search space of  10^152.
sprint_late01 has 1 skills, 4 shiftTypes, 8 patterns, 3 contracts, 10 employees, 28 shiftDates, 152 shiftAssignments and 150 requests with a search space of  10^152.
sprint_late02 has 1 skills, 3 shiftTypes, 4 patterns, 3 contracts, 10 employees, 28 shiftDates, 144 shiftAssignments and 139 requests with a search space of  10^144.
sprint_late03 has 1 skills, 4 shiftTypes, 8 patterns, 3 contracts, 10 employees, 28 shiftDates, 160 shiftAssignments and 150 requests with a search space of  10^160.
sprint_late04 has 1 skills, 4 shiftTypes, 8 patterns, 3 contracts, 10 employees, 28 shiftDates, 160 shiftAssignments and 150 requests with a search space of  10^160.
sprint_late05 has 1 skills, 4 shiftTypes, 8 patterns, 3 contracts, 10 employees, 28 shiftDates, 152 shiftAssignments and 150 requests with a search space of  10^152.
sprint_late06 has 1 skills, 4 shiftTypes, 0 patterns, 3 contracts, 10 employees, 28 shiftDates, 152 shiftAssignments and 150 requests with a search space of  10^152.
sprint_late07 has 1 skills, 4 shiftTypes, 0 patterns, 3 contracts, 10 employees, 28 shiftDates, 152 shiftAssignments and 150 requests with a search space of  10^152.
sprint_late08 has 1 skills, 4 shiftTypes, 0 patterns, 3 contracts, 10 employees, 28 shiftDates, 152 shiftAssignments and   0 requests with a search space of  10^152.
sprint_late09 has 1 skills, 4 shiftTypes, 0 patterns, 3 contracts, 10 employees, 28 shiftDates, 152 shiftAssignments and   0 requests with a search space of  10^152.
sprint_late10 has 1 skills, 4 shiftTypes, 0 patterns, 3 contracts, 10 employees, 28 shiftDates, 152 shiftAssignments and 150 requests with a search space of  10^152.

medium01      has 1 skills, 4 shiftTypes, 0 patterns, 4 contracts, 31 employees, 28 shiftDates, 608 shiftAssignments and 403 requests with a search space of  10^906.
medium02      has 1 skills, 4 shiftTypes, 0 patterns, 4 contracts, 31 employees, 28 shiftDates, 608 shiftAssignments and 403 requests with a search space of  10^906.
medium03      has 1 skills, 4 shiftTypes, 0 patterns, 4 contracts, 31 employees, 28 shiftDates, 608 shiftAssignments and 403 requests with a search space of  10^906.
medium04      has 1 skills, 4 shiftTypes, 0 patterns, 4 contracts, 31 employees, 28 shiftDates, 608 shiftAssignments and 403 requests with a search space of  10^906.
medium05      has 1 skills, 4 shiftTypes, 0 patterns, 4 contracts, 31 employees, 28 shiftDates, 608 shiftAssignments and 403 requests with a search space of  10^906.
medium_hint01 has 1 skills, 4 shiftTypes, 7 patterns, 4 contracts, 30 employees, 28 shiftDates, 428 shiftAssignments and 390 requests with a search space of  10^632.
medium_hint02 has 1 skills, 4 shiftTypes, 7 patterns, 3 contracts, 30 employees, 28 shiftDates, 428 shiftAssignments and 390 requests with a search space of  10^632.
medium_hint03 has 1 skills, 4 shiftTypes, 7 patterns, 4 contracts, 30 employees, 28 shiftDates, 428 shiftAssignments and 390 requests with a search space of  10^632.
medium_late01 has 1 skills, 4 shiftTypes, 7 patterns, 4 contracts, 30 employees, 28 shiftDates, 424 shiftAssignments and 390 requests with a search space of  10^626.
medium_late02 has 1 skills, 4 shiftTypes, 7 patterns, 3 contracts, 30 employees, 28 shiftDates, 428 shiftAssignments and 390 requests with a search space of  10^632.
medium_late03 has 1 skills, 4 shiftTypes, 0 patterns, 4 contracts, 30 employees, 28 shiftDates, 428 shiftAssignments and 390 requests with a search space of  10^632.
medium_late04 has 1 skills, 4 shiftTypes, 7 patterns, 3 contracts, 30 employees, 28 shiftDates, 416 shiftAssignments and 390 requests with a search space of  10^614.
medium_late05 has 2 skills, 5 shiftTypes, 7 patterns, 4 contracts, 30 employees, 28 shiftDates, 452 shiftAssignments and 390 requests with a search space of  10^667.

long01        has 2 skills, 5 shiftTypes, 3 patterns, 3 contracts, 49 employees, 28 shiftDates, 740 shiftAssignments and 735 requests with a search space of 10^1250.
long02        has 2 skills, 5 shiftTypes, 3 patterns, 3 contracts, 49 employees, 28 shiftDates, 740 shiftAssignments and 735 requests with a search space of 10^1250.
long03        has 2 skills, 5 shiftTypes, 3 patterns, 3 contracts, 49 employees, 28 shiftDates, 740 shiftAssignments and 735 requests with a search space of 10^1250.
long04        has 2 skills, 5 shiftTypes, 3 patterns, 3 contracts, 49 employees, 28 shiftDates, 740 shiftAssignments and 735 requests with a search space of 10^1250.
long05        has 2 skills, 5 shiftTypes, 3 patterns, 3 contracts, 49 employees, 28 shiftDates, 740 shiftAssignments and 735 requests with a search space of 10^1250.
long_hint01   has 2 skills, 5 shiftTypes, 9 patterns, 3 contracts, 50 employees, 28 shiftDates, 740 shiftAssignments and   0 requests with a search space of 10^1257.
long_hint02   has 2 skills, 5 shiftTypes, 7 patterns, 3 contracts, 50 employees, 28 shiftDates, 740 shiftAssignments and   0 requests with a search space of 10^1257.
long_hint03   has 2 skills, 5 shiftTypes, 7 patterns, 3 contracts, 50 employees, 28 shiftDates, 740 shiftAssignments and   0 requests with a search space of 10^1257.
long_late01   has 2 skills, 5 shiftTypes, 9 patterns, 3 contracts, 50 employees, 28 shiftDates, 752 shiftAssignments and   0 requests with a search space of 10^1277.
long_late02   has 2 skills, 5 shiftTypes, 9 patterns, 4 contracts, 50 employees, 28 shiftDates, 752 shiftAssignments and   0 requests with a search space of 10^1277.
long_late03   has 2 skills, 5 shiftTypes, 9 patterns, 3 contracts, 50 employees, 28 shiftDates, 752 shiftAssignments and   0 requests with a search space of 10^1277.
long_late04   has 2 skills, 5 shiftTypes, 9 patterns, 4 contracts, 50 employees, 28 shiftDates, 752 shiftAssignments and   0 requests with a search space of 10^1277.
long_late05   has 2 skills, 5 shiftTypes, 9 patterns, 3 contracts, 50 employees, 28 shiftDates, 740 shiftAssignments and   0 requests with a search space of 10^1257.

図3.13 ドメインモデル

3.16. 巡回トーナメント問題 (TTP)
リンクのコピー

n チーム間の試合をスケジュールします。

ハード制約:

各チームは、他のチームとそれぞれ 2 回 (ホームとアウェイ) 試合をする。
各チームは、各時間枠に 1 試合だけ行う。
3 回連続で、ホームまたはアウェイでの試合はできない。
繰り返しなし: 同じ対戦相手と 2 回連続で対戦できない。

ソフト制約:

全チームが移動する合計距離を最小限に抑える。

この問題は Michael Trick の Web サイト (世界記録が含まれます) で定義されています。

問題の規模

1-nl04     has  6 days,  4 teams and   12 matches with a search space of    10^5.
1-nl06     has 10 days,  6 teams and   30 matches with a search space of   10^19.
1-nl08     has 14 days,  8 teams and   56 matches with a search space of   10^43.
1-nl10     has 18 days, 10 teams and   90 matches with a search space of   10^79.
1-nl12     has 22 days, 12 teams and  132 matches with a search space of  10^126.
1-nl14     has 26 days, 14 teams and  182 matches with a search space of  10^186.
1-nl16     has 30 days, 16 teams and  240 matches with a search space of  10^259.
2-bra24    has 46 days, 24 teams and  552 matches with a search space of  10^692.
3-nfl16    has 30 days, 16 teams and  240 matches with a search space of  10^259.
3-nfl18    has 34 days, 18 teams and  306 matches with a search space of  10^346.
3-nfl20    has 38 days, 20 teams and  380 matches with a search space of  10^447.
3-nfl22    has 42 days, 22 teams and  462 matches with a search space of  10^562.
3-nfl24    has 46 days, 24 teams and  552 matches with a search space of  10^692.
3-nfl26    has 50 days, 26 teams and  650 matches with a search space of  10^838.
3-nfl28    has 54 days, 28 teams and  756 matches with a search space of  10^999.
3-nfl30    has 58 days, 30 teams and  870 matches with a search space of 10^1175.
3-nfl32    has 62 days, 32 teams and  992 matches with a search space of 10^1367.
4-super04  has  6 days,  4 teams and   12 matches with a search space of    10^5.
4-super06  has 10 days,  6 teams and   30 matches with a search space of   10^19.
4-super08  has 14 days,  8 teams and   56 matches with a search space of   10^43.
4-super10  has 18 days, 10 teams and   90 matches with a search space of   10^79.
4-super12  has 22 days, 12 teams and  132 matches with a search space of  10^126.
4-super14  has 26 days, 14 teams and  182 matches with a search space of  10^186.
5-galaxy04 has  6 days,  4 teams and   12 matches with a search space of    10^5.
5-galaxy06 has 10 days,  6 teams and   30 matches with a search space of   10^19.
5-galaxy08 has 14 days,  8 teams and   56 matches with a search space of   10^43.
5-galaxy10 has 18 days, 10 teams and   90 matches with a search space of   10^79.
5-galaxy12 has 22 days, 12 teams and  132 matches with a search space of  10^126.
5-galaxy14 has 26 days, 14 teams and  182 matches with a search space of  10^186.
5-galaxy16 has 30 days, 16 teams and  240 matches with a search space of  10^259.
5-galaxy18 has 34 days, 18 teams and  306 matches with a search space of  10^346.
5-galaxy20 has 38 days, 20 teams and  380 matches with a search space of  10^447.
5-galaxy22 has 42 days, 22 teams and  462 matches with a search space of  10^562.
5-galaxy24 has 46 days, 24 teams and  552 matches with a search space of  10^692.
5-galaxy26 has 50 days, 26 teams and  650 matches with a search space of  10^838.
5-galaxy28 has 54 days, 28 teams and  756 matches with a search space of  10^999.
5-galaxy30 has 58 days, 30 teams and  870 matches with a search space of 10^1175.
5-galaxy32 has 62 days, 32 teams and  992 matches with a search space of 10^1367.
5-galaxy34 has 66 days, 34 teams and 1122 matches with a search space of 10^1576.
5-galaxy36 has 70 days, 36 teams and 1260 matches with a search space of 10^1801.
5-galaxy38 has 74 days, 38 teams and 1406 matches with a search space of 10^2042.
5-galaxy40 has 78 days, 40 teams and 1560 matches with a search space of 10^2301.

3.17. コストを抑えるスケジュール
リンクのコピー

全タスクを時間内にスケジュールし、機械の電気代を最小限に抑えます。電気代は時間によって異なります。これは、ジョブショップスケジューリング の応用です。

ハード制約:

開始時間の制限: 各タスクは、最早と最遅の開始時間の制限内に、開始する必要がある。
最大容量: マシンに割り当てる各リソースはこの量を超えてはいけない。
開始および終了: 各機械は、タスクが割り当てられている間は稼働している必要がある。次のタスクまでの間、起動および終了コストを避けるため、機械をアイドルにすることができる。

中程度の制約:

電気代: 全スケジュールの合計電気代を最小限に抑える。
- 機械の電気代: 稼働中またはアイドル中の機械はそれぞれ、電気を消費し、電気代が発生する (金額は使用時の電気代によって異なる)。
- タスクの電気代: 各タスクも電気を消費し、電気代が発生する (金額は使用時の電気代によって異なる)。
- 機械の起動および終了コスト: 機械を起動または終了するたびに、追加のコストが発生する。

ソフト制約 (問題に元々設定されている定義に追加):

早く開始: なるべく早めにタスクを開始するようにする。

この問題は ICON challenge で定義されています。

問題の規模

sample01   has 3 resources,   2 machines, 288 periods and   25 tasks with a search space of    10^53.
sample02   has 3 resources,   2 machines, 288 periods and   50 tasks with a search space of   10^114.
sample03   has 3 resources,   2 machines, 288 periods and  100 tasks with a search space of   10^226.
sample04   has 3 resources,   5 machines, 288 periods and  100 tasks with a search space of   10^266.
sample05   has 3 resources,   2 machines, 288 periods and  250 tasks with a search space of   10^584.
sample06   has 3 resources,   5 machines, 288 periods and  250 tasks with a search space of   10^673.
sample07   has 3 resources,   2 machines, 288 periods and 1000 tasks with a search space of  10^2388.
sample08   has 3 resources,   5 machines, 288 periods and 1000 tasks with a search space of  10^2748.
sample09   has 4 resources,  20 machines, 288 periods and 2000 tasks with a search space of  10^6668.
instance00 has 1 resources,  10 machines, 288 periods and  200 tasks with a search space of   10^595.
instance01 has 1 resources,  10 machines, 288 periods and  200 tasks with a search space of   10^599.
instance02 has 1 resources,  10 machines, 288 periods and  200 tasks with a search space of   10^599.
instance03 has 1 resources,  10 machines, 288 periods and  200 tasks with a search space of   10^591.
instance04 has 1 resources,  10 machines, 288 periods and  200 tasks with a search space of   10^590.
instance05 has 2 resources,  25 machines, 288 periods and  200 tasks with a search space of   10^667.
instance06 has 2 resources,  25 machines, 288 periods and  200 tasks with a search space of   10^660.
instance07 has 2 resources,  25 machines, 288 periods and  200 tasks with a search space of   10^662.
instance08 has 2 resources,  25 machines, 288 periods and  200 tasks with a search space of   10^651.
instance09 has 2 resources,  25 machines, 288 periods and  200 tasks with a search space of   10^659.
instance10 has 2 resources,  20 machines, 288 periods and  500 tasks with a search space of  10^1657.
instance11 has 2 resources,  20 machines, 288 periods and  500 tasks with a search space of  10^1644.
instance12 has 2 resources,  20 machines, 288 periods and  500 tasks with a search space of  10^1637.
instance13 has 2 resources,  20 machines, 288 periods and  500 tasks with a search space of  10^1659.
instance14 has 2 resources,  20 machines, 288 periods and  500 tasks with a search space of  10^1643.
instance15 has 3 resources,  40 machines, 288 periods and  500 tasks with a search space of  10^1782.
instance16 has 3 resources,  40 machines, 288 periods and  500 tasks with a search space of  10^1778.
instance17 has 3 resources,  40 machines, 288 periods and  500 tasks with a search space of  10^1764.
instance18 has 3 resources,  40 machines, 288 periods and  500 tasks with a search space of  10^1769.
instance19 has 3 resources,  40 machines, 288 periods and  500 tasks with a search space of  10^1778.
instance20 has 3 resources,  50 machines, 288 periods and 1000 tasks with a search space of  10^3689.
instance21 has 3 resources,  50 machines, 288 periods and 1000 tasks with a search space of  10^3678.
instance22 has 3 resources,  50 machines, 288 periods and 1000 tasks with a search space of  10^3706.
instance23 has 3 resources,  50 machines, 288 periods and 1000 tasks with a search space of  10^3676.
instance24 has 3 resources,  50 machines, 288 periods and 1000 tasks with a search space of  10^3681.
instance25 has 3 resources,  60 machines, 288 periods and 1000 tasks with a search space of  10^3774.
instance26 has 3 resources,  60 machines, 288 periods and 1000 tasks with a search space of  10^3737.
instance27 has 3 resources,  60 machines, 288 periods and 1000 tasks with a search space of  10^3744.
instance28 has 3 resources,  60 machines, 288 periods and 1000 tasks with a search space of  10^3731.
instance29 has 3 resources,  60 machines, 288 periods and 1000 tasks with a search space of  10^3746.
instance30 has 4 resources,  70 machines, 288 periods and 2000 tasks with a search space of  10^7718.
instance31 has 4 resources,  70 machines, 288 periods and 2000 tasks with a search space of  10^7740.
instance32 has 4 resources,  70 machines, 288 periods and 2000 tasks with a search space of  10^7686.
instance33 has 4 resources,  70 machines, 288 periods and 2000 tasks with a search space of  10^7672.
instance34 has 4 resources,  70 machines, 288 periods and 2000 tasks with a search space of  10^7695.
instance35 has 4 resources,  80 machines, 288 periods and 2000 tasks with a search space of  10^7807.
instance36 has 4 resources,  80 machines, 288 periods and 2000 tasks with a search space of  10^7814.
instance37 has 4 resources,  80 machines, 288 periods and 2000 tasks with a search space of  10^7764.
instance38 has 4 resources,  80 machines, 288 periods and 2000 tasks with a search space of  10^7736.
instance39 has 4 resources,  80 machines, 288 periods and 2000 tasks with a search space of  10^7783.
instance40 has 4 resources,  90 machines, 288 periods and 4000 tasks with a search space of 10^15976.
instance41 has 4 resources,  90 machines, 288 periods and 4000 tasks with a search space of 10^15935.
instance42 has 4 resources,  90 machines, 288 periods and 4000 tasks with a search space of 10^15887.
instance43 has 4 resources,  90 machines, 288 periods and 4000 tasks with a search space of 10^15896.
instance44 has 4 resources,  90 machines, 288 periods and 4000 tasks with a search space of 10^15885.
instance45 has 4 resources, 100 machines, 288 periods and 5000 tasks with a search space of 10^20173.
instance46 has 4 resources, 100 machines, 288 periods and 5000 tasks with a search space of 10^20132.
instance47 has 4 resources, 100 machines, 288 periods and 5000 tasks with a search space of 10^20126.
instance48 has 4 resources, 100 machines, 288 periods and 5000 tasks with a search space of 10^20110.
instance49 has 4 resources, 100 machines, 288 periods and 5000 tasks with a search space of 10^20078.

3.18. 投資資産クラスの割り当て (ポートフォリオの最適化)
リンクのコピー

各資産クラスに投資する相対数を決定します。

ハード制約:

リスクの最大値: 標準偏差合計は、標準偏差の最大値を超えてはならない。
- 標準偏差合計の計算は、Markowitz Portfolio Theory を適用した、資産クラスの相対関係を考慮する必要があります。
地域の最大値: 地域ごとに数量の最大値がある。
セクターの最大値: 各セクターに数量の最大値がある。

ソフト制約:

期待収益を最大化する。

問題の規模

de_smet_1 has 1 regions, 3 sectors and 11 asset classes with a search space of 10^4.
irrinki_1 has 2 regions, 3 sectors and 6 asset classes with a search space of 10^3.

サイズが大きいデータセットは作成/検証されていませんが、問題はないはずです。データに関する適切な情報源として、このアセット相関の Web サイトを参照してください。

3.19. 会議スケジュール
リンクのコピー

各会議を時間帯と部屋に割り当てていきます。時間帯は重複させることができます。*.xlsx ファイルに対する読み取りや書き込みが可能で、このファイルは LibreOffice または Microsof Excel で編集できます。

ハード制約:

時間帯の会議タイプ: 会議のタイプは、時間帯の会議タイプと一致する必要がある。
部屋が使用中の時間帯: 会議用の部屋は会議の時間帯で利用できなければならない。
部屋のダブルブッキング: 2 つの会議が、同じ時間に同じ会議室を使用することはできない。
講演者が空いていない時間帯: 講演者は必ず、会議の時間帯で空いていなければならない。
講演者のダブルブッキング: 同じ時間帯の 2 つの会議に同じ講演者を割り当てることができない。
汎用の時間帯および部屋のタグ
- 講演者が要求する時間帯タグ: 講演者に、必須時間帯タグが付けられている場合には、講演者の会議はそのタグが付いている時間に割り当てる必要がある。
- 講演者の禁止時間帯タグ: 公演者に、禁止時間帯タグが割り当てられている場合には、そのタグの付いた時間帯に講演者の会議をどれも割り当てることができない。
- 会議を設定する必要のある時間帯タグ: 会議に必須時間帯タグが付いている場合には、そのタグの付いた時間帯に割り当てる必要がある。
- 会議の禁止時間帯タグ: 会議に、禁止時間帯タグが割り当てられている場合には、そのタグの付いた時間帯にその会議を割り当てることができない。
- 講演者が要求する部屋のタグ: 講演者に、必須の部屋タグが付けられている場合には、講演者の会議はそのタグが付いている部屋に割り当てる必要がある。
- 講演者が禁止する部屋のタグ: 講演者に、禁止部屋のタグが付けられている場合には、講演者の会議はそのタグが付いている部屋に割り当てことができない。
- 会議を設定する必要のある部屋タグ: 会議に必須部屋タグが付いている場合には、そのタグの付いた部屋に割り当てる必要がある。
- 会議の禁止部屋タグ: 会議に、禁止部屋タグが割り当てられている場合には、そのタグの付いた部屋にその会議を割り当てることができない。
他の会議と同じ時間帯に設定しないタグ: このタグが付いている会議は、同じ時間帯に重複してスケジュールしてはいけない。
受講条件が付いた会議: 受講条件が付いた会議をすべて完了してからでないと対象の会議をスケジュールしてはいけない。

ソフト制約:

テーマの追跡競合: 同じ時間帯で、同じテーマのタグが付いた会議の数を最小限に抑える。
セクターの競合: 同じ時間帯で同じセクタータグの付いた会議の数を最小限に抑える。
コンテンツの受講者レベルのフロー違反: コンテンツタグすべてに対して、上級者用の会議の前に入門レベルの会議をスケジュールする。
受講者レベルの多様性: すべての時間帯において、異なる受講者レベルの会議数を最大限に増やす。
言語の多様性: すべての時間帯において、異なる言語の会議数を最大限を増やす。
汎用の時間帯および部屋のタグ
- 講演者が希望する時間帯タグ: 講演者に、希望の時間帯タグが付けられている場合には、講演者の会議はそのタグが付いている時間に割り当てるようにする。
- 講演者が希望しない時間帯タグ: 講演者に、希望しない時間帯タグが付けられている場合には、講演者の会議はそのタグが付いている時間に割り当てないようにする。
- 会議の希望の時間帯タグ: 会議に希望の時間帯タグが付いている場合には、そのタグの付いた時間帯に割り当てるようにする。
- 会議の設定を希望しない時間帯タグ: 会議に、希望しない時間帯タグが付いている場合には、そのタグの付いた時間帯に割り当てないようにする。
- 講演者が希望する部屋のタグ: 講演者に、希望の部屋タグが付けられている場合には、講演者の会議はそのタグが付いている部屋に割り当てるようにする。
- 講演者が希望しない部屋のタグ: 講演者に、希望しない部屋タグが付けられている場合には、講演者の会議はそのタグが付いている部屋に割り当てないようにする。
- 会議を希望の部屋タグ: 会議に希望の部屋タグが付いている場合には、そのタグの付いた部屋に割り当てるようにする。
- 会議での使用を希望しない部屋タグ: 会議に、希望しない部屋タグが付いている場合には、そのタグの付いた部屋に割り当てないようにする。
同じ日の会議: 同じテーマタグまたはコンテンツタグが付いた会議は必ず、必要最小限に日数 (理想としては同じ日) にスケジュールするようにする。

図3.14 価値提案

問題の規模

18talks-6timeslots-5rooms    has  18 talks,  6 timeslots and  5 rooms with a search space of  10^26.
36talks-12timeslots-5rooms   has  36 talks, 12 timeslots and  5 rooms with a search space of  10^64.
72talks-12timeslots-10rooms  has  72 talks, 12 timeslots and 10 rooms with a search space of 10^149.
108talks-18timeslots-10rooms has 108 talks, 18 timeslots and 10 rooms with a search space of 10^243.
216talks-18timeslots-20rooms has 216 talks, 18 timeslots and 20 rooms with a search space of 10^552.

3.20. ロックツアー
リンクのコピー

次のショーへの移動はロックバスをを使用し、空いている日のみショーをスケジュールする。

ハード制約:

必要とされるショーをすべてスケジュールする。
できるだけ多くショーをスケジュールする。

中程度の制約:

収益の機会を最大化する。
運転時間を最小限に抑える。
できるだけ早く到着する。

ソフト制約:

長時間の運転は避ける。

問題の規模

47shows の場合は、探索空間が 10^59 で、47 回ショーを行う。

3.21. 航空機乗組員のスケジューリング
リンクのコピー

パイロットと客室乗務員にフライトを割り当てます。

ハード制約:

必須スキル: フライトの割り当てにはそれぞれ、必要とされるスキルがあります。たとえば、フライト AB0001 ではパイロット 2 名と、客室乗務員 3 名が必要です。
フライトの競合: 各従業員は同じ時間に出勤できるフライトは 1 つだけにする。
2 つのフライト間での移動: 2 つのフライトの間で、従業員は到着先の空港と、出発元の空港に移動できる必要がある (たとえば、アンは 10 時にブリュッセルに到着し、15 時にアムステルダムを出発するなど)。
従業員の勤務できない日: 従業員はフライトの当日は空いていなければならない (たとえば、アンは 2 月 1 日に休暇を取っているなど)。

ソフト制約:

最初の仕事が自国から出発する。
最後の仕事が自国に到着する。
総フライト時間を従業員別に平均的に分散する。

問題の規模

175flights-7days-Europe  has 2 skills, 50 airports, 150 employees, 175 flights and  875 flight assignments with a search space of  10^1904.
700flights-28days-Europe has 2 skills, 50 airports, 150 employees, 700 flights and 3500 flight assignments with a search space of  10^7616.
875flights-7days-Europe  has 2 skills, 50 airports, 750 employees, 875 flights and 4375 flight assignments with a search space of 10^12578.
175flights-7days-US      has 2 skills, 48 airports, 150 employees, 175 flights and  875 flight assignments with a search space of  10^1904.

3.1. 例のダウンロードおよび実行
リンクのコピー

3.1.1. Red Hat Business Optimizer の例のダウンロード
リンクのコピー

3.1.2. Business Optimizer サンプルの実行
リンクのコピー

3.1.3. IDE (IntelliJ、Eclipse、または Netbeans) での Red Hat Business Optimizer サンプルの実行
リンクのコピー

3.1.4. Web のサンプルの実行
リンクのコピー

3.2. Business Optimizer サンプルの表
リンクのコピー

3.3. N クィーン
リンクのコピー

3.3.1. N クィーンのドメインモデル
リンクのコピー

3.4. クラウドバランシング
リンクのコピー

3.5. 巡回セールスマン (TSP - 巡回セールスマン問題)
リンクのコピー

3.6. ディナーパーティー
リンクのコピー

3.7. テニスクラブのスケジュール
リンクのコピー

3.8. 会議のスケジュール
リンクのコピー

3.9. コースの時間割 (ITC 2007 Track 3 - カリキュラムのスケジュール)
リンクのコピー

3.10. マシンの再割当て (Google ROADEF 2012)
リンクのコピー

3.11. 配送経路
リンクのコピー

3.11.1. 配送経路のドメインモデル
リンクのコピー

3.12. プロジェクトジョブのスケジュール
リンクのコピー

3.13. タスクの割り当て
リンクのコピー

3.14. 試験の時間割 (ITC 2007 track 1 - 試験)
リンクのコピー

3.14.1. 試験の時間割のドメインモデル
リンクのコピー

3.15. 看護師の勤務表 (INRC 2010)
リンクのコピー

3.16. 巡回トーナメント問題 (TTP)
リンクのコピー

3.17. コストを抑えるスケジュール
リンクのコピー

3.18. 投資資産クラスの割り当て (ポートフォリオの最適化)
リンクのコピー

3.19. 会議スケジュール
リンクのコピー

3.20. ロックツアー
リンクのコピー

3.21. 航空機乗組員のスケジューリング
リンクのコピー

詳細情報

試用、購入および販売

コミュニティー

Red Hat ドキュメントについて

多様性を受け入れるオープンソースの強化

会社概要

Theme

Red Hat legal and privacy links

Red Hat legal and privacy links

第3章 Red Hat Business Optimizer で提供される例

3.1. 例のダウンロードおよび実行リンクのコピーリンクがクリップボードにコピーされました!

3.1.1. Red Hat Business Optimizer の例のダウンロードリンクのコピーリンクがクリップボードにコピーされました!

3.1.2. Business Optimizer サンプルの実行リンクのコピーリンクがクリップボードにコピーされました!

3.1.3. IDE (IntelliJ、Eclipse、または Netbeans) での Red Hat Business Optimizer サンプルの実行リンクのコピーリンクがクリップボードにコピーされました!

3.1.4. Web のサンプルの実行リンクのコピーリンクがクリップボードにコピーされました!

3.2. Business Optimizer サンプルの表リンクのコピーリンクがクリップボードにコピーされました!

3.3. N クィーンリンクのコピーリンクがクリップボードにコピーされました!

3.3.1. N クィーンのドメインモデルリンクのコピーリンクがクリップボードにコピーされました!

3.4. クラウドバランシングリンクのコピーリンクがクリップボードにコピーされました!

3.5. 巡回セールスマン (TSP - 巡回セールスマン問題)リンクのコピーリンクがクリップボードにコピーされました!

3.6. ディナーパーティーリンクのコピーリンクがクリップボードにコピーされました!

3.7. テニスクラブのスケジュールリンクのコピーリンクがクリップボードにコピーされました!

3.8. 会議のスケジュールリンクのコピーリンクがクリップボードにコピーされました!

3.9. コースの時間割 (ITC 2007 Track 3 - カリキュラムのスケジュール)リンクのコピーリンクがクリップボードにコピーされました!

3.10. マシンの再割当て (Google ROADEF 2012)リンクのコピーリンクがクリップボードにコピーされました!

3.11. 配送経路リンクのコピーリンクがクリップボードにコピーされました!

3.11.1. 配送経路のドメインモデルリンクのコピーリンクがクリップボードにコピーされました!

3.12. プロジェクトジョブのスケジュールリンクのコピーリンクがクリップボードにコピーされました!

3.13. タスクの割り当てリンクのコピーリンクがクリップボードにコピーされました!

3.14. 試験の時間割 (ITC 2007 track 1 - 試験)リンクのコピーリンクがクリップボードにコピーされました!

3.14.1. 試験の時間割のドメインモデルリンクのコピーリンクがクリップボードにコピーされました!

3.15. 看護師の勤務表 (INRC 2010)リンクのコピーリンクがクリップボードにコピーされました!

3.16. 巡回トーナメント問題 (TTP)リンクのコピーリンクがクリップボードにコピーされました!

3.17. コストを抑えるスケジュールリンクのコピーリンクがクリップボードにコピーされました!

3.18. 投資資産クラスの割り当て (ポートフォリオの最適化)リンクのコピーリンクがクリップボードにコピーされました!

3.19. 会議スケジュールリンクのコピーリンクがクリップボードにコピーされました!

3.20. ロックツアーリンクのコピーリンクがクリップボードにコピーされました!

3.21. 航空機乗組員のスケジューリングリンクのコピーリンクがクリップボードにコピーされました!

詳細情報

試用、購入および販売

コミュニティー

Red Hat ドキュメントについて

多様性を受け入れるオープンソースの強化

会社概要

Theme

Red Hat legal and privacy links

Red Hat legal and privacy links

3.1. 例のダウンロードおよび実行
リンクのコピー

3.1.1. Red Hat Business Optimizer の例のダウンロード
リンクのコピー

3.1.2. Business Optimizer サンプルの実行
リンクのコピー

3.1.3. IDE (IntelliJ、Eclipse、または Netbeans) での Red Hat Business Optimizer サンプルの実行
リンクのコピー

3.1.4. Web のサンプルの実行
リンクのコピー

3.2. Business Optimizer サンプルの表
リンクのコピー

3.3. N クィーン
リンクのコピー

3.3.1. N クィーンのドメインモデル
リンクのコピー

3.4. クラウドバランシング
リンクのコピー

3.5. 巡回セールスマン (TSP - 巡回セールスマン問題)
リンクのコピー

3.6. ディナーパーティー
リンクのコピー

3.7. テニスクラブのスケジュール
リンクのコピー

3.8. 会議のスケジュール
リンクのコピー

3.9. コースの時間割 (ITC 2007 Track 3 - カリキュラムのスケジュール)
リンクのコピー

3.10. マシンの再割当て (Google ROADEF 2012)
リンクのコピー

3.11. 配送経路
リンクのコピー

3.11.1. 配送経路のドメインモデル
リンクのコピー

3.12. プロジェクトジョブのスケジュール
リンクのコピー

3.13. タスクの割り当て
リンクのコピー

3.14. 試験の時間割 (ITC 2007 track 1 - 試験)
リンクのコピー

3.14.1. 試験の時間割のドメインモデル
リンクのコピー

3.15. 看護師の勤務表 (INRC 2010)
リンクのコピー

3.16. 巡回トーナメント問題 (TTP)
リンクのコピー

3.17. コストを抑えるスケジュール
リンクのコピー

3.18. 投資資産クラスの割り当て (ポートフォリオの最適化)
リンクのコピー

3.19. 会議スケジュール
リンクのコピー

3.20. ロックツアー
リンクのコピー

3.21. 航空機乗組員のスケジューリング
リンクのコピー