2. 调度问题建模：数学建模基础、变量与约束、目标函数定义
好，咱们进入正题。调度问题建模，说白了就是把一个实际的生产排程问题，翻译成数学语言。你想想看，车间里机器怎么分配、订单先做哪个、物料什么时候到位——这些在数学里就是变量、约束和目标函数。
我个人习惯，拿到一个调度问题，先不急着写代码。我会拿张白纸，把问题拆成三块：决策变量（我要决定什么）、约束条件（有什么限制）、目标函数（我要优化什么）。这三块搞清楚了，模型就搭好了八成。
2.1 数学建模基础：从实际问题到数学表达
数学建模，其实就是搭桥。桥的一头是车间里的真实场景，另一头是求解器能懂的数学公式。
我记得刚入行时，带我的老工程师跟我说过一句话，我一直记着：「建模不是越复杂越好，而是越准确越好。」你想想看，一个模型里塞了上百个变量，求解器跑三天三夜出不来结果，那还不如不建。
常见的调度问题类型，我列个表给你看：
| 问题类型 | 典型场景 | 核心难点 |
|---|---|---|
| 作业车间调度（JSP） | 多工序、多机器 | 工序顺序约束 |
| 流水车间调度（FSP） | 流水线生产 | 机器阻塞、等待时间 |
| 并行机调度（PMS） | 多台相同机器 | 负载均衡 |
| 项目调度（RCPSP） | 资源受限项目 | 资源冲突、工期约束 |
嗯，这里要注意：同一个实际问题，可以建出不同的数学模型。比如一个简单的流水线，你可以用离散时间模型，也可以用连续时间模型。选哪个？看你的精度要求和求解时间。
2.2 变量定义：把「做什么」变成数学符号
变量，就是你要决策的东西。在调度问题里，最常见的变量就两类：
- 二进制变量：表示「做」或「不做」。比如
x_{i,j,t} = 1表示工件 i 在机器 j 上、时刻 t 开始加工。 - 连续变量：表示时间、数量等。比如
C_i表示工件 i 的完工时间。
我在项目中遇到过一个问题：一个同事把所有决策都定义成二进制变量，结果模型变量数量爆炸，求解器直接内存溢出。后来我建议他把部分变量改成连续变量，问题就解决了。
举个例子，一个简单的作业车间调度，变量定义可以这样写：
// 决策变量定义
// x[i][j][k] = 1 表示工件 i 的第 j 道工序在机器 k 上加工
var x{i in JOBS, j in OPS, k in MACHINES} binary;
// s[i][j] 表示工件 i 的第 j 道工序的开始时间
var s{i in JOBS, j in OPS} >= 0;
// C[i] 表示工件 i 的完工时间
var C{i in JOBS} >= 0;你看，变量定义其实就是在回答三个问题：谁？在哪？什么时候？
2.3 约束条件：给问题戴上「紧箍咒」
约束，就是规则。没有约束的调度问题，那叫「随便排」。常见的约束类型，我总结了几种：
核心约束类型：
- 工序顺序约束：一个工件的后道工序必须等前道工序做完才能开始。
- 机器唯一性约束：同一台机器在同一时间只能加工一个工件。
- 资源容量约束：某种资源（比如工人、工具）的总使用量不能超过上限。
- 时间窗口约束：某些工序必须在特定时间范围内完成。
我曾经踩过一个坑：在建模时漏掉了一个「换模时间」约束。结果模型跑出来的排程方案，在车间里根本没法执行——因为换模具需要半小时，但模型以为机器可以无缝切换。嗯，从那以后，我每次建模都会列一个「约束检查清单」。
来看一个工序顺序约束的数学表达：
// 工序顺序约束：后道工序的开始时间 ≥ 前道工序的结束时间
subject to SequenceConstraint{i in JOBS, j in OPS: j > 1}:
s[i, j] >= s[i, j-1] + p[i, j-1];
// 其中 p[i, j-1] 是前道工序的加工时间机器唯一性约束稍微复杂一点，需要用到「大 M 法」：
// 机器唯一性约束：同一台机器上，两个工序不能同时加工
subject to MachineConflict{i1 in JOBS, j1 in OPS, i2 in JOBS, j2 in OPS, k in MACHINES:
i1 != i2 and x[i1,j1,k] = 1 and x[i2,j2,k] = 1}:
s[i1, j1] >= s[i2, j2] + p[i2, j2] - M * (1 - y[i1,j1,i2,j2])
or
s[i2, j2] >= s[i1, j1] + p[i1, j1] - M * y[i1,j1,i2,j2];这里 y 是一个辅助二进制变量，用来决定两个工序谁先谁后。M 是一个足够大的数。说白了，就是「要么你先做，要么我先做，不能同时做」。
2.4 目标函数：你到底想要什么？
目标函数，就是你的「指挥棒」。不同的目标，会导向完全不同的排程方案。
常见的调度目标有：
- 最小化最大完工时间（Makespan）：让整个批次尽快做完。这是最常用的目标。
- 最小化总拖期：让所有订单尽量不延期。
- 最小化总成本：包括加工成本、库存成本、换线成本等。
- 最大化设备利用率：让机器别闲着。
我个人建议，刚开始做调度建模时，先选一个目标。别贪多。多目标优化虽然听起来高大上，但实际求解时很容易陷入「顾此失彼」的困境。
来看一个最小化 Makespan 的目标函数：
// 目标函数：最小化最大完工时间
minimize Makespan:
max{i in JOBS} C[i];
// 或者用辅助变量简化
var MakespanVar >= 0;
subject to MakespanDef{i in JOBS}:
MakespanVar >= C[i];
minimize TotalMakespan: MakespanVar;你想想看，这个目标函数其实很直观——所有工件都做完了，最后一个工件完工的时间就是 Makespan。我们要让这个时间尽可能短。
小技巧： 如果你的目标函数里有「max」或「min」嵌套，建议用辅助变量展开。这样求解器处理起来更高效。我在一个项目里试过，展开后求解时间从 3 分钟降到了 20 秒。
2.5 知识体系框架图
下面这张图，是我自己总结的调度建模知识体系。你把它存下来，以后建模时对着看，基本不会漏东西。
避坑提醒： 建模时最容易犯的错误是「过度约束」。我曾经在一个项目里，把车间里所有细节都写进了约束——连工人上厕所的时间都考虑了。结果模型有 5000 多个约束，求解器跑了 8 小时没出结果。后来删掉了 30% 的非关键约束，15 分钟就出方案了。
记住：模型是现实的简化，不是现实的复制品。
好了，这一章的内容就这些。变量、约束、目标函数，这三块是调度建模的「三驾马车」。你把这章吃透了，后面讲求解算法时就会轻松很多。
本章要点回顾：
- 建模三要素：变量（做什么）、约束（限制什么）、目标（优化什么）
- 变量类型：二进制变量（0/1决策）、连续变量（时间/数量）
- 核心约束：工序顺序、机器唯一性、资源容量、时间窗口
- 目标函数：选一个主要目标，别贪多
- 建模原则：准确 > 复杂，简单模型更实用
公众号:蓝海资料掘金营，微信deep3321