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

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 → ∞ .