Preemptive Semi-Online Scheduling with Tightly-Grouped Processing Times

This paper investigates a preemptive semi-online scheduling problem on m identical parallel machines where m=2,3. It is assumed that all jobs have their processing times in between p and rp ( p > 0, r >= 1). The goal is to minimize the makespan. Best possible algorithms are designed for any r >= 1 when m=2,3.