并行批量机器上双代理调度的帕累托优化

《Expert Systems with Applications》：Pareto optimization of two-agent scheduling on parallel batch machines

并行批处理机调度中多目标Pareto优化研究，提出综合算法提升近似Pareto前沿质量。该算法融合四种启发式策略，在保证2-近似Pareto最优解的条件下，通过集成优化框架实现高精度Pareto解集生成，经实验验证优于NSGA-II算法。

　　本文探讨了在并行批处理机器上对两个竞争代理的作业进行调度的帕累托优化问题。作业具有相同的处理时间但不同的作业尺寸，目标是找到能够同时最小化两个代理完成时间（makespan）的帕累托最优解及其对应的调度方案。研究者通过分析和识别一个具有2近似帕累托最优保证的近似帕累托区域，提出了一种综合算法，以寻找高质量的近似帕累托最优解。实验结果表明，该算法在性能上优于广泛使用的非支配排序遗传算法（NSGA-II），并且所获得的近似帕累托前沿与真正的帕累托前沿非常接近。

研究的背景来源于热处理车间中不同订单的安排问题。热处理炉通过受控加热和冷却固体金属或合金部件，以改变材料的微观结构，从而进一步影响其机械性能，如硬度、强度、韧性、延展性和弹性。热处理炉的管理需要大量的努力，一方面，它作为并行批处理机器，可以同时处理多个部件，提高生产系统的吞吐量并平衡材料流动；另一方面，由于设备成本、能耗、安装空间限制和环保要求等因素，生产系统中并行批处理机器的数量通常不会超过一定数值。因此，与单件处理机器相比，并行批处理机器上的作业调度往往需要更长的处理时间。在实际操作中，一个批处理作业可能需要几个小时，而单件处理作业可能只需要几分钟。由此可见，并行批处理机器上的作业调度对整个系统的整体性能具有显著影响。

在本研究中，考虑了两种类型的订单：原始订单和新订单。原始订单已经安排在并行批处理机器上进行处理，但尚未开始执行；新订单则是在原始订单处理过程中到达，需要与原始订单竞争机器的使用。为了更好地描述这一场景，研究者引入了“代理”这一概念，每个订单由一组作业组成，每个代理希望自己的订单尽可能早地完成。虽然在调度决策中，来自两个代理的作业可以被视为无差异的，但最终的调度方案可能无法满足任何一个代理的需求。因此，生产管理者的目标是找到一种能够平衡两个代理完成时间的调度方案。

本研究的核心问题是在并行批处理机器上调度两个竞争代理的作业，使得两个代理的完成时间尽可能小。每个代理的完成时间定义为其订单中所有作业的最大完成时间。作业的处理时间相同，但尺寸不同，且所有作业的尺寸均不超过机器的容量。并行批处理机器可以在一批作业的总尺寸不超过其容量的情况下同时处理多个作业。一旦批处理开始，就不能中断或更改其处理过程，直到完成。因此，调度策略需要在确保作业尺寸总和不超过机器容量的前提下，合理安排作业的顺序和批次，以最小化两个代理的完成时间。

本文的主要贡献体现在以下几个方面：首先，通过分析帕累托最优解的性质，识别了一个覆盖帕累托前沿的近似帕累托区域，并且该区域内的所有近似帕累托解都能保证2近似帕累托最优的性能。其次，研究者设计了一种综合算法，在统一的框架下实现了多种启发式方法的更新、封装和组合。该算法将四种不同的启发式方法整合在一起，汇集所有已获得的近似帕累托最优解集，从而生成高质量的近似帕累托最优解集。最后，通过实验验证，该算法在性能上优于广泛使用的非支配排序遗传算法（NSGA-II），并且所获得的近似帕累托前沿与真实的帕累托前沿非常接近。

在问题建模方面，研究者将并行批处理机器视为能够同时处理多个作业的设备，其容量是有限的。每个作业的尺寸不同，但处理时间相同。批处理的处理时间等于该批中所有作业的最大处理时间，因此所有批处理作业的处理时间都为单位时间。一旦批处理开始，其处理过程就无法中断或更改。因此，调度策略需要考虑如何将不同尺寸的作业分配到不同的批次中，以最小化两个代理的完成时间。研究者还指出，由于问题的复杂性，该调度问题属于NP难问题，因此无法在多项式时间内找到精确的帕累托最优解集。因此，研究的重点在于设计高效的启发式方法，以在合理的时间内找到高质量的近似帕累托最优解。

为了验证所提出的综合算法的有效性，研究者进行了系统的实验设计。他们生成了具有代表性的随机实例，并在实验中调整了四个关键因素：机器容量、作业尺寸、总作业数量以及代理A的作业数量。机器容量被固定为100，即所有实例中的机器容量相同。作业尺寸则通过均匀离散分布生成，范围在1到100之间。总作业数量从10到100不等，每次增加10，即总作业数量为10、20、30、…、100。对于代理A的作业数量与总作业数量的比值，研究者分别设置了0.2和0.4两种情况，以模拟不同比例的作业分配。通过这些实验设置，研究者能够全面评估算法在不同条件下的表现，并验证其在实际应用中的有效性。

