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.