★ FEATURED ARTICLE 2006年那届研究生数学建模竞赛里D题“学生面试问题”是我印象很深的一道题。不是因为算法多复杂而是它把“老师不够用”这个现实中特别具体的痛点硬生生变成了一道需要建模、评估、排期、决策的综合题。那会儿大家普遍在练优化、练预测突然来一道跟现场管理、人员分配沾边的题思路没转过来的队伍很容易栽跟头。我当年带着几个人一起推过这道题后来也帮别的团队复盘过几轮今天把整个解题框架、实操细节、踩坑记录完整写出来。如果你正在准备建模比赛或者工作中要处理“资源受限下的分配调度”问题这篇内容可以直接当参考手册用。1. 整体解构这题到底在问什么1.1 先把题目翻译成大白话面试问题的设定通常是这样有一批学生要参加面试每个学生的面试时长得固定有一批老师可以当考官每位老师有自己的可用时间段每个学生至少要经过若干位老师的面试最终根据打分决定结果。表面看是“排个面试表”实际上题目隐含了三层要求一是时间表必须排得开不能冲突二是老师资源要尽量均匀使用不能有人忙死有人闲死三是如果老师临时缺席或学生迟到方案要有调整空间。很多队伍上来就奔着排课表去用贪心、用遗传算法结果搞出来一个时间表却发现根本没回答题目真正关心的“评价指标”。这道题最核心的考点其实是怎么定义“好方案”。如果连评估标准都没有后面所有算法都是在自嗨。当年我们的第一步不是写代码而是把题目里的所有角色和约束列成一张表。学生有编号、有面试时长、有可面试时段老师有编号、有可用时段、有擅长方向面试规则规定了每个学生至少见几位老师、老师两两之间能不能组合、有没有回避规则。把这些实体和约束理清楚题目才算是真正被读懂了。1.2 建模竞赛题和真实项目的区别有人问这种题是不是就是练个手跟工作里的排班系统没啥关系其实关系很大。企业里排面试官、安排会议室、分配客服班次本质上都是“约束满足资源均衡”问题。建模竞赛的好处是题目会故意剥离掉很多脏数据让你集中精力设计核心逻辑。工作里的排班可能还要考虑员工偏好、劳动法、系统接口但底层模型是一致的。所以我一直建议做这道题时别只盯着“解出来”要盯着“评估指标是否合理”。比赛评审看重的往往不是你的算法有多酷而是你有没有说清楚“为什么选这个指标”“这个指标能不能反映真实场景”。1.3 常见误区把D题当纯优化题做我看到过不少队伍的论文开头先写一堆神经网络、模拟退火最后却连“老师利用率”都没定义清楚。评委一问回答不上来。这就是典型的把D题当成了纯优化题。正确姿势是用“建模思维”拆解明确目标是什么例如总面试时间最短、老师空闲时间最长的那位越短越好、学生等待时间越短越好明确约束是什么老师可用时段、学生可面试时段、每个学生需要面试的老师数量、教室数量明确决策变量是什么谁在什么时间、什么地点、面谁明确评价方案是什么冲突率、老师负载均衡度、方案调整的鲁棒性把这四件事写在论文最前面后面的内容都会顺很多。2. 模型设计与指标拆解不是所有“快”都叫好方案2.1 最基础的排期模型经典做法是构建一个三维决策变量某个时段、某个老师、某个学生组合在一起是一个“事件”。约束条件大概有四类一个学生同一时间只能参加一场面试一位老师同一时间只能参与一场面试每个学生必须完成要求数量的面试老师只能在可用时段内参与面试。在此基础上目标函数可以是最小化总完成时间makespan也可以是最小化老师的空闲碎片时间。如果题目还给了教室数量限制那就要再加一维约束同一时间使用的教室数不能超过可用教室数。当时我们用的是整数规划框架先跑一遍小规模数据得到可行解之后再去扩展启发式算法。对于6位老师、20位学生的小样本整数规划能直接出最优到了50位学生、10位老师就要改用启发式。2.2 资源分配均衡度才是关键排得开只是及格线。题目里通常隐含一个价值导向老师的工作量要均衡不能出现某位老师连续面了8个学生、另一位老师却在旁边刷手机的情况。我定义了两个指标老师负载均衡度每位老师实际参与面试时长的方差或者极差。极差就是最大负载减最小负载简单直观。老师利用率老师实际参与面试的时间除以老师总可用时间。这两个指标需要放在一起看。只看利用率容易让某位老师被塞满只看极差又可能导致整体完成时间变长。我们当年的做法是分两步走第一步在满足所有硬约束的前提下最小化总完成时间第二步在总完成时间不变或略增的范围内最小化老师负载极差。相当于一个多目标问题用两层优化来处理。2.3 多维评估好方案需要一张“体检表”单看完成时间、利用率其实还不够。后来复盘时我们给方案做了个五维评分表评估维度具体计算方式说明总完成时间最后一个面试结束时刻反映效率老师负载极差最大负载减最小负载反映均衡度学生等待时间均值学生从到场到面试结束的总等待反映公平与体验约束违反次数硬约束被打破的次数必须是0调整鲁棒性随机移除一位老师后重新排期的成本反映方案抗干扰能力这个表不仅可以用在建模比赛里平时做项目汇报、做方案选型时也很有用。评估不只是“这个方案能不能跑通”而是“这个方案跑到什么程度算好”。3. 算法选型实战从整数规划到遗传算法的逐级演进3.1 小规模场景首选整数规划当时我们先用Python调用开源求解器跑整数规划。建模过程其实很顺约束条件直接按题目写就行。小规模数据下求解器能快速返回最优解这个最优解可以当作后续启发式算法的“标尺”。不过这里有个坑整数规划在变量多的时候会非常慢。比赛数据如果给到几十个学生、十位老师变量数量轻松上万普通笔记本跑起来很吃力。我们当时跑20个学生还算流畅跑到40个学生就开始明显卡顿。所以整数规划只用来验证小规模场景和提取最优解的下界。3.2 启发式算法贪心初始解局部搜索中等规模我们用了“贪心构造局部搜索”的组合。贪心策略很简单把老师按可用时段从少到多排序时段紧的老师优先分配把学生按面试时长从长到短排序耗时长的学生优先安排。这个策略的本质是“越稀缺的资源越早占用”。局部搜索用的是两两交换随机选两个学生看交换他们的面试时段能否降低目标函数能就换不能就保留。这个操作看起来简单但迭代几千次之后方案质量会肉眼可见地提升。我们当时还试过把模拟退火加进去温度系数从高到低前期允许接受差解跳出局部最优后期收敛到稳定解。实测下来模拟退火比纯局部搜索的稳定性好但参数调起来因人而异新手容易调过头导致结果忽好忽坏。3.3 遗传算法编码方式决定上限遗传算法的关键在编码。我们试过两种方式整数编码每个基因位表示某个学生分给哪个老师、哪个时段解码时需要检查冲突。排列编码每个个体表示学生的面试顺序解码时按顺序依次分配最早可用时段。第二种比第一种更容易维护可行性因为它在解码过程中天然满足时间先后顺序。交叉操作我们用了我记得叫“部分映射交叉”的方法变异操作则是随机交换两个学生的顺序。遗传算法跑起来的感受是前50代收敛很快后面会进入平台期。这时候再去调大变异率反而可能破坏已经不错的解。所以参数策略应该是前期强调选择压力后期强调变异多样性动态调整。3.4 混合策略把“最优下界”和“近似解”结合最终我们采用了一套混合策略先用整数规划跑小规模得到最优解下界再用遗传算法在大规模上跑得到近似解然后计算近似解与下界的差距如果差距在5%以内就接受超过则继续迭代或增加迭代次数。这个流程的本质是把“精确算法的下界”当作一把尺子去度量启发式算法的质量。在论文里写这个流程评委是认可的因为它体现了算法选型的逻辑性而不是堆砌方法。4. 实操过程全记录从数据清洗到结果输出4.1 数据准备与预处理题目给的数据通常很规整但真实场景未必。比赛时我们也遇到过老师可用时段写了“下午”这种模糊说法需要自己映射成具体时间段。我的建议是提前做一套数据预处理脚本把输入变成统一格式的表后用代码也好、手算也好都会省很多事。预处理通常包括把日期时间统一成分钟单位例如9:00记为540把老师的可用时段展开成最小时间片列表把学生的可面试时段同样展开检查矛盾数据例如老师可用时间与学生可面试时间完全没有交集时需要标记并决定是否剔除或特殊处理。4.2 代码实现的结构我们当时用Python写了一套主流程结构大概是这样# 伪代码主流程 def main(): teachers load_teachers(data/teachers.csv) students load_students(data/students.csv) rooms load_rooms(data/rooms.csv) # 生成所有候选时间段 slots generate_slots(teachers, students) # 整数规划或启发式求解 schedule solve_schedule(teachers, students, rooms, slots) # 评估 report evaluate(schedule) plot_gantt(schedule)代码不复杂但一定要把“数据加载”“求解”“评估”“可视化”拆成独立模块。这样后面换算法时只需要替换solve_schedule这一个函数其他都不用动。4.3 输出可视化甘特图是跟评委沟通的桥梁做了那么多计算最后展示才是关键。我们画了老师维度的甘特图横轴是时间纵轴是老师每个块代表一场面试。这张图一出来评委立刻能看出时间是否冲突、老师是否均衡。另外一个很有用的可视化是“老师负载柱状图”直接标出每位老师的总面试时长。评委一眼就能看出负载均不均衡。画甘特图的时候注意颜色别太多同一个学生全程用同一种颜色这样看连续面试时能一眼追踪。我们最初用随机颜色结果自己都分不清谁是谁后来改成按学生编号映射固定颜色画图之后的信息密度高了很多。4.4 实验配置记录这里分享一组我们实验跑出来的配置仅供参考不保证所有数据都一样但可以当一个起点参数数值说明老师人数8可用时段每人不完全重叠学生人数30每个学生需面3位老师教室数量2同时最多两场面试遗传算法种群100个体数量遗传算法代数150迭代代数交叉率0.8交叉操作概率变异率0.1变异操作概率在这个配置下总完成时间比单纯用贪心缩短了约18%。不过要强调的是参数要跟着数据规模走不要照抄。5. 常见问题与排查技巧实录5.1 解不可行几乎所有队伍都会遇到我第一次跑遗传算法时经常出现“看似有解、解码全是冲突”的情况。排查后发现是因为交叉操作把两个父本信息打乱后子代里学生重复出现。解决方法是引入修复机制交叉后扫描一遍基因序列发现重复的学生就替换成缺失的学生保证每个学生出现且仅出现一次。这里分享一个排查技巧写一个校验函数输入任意个体输出是“是否满足所有硬约束”。每次迭代后都调用这个函数不仅能抓冲突还能统计冲突类型。我们在校验函数里按学生冲突、老师冲突、教室冲突分三类统计定位问题非常快。5.2 目标函数优化但实际方案不合理有几次算法跑完发现总用时最短但早上8点就安排老师连续面试到12点不休息下午反而全空。这个问题在于目标函数只考虑了总用时没有惩罚连续工作疲劳。后来在目标函数里加入“同一老师连续面试超过两场增加一个惩罚系数”方案就自然变成了有间隔的合理排期。这个坑在真实排班系统里更常见加惩罚项比改约束条件灵活得多。5.3 老师的可用时段被用完学生却没排完这是约束建模疏漏的典型表现。原因通常是学生可面试时段与老师可用时段的重叠被忽略或者某个时段的教室容量限制没考虑进约束。我们的排查方法是做“需求-容量”分析把每个时段可用的老师数、学生需求量、教室数放在一张热力表里哪个时段是瓶颈一目了然。5.4 鲁棒性测试方法最后还有一个值得分享的方法鲁棒性测试。我们当时做了这样一个实验随便抽走一位老师看重新排期或局部调整后方案是否还能跑通。如果某个老师被抽走后直接导致好几个学生无法完成面试那说明方案过度依赖某个关键老师在真实场景中风险很大。鲁棒性指标可以写成“移除一位老师后需要重新调整的学生比例”或者“调整后的总完成时间变化率”。把这个指标写进论文或方案汇报里比单独说“我的方案可行”更有说服力。6. 个人实操体会这些细节比算法更重要6.1 读题三遍再动手真的不亏我们最早就是因为第一遍读题时漏了“每位老师的可用时段不完全一致”这个条件导致初始模型连续好几天跑不出合理结果。后来重新梳理题目把每个约束都写成白纸黑字模型才走上正轨。建模比赛的题目通常不会太长但每个字都可能影响模型结构读题三遍不是浪费时间。6.2 数据可视化是做判断的第一工具每次算法改完我第一件事不是看指标数值而是看甘特图。图里如果出现大片的空白或高度重叠即使指标说“完成时间最小”也要回头检查约束是否有遗漏。有一次我盯着甘特图看了一会儿发现一位老师上午连续面了4个学生下午完全空闲这个信息比看负载方差来得直观得多。6.3 多目标处理思路分层优于加权把多个目标用一个权重合成最大的问题是权重难调。我们的经验是优先保证硬约束然后分层次优化。第一层最小化总完成时间第二层在不超过第一层结果5%的范围内优化均衡度。这是工程上常见的“目标优先级”思想比调权重稳定。6.4 文档记录也是竞争力我们当时要求每个团队成员都把调试过程、参数变化、实验结果记录在共享表格里。到了写论文阶段素材丰富得无压力。哪个参数试过、效果如何、为什么最终这么选全部有据可查。很多队伍到最后写论文时才发现前期实验记录太少只能编编出来的内容一被追问就露馅。记录不只是为了论文也是为了让自己在复盘中真正理解每个参数的作用。6.5 关于“完美方案”的一点看法这道题以及这类调度问题几乎不存在一个在所有指标上都最优的解。总完成时间最短可能老师负载就不均匀老师负载均匀了学生等待时间可能变长。选方案时的核心是弄清楚你最在意哪个指标然后把它当作主要优化目标其他指标作为辅助参考。这种思路放在真实业务场景里也完全成立开会时跟需求方对齐优先级比闷头优化有用得多。6.6 最后分享一个排期小技巧如果面试过程中可能出现老师临时缺席的情况可以在排期时故意留出“备用时段”例如每个老师的可用时段里只排80%的面试剩下20%作为缓冲。这样做的代价是总完成时间略微增加但换来的是即便有人临时缺席局部调整就能搞定不需要推倒重来。这个思路其实来自修电脑先备份文件的直觉多留一条后路永远比事后救火舒服。如果你正在准备类似比赛或要解决现实里的排班调度问题建议先从这道D题做起把资源约束、目标函数、鲁棒性这些概念过一遍。这套方法论学会了以后遇到再复杂的调度需求心里都会有一张清晰的图。
阅读完成 · 觉得有帮助？
