Single-machine scheduling with deteriorating functions for job processing times

Edwin Tai Chiu Cheng, Wen Chiung Lee, Chin Chia Wu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

29 Citations (Scopus)


In many realistic scheduling settings a job processed later consumes more time than when it is processed earlier - this phenomenon is known as scheduling with deteriorating jobs. In the literature on deteriorating job scheduling problems, majority of the research assumed that the actual job processing time of a job is a function of its starting time. In this paper we consider a new deterioration model where the actual job processing time of a job is a function of the processing times of the jobs already processed. We show that the single-machine scheduling problems to minimize the makespan and total completion time remain polynomially solvable under the proposed model. In addition, we prove that the problems to minimize the total weighted completion time, maximum lateness, and maximum tardiness are polynomially solvable under certain agreeable conditions.
Original languageEnglish
Pages (from-to)4171-4178
Number of pages8
JournalApplied Mathematical Modelling
Issue number12
Publication statusPublished - 1 Dec 2010


  • Deteriorating jobs
  • Scheduling
  • Single machine

ASJC Scopus subject areas

  • Applied Mathematics
  • Modelling and Simulation

Cite this