求解带序列相关启动时间的单机调度问题的联合邻域搜索算法
Neighborhood Combination Search for Single-Machine Scheduling with Sequence-Dependent Setup Time
-
摘要: 在局部搜索算法中，其最重要的特征之一是其邻域的定义，这对算法的性能至关重要。本文以最小化总加权拖期为目标，提出了一种组合邻域搜索算法，用于求解具有序列相关启动时间的单机调度问题。首先提出了一种新的邻域结构，称为“块交换”，它可以看作是以前广泛使用的“块移动”邻域的扩展，并提出了一个快速增量评估技术来提高其评估效率。然后，提出了块交换和块移动的两种邻域的组合，称为联合邻域搜索和令牌环搜索，并研究了它们在两种典型的元启发式算法上的性能：迭代局部搜索（ILS）和混合进化算法（HEA）。大量实验表明，基于联合邻域的令牌环搜索策略具有一定的竞争力。在120个公共基准测试算例上进行实验，本文的算法与精确算法和最近的元启发式算法相比，在解决方案质量和计算时间方面具有较强的竞争力。本文还测试了基于联合邻域搜索的HEA算法，以处理具有序列相关启动时间的单机调度问题的64个公共基准算例。HEA算法能够匹配所有64个算例的最优解或已知最好解。特别是，对于5个极具挑战性的算例，HEA获得已知最好解所需的计算时间显著减少。研究背景 邻域搜索和局部搜索算法是求解大规模组合优化问题的高效的元启发式算法之一。在局部搜索算法中，其最重要的特征之一是邻域结构的定义，这对算法整体性能至关重要。已有研究表明，某些特定的邻域结构对特定的问题十分有效，比如k-opt邻域求解TSP问题，N6和N7邻域求解JSP问题，而其他的邻域却收效甚微。因此，在启发式优化中，对具体的问题，根据其结构特征设计特定的邻域结构十分重要。目的 本文以带序列相关启动时间的单机调度问题为研究对象，给定N个任务，它们在单一机器上加工，每个任务的加工时间、截止时间、权重均已知。此外，相邻任务之间存在一个固定都安装时间、其大小与该相邻的两个任务有关。本文以最小化带权总拖期为目标，设计启发式算法，探究不同邻域结构及其组合对算法性能的影响。方法 本文提出一种组合邻域搜索算法，用于求解具有序列相关安装时间的单机调度问题。首先提出了一种新的邻域结构，称为“块交换”，它可以看作是以前广泛使用的“块移动”邻域的扩展，并提出了一个快速增量评估技术来提高其评估效率。然后，提出了块交换和块移动的两种邻域的组合，称为联合邻域搜索和令牌环搜索，并研究了它们在两种典型的元启发式算法上的性能：迭代局部搜索（ILS）和混合进化算法（HEA），即将联合邻域搜索和令牌环搜索嵌入ILS和HEA算法中，作为集中性搜索算子，并配合扰动、交叉等算子，形成求解该问题的高效的启发式优化算法。结果 本文的算法在120个标准算例上做了广泛的实验。实验结果显示，相比于论文中的其他算法如变邻域搜索算法、基于变邻域的遗传算法等，在相同的计算时间内，本文的HEA算法均改进了至少2个算例的历史最好解、最多只有1个算例较差、其他算例持平。并且，还测试了在不带权的单机调度问题，其以最小化总拖期为目标，求解了64个标准算例。实验结果显示，在相同的计算时间内，HEA算法能改进至少2个算例的历史最好解、最多只有2个算例较差、其他算例持平。结论 本文提出了一种新的邻域结构，称为“块交换”，它是之前广泛使用的“块移动”邻域的扩展，并提出了一个快速增量评估技术来提高其评估效率。然后，提出了块交换和块移动的两种邻域的组合，称为联合邻域搜索和令牌环搜索，并研究了它们在两种典型的元启发式算法上的性能：迭代局部搜索（ILS）和混合进化算法（HEA）。在一类单机调度问题上，以最小化总加权拖期为目标，测试了这两种邻域结构的效能。实验结果表明，与文献中已知的算法相比，基于块交换和块移动的邻域结构的HEA算法在解的质量和求解效率上具有较强的竞争力。特别是带令牌环搜索的HEA算法获得了64个算例的最优解和历史最好解，并且其所需的计算时间显著减少。Abstract: In a local search algorithm, one of its most important features is the definition of its neighborhood which is crucial to the algorithm’s performance. In this paper, we present an analysis of neighborhood combination search for solving the single-machine scheduling problem with sequence-dependent setup time with the objective of minimizing total weighted tardiness (SMSWT). First, We propose a new neighborhood structure named Block Swap (B1) which can be considered as an extension of the previously widely used Block Move (B2) neighborhood, and a fast incremental evaluation technique to enhance its evaluation efficiency. Second, based on the Block Swap and Block Move neighborhoods, we present two kinds of neighborhood structures: neighborhood union (denoted by B1 \cup B2) and token-ring search (denoted by B1 \rightarrow B2), both of which are combinations of B1 and B2. Third, we incorporate the neighborhood union and token-ring search into two representative metaheuristic algorithms: the Iterated Local Search Algorithm ( \mathrmILS_\rm new ) and the Hybrid Evolutionary Algorithm (HEA _\rm new ) to investigate the performance of the neighborhood union and token-ring search. Extensive experiments show the competitiveness of the token-ring search combination mechanism of the two neighborhoods. Tested on the 120 public benchmark instances, our HEA _\textnew has a highly competitive performance in solution quality and computational time compared with both the exact algorithms and recent metaheuristics. We have also tested the HEA _\textnew algorithm with the selected neighborhood combination search to deal with the 64 public benchmark instances of the single-machine scheduling problem with sequence-dependent setup time. HEA _\textnew is able to match the optimal or the best known results for all the 64 instances. In particular, the computational time for reaching the best well-known results for five challenging instances is reduced by at least 61.25%.
下载: