CPLEXサンプル sched_mmasp（複数マシン割り当てスケジューリングの問題）を読み解く

CPLEXのサンプルの sched_mmasp（[複数マシン割り当てスケジューリングの問題](https://www.ibm.com/docs/ja/icos/20.1.0?topic=library-manufacturing#section1205855439329) ）を読み解いていきます。

オリジナルのサンプルは<サンプル導入ディレクトリ>opl/examples/opl/sched_mmasp/sched_mmasp.mod
にあります。
* 実行環境
    * CPLEX 22.1.1
    * Windows 11 64bit

* サンプル
□コード

https://github.com/hkwd/230823cplexsample/blob/master/240902sched_mmasp/sched_mmasp_custom.mod

この記事でのサンプルは、オリジナルのサンプルとほぼ同じ内容ですが、日本語コメントを入れたり順序を入れ替えたり、添え字を入れ替えたりして読みやすくしています

□サンプルデータ

https://raw.githubusercontent.com/hkwd/230823cplexsample/master/240902sched_mmasp/single1.1custom.dat

# 問題

３つのジョブを2台のマシンに割り当てるスケジュールを立てます。
各ジョブは2台のマシンのいずれかに割り当てます。
1台のマシンでは同時に一つのジョブしか実行できません。
各ジョブには開始可能日と締切日があります。
各ジョブとマシンの組合せで所要時間とコストが決まっています。速いマシンはコストが高くなります。


開始可能日と締め切り日を守ったうえで、コストを最小限に抑えるスケジュールを立てます。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/2460374b-b0d3-4552-59d5-501278fe1c30.png)




## 利用データ

1. ジョブの期間制約

|Jobs|開始可能日|締切日|
|:----|:----|:----|
|1|2|16|
|2|3|13|
|3|4|21|

2.ジョブとマシンの組合せ情報(マシン1の方が速いがコストが高い)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/c51d8c5f-5ec0-029e-5a4e-3eef6f94f3e7.png)


## 決定変数
0.  各マシンに割り当てた各ジョブの開始日と終了日


## 目的関数
最小化：マシンに割り当てられたタスク＊コスト


## 制約
0.  各ジョブには開始可能日と締切日がある
0.  各ジョブはマシンのどちらかに割り当てる
0.  マシンのスケジュールは重複しない

## 問題の種類
制約プログラミング（スケジューリング）

# 解
先に解を紹介します。

## 目的関数
コストの合計:26

## 決定変数
0.  各マシンに割り当てた各ジョブの開始と終了

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/cc6f8f89-aaf8-f7e2-245c-f8ad99abe184.png)




# OPLコード解説
OPLコードの解説を行っていきます。

まずCP（制約プログラミング）のエンジンを使うことを宣言しています。
```java:制約プログラミング
using CP;
```

## 利用データ
まず基本データの定義を行っています。

```java:基本データ.mod
// マシン台数 (Packing + Manufacturing)
int nbMachines = ...;
range Machines = 1..nbMachines;

// ジョブ数
int nbJobs = ...;
range Jobs = 1..nbJobs;
```
定義はsingle1.1custom.datファイルの中で行っています。

```java:基本データ.dat
// マシン台数
nbMachines = 2;
// ジョブ数
nbJobs = 3;
```

問題ブラウザで見ると以下のようになっています。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/aaf7b74b-f907-6bdd-d23b-31da52db60bb.png)



次にジョブの期間制約の定義を行っています。


```java:ジョブの期間制約.mod
//　開始可能日
int release [Jobs] = ...;
//　締切日
int due     [Jobs] = ...;
```


```java:ジョブの期間制約.dat
// 開始可能日
release = [2,3,4];
// 締切日
due = [16, 13, 21];
```

問題ブラウザで見ると以下のようになっています。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/c37cd763-b409-4359-143c-e6b4130f7fc6.png)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/ebf68800-0226-eb10-9d13-0abb9f7473b0.png)


次にジョブとマシンの組合せ情報の定義を行っています。


```java:ジョブとマシンの組合せ情報.mod
// 所要時間
int duration[Jobs,Machines] = ...;
// コスト
int cost    [Jobs,Machines] =...;
```

