«
»
suganuma

量子アニーリングでシフト表作成

某雑誌で量子アニーリングの記事を読み興味を持ち、これを使ったなにか良いお題がないか考えた結果、シフト表を作成しようと思い立ちました。

以下のような月のシフト表に、自動で出勤日を決定できるようにします。
0が休日で、1が出勤日とします。

フィックスターズの量子アニーリングクラウド「Fixstars Amplify」を使います。
Pythonでamplifyモジュールをインストールするだけで簡単に利用できます。

今回使うイジングマシンのエンジンは、Fixstars Amplify Annealing Engine です。これはGPUベースのアニーリングマシン（いわゆる古典コンピュータ）です。
これ以外にも、たとえば「D-Wave 2000Q」や「D-Wave Advantage」といった量子コンピュータが使えます。同じコードで設定を変えるだけで、簡単にエンジンを切り替えられます。

量子アニーリングのプログラミングは、だいたい以下のステップです。

  1. 決定変数を定義
    決定変数は2値の値を取りえます
  2. 決定変数を使い、条件を最適化関数として記述
    イジングマシンは最適化関数が最小になるような決定変数の組み合わせを自動で見つけてくれます
  3. イジングマシンを実行
    決定変数の値が確定
  4. 結果（確定した決定変数）の処理

シフト表作成で、以下の条件を課します。

  • できるだけ全員が同じ出勤数にする
  • 一日あたり二人が出勤
  • 連続６勤務以上は禁止
  • 担当者A：どの日でもOK
  • 担当者B：土日のみ出勤可
  • 担当者C：土日以外のみ出勤可
  • 担当者D：1日〜5日は休み

Google Colabノートブックを使って作業を行いました。
以下のリンクでノートブックを閲覧できます。
https://colab.research.google.com/drive/1xMYavIDCyFJoxkvzwhxIZnrUxMk4d1wA?usp=sharing

作成したシフト表が以下です。

条件を満たしたシフト表を作成することができました。

カテゴリー: Python | タグ: , , ,

«
»