在实验结果中，研究者展示了所提出的综合算法在多个实例中的表现。算法能够有效地生成高质量的近似帕累托前沿，并且在大多数情况下，其结果与真正的帕累托前沿非常接近。此外，算法在计算效率方面也表现出色，能够在合理的时间内处理大量实例。相比之下，NSGA-II虽然在多目标优化问题中被广泛使用，但在本研究的特定问题上，其性能不如所提出的综合算法。这表明，针对并行批处理机器上的多代理调度问题，设计专门的启发式算法能够显著提高求解效率和解的质量。

研究者还探讨了帕累托前沿的近似方法。他们指出，帕累托前沿的性质对于调度问题的求解至关重要。由于帕累托前沿的复杂性，直接计算其所有点在计算上是不可行的。因此，研究者提出了一种近似帕累托区域的概念，该区域覆盖了帕累托前沿，并且可以在多项式时间内获得。此外，他们还引入了下界集合和参考集合，用于评估近似帕累托最优解的质量。下界集合提供了帕累托最优解的理论下限，而参考集合则用于比较不同算法在生成近似帕累托前沿时的表现。这些方法为后续研究提供了理论基础和实践指导。

在理论分析方面，研究者对帕累托最优解的性质进行了深入探讨。他们发现，由于作业的处理时间相同但尺寸不同，调度问题的复杂性主要来自于如何平衡两个代理的完成时间。研究者进一步分析了近似帕累托区域的覆盖范围和特性，并证明了该区域内的所有近似帕累托解都能保证2近似帕累托最优的性能。这意味着，即使无法找到精确的帕累托最优解，所提出的算法仍然能够在合理的时间内生成高质量的近似解。此外，研究者还对帕累托最优解的总数进行了上界分析，这为算法设计提供了重要的理论依据。

在算法设计方面，研究者提出了一个综合算法，该算法在统一的框架下整合了多种启发式方法。通过这种方式，算法能够动态更新和组合不同的启发式策略，从而提高求解的灵活性和效率。该算法的主要步骤包括：初始化解集、生成初始解、应用多种启发式方法改进解集、筛选高质量的近似帕累托最优解，并最终输出结果。在这一过程中，研究者特别强调了启发式方法的多样性和组合策略的重要性。不同的启发式方法适用于不同的实例特征，因此通过组合多种方法，可以提高算法的整体性能。

在实验设计中，研究者采用了多种方法来评估算法的性能。首先，他们比较了所提出的综合算法与NSGA-II在生成近似帕累托前沿时的表现。实验结果显示，综合算法在大多数情况下都能生成更接近真实帕累托前沿的解集，且计算效率更高。其次，研究者分析了不同参数设置对算法性能的影响，例如机器容量、作业尺寸、总作业数量以及代理A的作业数量比例。通过调整这些参数，他们能够验证算法在不同场景下的鲁棒性和适应性。此外，研究者还考虑了不同规模的实例，以确保算法能够在各种情况下都能有效运行。

本文的研究不仅具有理论价值，还具有重要的实际应用意义。在制造业和生产管理系统中，多代理调度问题是一个常见的挑战，尤其是在资源有限的情况下。通过合理安排作业的顺序和批次，生产管理者可以在满足多个代理需求的同时，优化整体生产效率。本文所提出的综合算法为解决此类问题提供了一种新的思路，其高效性和准确性能够帮助生产管理者在实际操作中做出更优的调度决策。此外，研究者所提出的近似帕累托区域和评估方法也为后续研究提供了重要的参考。

研究者还指出，未来的研究可以进一步探索该问题的扩展形式，例如考虑作业的优先级、处理时间的不确定性以及机器容量的动态变化等因素。此外，可以尝试将该算法应用于更复杂的生产系统，例如多台并行批处理机器、多代理竞争环境以及混合类型的作业调度问题。这些扩展研究将有助于提高算法的适用范围和实际价值。同时，研究者也建议进一步优化启发式方法的组合策略，以提高算法的计算效率和解的质量。

综上所述，本文在并行批处理机器上的多代理调度问题方面取得了重要进展。通过分析帕累托最优解的性质，提出了一种高效的综合算法，并验证了其在多个实例中的优越性能。研究者所采用的近似帕累托区域和评估方法为后续研究提供了理论支持和实践指导。此外，本文的研究结果对制造业和生产管理系统具有重要的实际意义，能够帮助生产管理者在资源有限的情况下，找到平衡多个代理需求的最优调度方案。未来的研究可以进一步拓展该问题的适用范围，并探索更高效的算法设计。