多目标变邻域搜索算法在单机排序问题中的应用

"这篇文章探讨了应用多目标变邻域搜索（VNS）算法解决具有不同交货期窗口的单机排序问题。作者对比了三种多目标算法，并对算法进行了强化，以优化总的加权提前/拖期和总的排队时间。通过在一系列中等和大型问题实例上的测试，结果显示提出的算法在解的质量上优于原始的多目标VNS算法。此外，文章还进行了统计分析以评估新方法的性能。关键词包括多目标优化、局部搜索算法和作业调度。" 在单机排序问题（SMSP）领域，研究通常聚焦于单一优化标准，如最小化最大完工时间、总生产时间和总延误。然而，实际操作中，决策者可能需要同时考虑多个相互冲突的目标。最小化完工时间可以提高吞吐量和资源利用率，而最小化流水时间有助于降低平均周期时间和在制品库存。另一方面，总拖期与作业的交货期密切相关，对于制造业系统的准时交付至关重要。 文章中介绍的多目标变邻域搜索算法（MOVNS）是一种局部搜索策略，其核心在于通过改变搜索区域来探索解决方案空间，以寻找满足多个目标的最优解。作者对原始的MOVNS算法进行了两方面的强化，提升了算法在处理不同交货期窗口下的排序问题时的表现。这种增强可能包括改进的邻域结构、更有效的接受准则或者对搜索过程的动态调整。 通过对一组实例进行计算实验，作者展示了提出的算法在解的质量上优于原版MOVNS。这些实验不仅验证了算法的有效性，还通过统计分析揭示了算法性能的稳定性以及与其他算法相比的优越性。这为实际应用中选择合适的调度策略提供了有力依据。 这项工作为解决具有复杂约束的调度问题提供了新的方法，特别是在考虑多种优化目标时。多目标优化算法的应用能够帮助制造业和其他领域的企业更好地平衡各种目标，以实现更高效的生产计划。