LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@s-kajiokain株式会社アイエンター

QUBOで解くシフトスケジューリング 2（実装編）

Last updated at Posted at 2025-10-03

本記事では前回の続きとして、実際の疑似アニーリングのプログラム実装と実験を紹介する。
基本的な疑似アニーリングの仕組みは数独の記事で紹介したため割愛する。
※本記事にはAIで生成したコードが含まれます

3. 実装の流れ

実装の大きなステップは次の通り。

3.1 パラメータ設定

  • 従業員数、日数、シフト種別、必要人数などを定義する
    従業員5人・7日間・3シフトを想定
【コード】ShiftScheduler クラスの実装 
   class ShiftScheduler:
    def __init__(self, num_employees=5, num_days=7):
        """
        シフトスケジューリング問題のクラス
        
        Parameters:
        - num_employees: 従業員数
        - num_days: スケジュール期間（日数）
        """
        self.num_employees = num_employees
        self.num_days = num_days
        self.shift_types = ["Morning", "Evening", "Night"]  # 朝、夕、夜
        self.num_shifts = len(self.shift_types)
        
        # 従業員名
        self.employees = [f"Employee_{i+1}" for i in range(num_employees)]
        
        # 各シフトの必要人数（最低要求）
        self.min_required = {
            "Morning": 2,  # 朝シフトは最低2人
            "Evening": 2,  # 夕シフトは最低2人  
            "Night": 1     # 夜シフトは最低1人
        }
        
        # 従業員ごとの最大勤務日数
        self.max_work_days = 5

3.2 制約の追加

制約をQUBOのペナルティ項に変換する。本記事では以下の制約を実装した。

  • 各シフトの最低人数を満たす（必須）
  • 1人1日1シフトまで（必須）
  • 連続夜勤の禁止（推奨）
  • 最大勤務日数の制限（推奨）
    さらに、希望シフトが満たされた場合に報酬を与える項を追加している。
【コード】制約 
    def build_shift_bqm(self, preferences=None, 
                       penalty_understaffed=10.0,    # 人員不足ペナルティ
                       penalty_overwork=5.0,         # 過労ペナルティ
                       penalty_consecutive=3.0,      # 連続勤務ペナルティ
                       reward_preference=2.0):       # 希望シフト報酬
        """
        シフトスケジューリング問題のBQMを構築
        """
        Q = defaultdict(float)
        offset = 0.0
        
        if preferences is None:
            preferences = self.generate_sample_preferences()
        
        # --- 制約1: 各シフトの最低人員確保 ---
        for day in range(self.num_days):
            for shift_idx, shift_name in enumerate(self.shift_types):
                min_req = self.min_required[shift_name]
                
                # 各シフトに配属される人数をカウント
                shift_vars = [self.variable_key(emp_idx, day, shift_idx) 
                             for emp_idx in range(self.num_employees)]
                
                # (min_req - sum(x_i))^2 を最小化（人員不足を避ける）
                offset += penalty_understaffed * (min_req ** 2)
                
                # 線形項: -2 * min_req * sum(x_i)
                for var in shift_vars:
                    Q[(var, var)] += -2.0 * penalty_understaffed * min_req
                
                # 二次項: sum(x_i * x_j)
                for i, var1 in enumerate(shift_vars):
                    Q[(var1, var1)] += penalty_understaffed
                    for j, var2 in enumerate(shift_vars):
                        if i < j:
                            Q[(var1, var2)] += 2.0 * penalty_understaffed
        
        # --- 制約2: 従業員の過労防止（最大勤務日数制限）---
        for emp_idx in range(self.num_employees):
            work_vars = []
            for day in range(self.num_days):
                for shift_idx in range(self.num_shifts):
                    work_vars.append(self.variable_key(emp_idx, day, shift_idx))
            
            # (sum(x_i) - max_work_days)^2 を最小化（ただし、超過分のみペナルティ）
            # 簡略化: sum(x_i) が max_work_days を超えないように制約
            for i, var1 in enumerate(work_vars):
                for j, var2 in enumerate(work_vars):
                    if i < j:
                        Q[(var1, var2)] += penalty_overwork
        
        # --- 制約3: 同一日に複数シフト禁止 ---
        for emp_idx in range(self.num_employees):
            for day in range(self.num_days):
                day_vars = [self.variable_key(emp_idx, day, shift_idx) 
                           for shift_idx in range(self.num_shifts)]
                
                # 1日1シフトまで: (sum(x_i))^2 - sum(x_i) を最小化
                for i, var1 in enumerate(day_vars):
                    Q[(var1, var1)] += -penalty_overwork
                    for j, var2 in enumerate(day_vars):
                        if i < j:
                            Q[(var1, var2)] += 2.0 * penalty_overwork
        
        # --- 制約4: 連続夜勤の制限 ---
        for emp_idx in range(self.num_employees):
            for day in range(self.num_days - 1):
                night_today = self.variable_key(emp_idx, day, 2)  # 夜シフト = index 2
                night_tomorrow = self.variable_key(emp_idx, day + 1, 2)
                
                # 連続夜勤を避ける: x_i * x_{i+1} にペナルティ
                Q[(night_today, night_tomorrow)] += penalty_consecutive
        
        # --- 目的: 従業員の希望を満たす ---
        for emp_idx, emp_name in enumerate(self.employees):
            if emp_name in preferences:
                for day, shift_idx in preferences[emp_name]:
                    var = self.variable_key(emp_idx, day, shift_idx)
                    Q[(var, var)] += -reward_preference  # 希望シフトには負のバイアス
        
        # BQM作成
        bqm = dimod.BinaryQuadraticModel.from_qubo(dict(Q), offset=offset)
        return bqm, preferences
  • 1.2節 の二値変数 $x_{e,d,s}$ を dimod.Binary で作成
