CPLEXサンプル Staffing（人材割り当て問題、シフト表作成）を読み解く

CPLEXのサンプルの Staffing（[人材割り当て問題](https://www.ibm.com/docs/ja/icos/20.1.0?topic=library-time-tabling#usroplsamples.uss_opl_modlib.1016667__section1326724874242) ）を読み解いていきます。

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

* サンプル
□コード

https://github.com/hkwd/230823cplexsample/blob/master/241129staffing/staffing_customNonAvail2.mod

この記事でのサンプルは、オリジナルのサンプルよりデータ量をすくなくし、一部決定変数を集約してわかりやすくしています

□サンプルデータ

https://github.com/hkwd/230823cplexsample/blob/master/241129staffing/staffing_custom.dat

# 問題

飲食店のシフト表を作ります。
各営業日は朝、昼、夜の3つのシフトに分割されており、料理人、会計係の２つの仕事を４人の人員に割り当てます。月曜日から水曜日までのシフトを作ります。

- 一日のシフトが２シフトである場合、連続である必要があります。朝と夜のシフトのような間を飛ばしたシフトは不可です
- 一日の間に２シフト以上連続では働けません
- 夜のシフトで労働する人は、翌日の朝のシフトで労働しません
- 一人の人が一つのシフト内でできる仕事は料理人、会計係のどちらかのみです
- 各シフトには、料理人、会計係が最低一人は必要です
- 人員によってできる仕事が異なります。料理人、会計係両方できる人もいますし、どちらかだけできる人もいます
- 一部の人員は特定の日に労働できないことがあります

目的は、①各シフトには各仕事の割当要求人数がある。それを満たさないシフト数を最小化する、②作業者のシフトが偏らないようにすることです。


![{080A4A6A-22A7-4696-A944-FB6946C43849}.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/9631900a-2540-ad31-7b82-453082b67896.png)





## 利用データ

1. 人員関連

|人員|スキル|出勤不可|
|:----|:----|:----|
|Abe|料理、会計|水|
|Beth|会計| |
|Charles|料理| |
|David|会計| |


2.割当要求人数

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/d3e4884b-7a9b-3086-6758-f1832e94622b.png)




## 決定変数
0.  各曜日、各シフトに人員と割り当てた仕事


## 目的関数
最小化：以下の①と②の合計
①各シフトには各仕事の割当要求人数がある。それを満たさないシフト数を最小化する。満たさないシフト数＊(総シフト数+1)（ペナルティ）
②作業者のシフトが偏らないようにする。各人員に割り当てられたシフト数の最大差を最小化する


## 制約
0. 一日のシフトが２シフトである場合、連続である必要があります。朝と夜のシフトのような間を飛ばしたシフトは不可です
0. 一日の間に２シフト以上連続では働けません
0. 夜のシフトで労働する人は、翌日の朝のシフトで労働しません
0. 一人の人が一つのシフト内でできる仕事は料理人、会計係のどちらかのみです
0. 各シフトには、料理人、会計係が最低一人は必要です
0. 人員によってできる仕事が異なります。料理人、会計係両方できる人もいますし、どちらかだけできる人もいます
0. 一部の人員は特定の日に労働できないことがあります


## 問題の種類
整数計画

# 解
実はこの問題は解なしでした。
緩和解として「一日の間に２シフト以上連続では働けません」の制約を緩和して、「水曜日のCharlesが３シフトにでる」という解を返しています。

## 目的関数
①６(満たさないシフト数)＊7（ペナルティ）
②4(各人員に割り当てられたシフト数の最大差)
=46(ただし緩和解)

## 決定変数
1.各曜日、各シフトに人員と割り当てた仕事

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/6b63bf98-2a87-c51f-5f04-d9477ccec7ef.png)

2.割当要求人数を満たさないシフト

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/3d7f0772-7950-89b4-a440-050125fc48f2.png)


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


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

```java:基本データ.mod
int Totalshifts = ...; // １日あたりの総シフト数
int Nbshifts = ...;    // １日あたりに一人が働けるシフト数
range Shifts = 1..Totalshifts; 

{string} Skills = ...;     // スキル
{string} Weekdays = ...;   // 労働曜日 
{string} People = ...;     // 人員

int Req[Weekdays][Shifts][Skills] = ...;  // 各シフトの割当要求人数
```
定義はstaffing_custom.datファイルの中で行っています。

