有效的启发式集合,用于安排新作业插入的灵活作业车间问题.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新作业插入问题,因为它们运行时间短,适合实时调度。
相关报告
-
4.41 MB 17页 智能制造混合人工蜂群算法解决灵活的作业车间调度问题.pdf
-
410.81 KB 6页 改进的Firefly算法优化的数据驱动作业车间调度系统调度特征选择.pdf
-
1.91 MB 28页 2024停机的隐性成本报告-全球企业2000强面临的4000亿美元的问题.pdf
-
2.44 MB 47页 平台经济下的新业态-女性灵活就业现状与需求调研报告-简知-2023.pdf
-
1.6 MB 4页 普华永道-食品饮料行业_防疫应变_疫情下的食品行业问题与对策_4页.pdf
-
1.22 MB 14页 大漂亮法案的三个重要问题-招商证券-20250706.pdf
-
6.54 MB 66页 全球视野下的中国创新药产业.pdf
-
1.47 MB 16页 关于提振消费问题的再思考:从苏超、Labubu等爆品看提振消费-德邦证券-202507.pdf
-
14.77 MB 61页 看见:短视频时代的生活服务业-中国社科院-2025.pdf
-
34.76 MB 97页 2025年数字经济下灵活就业发展研究报告-新京报-202605.pdf
-
9.67 MB 46页 奢侈品行业解析:从消费者变迁洞察品牌增长的原动力-数说故事-202506.pdf
-
7.98 MB 82页 2025年中国宠物行业市场报告——“它经济”的消费升级与市场洞察-毕马威-202506.pdf
-
9.48 MB 25页 企业中的人工智能.pdf
-
3.46 MB 79页 CMF中国宏观经济专题报告(第84期) 我国银发产业高质量发展的 机遇、挑战与策略选择.pdf
-
6.7 MB 78页 2025年人工智能就绪度白皮书-企业数智化转型的Al变.pdf
-
1.37 MB 38页 AI时代的商业进化蓝图-中欧国际商学院-202505.pdf
-
2.44 MB 23页 灵活就业群体调查暨2025年一季度灵活就业景气指数报告-蚂蚁集团-202505.pdf