Local search algorithm with path relinking for single batch-processing machine scheduling problem
Local search algorithm with path relinking for single batch-processing machine scheduling problem
复制标题
DOI：
10.1007/s00521-016-2339-z
复制
发表时间：
2016-05
影响因子：
6
通讯作者：
Xin Zhang;Xiang-tao Li;Jianan Wang
中科院分区：
文献类型：
--
作者：
Xin Zhang;Xiang-tao Li;Jianan Wang
最小化最大完工时间的单机分批问题有着广泛的应用，包括工程基础和理论背景。机器可以同时处理多个工件，每个工件都有三个不同的属性：工件大小、处理时间和工件到达。本文提出了一种结合路径重连的混合局部搜索算法来解决该问题。我们不仅首先产生一个最优的初始解，但更注重提高解的质量。采用三种局部搜索方法增强解的多样性;采用路径重连方法，通过连接当前解和精英集中最优解的局部轨迹探索更优解。通过这些方法，它可以保持勘探和开发能力之间的平衡。对40个基准算例的计算结果表明，LP算法具有上级收敛性和鲁棒性，优于遗传算法、蚁群算法等现有算法，特别是在大规模算例中。
The single batch-processing machine problem is to minimize makespan, which has broad applications, including engineering fundamentals and theoretical background. The machine can process several jobs as a batch simultaneously, and every job has three different attributes: job size, processing time, and job arrival. In this paper, a hybrid local search algorithm with path relinking (LP) is devised to solve the problem. We not only generate an optimal initial solution firstly but also pay more attention to improving the solution quality. Three kinds of local searches are applied to enhance the diversity of solutions; the path relinking is adopted to explore better solutions through local tracks connecting the current solution and the best in the elite set. With these approaches, it can keep a balanced rate between exploratory and exploitative capacity. Computational experiments on 40 benchmark instances indicate that LP has the superior convergence and robust performance and it surpasses the current state-of-the-art methods such as genetic algorithm and ant colony optimization, especially for large instances.