DocumentCode
3239850
Title
An optimal semi-online algorithm on the generalized machine covering problem
Author
Tan, Jinzhi
Author_Institution
Coll. of Math. & Inf. Sci., Wenzhou Univ., Wenzhou, China
fYear
2011
fDate
27-29 May 2011
Firstpage
171
Lastpage
175
Abstract
This paper investigates the generalized machine covering problem on two parallel identical machines with non-simultaneous machine available times. For the semi-online version with the jobs arrive sorted by non-increasing sizes and the total processing time of all jobs known in advance, the aim of this paper is to obtain its optimal algorithm. The result of this paper is that a lower bound is analyzed by an adversary argument and an optimal algorithm with competitive ratio 6/5 is presented.
Keywords
scheduling; competitive ratio; generalized machine covering problem; nonsimultaneous machine available time; optimal semionline algorithm; parallel identical machines; Algorithm design and analysis; Optimal scheduling; Optimized production technology; Principal component analysis; Resource management; Schedules; analysis of algorithm; competitive ratio; machine covering; semi-online scheduling;
fLanguage
English
Publisher
ieee
Conference_Titel
Communication Software and Networks (ICCSN), 2011 IEEE 3rd International Conference on
Conference_Location
Xi´an
Print_ISBN
978-1-61284-485-5
Type
conf
DOI
10.1109/ICCSN.2011.6014698
Filename
6014698
Link To Document