Applying Variable Neighborhood Search to the Single-machine Maximum Lateness Rescheduling Problem

In response to an unexpected arrival of new jobs, this paper investigates the single-machine maximum lateness rescheduling problem subject to an upper limit on the total sequence disruption. Problem-specific variable neighborhood search (VNS) meta-heuristics are developed to obtain the near-optimal solution. A computational experiment is conducted to evaluate their performances. As shown by the obtained results, the VNS algorithms have quite high accuracy to the optima for instances up to 24 jobs (with the mean error percentage of less than 0.5%). Besides, it is found that the first proposed VNS alternative is more recommended.