Publication at Faculty of Mathematics and Physics |
2015
Abstract
We study online preemptive makespan minimization on m parallel machines, where the (multiprocessor) jobs arrive over time and have widths from some fixed set W subset of {1, 2, ..., m}. For every number m of machines we concisely characterize all the sets W for which there is a 1-competitive fully online algorithm and all the sets W for which there is a 1-competitive nearly online algorithm.