An improved exact algorithm for single-machine scheduling to minimise the number of tardy jobs with periodic maintenance

Abstract

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.

Keywords:

• scheduling
• branch-and-bound
• periodic maintenance
• single machine
• number of tardy jobs

Notes

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work was supported by the National Science Foundation of China under [grant number 71101106], [grant number 71571134], [grant number 71171149], [grant number 71571135], [grant number 71428002]. The second author is also supported in part by the Fundamental Research Funds for the Central Universities.