Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/656
Title: Single-machine scheduling with periodic maintenance to minimize makespan
Authors: Ji, M
He, Y
Cheng, TCE 
Keywords: Single-machine scheduling
Periodic maintenance
Nonresumable jobs
Approximation algorithm
Non-approximability
Issue Date: Jun-2007
Publisher: Pergamon Press
Source: Computers and operations research, June 2007, v. 34, no. 6, p. 1764-1770 How to cite?
Journal: Computers and operations research 
Abstract: We consider a single-machine scheduling problem with periodic maintenance activities. Although the scheduling problem with maintenance has attracted researchers' attention, most of past studies considered only one maintenance period. In this research several maintenance periods are considered where each maintenance activity is scheduled after a periodic time interval. The objective is to find a schedule that minimizes the makespan, subject to periodic maintenance and nonresumable jobs. We first prove that the worst-case ratio of the classical LPT algorithm is 2. Then we show that there is no polynomial time approximation algorithm with a worst-case ratio less than 2 unless P=NP, which implies that the LPT algorithm is the best possible.
URI: http://hdl.handle.net/10397/656
ISSN: 0305-0548
EISSN: 1873-765X
DOI: 10.1016/j.cor.2005.05.034
Rights: Computers & Operations Research © 2005 Elsevier Ltd. The journal web site is located at http://www.sciencedirect.com.
Appears in Collections:Journal/Magazine Article

Files in This Item:
File Description SizeFormat 
Periodic_Maintenance_C_OR_V3.pdfPre-published version150.07 kBAdobe PDFView/Open
Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

86
Last Week
0
Last month
5
Citations as of Aug 14, 2017

WEB OF SCIENCETM
Citations

68
Last Week
0
Last month
2
Citations as of Aug 21, 2017

Page view(s)

362
Last Week
4
Last month
Checked on Aug 20, 2017

Download(s)

1,676
Checked on Aug 20, 2017

Google ScholarTM

Check

Altmetric



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