```java:基本データ.dat
Totalshifts=3;

Nbshifts=2;

// N=2; // 労働者が連続して働けるシフト数

Weekdays={Mon, Tue, Wed};

Skills= {cashier, cooker};

Req = [ 
   [ [1,1], [2,2], [1,1] ],
   [ [1,1], [2,2], [2,2] ], 
   [ [1,1], [2,2], [1,1] ]
   ];
```

Reqは問題ブラウザで見ると以下のようになっています。
![{6B764FB2-391F-4623-B643-D736573C1268}.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/f48de265-f775-6951-4ddc-80d68e88ef20.png)



次に人員関連のデータ定義を行っています。


```java:人員の定義
{string} People = ...;     // 人員      
// Data Structure
tuple shift {
  key string p;
  string w;
}

tuple PSkill {
  key string p;
  {string} s;
}

{PSkill} PeopleSkills = ...; //  各人が持つスキルのリスト 
{shift}  Unavailable = ...;  // 各人の出勤不可曜日

```


```java:人員のデータ
People= {Abe, Beth, Charles, David};

PeopleSkills = { 
 <Abe, {cooker,cashier}>, 
 <Beth, {cashier}>, 
 <Charles,{cooker}>,
 <David,{cashier}>
};

Unavailable = {<Abe, Wed>};
```

問題ブラウザで見ると以下のようになっています。
![{18E06DCB-9A4A-4E59-B474-97AD91FED86B}.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/460cb75b-271f-0b74-cff4-c4e025d99538.png)


![{3AB2A2C7-15E1-4F2A-8F42-479F5FF7EDF3}.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/803dbb9a-1550-c174-c779-4ee3921d6312.png)



次に未割当シフトに対するペナルティの定義を行っています。
出勤可能なシフト数＋１で定義されています。

```java:ペナルティの定義
int Penalty = card(Weekdays)*Nbshifts+1; // 未割当シフトに対するペナルティ
```


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

### 決定変数１：シフト割り当て
シフトの割当です。
```java:シフト割り当てを示します
dvar boolean Assign[Weekdays][Shifts][People][Skills];
```

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

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/b891130e-13da-2d65-4aaf-df25a41139ac.png)


例えば、Monの朝（１）のBethのシフトはcashierです。
データは縦持ちですが、シフトと人のクロス表で表現すると以下のようになります。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/f0f52d83-e054-2f59-8aae-d47751f83104.png)


### 決定変数２：割当要求人数を満たさないシフト
Reqで定義した割当要求人数を満たさないシフトです。

```java:割当要求人数を満たさないシフト
dvar int Unfilled[Weekdays][Shifts][Skills] in 0..maxint; 
```

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

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/ad4e015d-1bba-03b6-ba80-e6678a8df2ef.png)


例えば、Monの昼（2）の会計のシフトは割当要求を1名分満たしていません。
やはりデータは縦持ちですが、シフトとスキルのクロス表で表現すると以下のようになります。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/82dcf644-50f1-1d69-20b2-8a1fd2d04e3a.png)



### 決定変数３：各人各日の勤務の最初のシフト
各人各日の勤務の最初のシフトも定義しています。
これは業務上の問題としては定義されていなかった決定変数ですが、シフトの連続性を制約するために使われています。


```java:各人各日の勤務の最初のシフト
dvar boolean Start[Weekdays][Shifts][People];             

```
これらの決定変数は、求められた解では以下のようになりました。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/9472de11-6ea2-d715-d332-416f99fea072.png)

例えば、BethのMonの最初のシフトは朝（１）です。


## 目的関数
次に目的関数の定義を行っています。
「①各シフトには各仕事の割当要求人数がある。それを満たさないシフト数を最小化する」ので、まず決定式で割当要求人数を満たさないシフトの総数を計算します。
`Unfilled`の合計を計算しています。

```java:割当要求人数を満たさないシフトの総数
dexpr int TotUnfilled  =
  sum(w in Weekdays, s in Shifts, j in Skills) Unfilled[w][s][j];

```


