An improved exact algorithm for single-machine scheduling to minimise the number of tardy jobs with periodic maintenance
研究单机调度中带定期维护的问题，目标是减少延迟作业数量，提出一种基于高效下界和优势性质的分支定界精确算法，并通过数值实验验证其效率。
In this paper, we investigate a single-machine scheduling problem with periodic maintenance, which is motivated by various industrial applications (e.g. tool changes). The pursued objective is to minimise the number of tardy jobs, because it is one of the important criteria for the manufacturers to avoid the loss of customers. The strong NP-hardness of the problem is shown. To improve the state-of-the-art exact algorithm, we devise a new branch-and-bound algorithm based on an efficient lower bounding procedure and several new dominance properties. Numerical experiments are conducted to demonstrate the efficiency of our exact algorithm.