```java:ジョブとマシンの組合せ情報.dat
// 所要時間
duration = [
		[10,14], 
		[6,8],
		[11,16]
			];
// コスト
cost = [
	[10,6],
	[8,5],
	[12,7]
```

問題ブラウザで見ると以下のようになっています。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/920b4ff2-8c9b-179f-8e5b-5e463a3ca39b.png)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/6ced3ab7-37e8-7000-1124-bcb0b621b893.png)


## 決定変数
次に決定変数の定義を行っています。
dvarが決定変数を意味します。

### 決定変数１：タスクについての間隔変数
まず、各タスクについての間隔変数を定義しています。
「間隔変数型」[interval](https://www.ibm.com/docs/ja/icos/20.1.0?topic=keywords-interval)は、制約プログラミングのスケジュール最適化に特化した変数です。間隔変数は、開始値、終了値、サイズなどの情報をもったクラスのような変数です。CPLEXではこのようなスケジューリングに特化した変数を用意することで、スケジュール最適化問題をわかりやすく、かつ速く解けるようにしています。
各ジョブの配列になっています。
ここでは「in]で開始可能日と締切日を指定しています。例えばジョブ1であれば2日以降16日前に終わらせる必要があります。この定義で制約1の「各ジョブには開始可能日と締切日がある」も行われています。

```java:タスク。開始可能日と締切日がある。これで制約1の「各ジョブには開始可能日と締切日がある」が制約される
dvar interval job[j in Jobs] in release[j]..due[j];
```

これらの決定変数は、求められた解では以下のようになりました。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/f080fc38-01e2-015d-8da3-0c5a417ef0ec.png)



例えば、Job2は<1,2,16,14>と決定されました。
1は存在するかどうかを示しています。
2は開始日です。16が終了日です。
14は長さをあらわしています。

interval変数は、「ガント・チャート」のビューに切り替えるとガントチャートでも確認できます。各ジョブの開始終了がわかります。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/073055e0-f74e-5d16-aefc-91f597f3d478.png)



### 決定変数２：マシンに割り当てられたタスクについての間隔変数
次にマシンに割り当てられたタスクについての間隔変数も定義しています。これは決定変数１「ジョブの間隔変数`job`」を包含する間隔変数です。後で出てくる`alternative`という関数でこの包含関係を制約します。
各ジョブ＊各マシンの2次元の配列になっています。
`Optional`があるので存在しないことがあり得ます。この`Optional`は後で出てくる`alternative`の制約をつかうために設定されています。

ここでは`size`で各ジョブの所要日数を定義している`duration`を指定しています。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/d03f5abc-ed1e-6e89-4b20-415997290bfb.png)

例えばジョブ1であれば、マシン１で作った場合は10日かかりで、マシン２で作った場合は14日かかることが定義されています。


```java:マシンに割り当てられたジョブについての間隔変数
dvar interval assignedJobToMachine[j in Jobs][m in Machines] optional size duration[j][m];
```

これらの決定変数は、求められた解では以下のようになりました。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/94fd08f9-18c8-e604-c39a-4b0873ac053a.png)




例えば、Job1は<0,0,0,0><1,2,16,14>となっています。
先頭の0、1は存在するかどうかを示しています。Machine2のみ存在する＝Machine2で作ることを意味します。
2は開始日です。16が終了日です。
14は長さをあらわしています。マシン２でつくっても16日までに作成できてかつコストが安いのでマシン2を選んだと考えられます。
この間隔変数の中にジョブ１の`job`の間隔変数が含まれています。

やはりガント・チャートで確認可能です。添え字の前半がジョブで後半がマシンをあらわしています。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/eabda74b-24f4-4855-97dc-6641b33514b9.png)




### 決定変数３：マシンに割り当てられたジョブの順序変数
次に各マシンについての順序変数[sequence](https://www.ibm.com/docs/ja/icos/20.1.0?topic=keywords-sequence)も定義しています。順序変数は、一連の間隔変数の全体の順序を表します。マシンごとに各ジョブの間隔変数の順序を決定します。


ここではマシンに割り当てられたジョブを内包しています。

```java:マシンに割り当てられたジョブの順序変数
dvar sequence machine[m in Machines] in all(j in Jobs) 
  assignedJobToMachine[j][m];

```
これらの決定変数は、求められた解では以下のようになりました。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/5e119b53-3f85-ef81-b955-84d1090ae282.png)




