Variable neighbourhood search for job scheduling with position-dependent deteriorating processing times
研究手密集型制造中加工时间随顺序恶化的作业调度问题，以最小化最大延迟，提出变邻域搜索算法，实验证明其在大规模问题上能快速给出优质解。
This article studies the problem of job scheduling in hand-intensive manufacturing with processing times that deteriorate depending on the sequence in order to minimize the maximum delay of the set of jobs. In the literature, only a small number of academic works has considered the assumption of non-stationary workers during the planning horizon. This problem is NP-hard since it is as an extension of the parallel machine scheduling problem with makespan minimization, which is itself NP-hard. A variable neighbourhood search (VNS) algorithm is presented to solve this problem; its efficiency is evaluated through an extended set of numerical experiments with random-generated datasets. Results are compared with an exact method based on mathematical programming. The results show that the VNS algorithm provides good solutions in reasonable computing times even for large problems.