Multiprocessor Jobs, Preemptive Schedules, and One-Competitive Online Algorithms

Abstrakt

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.

Klíčová slova

• parallel jobs
• minimize
• machines
• tasks