Publication at Faculty of Mathematics and Physics |
2023
Abstract
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 subset of {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.