Scheduling linear deteriorating jobs with an availability constraint on a single machine

Min Ji, Yong He, Edwin Tai Chiu Cheng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

72 Citations (Scopus)


We consider a single machine scheduling problem in which the processing time of a job is a simple linear increasing function of its starting time and the machine is subject to an availability constraint. We consider the non-resumable case. The objectives are to minimize the makespan and the total completion time. We show that both problems are NP-hard and present pseudo-polynomial time optimal algorithms to solve them. Furthermore, for the makespan problem, we present an optimal approximation algorithm for the on-line case, and a fully polynomial time approximation scheme for the off-line case. For the total completion time problem, we provide a heuristic and evaluate its efficiency by computational experiments.
Original languageEnglish
Pages (from-to)115-126
Number of pages12
JournalTheoretical Computer Science
Issue number1-3
Publication statusPublished - 11 Oct 2006


  • Approximation algorithms
  • Availability constraint
  • Computational complexity
  • Deteriorating job
  • Scheduling

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this