Skip to content
返回搜索结果

作业车间调度

提出者
Pinedo, M. L.
年份
2016
类型
Combinatorial scheduling problem
类别
Optimization

本文为机器翻译,尚未经过审校。 阅读英文原文

字号

它有什么作用?

作业车间调度是指在时间维度上,将一组作业(任务)分配给一组机器(资源),同时遵守优先级和能力约束,以优化完工时间(总完成时间)、延迟或成本等绩效指标的问题。作业车间问题是运筹学中一个经典的组合优化问题,通过启发式方法(贪婪调度规则、模拟退火、遗传算法)和精确算法(分支定界、约束规划)来解决。它在制造业、项目管理和计算调度中具有基础性地位。

方法背后的直觉

设想一个拥有10台机器的小型机械车间。一个客户订单(作业)包含5个零件,每个零件都需要在不同机器上进行一系列操作:零件1需要在机器A上加工,然后在机器C上钻孔。零件2需要在机器B上钻孔,然后在机器D上焊接。所有零件最终汇集进行总装。挑战在于:在不超出机器能力、同时遵守每个零件操作顺序的前提下,调度所有操作以最小化总完成时间。如果零件1分配到机器A的时间过晚,机器C就会闲置。如果机器C超负荷,所有后续操作都会积压。作业车间问题捕捉了这种复杂性:对于100个作业和20台机器,可能的调度方案数量是天文数字,使得精确求解不切实际。因此,您需要使用启发式方法快速找到一个好的(不一定是最佳的)调度方案。

历史学

作业车间调度问题于20世纪50年代作为运筹学中的一个研究问题出现。Johnson (1954) 的开创性工作最优地解决了两机问题;Fisher和Thompson (1963) 创建了至今仍在使用的基准问题。该问题是NP-hard(在20世纪70年代被证明),这促使了启发式和元启发式方法的发展。现代方法包括约束规划(20世纪90年代至21世纪初)、遗传算法和混合方法。作业车间调度现在是一个成熟的领域,其应用已从制造业扩展到云计算、电信和交通运输。

何时使用

作业车间调度适用于任何具有多台机器/资源和具有不同操作序列作业的制造或服务环境。典型应用包括机械车间、印刷厂、半导体晶圆制造、医院(手术室调度)和项目调度。当作业复杂性高(每个作业有多个操作)、机器利用率至关重要或截止日期紧张时使用。在装配线环境(线性流程)或简单的单机操作中,其重要性较低。

局限与注意事项

  • 组合复杂性:找到最优解是NP-hard问题;实际解决方案需要启发式方法,这些方法可能无法达到全局最优
  • 启发式解决方案具有情境依赖性;适用于一个车间的规则可能在另一个车间表现不佳,需要进行调整和验证
  • 假设输入是静态的(固定的作业和机器);实际车间会遇到动态的作业到达、取消和设备故障,需要频繁重新调度
  • 调度稳定性:频繁的调度变更(由于新作业或中断)会增加成本并使与工人及客户的协调复杂化

来源中的条件不能替代独立的科学审查或分析引擎的验证。

优势

  • 能够处理简单调度规则无法应对的复杂、现实约束(优先级、机器能力、截止日期)
  • 针对相关的业务指标(完工时间、延迟、机器利用率)进行优化,而非采用临时规则
  • 能够快速响应中断;当机器发生故障或紧急作业到达时,重新调度算法可以生成修订计划
  • 数学公式允许进行敏感性分析和权衡探索(例如,延迟与完工时间)
  • 有高效的软件工具和成熟的元启发式算法支持

应用

  • 一家精密机械车间使用模拟退火的作业车间调度方法,调度15台数控机床上的200多个定制零件,将完工时间缩短15%,并将准时交货率从85%提高到95%
  • 一家半导体制造厂应用基于约束的调度方法管理500多个工艺步骤,涉及50台设备,从而最大限度地缩短晶圆周期时间,并将在制品库存减少20%
  • 一家印刷公司使用动态作业车间调度方法,将印刷作业分配给8台具有不同功能的印刷机,优化作业组合(大批量与专业化),并最大限度地缩短换型时间
  • 一家医院调度团队为手术室调度实施作业车间算法,协调外科医生、手术团队和设备,将手术室利用率从65%提高到82%

使用方式

使用方式

1

定义作业(订单、任务),包括操作序列、机器需求、加工时间和截止日期。定义可用机器及其可用时间窗口。

2

指定约束:操作优先级(零件1必须在完成操作A后才能开始操作B)、能力(每台机器一次只能处理一个作业),以及可选的发布时间和截止日期。

3

应用调度规则(例如,最短加工时间、最早截止日期、关键比率)来安排每台机器上的作业顺序,生成初始调度方案。

4

使用元启发式算法(模拟退火、禁忌搜索、遗传算法、蚁群优化)通过局部搜索或基于种群的方法改进调度方案。

5

评估调度方案的质量(完工时间、延迟、空闲时间、缓冲时间)。如果可接受,则实施;否则,调整参数并重新优化。

常见陷阱

  • 优化了错误的指标;最大化机器利用率可能会增加作业延迟,而满足所有截止日期可能需要大量的空闲时间
  • 忽略设置时间和换型时间;一个最小化空闲时间但需要频繁、耗时设置的调度方案在实践中可能不是最优的
  • 过度信任启发式调度方案而未根据实际车间行为进行验证;约束通常比模型捕捉的更复杂

常见问题

完工时间是什么,为什么它很重要?

完工时间是从第一个操作开始到最后一个操作完成的总时间。它与设备利用率、现金流(完成越快=付款越快)和客户满意度直接相关。最小化完工时间是作业车间调度中常见的首要目标。

静态作业车间调度和动态作业车间调度有什么区别?

静态调度假设所有作业都预先已知;您优化的是一组固定的作业。动态调度处理随时间到达的作业;当新作业到达或发生中断时,调度方案会进行修订。大多数实际车间都是动态的,需要快速的重新优化算法。

我们应该使用哪种调度规则?

没有单一的规则是绝对优势的。最短加工时间(SPT)最小化完工时间;最早截止日期(EDD)最小化延迟;关键比率则平衡两者。通过历史数据或模拟测试规则,以找到最适合您车间优先级和约束的规则。

作业车间调度能否处理工人技能和交叉培训?

可以,通过扩展资源模型:不再仅仅是“机器A”,而是指定“机器A与工人1”或“机器A与工人2”。然而,这会增加问题的复杂性;请确保您的调度软件支持多资源约束。

相关方法

参考文献

  1. Pinedo, M. L. (2016). Scheduling: Theory, algorithms, and systems (5th ed.). Cham: Springer.

    打开 DOI 文献
    已复制。
  2. Taillard, E. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2), 278-285.

    打开 DOI 文献
    已复制。