在现代工业和生产管理中，调度问题无处不在，它涉及如何最优地分配资源、机器和人力，以完成一系列作业。这不仅影响生产效率和成本，还直接关系到企业的竞争力和市场响应速度。然而由于调度问题的复杂性，特别是在存在多种约束和目标的情况下，实现最优调度成为一项巨大的挑战。无关平行机调度问题（UPMS）因其组合优化的本质，被认为是NP难题，需要在有限的时间内找到近似最优解。
11 月 13 日，来自意大利、西班牙多个高校和机构的专家团队联合发表论文《Exploring Multi-Agent Reinforcement Learning for Unrelated Parallel Machine Scheduling》展示他们的最新研究成果，他们为了应对上述这些复杂的调度问题，引入了多智能体强化学习（MARL）方法。强化学习作为机器学习的一种，通过让智能体与环境交互，从中学习最优策略。但是单一智能体在面对复杂问题时往往表现有限。多智能体强化学习通过多个智能体的协作与竞争，能够更好地处理复杂系统中的不确定性和动态性。特别是在UPMS中，多智能体方法可以利用多台机器并行处理多个任务，从而提高调度效率和资源利用率。
研究团队的研究主要贡献在于以下几个方面：
引入了MARL方法来解决UPMS问题，并设计了相应的强化学习环境，包括动作空间、观察空间和奖励函数的定义。 比较了多智能体方法与单智能体方法在不同场景下的表现，验证了MARL在复杂调度问题中的潜力和优势。 通过实证分析，展示了PPO算法在单智能体场景中的有效性，以及多智能体PPO算法在多智能体设置中的可扩展性。
研究团队由来自多个研究机构的专家组成，他们在物理学、计算机科学和人工智能领域都有深厚的背景和丰富的研究经验。团队成员Maria Zampella隶属于那不勒斯费德里科二世大学（University of Naples "Federico II"）物理系“埃托雷·潘奇尼”，那不勒斯，意大利。Urtzi Otamendi隶属于巴斯克技术研究联盟（BRTA）的Vicomtech基金会，多诺斯蒂亚-圣塞巴斯蒂安，西班牙；同时也隶属于巴斯克大学（UPV/EHU）计算机科学与人工智能系，多诺斯蒂亚-圣塞巴斯蒂安，西班牙。Xabier Belaunzaran隶属于巴斯克技术研究联盟（BRTA）的Vicomtech基金会，多诺斯蒂亚-圣塞巴斯蒂安，西班牙。Arkaitz Artetxe隶属于巴斯克技术研究联盟（BRTA）的Vicomtech基金会，多诺斯蒂亚-圣塞巴斯蒂安，西班牙；同时也隶属于巴斯克大学（UPV/EHU）计算机科学与人工智能系，多诺斯蒂亚-圣塞巴斯蒂安，西班牙。Igor G. Olaizola隶属于巴斯克技术研究联盟（BRTA）的Vicomtech基金会，多诺斯蒂亚-圣塞巴斯蒂安，西班牙。Giuseppe Longo隶属于那不勒斯费德里科二世大学（University of Naples "Federico II"）物理系“埃托雷·潘奇尼”，那不勒斯，意大利。Basilio Sierra隶属于巴斯克大学（UPV/EHU）计算机科学与人工智能系，多诺斯蒂亚-圣塞巴斯蒂安，西班牙。该团队跨学科和多机构的合作，使他们能够结合物理学与计算科学的优势，深入探索多智能体强化学习在复杂调度问题中的应用。
相关工作
作业调度是工业和服务领域中的一个核心问题，涉及将任务分配给机器或工人，以优化某些预定目标，如最小化完成时间或最大化资源利用率。调度问题的复杂性在于其多样化和多层次的约束条件，涵盖了生产制造、运输物流、项目管理等多个行业。例如，在制造业中，生产调度的主要目标是高效分配有限资源，以支持生产过程，通常面临着作业顺序、机器可用性和工人技能等多种限制条件。此外，作业调度问题往往需要处理大量的变量和限制条件，使得其求解过程充满挑战，尤其是在大规模、多任务的情况下，调度问题被归类为NP难题。
为了解决调度问题，研究人员提出了各种方法，包括启发式算法、元启发式算法和机器学习方法。在启发式方法中，贪婪算法和局部搜索方法被广泛使用，但它们通常只能找到次优解。元启发式算法，如遗传算法（GA）、蚁群优化（ACO）和粒子群优化（PSO），则通过模拟自然界中的进化或群体行为来找到更优的解。遗传算法通过选择、交叉和变异操作，生成新一代的候选解以逼近最优解；蚁群优化模仿蚂蚁在寻找食物时的路径选择，通过信息素更新机制来优化解；粒子群优化借鉴鸟群飞行的协同机制，通过调整个体和群体最优位置来迭代搜索最优解。
在机器学习方法中，神经网络和深度学习技术在作业调度中也显示出巨大潜力。深度强化学习（DRL）通过利用深度神经网络来逼近复杂的策略和值函数，从而实现对动态和不确定环境中的决策优化。然而，现有方法在处理大规模问题和适应多变环境时，仍然面临计算复杂性和泛化能力不足等挑战。
强化学习（RL）作为一种自适应优化方法，通过智能体与环境的交互，从经验中学习最优策略，具有处理动态任务调度问题的显著优势。RL方法能够应对环境不确定性，自动调整策略以适应变化。特别是多智能体强化学习（MARL）通过多个智能体的协作，进一步增强了对复杂系统的处理能力。每个智能体在独立学习的同时，还能通过交互共享信息，实现更好的全局优化。MARL在不确定和动态的生产环境中，能够有效提高调度策略的灵活性和效率，解决传统方法难以克服的规模和复杂性问题。
作业调度问题在各行业中的广泛应用和复杂性使其成为研究热点。现有的调度方法虽然取得了显著进展，但在应对大规模复杂问题时仍有局限。强化学习尤其是多智能体强化学习，以其自适应性和灵活性，为解决动态任务调度问题提供了新的思路和解决方案。
问题描述
不相关平行机调度问题（UPMS）是一类复杂的组合优化问题，广泛应用于生产调度和资源管理中。其主要目标是在多台机器上合理分配作业，优化特定目标，如最小化作业完成时间和资源利用率。与传统调度问题不同，UPMS考虑了机器之间的差异性，即不同的机器在处理相同作业时可能有不同的处理时间。这种差异增加了调度过程的复杂性，需要更高效的算法来寻找近似最优解。
图1：使用最优解决方案安排的示例：五个作业、两台机器和两名工人。时间线图分为机器作业（黄色）和工人机器（灰色）调度。
在描述UPMS问题时，研究团队引入了以下数学符号：
机器集：表示为 $M = \{m_i | i \in \{1, 2, ..., M\}\}$，其中 $M$ 是机器的总数。
作业集：表示为 $J = \{j_i | i \in \{1, 2, ..., J\}\}$，其中 $J$ 是作业的总数。
处理时间：在机器 $m$ 上处理作业 $j$ 所需的时间，表示为 $pt_{jm}$。
设置时间：在机器 $m$ 上从作业 $j_i$ 切换到作业 $j_k$ 所需的时间，表示为 $st_{jikm}$。
工人集：表示为 $W = \{w_i | i \in \{1, 2, ..., W\}\}$，其中 $W$ 是工人的总数。
工人与机器的兼容性：二元变量 $owm$ 表示工人 $w$ 是否能操作机器 $m$，其中 $owm = 1$ 表示兼容，$owm = 0$ 表示不兼容。
所需的工人人数：在机器 $m$ 上执行作业 $j$ 所需的工人人数，表示为 $r_{jm}$。
UPMS问题的主要目标是有效地将任务分配给机器，并确定每台机器上任务的执行顺序，考虑处理时间、设置时间和工人约束。优化目标包括最小化任务完成时间、减少设置时间和优化资源利用率。
为了更好地理解UPMS问题，研究团队提供了一个实际示例。在一个制造环境中，有三台机器（$M = 3$），处理五个作业（$J = 5$），工人数量为两人（$W = 2$）。通过如下表格展示了处理时间和所需的工人人数：
处理时间表格（$pt_{jm}$）：
所需工人人数表格（$r_{jm}$）：
通过分析这些表格，可以设计出一个调度方案，目标是最小化作业完成时间，同时优化设置时间和资源利用率。
这个实例展示了UPMS问题的复杂性和实际应用，帮助读者更好地理解该问题的解决方案及其在现实场景中的应用。这一部分对UPMS问题的定义、数学符号和实际应用场景的解释，为后续的算法设计和实验提供了坚实的基础。
强化学习环境
在强化学习（RL）环境中，几个关键概念构成了系统的基础：动作空间、观察空间和奖励函数。动作空间定义了智能体在每一步可能执行的动作集合。观察空间则描述了当前状态的信息集合，帮助智能体做出决策。奖励函数提供数值反馈，衡量智能体的动作对目标的贡献程度，从而引导其学习最优策略。
图2：强化学习系统的简化表示。
在单智能体方法中，环境由工厂的机器、待处理的作业以及可用资源组成。每个作业的特征包括处理时间、设置时间和资源需求，这些变量与目标函数相关联。单智能体环境的关键概念是作业槽，这是一组具有固定大小的候选作业，智能体在每个时间步考虑这些作业，而剩余作业则排队等候。
在单智能体框架中，动作表示将作业分配给机器。动作空间由作业-机器配对组成，其大小等于作业槽的大小乘以机器数量，再加上一个表示无动作的动作。当智能体选择无动作时，表示没有其他可执行的动作，环境进入下一时间步。
观察空间描述了策略确定最优动作所需的信息。在该环境中，观察表示为与当前决策步骤相关的每个作业-机器配对的基本信息数组。具体来说，每个作业-机器分配存储五个信息元素：剩余处理时间、可用资源、机器的总计划时间、作业的总执行时间以及执行作业所需的资源。定义观察空间的挑战在于确保输入与输出层的固定大小，以便适应神经网络架构的要求。
在多智能体方法中，每台机器被视为一个独立的智能体。通过减少观察和动作空间，这种方法简化了系统，专注于与每台机器相关的作业。在涉及多台机器的问题中，定义了多个智能体、动作空间和观察空间。
在多智能体框架中，每台机器作为独立的智能体，其决策仅限于可以在该机器上执行的作业。因此，动作空间由与该机器相关的作业定义，并保持与单智能体方法中的作业槽一致。
观察空间包括与该机器上可执行作业相关的信息，这种个性化的视角对于改进决策至关重要。每个作业的分配由五个值表示：剩余处理时间、可用资源、机器的总计划时间、作业的总处理时间以及执行作业所需的资源。
在多智能体方法中，集中协调至关重要。一个协调员维护包括所有智能体的全局视图，充当额外智能体，但具有全局观察的独特特征。这种全局观察汇总了所有智能体的个体观察，为系统的全局状态提供了视角。在需要协作策略以实现最佳结果的场景中，集中协调显得尤为重要。
通过以上对强化学习环境的详细描述，我们可以看出单智能体和多智能体方法在处理调度问题时各有优劣。单智能体方法适用于较小规模和相对简单的场景，而多智能体方法在应对复杂系统和大规模问题时显示出更高的灵活性和效率。
算法设计与比较
单智能体算法概述
深度Q学习（DQN）是一种基于Q-learning的算法，旨在近似最优动作值函数（Q函数），即在特定状态下执行每个可能动作所能获得的最高期望奖励。在交互阶段，智能体接收环境观察并使用Q网络决定最优动作，将经验记录到缓冲区。在学习阶段，从缓冲区随机选择一批经验训练深度神经网络，目标是最小化预测和实际Q值之间的差距。DQN算法通过使用目标网络稳定学习过程，并采用epsilon-greedy策略确保探索环境。在复杂环境中，DQN算法表现出色，超越了人类在多个Atari游戏中的表现。
优势演员-评论家（A2C）是一种演员-评论家算法的高级变体，利用优势函数稳定训练并减少方差。在这种方法中，演员表示策略函数，指导智能体的动作，评论家估计Q值函数。评论家和演员函数通过神经网络参数化。A2C有效结合了策略和价值方法，使其在连续动作空间中能够更快收敛。然而，A2C在训练过程中可能面临较高的方差，导致收敛速度变慢。此外，优势函数的实现需要利用两个值函数，可能增加计算复杂性和内存使用。尽管存在这些限制，A2C仍然是训练复杂环境中智能体的强大工具。
近端策略优化（PPO）是一种强化学习方法，通过在目标函数中引入约束作为惩罚克服传统策略梯度方法的缺点。PPO算法简化了TRPO算法的计算，增强了优化过程，允许间歇性违反约束。PPO采用裁剪替代目标函数，限制策略更新在信任区域内，保持优化过程的稳定性和可靠性。这种方法最小化了与初始策略的偏差，提高了向最优解收敛的可能性。PPO由于其多功能性和有效性，能够解决大规模问题，标志着强化学习算法的重大进步。
可掩蔽的PPO（Maskable PPO）是PPO方法的变体，通过无效动作掩蔽技术扩展。该策略防止在训练策略梯度算法时执行无效动作。相比于对无效动作赋予负奖励，通过使用掩码避免选择无效动作更有效，并且在具有大量无效动作的场景中不容易失败。研究表明，在处理大量无效动作时，这种方法具有可扩展性，尤其在复杂场景中。
多智能体算法概述
反事实多智能体策略梯度（COMA）是Foerster等人提出的一种多智能体演员-评论家方法，利用集中式评论家训练每个智能体的分散式演员。该方法通过估计单个智能体的反事实优势函数来解决多智能体奖励分配问题。反事实基线用于评估单个智能体的动作，同时保持其他智能体的动作不变。集中式评论家提供高效计算反事实基线的表示，优势函数计算使用集中式评论家确定反事实，当只有智能体a的动作改变时。
多智能体PPO（MAPPO）是由Yu等人提出的方法，利用PPO算法实现多智能体。每个智能体遵循标准PPO训练算法，通过添加集中值函数计算广义优势估计（GAE），执行PPO评论家学习过程。该算法在多智能体挑战中表现出色，具有较少的调优需求，并且在多样化的场景中展示了强大的性能。
多智能体信任域策略优化（MATRPO）是Li等人扩展TRPO方法以用于多智能体强化学习的算法。该方法将TRPO策略更新转化为分布式共识优化，优化基于局部观察和个体奖励的分布式策略，使智能体无需了解全局观察、奖励或策略。智能体仅通过点对点通信网络与邻居共享局部策略比例，无需集中控制。该方法在部分可观测问题中尤为重要。
实验设计与结果分析
实验环境与参数设置
研究团队的实验设计旨在评估多智能体强化学习（MARL）方法在不相关平行机调度（UPMS）问题中的表现。为此，研究团队设计了一系列实验环境，涵盖不同数量的机器、作业和工人，以确保结果具有广泛适用性。具体而言，实验场景包括30个作业（J=30）、12台机器（M=12）和60个工人（W=60），并设置作业槽约束为10。通过随机修改变量，如每台机器的处理时间、单位数量、资源需求和设置时间，引入动态元素，模拟实际操作中的变化。
图3：四个单代理模型在500万个时间步内的训练结果，显示了平均发作奖励作为指标。该线显示了多次训练运行的中心趋势和置信区间的估计值。
训练阶段的表现
在训练过程中，采用了多次运行，以暴露模型在各种操作条件下的表现。训练阶段生成了多个场景，使模型能够面对具有不同动态变量的环境，同时保持静态参数，如机器数量和作业槽，避免神经网络输入和输出大小的冲突。
单智能体模型的训练结果显示，Maskable PPO算法在初始阶段表现出色。通过有效选择动作，大大提高了学习过程的效率。训练结果显示，在训练的前几百万时间步中，Maskable PPO算法累积了较高的奖励。这是因为该算法通过掩码技术避免了无效动作，使其更快地学习到最优调度策略。
多智能体模型的训练结果则展现了MAPPO算法的强大性能。尽管与单智能体训练相比，多智能体强化学习方法需要更多时间来累积正奖励，但其在协调协作环境中的挑战得到了有效解决。训练结果显示，MAPPO算法在多个智能体同时学习的情况下，能够实现稳定且高效的调度策略。
图4:500万个时间步内多智能体模型的训练结果，显示了平均发作奖励作为指标。该线显示了多次训练运行的中心趋势和置信区间的估计值。
通过对比单智能体和多智能体模型的训练结果，可以看出在处理较小规模和相对简单的场景时，Maskable PPO算法表现出色，而在更复杂和大规模的环境中，多智能体方法显示出更高的灵活性和效率。
在具体性能方面，Maskable PPO和MAPPO算法在训练后的表现相当，均积累了接近100分的奖励。尽管MAPPO算法没有使用有效动作掩蔽技术，它能够在初期学习中区分可能和不可能的动作，并最终实现与Maskable PPO相当的性能。
对训练时间和奖励函数的影响
进一步调整奖励函数可以优化训练过程，使模型性能与预期目标更一致。学习曲线显示，延长训练时间可以提高性能，曲线在最后的时间步中并未收敛，表明仍有改进空间。这一验证过程足以展示两种方法在解决UPMS问题上的潜力和有效性。
图5：最佳单代理算法Maskable PPO和多代理算法MAPPO的训练结果比较。
单智能体和多智能体方法在不同场景下的性能各有千秋。单智能体方法在小规模问题中表现优异，而多智能体方法在处理大规模复杂问题时显示出强大的扩展能力。通过这些详细的实验设计与结果分析，可以看出多智能体强化学习在优化复杂调度问题中的巨大潜力。
结论与未来研究方向
研究团队研究展示了多智能体强化学习（MARL）在解决不相关平行机调度问题（UPMS）中的有效性，特别是在动态和复杂的生产环境下。通过对比单智能体和多智能体方法，研究表明，MARL在应对复杂调度问题时具有显著优势。具体来说，多智能体PPO算法在多智能体场景中表现出色，能够有效协调多个智能体的决策，实现高效调度。此外，Maskable PPO算法在单智能体环境中，通过掩蔽无效动作，显著提升了学习效率和调度性能。研究团队通过设计一系列实验，验证了不同算法在多种场景下的表现，提供了详实的数据支持。
随着生产制造和资源管理系统的复杂性不断增加，多智能体强化学习在调度问题中的应用前景广阔。MARL方法能够灵活应对动态和不确定的环境，适用于大规模和多任务的调度场景。例如，在制造业中，多个生产单元和工位的协同调度可以通过MARL实现，提升整体生产效率。在物流和运输领域，MARL可以优化车辆调度和路径规划，降低运营成本。此外，在项目管理中，MARL有助于资源的动态分配和任务的高效执行。
尽管研究团队研究取得了显著成果，但多智能体强化学习在调度问题中的应用仍面临一些挑战，需要进一步探索。未来的研究可以从以下几个方向进行深化。
进一步优化MARL算法，提升其在大规模问题中的计算效率和收敛速度。例如，探索新的奖励函数设计和策略更新方法，以提高学习过程的稳定性和性能。
研究如何在调度问题中引入更多的实际约束条件，如设备故障、工人休假等，提高算法的实用性和适应性。
深入研究多智能体之间的协作机制，提升其在高度动态和协作密集型环境中的表现。探索多智能体通信和协调策略，以实现更高效的调度。
将MARL方法推广到更多领域，验证其在不同应用场景中的通用性和有效性。例如，医疗资源调度、智能电网管理等。
研究团队的研究为多智能体强化学习在复杂调度问题中的应用提供了重要参考，展示了其在提升生产效率和资源利用率方面的潜力。未来的研究将继续推动MARL方法的发展，使其在更多领域发挥作用，实现更广泛的应用价值。（END）
参考资料：https://arxiv.org/pdf/2411.07634
波动世界（PoppleWorld)是噬元兽数字容器的一款AI应用，基于意识科学和情绪价值的理论基础，通过AI技术驱动帮助用户进行情绪管理的工具和传递情绪价值的社交产品，波动世界将人的意识和情绪作为研究和应用的对象，探索人的意识机制和特征，培养人的意识技能和习惯，满足人的意识体验和意义，提高人的自我意识、自我管理、自我调节、自我表达和自我实现的能力，让人获得真正的自由快乐和内在的力量。波动世界将建立一个指导我们的情绪和反应的价值体系。这是一款针对普通人的基于人类认知和行为模式的情感管理Dapp应用程序。
加入AI交流群请扫码加微信
