Title
Stochastic Online Scheduling on Parallel Machines
Authors
-
Publication
Appeared in: Persiano and R. Solis-Oba (eds):
Approximation and Online Algorithms, Lecture Notes
in Computer Science 3351, pages 167-180, Springer,
2005.
Source
-
Classification
-
not available
Keywords
-
stochastic scheduling, online scheduling, parallel
machines, average completion time
-
-
We consider a non-preemptive, stochastic parallel
machine scheduling model with the goal to minimize
the weighted completion times of jobs. In contrast
to the classical stochastic model where jobs with
their processing time distributions are known
beforehand, we assume that jobs appear one by one,
and every job must be assigned to a machine
online. We propose a simple online scheduling policy
for that model, and prove a performance guarantee
that matches the currently best known performance
guarantee for stochastic parallel machine
scheduling. For the more general model with job
release dates we derive an analogous result, and for
NBUE distributed processing times we even improve
upon the previously best known performance guarantee
for stochastic parallel machine
scheduling. Moreover, we derive some lower bounds on
approximation.
