【SRE】オンコールシフト最適化問題をClaudeで定式化しOR-ToolsとSCIPを用いて解く【数理最適化】
概要
この記事ではナーススケジューリングの亜種のような形でシステム運用におけるオンコールシフト最適化問題をClaudeで定式化します。
何故今数理最適化なのか？
数理最適化ツールを使うと本来の意味で「解く」ことができます。つまり、生成AIにぶん投げるだけでは得られない保証付きの最適値が得られるということです。
一方で、最適化の知識が無い人にとってはこれらのツールは非常に難解に見えます。
生成AIに最適化ツールを使わせ、その結果を用いることで、信頼性の高い結果を得るためのしきい値を下げることができると思っています。
今回使ったコード
基礎知識
ナーススケジューリング問題
ナーススケジューリング問題とは、数理最適化としてナースのシフト表を作成するような問題です。必ず満たすべきハード制約となるべく満たしたいが満たさなくても良いソフト制約があるのが特徴です。
ナースは24時間のシフト勤務が前提の職務ですが、システム運用におけるオンコールシフトは大抵適当な運用がされていて、昼は普通に仕事しつつ夜も起きることが求められるように思います。したがって今回は昼の時間は簡単のため無視します。
数理最適化
誤解を恐れずに言えば、制約を数式で表し、その制約を満たしながら目的の関数を最小化する枠組みで問題を解く事をいいます。
どのような制約と目的関数なら効率的に解けるのか、逆に解けないのか、どうすれば妥協した解を得られるかなどが研究されています。
OR-Tools
OR-Toolsは数理最適化の様々な問題を扱うためのGoogle製のOSSライブラリです。今回は以下の問題を解く目的で使用します。
- 混合整数線形計画問題 (Mixed Integer Linear Programming, MILP)
対抗馬としてはPuLPやPython-MIPなどがありますが、今回はスター数が多いOR-Toolsを選択しました。
SCIP
SCIPはOSSの混合整数線形計画問題ソルバーです。
ソルバーは以下のように多様なのですが、ここでは商用利用可能なオープンソースであり、OR-Toolsにも対応しているSCIPを使用します。SCIPは昔は非商用のみだったのですが、数年前にApahe License 2.0になり使いやすくなりました。
最適化ソルバー比較表 (by Claude)。
研究だとCPLEXとGurobiが多い印象があります。
定式化と実装
ナーススケジューリング
ベースはナーススケジューリングを用います。
こちらで実行すると以下のような結果が得られます。
Solving the problem...
Solved in 0.02 seconds
Solution found with objective value = 162.0
基本コスト: 112.0
最大労働日数超過ペナルティ: 12.0
連続夜勤制限違反ペナルティ: 0.0
希望シフト違反ペナルティ: 38.0
最終スケジュール:
日1 日2 日3 日4 日5 日6 日7 日8 日9 日10 日11 日12 日13 日14
看護師1 遅番 夜勤 休み 遅番 遅番 夜勤 遅番 休み 遅番 早番 遅番 遅番 遅番 遅番
看護師2 遅番 遅番 早番 夜勤 夜勤 遅番 早番 休み 早番 夜勤 休み 早番 早番 早番
看護師3 夜勤 夜勤 休み 休み 早番 早番 早番 遅番 夜勤 休み 休み 遅番 遅番 遅番
看護師4 早番 早番 夜勤 遅番 休み 遅番 早番 早番 休み 遅番 遅番 夜勤 遅番 早番
看護師5 夜勤 休み 遅番 早番 遅番 遅番 休み 遅番 遅番 早番 夜勤 休み 夜勤 休み
看護師6 休み 早番 早番 早番 休み 早番 遅番 夜勤 遅番 夜勤 遅番 夜勤 休み 夜勤
看護師7 遅番 遅番 早番 休み 遅番 休み 夜勤 遅番 早番 早番 早番 早番 早番 夜勤
看護師8 早番 遅番 遅番 早番 早番 夜勤 休み 早番 休み 遅番 早番 遅番 夜勤 遅番
看護師9 休み 早番 遅番 遅番 早番 早番 夜勤 夜勤 夜勤 休み 早番 早番 休み 早番
看護師10 早番 休み 夜勤 夜勤 夜勤 休み 遅番 早番 早番 遅番 夜勤 休み 早番 休み
看護師別統計:
看護師 総勤務日数 早番 遅番 夜勤
0 看護師1 12 1 9 2
1 看護師2 12 6 3 3
2 看護師3 10 3 4 3
3 看護師4 12 5 5 2
4 看護師5 10 2 5 3
5 看護師6 11 4 3 4
6 看護師7 12 6 4 2
7 看護師8 12 5 5 2
8 看護師9 11 6 2 3
9 看護師10 10 4 2 4
日別統計:
日付 勤務看護師数 早番 遅番 夜勤
0 日1 8 3 3 2
1 日2 8 3 3 2
2 日3 8 3 3 2
3 日4 8 3 3 2
4 日5 8 3 3 2
5 日6 8 3 3 2
6 日7 8 3 3 2
7 日8 8 3 3 2
8 日9 8 3 3 2
9 日10 8 3 3 2
10 日11 8 3 3 2
11 日12 8 3 3 2
12 日13 8 3 3 2
13 日14 8 3 3 2
実装1
ナーススケジューリングから以下の変更を加えました。
- 6ヶ月のシフト表の作成
- 早番遅番は無く、プライマリシフト、セカンダリシフト、なしの3択
- 平日と週末を考慮
- 連続しすぎるシフトはなるべく入れない
実行結果1
以下のような実行結果が得られました。祝日申請は全て通り、それなりに負荷も平準化することができましたが、祝日の稼働は3倍の差が生まれてしまいました。
エンジニア別オンコール負荷分布。
エンジニア別週末・祝日当番回数。
Solving the problem...
Solved in 4.79 seconds
Solution found with objective value = 714.0
基本コスト: 270.0
最大オンコール日数超過ペナルティ: 119.99999999999994
連続オンコール制限違反ペナルティ: 0.0
希望シフト違反ペナルティ: 0.0
週末・祝日担当バランス違反ペナルティ: 54.000000000000014
月ごとのバランス違反ペナルティ: 270.0000000000001
6ヶ月間のオンコールスケジュール:
...
===== スケジュール分析結果 =====
1. 負荷バランス分析:
当番回数: 最小=11, 最大=26, 平均=18.00, 標準偏差=3.79
バックアップ回数: 最小=10, 最大=22, 平均=18.00, 標準偏差=3.71
総負荷(当番+0.5*バックアップ): 最小=22.0, 最大=32.0, 平均=27.00, 標準偏差=3.04
2. 連続当番分析:
最大連続当番日数: 最小=2, 最大=2, 平均=2.00
3. 週末・祝日負荷分析:
週末・祝日の総数: 60
週末・祝日担当回数: 最小=3, 最大=9, 平均=5.80, 標準偏差=1.66
4. 希望シフト遵守率分析:
総希望休暇日数: 200
違反回数: 0
全体遵守率: 100.00%
エンジニア別違反回数: 最小=0, 最大=0, 平均=0.00
5. 月ごとの負荷バランス分析:
2025年5月:
当番回数: 最小=1, 最大=9, 平均=3.10, 標準偏差=2.07
バックアップ回数: 最小=1, 最大=5, 平均=3.10, 標準偏差=1.22
総負荷: 最小=3.5, 最大=11.0, 平均=4.65, 標準偏差=2.16
2025年6月:
当番回数: 最小=1, 最大=6, 平均=3.00, 標準偏差=1.61
バックアップ回数: 最小=2, 最大=5, 平均=3.00, 標準偏差=1.10
総負荷: 最小=3.0, 最大=7.5, 平均=4.50, 標準偏差=1.82
2025年7月:
当番回数: 最小=1, 最大=12, 平均=3.10, 標準偏差=3.05
バックアップ回数: 最小=1, 最大=5, 平均=3.10, 標準偏差=1.30
総負荷: 最小=3.5, 最大=13.5, 平均=4.65, 標準偏差=2.98
2025年8月:
当番回数: 最小=0, 最大=7, 平均=3.10, 標準偏差=1.81
バックアップ回数: 最小=0, 最大=7, 平均=3.10, 標準偏差=2.34
総負荷: 最小=3.5, 最大=8.0, 平均=4.65, 標準偏差=1.29
2025年9月:
当番回数: 最小=1, 最大=7, 平均=3.00, 標準偏差=1.67
バックアップ回数: 最小=0, 最大=6, 平均=3.00, 標準偏差=1.90
総負荷: 最小=3.0, 最大=10.0, 平均=4.50, 標準偏差=2.32
2025年10月:
当番回数: 最小=1, 最大=7, 平均=2.70, 標準偏差=1.79
バックアップ回数: 最小=0, 最大=6, 平均=2.70, 標準偏差=1.85
総負荷: 最小=3.0, 最大=7.5, 平均=4.05, 標準偏差=1.33
6. 最適化効率分析:
最大オンコール日数制約違反: 60
連続オンコール制約違反: 0
当番-バックアップ連続性違反: 0
分析グラフを保存しました。
実装2
あまりにも休日の格差が激しいので、ミニマックス法を用いて平等さを目的関数に追加します。休日稼働日数の最大値を最小化することで平準化します。
実行結果2
実行時間がかなり長いため数分で切ったところ以下のようになりました。結果として2倍未満の差分に抑えることができました。まだ少し不平等ですが、これくらいなら報酬制度でカバーできそうです。
エンジニア別オンコール負荷分布2。
エンジニア別週末・祝日当番回数2
SCIP Status : solving was interrupted [user interrupt]
Solving Time (sec) : 98.29
Solving Nodes : 194
Primal Bound : +6.69200000000000e+02 (19 solutions)
Dual Bound : +6.60000000000000e+02
Gap : 1.39 %
Solved in 98.29 seconds
Solution found with objective value = 669.1999999999998
週末・祝日担当バランス最大最小差: 0.5
週末・祝日担当バランス違反ペナルティ: 5.0
基本コスト: 270.0
最大オンコール日数超過ペナルティ: 120.0
連続オンコール制限違反ペナルティ: 0.0
希望シフト違反ペナルティ: 0.0
月ごとのバランス違反ペナルティ: 274.1999999999999
各エンジニアの週末・祝日シフト数:
エンジニア 0: 9.0
エンジニア 1: 8.5
エンジニア 2: 8.5
エンジニア 3: 8.5
エンジニア 4: 9.0
エンジニア 5: 9.0
エンジニア 6: 8.5
エンジニア 7: 8.5
エンジニア 8: 8.5
エンジニア 9: 9.0
6ヶ月間のオンコールスケジュール:
...
===== スケジュール分析結果 =====
1. 負荷バランス分析:
当番回数: 最小=11, 最大=27, 平均=18.00, 標準偏差=4.63
バックアップ回数: 最小=12, 最大=24, 平均=18.00, 標準偏差=4.15
総負荷(当番+0.5*バックアップ): 最小=23.0, 最大=33.5, 平均=27.00, 標準偏差=3.39
2. 連続当番分析:
最大連続当番日数: 最小=2, 最大=2, 平均=2.00
3. 週末・祝日負荷分析:
週末・祝日の総数: 60
週末・祝日担当回数: 最小=4, 最大=7, 平均=5.80, 標準偏差=0.87
4. 希望シフト遵守率分析:
総希望休暇日数: 200
違反回数: 0
全体遵守率: 100.00%
エンジニア別違反回数: 最小=0, 最大=0, 平均=0.00
5. 月ごとの負荷バランス分析:
2025年5月:
当番回数: 最小=1, 最大=5, 平均=3.10, 標準偏差=1.22
バックアップ回数: 最小=0, 最大=7, 平均=3.10, 標準偏差=2.30
総負荷: 最小=3.0, 最大=8.5, 平均=4.65, 標準偏差=1.79
2025年6月:
当番回数: 最小=1, 最大=8, 平均=3.00, 標準偏差=2.24
バックアップ回数: 最小=0, 最大=6, 平均=3.00, 標準偏差=1.73
総負荷: 最小=3.0, 最大=9.5, 平均=4.50, 標準偏差=2.40
2025年7月:
当番回数: 最小=0, 最大=5, 平均=3.10, 標準偏差=1.58
バックアップ回数: 最小=0, 最大=8, 平均=3.10, 標準偏差=3.14
総負荷: 最小=3.0, 最大=9.0, 平均=4.65, 標準偏差=1.78
2025年8月:
当番回数: 最小=0, 最大=9, 平均=3.10, 標準偏差=2.43
バックアップ回数: 最小=1, 最大=9, 平均=3.10, 標準偏差=2.12
総負荷: 最小=3.0, 最大=10.0, 平均=4.65, 標準偏差=2.17
2025年9月:
当番回数: 最小=1, 最大=8, 平均=3.00, 標準偏差=2.19
バックアップ回数: 最小=0, 最大=6, 平均=3.00, 標準偏差=2.00
総負荷: 最小=3.0, 最大=10.0, 平均=4.50, 標準偏差=2.32
2025年10月:
当番回数: 最小=1, 最大=8, 平均=2.70, 標準偏差=1.90
バックアップ回数: 最小=1, 最大=5, 平均=2.70, 標準偏差=1.10
総負荷: 最小=2.5, 最大=9.0, 平均=4.05, 標準偏差=1.74
6. 最適化効率分析:
最大オンコール日数制約違反: 60
連続オンコール制約違反: 0
当番-バックアップ連続性違反: 0
分析グラフを保存しました。
まとめ
この記事ではClaudeを使ってナーススケジューリング問題を変形したオンコールシフト最適化問題を定式化し、OR-ToolsとSCIPを用いて解きました。
ポイントは数理最適化ツールを使うと本来の意味で「解く」ことができるということです。つまり、生成AIにぶん投げるだけでは得られない保証付きの最適値が得られるということです。
皆さんも試してみてはいかがでしょうか。
注記
コードはClaudeの補助を使って作成しています。
文章は直筆です。
Discussion