図で表すと以下のようなイメージです。合計で6枠分のシフトが未割当です。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/d63250d2-1f23-9c2a-085c-39eb2e167d46.png)

次に「②作業者のシフトが偏らないようにする。各人員に割り当てられたシフト数の最大差を最小化する」を求めるために、決定式で各人のシフトの総数（PAssign）を計算し、その最大値と最小値の差（Pdiff）を算出します。



```java:各人員に割り当てられたシフト数の最大差
//作業者のシフトが偏らないようにする。各人員に割り当てられたシフト数の最大差
dexpr int PAssign[p in People] = sum(w in Weekdays, s in Shifts, j in Skills) Assign[w][s][p][j];  
dexpr int Pdiff = max(p in People) PAssign[p] - min(p in People) PAssign[p];
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/9426b416-f682-c7bf-ab2f-1e07fcae5861.png)

①と②を合わせた値を最小化します。
「①各シフトには各仕事の割当要求人数がある。それを満たさないシフト数を最小化する」を優先するので、`Penalty = card(Weekdays)*Nbshifts+1`をかけています。「②各人員に割り当てられたシフト数の最大差」は最大でも`card(Weekdays)*Nbshifts`なので、それ以上の数を`Penalty`として①にかけることで①を優先しています。
```java:各人員に割り当てられたシフト数の最大差
minimize TotUnfilled*Penalty + Pdiff;
// Note:  ペナルティは、各人員に割り当てられたシフト数の最大差よりも高いため、スケジュールは常に最初に需要を満たし、次に作業負荷のバランスをとります。

```




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

---略----
}

```

### 制約1: 一日のシフトが２シフトである場合、連続である必要があります。朝と夜のシフトのような間を飛ばしたシフトは不可です
この制約はCPLEX上のモデル上では三つの制約で実現しています。

#### 制約1-1:シフトが連続すること。シフトk中の人員の数 = kとk-1シフトの開始人員の合計数。
`forall(w in Weekdays, s in Shifts) `で曜日×シフト分との制約を作っています。
各シフトに割り当てられた人数と、そのシフトとひとつ前のシフトでシフトが始まった人数が同一であることを制約しています。
```java:制約1_1:シフトが連続すること。シフトk中の人員の数 = kとk-1シフトの開始人員の合計数。
  forall(w in Weekdays, s in Shifts)   
      ct01_1:
      sum(p in People, j in Skills) Assign[w][s][p][j] == sum(i in Shifts: s-Nbshifts+1 <= i <= s, j in People) Start[w][i][j];
```

以下のような制約が定義されました（一部）。
![{303AC1C8-04FE-4BAC-B313-66195DEBA810}.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/06c67219-6ca8-c886-9bda-450427101bca.png)

`(i in Shifts: s-Nbshifts+1 <= i <= s)`で1シフト前からの合計を求めています。

図で表すと以下のようなイメージです（月曜日分のみ）。例えば月曜の昼（２）のシフトは`Start`の朝（１）、昼（２）の合計と`Assign`の昼（２）の合計が一致することを示しています。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/685bf5f7-774c-4ceb-58bb-149b9b5d3122.png)

#### 制約1-2:ある人がシフト k で開始した場合、その人は次の nbshifts シフトで勤務可能になります。 

`forall(w in Weekdays, s in Shifts,p in People) `で曜日×シフト×人分、そして`forall(k in Shifts: s-Nbshifts+1 <= k <= s) `で一つ前のシフト分の制約を作っています。
各シフトに割り当てられた人は、そのシフトかひとつ前のシフトでシフトが始まっていることを制約しています。シフトが始まっていないのに割り当てがあることのないように制約されています。
```java:制約1_2:ある人がシフト k で開始した場合、その人は次の nbshifts シフトで勤務可能
  forall(w in Weekdays, s in Shifts,p in People) {
    // ある人がシフト k で開始した場合、その人は次の nbshifts シフトで勤務可能になります。 
    forall(k in Shifts: s-Nbshifts+1 <= k <= s) 
      ct01_2:
      sum(j in Skills) Assign[w][s][p][j] >= Start[w][k][p];
```
以下のような制約が定義されました（一部）。
![{596FB521-8462-4C71-9B17-54290B5F5CDA}.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/3dce810b-e316-2965-6aee-6bace494c877.png)


