2. 生产排程基础
在进入算法与求解器工程之前，必须先建立一套“共同语言”。生产排程之所以复杂，往往不是算法本身难，而是问题边界没有被描述清楚：车间属于哪种类型、任务如何流动、约束来自哪里、优化目标是什么。如果这些基础概念混淆，后续无论用启发式规则还是混合整数规划，都会出现“模型与现场不一致”的致命问题。本节从车间类型、调度术语、性能指标和约束分类四个维度，搭建排程问题的标准描述框架。
一、核心原理：车间类型决定问题结构
车间类型描述的是“工件在设备之间的流动方式”，它直接决定可行解空间的大小和求解难度。最常见的分类包括：
- 单机调度（Single Machine）：所有任务在同一台设备上加工，只需决定加工顺序。它是理解调度规则的起点，例如 SPT（最短加工时间优先）可最小化平均流程时间。
- 并行机调度（Parallel Machines）：多台功能相同的设备并行工作，任务分配到某台机器并排序。关键问题是分配均衡与负载平衡。
- 流水车间（Flow Shop）：所有工件按相同工艺顺序经过多台设备，如先车削、再铣削、后热处理。顺序固定，难点在于设备间的等待与阻塞。
- 作业车间（Job Shop）：每个工件有自己独立的工艺路线，设备访问顺序不同。这是最经典也最难的排程问题之一，解空间呈组合爆炸。
- 开放车间（Open Shop）：工序没有固定先后顺序，可自由选择加工次序，常见于检测、返修等场景。
此外，实际生产中还存在柔性作业车间（FJSP），即同一道工序可由多台不同设备完成，需要在“选机”和“排序”之间联合决策。车间类型一旦确定，问题的数学结构、约束形式和适用算法范围就基本确定。
二、调度术语：建立精确的问题描述
调度领域有一套标准术语，用于无歧义地描述问题。常用术语包括：
| 术语 | 含义 | 示例 |
|---|---|---|
| 工件（Job） | 需要完成的生产任务 | 订单 A、批次 B |
| 工序（Operation） | 工件的一道加工步骤 | 车削、钻孔、装配 |
| 机器（Machine） | 执行工序的资源 | CNC-01、装配线 2 |
| 加工时间（Processing Time） | 工序占用机器的时间 | pij = 45 min |
| 释放时间（Release Time） | 工件最早可开始时间 | 物料 8:00 到齐 |
| 交货期（Due Date） | 承诺完成时间 | 订单 18:00 前交付 |
| 完工时间（Completion Time） | 工件最后工序结束时间 | Cj |
| 拖期（Tardiness） | 超过交货期的时长 | Tj = max(0, Cj − dj) |
在学术表达中，常用三元组 α|β|γ 描述调度问题：α 表示机器环境，β 表示约束与特征，γ 表示目标函数。例如 Jm || Cmax 表示作业车间、无额外约束、最小化最大完工时间。掌握这套记号，能快速判断问题属于哪一类，并检索对应的算法与求解器配置。
三、性能指标：优化目标必须可量化
排程不是“排得好看”，而是要在明确目标下求最优或近优。常见性能指标分为三类：
- 时间类：最大完工时间 Cmax、平均流程时间、平均等待时间。适合关注产能与交付速度的场景。
- 交付类：最大拖期 Tmax、总拖期 ΣTj、拖期工件数。适合订单交付导向的车间。
- 成本类：换型次数、在制品库存、设备利用率、能耗。适合精益与成本控制场景。
关键提醒：多目标之间往往冲突。例如最小化 Cmax 可能增加换型次数，最小化拖期可能降低设备利用率。工程上通常采用加权求和、分层优化或帕累托前沿分析，而不是追求单一指标的极致。
四、约束分类：区分硬约束与软约束
约束是排程可行性的边界。按性质可分为：
- 硬约束：必须满足，否则解不可行。如设备同一时刻只能加工一个工件、工序先后顺序、物料可用时间。
- 软约束：尽量满足，允许违反但需付出惩罚。如优先客户订单、尽量减少换型、避免夜班。
- 工艺约束：由产品工艺路线决定，如必须先热处理后精加工。
- 资源约束：设备、模具、人员、夹具的可用性与容量限制。
- 时间约束：班次日历、维护窗口、释放时间与交货期。
在建模时，硬约束进入可行域，软约束进入目标函数。很多排程失败案例，都是因为把软约束误当硬约束，导致模型无解；或把硬约束当软约束，导致排出的计划现场无法执行。
五、案例场景：从订单到排程描述
假设某机加工车间收到 3 个订单，设备为 2 台 CNC。订单 A 工艺为“车→铣”，订单 B 为“铣→钻”，订单 C 为“车→钻”。这是一个典型的作业车间问题。若忽略换型时间，目标是最小化最大完工时间，则可描述为：
问题类型：Job Shop
机器数：2（CNC-01, CNC-02）
工件数：3（A, B, C）
目标函数：min Cmax
硬约束：
1. 每台机器同一时刻仅加工一个工序
2. 同一工件的工序按工艺顺序执行
3. 工序不可抢占
软约束：
1. 优先完成交期最近的订单
2. 减少同机器上的换型次数有了这段结构化描述，才能进一步选择求解器：小规模可用 CP-SAT 或 OR-Tools，大规模则需启发式或元启发式配合仿真评估。
六、误区与复盘
常见误区一：把流水车间当成作业车间建模，导致约束冗余、求解变慢。
常见误区二：只关注 Cmax，忽略拖期与换型，排出的计划“产能高但交付差”。
常见误区三：约束未分类，硬软混在一起，模型无解时无法定位原因。
复盘方法：每次排程前，先用三元组写出问题类型，再列出硬约束清单和软约束清单，最后确认目标函数。这个“三分钟描述”能避免 80% 的建模返工。
本节建立的描述框架，是后续所有算法与工程实现的输入规范。只有先把车间类型、术语、指标和约束说清楚，才能让求解器“听懂”现场语言，输出真正可执行的排程方案。