はじめに
先日開催された本記事では第9回Asprovaプログラミングコンテストでは6位という好成績を収めることができました。今回はこのコンテストを通して痛感したヒューリスティックコンテストの基本について書きたいと思います。
結論は簡単なことなので先に書いておきますが、
- できることをやる
- 少しずつ改善する
ということです。
問題概要
今回の問題はShift Schedulingという問題です。細かい説明は省略しますが、以下のような工場の稼働計画に関する問題です。
- 工場では複数種類の製品を作っており、各製品は複数の設備を使用した工程を経て完成する
- 今後数週間の間に対応しなければならない注文(製品・納期が与えられている)がある
- 設備の1日の稼働時間は9パターンから選ぶことができる(9:00-12:00＋13:00-18:00など)
- パターンは各週に対して平日のパターン、休日のパターンの2種類選べる。同一週の平日同士・休日同士は同じパターンを適用する
- 選択したパターンに対して、コストが決まる
- 連続した週で平日パターン、休日パターンを変化させることは可能だが、変化させる回数には上限がある
- 作成するプログラムの目的は、納期遅延を出さずパターン変更回数上限を守った上で、コストを少なく抑えること
- ただし、プログラムには注文情報等の詳細は与えられず、限られた情報しか使用できない代わりに、所定の回数パターンを作成して、稼働率や遅延製品数などのフィードバックを得ることができる
- 与えられる情報は、設備数、週数、パターン変更回数上限、作成可能パターン回数、各設備のパターン毎のコスト
作戦の推移
この問題を見たときに、まず着目したのはクエリ回数(E)の少なさでした。50回、100回、300回の3パターンで最大でも300回しかできないので、焼きなましとかをやっている余裕はなさそうでした。
次に着目したのは、ジャッジから与えられるフィードバックの内容でした。フィードバックは以下の内容が与えられます。
- スコア(≒総コスト)
- 納期遅延製品数
- パターン変更上限違反回数
- 週・設備毎の以下の情報
- 納期遅延製品数
- 稼働率
プログラム側には注文の情報が与えられていないため、納期がどのような分布になっているかはわかりません。稼働率が与えられているので、設備毎の稼働の状況はわかりますが、納期に対して余裕があるのかどうかは納期遅延を出してみないとわかりません。
つまり多少の納期遅延がある方が得られる情報が多いわけです。そこで初めに立てた作戦は、少し納期遅延がある状態をまずは作り、その状態を少しずつ改善しながら最終的に納期遅延のない理想的な稼働パターンを決める、というものでした。
しかし、「最終的に納期遅延のない理想的な稼働パターンを決める」というのが結構難しく、どこでネックが発生しているのかわからずに遅延が残ったままになってしまうような状況が続きました。
仕方ないので、まずは余裕で納期を守れる状態を作ってから、稼働を削減させてみて、遅延が発生したら大丈夫になるまで少しずつ戻すというようなベースキャンプ的に前進する方法に変えることにしました。イメージで描けば以下のような感じです。
このコンテストの期間は1週間でしたが、最初の数日は理想方式を試みては挫折して、単純なベースキャンプ方式を作成し、また欲を出して理想方式に手を出しては挫折するという繰り返しでした。
スコアが伸び出したのはベースキャンプ方式に徹してからで、ヒューリスティックコンテストで大切な「できることをやる」「少しずつ改善する」ということをこんなに痛感したのは初めてでした。
今回言いたかったのはこのことなのですが、せっかくなので最終的にどのような解法になったかを以下書くことにします。
解法
基本的な考え方
先にも述べた通り、基本的には遅延のないパターンを少しずつ改善していき、遅延が発生したらしなくなるまで戻るというアプローチを取りました。最終解法は大きく6つのフェーズから成り立っています。
- フェーズ0：各設備の稼働量などの統計情報を取得する
- フェーズ1：設備ごとにパターンが全週一定として稼働を削減する
- フェーズ2：設備ごとにパターンが週に対して単調減少と仮定して稼働を削減する(このフェーズ以降、パターン変更上限は一旦無視)
- フェーズ3：任意の週の稼働を削減する
- フェーズ4：変更回数上限の制約を満たすよう調整
- フェーズ5：任意区間の稼働を削減する
フェーズ0：統計情報取得
テストケースの構成方法から、フル稼働すれば納期遅れが出ないことは保証されているので、各設備をフル稼働させて、フィードバックされる稼働率を元に各設備がどれだけ稼働が必要かという情報を得ることにしました。実際には、全てパターン8で実行すればほとんどのケースで遅延が出ないので全てパターン8で実行し、万一失敗した場合はパターン9で実行するようにしました。こうすることで、高確率で「全設備パターン8」はOKであることが1手でわかります。
また、2手目として(パターン9をやった場合は3手目として)、最後の2週までは無稼働、最後の2週だけフル稼働というパターンを実行させて遅延数を見ました。これにより、1注文あたりで各設備が必要とされている稼働時間の平均が得られることになります。
ただし、コンテスト中は気づかなかったのですがこれは実際は悪手だったようで、このクエリで得られる情報で得をすることよりも、特にE=50,100では1手失うデメリットの方が大きく、やる意味はあまりなかったようです(やるとしてもE=300の時のみにすべきでした)
フェーズ1：全週一定での削減
ここからは稼働の削減をしていくわけですが、削減のさせ方は各週の平日と休日のパターンをセットにして、(平日,休日)の順で(8,8)→(8,7)→(7,7)→(7,6)→(6,6)のように休日を優先して下げるようにしてみました。ただし、E=50の時にこの粒度でやると手数が足りなくなるので、使用するのは以下のようにしました。
- E=50のとき：下図の濃い赤
- E=100のとき：下図の濃い赤＋ピンク
- E=300のとき：下図の着色部すべて(フェーズ1ではパターン2まで)
このパターンを元に以下の手順でパターンを下げていきました。
- (限界未確定の)全設備の稼働を1段階下げる
- 納期遅延が出たら、遅延稼働時間等を使用して求めた評価値の悪い順に1設備ずつ元に戻す
- 納期遅延が出なくなったら、元に戻し過ぎているかもしれないので最後の1つを除いて再度稼働を1つずつ下げる(評価値的に無理そうなものはやらない。E=50の時は手数が足りなくなるので全くやらない)
- 1から繰り返す
フェーズ2: 設備ごとに単調減少として削減
次に考えたのは、多くの設備で最初は納期を守るために多くの稼動が必要かもしれないけれども徐々に稼働を緩めても間に合うようになるはずだということでした。
以下のやり方で稼働を下げていきました。
- (限界未確定の)全設備全週の稼働を1段階下げる
- 納期遅延が出たら、遅延個数や稼働率を使用して求めた評価値の最悪週(E=100,300の時はその1週手前)までの未確定週について稼働を1段階戻して確定させる
- 遅延がなくなるまで2.を繰り返す
- 遅延がなくなったら未確定の週以降で1から繰り返す
もちろん、後工程の方では最初は製品が流れて来ずに、ちょっと経ってからの方が稼動が必要なこともあるはずなので、単調減少の仮定はやや乱暴ではありますが、とりあえずやりやすくて意味がありそうなことをやってみる方が大事ということが今回の教訓です。
なおこのフェーズと次のフェーズはパターン変更上限回数違反は無視して進めることにしています（後で補正する前提）
フェーズ3: 任意の週を削減
E=50や100のケースはフェーズ2まででほとんどクエリ回数を使い果たしてしまうのですが、E=300のケースはまだまだ余裕があるので、各設備の各週が下げられないか1つずつ試して下げていくことにしました。途中で回数切れになることもあるので、以下のような工夫をしました。
- 週の稼働率と削減成功率の統計を取っておき、各設備・週ごとに削減成功率を試算
- 成功率と削減コストを元に期待値を出し、期待値の高い方から削減を実施。複数まとめた方が期待値が高い場合はまとめて実施(失敗したら1個ずつにバラして実施)
フェーズ4: パターン変更回数の調整(上限制約対応)
フェーズ2以降でパターン変更上限は無視しているので、ここで上限回数を補正します。補正をする前に、稼働率0の場合は稼働なしにできるはずなので、稼働率0にした上で上限制約を満たすように調整しました。
- 稼働率0の週の稼働をパターン1(稼働なし)とする
- パターン変更回数が上限を超えていた場合、パターンが変わる前後の区間を稼動が高い方に合わせた時に、コストの増分が少ない箇所を変更する
- 回数の上限制約が満たせるようになるまで2.を繰り返し
要は回数制限に合うように、増加コストの低いところから貪欲に稼働を上げています。
フェーズ5: 区間の稼働削減
ここからは上限制約が崩れないように、同一稼働の区間単位で下げることができないか試しています。
元々はこのフェーズは意味がないかと思っていたのですが、E=300で回数を余らせているケースがあったので、何もしないよりはちょっとでも意味があるかもしれないことをやっておこうということで実装しました。しかし想定より遥かに意味があったため、これをやる回数を残す調整も最終的にはしています。
ここでも「できることをやる」「少しずつ改善する」ことの大切さを感じました。
この改善でも、稼働率から成功率の統計を取り、期待値の高い順に実行しています。
回数配分
ここまでが全体的な流れでしたが、今回クエリの回数が3パターン、E=50,100,300とありました。少ないクエリ回数を各フェーズにどう割り振っていくかが問われます。
結果的には以下のような割り振りになりました。
- フェーズ5はEの値により手元のテストケースでチューニングして最適な回数分残すように設定
- それ以前は基本的に回数配分はせずに成り行きで実行。ただし回数が増え過ぎない工夫として以下の仕組みを入れた
- Eが少ないケースでは平日・休日の稼働パターンの組み合わせ粒度を下げた
- 稼働パターンの下限を設けた
- Eが少ないケースでは効果が薄そうな処理はスキップした
おわりに
最後に繰り返しになりますが、今回得られた教訓を書いておきます。
- できることをやる
- 少しずつ改善する
ヒューリスティック系コンテストの基本だと思いますが、今後も戒めにして取り組んでいきたいと思います。