Best Possible Approximation Algorithms for Single Machine Scheduling with Increasing Linear Maintenance Durations
Joint Authors
Source
Issue
Vol. 2014, Issue 2014 (31 Dec. 2014), pp.1-8, 8 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2014-02-13
Country of Publication
Egypt
No. of Pages
8
Main Subjects
Medicine
Information Technology and Computer Science
Abstract EN
We consider a single machine scheduling problem with multiple maintenance activities, where the maintenance duration function is of the linear form f t = a + b t with a ≥ 0 and b > 1 .
We propose an approximation algorithm named FFD-LS2I with a worst-case bound of 2 for problem.
We also show that there is no polynomial time approximation algorithm with a worst-case bound less than 2 for the problem with b ≥ 0 unless P = N P , which implies that the FFD-LS2I algorithm is the best possible algorithm for the case b > 1 and that the FFD-LS algorithm, which is proposed in the literature, is the best possible algorithm for the case b ≤ 1 both from the worst-case bound point of view.
American Psychological Association (APA)
Shi, Xuefei& Xu, Dehua. 2014. Best Possible Approximation Algorithms for Single Machine Scheduling with Increasing Linear Maintenance Durations. The Scientific World Journal،Vol. 2014, no. 2014, pp.1-8.
https://search.emarefa.net/detail/BIM-1050082
Modern Language Association (MLA)
Shi, Xuefei& Xu, Dehua. Best Possible Approximation Algorithms for Single Machine Scheduling with Increasing Linear Maintenance Durations. The Scientific World Journal No. 2014 (2014), pp.1-8.
https://search.emarefa.net/detail/BIM-1050082
American Medical Association (AMA)
Shi, Xuefei& Xu, Dehua. Best Possible Approximation Algorithms for Single Machine Scheduling with Increasing Linear Maintenance Durations. The Scientific World Journal. 2014. Vol. 2014, no. 2014, pp.1-8.
https://search.emarefa.net/detail/BIM-1050082
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-1050082