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

15 Citations (Scopus)

Abstract

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
Volume411
Issue number40-42
DOIs
Publication statusPublished - 6 Sep 2010

Keywords

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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this