最適化楽屋話#8 Excelアドインによるシフトスケジューリング

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

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

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

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

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