図で表すと以下のようなイメージです（一部のみを表示しています）。例えば月曜の昼（２）のBethのシフトは`Start`の朝（１）、昼（２）のいずれかで始まっていることを示しています。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/09147c3b-2a7a-6768-9c1b-672ed9978425.png)


#### 制約1-3:開始は連続できない。人がすでに開始している場合は、次の nbshifts シフトのいずれでも再度「開始」することはできません 

`forall(w in Weekdays, s in Shifts,p in People) `で曜日×シフト×人分、そして`forall(k in Shifts: s+1 <= k <= s+Nbshifts-1)`で一つ後のシフト分の制約を作っています。
一つ前の`Start`で開始したら、次の`Start`では開始ができないことを制約しています。
```java:制約1_3:ある人がシフト k で開始した場合、その人は次の nbshifts シフトで勤務可能
  forall(w in Weekdays, s in Shifts,p in People) {
    // 開始は連続できない。人がすでに開始している場合は、次の nbshifts シフトのいずれでも再度「開始」することはできません。 
    forall(k in Shifts: s+1 <= k <= s+Nbshifts-1) 
      ct01_3:
      1-Start[w][s][p] >= Start[w][k][p];
```
以下のような制約が定義されました（月曜朝分のみ）。
![{574897F6-A98A-4FAA-AF86-A0E459635F0E}.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/b171b577-f234-7be7-e266-b3c27be7efef.png)



図で表すと以下のようなイメージです（一部のみを表示しています）。
ポイントは直前の開始に`*(-1)+1`でビットを反転していることです。
例えば月曜の朝（1）のAbeの開始はなかったので、昼（２）の開始はあってもなくてもかまいません。月曜の朝（1）のBethの開始はあったので、昼（２）の開始はあってはいけません（もしあると`0>=1`になってしまいます）。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/0d2fb5bc-211c-301c-a441-6dead689253d.png)

なお、制約の以下の式は
```java
1-Start[w][s][p] >= Start[w][k][p];
```
以下のように移項して書き換えた方が理解しやすいかもしれません。連続するシフトのStartの合計が１以下になるようにという意味になります。
```java
Start[w][s][p] + Start[w][k][p] <=1;
```

### 制約２．一日の間に２シフト以上連続では働けません

`forall(w in Weekdays, p in People)`で曜日×人分の制約を作っています。

各曜日の1日分のシフト数が２以下を示しています。

```java:制約2:一日の間に２シフト以上連続では働けません
  forall(w in Weekdays, p in People) 
    ct02Shifts:      
      sum(s in Shifts, j in Skills) 
        Assign[w][s][p][j] <= Nbshifts;

```

以下のような制約が定義されました（月曜分のみ）。
![{2CCA4ECF-87E4-4FD7-82AB-E5C9FF057D5A}.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/9761687f-e37b-3837-04e4-246876955f2b.png)


図で表すと以下のようなイメージです（月曜分のみ）。
MonのBethは朝と昼のシフトで2シフトになっています。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/7178a45b-117b-7037-2598-6dab3ecae5b3.png)



### 制約３:夜のシフトで労働する人は、翌日の朝のシフトで労働しません

`forall(p in People, k in Skills)`で人員×スキル分の制約を作っています。

前日の夜（３）シフトがある場合は各人の朝（１）シフトがないようにしています。

`Totalshifts`は３なのでここでは夜（３）になっています。
`*(-1)+1`で夜のシフトをビット反転させています。これによって夜シフトがあった場合は`０`になり、朝シフトがあると`<=`が成り立たなくなり制約違反になります。夜シフトがなかった場合は`１`になるので、朝シフトがあっても`<=`が成り立ちます。

```java:制約３:夜のシフトで労働する人は、翌日の朝のシフトで労働しません。
  forall(p in People, k in Skills) {
    ct03_1:   
    Assign["Tue"][1][p][k] <= 1 - sum(j in Skills) Assign["Mon"][Totalshifts][p][j];
    ct03_2:   
    Assign["Wed"][1][p][k] <= 1 - sum(j in Skills) Assign["Tue"][Totalshifts][p][j];
  }
```

