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

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