Semi-online early work maximization problems on two hierarchical uniform machines with partial information of processing time

In this paper, we consider four semi-online early work maximization problems on two hierarchical uniform machines $$M_1$$ M 1 and $$M_2$$ M 2 , where machine $$M_1$$ M 1 with speed $$s>0$$ s > 0 is available for all jobs and machine $$M_2$$ M 2 with speed 1 is only available for high-hierarchy jobs. When the total size of all jobs is known, we design an optimal online algorithm with a competitive ratio of $$\min \{1+s,\frac{2+2s}{1+2s}\}$$ min { 1 + s , 2 + 2 s 1 + 2 s } . When the total size of low-hierarchy jobs is known, we design an optimal online algorithm with a competitive ratio of $$\min {\{1+s, \frac{\sqrt{9\,s^2+10\,s+1}-s-1}{2\,s}}\}$$ min { 1 + s , 9 s 2 + 10 s + 1 - s - 1 2 s } . When the total size of high-hierarchy jobs is known, we design an optimal online algorithm with a competitive ratio of $$\min \{\sqrt{s+1}, \sqrt{s^2+2\,s+2}-s\}$$ min { s + 1 , s 2 + 2 s + 2 - s } . When both the total sizes of low-hierarchy and high-hierarchy jobs are known, we give a lower bound $$\frac{2s+2}{s+2}$$ 2 s + 2 s + 2 for the case $$s\le \frac{2}{3}$$ s ≤ 2 3 , and an optimal online algorithm with a competitive ratio of $$\frac{3s+3}{3s+2}$$ 3 s + 3 3 s + 2 for the case $$s>\frac{2}{3}$$ s > 2 3 .