Due-date assignment and single-machine scheduling with generalised position-dependent deteriorating jobs and deteriorating multi-maintenance activities

Yunqiang Yin, Wen Hung Wu, Edwin Tai Chiu Cheng, Chin Chia Wu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

43 Citations (Scopus)


This paper addresses a single-machine scheduling problem with simultaneous consideration of due-date assignment, generalised position-dependent deteriorating jobs, and deteriorating maintenance activities. It is assumed that the actual processing time of a job is a general non-decreasing function depending on the number of maintenance activities performed before it and its position in a sequence. Moreover, the machine may be subject to several maintenance activities up to a limit over the scheduling horizon. The maintenance activities do not necessarily restore the machine fully to its original perfect state and the duration of a maintenance activity depends on its start time. The objective is to find jointly the optimal job sequence, maintenance frequency and maintenance positions to minimise an objective function that includes the cost of due-date assignment, the cost of discarding jobs that cannot be completed by their due dates and the earliness of the scheduled jobs under the popular CON and SLK due-date assignment methods. We provide polynomial-time solution algorithms for various versions of the problem.
Original languageEnglish
Pages (from-to)2311-2326
Number of pages16
JournalInternational Journal of Production Research
Issue number8
Publication statusPublished - 18 Apr 2014


  • Deteriorating jobs
  • Deteriorating multi-maintenance activities
  • Due-date assignment
  • Scheduling

ASJC Scopus subject areas

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

Cite this