Abstract: Aiming at the Single-Machine Maximum Lateness Rescheduling Problem (SMMLRP) with an unexpected arrival of new jobs,a hybrid algorithm incorporating Harmony Search (HS) with Variable Neighborhood Search (VNS) technique was proposed.In this algorithm,the harmony memory was initialized by combination of Two-Stage Heuristic (TSH) and random generation method for permutation-based solutions.Furthermore,a SMMLRP-specific variable neighborhood search phase was embedded into the iterative HS framework.To further enhance the search capacity,an elimination method of non-optimal solutions based on SMMLRP dominance properties was designed and ran as the local search procedures in VNS phase.The suggested values for parameters Harmony Memory Size (HMS) and Harmony Memory Considering Rate (HMCR) were obtained with an extensive experimental parameter calibration.Computational tests and comparisons were conducted upon a large number of SMMLRP instances to validate the effectiveness of proposed algorithm after calibration.As demonstrated in the results,the proposed algorithm outperformed three reported standalone VNS algorithms in terms of both solution quality and robustness.

Key words: rescheduling, single machine, harmony search, variable neighborhood search, algorithms

摘要： 针对新工件突然到达干扰下的单机最大延迟时间重调度问题,提出一种融合和声搜索与变邻域搜索技术的混合算法。该算法运用两阶段启发式与排序解随机生成相融合的方法来初始化和声记忆库,在和声搜索迭代框架中嵌入了结合问题特征的变邻域搜索算子。为进一步强化算法的寻优能力,设计了基于占优性质的非最优解排除方法,在变邻域搜索算子的局部搜索环节中实施。通过参数校准实验及其结果分析,得出和声记忆库规模与和声记忆思考率两个参数的建议取值。运用校准后的算法对大量算例进行计算测试,并与单独应用变邻域搜索技术的3种已报道算法展开优化性能比较,结果表明所提算法在解的质量与鲁棒性上均具备比较优势。

关键词: 重调度, 单机, 和声搜索, 变邻域搜索, 算法