Thumbnail Image

Approximation Results for Preemptive Stochastic Online Scheduling

Megow, Nicole; Vredeveld, Tjark

Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin

We present first constant performance guarantees for preemptive stochastic scheduling to minimize the sum of weighted completion times. For scheduling jobs with release dates on identical parallel machines we derive policies with a guaranteed performance ratio of 2 which matches the currently best known result for the corresponding deterministic online problem.