数理システム 数理最適化ブログ

最適化楽屋話#8

Numerical Optimizer 開発責任者の田辺隆人でございます。

最適化読本(の「続」の方)に書いたことですが、スケジューリングなど、実務で現れる離散最適化問題を解くようになって印象的だったのは、明確な制約を満たす答がじつは非常に多様である(ある意味、実行可能領域はとても広い)こと、そしてその中から本当に欲しい解を絞り込むのにはモデリングとアルゴリズムの高度な合わせ技が必要であることでした。実務家の方の感触に合わせるため、それこそ打ち合わせの最中にもモデルをどんどんと改変して答を絞り込んでゆく。そんなモデルづくりの「鉄火場」では、高精度の解をじっくり求めるアルゴリズムだけではなく、ヒューリスティックなアルゴリズムが活躍します。

Excelアドインのサンプルとして第二弾に選んだのはいわゆるシフトスケジューリングで 5人の一週間のスケジュールを決める話です。こちらからエクセルシート、モデルのダウンロードができます。アルゴリズムwcspの乱数シードを時刻に関連づけて毎回変化させているので、

   

などなど、多様なシフトパターンがモデルを実行するたびに現れます。実行可能解の大海原に出た感じをまずは実感いただければと思います。これらは

  • 毎日一人は誰かが夜勤をする
  • 各人週当たり夜勤は2回以下(Aは1回以下)
  • Eは他の人と組になって夜勤をする

という制約を満たす答なのですが、その中で実務家の感触として許せるものはごくごく一部なのが普通。
そういえば、なんか一部の人に日勤ばかり続くような答えが多いような気がします。たまにバランスの良い答が出たらシード値をメモしておいて「固定乱数シード」のセルに入れると再現させることができます。もちろん実際はこうしたまぐれ当たりではなく、確実にバランスの良い答を出すためにはどういう制約を加えればよいかを考えてモデルを改変してゆくのが実務的なモデルづくりの作業そのものになります。関連づけられているSIMPLEによるモデルはDiscreteVariable(離散変数)の使い方、またモデル内で Windows の時刻を取るシステム関数を呼ぶ方法の実例になっています。ぜひお試しいただければと思います。

 

田辺隆人

Numerical Optimizer 開発責任者

無料最適化セミナーのご案内
紹介資料はこちら