Single-machine scheduling with past-sequence-dependent delivery times and a linear deterioration

Yunqiang Yin, Edwin Tai Chiu Cheng, Jianyou Xu, Shuenn Ren Cheng, Chin Chia Wu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

18 Citations (Scopus)


In many real-life scheduling environments, the jobs deteriorate at a certain rate while waiting to be processed. This paper addresses some single-machine scheduling problems with past-sequence-dependent (p-s-d) delivery times and a linear deterioration. The p-s-d delivery time of a job is propor-tional to the job's waiting time. It is assumed that the deterioration process is reected in the job processing times being an increasing function of their starting times. We consider the following objectives: the makespan, total com-pletion time, total weighted completion time, maximum lateness, and total ab-solute differences in completion times. We seek the optimal schedules for the problems to minimize the makespan and total completion time. Despite that the computational complexities of the problems to minimize the total weighted completion time and maximum lateness remain open, we present heuristics and analyze their worst-case performance ratios, and show that some special cases of the problems are polynomially solvable. We also show that the optimal schedule for the problem to minimize the total absolute differences in comple-tion times is V -shaped with respect to the normal job processing times.
Original languageEnglish
Pages (from-to)323-339
Number of pages17
JournalJournal of Industrial and Management Optimization
Issue number2
Publication statusPublished - 26 Mar 2013


  • Deterioration
  • Past-sequence-dependent delivery times
  • Scheduling

ASJC Scopus subject areas

  • Business and International Management
  • Strategy and Management
  • Control and Optimization
  • Applied Mathematics


Dive into the research topics of 'Single-machine scheduling with past-sequence-dependent delivery times and a linear deterioration'. Together they form a unique fingerprint.

Cite this