bqm = dimod.BinaryQuadraticModel.from_qubo(dict(Q), offset=offset)

3.3 OpenJijでサンプリング

  • samplerで解を探索
【コード】OpenJijでサンプリング 
    def solve_shift_schedule(self, preferences=None, num_reads=500, sampler_type="sqa"):
        """
        シフトスケジュールを最適化
        """
        bqm, used_preferences = self.build_shift_bqm(preferences)
        
        if sampler_type == "sqa":
            sampler = oj.SQASampler()
        else:
            sampler = oj.SASampler()
        
        batch_size = min(50, num_reads)
        all_samples = None
        
        for i in tqdm(range(0, num_reads, batch_size), desc="Optimizing Schedule"):
            current_batch = min(batch_size, num_reads - i)
            sampleset = sampler.sample(bqm, num_reads=current_batch)
            if all_samples is None:
                all_samples = sampleset
            else:
                all_samples = dimod.concatenate([all_samples, sampleset])
        
        best_solution = all_samples.first.sample
        return self.decode_solution(best_solution), all_samples.first.energy, used_preferences
    
    def decode_solution(self, solution):
        """
        QUBO解をシフトスケジュールに変換
        """
        schedule = np.zeros((self.num_employees, self.num_days, self.num_shifts), dtype=int)
        
        for emp_idx in range(self.num_employees):
            for day in range(self.num_days):
                for shift_idx in range(self.num_shifts):
                    var_key = self.variable_key(emp_idx, day, shift_idx)
                    if solution.get(var_key, 0) == 1:
                        schedule[emp_idx, day, shift_idx] = 1
        
        return schedule

3.4 解の可視化・評価

  • スケジュール表やヒートマップに変換
  • 希望満足率や違反数を計算

4. 実装上の注意点

  • ペナルティ係数の調整が重要

    • 人員不足の制約は重くする（絶対守るべき条件）
    • 希望シフトは軽め（守れたら嬉しいくらい）

  • 変数数が急増する問題

    • $E \times D \times |S|$ のオーダーで変数が増える
    • 大規模な場合は工夫や経験に基づく判断が必要

5. 実験と評価

5.1 評価指標

  • 希望満足率
    従業員 $e$ の希望集合を $P_e$ とし、満たされた希望の数を $s_e$ とする。
    個人の満足率は次で表される:

$$
\text{Satisfaction}(e) = \frac{s_e}{|P_e|} \times 100 \quad [\%]
$$

全体の満足率は

