第6章 在约束条件下安排资源
工作阶段： 把任务、资源和限制组合成可执行的候选方案。
公共核心项目： 与AI协同开发一个本地运行的“设备维护工单排程器”。
核心技术： 实体与属性、硬约束与软约束（软目标）、先到先服务基线、约束搜索、启发式搜索顺序、独立可行性检查、无解解释和条件变更重算。
输入输出链： 工单与班组JSON → 字段校验 → 基线/约束搜索 → 候选排程或无解原因 → 独立验证 → 人工审批。
应用中的AI： 在小规模离散时段中搜索满足技能、班次和时间窗的工单组合，并在可行方案间比较加权等待的计算智能。
协助开发的AI： 帮助学生追问业务条件、把自然语言限制翻译成候选字段、生成和解释代码、分析无解以及完成限定修改的大语言模型。
人的责任： 确认任务、技能、时长、时间窗和优先级；批准任何条件变更；检查遗漏的现实约束；决定候选方案是否采用。
主要交付物： 任务合同、三个冻结场景、先到先服务基线、约束搜索器、独立验证器、真实运行报告、系统卡与一键验收。
明确边界： 程序不自动派工，不自行放宽期限、降低安全规则或修改优先级；“程序可行”只对当前已建模条件成立。
跨章关系： 第5章的预测量可以成为工单或资源需求输入；本章把它放进明确约束，不能把预测值当作确定命令。
学习目标
完成本章学习后，你将能够：
- 把排程委托写成目标、实体、属性、硬约束、软目标和审批责任明确的任务；
- 用先到先服务建立透明基线，解释它为何可能错过整体可行方案；
- 读懂一个枚举合法班组和开始时段的完整约束搜索程序；
- 使用独立检查器验证任务完整、技能匹配、时间窗和班组不重叠；
- 区分“程序故障”和“当前条件无可行解”，在批准变更后重新计算；
- 用正常、边界、陌生、故障与条件变更测试形成可复现交付。
项目导入
企业服务值班人员每天可能收到网络、配电、设施和环境等工单。每条工单有提交时点、所需技能、预计时长、最早开始和最晚完成；不同班组拥有不同技能和班次。按收到顺序逐条安排很直观，却可能让一个能由多组处理的长任务先占用稀缺班组，随后只有该班组能做的紧急任务反而无处安排。
本章要做的是完整的工单排程器，而不是让大语言模型写一张看似合理的日程表。程序读取工单与班组JSON，先验证字段，再运行“先到先服务”基线和约束搜索。搜索器只考虑满足全部硬约束的候选；如果找不到，输出无解而不是偷偷删任务。搜索产生方案后，另一个独立函数再次检查完整性、技能、时间窗、班次和重叠，最终由人审批。
配套正常场景有2个班组和6条工单，一个时段为30分钟。A组会网络与电气，B组会网络、设施与环境。较早提交的J01网络任务两组都能处理；较晚提交的J02电气任务只能由A组处理，且必须在前4个时段内完成。先到先服务若把J01给A组，会留下J02；约束搜索可以把J02先放A组，把J01交给B组，形成整体可行方案。
自然语言工单与班组条件
↓ 人工确认字段与责任
JSON场景数据
↓ 输入校验
┌──────┴────────┐
先到先服务 约束搜索
│ │
未排任务/候选 可行方案/无解
└──────┬───────────┘
独立硬约束检查
↓
条件变更记录与人工审批
建议用5—7学时。学生先手工尝试正常场景，体验局部顺序为何影响整体；再运行基线与搜索；随后逐段阅读数据表示、可行性检查和递归搜索；最后修改一个软目标或在批准记录中改变一个条件并重跑三个场景。核心路径只使用Python标准库，无需网络和第三方优化框架。
本章成果
- 一份明确目标、硬约束、软目标和审批权的任务合同；
normal.json、no_solution.json和condition_change.json三个冻结场景；- 一个先到先服务基线和一个完整的小规模约束搜索器；
- 一个与搜索逻辑分离的方案验证函数；
- 一份包含可行方案、未排工单、无解原因、目标值和搜索数量的真实报告；
- 正常、边界、陌生、故障与条件变更测试；
- README、数据卡、系统卡、完整代码和另一组复现记录。
AI协同开发路线
先向协助开发的AI说明工作问题，不要求它立即排表：“我们要安排设备维护工单。请只追问会改变可行性的条件，例如班组技能、班次、任务时长、最早开始、最晚完成和不可更改规则；把偏好与硬约束分开。”AI提出的问题由值班或设施责任人回答。若真实条件未知，数据中要标记待确认，不能让AI按常识补一个时长。
条件确认后，让AI先输出数据结构和反例。例如请它构造“一条工单本身时间窗小于所需时长”的无解样例，并解释程序应停止在哪里。再限定工程：“只用Python标准库；先实现字段校验、先到先服务、独立可行性检查，再实现约束搜索；无解不得删除任务；任何条件变化必须来自新场景文件。”学生检查结构后再生成完整代码。
运行时把实际场景、输出和测试结果交给AI，要求它指出基线失败的具体资源冲突，不接受“AI优化更聪明”这类空话。修改时可要求：“只把软目标中的最晚完成权重从0.1改为0.3，保持工单、班组、硬约束和搜索范围不变；给出差异和三场景回归。”学生审查后决定是否保留。大语言模型可以帮助编码，却不拥有延长期限、增加班组或降低安全规则的权限。
第一节 把工作目标和限制写成可检查的约束
一、从“排得更合理”到明确目标
“请把工单排得更合理”没有办法验收。合理可能指按提交顺序、优先紧急任务、减少等待、均衡班组，或满足承诺时间。不同目标会产生不同方案。本项目先规定硬条件：每条工单恰好安排一次；班组必须具备所需技能；任务在班组班次与自身时间窗内完成；同一班组的任务不能重叠。
在全部硬条件通过后，才比较软目标。本项目目标值为“按优先级加权的等待时段 + 0.1×最晚完成时段”。等待从工单最早开始到实际开始计算，优先级越高，延迟代价越大。0.1只是教学权重，用于在等待相同的方案间稍微偏向更早结束，不是通用管理标准。
硬约束决定方案能否执行，软目标只在可行方案之间排序。不能因为一个方案总等待更小，就允许它让电气任务由无资质班组处理。学生应把每条自然语言要求标为“硬、软、待确认”之一，并写出对应字段和责任人。
二、用反例检查约束是否完整
一条好约束应能被反例触发。技能约束的反例是把J02电气任务给不具备electrical技能的B组；时间窗反例是J02从时段3开始、时段6结束，却要求最晚时段4完成；完整性反例是方案看起来不冲突，但悄悄漏掉J05；重叠反例是A组同时执行两个任务。
反例还能暴露未建模条件。如果任务之间有“先断电检查、后恢复网络”的前置关系，当前数据没有predecessor字段，程序可行并不代表现场可行。此时应扩展合同、数据和测试，而不是把关系藏进提示词。现实中的地点路程、备件、人员休息和突发事件也未进入首版，系统卡必须如实列出。
三、无解不是失败措辞
当任务时长为5个时段，却要求在0—4内完成，任何排程都不可能满足。正确输出是“无可行解：J02时长超过自身时间窗”，并把改变期限、缩短任务或增加资源交给有权限的人。程序不能把时长改成4，也不能把最晚完成改成5后假装仍是原问题。
配套no_solution.json冻结这种冲突；condition_change.json明确记录责任人批准把J02完成上限由4调整为5，其他条件保持不变。两者是不同版本和不同决策，必须分别保存。
专业迁移卡：商业贸易与交通服务
商贸方向可安排订单拣选、复核和发货，技能改为库区或设备资格，硬约束包括截单时间与不可并行工序。交通方向可安排车辆维护工单，技能改为工种与资质，硬约束还包括工位、备件和安全锁定。预测到达量只能形成任务候选，正式时限和车辆安全规则必须由业务责任人批准。
第二节 把路线、工单或养护任务表示为可计算问题
一、把文字转成实体、属性和关系
工程位于resources/ch06/project/。每个班组含编号、技能集合、可用开始与结束；每条工单含编号、名称、所需技能、持续时段、最早开始、最晚完成、提交时点和优先级。一个时段为30分钟，但程序只计算整数槽位，避免在首版同时处理日期、时区和跨班次。
{
"job_id": "J02",
"name": "配电箱测温复核",
"skill": "electrical",
"duration": 3,
"earliest": 0,
"latest_finish": 4,
"submitted_at": 1,
"priority": 4
}
duration=3和latest_finish=4意味着合法开始只能是0或1。若A组在0—4被其他任务占用，J02便无法安排。程序先检查时长和时间窗是否为正、编号是否重复、技能是否有班组提供。输入无效时在搜索前失败，避免把数据问题误写成“算法找不到”。
二、先算人工基线
先到先服务按submitted_at排序，依次寻找列表中第一个具备技能且有连续空档的班组：
for job in sorted(jobs, key=lambda j: (j.submitted_at, j.job_id)):
chosen = None
for team in teams:
if job.skill not in team.skills:
continue
for start in range(
max(job.earliest, team.start),
min(job.latest_finish, team.end) - job.duration + 1,
):
if not overlaps(start, start + job.duration,
assigned[team.team_id]):
chosen = {"job_id": job.job_id,
"team_id": team.team_id,
"start": start,
"finish": start + job.duration}
break
if chosen:
break
它透明、快速，并尊重已编码硬约束，但只看当前工单，不为后面保留稀缺技能。正常场景中，J01最先提交且A组排在列表前，因此占用A组0—4；J02随后只能由A组处理，却已经没有能在时段4前完成的空档，基线留下J02。这个失败不是故意做差，而是清楚展示局部贪心与整体组合的差别。
三、状态空间和候选数量
每条工单可能选择不同班组和不同开始时段。任务数量增加时，组合数会快速增长。首版只处理不超过约8条工单的小规模整数时段，让学生能够看到完整搜索并核对每个候选。它不是大型生产调度器，也不声称适合几百条实时工单。
搜索使用“剩余空间最小、可选班组更少、优先级更高”的顺序先处理受限工单。这是启发式：它改变先搜索谁，通常更早发现可行方案；它没有删除任何合法班组和开始时段，因此在当前有限表示中仍检查全部完整组合。若以后加入剪枝，必须证明剪掉的分支不可能优于当前方案。
四、让表示本身接受测试
学生应先测试数据结构，而不是只测最后日程。正常输入检查字段齐全；边界输入把任务放在时间窗最后一个合法开始点；陌生输入加入未登记技能或跨日任务，系统应拒绝并要求扩展合同；故障输入使用负时长、重复编号、结束早于开始或空班组，程序应在搜索前明确停止。
DATA_CARD.md说明三份JSON都是课堂模拟，不含姓名、电话或真实位置。使用真实工单时应把权限、隐私、位置精度、技能资质、时长来源和变更历史纳入数据治理，不能把整个业务压成几列数字后忘记丢失了什么。
第三节 组合预测、规则与优化形成可行方案
一、完整最小搜索程序
scheduler.py中的递归函数每次选择一条受限工单，枚举所有具备技能的班组和合法整数开始时段。若与该班组已排任务重叠就跳过；全部工单安排后计算目标值并保留更好的完整方案。
def visit(index):
nonlocal best, explored
if index == len(ordered):
explored += 1
flat = sorted(
[item.copy() for values in assigned.values()
for item in values],
key=lambda a: (a["start"], a["team_id"], a["job_id"]),
)
score = score_schedule(jobs, flat)
if best is None or score < best["objective"]:
best = {"feasible": True,
"assignments": flat,
"objective": score}
return
job = ordered[index]
for team in teams:
if job.skill not in team.skills:
continue
latest = min(job.latest_finish, team.end) - job.duration
for start in range(max(job.earliest, team.start), latest + 1):
finish = start + job.duration
if overlaps(start, finish, assigned[team.team_id]):
continue
assigned[team.team_id].append(
{"job_id": job.job_id, "team_id": team.team_id,
"start": start, "finish": finish}
)
visit(index + 1)
assigned[team.team_id].pop()
学生要能指出：硬约束在哪里检查；为什么任务完成后要pop回退；explored只统计完整方案而不是所有递归节点；目标值为什么只能在可行方案之间比较。大语言模型可以解释递归语法，但学生要拿正常场景手工走一条分支。
二、用独立函数再次验证方案
不能因为方案由搜索器产生就默认正确。validate_schedule独立检查工单集合是否完全一致、技能是否匹配、开始和持续时长是否正确、结束是否越过工单或班组边界、同一班组是否重叠。搜索实现中的错误可能导致它认为自己满足了约束，独立验证提供第二道证据。
errors = validate_schedule(teams, jobs,
result["optimized"]["assignments"])
if errors:
raise AssertionError("搜索器产生无效方案: " + "; ".join(errors))
现实交付还需要人对照原工单检查：预计时长是否可信；技能是不是合法资质；位置路程是否遗漏；高风险任务是否应走另一条正式流程。程序验证只说明JSON世界内部一致。
三、读取本次真实运行
参考环境为Windows、Python 3.12.13，只使用标准库。run_scenarios.py --write-reference实际运行三个冻结场景，结果写入reports/reference_results.json。
正常场景中，先到先服务排出5条并留下J02，因而不可行。约束搜索枚举24个完整可行排程，找到目标值3.7的候选：J02由A组0—3处理；J01由A组3—7处理；B组依次处理J04、J03、J05和J06。独立验证没有发现技能、时间窗或重叠错误。
“24个完整方案”只是在当前整数时段、当前班组列表和当前硬约束下的数量。不能说搜索证明了现实世界最优，因为地点路程等条件没有建模。目标值3.7也没有自然单位，它用于同一合同内排序，不适合跨业务比较。
课堂中应把JSON、候选表和代码三者来回对应。第一组学生从结果中选J02，说明它为什么只能由A组处理、合法开始为何只有0或1；第二组故意把它放到时段2，再用验证器读出“超过硬时间窗”；第三组比较基线与搜索，指出问题不是提交顺序字段错误，而是基线把第一个可用班组当成最终选择。随后互换场景，不询问原作者，独立复现目标值和约束检查。这样的活动让学生真正理解表示与搜索，而不是只看程序输出一张排班表。
协助开发的AI可以把一条结果转换为解释草稿，但学生要逐项回查原数据。若AI声称B组也会电气，应以skills字段纠正；若AI说目标值3.7代表3.7小时，应指出该值是加权等待与0.1倍最晚完成的组合，没有独立物理单位。能够识别这种“语言听起来合理、数据却不支持”的说明，是AI协同开发的重要能力。
四、预测、规则和搜索各做什么
第5章模型可能预测下一日需求上升，这可以帮助形成工单数量或时长候选，但预测不是硬事实。确定性规则负责技能、时间窗、不可重叠等已明确约束；搜索负责组合合法选择；人确认预测、制度和现场现实。大语言模型可以协调开发文件，却不应直接输出一张无法验证的排程并称为“优化”。
如果预测不确定，可以建立高、低两种需求场景分别搜索，而不是把一个小数当作唯一未来。若某场景无解，报告应说明它在哪些条件下无解，并把增加班组、延长期限或拆分任务作为待审批选项。
第四节 在条件变化和无可行解时重新计算并解释取舍
一、冻结五类系统测试
这些场景和断言组成项目的固定测试。它们在修改搜索顺序、目标权重或数据校验前冻结，不能为了让新版本通过而删掉无解、陌生或故障样例。
正常测试使用6工单场景，要求搜索结果覆盖全部任务并通过独立检查。边界测试把任务放到最早或最晚合法时点，检查区间端点。陌生测试加入程序未支持的跨日、双人协作或未知技能，预期是拒绝并要求扩展表示，不是丢弃字段。
故障测试使用负时长、重复编号、无班组或错误JSON，程序必须在搜索前停止。无解测试使用J02“持续5、时间窗0—4”，要求明确写出冲突。条件变更测试把经批准的最晚完成改为5，其他条件不变，要求重新找到可行方案并保留变更记录。
一键验收如下：
cd resources\ch06\project
python acceptance.py
python schedule.py data\normal.json
python run_scenarios.py --write-reference
acceptance.py检查必需文件、Python语法、9项单元测试、三个冻结场景的SHA-256身份、命令行复现结果和参考报告，实际运行通常不足一秒。9项测试覆盖正常、无解、条件变更、最晚合法开始边界、未支持字段、错误JSON、负时长、重复编号/空班组和参考记录；它们共同落实本节的正常、边界、陌生、故障与条件变更五类系统行为。能启动脚本并不等于通过；当前运行还必须与冻结报告一致。
二、无可行解不是程序失败
在no_solution.json中，J02需要5个时段却必须在0—4完成。搜索没有完整方案，程序输出“J02时长5超过自身时间窗0—4”，完整方案数为0。这是正确识别业务冲突，而不是异常崩溃。
可选处理包括：由责任人延长完成时限；拆分为可以合法交接的任务；增加具备技能的班组；调整任务范围；或转正式人工应急安排。每种做法都改变合同，必须新建场景、说明批准人和生效范围。程序不得自动选择“最容易算”的放宽方式。
三、条件变化后重新计算
condition_change.json记录J02完成上限由4调整为5。重算后，先到先服务仍因顺序留下J02；约束搜索枚举4个完整方案，找到目标值4.6的候选：A组0—5处理J02，B组0—4处理J01、4—6处理J03。条件变化解决了单项时间窗冲突，却没有让基线自动变好，这说明方法和条件是两个不同变量。
本次实际结果均由run_scenarios.py生成并写入机器可读报告，不是依据代码手工推测。正常场景24个完整方案、无解场景0个、条件变更场景4个，分别回答“当前条件下能否排、为什么不能排、批准变化后如何重算”。
控制变量实验可以只把目标函数中“最晚完成权重”由0.1改为0.3，固定工单、班组、硬约束与搜索空间。修改前预测它可能在等待相同的方案间选择更早结束者，也可能因为当前数据没有并列而结果不变。学生让AI只改一行和相应测试，审查差异后重跑全部场景。
四、解释取舍并完成审批交付
面向值班人员的结果不应只是一串目标值。报告要列出每条工单、班组、开始/结束、等待、约束检查、未排任务和场景版本；无解时列出冲突而不是空表。每个候选都带“人工审批必需”和“禁止自动派工”。
完整交付包含README、任务合同、三份场景、数据卡、基线、搜索、验证、命令行入口、测试、真实报告和系统卡。另一组应能在无网络环境运行acceptance.py，复现正常场景24个完整方案、无解0个和变更场景4个，并解释这些数字的有限含义。
采用表示当前小规模合同内的候选排程通过全部验证；限用表示仍须人工确认现实条件；退回表示字段、约束、目标或复现不完整；停止表示权限、安全或数据条件不具备。本项目最终结论是当前模拟工单范围限用，不自动派工。
专业迁移卡：风景园林、设计与数字媒体
园林方向可安排养护任务，硬约束包括季节、天气、药剂资质和不可同时作业区域；设计与数字媒体方向可安排拍摄、剪辑、审校和发布，技能、设备、素材到位和审批是硬条件。AI生成的时长估计只能作为待确认输入。迁移时要重新建立真实实体与约束，不能只把“工单”替换成“作品”。
本章小结
本章完成了“数据—基线—约束搜索—独立验证—无解—条件变更—交付”的完整排程项目。先到先服务透明却可能因局部选择留下稀缺技能任务；约束搜索在当前小规模表示中找到整体可行方案；独立检查器防止搜索器自证正确；无解被当作有价值的业务结论，而不是由程序偷偷放宽条件。
应用中的智能是可检查的搜索，不是大语言模型写日程。协助开发的AI帮助把语言变成代码和测试，人负责约束真实性、条件变更和正式审批。真正的技术能力包括：知道什么能计算、什么尚未建模、为什么无解、谁能改条件，以及另一组怎样复现。
关键术语
- 实体：问题中的对象，如工单、班组和时段。
- 硬约束：任何可执行方案都必须满足的条件。
- 软目标：只在可行方案之间比较优劣的偏好。
- 软约束：允许以代价权衡的偏好，本章把它量化为软目标，不得覆盖硬约束。
- 先到先服务：按提交顺序逐个安排的透明基线。
- 约束搜索：枚举或构造满足约束的候选组合。
- 启发式：帮助更快找到候选的搜索顺序或经验，不等于保证现实最优。
- 可行解：满足当前已建模全部硬约束的方案。
- 无可行解：当前条件组合下不存在满足全部硬约束的方案。
- 独立验证：用与搜索分离的逻辑再次检查方案。
- 条件变更：经授权修改资源、期限、范围或规则并重新计算。
目标测试
- 下列哪一项属于硬约束？
A. 尽量少等待 B. 尽量早点结束 C. 班组必须具备工单所需技能 D. 页面颜色统一 - 正常场景中，先到先服务为什么留下J02？
A. J02没有名称 B. J01先占用唯一具备电气技能的A组 C. 搜索器删除J02 D. B组班次为空 - 启发式“先处理剩余空间最小的工单”在本项目中做了什么？
A. 自动放宽时间窗 B. 改变搜索顺序，但仍检查合法选择 C. 预测任务时长 D. 替人批准方案 - 找不到满足全部硬约束的方案时，系统应怎样处理？
A. 删除最低优先工单 B. 自动延长期限 C. 输出无解和冲突，等待责任人决定条件变更 D. 返回上次方案 - 判断并改错：“目标值更小的方案即使有一条工单超出时间窗，也可以采用。”
- 判断并改错：“搜索器自己生成的方案不需要独立验证。”
- 写出本项目三个硬约束和一个软目标，并说明分别由谁确认。
- 解释正常场景中为什么把J02先给A组、把J01留给B组能够恢复整体可行。
- 为排程器各设计一条陌生测试和故障测试，写出预期行为。
- J02持续5个时段、时间窗为0—4。请说明为什么无解，并提出两种必须经责任人批准的改变；说明改变后应重跑哪些测试。
答案编号：A3-6-01—A3-6-10。完整答案和评分要点统一放入书后“目标测试参考答案”。