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

Xiaoyun Xiong, Dujuan Wang, Edwin Tai Chiu Cheng, Chin Chia Wu, Yunqiang Yin

Research output: Journal article publicationJournal articleAcademic researchpeer-review

13 Citations (Scopus)


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.
Original languageEnglish
Pages (from-to)1345-1360
Number of pages16
JournalInternational Journal of Production Research
Issue number3
Publication statusPublished - 1 Feb 2018


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

ASJC Scopus subject areas

  • Strategy and Management
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering

Cite this