简介基于谷歌优化工具OR-Tools的Java API这份人员排班问题建模与求解示例面向需要处理排班、调度场景的Java开发者与运筹优化入门者重点演示如何将班次需求、员工技能、工时限制等实际条件转化为整数规划模型并调用求解器获得最优或可行排班方案。资源为zip压缩包共4个文件含1个Java源文件和3个CSV数据文件班次表、需求人数矩阵等整包仅3KB轻量易读便于二次修改。已有978人浏览学习。示例代码按工程流程展示了模型构建、决策变量定义、约束添加、求解器配置与结果输出等完整环节并配有可直接运行的真实数据读者可据此理解此类工具在人员排班场景中的典型写法也能通过调整数据和约束迁移到门店调度、项目排期等同类问题是系统掌握优化建模与求解方法的实用参考。1. 人员排班用 OR-Tools 解决为什么手工排班总是效率低做过排班系统的开发者都清楚手工排班和用脚本去排是两回事。手工排班面对几十人、一周七天、两到三班倒的时候规则一多就开始互相打架——谁谁不能连班、谁谁周末必须休、工时不能超、账不能负全撞在一起。这本质是一个约束满足问题而 OR-Tools 就是 Google 出的一整套离散优化工具专门干这种事把约束翻译成数学模型再用 CP-SAT 求解器去找可行解甚至最优解。如果你在 Java 后端里开发排班、排产、排课这类模块并且已经受够了周末加班给每个人手动微调 Excel 表那这篇就是每个人的必读。本文从一个模拟项目 X 的实际拆解出发讲清楚 Java API 的建模思路、求解器参数怎么调、以及五个容易翻车的坑。2. Java API 快速上手先把依赖和头 100 行跑通2.1 依赖引入与工程结构我建议先从 Maven 开始本地开发环境用 JDK 11 及以上。OR-Tools 的 Java 包在 Maven Central 上有预编译版本Windows、Linux、macOS 都提供了对应的 native 库所以并不需要你自己编译 C 核心。dependency groupIdcom.google.ortools/groupId artifactIdortools-java/artifactId version9.11.4210/version /dependency引入依赖后第一步要做的不是写模型而是加载本地动态库。很多人为了这行代码折腾半小时因为 native 库加载失败时抛的异常和普通 jar 包冲突很像。import com.google.ortools.Loader; public class ShiftScheduler { static { Loader.loadNativeLibraries(); } // 后续模型代码 }逻辑说明Loader 做的事情是把 OR-Tools 的本地库从 jar 包中抽取到临时目录然后执行 System.load 加载。这个静态块要放在 class 的初始化中保证 JVM 加载类时最先执行。参数说明如果项目部署在内网环境且不允许 JVM 写临时目录可以通过环境变量JAVA_TMPDIR指定可写路径。另外注意某个版本的 protobuf-java 和 or-tools 的传递依赖可能会有版本冲突建议在 pom 里引入com.google.protobuf:protobuf-java的兼容版本。2.2 认识核心对象CpModel、BoolVar 与 Objective排班问题建模时最核心的对象就几个CpModel是模型的容器BoolVar是 0/1 决策变量IntVar是整数变量最终用CpSolver去求解。第一次接触 CP-SAT 的人容易把它和混合整数规划MIP搞混但其实二者的求解逻辑完全不同CP-SAT 大量依赖子句传播和冲突回溯更贴近图搜索所以在布尔约束密集的排班问题里优势很大。写一个最小模型验证环境CpModel model new CpModel(); BoolVar x model.newBoolVar(x); BoolVar y model.newBoolVar(y); model.addBoolOr(new Literal[]{x, y.not()}); model.minimize(x); // 求 x0 的可行解作为环境冒烟测试 CpSolver solver new CpSolver(); CpSolverStatus status solver.solve(model); System.out.println(status);这段代码的意思是设置两个布尔变量约束条件是 x 为真或者 y 为假至少成立一个目标函数让 x 最小。由于目标函数最小化时x0 是最优的所以 CP-SAT 会返回 OPTIMAL。注意model.minimize()接受 IntVar 或 LinearExprBoolVar 是 IntVar 的子类所以这里可以直接传。跑通这 100 行说明你的环境已经能执行 OR-Tools 的全部运算后续就可以放心建模了。2.3 数据模型设计人员、日期、班次的三维立方体排班本质上是给「人 × 日期 × 班次类型」这个三维空间里的每个元素赋 0/1 值。我们用布尔变量x[person][day][shift]表示某人某天某个班次是否被安排。这样的设计天然具备灵活性——每个格子可以是 0 也可以是 1约束就写在格子上。int numPeople 20; int numDays 7; int numShifts 3; // 早班、中班、晚班 BoolVar[][][] x new BoolVar[numPeople][numDays][numShifts]; for (int p 0; p numPeople; p) { for (int d 0; d numDays; d) { for (int s 0; s numShifts; s) { x[p][d][s] model.newBoolVar(x_ p _ d _ s); } } }构建三维数组时有个隐藏的陷阱如果你在循环里把变量名写成了不带索引的字符串比如x模型本身不会报错但调试时完全无法区分变量解出来也没法回填。变量名建议带上维度下标例如shift_p0_d6_s2转成模型导出 DOT 文件之后会非常直观。数据规模方面20人 7 天 3 班生成 420 个布尔变量这对 CP-SAT 来说是玲珑级问题。但如果做到 500 人 30 天 5 班次变量数就会飙到 7.5 万个这时候就必须依赖模式化约束和求解器参数来收敛了。3. 约束建模把排班规则翻译成 CP-SAT 的合法句式3.1 硬约束一每人每天最多轮一个班次排班里第一条必须满足的硬规则是同一个人同一天不能同时被安排早班和晚班。这句话翻译成约束是「对同一个人、同一天内所有班次的决策变量之和 ≤ 1」。for (int p 0; p numPeople; p) { for (int d 0; d numDays; d) { Literal[] literals new Literal[numShifts]; for (int s 0; s numShifts; s) { literals[s] x[p][d][s]; } model.addAtMostOne(literals); } }逻辑说明addAtMostOne是 CP-SAT 提供的高层约束等价于 Σx ≤ 1但底层实现做了更精巧的子句传播。换成手动累加再 addLessOrEqual 其实也行不过当班次数量多时前者性能略好。参数说明这里literals数组的元素类型是LiteralBoolVar 自动实现了这个接口。如果你是把 IntVar 转成布尔等价条件来传就要用model.newBoolVar()加model.addEquality()进行绑定直接强转会抛 ClassCastException。3.2 硬约束二连续工作天数不能突破上限如果要求每人连续出勤最多 5 天需要把「连续子序列约束」表达出来。CP-SAT 没有直接的「最长连续 1 序列」函数但可以通过滑动窗口求和实现任意连续 6 天窗口内总工作天数 ≤ 5。// workDay[p][d] 表示 p 在 d 天是否上班任意班次 IntVar[][] workDay new IntVar[numPeople][numDays]; for (int p 0; p numPeople; p) { for (int d 0; d numDays; d) { Literal[] shifts new Literal[numShifts]; for (int s 0; s numShifts; s) { shifts[s] x[p][d][s]; } workDay[p][d] model.newBoolVar(work_ p _ d); model.addBoolOr(shifts).onlyEnforceIf(workDay[p][d]); // 反向约束如果 workDay1 说明至少上一班 // addBoolOr 的 onlyEnforceIf 是一条单向蕴含需要反向补一条 model.addImplication(workDay[p][d], model.newBoolVar(tmp)); } }实际建模时会遇到一个典型的问题addBoolOr(...).onlyEnforceIf(workDay[p][d])表示的是「如果 workDay 为 1则至少有一个班次被选中」但反之不成立也就是说 workDay 为 0 时班次可能仍然是 1。为了解决这种双向关系我会用「sum 等式」来定义 workDay而不是靠蕴含LinearExprBuilder expr LinearExpr.newBuilder(); for (int s 0; s numShifts; s) { expr.add(x[p][d][s]); } model.addEquality(workDay[p][d], expr.build());注意这里用了LinearExpr.newBuilder()构造线性表达式将四个班次的变量累加然后赋值给 workDay。累加和只能等于 0 或 1因为有 addAtMostOne 约束所以 workDay 完美等价于「当天是否上班」。连续 6 天窗口约束写起来就干净了for (int p 0; p numPeople; p) { for (int d 0; d 5 numDays; d) { LinearExprBuilder window LinearExpr.newBuilder(); for (int k 0; k 6; k) { window.add(workDay[p][d k]); } model.addLessOrEqual(window.build(), 5); } }这个模式的复杂度是 人数 × 窗口数滑动窗口是排班问题里最典型的子序列约束写法。3.3 软约束让周末班次均匀分布硬约束保证可行性软约束则决定解的质量。比如「连续两周内每个人周末班次数差异要小」直接写成硬约束可能导致模型不可行所以一般做成目标函数的一部分或者带惩罚项的约束。软约束的经典做法是统计每个人在观察周期内被安排的周末班总数然后对这个总数和理想均值之差的绝对值做惩罚。绝对值在 CP-SAT 里可以通过辅助变量引入也可以用平方近似后者的线性化成本更高我更常用绝对值。// weekendCount[p] 为整数变量 IntVar[] weekendCount new IntVar[numPeople]; for (int p 0; p numPeople; p) { weekendCount[p] model.newIntVar(0, 6, wknd_ p); LinearExprBuilder expr LinearExpr.newBuilder(); for (int d : weekendDays) { for (int s 0; s numShifts; s) { expr.add(x[p][d][s]); } } model.addEquality(weekendCount[p], expr.build()); } // 辅助变量 dev 表示与均值的偏差 IntVar[] deviation new IntVar[numPeople]; int avgWeekend 2; for (int p 0; p numPeople; p) { deviation[p] model.newIntVar(0, 6, dev_ p); model.addAbsEquality(deviation[p], LinearExpr.term(weekendCount[p], 1).add(-avgWeekend).build()); }然后目标函数中就可以通过model.minimize(LinearExpr.sum(deviation))来引导求解器产生均匀的安排。这里addAbsEquality表示 deviation |weekendCount - avg|它是 CP-SAT 提供的现成绝对值封装不用手工拆段。4. 完整求解流程从数据准备到结果回填的落地代码4.1 从 CSV 读入人员与班次需求排班系统落地的第一步是接数据。一般工单系统导出的 CSV 包含员工 ID、姓名、可排班日期、班次偏好、最大每周工时。用 Java 解析时建议直接把数据映射成内部的三维布尔索引而不是在建模循环里再去做字符串匹配。MapString, Person people new HashMap(); try (Reader reader Files.newBufferedReader(Paths.get(people.csv))) { CSVReader csv new CSVReader(reader); String[] header csv.readNext(); String[] row; while ((row csv.readNext()) ! null) { Person p new Person(); p.id row[0]; p.name row[1]; p.weekMaxHours Integer.parseInt(row[2]); p.unavailableDays parseDays(row[3]); people.put(p.id, p); } }人员数据读入之后一般要检查一下不可用日期与全局法定节假日重叠的情况这类外生数据我习惯放到单独的 JSON 配置里不写死在代码中。4.2 决策变量创建参数的动态计算决策变量的上限范围需要提前估算。比如 IntVar 表示「某个人这个月的总工时」范围应该算出来而不是粗暴设置成 0 到 9999因为求解器的搜索域越大剪枝越难。动态计算起到「把域缩小到接近真实可行域」的作用。int minHours 80; int maxHours 120; IntVar[] totalHours new IntVar[numPeople]; for (int p 0; p numPeople; p) { LinearExprBuilder expr LinearExpr.newBuilder(); for (int d 0; d numDays; d) { for (int s 0; s numShifts; s) { expr.addTerm(x[p][d][s], shiftHours[s]); } } totalHours[p] model.newIntVar(minHours, maxHours, hours_ p); model.addEquality(totalHours[p], expr.build()); }addTerm表示给决策变量乘以一个系数此处为班次小时数后累加。把 totalHours 的上下界设为可接受范围一方面约束了可行性另一方面也给求解器提供了域的边界信息。4.3 求解器参数时间限制、并行线程与日志开关排班模型通常不一定非要最优解业务上能接受可行解加可解释性这时候求解器参数配置就是经验和玄学的结合点。CP-SAT 的参数入口是CpSolver配合SolverParameters。SolverParameters parameters SolverParameters.newBuilder() .setMaxTimeInSeconds(60.0) .setNumSearchWorkers(8) .setLogSearchProgress(true) .build(); CpSolver solver new CpSolver(); solver.solve(model, parameters);逻辑说明maxTimeInSeconds设置了 60 秒的求解上限CP-SAT 在这个时间内尽量返回当前最优可行解。80 人规模的排班一般在 20 秒内能出可行解最优解可能需要更多时间。numSearchWorkers是用来做并行搜索的工作线程数过多并不会线性加速因为线程间还有同步开销在大多数 CPU 上设成物理核数即可。参数说明logSearchProgress(true)会在标准输出打印不断更新的下界、上界和当前解信息。建议生产环境把它关掉否则日志量非常大。但如果模型难收敛打开日志排查会觉得它是救命稻草。另外一个经常被忽视的参数是setEnumerateAllSolutions它只用于需要收集全部解的场景比如你还要做公平性轮换不要和求解普通最优解混用。4.4 解的回填把求解结果写回排班表CP-SAT 求解完成后solver.value(x[p][d][s])返回决策变量当前解的值是 0 或 1。常见错误是直接用solver.solutionValue(x[p][d][s])这个旧 API会一直得到 0。新版里应优先用value()方法。ListAssignment assignments new ArrayList(); if (status CpSolverStatus.OPTIMAL || status CpSolverStatus.FEASIBLE) { for (int p 0; p numPeople; p) { for (int d 0; d numDays; d) { for (int s 0; s numShifts; s) { if (solver.value(x[p][d][s]) 1) { assignments.add(new Assignment(personIds[p], d, s)); } } } } }回填时还有一个常见问题由于解的唯一性没有保证只把排班结果写数据库不够建议把整个解的哈希值也存储起来方便后续对比不同参数跑出来的解差异。如果要把解导出为文本文件给其他系统做展示直接序列化 assignments 列表即可。4.5 校验求解结束不等于约束全部满足这一步我每次都会做从来不省。把求解结果回读一遍检查每一条硬约束是否被违反然后打印违规项。最优解未找到时会有 FEASIBLE 状态但硬约束必然满足如果不满足说明约束建模逻辑有漏洞而不是求解器的问题。int violations 0; for (int p 0; p numPeople; p) { for (int d 0; d numDays; d) { int assigned 0; for (int s 0; s numShifts; s) { assigned solver.value(x[p][d][s]); } if (assigned 1) { System.out.println(violation: p p d d); violations; } } }这段校验代码的价值在于它可以把模型层错误和业务层错误分开。每当我改动需求我会先跑校验再谈性能。排班系统最怕的其实不是求解不快而是求出来没人敢用——解合不合法跟解的质量高不高是两个问题这个校验步骤是我的固定程序。5. 常见问题排查求解慢、不收敛和结果反直觉的五个现场5.1 求解器长时间没有进展现象设置 120 秒时间上限日志里上界一直不变输出也没有新的解。原因目标函数中多个软约束的权重差异过大惩罚项数量级不在同一个尺度。比如每天工时不均匀的偏差作为误差值只有 0 到 2而偏好惩罚是 0 到 200优化器几乎把所有精力放在减小大项上对小项失去优化动力。解决将各软约束的量纲归一化到同一等级或者把每项目标拆出来线性加权偏好偏差乘以系数 1工时方差乘以系数 10。我一般用一个单独的配置类来维护权重表避免改权重就改代码。5.2 求出来的排班出现违背「常识」的连班现象某个员工被排了早班接晚班同一天两个班次人不可能连续工作 16 小时。原因约束条件里定义了每人每天最多一个班次但这个约束的对象索引写错了用了p而不是p1或者日期循环是d1错写成d。解决在建模循环里永远枚举打印小型化场景3 人 × 3 天 × 2 班肉眼扫一遍再投入全量数据。建议写一个 debug 方法能把约束用近乎自然语言打印出来大模型中这能省掉大量排查时间。5.3 结果里出现个别员工被「闲置」现象排班表里有一两个人一周全是空而其他人 6 天全排满原因看起来很怪。原因这是目标函数的设计问题。如果不把「工作天数均匀」作为软约束而只设了「满足每日最低需求」那么 CP-SAT 会倾向于使用尽可能少的人去覆盖需求剩余的人放空。浪费人力反而让目标更优。解决把「每人工作天数差异」加入目标函数做惩罚比如加入一个最小工作天数的硬约束或者将总工作天数作为软约束项加偏差惩罚。后者更接近实际情况因为我还要允许请假或特殊调班的场景。5.4 求解速度慢得离谱出乎预期现象20人 × 7天 × 3班的规模求解时间居然超过了 60 秒而一般这类规模应该秒出。原因决策变量x[p][d][s]虽然只有 420 个但workDay[p][d]变量和totalHours[p]变量之间用了乘法或非线性关系引入了新增的辅助约束搜索空间指数膨胀。另一个常见原因是没加addAtMostOne的约束等于允许了同一个人的多个班次同时为 1让组合数扩大。解决检查模型定义中所有 IntVar 变量之间的耦合方式。CP-SAT 对线性约束很顺手但非线性甚至乘法就需要额外变量来线性化。保证所有结构化约束都用 LinearExpr 表达避免通过乘法生成中间变量。5.5 同一份输入每次求解结果不同无法稳定复现现象参数没有变但运行两次结果不一样用户很不安。原因CP-SAT 的并行搜索在不同线程数情况下存在随机搜索行为即使numSearchWorkers固定某些策略下也会触发随机扰动。解决设置SolverParameters.newBuilder().setRandomSeed(0)并且在日志里输出求解器的版本源码哈希便于记录和复现。此外如果业务上只是需要尽快拿到可行解而不是最优解随机扰动反而能给你多种候选方案供业务抄选。6. 进阶把轮班公平性做成一个可迭代的闭环第一次建模时通常只关注「能不能排出来」跑通之后就要面对更现实的问题公平性和长期轮换。比如两个人连续三周的周末班次数完全一样导致某个员工心理不平衡或者夜班长期集中在少数人头上引起投诉。CP-SAT 解决这个问题的思路是把公平性指标动态序列化到目标函数按周期迭代求解。第一步是构建一个周期索引把 28 天拆成 4 个连续的轮转周期每个周期结束时统计每个人的夜班数、周末班数和总小时数并把上周期数据传入下周期的模型初始值。CP-SAT 不支持 Incumbent 热启动但变量赋初值可以显著加快求解方法是model.addHint()。for (int p 0; p numPeople; p) { for (int d 0; d numDays; d) { for (int s 0; s numShifts; s) { model.addHint(x[p][d][s], previousSolution[p][d][s]); } } }addHint的作用是告诉求解器一个大概率不错的解CP-SAT 会从该解出发执行邻域搜索。真实业务场景中前一周的排班结果与新一周需求的重叠度通常在七八成以上所以 hint 的加速效果非常明显。第二个进阶点是软约束权重的自动调节。我习惯写一个小工具类统计每一轮解出的各项指标方差然后自动根据方差调整权重如果周末班方差过高权重就上调如果总工时没问题权重就保持。这本质是闭环调节也符合实际排班管理者「看到问题就更新规则」的思考习惯。实际项目中某公司在做 80 人规模的排班时从手工 Excel 到 CP-SAT 自动求解经历了三个阶段最开始只求硬约束少被投诉的是一堆不合理的连班后来加了软约束均匀性求解时间涨了 3 倍最后通过 hint 权重自动调节把求解时间压回 30 秒内。从那以后我每做一个排班项目都会强制走一遍三问是否所有决策变量由数据驱动创建软约束权重是否有外部配置入口求解结果是否有独立校验脚本。如果这三个问题的答案都是肯定的那么这个项目不会出结构性的坑。希望帮到你。本文还有配套的精品资源点击获取 
长河君 · 2026/10/14 3:40:50 · 阅读 1.2k OR-Tools CP-SAT排班实战：Java API建模与求解器调优指南
简介基于谷歌优化工具OR-Tools的Java API这份人员排班问题建模与求解示例面向需要处理排班、调度场景的Java开发者与运筹优化入门者重点演示如何将班次需求、员工技能、工时限制等实际条件转化为整数规划模型并调用求解器获得最优或可行排班方案。资源为zip压缩包共4个文件含1个Java源文件和3个CSV数据文件班次表、需求人数矩阵等整包仅3KB轻量易读便于二次修改。已有978人浏览学习。示例代码按工程流程展示了模型构建、决策变量定义、约束添加、求解器配置与结果输出等完整环节并配有可直接运行的真实数据读者可据此理解此类工具在人员排班场景中的典型写法也能通过调整数据和约束迁移到门店调度、项目排期等同类问题是系统掌握优化建模与求解方法的实用参考。1. 人员排班用 OR-Tools 解决为什么手工排班总是效率低做过排班系统的开发者都清楚手工排班和用脚本去排是两回事。手工排班面对几十人、一周七天、两到三班倒的时候规则一多就开始互相打架——谁谁不能连班、谁谁周末必须休、工时不能超、账不能负全撞在一起。这本质是一个约束满足问题而 OR-Tools 就是 Google 出的一整套离散优化工具专门干这种事把约束翻译成数学模型再用 CP-SAT 求解器去找可行解甚至最优解。如果你在 Java 后端里开发排班、排产、排课这类模块并且已经受够了周末加班给每个人手动微调 Excel 表那这篇就是每个人的必读。本文从一个模拟项目 X 的实际拆解出发讲清楚 Java API 的建模思路、求解器参数怎么调、以及五个容易翻车的坑。2. Java API 快速上手先把依赖和头 100 行跑通2.1 依赖引入与工程结构我建议先从 Maven 开始本地开发环境用 JDK 11 及以上。OR-Tools 的 Java 包在 Maven Central 上有预编译版本Windows、Linux、macOS 都提供了对应的 native 库所以并不需要你自己编译 C 核心。dependency groupIdcom.google.ortools/groupId artifactIdortools-java/artifactId version9.11.4210/version /dependency引入依赖后第一步要做的不是写模型而是加载本地动态库。很多人为了这行代码折腾半小时因为 native 库加载失败时抛的异常和普通 jar 包冲突很像。import com.google.ortools.Loader; public class ShiftScheduler { static { Loader.loadNativeLibraries(); } // 后续模型代码 }逻辑说明Loader 做的事情是把 OR-Tools 的本地库从 jar 包中抽取到临时目录然后执行 System.load 加载。这个静态块要放在 class 的初始化中保证 JVM 加载类时最先执行。参数说明如果项目部署在内网环境且不允许 JVM 写临时目录可以通过环境变量JAVA_TMPDIR指定可写路径。另外注意某个版本的 protobuf-java 和 or-tools 的传递依赖可能会有版本冲突建议在 pom 里引入com.google.protobuf:protobuf-java的兼容版本。2.2 认识核心对象CpModel、BoolVar 与 Objective排班问题建模时最核心的对象就几个CpModel是模型的容器BoolVar是 0/1 决策变量IntVar是整数变量最终用CpSolver去求解。第一次接触 CP-SAT 的人容易把它和混合整数规划MIP搞混但其实二者的求解逻辑完全不同CP-SAT 大量依赖子句传播和冲突回溯更贴近图搜索所以在布尔约束密集的排班问题里优势很大。写一个最小模型验证环境CpModel model new CpModel(); BoolVar x model.newBoolVar(x); BoolVar y model.newBoolVar(y); model.addBoolOr(new Literal[]{x, y.not()}); model.minimize(x); // 求 x0 的可行解作为环境冒烟测试 CpSolver solver new CpSolver(); CpSolverStatus status solver.solve(model); System.out.println(status);这段代码的意思是设置两个布尔变量约束条件是 x 为真或者 y 为假至少成立一个目标函数让 x 最小。由于目标函数最小化时x0 是最优的所以 CP-SAT 会返回 OPTIMAL。注意model.minimize()接受 IntVar 或 LinearExprBoolVar 是 IntVar 的子类所以这里可以直接传。跑通这 100 行说明你的环境已经能执行 OR-Tools 的全部运算后续就可以放心建模了。2.3 数据模型设计人员、日期、班次的三维立方体排班本质上是给「人 × 日期 × 班次类型」这个三维空间里的每个元素赋 0/1 值。我们用布尔变量x[person][day][shift]表示某人某天某个班次是否被安排。这样的设计天然具备灵活性——每个格子可以是 0 也可以是 1约束就写在格子上。int numPeople 20; int numDays 7; int numShifts 3; // 早班、中班、晚班 BoolVar[][][] x new BoolVar[numPeople][numDays][numShifts]; for (int p 0; p numPeople; p) { for (int d 0; d numDays; d) { for (int s 0; s numShifts; s) { x[p][d][s] model.newBoolVar(x_ p _ d _ s); } } }构建三维数组时有个隐藏的陷阱如果你在循环里把变量名写成了不带索引的字符串比如x模型本身不会报错但调试时完全无法区分变量解出来也没法回填。变量名建议带上维度下标例如shift_p0_d6_s2转成模型导出 DOT 文件之后会非常直观。数据规模方面20人 7 天 3 班生成 420 个布尔变量这对 CP-SAT 来说是玲珑级问题。但如果做到 500 人 30 天 5 班次变量数就会飙到 7.5 万个这时候就必须依赖模式化约束和求解器参数来收敛了。3. 约束建模把排班规则翻译成 CP-SAT 的合法句式3.1 硬约束一每人每天最多轮一个班次排班里第一条必须满足的硬规则是同一个人同一天不能同时被安排早班和晚班。这句话翻译成约束是「对同一个人、同一天内所有班次的决策变量之和 ≤ 1」。for (int p 0; p numPeople; p) { for (int d 0; d numDays; d) { Literal[] literals new Literal[numShifts]; for (int s 0; s numShifts; s) { literals[s] x[p][d][s]; } model.addAtMostOne(literals); } }逻辑说明addAtMostOne是 CP-SAT 提供的高层约束等价于 Σx ≤ 1但底层实现做了更精巧的子句传播。换成手动累加再 addLessOrEqual 其实也行不过当班次数量多时前者性能略好。参数说明这里literals数组的元素类型是LiteralBoolVar 自动实现了这个接口。如果你是把 IntVar 转成布尔等价条件来传就要用model.newBoolVar()加model.addEquality()进行绑定直接强转会抛 ClassCastException。3.2 硬约束二连续工作天数不能突破上限如果要求每人连续出勤最多 5 天需要把「连续子序列约束」表达出来。CP-SAT 没有直接的「最长连续 1 序列」函数但可以通过滑动窗口求和实现任意连续 6 天窗口内总工作天数 ≤ 5。// workDay[p][d] 表示 p 在 d 天是否上班任意班次 IntVar[][] workDay new IntVar[numPeople][numDays]; for (int p 0; p numPeople; p) { for (int d 0; d numDays; d) { Literal[] shifts new Literal[numShifts]; for (int s 0; s numShifts; s) { shifts[s] x[p][d][s]; } workDay[p][d] model.newBoolVar(work_ p _ d); model.addBoolOr(shifts).onlyEnforceIf(workDay[p][d]); // 反向约束如果 workDay1 说明至少上一班 // addBoolOr 的 onlyEnforceIf 是一条单向蕴含需要反向补一条 model.addImplication(workDay[p][d], model.newBoolVar(tmp)); } }实际建模时会遇到一个典型的问题addBoolOr(...).onlyEnforceIf(workDay[p][d])表示的是「如果 workDay 为 1则至少有一个班次被选中」但反之不成立也就是说 workDay 为 0 时班次可能仍然是 1。为了解决这种双向关系我会用「sum 等式」来定义 workDay而不是靠蕴含LinearExprBuilder expr LinearExpr.newBuilder(); for (int s 0; s numShifts; s) { expr.add(x[p][d][s]); } model.addEquality(workDay[p][d], expr.build());注意这里用了LinearExpr.newBuilder()构造线性表达式将四个班次的变量累加然后赋值给 workDay。累加和只能等于 0 或 1因为有 addAtMostOne 约束所以 workDay 完美等价于「当天是否上班」。连续 6 天窗口约束写起来就干净了for (int p 0; p numPeople; p) { for (int d 0; d 5 numDays; d) { LinearExprBuilder window LinearExpr.newBuilder(); for (int k 0; k 6; k) { window.add(workDay[p][d k]); } model.addLessOrEqual(window.build(), 5); } }这个模式的复杂度是 人数 × 窗口数滑动窗口是排班问题里最典型的子序列约束写法。3.3 软约束让周末班次均匀分布硬约束保证可行性软约束则决定解的质量。比如「连续两周内每个人周末班次数差异要小」直接写成硬约束可能导致模型不可行所以一般做成目标函数的一部分或者带惩罚项的约束。软约束的经典做法是统计每个人在观察周期内被安排的周末班总数然后对这个总数和理想均值之差的绝对值做惩罚。绝对值在 CP-SAT 里可以通过辅助变量引入也可以用平方近似后者的线性化成本更高我更常用绝对值。// weekendCount[p] 为整数变量 IntVar[] weekendCount new IntVar[numPeople]; for (int p 0; p numPeople; p) { weekendCount[p] model.newIntVar(0, 6, wknd_ p); LinearExprBuilder expr LinearExpr.newBuilder(); for (int d : weekendDays) { for (int s 0; s numShifts; s) { expr.add(x[p][d][s]); } } model.addEquality(weekendCount[p], expr.build()); } // 辅助变量 dev 表示与均值的偏差 IntVar[] deviation new IntVar[numPeople]; int avgWeekend 2; for (int p 0; p numPeople; p) { deviation[p] model.newIntVar(0, 6, dev_ p); model.addAbsEquality(deviation[p], LinearExpr.term(weekendCount[p], 1).add(-avgWeekend).build()); }然后目标函数中就可以通过model.minimize(LinearExpr.sum(deviation))来引导求解器产生均匀的安排。这里addAbsEquality表示 deviation |weekendCount - avg|它是 CP-SAT 提供的现成绝对值封装不用手工拆段。4. 完整求解流程从数据准备到结果回填的落地代码4.1 从 CSV 读入人员与班次需求排班系统落地的第一步是接数据。一般工单系统导出的 CSV 包含员工 ID、姓名、可排班日期、班次偏好、最大每周工时。用 Java 解析时建议直接把数据映射成内部的三维布尔索引而不是在建模循环里再去做字符串匹配。MapString, Person people new HashMap(); try (Reader reader Files.newBufferedReader(Paths.get(people.csv))) { CSVReader csv new CSVReader(reader); String[] header csv.readNext(); String[] row; while ((row csv.readNext()) ! null) { Person p new Person(); p.id row[0]; p.name row[1]; p.weekMaxHours Integer.parseInt(row[2]); p.unavailableDays parseDays(row[3]); people.put(p.id, p); } }人员数据读入之后一般要检查一下不可用日期与全局法定节假日重叠的情况这类外生数据我习惯放到单独的 JSON 配置里不写死在代码中。4.2 决策变量创建参数的动态计算决策变量的上限范围需要提前估算。比如 IntVar 表示「某个人这个月的总工时」范围应该算出来而不是粗暴设置成 0 到 9999因为求解器的搜索域越大剪枝越难。动态计算起到「把域缩小到接近真实可行域」的作用。int minHours 80; int maxHours 120; IntVar[] totalHours new IntVar[numPeople]; for (int p 0; p numPeople; p) { LinearExprBuilder expr LinearExpr.newBuilder(); for (int d 0; d numDays; d) { for (int s 0; s numShifts; s) { expr.addTerm(x[p][d][s], shiftHours[s]); } } totalHours[p] model.newIntVar(minHours, maxHours, hours_ p); model.addEquality(totalHours[p], expr.build()); }addTerm表示给决策变量乘以一个系数此处为班次小时数后累加。把 totalHours 的上下界设为可接受范围一方面约束了可行性另一方面也给求解器提供了域的边界信息。4.3 求解器参数时间限制、并行线程与日志开关排班模型通常不一定非要最优解业务上能接受可行解加可解释性这时候求解器参数配置就是经验和玄学的结合点。CP-SAT 的参数入口是CpSolver配合SolverParameters。SolverParameters parameters SolverParameters.newBuilder() .setMaxTimeInSeconds(60.0) .setNumSearchWorkers(8) .setLogSearchProgress(true) .build(); CpSolver solver new CpSolver(); solver.solve(model, parameters);逻辑说明maxTimeInSeconds设置了 60 秒的求解上限CP-SAT 在这个时间内尽量返回当前最优可行解。80 人规模的排班一般在 20 秒内能出可行解最优解可能需要更多时间。numSearchWorkers是用来做并行搜索的工作线程数过多并不会线性加速因为线程间还有同步开销在大多数 CPU 上设成物理核数即可。参数说明logSearchProgress(true)会在标准输出打印不断更新的下界、上界和当前解信息。建议生产环境把它关掉否则日志量非常大。但如果模型难收敛打开日志排查会觉得它是救命稻草。另外一个经常被忽视的参数是setEnumerateAllSolutions它只用于需要收集全部解的场景比如你还要做公平性轮换不要和求解普通最优解混用。4.4 解的回填把求解结果写回排班表CP-SAT 求解完成后solver.value(x[p][d][s])返回决策变量当前解的值是 0 或 1。常见错误是直接用solver.solutionValue(x[p][d][s])这个旧 API会一直得到 0。新版里应优先用value()方法。ListAssignment assignments new ArrayList(); if (status CpSolverStatus.OPTIMAL || status CpSolverStatus.FEASIBLE) { for (int p 0; p numPeople; p) { for (int d 0; d numDays; d) { for (int s 0; s numShifts; s) { if (solver.value(x[p][d][s]) 1) { assignments.add(new Assignment(personIds[p], d, s)); } } } } }回填时还有一个常见问题由于解的唯一性没有保证只把排班结果写数据库不够建议把整个解的哈希值也存储起来方便后续对比不同参数跑出来的解差异。如果要把解导出为文本文件给其他系统做展示直接序列化 assignments 列表即可。4.5 校验求解结束不等于约束全部满足这一步我每次都会做从来不省。把求解结果回读一遍检查每一条硬约束是否被违反然后打印违规项。最优解未找到时会有 FEASIBLE 状态但硬约束必然满足如果不满足说明约束建模逻辑有漏洞而不是求解器的问题。int violations 0; for (int p 0; p numPeople; p) { for (int d 0; d numDays; d) { int assigned 0; for (int s 0; s numShifts; s) { assigned solver.value(x[p][d][s]); } if (assigned 1) { System.out.println(violation: p p d d); violations; } } }这段校验代码的价值在于它可以把模型层错误和业务层错误分开。每当我改动需求我会先跑校验再谈性能。排班系统最怕的其实不是求解不快而是求出来没人敢用——解合不合法跟解的质量高不高是两个问题这个校验步骤是我的固定程序。5. 常见问题排查求解慢、不收敛和结果反直觉的五个现场5.1 求解器长时间没有进展现象设置 120 秒时间上限日志里上界一直不变输出也没有新的解。原因目标函数中多个软约束的权重差异过大惩罚项数量级不在同一个尺度。比如每天工时不均匀的偏差作为误差值只有 0 到 2而偏好惩罚是 0 到 200优化器几乎把所有精力放在减小大项上对小项失去优化动力。解决将各软约束的量纲归一化到同一等级或者把每项目标拆出来线性加权偏好偏差乘以系数 1工时方差乘以系数 10。我一般用一个单独的配置类来维护权重表避免改权重就改代码。5.2 求出来的排班出现违背「常识」的连班现象某个员工被排了早班接晚班同一天两个班次人不可能连续工作 16 小时。原因约束条件里定义了每人每天最多一个班次但这个约束的对象索引写错了用了p而不是p1或者日期循环是d1错写成d。解决在建模循环里永远枚举打印小型化场景3 人 × 3 天 × 2 班肉眼扫一遍再投入全量数据。建议写一个 debug 方法能把约束用近乎自然语言打印出来大模型中这能省掉大量排查时间。5.3 结果里出现个别员工被「闲置」现象排班表里有一两个人一周全是空而其他人 6 天全排满原因看起来很怪。原因这是目标函数的设计问题。如果不把「工作天数均匀」作为软约束而只设了「满足每日最低需求」那么 CP-SAT 会倾向于使用尽可能少的人去覆盖需求剩余的人放空。浪费人力反而让目标更优。解决把「每人工作天数差异」加入目标函数做惩罚比如加入一个最小工作天数的硬约束或者将总工作天数作为软约束项加偏差惩罚。后者更接近实际情况因为我还要允许请假或特殊调班的场景。5.4 求解速度慢得离谱出乎预期现象20人 × 7天 × 3班的规模求解时间居然超过了 60 秒而一般这类规模应该秒出。原因决策变量x[p][d][s]虽然只有 420 个但workDay[p][d]变量和totalHours[p]变量之间用了乘法或非线性关系引入了新增的辅助约束搜索空间指数膨胀。另一个常见原因是没加addAtMostOne的约束等于允许了同一个人的多个班次同时为 1让组合数扩大。解决检查模型定义中所有 IntVar 变量之间的耦合方式。CP-SAT 对线性约束很顺手但非线性甚至乘法就需要额外变量来线性化。保证所有结构化约束都用 LinearExpr 表达避免通过乘法生成中间变量。5.5 同一份输入每次求解结果不同无法稳定复现现象参数没有变但运行两次结果不一样用户很不安。原因CP-SAT 的并行搜索在不同线程数情况下存在随机搜索行为即使numSearchWorkers固定某些策略下也会触发随机扰动。解决设置SolverParameters.newBuilder().setRandomSeed(0)并且在日志里输出求解器的版本源码哈希便于记录和复现。此外如果业务上只是需要尽快拿到可行解而不是最优解随机扰动反而能给你多种候选方案供业务抄选。6. 进阶把轮班公平性做成一个可迭代的闭环第一次建模时通常只关注「能不能排出来」跑通之后就要面对更现实的问题公平性和长期轮换。比如两个人连续三周的周末班次数完全一样导致某个员工心理不平衡或者夜班长期集中在少数人头上引起投诉。CP-SAT 解决这个问题的思路是把公平性指标动态序列化到目标函数按周期迭代求解。第一步是构建一个周期索引把 28 天拆成 4 个连续的轮转周期每个周期结束时统计每个人的夜班数、周末班数和总小时数并把上周期数据传入下周期的模型初始值。CP-SAT 不支持 Incumbent 热启动但变量赋初值可以显著加快求解方法是model.addHint()。for (int p 0; p numPeople; p) { for (int d 0; d numDays; d) { for (int s 0; s numShifts; s) { model.addHint(x[p][d][s], previousSolution[p][d][s]); } } }addHint的作用是告诉求解器一个大概率不错的解CP-SAT 会从该解出发执行邻域搜索。真实业务场景中前一周的排班结果与新一周需求的重叠度通常在七八成以上所以 hint 的加速效果非常明显。第二个进阶点是软约束权重的自动调节。我习惯写一个小工具类统计每一轮解出的各项指标方差然后自动根据方差调整权重如果周末班方差过高权重就上调如果总工时没问题权重就保持。这本质是闭环调节也符合实际排班管理者「看到问题就更新规则」的思考习惯。实际项目中某公司在做 80 人规模的排班时从手工 Excel 到 CP-SAT 自动求解经历了三个阶段最开始只求硬约束少被投诉的是一堆不合理的连班后来加了软约束均匀性求解时间涨了 3 倍最后通过 hint 权重自动调节把求解时间压回 30 秒内。从那以后我每做一个排班项目都会强制走一遍三问是否所有决策变量由数据驱动创建软约束权重是否有外部配置入口求解结果是否有独立校验脚本。如果这三个问题的答案都是肯定的那么这个项目不会出结构性的坑。希望帮到你。本文还有配套的精品资源点击获取