Article ID: | iaor20072876 |
Country: | Netherlands |
Volume: | 34 |
Issue: | 6 |
Start Page Number: | 692 |
End Page Number: | 696 |
Publication Date: | Nov 2006 |
Journal: | Operations Research Letters |
Authors: | Chang Soo Y., Lee Kangbok, Park Jongho |
Keywords: | performance |
We consider the online scheduling of two machines under a grade of service 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.