Multiprocessor jobs, preemptive schedules, and one-competitive online algorithms

We study online preemptive makespan minimization on m parallel machines, where multiprocessor jobs arrive over time and have widths (i.e., the number of machines used) from some fixed set W⊆{1,2,…,m}. For every number m of machines we concisely characterize all the sets W for which there exists a 1-competitive fully online algorithm and all the sets W for which there is a 1-competitive nearly online algorithm.