以下のような制約が定義されました（火―月分のみ）。
![{C102E89F-D6A4-4A0E-BAD4-EA46A524FAFE}.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/b35aa3ff-1b9e-0d20-1d4e-20b01afafc1e.png)


図で表すと以下のようになります火―月分のみ）。
Abeは月曜夜（３）のシフトがあるので火曜朝（１）は`0`でないといけません。
Bethは月曜夜（３）のシフトがないので火曜朝（１）は`1`でも構いません。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/6eb39c8f-2783-c919-37b1-a405dbde724b.png)


### 制約４:一人の人が一つのシフト内でできる仕事は料理人、会計係のどちらかのみです     

`forall(w in Weekdays, s in Shifts, p in People)`で曜日×シフト×人員分の制約を作っています。

スキルについて合計値をだしてそれが1以下という制約になっています。つまり料理人、会計係のどちらかが1になったら、もう一つのスキルは担当できないということになります。

```java:制約４:一人の人が一つのシフト内でできる仕事は料理人、会計係のどちらかのみです     
  forall(w in Weekdays, s in Shifts, p in People) 
    ct04Tasks:      
      sum(j in Skills) 
        Assign[w][s][p][j] <= 1;
```

以下のような制約が定義されました（一部のみ）。
![{398CDAC0-501E-4FCA-9D77-770F7AC7FB4D}.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/75d117ce-f51c-36c8-c737-5cf972e26162.png)



図で表すと以下のようになります（月分のみ）。
Abeは料理人、会計係のどちらも担当可能ですが、月曜夜（３）のシフトでは、料理人のみを担当しています。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/8d276006-db49-2662-d8bd-15a06eac4b10.png)



### 制約５:各シフトには、料理人、会計係が最低一人は必要です     

`forall(w in Weekdays, s in Shifts, j in Skills)`で曜日×シフト×スキル分の制約を作っています。

各シフトの割当要求人数の`Req`にかかわらず、全てのシフトで料理人と会計係に一人はAssignがあるようにします。


```java:制約５:各シフトには、料理人、会計係が最低一人は必要です     
  forall(w in Weekdays, s in Shifts, j in Skills) 
    ct05Skills:
      sum(p in People) Assign[w][s][p][j] >= 1;   
```

以下のような制約が定義されました。
![{94418F28-9B0C-47FF-AB85-3D358A0B7933}.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/55a80638-1fe6-05b1-5e01-c17a62a04ebb.png)



図で表すと以下のようになります(火のみ）。
火曜昼（２）の会計はBethとDavidが割り当てられているので、一人以上が割り当てられています。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/80171870-b6a4-57ee-94d7-ae0c979ab679.png)


### 制約６:人員によってできる仕事が異なります。料理人、会計係両方できる人もいますし、どちらかだけできる人もいます       

`forall(w in Weekdays, s in Shifts, t in PeopleSkills, k in Skills: k not in t.s)`で曜日×シフト×`PeopleSkills`で定義された人員×`not in`で持っていないスキル分の制約を作っています。

持っていないスキルのAssignが`0`であるという制約です。
`t.p`と`t.s`は以下の`PeopleSkills`から取得しています。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/1a1ef7ea-436b-6e42-a7e3-a56d51b3d1a0.png)


```java:制約６:人員によってできる仕事が異なります。料理人、会計係両方できる人もいますし、どちらかだけできる人もいます       
  forall(w in Weekdays, s in Shifts, t in PeopleSkills, k in Skills: k not in t.s)
    ct06:
    Assign[w][s][t.p][k] == 0; 
```

以下のような制約が定義されました（月のみ）。
![{859B1D49-A865-452C-B921-83C65A28BF74}.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/282109ac-6064-131a-e10d-6ba6e730b53e.png)




図で表すと以下のようになります(月のみ）。
Abeは料理と会計のスキルを両方持っているので制約はありません。
Bethは会計のスキルは持っていますが、料理のスキルがないので`==0`の制約があります。
この制約は全てのシフトに対して繰り返して適用されます。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/58d20213-47ad-3b84-fa46-87219d9b8312.png)


### 制約７:一部の人員は特定の日に労働できないことがあります      

`forall(<p,w> in Unavailable, s in Shifts, j in Skills)`で、`Unavailable`で定義された曜日×人員×シフト×スキル分の制約を作っています。

