Online scheduling on two uniform machines to minimize the makespan

We consider two problems of online scheduling on two uniform machines: online scheduling under a grade of service (GoS) and online scheduling with reassignment. These problems are online in the sense that when a job presents, we have to irrevocably assign it to one of the machines before the next job is seen. The objective is to minimize the makespan. In the first problem, GoS means that some jobs have to be processed by some machine so that they can be guaranteed a higher quality. Assume that the speed of the higher GoS machine is normalized to 1, while the speed of the other one is s. We show that a lower bound of competitive ratio is 1 + frac(2 s, s + 2) in the case 0 < s ≤ 1 and 1 + frac(s + 1, s (2 s + 1)) in the case s > 1. Then we propose and analyze two online algorithms: HSF algorithm and EX-ONLINE algorithm. HSF is optimal in the case where s > 1 and Σ₁ ≥ frac(Σ₂, s), where Σ₁ and Σ₂ denote the total processing time of jobs which request higher GoS machine and the total processing time of jobs which request the normal one, respectively. EX-ONLINE is optimal in the case 2 (sqrt(2) - 1) ≤ s ≤ 1. In the second problem, we study two subproblems P_L and P_A proposed in [Z. Tan, S. Yu, Online scheduling with reassignment, Operations Research Letters 36 (2008) 250-254]. Assume that the speeds of 2 uniform machines are 1 and s ≥ 1, respectively. For P_L where we can reassign the last k jobs of the sequence, we show a lower bound of competitive ratio 1 + frac(1, 1 + s). For P_A where we can reassign arbitrary k jobs, we show a lower bound of competitive ratio frac((s + 1)², s² + s + 1). We propose a frac(s + 1, s)-competitive algorithm HSF-1 for both P_L and P_A. For P_A, we propose a frac((s + 1)², s + 2)-competitive algorithm EX-RA, which is superior to HSF-1 when 1 ≤ s ≤ sqrt(2).