top of page

シフトスケジューリング問題を量子アニーリングで解決

  • 執筆者の写真: Yuichiro Minato
    Yuichiro Minato
  • 2024年12月9日
  • 読了時間: 3分

今回のブログでは、シフトスケジューリング問題を量子アニーリングを活用して解決する方法をご紹介します。量子アニーリングは複雑な組み合わせ最適化問題を効率的に解決する手法で、PythonライブラリのTYTANを使って実装を行います。初心者の方にも分かりやすく、目的や課題を解説します！


1. シフトスケジューリング問題とは？

シフトスケジューリング問題は、必要な作業量（人数や工数）に対して、従業員を効率的に配置する問題です。この問題では以下のことを目指します：

  • 必要な作業量を満たすために、適切な人数を割り当てる。

  • 各従業員の希望を考慮し、シフトの満足度を高める。


2. 問題の設定

以下のような条件で問題を設定しました：


  1. 必要作業量6つの時間帯において、必要な人数が以下のように設定されています：

    必要人数: [3, 3, 5, 5, 4, 4]

  2. 従業員のシフト希望10人の従業員が、各時間帯で働けるかどうかを次のような行列で表しました。

    シフト希望表: [[2, 2, 2, 2, 0, 0], # 従業員0の希望 [0, 0, 0, 1, 1, 1], # 従業員1の希望 ... [0, 0, 1, 1, 1, 1]] # 従業員9の希望

    • 値が大きいほど、その時間帯での従業員の希望度が高いことを意味します。

  3. 目的

    • 必要人数を満たしつつ、シフト希望をできるだけ尊重する。


3. 使用するライブラリ：TYTAN

TYTANは、量子アニーリングをPythonで扱うためのライブラリです。このライブラリを使うと、複雑な最適化問題をQUBO（Quadratic Unconstrained Binary Optimization）形式で定式化し、効率的に解くことができます。


4. コードの解説

以下に、実際のコードの重要な部分を解説します。


(1) 量子ビットの設定

従業員10人を量子ビットで表します。1人がシフトに入る場合、そのビットは1になります。

q = symbols_list([10], 'q{}')

(2) コスト条件の設定

全員がシフトに入ることは現実的ではありません。そのため、コスト条件を設定し、無駄な割り当てを減らします。

Hcost = 0
Hcost += (q[0] + q[1] + ... + q[9] - 0)**2

(3) 制約条件の設定

各時間帯の必要人数を満たすように制約条件を設定します。

Hconst = 0
for j in range(T):
    Hconst += (sum(shift[i][j] * q[i] for i in range(N)) - req[j])**2

(4) 全体のハミルトニアンを定義

コスト条件と制約条件を合成し、問題全体を定式化します。

H = Hconst + 0.1 * Hcost

(5) サンプリング

TYTANのSASamplerを使い、最適な割り当てを探索します。

solver = sampler.SASampler()
result = solver.run(qubo)

(6) 結果の確認

サンプル結果を確認し、各従業員のシフト状況を出力します。

for r in result:
    arr, subs = Auto_array(r[0]).get_ndarray('q{}_{}')
    print(arr)

5. 結果の例

サンプル実行結果を確認してみましょう。

最適なシフト割り当て

  • 従業員0: シフトに入らない

  • 従業員1: 時間帯3, 4, 5に割り当て

  • 従業員2: 時間帯1, 2に割り当て


    ...

各時間帯の割り当て状況

  • 時間帯1: 必要人数3 -> 割り当て3人 (条件クリア)

  • 時間帯2: 必要人数3 -> 割り当て3人 (条件クリア)


    ...


6. まとめ

今回のシフトスケジューリング問題では、量子アニーリングを使い効率的に従業員を割り当てる方法を紹介しました。この方法を応用すれば、実際の職場でも従業員の希望を尊重しつつ、必要な作業量を満たすスケジュールを作成できます。

TYTANライブラリは、こうした最適化問題を簡単に定式化し解決できる便利なツールです。初心者の方もぜひチャレンジしてみてください！

 
 
 

Comments

bottom of page