Several semi-online scheduling problems on two identical machines with combined information

In this paper we consider several semi-online scheduling problems on two identical machines with combined information. The objective of each problem is to minimize the makespan. The first problem is semi-online scheduling with known optimal solution value and maximum job size. We obtain a lower bound and design an optimal algorithm with a competitive ratio . The second problem is semi-online scheduling with a buffer of size k, where k(k≥1) is a finite positive integer, and known maximum job size. We obtain a lower bound and design an algorithm with a competitive ratio . The third problem is semi-online scheduling with a buffer of size 1 and jobs arriving in decreasing order of their processing times. We obtain a lower bound , which matches an upper bound in the literature. The last problem is semi-online scheduling with a buffer of size 1 and all the job processing times being bounded in the interval [1,t](t≥1). We obtain a lower bound , where the lower bound for t≥6 matches an upper bound in the literature, and design an algorithm with a competitive ratio for , which is optimal for .