Optimal Semi-online Scheduling Algorithms on Two Parallel Identical Machines under a Grade of Service Provision

摘要

This paper investigates semi-online scheduling problems on two parallel identical machines under a grade of service (GoS) provision. We consider two different semi-online versions where the optimal offline value of the instance is known in advance or the largest processing time of all jobs is known in advance. Respectively for two semi-online problems, we develop algorithms with competitive ratios of 3/2 and (√5 + l)/2, which are shown to be optimal.