Single-machine scheduling with time-dependent and position-dependent deteriorating jobs

Yunqiang Yin, Wen Hung Wu, T. C.E. Cheng, Chi Chia Wu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

46 Citations (Scopus)


In many real-life scheduling situations, the jobs deteriorate at a certain rate while waiting to be processed. This study introduces a new deterioration model where the actual processing time of a job depends not only on the starting time of the job but also on its scheduled position. The objective is to find the optimal schedule such that the makespan or total completion time is minimised. This study first shows that both problems are solvable in O(n log n) time. This study further shows that in both cases there exists an optimal schedule that is the shortest processing time, longest processing time, or V-shaped with respect to the job normal processing times, depending on the relationships between problem parameters.

Original languageEnglish
Pages (from-to)781-790
Number of pages10
JournalInternational Journal of Computer Integrated Manufacturing
Issue number7
Publication statusPublished - 3 Jul 2015


  • deteriorating jobs
  • makespan
  • scheduling
  • total completion time

ASJC Scopus subject areas

  • Aerospace Engineering
  • Mechanical Engineering
  • Computer Science Applications
  • Electrical and Electronic Engineering

Cite this