Semi-online scheduling with combined information on two identical machines in parallel

This paper is concerned with a semi-online scheduling problem with combined information on two identical parallel machines to minimize the makespan, where all the jobs have processing times in the interval \(1,\,t]\)  \((t\ge 1)\) and the jobs arrive in non-increasing order of their processing times. The objective is to minimize the makespan. For \(t\ge 1\), we obtain a lower bound \(\max _{N=1,2,3,\ldots }\left\{ \min \{\frac{4N+3}{4N+2}\,,\frac{Nt+N+1}{2N+1}\}\right\} \) and show that the competitive ratio of the \(LS\) algorithm achieves the lower bound.