背景教培机构的教师排班是一个经典的运筹优化问题。一个中型机构可能有30个老师、5间教室、6个时间段每个老师有可上班时间偏好、最大课时限制、擅长课程类型等约束排班目标是在满足所有约束的前提下最大化教室利用率并均衡教师工作量。之前帮一个客户做排班分析时发现教务主管每周花6小时手工排班排出来的结果教师满意度只有62%主要抱怨是工作量不均衡和排班时间不符合个人偏好。用线性规划重构后排班时间降到3秒教师满意度提升到85%。今天分享用Python PuLP库实现教师排班优化的完整过程。一、问题建模定义决策变量x[i,j,k,t]为布尔变量表示教师i在教室j给课程k在时间段t上课是否为1。import pulpimport pandas as pd# 数据准备teachers [T1, T2, T3, T4, T5]rooms [R1, R2, R3]courses [C1, C2, C3, C4]timeslots [TS1, TS2, TS3, TS4, TS5, TS6]# 教师可用时间偏好 (1可用, 0不可用)teacher_availability {(T1, TS1): 1, (T1, TS2): 1, (T1, TS3): 1, (T1, TS4): 0, (T1, TS5): 0, (T1, TS6): 1,(T2, TS1): 0, (T2, TS2): 1, (T2, TS3): 1, (T2, TS4): 1, (T2, TS5): 1, (T2, TS6): 0,# ... 其他教师}# 教师最大课时max_hours {T1: 20, T2: 25, T3: 18, T4: 22, T5: 15}# 教师擅长课程 (1可教, 0不可教)teacher_course_match {(T1, C1): 1, (T1, C2): 1, (T1, C3): 0, (T1, C4): 0,(T2, C1): 0, (T2, C2): 1, (T2, C3): 1, (T2, C4): 1,# ... 其他教师}# 课程需求每门课每周需要的课时数course_demand {C1: 8, C2: 6, C3: 5, C4: 4}二、构建LP模型model pulp.LpProblem(Teacher_Scheduling, pulp.LpMaximize)# 决策变量x {}for i in teachers:for j in rooms:for k in courses:for t in timeslots:name fx_{i}_{j}_{k}_{t}x[i,j,k,t] pulp.LpVariable(name, catBinary)# 目标1最大化教室利用率排的课越多越好utilization pulp.lpSum(x[i,j,k,t] for i in teachers for j in rooms for k in courses for t in timeslots)# 目标2教师工作量均衡最小化最大课时与最小课时之差teacher_workload {}for i in teachers:teacher_workload[i] pulp.lpSum(x[i,j,k,t] for j in rooms for k in courses for t in timeslots)max_workload pulp.LpVariable(max_workload, lowBound0)min_workload pulp.LpVariable(min_workload, lowBound0)for i in teachers:model teacher_workload[i] max_workloadmodel teacher_workload[i] min_workloadworkload_gap max_workload - min_workload# 加权目标函数最大化利用率同时最小化工作量差距model utilization - 10 * workload_gap三、添加约束条件# 约束1教师只能在自己可用的时间段上课for i in teachers:for t in timeslots:if teacher_availability.get((i, t), 0) 0:for j in rooms:for k in courses:model x[i,j,k,t] 0# 约束2教师只能教自己擅长的课程for i in teachers:for k in courses:if teacher_course_match.get((i, k), 0) 0:for j in rooms:for t in timeslots:model x[i,j,k,t] 0# 约束3教师课时不超过上限for i in teachers:model teacher_workload[i] max_hours[i]# 约束4每门课满足周课时需求for k in courses:model pulp.lpSum(x[i,j,k,t] for i in teachers for j in rooms for t in timeslots) course_demand[k]# 约束5同一教室同一时间段只能有一门课for j in rooms:for t in timeslots:model pulp.lpSum(x[i,j,k,t] for i in teachers for k in courses) 1# 约束6同一教师同一时间段只能在一个教室上一门课for i in teachers:for t in timeslots:model pulp.lpSum(x[i,j,k,t] for j in rooms for k in courses) 1# 约束7每门课每次至少2个连续时间段保证课的完整性for k in courses:for i in teachers:for j in rooms:for t_idx in range(len(timeslots) - 1):t1 timeslots[t_idx]t2 timeslots[t_idx 1]# 如果排了t1也必须排t2model x[i,j,k,t1] - x[i,j,k,t2] 0四、求解与分析solver pulp.PULP_CBC_CMD(msgFalse, timeLimit30)model.solve(solver)print(f求解状态: {pulp.LpStatus[model.status]})print(f目标值: {pulp.value(model.objective)})# 提取排班结果schedule []for i in teachers:for j in rooms:for k in courses:for t in timeslots:if pulp.value(x[i,j,k,t]) 1:schedule.append({teacher: i, room: j, course: k, timeslot: t})schedule_df pd.DataFrame(schedule)print(schedule_df.groupby(teacher).size()) # 每个教师的课时数求解后对比人工排班和优化排班的结果人工排班教室利用率78%教师课时标准差6.2满意度62%。优化排班教室利用率91%教师课时标准差2.8满意度85%。五、踩坑经验第一个坑是连续时间段约束。最初没加这个约束排出来的课表出现了一门课在TS1上了40分钟又在TS4上了40分钟的情况老师和学生都受不了。加了约束7后保证每次课至少是连续的两个时间段。第二个坑是目标函数的权重。最初把workload_gap的权重设为1结果优化器为了均衡工作量牺牲了大量教室利用率。调到10之后两者达到了比较好的平衡。这个权重需要跟机构实际需求对齐有些机构更看重利用率有些更看重教师满意度。第三个坑是求解时间。当教师数超过50人、时间段超过20个时变量数量爆炸CBC求解器可能需要几分钟。这时候可以考虑用Gurobi等商业求解器或者用列生成算法做问题分解。六、总结线性规划排班的核心价值不是替代人而是给教务主管一个高质量的初始方案。人工排班最大的问题是容易陷入局部最优——排到后面发现前面的不合理改了前面后面的又冲突了最后勉强排完但质量不高。LP求解器能全局优化在几秒内给出一份满足所有硬约束的排班方案教务主管再根据实际情况微调效率和质量都大幅提升。