CPLEXのサンプルのsched_sequence(スケジューリング問題:2 人の作業者での住宅建設)を読み解いていきます。
オリジナルのサンプルは<サンプル導入ディレクトリ>opl/examples/opl/sched_sequence/sched_sequence.mod
にあります。
-
実行環境
- CPLEX 22.1.1
- Windows 11 64bit
-
サンプル
□コード
この記事でのサンプルは、オリジナルのサンプルとほぼ同じ内容ですが、日本語コメントを入れたり順序を入れ替えたり、添え字を入れ替えたりして読みやすくしています
□サンプルデータ
問題
異なる場所に5軒の住宅を建てるという問題です。
石積み、屋根葺き、塗装などのタスクをスケジュールする必要があります。
一部のタスクは必ず他のタスクより前に実行する必要があり、これらの要件は先行タスクの制約によって表現されます。
作業員は 2 人おり、各作業員が行えるタスクは決まっています。
作業員が各住宅の間を移動するのに必要な日数を考慮する必要があります。
各住宅を建てるのにかかる日数の長さに対するコストが発生します。
さらに、各住宅毎にそれぞれ建設開始可能日と終了希望日が決まっています。終了希望日を過ぎた場合は遅延コストも発生します。
目的は、これらのコストを最小限に抑えることです。
利用データ
- 住宅の軒数: 5
- タスクに関する情報:所要日数、担当作業者、先行タスク
タスク | 所要日数 | 作業者 | 先行タスク |
---|---|---|---|
基礎(masonry) | 35 | Joe | |
大工仕事(carpentry) | 15 | Joe | 基礎 |
配管(plumbing) | 40 | Jim | 基礎 |
天井(ceiling) | 15 | Jim | 基礎 |
屋根ふき(roofing) | 5 | Joe | 大工仕事 |
塗装(painting) | 10 | Jim | 天井 |
窓(windows) | 5 | Jim | 屋根ふき |
外装(facade) | 10 | Joe | 屋根ふき、配管 |
庭(garden) | 5 | Joe | 屋根ふき、配管 |
引越(moving) | 5 | Jim | 窓、外装、庭、塗装 |
3.住宅に関する情報:最短開始可能日、 終了希望日、 終了希望日以降の1日当たりの遅延ペナルティコスト
住宅 | 最短開始可能日 | 終了希望日 | 終了希望日以降の1日当たりの遅延ペナルティコスト |
---|---|---|---|
1 | 0 | 120 | 100 |
2 | 0 | 212 | 100 |
3 | 151 | 304 | 100 |
4 | 59 | 181 | 200 |
5 | 243 | 425 | 100 |
4.住宅間の移動日数
1 | 2 | 3 | 4 | 5 | |
---|---|---|---|---|---|
1 | 0 | 1 | 2 | 3 | 4 |
2 | 1 | 0 | 1 | 2 | 3 |
3 | 2 | 1 | 0 | 1 | 2 |
4 | 3 | 2 | 1 | 0 | 1 |
5 | 4 | 3 | 2 | 1 | 0 |
決定変数
- 各住宅の各タスクの開始と終了
目的関数
各住宅の建設日数*1
+終了希望日からの遅延日数*ペナルティコストの合計が最小
制約
- 各タスクにはそれぞれ所要日数があり、連続して行う必要がある。(途中で中断できない)
- 各住宅は開始可能日以降に建設を開始する必要がある
- 各タスクは担当作業者が行う
- 各タスクの前後関係が守られている
- 一人の作業者のタスクは1時点で一つのみ
- 住宅から住宅へ作業者が移動する場合にはそれぞれの移動日数が発生する
問題の種類
制約プログラミング(スケジューリング)
解
先に解を紹介します。
目的関数
コストの合計:13,852
決定変数
- 各住宅の各タスクをいつから、いつまで行うか。(「誰が」は制約で決まっている)
OPLコード解説
OPLコードの解説を行っていきます。
利用データ
まず基本データの定義を行っています。
//住宅の軒数
int NbHouses = ...;
range Houses = 1..NbHouses;
//作業者名のセット
{string} WorkerNames = ...;
//タスク名のセット
{string} TaskNames = ...;
定義はsched_sequence_hkwd.datファイルの中で行っています。
//住宅の軒数
NbHouses = 5;
//作業者名のセット
WorkerNames = {"Joe", "Jim" };
//タスク名のセット
TaskNames = {
"masonry",
"carpentry",
"plumbing",
"ceiling",
"roofing",
"painting",
"windows",
"facade",
"garden",
"moving"
};
次にタスク関係のデータの定義を行っています。
//タスク所要日数の配列
int Duration [t in TaskNames] = ...;
//タスクに割り当てられた作業者
string Worker [t in TaskNames] = ...;
//タスクの前後関係のタプルセット
tuple Precedence {
string pre;
string post;
};
{Precedence} Precedences = ...;
//タスク所要日数の配列
Duration = [
35,
15,
40,
15,
05,
10,
05,
10,
05,
05
];
//タスクに割り当てられた作業者
Worker = #[
"masonry" : "Joe" ,
"carpentry": "Joe" ,
"plumbing" : "Jim" ,
"ceiling" : "Jim" ,
"roofing" : "Joe" ,
"painting" : "Jim" ,
"windows" : "Jim" ,
"facade" : "Joe" ,
"garden" : "Joe" ,
"moving" : "Jim"
]#;
//タスクの前後関係
Precedences = {
<"masonry", "carpentry">,
<"masonry", "plumbing">,
<"masonry", "ceiling">,
<"carpentry", "roofing">,
<"ceiling", "painting">,
<"roofing", "windows">,
<"roofing", "facade">,
<"plumbing", "facade">,
<"roofing", "garden">,
<"plumbing", "garden">,
<"windows", "moving">,
<"facade", "moving">,
<"garden", "moving">,
<"painting", "moving">
};
次に住宅関係のデータの定義を行っています。
//住宅建設の最短開始可能日
int ReleaseDate[Houses] = ...;
//住宅建設の終了希望日
int DueDate [Houses] = ...;
//終了希望日以降の1日当たりの遅延ペナルティコスト
float Weight [Houses] = ...;
//住宅建設の最短開始可能日
ReleaseDate = [ 0, 0, 151, 59, 243];
//住宅建設の終了希望日
DueDate = [120, 212, 304, 181, 425];
//終了希望日以降の1日当たりの遅延ペナルティコスト
Weight = [100.0, 100.0, 100.0, 200.0, 100.0];
また、住宅間の移動に必要な日数も定義しています。
tuple triplet { int type1; int type2; int value; };
{triplet} transitionTimes = { <i,j, ftoi(abs(i-j))> | i in Houses, j in Houses };
問題ブラウザで見ると以下のようになっています。
例えばHouse1からHouse2へ移動するには1日かかるという意味です。
決定変数
次に決定変数の定義を行っています。
dvarが決定変数を意味します。
決定変数1:各住宅各タスクについての間隔変数
まず、各住宅各タスクについての間隔変数を定義しています。
「間隔変数型」intervalは、スケジュールの制約プログラミングに特化した変数です。間隔変数は、開始値、終了値、サイズなどの情報をもったクラスのような変数です。CPLEXではこのようなスケジューリングに特化した変数を用意することで、スケジュールの制約プログラミングをわかりやすく、かつ速く解けるようにしています。
各住宅*各タスクの2次元の配列になっています。
ここでは「size]で各タスクの所要日数を指定しています。例えばmansonyであれば全住宅で共通の35日です。この定義で制約1の「各タスクにはそれぞれ所要日数があり、連続して行う必要がある」も行われています。
dvar interval itvs [h in Houses][t in TaskNames] size Duration[t];
これらの決定変数は、求められた解では以下のようになりました。
例えば、House2のmansonyは<1,138,173,35>と決定されました。
1は存在するかどうかを示しています。Optionalの場合存在しないことがあり得ます。
138は開始日です。173が終了日です。
35は長さをあらわしています。Intensityの指定がない場合は「長さ=サイズ」です(intencityが100%未満の場合、長さ>サイズになることがあります)。mansonryのサイズは35でしたので長さも35です。
interval変数は、「ガント・チャート」のビューに切り替えるとガントチャートでも確認できます。House2のmansonyが138日目に開始し、173日目で終了しています。
図で表すと以下のようになります。
決定変数2:各住宅についての間隔変数
次に各住宅についての間隔変数も定義しています。これは各住宅各タスクの間隔変数を包含する間隔変数です。後で出てくるspanという関数でこの包含関係を制約します。
これはビジネス上の決定変数の定義では定義されていなかった決定変数です。各住宅の各タスクの間隔変数itvsでも各住宅の開始日と終了日を表現できますが、住宅単位での間隔変数もあった方がわかりやすく表現できる制約や目的関数があるために定義しています。
ここでは「in」で最小開始日を住宅建設の開始可能日以降に指定し、最大終了日をINT型の最大値の半分と便宜上定義しています。
制約2の「各住宅は開始可能日以降に建設を開始する必要がある」はこの定義で指定しています。
dvar interval houses[h in Houses] in ReleaseDate[h]..(maxint div 2)-1;
これらの決定変数は、求められた解では以下のようになりました。
例えば、House2は<1,138,272,134>となっています。
1は存在するかどうかを示しています。Optionalの場合存在しないことがあり得ます。
138は開始日です。272が終了日です。
134は長さをあらわしています。
この間隔変数の中にmanosonryからmovingまでのタスクの間隔変数が含まれることになります。
決定変数3:各ワーカーについての順序変数
次に各ワーカーについての順序変数sequenceも定義しています。順序変数は、一連の間隔変数の全体の順序を表します。作業者ごとに各住宅各タスクの間隔変数の順序を決定します。
これはビジネス上の決定変数の定義では定義されていなかった決定変数です。各住宅の各タスクの間隔変数itvsだけでは作業者毎のタスクを表現できませんので、作業者関連の制約を定義するために、作業者単位での順序変数の決定変数をつくっています。
ここでは作業者毎の各住宅の各タスクを割り当てています。さらにTypesで各住宅のIDを与えています。
制約3「各タスクは担当作業者が行う」はこの順序変数自体を作業者毎に分けて定義することで行っています。
さらに後で出てくるnoOverlapという関数でこの順序変数内の間隔変数が同時には実行できないことなどを制約しています。またnoOverlap関数では、各Type(住宅)間の移動日数も定義しています。
dvar sequence workers[w in WorkerNames]
in all(h in Houses, t in TaskNames: Worker[t]==w) itvs[h][t]
types all(h in Houses, t in TaskNames: Worker[t]==w) h;
これらの決定変数は、求められた解では以下のようになりました。
例えば、House2のmansonryはJoeの8番目タスクです。House2がTypeで指定されています。
138は開始日です。173が終了日です。
サイズは35です。
図で表すと以下のようになります。
パラメータ指定
制約プログラミング(CP)ではパラメーターで求解が終わらなくならないように制限を指定できます。
元のサンプルでは以下のLimitが設定されていました。
FailLimit:求解探索の失敗制限回数。
timeLimit:求解時間制限秒。
しかしながら、FailLimitを外すと最適解が得られたのでこの例では外しています。
FailLimit:求解探索の失敗制限回数。デフォルトは無限
timeLimit:求解時間制限秒。デフォルトは無限
//失敗回数の設定
/*
execute {
cp.param.FailLimit = 30000;
}
*/
//時間制限の設定
execute{
cp.param.timeLimit=60;
}
目的関数
次に目的関数の定義を行っています。
lengthOf関数は間隔変数の長さを返します。
lengthOf(houses[h])で各住宅の建設日数分*1のコストを計算しています。
また、endOf関数は間隔変数の終了を返します。
endOf(houses[h])-DueDate[h]で各住宅建設の完了日と終了希望日の差から遅延日数を計算します。そして終了希望日より遅れていた場合はその遅延日数*Weight[h]で遅延ペナルティコストを計算しています。
各住宅についてこれらを計算した合計を最小化します。
minimize sum(h in Houses)
(lengthOf(houses[h]) + maxl(0, endOf(houses[h])-DueDate[h]) * Weight[h]);
制約
次に制約の定義を行っています。
subject toの中カッコで囲みます。
subject to{
---略----
}
制約1-3は決定変数の定義の中ですでに行われましたので、それ以外の制約を定義します。
制約4: 各タスクの前後関係が守られている
forall(h in Houses) forall(p in Precedences)で住宅数分と前後順序の制約を作っています。
ctPrecedence:で制約にラベルを付けています。
endBeforeStart関数は、間隔変数の相対位置を制限するための OPL 制約です。
forall(h in Houses)
forall(p in Precedences)
ctPrecedence:
endBeforeStart(itvs[h][p.pre], itvs[h][p.post]);
例えば住宅1のmansonryの後に住宅1のcarpentry来なければならないという制約になっています。
制約5,6:一人の作業者のタスクは1時点で一つのみ、住宅から住宅へ作業者が移動する場合にはそれぞれの移動日数が発生するという制約
forall(h in WorkerNames)で作業者数分の制約を作っています。
ctWorker:で制約にラベルを付けています。
noOverlap関数は、シーケンス内の間隔変数がオーバーラップするのを防止し、(オプションで) 連続した間隔変数の間の最小時間(距離)を確保するために使用されるOPL 制約です。これで二つの制約を記述することができます。
forall(w in WorkerNames)
ctWorker:
noOverlap(workers[w], transitionTimes);
以下のような制約が定義されました。JoeとJimでそれぞれのシーケンスがかぶらないようにという制約になっています。
また、transitionTimesは以下のように定義していました。例えば、住宅1から住宅4への移動は3日です。このように個々のタスクを場所(Type)のような概念でグループ化してそのType間の移動時間(待機時間)を簡単に定義できるのはCPLEXの強味の一つです。
結果の決定変数workersシーケンスは以下のようになっています。
例えば、Joeのタスクである住宅1のmanosonryは36日目で終わり、36日目から住宅1のcarpentryのタスクは始まっていて、間隔変数の期間がかぶらないようにしています。そして、住宅1のroofingは56日目で終わり、住宅4のmanosonryは59日目で開始になっていますので、タスク間には3日分(以上)を空けています。
制約6:家の間隔変数内にその家のタスクの間隔変数があるという制約
この制約は問題の定義にはありませんでした。しかし、決定変数housesの定義で指定した制約2の「各住宅は最短開始可能日以降に建設を開始する必要がある」を有効にするために必要なテクニカルな制約になります。また、目的関数で使っている住宅単位での終了日や期間の情報のためにも必要になっています。
span関数は間隔変数のグループの開始と終了をスパンするために使用されるOPL 制約です。houses間隔変数にmanosonryからmovingタスクの間隔変数が含まれることを意味します。
allキーワードは配列パラメーターを取る関数で配列の一部のみを使用できるようにする OPL キーワードです。ここでは各住宅毎のタスクの間隔変数itvsを集めています。
forall(h in Houses)で住宅数分の制約を作っています。
ctHouse:で制約にラベルを付けています。
forall(h in Houses)
ctHouse:
span(houses[h], all(t in TaskNames) itvs[h][t]);
以下のような制約が定義されました。
つまり、各住宅の間隔変数には各住宅用のmanosonryからmovingまでのタスクがすべて入っていることを制約しています。
図で表すと以下のようになります。
結果データ出力
最終終了日と各住宅の遅延ペナルティのコストを出力します。
ここで定義する変数は業務目的の参照専用であって、求解には用いられません。
//最終終了日
int endOfAll = max(h in Houses) endOf(houses[h]);
//遅延ペナルティコスト
float penalties[h in Houses] = maxl(0, endOf(houses[h])-DueDate[h]) * Weight[h];
execute {
writeln("endOfAll: " + endOfAll);
writeln("Penalties");
for(h in Houses){
writeln("house"+h+": "+penalties[h]);
}
}
以下の結果を得られました。
endOfAll: 425
Penalties
house1: 0
house2: 6000
house3: 4400
house4: 2800
house5: 0
完成OPL
製品サンプルとほぼ同じ内容ですが、日本語コメントを入れたり順序を入れ替えたり、添え字を入れ替えたりして読みやすくしています。
//制約プログラミング
using CP;
//住宅の軒数
int NbHouses = ...;
range Houses = 1..NbHouses;
//作業者名のセット
{string} WorkerNames = ...;
//タスク名のセット
{string} TaskNames = ...;
//タスク所要日数の配列
int Duration [t in TaskNames] = ...;
//タスクに割り当てられた作業者
string Worker [t in TaskNames] = ...;
//タスクの前後関係のタプルセット
tuple Precedence {
string pre;
string post;
};
{Precedence} Precedences = ...;
//住宅建設の最短開始可能日
int ReleaseDate[Houses] = ...;
//住宅建設の終了希望日
int DueDate [Houses] = ...;
//終了希望日以降の1日当たりの遅延ペナルティコスト
float Weight [Houses] = ...;
//住宅から住宅への移動必要日数
tuple triplet { int loc1; int loc2; int value; };
{triplet} transitionTimes = { <i,j, ftoi(abs(i-j))> | i in Houses, j in Houses };
////決定変数
//各住宅の各タスクの間隔変数。サイズの所要日数の指定がある。これで制約1の「各タスクにはそれぞれ所要日数があり、連続して行う必要がある」が制約される
dvar interval itvs [h in Houses][t in TaskNames] size Duration[t];
//各住宅の間隔変数。スタートは開始可能日以降。これで制約2の「各住宅は開始可能日以降に建設を開始する必要がある」が制約される
dvar interval houses[h in Houses] in ReleaseDate[h]..(maxint div 2)-1;
//作業者のシーケンス変数。各作業者毎に各住宅の、実行可能な各タスクを割り当てる。これで制約3「各タスクは担当作業者が行う」が制約される
dvar sequence workers[w in WorkerNames]
in all(h in Houses, t in TaskNames: Worker[t]==w) itvs[h][t]
types all(h in Houses, t in TaskNames: Worker[t]==w) h;
/*
//失敗回数の設定
execute {
cp.param.FailLimit = 30000;
}
*/
//時間制限の設定
execute{
cp.param.timeLimit=60;
}
////目的関数
//各住宅の建設日数+終了希望日からの遅延日数*ペナルティコストの合計が最小
minimize sum(h in Houses)
(lengthOf(houses[h]) + maxl(0, endOf(houses[h])-DueDate[h]) * Weight[h]);
////制約
subject to {
//制約4: 各タスクの前後関係が守られている
forall(h in Houses)
forall(p in Precedences)
ctPrecedence:
endBeforeStart(itvs[h][p.pre], itvs[h][p.post]);
//制約5,6:一人の作業者のタスクは1時点で一つのみ、住宅から住宅へ作業者が移動する場合にはそれぞれの移動日数が発生するという制約
forall(w in WorkerNames)
ctWorker:
noOverlap(workers[w], transitionTimes);
//制約7:家の間隔変数内にその家のタスクの間隔変数があるという制約
forall(h in Houses)
ctHouse:
span(houses[h], all(t in TaskNames) itvs[h][t]);
}
//結果データ出力
//最終終了日
int endOfAll = max(h in Houses) endOf(houses[h]);
//遅延ペナルティコスト
float penalties[h in Houses] = maxl(0, endOf(houses[h])-DueDate[h]) * Weight[h];
execute {
writeln("endOfAll: " + endOfAll);
writeln("Penalties");
for(h in Houses){
writeln("house"+h+": "+penalties[h]);
}
}
//住宅の軒数
NbHouses = 5;
//作業者名のセット
WorkerNames = {"Joe", "Jim" };
//タスク名のセット
TaskNames = {
"masonry",
"carpentry",
"plumbing",
"ceiling",
"roofing",
"painting",
"windows",
"facade",
"garden",
"moving"
};
//タスク所要日数の配列
Duration = [
35,
15,
40,
15,
05,
10,
05,
10,
05,
05
];
//タスクに割り当てられた作業者
Worker = #[
"masonry" : "Joe" ,
"carpentry": "Joe" ,
"plumbing" : "Jim" ,
"ceiling" : "Jim" ,
"roofing" : "Joe" ,
"painting" : "Jim" ,
"windows" : "Jim" ,
"facade" : "Joe" ,
"garden" : "Joe" ,
"moving" : "Jim"
]#;
//タスクの前後関係
Precedences = {
<"masonry", "carpentry">,
<"masonry", "plumbing">,
<"masonry", "ceiling">,
<"carpentry", "roofing">,
<"ceiling", "painting">,
<"roofing", "windows">,
<"roofing", "facade">,
<"plumbing", "facade">,
<"roofing", "garden">,
<"plumbing", "garden">,
<"windows", "moving">,
<"facade", "moving">,
<"garden", "moving">,
<"painting", "moving">
};
//住宅建設の最短開始可能日
ReleaseDate = [ 0, 0, 151, 59, 243];
//住宅建設の終了希望日
DueDate = [120, 212, 304, 181, 425];
//終了希望日以降の1日当たりの遅延ペナルティコスト
Weight = [100.0, 100.0, 100.0, 200.0, 100.0];
おまけ制約の動きの確認
制約がどう働いているかを確認するためにあえて、一つ一つ制約をコメントアウトして結果を確認してみます。
「制約4: 各タスクの前後関係が守られている」を無効化した場合
mansonryが終わる前にpulmbingが始まってしまいました。
「 制約5,6:一人の作業者のタスクは1時点で一つのみ、住宅から住宅へ作業者が移動する場合にはそれぞれの移動日数が発生するという制約」を無効化した場合
まずそもそもwokers順序変数の決定変数自体が求められなくなってしまいました。
Joeのmansonryのタスクが住宅1と住宅2で同時に行われています。また、タスクが全部で6つ並行に行われてしまっています。
「 制約6:住宅から住宅へ作業者が移動する場合にはそれぞれの移動日数が発生するという制約」を無効化した場合
制約5は活かしつつ、 transitionTimesの指定をはずして、制約6だけ外してみます。
forall(w in WorkerNames)
ctWorker:
noOverlap(workers[w]);
Joeのmansonryのタスクは1時点では一つのみになりましたが、住宅4から住宅1への移動日数が0日に
なっています。
「 制約7:家の間隔変数内にその家のタスクの間隔変数があるという制約」を無効化した場合
全てのhouses間隔変数の開始終了が同じで長さが0になっています。そのため目的変数が0になっています。
また住宅2のmansonry開始は91なのにhouse2の開始は0で、houses間隔変数とitvs間隔変数が無関係の変数になってしまったことがわかります。
参考
住宅建設問題への作業者および遷移時間の追加 - IBM Documentation
Tutorial: Getting started with Scheduling in CPLEX for Python
OPLのサンプルsched_sequence.oplと、このチュートリアルの「Chapter 3. Adding workers and transition times to the house building problem」はほぼ同じ内容のDOCplex版です。
CPLEXサンプルを読み解く記事一覧