Title :
An optimal semi-online algorithm on the generalized machine covering problem
Author_Institution :
Coll. of Math. & Inf. Sci., Wenzhou Univ., Wenzhou, China
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;
Conference_Titel :
Communication Software and Networks (ICCSN), 2011 IEEE 3rd International Conference on
Conference_Location :
Xi´an
Print_ISBN :
978-1-61284-485-5
DOI :
10.1109/ICCSN.2011.6014698
