Scheduling time-dependent jobs under mixed deterioration

Stanisław Gawiejnowicz*, Miao-Tsong Lin

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

21 Scopus citations


We consider a new model of time-dependent scheduling. A set of deteriorating jobs has to be processed on a single machine which is available starting from a non-zero time. The processing times of some jobs from this set are constant, while other ones are either proportional or linear functions of the job starting times. The applied criteria of schedule optimality include the maximum completion time, the total completion time, the total weighted completion time, the maximum lateness and the number of tardy jobs. We delineate a sharp boundary between computationally easy and difficult problems, showing polynomially solvable and NP-hard cases.

Original languageEnglish
Pages (from-to)438-447
Number of pages10
JournalApplied Mathematics and Computation
Issue number2
StatePublished - 15 Mar 2010


  • Deteriorating jobs
  • NP-hard problems
  • Polynomial-time algorithms
  • Scheduling
  • Single machine

Fingerprint Dive into the research topics of 'Scheduling time-dependent jobs under mixed deterioration'. Together they form a unique fingerprint.

Cite this