Semi-Online Hierarchical Scheduling on Two Machines for lp-Norm Load Balancing
Xianglai Qi and
Jinjiang Yuan ()
Additional contact information
Xianglai Qi: School of Mathematics and Statistics, Zhengzhou University, Zhengzhou, Henan 450001, P. R. China
Jinjiang Yuan: School of Mathematics and Statistics, Zhengzhou University, Zhengzhou, Henan 450001, P. R. China
Asia-Pacific Journal of Operational Research (APJOR), 2019, vol. 36, issue 01, 1-16
Abstract:
This paper investigates semi-online hierarchical scheduling problems on two identical machines, with the purpose of minimizing the lp-norm of the machines’ loads. We consider two semi-online versions with knowing the total processing time T of all jobs, or knowing the total processing time Ti of the jobs of hierarchy i for i = 1, 2 in advance. For the two semi-online versions, the best possible online algorithms are designed with competitive ratios of φ∗ and 2p+4p 2(3)p 1 p, respectively, where φ∗ is the maximum value of the function φ(x) = (x+1 2 (1−x))p+(1 2 (1−x))p xp+(1−x)p 1 p in x ∈ [1 2, 1]. When p = ∞, our results cover the known results for minimizing the makespan.
Keywords: Scheduling; semi-online; hierarchical machines; lp-norm (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)
Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595919500027
Access to full text is restricted to subscribers
Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
HTML/Text
Persistent link: https://EconPapers.repec.org/RePEc:wsi:apjorx:v:36:y:2019:i:01:n:s0217595919500027
Ordering information: This journal article can be ordered from
DOI: 10.1142/S0217595919500027
Access Statistics for this article
Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao
More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().