有效的启发式集合,用于安排新作业插入的灵活作业车间问题.pdf

有效的启发式集合,用于安排新作业插入的灵活作业车间问题.pdf
本文研究了具有新作业插入的柔性车间调度问题(FJSP),该问题模拟了再制造环境。FJSP 的新作业插入包含两个阶段:初始化调度和每次新作业插入后的重新调度。文章提出了四种启发式组合用于解决具有新作业插入约束的 FJSP。 **1. 问题定义与建模:** * FJSP是经典车间调度问题(JSP)的扩展,增加了机器分配和操作顺序两个子问题。 * 机器分配是从候选机器集合中为每个操作选择一台机器。 * 操作顺序是调度所有操作在所有机器上以获得可行和令人满意的解决方案。 * 新作业插入模拟了再制造环境,其中返回的产品和返回时间是不可控的。 * 重新调度操作是必要的,当新作业到来并被插入到正在执行的调度方案中。 * 重新调度时间应该非常短,以确保在车间继续进行加工。 **2. 启发式算法与组合启发式算法:** 文章提出了几种解决FJSP问题的启发式算法,主要包括: * **机器分配启发式算法:** * MA1: 操作最小处理时间 * MA2: 局部最小处理时间 * MA3: 全局最小处理时间 * MA4: 最小完成时间 * MA5: 两步贪婪算法 * **操作序列启发式算法:** * OS1: 最长剩余工作量 * OS2: 最多剩余操作数量 * **组合启发式算法(EH):** 文章提出了四种组合启发式算法,基于对简单启发式算法的优势和劣势的分析: * EH1: 生成所有操作的机器处理时间表,并随机排列操作。 * EH2: 随机排列操作,并使用MA2启发式算法获取机器分配,并使用OS2启发式算法确定操作顺序。 * EH3: 随机选择机器,基于MA生成工作量,使用OS1确定操作序列,并使用MA4改善机器分配。 * EH4: 计算总操作数量,使用OS2确定操作顺序,并使用MA4进行机器分配。 **3. 实验设置与结果分析:** * 实验在8个实际的再制造企业案例上进行。 * 评估了11种启发式算法,包括简单启发式算法、组合启发式算法以及它们的组合。 * 使用最小值、平均值和标准差评估。 * 目标:最小化最大完成时间(Makespan)、平均的提前期和延误期(E/T)、最大机器工作负载(Mworkload)和总机器工作负载(Tworkload)。 * **初始化调度:** 通过比较11种启发式算法在不同目标下的结果,发现了一些表现较好的算法,如RMA2, MA4, EH1, EH2, EH3和EH4. * **重新调度:** 使用上述六种启发式算法进行新作业插入的重新调度,并计算相对百分比增量 (RPI) 和平均相对百分比增量 (ARPI) 来比较算法性能。 * 在makespan标准下,EH3 和 MA4 表现较好。 * 在 E/T标准下,RMA2 和 MA4 表现最好。 * 对于 Mworkload 和 Tworkload 标准,MA4 表现最佳。EH2 和 EH3 在这两个目标下也有不错的表现。 **4. 结论:** EH4 适用于小规模问题。RMA2, MA4, EH1, EH2 和 EH3 启发式算法在不同目标下均表现良好。EH4在小规模实例中表现良好,而EH2在 E/T 目标上表现最佳。总体来说,四种组合启发式算法适用于FJSP新作业插入问题,因为它们运行时间短,适合实时调度。
在线阅读 下载完整报告 | 375.44 KB | 11页
阅读和下载会消耗积分;登录、注册、邀请好友、上传报告可获取积分。
成为VIP会员可免费阅读和下载报告