Online and semi-online scheduling of two machines under a grade of service provision

We consider the online scheduling of two machines under a grade of service (GoS) provision and its semi-online variant where the total processing time is known. Respectively for the online and semi-online problems, we develop algorithms with competitive ratios of 5/3 and 3/2 which are shown to be optimal. (c) 2005 Elsevier B.V. All rights reserved.X1150sciescopu