作业车间调度 (GA)

什么是作业车间调度？遗传算法如何求解？

作业车间调度将多个作业的工序分配到机器上，确定最小化完工时间（makespan）或延迟的顺序。每个作业由特定机器上特定时间的有序工序组成。两个工序不能同时使用同一台机器。

JSSP是NP困难的。遗传算法通过进化候选调度的种群来求解。每条染色体编码工序顺序；POX交叉保留作业顺序同时组合父代；交换变异交换工序位置以探索新解。

JSSP在机加工、半导体制造和印刷等制造环境中至关重要。减少10-15%的完工时间可在无需资本投入的情况下直接提高产能。

Formula: 完工时间 = max(所有工序的完成时间) 延迟 = Σ max(0, 完成_j − 交期_j) GA: 种群初始化 → 适应度评估 → 父代选择 → POX交叉 → 交换变异 → 迭代

计算示例

3个作业、3台机器。作业1: M1(3)→M2(2)→M3(4)。作业2: M2(4)→M1(3)→M3(2)。作业3: M3(2)→M2(3)→M1(1)。最优makespan = 12。GA（种群100，代数200）通常找到此最优值或5%以内。

何时使用此计算器

• 生产计划员在使用共享设备的机加工车间调度多个作业以最小化完工时间时
• 制造工程师评估增加新机器或更改操作顺序对整体产能的影响时
• 印刷厂或半导体晶圆厂的调度员确定作业优先级以最小延迟满足客户交期时
• 运筹学研究员将GA调度与当前手动或优先规则调度方法进行基准比较时

应避免的常见错误

• 复杂问题的种群规模设置太小——10个以上作业和5台以上机器时，使用至少100-200个个体以维持遗传多样性并避免过早收敛
• 运行代数太少就接受次优解——监控适应度是否仍在改善；如果停滞则已收敛，如果仍在改善则增加代数
• 当存在释放时间和交期时忽略它们——没有这些约束，GA仅优化完工时间，可能产生违反实际时间要求的调度
• 不用不同随机种子多次运行GA——GA是随机的；单次运行可能陷入局部最优；运行3-5次取最佳结果

如何解读结果

• 如果总延迟为零，所有作业在交期前完成——调度可行，焦点应转向进一步缩短完工时间
• 如果完工时间接近瓶颈机器的处理时间总和，调度接近最优——改进空间很小
• 甘特图揭示机器上的空闲时间：大间隙表示调度低效或不可避免的顺序约束

相关标准与参考

• Garey, Johnson & Sethi (1976) — 确立了作业车间最大完工时间最小化的 NP 难性
• 最大完工时间(C_max)与总延迟 — 生产调度的标准目标函数
• 遗传算法(Holland, 1975) — 本工具用于搜索调度空间的元启发式类别

常见问题

如何设置GA参数以获得好的结果？

种群50-200，变异率0.05-0.15，200-500代开始。大种群探索更多解但更慢。10+作业的问题使用种群≥100、代数≥300。

makespan优化和延迟优化有什么区别？

makespan最小化专注于尽快完成所有作业——适合最大化产能。延迟最小化优先满足交期——对客户承诺至关重要。这两个目标可能冲突：最短makespan可能导致某些作业延迟。多目标优化可以平衡两者。