Optimal algorithm for semi-online scheduling on two machines under GoS levels.

Recently, Liu et al. (J Combin Optim 21:138-149, ) studied the semi-online scheduling problem on two machines under a grade of service provision. As the sum of jobs' processing times $$\varSigma $$ is known in advance and the processing times are bounded by an interval $$[1,\alpha ]$$ where $$1< \alpha <2$$ , they presented an algorithm which is $$\frac{1+\alpha }{2}$$ -competitive when $$\varSigma \ge \frac{2\alpha }{\alpha -1}$$ . In this paper, we give a modified algorithm which is shown to be optimal for arbitrary $$\alpha $$ and $$\varSigma $$ . [ABSTRACT FROM AUTHOR]