Zenn
🙌

[アルゴリズム解説] シフト・スケジューリング問題（バイトのシフト作成、面倒から卒業する方法）

に公開
Python
tech

どうも、mikanecoです。

みなさんバイトやお店のシフト組み、やったことありますか？
「責任者を必ず1人以上入れる」とか、「開店時には鍵を持ってる人が必要」とか、「あの2人はやらかすから絶対一緒に入れないで」みたいな細かいルールが山ほど出てきて、正直めちゃくちゃ面倒ですよね。

でも、これらの条件や制約を“数理モデル”として整理すると、自動でシフトが組めるようになるんです。今回はそんな「面倒なシフト作成を自動化するアプローチ」と「実際のコード例」まで紹介します。

1. シフト作成って何が大変なの？

まずは現実に起こる“めんどくさい”シフト作成の課題を整理します。ざっくり、以下みたいなやつです。

ケース1：責任者の配置

  • 各シフトに必ず1人以上責任者が必要。でも責任者が少ないと偏って負担が大きくなるので、バランスよく割り振りたい。

ケース2：組み合わせNG

  • 過去にトラブルがあった2人（例：松本さんと浜田さん）は同じシフトに入れないようにしたい。

ケース3：鍵を持つ人の配置

  • 開店時に“鍵”を持った人が必ず必要。もし1人しかいないなら、その人のシフト調整が特に重要。

ケース4：勤務時間の制約

  • 週○時間以上働かせたい・働かせたくない、フルタイム/パートの区分、休憩時間の確保など。いろんな時間的な制約もクリアしなきゃいけない。

これら全部を“手作業”でやるのは地獄ですが、数理モデルで整理すれば機械的に解ける問題に変わります。

2. 数理モデルってなに？どう使う？

“数理モデル”とは、現実のルールや条件を「変数」や「数式」で表すことです。

例えば…

  • 責任者を必ず1人以上入れる → 「各シフトの責任者数 >= 1」という条件を数式で書く。
  • AさんとBさんは一緒に入れない → 「AとBが同じシフトのとき、その割り当ては不可」とする。
  • 鍵を持つ人を開店時に配置 → 「開店シフトに鍵スタッフが1人以上」

こうやって全部の条件を“制約条件”として列挙し、「このルール全部守って、一番バランスのいいシフトを自動で作って！」という命令を出せるのが数理最適化の強み。

制約条件を全部並べてみる

  • 各シフトに責任者を1人以上含める
  • NG組み合わせは同じシフトにしない
  • 鍵を持つ人を開店時に入れる
  • 勤務時間の上下限を守る

これらをコード（数理モデル）に落とし込めば、あとは自動計算です。

シフト作成の基本フロー

  1. 入力データを準備（勤務可能時間、NGペア、責任者リストなど）
  2. 制約条件をすべて列挙
  3. 「なるべく希望が叶う」「バランスが良い」などの目的関数を決める
  4. 適したアルゴリズムを選ぶ（線形計画法・整数計画法など）
  5. 出力されたシフト案を微調整

3. 実際のアルゴリズムの作り方

大まかな流れはこんな感じです。

  1. データ準備

    • 従業員ごとの勤務可能時間
    • 責任者リスト
    • NG組み合わせ
    • 鍵を持つ人リスト
    • 各自の勤務時間制約

  2. 制約条件の整理

    • 例：各シフトに責任者が1人以上／NGペアは同じシフト不可／鍵持ちは開店に必須…など

  3. 目的関数を決める

    • 希望シフトを最大限叶えたい、責任者の負担を分散したい、など

  4. アルゴリズム選定＆実装

    • 線形計画法（LP）、整数計画法（IP）、遺伝的アルゴリズム（GA）など

  5. 結果を確認・微調整

    • 出力シフトをチェックし、必要なら条件やパラメータを調整

  6. さらに最適化

    • 実運用で得られた知見をもとに随時改善

4. Pythonでの実装例（Google OR-Tools）

実際にPython＋Google OR-Toolsでシフト割り当てを最適化してみます。

問題設定

  • 従業員A・B・C

  • シフトは「早番」「中番」「遅番」

  • 条件：

    • 各シフト1人ずつ
    • Aは遅番NG
    • Bは1日2回以上シフトに入らない
    • Cは早番必須

インストール

pip install ortools

コード

from ortools.sat.python import cp_model

# モデル作成\model = cp_model.CpModel()

employees = ['A', 'B', 'C']
shifts = ['early', 'mid', 'late']
assignment = {}
for e in employees:
    for s in shifts:
        assignment[(e, s)] = model.NewBoolVar(f'{e}_{s}')

# 各シフト1人
for s in shifts:
    model.Add(sum(assignment[(e, s)] for e in employees) == 1)
# Aは遅番NG
model.Add(assignment[('A', 'late')] == 0)
# 各従業員1日1回まで
for e in employees:
    model.Add(sum(assignment[(e, s)] for s in shifts) <= 1)
# Cは早番必須
model.Add(assignment[('C', 'early')] == 1)

solver = cp_model.CpSolver()
status = solver.Solve(model)

if status == cp_model.OPTIMAL:
    for s in shifts:
        for e in employees:
            if solver.Value(assignment[(e, s)]) == 1:
                print(f'{e} is assigned to {s} shift.')
else:
    print("No optimal solution found.")

結果例

C is assigned to early shift.
B is assigned to mid shift.
A is assigned to late shift.

すべての制約条件を満たした最適なシフトが一発で計算されます。

まとめ

数理モデル×最適化アルゴリズムを使えば、「責任者を均等に配置」「組み合わせNGを守る」「開店時に鍵を必ず配置」「勤務時間をバランス良く分配」など、現場の“めんどくさいシフト作成”を一気に自動化できます。

従業員やシフトの数・制約条件を増やしても、同じ手法で対応可能。ルールが増えるほど「自動化の価値」は高まります。シフト作成の面倒に悩んでる人は、ぜひこのやり方を試してみてください！

Discussion