车间有 4 台相同设备、12 个待加工订单，每个订单只有一道工序，加工时间已知，不允许抢占，完工才能交付。KPI 是总拖期 Σ max(0, C_i − d_i) 最小。请说明：(1) 你会选时间离散建模还是顺序（连续时间）建模，为什么；(2) 目标里的 max 是非线性的，怎么变成线性形式；(3) 如果从订单 A 换到订单 B 需要换型时间，且 A→B 和 B→A 不一样，模型要加什么。

面试官在考什么

判断候选人是否真的动手建过调度模型：时间建模方式对规模的影响、目标线性化、以及 sequence-dependent setup 的建模代价。

排产调度

回答框架 · 前两步

1. 时间离散建模的变量数约等于 设备 × 时间粒度 × 订单，粒度取到分钟会直接爆炸，取粗又会切掉可行解；12 订单 4 设备这种规模，顺序（先后）建模的变量数只跟订单数平方有关，通常更合适。但如果时间本身就是离散班次，离散建模反而更直观，要按场景选。
2. 目标线性化：引入 T_i，约束 T_i ≥ C_i − d_i 且 T_i ≥ 0，目标 min Σ T_i。两个不等式合起来保证最小时 T_i 恰为 max(0, C_i − d_i)；少了 T_i ≥ 0 会把提前完工记成负拖期。

同一能力域的其他题

• 你简历里用到了线性规划做工艺参数优化。请说明：当约束中出现「某两个参数不能同时取高值」这类互斥条件时，你是如何把它写进模型的？如果求解器返回 infeasible，你怎么定位是哪条约束导致的？
• 5 个工人、5 项任务的一对一指派问题，用 0-1 变量 x_ij 建模，目标是最小化总工时。你发现直接解 LP 松弛（把 x_ij ∈ {0,1} 放松成 0 ≤ x_ij ≤ 1）得到的解自动就是整数，根本不需要分支定界。现在客户加了一条约束：“任务 A 和任务 B 不能由同一个人做”，写成 x_Aj + x_Bj ≤ 1（对每个工人 j）。请说明：(1) 为什么原模型的 LP 松弛天然给整数解；(2) 加了这条约束之后还能不能保证，如果不能，你会怎么处理这个模型。
• 你需要为一个运输问题建模：10个供应点，20个需求点，最小化运输成本。原本的运输问题约束矩阵是全幺模的，LP松弛直接得到整数解。现在业务要求：每条运输路线如果使用，需要支付一次性固定费用（例如1000元），且每条路线有容量上限。请问：这个问题属于什么类型？LP松弛会得到什么性质解？如果LP松弛得到分数解，你如何判断是否需要精确求解整数解，还是可以用LP解四舍五入？
• 一个跨工厂的产能分配问题被建成线性规划：约 800 个变量、300 条约束，求解在秒级完成。但输出里出现“0.4 号产线”“1.7 个班组”这类不可执行结果。业务要求每周排一次、凌晨批处理窗口 30 分钟，且允许目标值比理论最优差 1%。你作为技术负责人，怎么判断哪些变量必须整数化、哪些可以保持连续？如果整数化后求解时间涨到小时级，你的降级路径和与业务的精度口径怎么定？请给出可落地的决策规则。
• 某车间只有一台设备，每天可用 6 机时、9 kg 原料。生产一件 A 用 1 机时、3 kg 原料，利润 5 元；生产一件 B 用 2 机时、1 kg 原料，利润 4 元。A、B 的产量必须是非负整数。请回答：(1) 写出这个整数规划模型；(2) 求出 LP 松弛的最优解和整数最优解，两者目标值差多少；(3) 有人说“先解 LP，再把结果四舍五入取整就行”，你同意吗？说明理由（本小题的数值是否恰好可行不影响你的结论）。
• 单机多周期生产计划模型里有一条约束 p_t ≤ M · y_t：p_t 是第 t 天的产量（连续变量），y_t 是设备当天是否开机的 0-1 变量，设备真实日产能上限是 120 件。同事把 M 直接写成 100000，理由是“写大一点免得约束误伤”。请回答：(1) 这样写会带来什么后果，为什么；(2) 你会怎么确定这个 M，并说明 M 必须满足什么条件，模型才和原意等价。