例えば、ジョブ3はマシン1の2番目ジョブです。
9は開始日です。20が終了日です。
サイズは11です。


やはりガント・チャートで確認可能です。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/fe99f745-c7b8-c583-67f6-02d7cb2dcd08.png)




## パラメータ指定
制約プログラミング(CP)では[パラメーター](https://www.ibm.com/docs/en/icos/20.1.0?topic=optimizer-parameters-cp)で求解が終わらなくならないように制限を指定できます。

以下のLimitが設定されていました。
FailLimit：求解探索の失敗制限回数。

```java:探索フェーズの定義
//失敗回数の設定
execute {
		cp.param.FailLimit = 5000;
}
```

## 目的関数
次に目的関数の定義を行っています。

[presenceOf](https://www.ibm.com/docs/ja/icos/20.1.0?topic=functions-presenceof)関数は間隔変数の指定された間隔変数の存在の有無を返します。
`cost[j][m] * presenceOf(assignedJobToMachine[j][m])`でコストの表と存在するジョブを掛け合わせています。


```java:総処理コストを最小限に抑える
minimize 
  sum(j in Jobs, m in Machines) cost[j][m] * presenceOf(assignedJobToMachine[j][m]);
```


図で表すと以下のようなイメージです。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/f9c13959-205c-24bb-82a0-aa8593dbeda0.png)






## 制約
次に制約の定義を行っています。
subject toの中カッコで囲みます。
```java:制約.mod
subject to{

---略----
}

```

制約１は決定変数の定義の中ですでに行われましたので、それ以外の制約を定義します。

### 制約2:各ジョブはマシンのどちらかに割り当てる

`forall(j in Jobs)`でジョブ数分との制約を作っています。
ct1_AssignOneOfTheMachneToTheJob:で制約にラベルを付けています。

[alternative関数](https://www.ibm.com/docs/ja/icos/20.1.0?topic=functions-alternative)は、間隔変数の間の択一型制約です。
２台のマシンから1つのジョブのジョブを一つ選択しています。つまり1つのジョブはどちらか1台のマシンに割り当てています。


```java:制約2:各ジョブはマシンのどちらかに割り当てる
forall(j in Jobs)
  ct1_AssignOneOfTheMachneToTheJob:
  alternative(job[j], all(m in Machines) assignedJobToMachine[j][m]);

```

以下のような制約が定義されました。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/dda51909-09c3-4c40-3f04-6048951b8c14.png)


図で表すと以下のようなイメージです。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/44aa16df-e0da-fbc6-5889-2bc8897df052.png)



### 制約3:機械のスケジュールは重複しない

`forall(m in Machines)`でマシン数分の制約を作っています。
ct2MachineSchedulesNoOverlap:で制約にラベルを付けています。

[noOverlap関数](https://www.ibm.com/docs/ja/icos/20.1.0?topic=functions-nooverlap)は、シーケンス内の間隔変数がオーバーラップするのを防止し、(オプションで) 連続した間隔変数の間の最小時間（距離）を確保するために使用されるOPL 制約です。

つまりマシン毎にジョブが重ならないようにスケジュールされます。


```java:制約3:機械のスケジュールは重複しない
forall(m in Machines)
   ct2MachineSchedulesNoOverlap:
   noOverlap(machine[m]);
```

以下のような制約が定義されました。マシン1とマシン2でそれぞれのシーケンスがかぶらないようにという制約になっています。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/10c2db77-ba71-231d-6383-a0cd7be81b06.png)



図で表すと以下のようになります。マシン１で実行されるジョブ３は、ジョブ２が終わったに開始されています。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/46115c8d-e018-c208-ff5a-4b9f90d4758c.png)




# 完成OPL

製品サンプルとほぼ同じ内容ですが、日本語コメントを入れたり順序を入れ替えたり、添え字を入れ替えたりして読みやすくしています。