`Unavailable`で定義された曜日、人員のAssignが`0`であるという制約です。
`p`と`w`は以下の`Unavailable`から取得しています。つまりAbeは水曜に出勤できません。
![{71F939AB-AAC1-466C-B7A6-2B0E8FC390BC}.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/37084bb2-5cd0-ac4b-a457-389bb2301161.png)


```java:制約７:一部の人員は特定の曜日に労働できないことがあります      
  forall(<p,w> in Unavailable, s in Shifts, j in Skills)
    ct07:
    Assign[w][s][p][j] == 0;
```

以下のような制約が定義されました。
![{5C9EA13B-EB3A-42F1-AA7A-58A31CA2B502}.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/23802daf-3a06-2926-1c38-abec17a1d971.png)




図で表すと以下のようになります。
Abeの水曜のすべてのシフトに`==0`の制約があります。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/cadb2a1f-90ca-cc45-8c6a-efa175951362.png)

### 制約８:各シフトにおいて、あるタイプのタスクに割り当てられた人数 + 空いているスロット >= そのタイプの必要な人数 （必要な人数を満たしてなくてもよい ）

この制約は問題の定義にはありませんでした。未割当の人数の決定変数である`Unfilled`に値をいれるための制約です。

`forall(w in Weekdays, s in Shifts, j in Skills)`で、曜日×シフト×スキル分の制約を作っています。

`各シフトにアサインされた人数+未割当の人数＞＝割当要求人数`なので、割り当て人数に満たない場合に`Unfilled`へ値が入ります。さらに`Unfilled`は目的関数でMinimizeされているので、基本的には`割当要求人数-各シフトにアサインされた人数=未割当の人数`が入ることになります。
ただし、`Unfilled`は非負で、`＞＝`の制約なので、割当要求人数よりもアサイン人数を多くすることもこの制約は許容しています。あまりシフトに入っていない人がいる場合には、シフトの平準化の目的関数のために割当要求人数よりも多くの人員をアサインをする可能性があります。


```java:制約８:各シフトにおいて、あるタイプのタスクに割り当てられた人数 + 空いているスロット >= そのタイプの必要な人数 （必要な人数を満たしてなくてもよい ）
  forall(w in Weekdays, s in Shifts, j in Skills)
    ct08Unfilled:    
      sum(p in People) 
        Assign[w][s][p][j] + Unfilled[w][s][j] >= Req[w][s][j];
```

以下のような制約が定義されました。
![{5C9EA13B-EB3A-42F1-AA7A-58A31CA2B502}.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/23802daf-3a06-2926-1c38-abec17a1d971.png)




図で表すと以下のようになります。
月曜昼（２）の会計は`Req`では`2`人ですが、Beth`1`人しか割り当てられていないので`Unfilled`が`1`人になっています。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/fd59a0b3-d16a-8f0d-0031-ee570fb2df41.png)


# 完成OPL

製品サンプルとほぼ同じ内容ですが、日本語コメントを入れたり順序を入れ替えたり、添え字を入れ替えたりして読みやすくしています。またオリジナルのサンプルには、PersonnelやAvailという決定変数がありましたが、結局はAssignで表現できていそうだったので、割愛しています。

