Total completion time minimization in online hierarchical scheduling of unit-size jobs |
| |
Authors: | Jueliang Hu Yiwei Jiang Ping Zhou An Zhang Qinghui Zhang |
| |
Affiliation: | 1.Department of Mathematics,Zhejiang Sci-Tech University,Hangzhou,People’s Republic of China;2.School of Humanities,Zhejiang Business College,Hangzhou,People’s Republic of China;3.Institute of Operational Research and Cybernetics,Hangzhou Dianzi University,Hangzhou,People’s Republic of China |
| |
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 xrceil +frac{x}{lceil xrceil }+3}, frac{2}{lfloor xrfloor +frac{x}{lfloor xrfloor }+3}}), where (x=sqrt{2m+4}). We then present a greedy algorithm with tight competitive ratio of (1+frac{2(m-1)}{m(sqrt{4m-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), we propose an optimal online algorithm with competitive ratio of (16) (/) (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., (nrightarrow infty ). |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|