```Java:sched_mmasp_custom.mod
//制約プログラミング
using CP;

// マシン台数 (Packing + Manufacturing)
int nbMachines = ...;
range Machines = 1..nbMachines;

// ジョブ数
int nbJobs = ...;
range Jobs = 1..nbJobs;

//　開始可能日
int release [Jobs] = ...;
//　締切日
int due     [Jobs] = ...;

// 所要時間
int duration[Jobs,Machines] = ...;
// コスト
int cost    [Jobs,Machines] =...;
 
//ジョブ。開始可能日と締切日がある
dvar interval job[j in Jobs] in release[j]..due[j];
//マシンに割り当てられたジョブ
dvar interval assignedJobToMachine[j in Jobs][m in Machines] optional size duration[j][m];
//マシンに割り当てられたジョブの順序
dvar sequence machine[m in Machines] in all(j in Jobs) assignedJobToMachine[j][m];

//失敗回数の設定
execute {
		cp.param.FailLimit = 5000;
}


// Minimize the total processing cost (24)
// 総処理コストを最小限に抑える（24）
minimize 
  sum(j in Jobs, m in Machines) cost[j][m] * presenceOf(assignedJobToMachine[j][m]);
subject to {
  // Each job needs one unary resource of the alternative set s (28)
  //制約2:各ジョブはマシンのどちらかに割り当てる
  forall(j in Jobs)
    ct1_AssignOneOfTheMachneToTheJob:
    alternative(job[j], all(m in Machines) assignedJobToMachine[j][m]);
  // No overlap on machines
  // 制約3:マシンのスケジュールは重複しない
  forall(m in Machines)
     ct2MachineSchedulesNoOverlap:
     noOverlap(machine[m]);
};

```

```Java:single1.1custom.dat
// マシン台数
nbMachines = 2;
// ジョブ数
nbJobs = 3;


// 開始可能日
release = [2,3,4];
// 締切日
due = [16, 13, 21];

// 所要時間
duration = [
		[10,14], 
		[6,8],
		[11,16]
			];
// コスト
cost = [
	[10,6],
	[8,5],
	[12,7]
		];
```


# おまけ1. マシンやジョブの数が増えた場合
このサンプルにはmodファイルは一つしかありませんが、複数のdatファイルが用意されていて、マシンやジョブの定義が変わった場合にも、同じモデルで最適化を試すことができます。
例えば、20のジョブと5台のマシンを定義しているsingle5.2.datで実行してみます。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/47a51087-b71e-f756-2db4-11d29259a825.png)

結果はマシン１とマシン４は割り当てられませんでしたが、20個のジョブを最低コストで実現するスケジュールが作り出されました。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/fda2b53a-66d2-ae2f-bce4-f85d946be21c.png)


![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/adde1f62-e115-114a-c1dc-0de7a400b42a.png)



# おまけ2. 制約の動きの確認
制約がどう働いているかを確認するためにあえて、一つ一つ制約をコメントアウトして結果を確認してみます。

### 「制約2:各ジョブはマシンのどちらかに割り当てる」を無効化した場合
`alternative`がなくなり、Taskとの紐づけがなくなったので、ジョブ自体を割り当てることを辞めてコストを０にしていました。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/33581fa6-85b4-a4a2-ce01-e6f014dfa353.png)


![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/328da322-ee4a-e738-fa94-5cd15f6ae3ba.png)



### 「 制約3:マシンのスケジュールは重複しない」を無効化した場合
`noOverlap`がなくなったので、全て安価なマシン2に割り当てていますが、スケジュールが重複しています。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/f8419e7d-4739-b703-2d4e-05f3bc0188f0.png)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/26bd0750-3be4-c177-0a3e-421edf7dd0ea.png)



# 参考
#### 複数マシン割り当てスケジューリングの問題 - IBM Documentation 

https://www.ibm.com/docs/ja/icos/20.1.0?topic=library-manufacturing#section1205855439329


#### CPLEXサンプルを読み解く記事一覧

https://qiita.com/spssfun2017/items/bdb85f66e5f1de6039d6