💥 💥 💞 💞 欢迎来到本博客 ❤️ ❤️ 💥 💥
🏆 博主优势： 🌞 🌞 🌞博客内容尽量做到思维缜密，逻辑清晰，为了方便读者。
⛳ 座右铭：行百里者，半于九十。
📋 📋 📋 本文目录如下： 🎁 🎁 🎁
目录
💥1 概述
📚2 运行结果
🎉3 文献来源
🌈4 Python代码实现
💥1 概述
灵活作业车间调度问题（FJSP）在现代制造业中起着至关重要的作用，广泛用于各种制造工艺，例如半导体制造，汽车和纺织品制造（Brucker和Schlie，1990，Garey等人，1976，Jain和Meeran，1999，Kacem等人，2002）。它是一个广义作业车间调度问题（JSP），是计算机科学和运筹学中经典的NP-hard组合优化问题。在 FJSP 中，作业由一系列特定的连续操作组成，其中每个操作都分配给一组兼容机器中的合格机器，以优化一个或多个目标，例如 makespan、平均完成时间、最大流量时间、总延迟等（Chaudhry and Khan，2016，Xie et al.，2019）。与 JSP 问题相比，FJSP 更加复杂和灵活，因为属于作业的操作可以分配给一台或多台具有不同处理时间的兼容机器。
目前，解决NP-hard组合优化问题的现有方法可以归纳为两类：精确方法和近似方法。精确的方法，如数学规划，在整个解空间中寻找最优解，但由于它们的NP硬度，这些方法很难在合理的时间内解决大规模的调度问题（Li，Pan，&Liang，2010）。由于 FJSP 实例的棘手性，越来越多的近似方法（包括启发式、元启发式和机器学习技术）被开发出来来解决现实世界问题的实例。通常，近似方法可以在计算工作量和结果计划的质量之间实现良好的权衡。特别是群体智能（SI）和进化算法（EA），如遗传算法（GA），粒子群优化（PSO），蚁群优化（ACO），人工蜂群等，在解决FJSP实例方面显示出优势。
尽管与精确的数学优化方法相比，SI和EA可以在合理的时间内解决FJSP，但这些方法在实时调度环境中并不适用，因为当底层算法需要大量迭代时，它们仍然可能遭受不可预测的极长计算时间以获得满意的解决方案。调度规则作为启发式方法的委托，广泛应用于实时调度系统，如考虑动态事件的中断。调度规则通常具有较低的计算复杂性，并且比数学规划和元启发式更容易实现。通常，用于解决FJSP的调度规则可以分为两个基本类别：作业选择规则和机器选择规则。这些规则的设计和组合旨在最大限度地减少调度目标，例如平均流时间、平均迟到和最大迟到。然而，有效的调度规则通常需要大量的领域专业知识和试错（Zhang等人，2020），并且无法保证局部最优（Luo，2020）。
最近，深度强化学习（DRL）算法为解决具有共同特征的调度问题提供了一种可扩展的方法。一些基于学习的工作（Bengio， Lodi， & Prouvost， 2021）专注于其他类型的组合优化问题，例如旅行推销员问题（TSP）和车辆路线问题（VRP），但尚不清楚DRL已被用于研究复杂的调度问题，例如FJSP。这种知识差距促使我们为FJSP开发基于学习的方法。
通常，RL 代理根据以下行为与环境交互：代理首先接收状态st并选择一个操作一个t根据每个时间步的状态，然后获得奖励rt并转移到下一个州st+1.在 RL 的设置中，操作一个t从操作空间中选择一个.然而，本文用作业操作动作空间和机器动作空间构造了FJSP的分层多动作空间，这意味着RL的一般设置不能应用于FJSP。为了求解 FJSP，此 RL 设置涉及作业操作操作空间和机器操作空间。特别是，两个操作空间具有层次结构而不是平行结构。在每个时间步长，RL 代理从其符合条件的操作操作空间中选择一个操作操作，然后从其兼容的计算机操作空间中为所选操作选择计算机操作。兼容的机器操作空间与选定的操作操作相关。图1显示了FJSP的分层结构动作空间的示例。它包含四个以绿色显示的作业操作操作，每个作业操作操作都有一个紫色的兼容计算机操作空间。
本文提出了一个端到端的深度强化框架，用于自动学习使用图神经网络解决灵活的作业车间调度问题 （FJSP） 的策略。在 FJSP 环境中，强化代理需要在每个时间步中安排属于一组兼容计算机中合格计算机上作业的操作。这意味着代理需要同时控制多个操作。这种多作用问题被表述为多重马尔可夫决策过程（MMDP）。为了求解MMDP，我们提出了一种多指针图网络（MPGN）架构和一种称为多近端策略优化（multi-PPO）的训练算法，以学习两个子策略，包括作业操作操作策略和机器操作策略，用于将作业操作分配给机器。MPGN 体系结构由两个编码器-解码器组件组成，它们分别定义作业操作操作策略和机器操作策略，用于预测不同操作和机器上的概率分布。我们引入了FJSP的析取图表示，并使用图神经网络嵌入调度过程中遇到的局部状态。计算实验结果表明，该智能体能够学习高质量的调度策略，在求解质量和 元启发式算法的运行时间上优于手工启发式调度规则。此外，在随机实例和基准实例上获得的结果表明，学习的策略在实际实例和具有多达 2000 个操作的更大规模实例上具有良好的泛化性能。
📚2 运行结果
🎉3 文献来源
部分理论来源于网络，如有侵权请联系删除。
