View article

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+2ss+2 in the case 01. Then we propose and analyze two online algorithms: HSF algorithm and EX-ONLINE algorithm. HSF is optimal in the case where s>1 and Σ₁≥Σ₂s, where Σ₁ and Σ₂ denote the total processing time of jobs which request higher GoS machine …