基于PuLP线性规划的排班优化：最低工时约束致模型不可行排查

不可行核心原因 #

1. 总工时供需不匹配：若所有员工的最低工时总和（员工数×5）大于所有品牌的总需求工时，模型必然无解——你要求每个员工至少干5小时，但没有足够的工作量支撑。
2. 单品牌需求无法适配连续5小时排班：比如某品牌仅在早9-12点需要人手（3小时），但约束要求员工必须连续干5小时，没有对应的合法时段能满足，导致冲突。
3. 约束逻辑错误：原代码可能直接给每个排班员工加了工时≥5的硬约束，但未关联品牌的可用时段区间，导致无法找到合法的分配方案。

修正思路 #

1. 重新定义决策变量：将变量从「员工是否分配到品牌」改为「员工是否分配到某品牌的某连续时段区间」，区间长度限制在5-9小时内。
2. 调整约束逻辑：
   • 每个员工单日仅能选择一个品牌的一个合法时段区间
   • 每个品牌每个小时的在岗人数≥该时段需求
   • 强制时段区间长度在5-9之间，自然满足工时约束
3. 前置校验：确保总需求工时≥员工数×5，否则先调整员工数量或需求。

完整修正代码示例 #

import pulp

# ---------------------- 基础数据 ----------------------
EMPLOYEES = ["E1", "E2", "E3", "E4"]  # 4名员工
BRANDS = ["BrandA", "BrandB"]
# 品牌小时需求：key=(品牌, 小时), value=所需人数
HOURLY_DEMAND = {
    ("BrandA", 9): 2, ("BrandA", 10): 2, ("BrandA", 11): 2, ("BrandA", 12): 1,
    ("BrandA", 13): 1, ("BrandA", 14): 2, ("BrandA", 15): 2, ("BrandA", 16): 2,
    ("BrandB", 9): 1, ("BrandB", 10): 1, ("BrandB", 11): 1, ("BrandB", 12): 1,
    ("BrandB", 13): 1, ("BrandB", 14): 1, ("BrandB", 15): 1, ("BrandB", 16): 1
}
WORK_HOURS = range(9, 17)  # 工作时段9-16点（共8小时，可调整）
MIN_SHIFT = 5  # 最小连续工时
MAX_SHIFT = 9  # 最大连续工时

# 生成所有合法的时段区间：长度5-9小时，且在工作时段内
valid_shifts = []
for start in WORK_HOURS:
    for length in range(MIN_SHIFT, MAX_SHIFT+1):
        end = start + length - 1
        if end <= max(WORK_HOURS):
            valid_shifts.append((start, end))

# ---------------------- 模型构建 ----------------------
model = pulp.LpProblem("Employee_Scheduling", pulp.LpMinimize)

# 决策变量：x[e, b, s, e_shift] = 1表示员工e分配到品牌b的时段(s, e_shift)
x = pulp.LpVariable.dicts(
    "Assign",
    [(e, b, s, e_shift) for e in EMPLOYEES for b in BRANDS for (s, e_shift) in valid_shifts],
    cat='Binary'
)

# 目标函数：最小化总工时（避免过度排班）
model += pulp.lpSum([(e_shift - s + 1) * x[(e, b, s, e_shift)] 
                     for e in EMPLOYEES for b in BRANDS for (s, e_shift) in valid_shifts])

# ---------------------- 约束条件 ----------------------
# 1. 每个员工单日仅能分配到一个品牌的一个时段
for e in EMPLOYEES:
    model += pulp.lpSum([x[(e, b, s, e_shift)] 
                         for b in BRANDS for (s, e_shift) in valid_shifts]) == 1

# 2. 每个品牌每个小时的在岗人数≥需求
for (b, h) in HOURLY_DEMAND:
    model += pulp.lpSum([x[(e, b, s, e_shift)] 
                         for e in EMPLOYEES for (s, e_shift) in valid_shifts 
                         if s <= h <= e_shift]) >= HOURLY_DEMAND[(b, h)]

# 3. 自动满足工时5-9小时：valid_shifts已过滤符合长度要求的时段，无需额外约束

# ---------------------- 求解与输出 ----------------------
model.solve(pulp.PULP_CBC_CMD(msg=0))  # msg=0关闭日志

if pulp.LpStatus[model.status] == "Optimal":
    print("最优排班方案：")
    for e in EMPLOYEES:
        for b in BRANDS:
            for (s, e_shift) in valid_shifts:
                if x[(e, b, s, e_shift)].value() == 1:
                    print(f"员工{e} → 品牌{b}，工作时段：{s}:00-{e_shift+1}:00，时长{e_shift - s + 1}小时")
else:
    print(f"模型状态：{pulp.LpStatus[model.status]}")
    # 排查建议
    print("排查方向：")
    print("- 检查总需求工时是否≥员工数×5")
    print("- 检查是否存在品牌的需求时段无法组合出5小时连续班")
    print("- 调整最小工时或员工数量")

关键说明 #

• 变量绑定具体连续时段，确保每个排班的工时天然符合5-9小时要求，避免硬加约束导致的冲突。
• 若模型仍不可行，先核对总需求工时：把所有HOURLY_DEMAND的值求和，必须≥员工数×5，否则没有足够工作量覆盖最低工时要求。
• 可根据实际工作时段调整WORK_HOURS，比如扩展到8-18点，生成更多合法的5-9小时时段。

内容的提问来源于stack exchange，提问作者davelod