有效的启发式集合,用于安排新作业插入的灵活作业车间问题.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.69 MB 21页 中观观察:行业协会眼中的现状与未来-华创证券-20250422.pdf
-
4.47 MB 40页 即时零售行业深度:电商的增量引擎,拥抱下沉市场新蓝海-华西证券-250416.pdf
-
3.87 MB 35页 实现全球数字就业的潜力.pdf
-
4.79 MB 55页 中国消费品和零售行业纵览2025:挖掘消费结构升级中的增长新机遇报告-德勤-202504.pdf
-
13.29 MB 66页 2025年基于大模型的企业架构建模助力银行数字化转型应用研究报告.pdf
-
4.94 MB 38页 美国发动“对等关税战”的影响-第一创业-202504.pdf
-
3.25 MB 13页 模块化研发在汽车及离散制造行业的实践之旅.pdf
-
5.63 MB 48页 快递行业电动化转型与运输效率优化的减排潜力.pdf
-
3.09 MB 22页 2025年如何进行有效的CMF用户研究以发现感官体验的新接触点报告.pdf
-
1.26 MB 15页 我国生产性服务业较快发展背后仍需关注三大问题 .pdf
-
6.99 MB 84页 2025年气候风险中的中国快递企业报告.pdf
-
9.33 MB 53页 2025电信行业150:《最有价值和最强大的电信品牌的年度报告》.pdf