Semi-online scheduling with known partial information about job sizes on two identical machines

In this paper we consider the semi-online scheduling problem with known partial information about job sizes on two identical machines, where all the jobs have processing times in the interval and the maximum job size is tp. The objective is to minimize the makespan. For and t≥2, we obtain lower bounds and on the optimal solution, respectively, which match the upper bounds given by He and Zhang (1999) in [2]. For , we prove that a lower bound on the optimal solution is and design an algorithm with a competitive ratio equal to this lower bound.