人員排班與輪值系統

人員排班是 ILP/CP 最經典的應用場景之一：如何安排員工的班次，在滿足所有人力需求的同時，最大化員工滿意度？

模型建立

from ortools.sat.python import cp_model

# === 定義排班需求 ===
DAYS = 7  # 一週 7 天
SHIFTS = ["早班", "中班", "晚班"]
NUM_SHIFTS = len(SHIFTS)
EMPLOYEES = [f"員工{i}" for i in range(10)]
NUM_EMPLOYEES = len(EMPLOYEES)

# 每天每個班次需要的人力
shift_requirements = {
    (0, 0): 2, (0, 1): 2, (0, 2): 1,  # 週一
    (1, 0): 2, (1, 1): 2, (1, 2): 2,  # 週二
    (2, 0): 2, (2, 1): 1, (2, 2): 1,  # 週三
    (3, 0): 3, (3, 1): 2, (3, 2): 1,  # 週四
    (4, 0): 3, (4, 1): 2, (4, 2): 2,  # 週五
    (5, 0): 1, (5, 1): 1, (5, 2): 2,  # 週六
    (6, 0): 1, (6, 1): 1, (6, 2): 2,  # 週日
}

# === 建立模型 ===
model = cp_model.CpModel()

# 變數：shifts[e][d][s] = 1 表示員工 e 在第 d 天的第 s 班
shifts = {}
for e in range(NUM_EMPLOYEES):
    for d in range(DAYS):
        for s in range(NUM_SHIFTS):
            shifts[(e, d, s)] = model.NewBoolVar(f"shift_e{e}_d{d}_s{s}")

# 限制 1：每個班次的人力需求必須滿足
for d in range(DAYS):
    for s in range(NUM_SHIFTS):
        if (d, s) in shift_requirements:
            model.Add(
                sum(shifts[(e, d, s)] for e in range(NUM_EMPLOYEES))
                == shift_requirements[(d, s)]
            )

# 限制 2：每個員工每天最多一個班次
for e in range(NUM_EMPLOYEES):
    for d in range(DAYS):
        model.Add(sum(shifts[(e, d, s)] for s in range(NUM_SHIFTS)) <= 1)

# 限制 3：每個員工每週最多 5 天
for e in range(NUM_EMPLOYEES):
    model.Add(
        sum(shifts[(e, d, s)] for d in range(DAYS) for s in range(NUM_SHIFTS))
        <= 5
    )

# 限制 4：不能連上晚班+早班（禁止晚班後隔天早班）
for e in range(NUM_EMPLOYEES):
    for d in range(DAYS - 1):
        model.Add(shifts[(e, d, 2)] + shifts[(e, d + 1, 0)] <= 1)

# 目標：公平分配（最大化最低班次數）
min_shifts = model.NewIntVar(0, DAYS * NUM_SHIFTS, "min_shifts")
for e in range(NUM_EMPLOYEES):
    total = sum(shifts[(e, d, s)] for d in range(DAYS) for s in range(NUM_SHIFTS))
    model.Add(min_shifts <= total)

model.Maximize(min_shifts)

# === 求解 ===
solver = cp_model.CpSolver()
solver.parameters.max_time_in_seconds = 30
status = solver.Solve(model)

if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    print(f"\n=== 人員排班結果 ===")
    
    # 建立排班表
    schedule = [["" for _ in range(DAYS)] for _ in range(NUM_EMPLOYEES)]
    for e in range(NUM_EMPLOYEES):
        for d in range(DAYS):
            for s in range(NUM_SHIFTS):
                if solver.Value(shifts[(e, d, s)]):
                    schedule[e][d] = SHIFTS[s]
    
    # 輸出
    headers = ["員工"] + [f"第{d+1}天" for d in range(DAYS)]
    print(" | ".join(headers))
    print("-" * 50)
    for e in range(NUM_EMPLOYEES):
        row = [EMPLOYEES[e]] + [schedule[e][d] or "-" for d in range(DAYS)]
        print(" | ".join(row))
    
    # 統計
    print(f"\n=== 員工班次統計 ===")
    for e in range(NUM_EMPLOYEES):
        total = sum(1 for d in range(DAYS) if schedule[e][d])
        print(f"{EMPLOYEES[e]}: {total} 天")
else:
    print("找不到可行排班！")

---

---

人員排班為什麼這麼難？

如果你曾經排過班表，你就知道這有多痛苦：

• 早班需要 3 個人，晚班需要 2 個人，大夜班只需要 1 個人
• 每個人一週不能超過 5 天班
• 不能連續排 2 天大夜班
• 特定員工週末不能上班
• 每個人的偏好不同

手動排班可能花掉主管一整天的時間，而且排出來的班表總是有人不滿意。

CP-SAT 可以在幾秒鐘內解決這個問題。

CP-SAT 的優勢

| 優勢 | 說明 | |:----:|------| | 自然建模 | 直接用「變數 = 決策」的方式描述問題，不需要轉換成線性方程式 | | 全域約束 | 內建 AllDifferent、AddExactlyOne 等強大約束 | | 最佳化 | 不僅能找到可行解，還能找出最佳解（最大化滿意度、最小化成本） | | 速度 | 利用 SAT 技術的剪枝能力，比傳統 ILP 求解器快數倍 |

下一章預告：從排班到資源分配

人員排班是「時間 × 人員」的分配問題。下一章的 資源分配 將擴展到更一般的場景——當你有多種資源（設備、空間、材料）需要同時分配時，該如何建模與求解。