Online hierarchical parallel-machine scheduling in shared manufacturing to minimize the total completion time

We consider online hierarchical scheduling on m identical machines in shared manufacturing to minimize the total completion time. Each job has a unit-size processing time. The jobs arrive one by one and must be assigned to one of the m machines before the next job arrives. The jobs with a lower hierarchy can only be processed on the first k machines, $1\le k\le m-1,$ and the jobs with a higher hierarchy can be processed on any one of the m machines. We first show that the lower bound of the problem is at least $1+\min \{\frac{1}{m-k+1},\max \{\frac{2}{k\lceil s\rceil +3k+\frac{2m+4}{\lceil s\rceil }},\frac{2}{k\lfloor s\rfloor +3k+\frac{2m+4}{\lfloor s\rfloor }}\left\}\right\},$ where $s=\sqrt{\frac{2m+4}{k}}.$ Proposing a greedy algorithm, we show that its tight competitive ratio is $1+\frac{2(m-k)k}{m(\sqrt{(4m-3k)k}+k)}$ by analyzing a set of instances that must contain a worst-case instance, which is different from the general method of calculating the competitive ratio. In addition, for the case where k = 1, we present an improved online algorithm with a tight competitive ratio of $1+\max \{\frac{2}{\lceil \sqrt{2m+4}\rceil +\frac{2m+4}{\lceil \sqrt{2m+4}\rceil }+3},\frac{2}{\lfloor \sqrt{2m+4}\rfloor +\frac{2m+4}{\lfloor \sqrt{2m+4}\rfloor }+3}\},$ which is optimal for $2\le m\le 5.$ Numerical experiments show that the greedy online algorithm has good performance, especially when k approaches 1 or m.