Preemptive scheduling with simple linear deterioration on a single machine

Chi To Ng, Shisheng Li, Edwin Tai Chiu Cheng, Jinjiang Yuan

Research output: Journal article publicationJournal articleAcademic researchpeer-review

17 Citations (Scopus)


In this paper we study the problem of scheduling n deteriorating jobs with release dates on a single machine. The processing time of a job is assumed to be the product of its deteriorating rate and its starting time. Precedence relations may be imposed on the set of jobs. Unlike the classical time-dependent scheduling problems, we assume that the execution of a job can be preempted in the sense that the job's deteriorating rate is reduced when it is preempted and each continuously processed part of a job can be regarded as an independent job with a specified deteriorating rate. The objective is to minimize some common regular scheduling performance measures. We first show that minimizing a class of regular symmetric functions is polynomially solvable. Then we construct an O(n2) algorithm for minimizing the maximum job completion cost with or without precedence constraints. Finally we show that minimizing the total weighted completion time is NP-hard even if there are only two distinct release dates.
Original languageEnglish
Pages (from-to)3578-3586
Number of pages9
JournalTheoretical Computer Science
Issue number40-42
Publication statusPublished - 6 Sept 2010


  • Linear deterioration
  • Preemption
  • Regular function
  • Release dates
  • Scheduling

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Preemptive scheduling with simple linear deterioration on a single machine'. Together they form a unique fingerprint.

Cite this