作业车间调度
- 提出者
- 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必须在完成操作A后才能开始操作B)、能力(每台机器一次只能处理一个作业),以及可选的发布时间和截止日期。
应用调度规则(例如,最短加工时间、最早截止日期、关键比率)来安排每台机器上的作业顺序,生成初始调度方案。
使用元启发式算法(模拟退火、禁忌搜索、遗传算法、蚁群优化)通过局部搜索或基于种群的方法改进调度方案。
评估调度方案的质量(完工时间、延迟、空闲时间、缓冲时间)。如果可接受,则实施;否则,调整参数并重新优化。
常见陷阱
- 优化了错误的指标;最大化机器利用率可能会增加作业延迟,而满足所有截止日期可能需要大量的空闲时间
- 忽略设置时间和换型时间;一个最小化空闲时间但需要频繁、耗时设置的调度方案在实践中可能不是最优的
- 过度信任启发式调度方案而未根据实际车间行为进行验证;约束通常比模型捕捉的更复杂
常见问题
完工时间是什么,为什么它很重要?
完工时间是从第一个操作开始到最后一个操作完成的总时间。它与设备利用率、现金流(完成越快=付款越快)和客户满意度直接相关。最小化完工时间是作业车间调度中常见的首要目标。
静态作业车间调度和动态作业车间调度有什么区别?
静态调度假设所有作业都预先已知;您优化的是一组固定的作业。动态调度处理随时间到达的作业;当新作业到达或发生中断时,调度方案会进行修订。大多数实际车间都是动态的,需要快速的重新优化算法。
我们应该使用哪种调度规则?
没有单一的规则是绝对优势的。最短加工时间(SPT)最小化完工时间;最早截止日期(EDD)最小化延迟;关键比率则平衡两者。通过历史数据或模拟测试规则,以找到最适合您车间优先级和约束的规则。
作业车间调度能否处理工人技能和交叉培训?
可以,通过扩展资源模型:不再仅仅是“机器A”,而是指定“机器A与工人1”或“机器A与工人2”。然而,这会增加问题的复杂性;请确保您的调度软件支持多资源约束。