Single-machine scheduling and common due date assignment with potential machine disruption

Abstract

This paper studies a single-machine due date assignment and scheduling problem in a disruptive environment, where a machine disruption may occur at a particular time that will last for a period of time with a certain probability, and the job due dates are determined by the decision-maker using the popular common due date assignment method. The goal is to determine jointly the optimal job sequence and the common due date so as to minimise the expected value of an integrated cost function that includes the earliness, tardiness and due date assignment costs. We analyse the computational complexity status of various cases of the problem, and develop pseudo-polynomial-time solution algorithms, randomised adaptive search algorithms, and fully polynomial-time approximation schemes for them, if viable. Finally, we conduct extensive numerical testing to assess the performance of the proposed algorithms.

Keywords:

• scheduling
• dynamic programming
• disruption management
• due date assignment
• fully polynomial-time approximation scheme

Acknowledgements

We thank the AE and two anonymous referees for their helpful comments on earlier versions of our paper.

Notes

No potential conflict of interest was reported by the authors.

Additional information

Funding

This paper was supported in part by the National Natural Science Foundation of China [grant number 11561036], [grant number 71501024], [grant number 71301022]; Fundamental Research Funds for the Central Universities [grant number 3132017083]; MOST of Taiwan [grant number 105-2221-E-035-053-MY3]. Cheng was also supported in part by the National Natural Science Foundation of China [grant number 71390334].