```Java:staffing_customNonAvail2.mod
//**************************** Data **************************************
int Totalshifts = ...; // １日あたりの総シフト数
int Nbshifts = ...;    // １日あたりに一人が働けるシフト数
range Shifts = 1..Totalshifts; 

{string} Skills = ...;     // スキル
{string} Weekdays = ...;   // 労働曜日 


int Req[Weekdays][Shifts][Skills] = ...;  // 各シフトの割当要求人数
          
{string} People = ...;     // 人員       
// Data Structure
tuple shift {
  key string p;
  string w;
}

tuple PSkill {
  key string p;
  {string} s;
}

{PSkill} PeopleSkills = ...; //  各人が持つスキルのリスト 
{shift}  Unavailable = ...;  // 各人の出勤不可曜日

int Penalty = card(Weekdays)*Nbshifts+1; // 未割当シフトに対するペナルティ

//********************************* 決定変数 **********************************
        
dvar boolean Assign[Weekdays][Shifts][People][Skills];   // シフト割り当てを示します
dvar int Unfilled[Weekdays][Shifts][Skills] in 0..maxint;  // 割当要求人数を満たさないシフト
dvar boolean Start[Weekdays][Shifts][People];             // 各人各日の勤務の最初のシフト



/************************************* Model *********************************/
// the total # of slots unfilled in a week
// 割当要求人数を満たさないシフトの総数
dexpr int TotUnfilled  =
  sum(w in Weekdays, s in Shifts, j in Skills) Unfilled[w][s][j];

//作業者のシフトが偏らないようにする。各人員に割り当てられたシフト数の最大差
dexpr int PAssign[p in People] = sum(w in Weekdays, s in Shifts, j in Skills) Assign[w][s][p][j];  
dexpr int Pdiff = max(p in People) PAssign[p] - min(p in People) PAssign[p];

minimize TotUnfilled*Penalty + Pdiff;
// Note:  ペナルティは、各人員に割り当てられたシフト数の最大差よりも高いため、スケジュールは常に最初に需要を満たし、次に作業負荷のバランスをとります。

subject to {
   
  // 制約１: 一日のシフトが２シフトである場合、連続である必要があります。朝と夜のシフトのような間を飛ばしたシフトは不可です
  // シフトが連続すること。シフトk中の人員の数 = kとk-1シフトの開始人員の合計数。
  forall(w in Weekdays, s in Shifts)   
      ct01_1:
      sum(p in People, j in Skills) Assign[w][s][p][j] == sum(i in Shifts: s-Nbshifts+1 <= i <= s, j in People) Start[w][i][j];
               
  forall(w in Weekdays, s in Shifts,p in People) {
    // ある人がシフト k で開始した場合、その人は次の nbshifts シフトで勤務可能になります。 
    forall(k in Shifts: s-Nbshifts+1 <= k <= s) 
      ct01_2:
      sum(j in Skills) Assign[w][s][p][j] >= Start[w][k][p];
    // 開始は連続できない。人がすでに開始している場合は、次の nbshifts シフトのいずれでも再度「開始」することはできません。 
    forall(k in Shifts: s+1 <= k <= s+Nbshifts-1) 
      ct01_3:
      1-Start[w][s][p] >= Start[w][k][p];
  }
   
    
    
  // In each shift,  # of people assigned to a type of task +
  //   unfilled slot >= # of people of that type required
  // 制約８:各シフトにおいて、あるタイプのタスクに割り当てられた人数 + 空いているスロット >= そのタイプの必要な人数 （必要な人数を満たしてなくてもよい ）
  forall(w in Weekdays, s in Shifts, j in Skills)
    ct08Unfilled:    
      sum(p in People) 
        Assign[w][s][p][j] + Unfilled[w][s][j] >= Req[w][s][j];

  // 制約６:人員によってできる仕事が異なります。料理人、会計係両方できる人もいますし、どちらかだけできる人もいます  
  forall(w in Weekdays, s in Shifts, t in PeopleSkills, k in Skills: k not in t.s)
    ct06:
    Assign[w][s][t.p][k] == 0;
        
  // 制約２:一日の間に２シフト以上連続では働けません
  forall(w in Weekdays, p in People) 
    ct02Shifts:      
      sum(s in Shifts, j in Skills) 
        Assign[w][s][p][j] <= Nbshifts;
        
  // 制約７:一部の人員は特定の曜日に労働できないことがあります
  forall(<p,w> in Unavailable, s in Shifts, j in Skills)
    ct07:
    Assign[w][s][p][j] == 0;
  
  // Each person can take only one task in each shift     
  // 制約４:一人の人が一つのシフト内でできる仕事は料理人、会計係のどちらかのみです     
  forall(w in Weekdays, s in Shifts, p in People) 
    ct04Tasks:      
      sum(j in Skills) 
        Assign[w][s][p][j] <= 1;
 
  // If a person is on a night shift, he cannot be assigned to the morning
  //  shift the next day
  // 制約３:夜のシフトで労働する人は、翌日の朝のシフトで労働しません
  forall(p in People, k in Skills) {
    ct03_1:   
    Assign["Tue"][1][p][k]+ sum(j in Skills) Assign["Mon"][Totalshifts][p][j] <= 1 ;
    // Assign["Tue"][1][p][k] <= 1 - sum(j in Skills) Assign["Mon"][Totalshifts][p][j];
    ct03_2:   
    Assign["Wed"][1][p][k] <= 1 - sum(j in Skills) Assign["Tue"][Totalshifts][p][j];
  }
  
  //Each shift has at least a cook, a cleaner and a cashier
  //制約５:各シフトには、料理人、会計係が最低一人は必要です
  forall(w in Weekdays, s in Shifts, j in Skills) 
    ct05Skills:
      sum(p in People) Assign[w][s][p][j] >= 1;     
}
```

