多目标局部搜索与NSGA-II融合解决双准则置换流水车间调度问题

简介：
在现代制造业中，生产流程要求在执行某个任务之前必须依次完成多个作业阶段。这种类型的问题被称为流水车间调度问题，在实践中具有重要的应用价值。置换流水车间调度问题（PFSP）因其广泛应用于工业生产而受到研究者的关注。该模型结构简单明了，并且能够解决各种工业场景下的调度优化问题，其解题方案丰富多样。对于给定的n个作业和m台机器，PFSP问题的目标是确定最优作业顺序，以实现两个关键指标——最大完成时间和最大延迟时间最小化的目的。本研究中提出了一种新的多目标局部搜索过程（MOLS），该方法与现有的NSGA-II算法相结合，用于解决双准则的排程问题。基于流水车间调度中的活性块特性，设计了MOINS和MOEXC两种新型邻域结构，以提高扰动效率。这些邻域操作对解的质量具有综合影响作用。在局部搜索过程中，MOLS通过系统性地调整邻域空间中的解来实现目标优化。该方法的搜索方向由MOINS与MOEXC之间的相互作用自然确定，并且无需预先设定任何参数。将所提出的MOLS策略与现有的多目标进化算法NSGA-II相结合，形成了新的求解框架NSGA-II-MOLS。通过在不同规模的实例上进行了广泛的实验分析，验证了该方法的有效性。大量对比实验表明，在保持相同种群规模和参数设置的前提下，NSGA-II-MOLS展现出显著的优势，能够更有效地逼近最优解集。 在本研究中，MOLS与NSGA-II算法相结合的方法被用来解决具有两个目标的置换流水车间调度问题。该问题旨在最小化两个主要指标，即最大完工时间和最长延迟时间。为了解决这一难题，本研究开发了一种基于MOINS和MOEXC的新型邻域结构。其中，MOINS负责执行插入操作，而MOEXC则处理交换操作。值得注意的是，该方法无需人工设定参数调节，从而实现了对置换流水车间调度问题的高效求解。基于流水车间调度问题的复杂性及其NP难特性特征，该研究选择了遗传算法这一类启发式算法作为解决方案。该算法遵循自然选择和遗传学理论基础，并通过一系列运算机制在解空间中进行搜索。由于其非确定性和随机性特点，使得该算法能够突破传统局部优化框架的限制，在全局范围内寻求最优解。NSGA-II算法作为一种多目标优化方法之一，它采用非支配排序策略对解进行分类处理，这种特性使其能够有效保留多样化的潜在解，并特别适用于求解具有多个目标函数的复杂优化问题。在这一研究中，NSGA-II-MOLS混合策略的提出即是将NSGA-II算法与MOLS相结合，在实现全局搜索的同时，通过MOLS方法对特定候选解进行局部精细化探索，从而实现了全局搜索与局部细化搜索的有机统一。流水车间（Flow Shop）是一种生产调度模式，在工业工程和运筹学领域具有广泛应用。多目标遗传算法（multi-objective genetic algorithm, MOGA）被广泛应用于解决复杂的多目标优化问题，其核心在于生成一组在多个目标维度上相互独立的最优解集合，即Pareto front。其中，makespan指的是最长完成时间，在生产调度中被视为关键性能指标之一，因为它直接反映了系统处理所有作业的整体效率。另一个重要参数是maximum lateness（最大延迟时间），它定义为所有作业中最迟的一个完成时间点，对于提高系统的准时性具有重要意义。该研究论文提出了一种新的解决途径，为求解多目标置换流水车间调度问题提供了一个有效的解决方案框架。该方法在解空间搜索中实现了对全局和局部优化的有效平衡，并通过动态调整参数以适应不同规模的问题实例，从而提高了算法的鲁棒性和适用性。同时，基于大量实验数据的验证表明，所提出的策略能够显著提升求解效率和解质量，在理论研究与实际应用领域均具有重要的参考价值。