$$
\text{Satisfaction}_{\text{overall}} = \frac{\sum_e s_e}{\sum_e |P_e|} \times 100
$$

  • 人員不足違反
    日 $d$、シフト $s$ に割り当てられた人数を $n_{d,s}$、必要人数を $m_s$ とする。
    不足分は

$$
\text{Violation}_{d,s} = \max(0, m_s - n_{d,s})
$$

全体違反数は

$$
\text{Total Violations} = \sum_{d=1}^D \sum_{s \in S} \text{Violation}_{d,s}
$$

  • 過労違反
    従業員 $e$ の勤務回数は

$$
W_e = \sum_{d=1}^D \sum_{s \in S} x_{e,d,s}
$$

最大勤務日数 $M$ を超えた場合は過労違反とする:

$$
W_e > M \quad \Rightarrow \quad \text{Overwork Violation}
$$

  • 連続夜勤違反 (Consecutive Night Shift Violation)
    従業員 $e$ が日 $d$ と $d+1$ の両方で夜勤（シフト $s = \text{夜}$）に割り当てられた場合を違反とする:
\text{ConsecNight}_{e,d} =
\begin{cases}
  1 & \text{if } x_{e,d,\text{夜}} = 1 \land x_{e,d+1,\text{夜}} = 1 \\
  0 & \text{otherwise}
\end{cases}

全体の連続夜勤違反数は

$$
\text{Total ConsecNight Violations} = \sum_{e=1}^E \sum_{d=1}^{D-1} \text{ConsecNight}_{e,d}
$$

  • 複数シフト違反 (Multiple Shift Assignment Violation)
    1人の従業員 $e$ が同じ日 $d$ に複数のシフトへ割り当てられた場合を違反とする:
\text{MultiShift}_{e,d} =
\begin{cases}
1 & \text{if } \sum_{s \in S} x_{e,d,s} > 1 \\
0 & \text{otherwise}
\end{cases}

全体の複数シフト違反数は

$$
\text{Total MultiShift Violations} = \sum_{e=1}^E \sum_{d=1}^D \text{MultiShift}_{e,d}
$$

5.2 実験結果の例

サンプルスケジュールとして5人のシフト希望をランダムで生成し、それに基づいたシフトスケジューリングの一連の流れを視覚化したものを以下に示す。

▼前提条件
image.png

▼シフト希望(今回夜の希望が多いというパターンで生成された)
image.png

▼シフトスケジューリング結果
image.png

▼制約違反サマリ
image.png

今回のサンプルスケジュールに基づき、以下の評価を行った。

  • 希望満足率

    • 個別満足率:
      • Employee_1: $44.4\%$
      • Employee_2: $57.1\%$
      • Employee_3: $57.1\%$
      • Employee_4: $66.7\%$
      • Employee_5: $44.4\%$
    • 全体満足率: 約 $51.4\%$

  • 人員不足違反

    • 各日の分析結果より、ほぼすべての日で「朝」「夕」に不足が見られた。
    • 特に木曜の夜、土曜の夜は割当が $0$ 名であり、重大な不足といえる。
    • 1週間あたりの違反総数は 15件 であった。

  • 過労違反

    • 各従業員の勤務回数は均等に $4$ 回であり、最大勤務日数制約（$M=5$ などと仮定）を超過しなかったため、過労違反は発生しなかった。

  • 夜勤の連続割当

    • 各従業員に夜勤は分散されており、連続割当は見られなかった。

ヒートマップ可視化では、行を従業員、列を日付に対応させ、色でシフト状態を示すことで不足状況が直感的に把握できた。

6. まとめ

本実験では、シフトスケジュールの自動生成結果を評価指標に基づき分析した。
希望満足率は約 $51\%$ と半数程度が希望通りに割り当てられたが、依然として人員不足が多く、特に夜勤の割当が欠落する日があるなど実務上の課題が残った。
一方で勤務回数の偏りは見られず、過労違反や夜勤連続といった制約違反は回避できていた。

今後は、

  • 人員不足をより重視した目的関数の改良
  • 希望満足率とのトレードオフ調整
  • 実際の運用条件（法規制・勤務パターン制約）への適用

などを通じて、より実用的なスケジューリングが可能になると考えられる。

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?