データはわかりやすくするためにスタッフ数やシフト数をオリジナルのサンプルよりも減らして小さくしています。

```Java:stuffing.custom.dat
// １日あたりの総シフト数
Totalshifts=3;
// １日あたりに一人が働けるシフト数
Nbshifts=2;

// N=2; // 労働者が連続して働けるシフト数
// 労働曜日
Weekdays={Mon, Tue, Wed};
// スキル
Skills= {cashier, cooker};


// 各シフトに必要なスキルタイプの人数
Req = [ 
   [ [1,1], [2,2], [1,1] ],
   [ [1,1], [2,2], [2,2] ], 
   [ [1,1], [2,2], [1,1] ]
   ];

//Shifts= { 8to12, 12to4, 4to8};
// 人員 
People= {Abe, Beth, Charles, David};
// 各人が持つスキルのリスト
PeopleSkills = { 
 <Abe, {cooker,cashier}>, 
 <Beth, {cashier}>, 
 <Charles,{cooker}>,
 <David,{cashier}>
};
// 各人の出勤不可曜日
Unavailable = {<Abe, Wed>};
//Unavailable = {};

```

# 実行
## 緩和解
実はこの問題は実行可能解がありません（もともとのサンプルは実行可能ですが、簡単にするためにStaffの数などを減らしたため実行可能解がなくなっています）。そのため出てきた結果は、制約が一部緩和された緩和解になっています。

`緩和`タブを開くと制約２に抵触していて、水曜日のCharlesが2シフト以上アサインした緩和解になっていることがわかります。クリックすると対象となっている制約のOPLコードが開きます。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/51197071-0c11-6dda-71c6-388ed6f57e78.png)

制約２を見てみるとスラックが`-1`になっていて制約違反をしていることがわかります。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/9846ba2d-7ef9-4e90-4944-c79e11cf52d6.png)

`Assign`を確認すると確かにCharlesは朝昼夜の3シフトにアサインされています。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/ee7861db-8f2f-be69-1d63-365e593a5712.png)

## 競合の解決
CPLEXが出してきた緩和解を受け入れられない場合は、別の制約を緩めるか、データを修正していきます。
`競合`タブを開くと競合した制約が表示されます。クリックすると対象となっている制約のOPLコードが開きます。

複数の競合した制約がありますが、ここでは、制約７で競合が起きていて、Abeが水曜日に休まなければ、競合が起きないことに注目してみます。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/2ec4e84d-0b2f-9a3c-598e-18e3098c4c7b.png)

では、ここではデータを修正して、Abeが水曜に休むというデータ`Unavailable = {<Abe, Wed>};`を削除し`Unavailable = {};`にしてみます。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/cd8f8acf-4632-8931-b7d1-8e4224d62ca3.png)

再度求解すると、今度は競合がなくなり、実行可能解、最適解が得られました。
Abeが水曜日に出勤していることがわかります。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/917bbf63-51f9-cbf4-f5d2-3e1db1e86c5d.png)

このように競合した制約を確認し、制約を緩和したり、データを修正することで、実行可能解を探していくことができます。

# おまけ. スタッフや曜日の数が増えた場合
この元々のサンプルのstaffing.datファイルでは、スタッフが8名、月ー金までの曜日が定義されています。
このdatファイルで実行してみた結果が以下です。8名のスタッフのシフトが作成されています。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/223763/0cd9bb4c-d4a8-2cd9-b87e-210d5188409a.png)




# 参考
#### 人材割り当て問題 - IBM Documentation 
https://www.ibm.com/docs/ja/icos/20.1.0?topic=library-time-tabling#usroplsamples.uss_opl_modlib.1016667__section1326724874242

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

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