Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/10404
Title: Optimal algorithms for semi-online machine covering on two hierarchical machines
Authors: Wu, Y
Cheng, TCE 
Ji, M
Keywords: Competitive ratio
Hierarchy
Scheduling
Semi-online
Two machines
Issue Date: 2014
Publisher: Elsevier
Source: Theoretical computer science, 2014, v. 531, p. 37-46 How to cite?
Journal: Theoretical computer science 
Abstract: This paper investigates the semi-online machine covering problem on two hierarchical machines where the jobs are correspondingly classified into two hierarchical classes. The objective is to maximize the minimum machine load. We show that if we only know the size of the largest job, no algorithm with a bounded competitive ratio exists. So we consider the case where we know both the size and the class of the largest job. If we know the size of the largest job and that it belongs to the higher class, then an optimal algorithm with a (1+√2/2)-competitive ratio exists. If we know the size of the largest job and that it belongs to the lower class, we design an optimal algorithm with an α-competitive ratio, where α≈2.48119 is the largest root of the equation x3-2x2-2x+2=0. For the case where the total size of all the jobs is known in advance, we show that the competitive ratio of an optimal algorithm is 2.
URI: http://hdl.handle.net/10397/10404
ISSN: 0304-3975
DOI: 10.1016/j.tcs.2014.02.015
Appears in Collections:Journal/Magazine Article

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

SCOPUSTM   
Citations

4
Last Week
0
Last month
0
Citations as of Nov 11, 2017

WEB OF SCIENCETM
Citations

4
Last Week
0
Last month
1
Citations as of Nov 11, 2017

Page view(s)

63
Last Week
5
Last month
Checked on Nov 13, 2017

Google ScholarTM

Check

Altmetric



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