Semi-Online Scheduling on Two Machines with GoS Levels and Partial Information of Processing Time

Abstract

This paper investigates semi-online scheduling problems on two parallel machines under a grade of service (GoS) provision subject to minimize the makespan. We consider three different semi-online versions with knowing the total processing time of the jobs with higher GoS level, knowing the total processing time of the jobs with lower GoS level, or knowing both in advance. Respectively, for the three semi-online versions, we develop algorithms with competitive ratios of 3/2, 20/13, and 4/3 which are shown to be optimal.