Single machine due-date scheduling of jobs with decreasing start-time dependent processing times

Edwin Tai Chiu Cheng, L. Y. Kang, C. T. Ng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

22 Citations (Scopus)


We study the problem of scheduling jobs whose processing times are decreasing functions of their starting times. We consider the case of a single machine and a common decreasing rate for the processing times. The problem is to determine an optimal combination of the due date and schedule so as to minimize the sum of due date, earliness and tardiness penalties. We give an O(n log n) time algorithm to solve this problem.
Original languageEnglish
Pages (from-to)355-366
Number of pages12
JournalInternational Transactions in Operational Research
Issue number3
Publication statusPublished - 1 Jan 2005


  • Deteriorating jobs
  • Due date
  • Single machine scheduling

ASJC Scopus subject areas

  • Business and International Management
  • Computer Science Applications
  • Strategy and Management
  • Management Science and Operations Research
  • Management of Technology and Innovation

Cite this