Total completion time minimization scheduling on two hierarchical uniform machines

This paper investigates an online hierarchical scheduling problem on two uniform machines to minimize the total completion time of all jobs. Machine M1 with a speed v1 has a lower hierarchy and machine M2 with a speed v2 has a higher hierarchy. Each job has a unit processing time and a hierarchy. The job with a lower hierarchy can only be processed on the machine M1 and the job with a higher hierarchy can be processed on any of the two machines. We consider two variants of the problem: v1=1≤v2=s and v1=s≥v2=1. For both variants, we provide parameter lower bounds and online algorithms with competitive ratio of 9−412 and 33−32 respectively, which are optimal in sense of constant bound.