Python线性规划排班:夜班约束、禁连续班及均衡分配建模
8人团队线性排班模型补全实现
一、现有代码的基础问题修正
原代码存在逻辑冲突:当前对每人每日班次数设置了==1的硬约束,直接和「每日最多2个班次」的规则矛盾,需要调整为两个独立约束:
- 每人每日至少安排1个班次
- 每人每日最多安排2个班次
- 删除原有等式约束
- 原代码中
solver = None的设置无需修改,PuLP会自动调用内置的开源CBC求解器完成计算
二、三类缺失规则的约束编码
1. 禁止连续相邻班次
首先明确需要禁止的相邻班次组合(只要存在时间衔接的前后班次,就不能安排给同一人):
- 同一天内相邻时段:早班→中班、中班→晚班
- 跨天衔接:前一天晚班→次日早班
对应约束逻辑:对每一组禁止的相邻班次对,同一人两个班次的赋值之和≤1,代码实现片段:
# 定义所有禁止连排的班次对(时间差, 前序班次, 后序班次) adjacent_pairs = [ (0, "morning", "afternoon"), (0, "afternoon", "night"), (1, "night", "morning") ] for day in all_days: for delta_d, shift1, shift2 in adjacent_pairs: target_day = day + delta_d # 超出调度周期范围直接跳过 if target_day >= len(all_days): continue for person in all_people: # 同一人不能同时排相邻的两个班 allocation_model.addConstraint( to_assign[(day, shift1, person)] + to_assign[(target_day, shift2, person)] <= 1 )
2. 夜班休息机会约束
规则要求:每人至少1次夜班休息(最优为2次)
- 定义对齐:夜班休息指员工上夜班后,次日不会被安排需要连夜衔接的早班。由于前面的连续班次禁止规则已经把「前一天夜班+次日早班」的组合完全锁死,只要安排夜班就天然对应1次休息机会,不需要额外计算二次项
- 硬约束:每人整个周期内至少被安排1次夜班,保证最低1次休息
- 最优目标引导:在目标函数中添加惩罚项,引导模型优先满足每人2次夜班的要求,若班次总量受限无法满足,会自动退而满足最低要求
代码实现片段:
# 硬约束:每人至少1次夜班(即至少1次休息) for person in all_people: total_night = sum(to_assign[(d, "night", person)] for d in all_days) allocation_model.addConstraint(total_night >= 1) # 目标惩罚:每差1次夜班(即少1次休息),计入目标值引导优化 allocation_model += (2 - total_night)
3. 均衡分配目标函数
需要实现「最小化人员间总班次、夜班数的最大差值」,线性规划中采用引入辅助变量的标准方法,避免直接使用max/min带来的非线性问题:
- 计算每个人员的总班次、夜班数基础表达式
- 引入4个连续型无范围变量:
max_total:所有人总班次的最大值min_total:所有人总班次的最小值max_night:所有人夜班数的最大值min_night:所有人夜班数的最小值
- 绑定线性约束,将辅助变量和人员实际指标关联
- 目标函数设置为最小化两个差值的加权和,权重可根据均衡偏好调整
代码实现片段:
# 定义均衡目标的辅助变量 max_total = LpVariable("max_total", lowBound=0, cat="Continuous") min_total = LpVariable("min_total", lowBound=0, cat="Continuous") max_night = LpVariable("max_night", lowBound=0, cat="Continuous") min_night = LpVariable("min_night", lowBound=0, cat="Continuous") for person in all_people: # 计算个人总班次、夜班数 total_p = sum(to_assign[(d, s, person)] for d in all_days for s in all_shifts) night_p = sum(to_assign[(d, "night", person)] for d in all_days) # 绑定max/min和实际值的约束 allocation_model.addConstraint(total_p <= max_total) allocation_model.addConstraint(total_p >= min_total) allocation_model.addConstraint(night_p <= max_night) allocation_model.addConstraint(night_p >= min_night) # 最终目标函数:总班次差值 + 夜班数差值(权重0.5可调整) allocation_model += (max_total - min_total) + 0.5*(max_night - min_night)
三、其他Python线性规划工具的实现思路
- SciPy实现:基于
scipy.optimize.linprog接口,需要将所有二元变量、辅助连续变量按固定顺序展开,把所有约束转换为不等式矩阵、等式矩阵形式。逻辑和PuLP完全一致,但需要手动处理变量索引和矩阵拼接,二元变量的求解效率低于PuLP自带的CBC求解器。 - Gurobi实现:不需要手动拆分max/min的辅助变量,可直接调用内置的
max()、min()函数构造目标表达式,代码量比PuLP少30%左右,求解速度随问题规模上升的优势明显,适合18天周期的排班场景(该场景下仅432个二元变量,Gurobi可实现毫秒级全局最优求解)。
内容的提问来源于stack exchange,提问作者Tommy Lees
相关产品推荐
相关产品推荐

