Preemptive Semi-online Algorithms for Parallel Machine Scheduling with Known Total Size

This paper investigates preemptive semi-online scheduling problems on m identical parallel machines, where the total size of all jobs is known in advance. The goal is to minimize the maximum machine completion time or maximize the minimum machine completion time. For the first objective, we present an optimal semi.online algorithm with competitive ratio 1. For the second objective, we show that the competitive ratio of any semi.online algorithm is at least 2m.3m.1 for any m > 2 and present optimal semi.online algorithms for m = 2, 3