Single-machine scheduling with deteriorating jobs and past-sequence-dependent setup times

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

Research output: Journal article publicationJournal articleAcademic researchpeer-review

40 Citations (Scopus)


In many realistic scheduling settings a job processed later consumes more time than the same job processed earlier - this is known as scheduling with deteriorating jobs. Most research on scheduling with deteriorating jobs assumes that the actual processing time of a job is an increasing function of its starting time. Thus a job processed late may incur an excessively long processing time. On the other hand, setup times occur in manufacturing situations where jobs are processed in batches whereby each batch incurs a setup time. This paper considers scheduling with deteriorating jobs in which the actual processing time of a job is a function of the logarithm of the total processing time of the jobs processed before it (to avoid the unrealistic situation where the jobs scheduled late will incur excessively long processing times) and the setup times are proportional to the actual processing times of the already scheduled jobs. Under the proposed model, we provide optimal solutions for some single-machine problems.
Original languageEnglish
Pages (from-to)1861-1867
Number of pages7
JournalApplied Mathematical Modelling
Issue number4
Publication statusPublished - 1 Apr 2011


  • Deteriorating jobs
  • Past-sequence-dependent setup time
  • Single-machine

ASJC Scopus subject areas

  • Applied Mathematics
  • Modelling and Simulation

Cite this