Single-machine scheduling with deteriorating jobs and setup times to minimize the maximum tardiness

Edwin Tai Chiu Cheng, Chou Jung Hsu, Yi Chi Huang, Wen Chiung Lee

Research output: Journal article publicationJournal articleAcademic researchpeer-review

32 Citations (Scopus)


In many realistic production situations, a job processed later consumes more time than the same job when it is processed earlier. Production scheduling in such an environment is known as scheduling with deteriorating jobs. However, research on scheduling problems with deteriorating jobs has rarely considered explicit (separable) setup time (cost). In this paper, we consider a single-machine scheduling problem with deteriorating jobs and setup times to minimize the maximum tardiness. We provide a branch-and-bound algorithm to solve this problem. Computational experiments show that the algorithm can solve instances up to 1000 jobs in reasonable time.
Original languageEnglish
Pages (from-to)1760-1765
Number of pages6
JournalComputers and Operations Research
Issue number12
Publication statusPublished - 1 Dec 2011


  • Deteriorating jobs
  • Maximum tardiness
  • Setup time
  • Single-machine scheduling

ASJC Scopus subject areas

  • Computer Science(all)
  • Management Science and Operations Research
  • Modelling and Simulation

Cite this