direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 08-2006

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

Approximation Results for Preemptive Stochastic Online Scheduling
primary: 90B36 Scheduling theory, stochastic
secondary: 68W40 Analysis of algorithms
68W25 Approximation algorithms
68M20 Performance evaluation; queueing; scheduling
scheduling, total weighted completion time, preemptive, approximation, stochastic dynamic optimization, online optimization
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.
Our policies apply to the recently introduced stochastic online scheduling model in which jobs arrive online over time. In contrast to the previously considered nonpreemptive setting, our preemptive policies extensively utilize information on processing time distributions other than the first (and second) moments. In order to derive our results we introduce a new nontrivial lower bound on the expected value of an unknown optimal policy that we derive from an optimal policy for the basic problem on a single machine without release dates. This problem is known to be solved optimally by a Gittins index priority rule. This priority index also inspires the design of our policies.
Download as [PDF] [ps]
Title: Source

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe