Total completion time minimization in online hierarchical scheduling of unit-size jobs

Jueliang Hu, Yiwei Jiang (), Ping Zhou, An Zhang and Qinghui Zhang
Additional contact information
Jueliang Hu: Zhejiang Sci-Tech University
Yiwei Jiang: Zhejiang Sci-Tech University
Ping Zhou: Zhejiang Business College
An Zhang: Hangzhou Dianzi University
Qinghui Zhang: Zhejiang Sci-Tech University

Journal of Combinatorial Optimization, 2017, vol. 33, issue 3, No 4, 866-881

Abstract: Abstract This paper investigates an online hierarchical scheduling problem on m parallel identical machines. Our goal is to minimize the total completion time of all jobs. Each job has a unit processing time and a hierarchy. The job with a lower hierarchy can only be processed on the first machine and the job with a higher hierarchy can be processed on any one of m machines. We first show that the lower bound of this problem is at least $$1+\min \{\frac{1}{m}, \max \{\frac{2}{\lceil x\rceil +\frac{x}{\lceil x\rceil }+3}, \frac{2}{\lfloor x\rfloor +\frac{x}{\lfloor x\rfloor }+3}\}$$ 1 + min { 1 m , max { 2 ⌈ x ⌉ + x ⌈ x ⌉ + 3 , 2 ⌊ x ⌋ + x ⌊ x ⌋ + 3 } , where $$x=\sqrt{2m+4}$$ x = 2 m + 4 . We then present a greedy algorithm with tight competitive ratio of $$1+\frac{2(m-1)}{m(\sqrt{4m-3}+1)}$$ 1 + 2 ( m - 1 ) m ( 4 m - 3 + 1 ) . The competitive ratio is obtained in a way of analyzing the structure of the instance in the worst case, which is different from the most common method of competitive analysis. In particular, when $$m=2$$ m = 2 , we propose an optimal online algorithm with competitive ratio of $$16$$ 16 $$/$$ / $$13$$ 13 , which complements the previous result which provided an asymptotically optimal algorithm with competitive ratio of 1.1573 for the case where the number of jobs n is infinite, i.e., $$n\rightarrow \infty $$ n → ∞ .

Keywords: Online scheduling; Hierarchy; Total completion time; Competitive ratio (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-016-0011-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:jcomop:v:33:y:2017:i:3:d:10.1007_s10878-016-0011-2

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-016-0011-2

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().