### Stochastic Online Scheduling

Participants: |
Nicole Megow |

Cooperation with: |
Tjark Vredeveld,
Zuse-Institute Berlin, Marc Uetz, Maastricht University |

Supported by: |
DFG Reseach Center MATHEON: Mathematics for key technologies. |

**Project description**

In order to cope with uncertainty about the future, there are two
major frameworks in the theory of machine scheduling, one is the
stochastic scheduling model, the other online scheduling model(s).
The main characteristic of *stochastic scheduling*, in contrast
to deterministic models, is the fact that the processing times of jobs
are subject to random fluctuations, and the actual processing times
become known only upon completion of the jobs. It is generally
assumed, though, that the respective random variables, or at least
their first moments, are known beforehand. In *online
scheduling*, the assumption is that the instance is presented to the
scheduler only piecewise. Depending on the precise model, jobs are
arriving either one-by-one (sequence model), or over time (time-stamp
model). The job characteristics such as weight and processing time are
usually disclosed upon arrival of the job, and decisions must be made
without any knowledge of the jobs to come.

We suggest a model that generalizes both, the
stochastic scheduling model as well as the online scheduling models.
We call it the *Stochastic Online Scheduling (SOS)* model. Like
in online scheduling, we assume that the instance is presented to the
scheduler piecewise, and nothing is known about jobs that might arrive
in the future. Once a job arrives, like in stochastic scheduling, we
assume that its weight and first moment of its processing time are
disclosed, but the actual processing time remains unknown until the
job completes.

**Policies & Performance**

We derive worst case performance guarantees for the expected performance of simple, combinatorial online scheduling policies for the stochastic online scheduling model on a single machine and on identical parallel machines, respectively, minimizing the sum of weighted completion times. For the analysis of policies respecting release dates, we restrict ourselves to random variables that we call delta-NBUE. This is a generalization of NBUE random variables.

In our performance analysis, we crucially exploit the fact that lower bounds on the expected value of an optimal policy known from stochastic scheduling carry over to the SOS setting. We utilize the LP-based lower bound by Möhring, Schulz and Uetz (1999) on the expected performance of an optimal stochastic scheduling policy. It is a generalization of a lower bound by Eastman et al. (1964) for the deterministic setting.

**Stochastic online scheduling on a single machine**

For the single machine problem with release dates in the stochastic online scheduling model we consider the following policy which was proposed for parallel machines by Megow and Schulz (2004) in the deterministic online setting.

**alpha-Shift-WSEPT:** Modify the release date r_j of each job j such
that r'_j = max { r_j, alpha E[P_j] }, for some fixed alpha > 0. At any time, when the
machine is idle, start the job with highest priority in the WSEPT
order (i.e., the job with highest ratio of weight to expected
processing time) among all available jobs, respecting the modified release dates.

We can show that the alpha-Shift-WSEPT policy is a (delta +2)-approximation for the SOS problem on a single machine for delta-NBUE processing times. The best choice of the parameter alpha is alpha=1.

For NBUE distributed processing times this result matches the best known LP based performance bound derived by Möhring et. al (1999) for stochastic scheduling. In the online setting, the best possible algorithm is exactly 2-competitive which is shown in by Anderson, Potts (2002) and Hoogeveen, Vestjens (1996).

**Stochastic online scheduling on parallel machines**

In the parallel machine environment we apply the following simple,
combinatorial scheduling policy that we call *MinIncrease*. We
schedule jobs that have been assigned to the same machine in the
alpha-Shift-WSEPT order. The online decisions on job-to-machine
assignments are made as follows: as soon as a job is
presented, we assign it to that machine where it causes the minimal
increase in total expected objective value, given the jobs on each
machine would be scheduled in WSEPT order (non-increasing ratios of
weight over expected processing times). Note, that in order to assign
jobs to machines, we completely ignore release dates and information
about real processing times which could be observed from the schedule.

Then we can show the following: Consider the SOS problem of
nonpreemptive scheduling on parallel machines with release
dates. For NBUE processing times, the approximation ratio for
*MinIncrease* is less than 3.62 - 1/(2m), improving upon the previously best
known approximation ratio of 4-1/m from Möhring et al. (1999)
for the stochastic problem. Moreover, for deterministic instances the
performance of *MinIncrease* matches the currently best known competitive ratio
of 3.28 from Megow, Schulz (2004) for deterministic online scheduling.

In the special setting where all release dates are equal,
our *MinIncrease* policy indeed chooses for each job the
machine where it causes the least increase in the expected objective
function value, given the previously assigned jobs. We prove a performance ratio
which matches exactly the currently best known performance guarantee
for the classical stochastic setting, which was derived for the
performance of the WSEPT rule by Möhring et al (1999). The WSEPT rule,
however, requires the knowledge of all jobs with their weights w_j
and expected processing times E[ P_j ] at the outset.

**References**

- E.J. Anderson and C.N. Potts,
*On-line scheduling of a single machine to minimize total weighted completion time*, Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2002, pp. 548-557. - H. Hoogeveen and A.P.A. Vestjens,
*Optimal on-line algorithms for single-machine scheduling*, Proceedings of the Fifth Conference on Integer Programming and Combinatorial Optimization, W.H. Cunningham, S.T. McCormick, and M. Queyranne, eds., Lecture Notes in Computer Science, vol. 1084, Springer, 1996, pp. 404-414. - N. Megow and A.S. Schulz, On-line scheduling to minimize average completion time revisited, Operations Research Letters 32(5), 2004, pp. 485-490.
- Nicole Megow, Marc Uetz, and Tjark Vredeveld, Stochastic Online Scheduling on Parallel Machines.
*G. Persiano and R. Solis-Oba (eds): Approximation and Online Algorithms, Lecture Notes in Computer Science 3351, pages 167-180, Springer, 2005.* - Nicole Megow, Marc Uetz, and Tjark Vredeveld, Models and Algorithms for Stochastic Online Scheduling.
*(Exteded Version.) Submitted.* - R.H. Möhring, A.S. Schulz, and M. Uetz,
*Approximation in stochastic scheduling: the power of LP-based priority policies*, Journal of the ACM 46, 1999, pp. 924-942.