Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/9101
Title: Preemptive scheduling with simple linear deterioration on a single machine
Authors: Ng, CT 
Li, S
Cheng, TCE 
Yuan, J
Keywords: Linear deterioration
Preemption
Regular function
Release dates
Scheduling
Issue Date: 2010
Publisher: Elsevier
Source: Theoretical computer science, 2010, v. 411, no. 40-42, p. 3578-3586 How to cite?
Journal: Theoretical computer science 
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.
URI: http://hdl.handle.net/10397/9101
ISSN: 0304-3975
DOI: 10.1016/j.tcs.2010.05.032
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

13
Last Week
0
Last month
1
Citations as of Sep 9, 2017

WEB OF SCIENCETM
Citations

9
Last Week
0
Last month
0
Citations as of Sep 6, 2017

Page view(s)

49
Last Week
2
Last month
Checked on Sep 17, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.