Document [original]

Models and Algorithms for Stochastic Online Scheduling1

Nicole Megow

Technische Universit¨at Berlin, Institut f¨ur Mathematik, Strasse des 17. Juni 136, 10623 Berlin, Germany.

email: nmego[email protected]erlin.de

Marc Uetz

Maastricht University, Department of Quantitative Economics, P.O. Box 616, 6200 MD Maastricht, The

Netherlands.

email: m.uetz@ke.unimaas.nl

Tjark Vredeveld2

Maastricht University, Department of Quantitative Economics, P.O. Box 616, 6200 MD Maastricht, The

Netherlands.

email: t.vredeveld@ke.unimaas.nl

We consider a model for scheduling under uncertainty. In this model, we combine the main characteristics of online

and stochastic scheduling in a simple and natural way. Job processing times are assumed to be stochastic, but in

contrast to traditional stochastic scheduling models, we assume that jobs arrive online, and there is no knowledge

about the jobs that will arrive in the future. The model incorporates both, stochastic scheduling and online

scheduling as a special case. The particular setting we consider is non-preemptive parallel machine scheduling,

with the objective to minimize the total weighted completion times of jobs. We analyze simple, combinatorial

online scheduling policies for that model, and derive performance guarantees that match the currently best known

performance guarantees for stochastic and online parallel machine scheduling. For processing times that follow

NBUE distributions, we improve upon previously best known performance bounds from stochastic scheduling,

even though we consider a more general setting.

Key words: scheduling; stochastic; online; total weighted completion time; approximation

MSC2000 Subject Classification: Primary: 90B36 ; Secondary: 68W40, 68W25, 68M20

OR/MS subject classification: Primary: Production/scheduling ; Secondary: approximation/heuristic

1. Introduction. Scheduling on identical parallel machines to minimize the total weighted comple-

tion time of jobs, P | |PwjCjin the three-field notation of Graham et al. [12], is one of the classical

problems in combinatorial optimization. The problem plays a role whenever many jobs must be processed

on a limited number of machines or processors, with applications in manufacturing, parallel computing [5]

or compiler optimization [6]. The literature has witnessed many papers on this problem, as well as its vari-

ant where the jobs have individual release dates before which they must not be processed, P |rj|PwjCj.

In the off-line (deterministic) setting, where the set of jobs and their characteristics are known in ad-

vance, the complexity status of both problems is solved; both are strongly NP-hard [17], and they admit

a polynomial time approximation scheme [1, 27].

In order to cope with scenarios where there is uncertainty about the future, there are two major

frameworks in the theory of scheduling, one is stochastic scheduling, the other is online scheduling. In

stochastic scheduling the population of jobs is assumed to be known beforehand, but in contrast to

deterministic models, the processing times of jobs are random variables. The actual processing times

become known only upon completion of the jobs. The respective random variables, or at least their

first moments, are assumed to be known beforehand. In online scheduling, the assumption is that the

instance is presented to the scheduler only piecewise. Jobs are either arriving one-by-one (in the online-list

model), or over time (in the online-time model) [22]. The actual processing times are usually disclosed

upon arrival of a job, and decisions must be made without any knowledge of the jobs to come.

We consider a model that generalizes both, stochastic scheduling and online scheduling. 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 expected processing time is disclosed, but the actual processing time remains unknown until the

1Research partially supported by the DFG Research Center Matheon Mathematics for key technologies. An extended

abstract with parts of this work appeared in the Proc. of the 2nd Workshop on Approximation and Online Algorithms [19].

2Parts of this work were done while the author was with the Konrad-Zuse-Zentrum f¨ur Informationstechnik Berlin,

Germany.

2Megow, Uetz, Vredeveld: Models and Algorithms for Stochastic Online Scheduling

job completes. Before we discuss the model and related work in more detail, let us fix some basic notation

and definitions.

Model and definitions. Given is a set J={1, . . . , n}of jobs, with nonnegative weights wj,j∈J.

In the model with release dates, rjdenotes the earliest point in time when job jcan be started. Each

job must be processed non-preemptively on any of the midentical machines, and each machine can only

handle one job at a time. The goal is to find a schedule that minimizes the total weighted completion

time PjwjCj, where Cjdenotes the completion time of job j. By Pjwe denote the random variable

for the processing time of job j, by E[Pj] its expected processing time, and by pja particular realization

of Pj. The processing time distributions Pjare assumed to be independent. We assume that the jobs are

arriving over time upon their respective release dates rjin the order 1, . . . , n. Therefore, we can assume

w.l.o.g. that rj≤rkfor j < k. Notice that the number of jobs nis not known in advance. When a job

arrives at time rj, the scheduler is informed about its weight wjand its expected processing time E[Pj].

The goal is to find a stochastic online scheduling policy that minimizes the expected value of the

weighted completion times of jobs, E[PwjCj]. Our definition of a stochastic online scheduling policy

extends the traditional definition of stochastic scheduling policies by M¨ohring et al. [20] to the setting

where jobs arrive online. A scheduling policy specifies actions at decision times t. An action is a set of

jobs that is started at time t, and a next decision time t0> t at which the next action is taken, unless

some job is released or ends at time t00 < t0. In that case, t00 becomes the next decision time. In order to

decide, the policy may utilize the complete information contained in the partial schedule up to time t, as

well as information about unscheduled jobs that have arrived before t. However, a policy is required to be

non-anticipatory, thus at any time, it must neither utilize any information about jobs that will be released

in the future, nor must it utilize the actual processing times of jobs that are scheduled (or unscheduled)

but not yet completed. An optimal scheduling policy is defined as a non-anticipatory scheduling policy

that minimizes the objective function value in expectation. An optimal scheduling policy generally fails

to yield an optimal solution for all realizations of the processing times; this because it is non-anticipatory.

For any realization p= (p1, . . . , pn) of processing times of the jobs, a scheduling policy yields a feasible

m-machine schedule. For a given policy, denoted by Π, let SΠ

j(p) and CΠ

j(p) the start and completion

times of job jfor a given realization p, and let SΠ

j(P) and CΠ

j(P) denote the associated random variables.

Unless there is danger of ambiguity, we also write Sjand Cj, for short. We let

E[Π(P)] = EhXjwjCΠ

j(P)i=XjwjECΠ

j(P)

denote the expected performance of a scheduling policy Π. Let us denote the above defined model as

SoS, for stochastic online scheduling.

Generalizing the definitions by M¨ohring et al. in [21] for traditional stochastic scheduling, we define

the performance guarantee of a stochastic online scheduling policy as follows.

Definition 1.1 A stochastic online scheduling policy (SoS policy) Π is a ρ–approximation if, for some

ρ≥1, and all instances of the given problem,

E[Π(P)] ≤ρE[OPT(P)] .

Here, OPT denotes an optimal stochastic scheduling policy on the given instance, assuming a priori

knowledge of the set of jobs J, their weights wj, release dates rj, and processing time distributions Pj.

The constant ρis called the performance guarantee of policy Π.

Notice that the stochastic online scheduling policy Π in this definition does not have a priori knowledge

of the set of jobs J, their weights wj, release dates rj, and processing time distributions Pj. Policy Π is

an online policy, and only learns about the existence of any job jupon its release date rj. Hence, the

policy has to compete with an adversary that knows the online sequence of jobs in advance. However,

with respect to the processing times Pjof the jobs, the adversary is just as powerful as the policy Π

itself, since it does not foresee their actual realizations pjeither.

Probably the best known scheduling policy in stochastic scheduling is the WSEPT rule. Its online

version will also play a prominent role in this paper, and is defined next. To this end, call a job javailable

at a given time tif it has not yet been scheduled, and if its release date has passed, that is, if rj≤t.

Megow, Uetz, Vredeveld: Models and Algorithms for Stochastic Online Scheduling 3

Definition 1.2 (Online WSEPT, weighted shortest expected processing time first)At any point in

time when a machine is idle, among all jobs that are available, schedule the job with the highest ra-

tio of weight over expected processing time, wj/E[Pj].

Whenever release dates are absent, it reduces to the traditional WSEPT rule known from stochastic

scheduling, and the jobs appear in the schedule in order of non-increasing ratios wj/E[Pj]. For unit

weights, it reduces to SEPT, shortest expected processing time first. For single machine (stochastic)

scheduling without release dates, 1 | |PwjCj, the WSEPT rule is optimal; this follows by a simple job

interchange argument [23, 29].

Related work. Stochastic machine scheduling models have been addressed mainly since the 1980s [9].

In the traditional stochastic setting, Weiss [33, 34] analyzes the performance of the WSEPT rule. He

derives additive performance bounds for the stochastic parallel machine model without release dates,

P||E[PwjCj]. His bounds yield asymptotic optimality of the WSEPT rule for a certain class of pro-

cessing time distributions. More recently, approximation algorithms for stochastic machine scheduling

have been derived by M¨ohring et al. [21] and Skutella and Uetz [26]. In these papers, the expected

performance of the WSEPT rule, and linear programming based stochastic scheduling policies, are com-

pared against the expected performance of an optimal stochastic scheduling policy. The results are

constant-factor approximations for models without or with release dates [21], and also with precedence

constraints [26]. However, these papers do not address the situation where jobs arrive online.

In contrast to traditional stochastic scheduling, in online scheduling it is assumed that nothing is

known about jobs that are about to arrive in the future. However, once a job becomes known, its weight

wjand its actual processing time pjare disclosed. The quality of online algorithms is assessed by their

competitive ratio [15, 28]. An algorithm is called ρ-competitive if, for any instance, a solution is achieved

with value not worse than ρtimes the value of an optimal off-line solution. In the online-time model jobs

become known upon their release dates rj. In the online-list model, jobs are presented one-by-one, all

at time 0. Upon presentation, a job has to be scheduled immediately before the next job can be seen (at

some time that is feasible with respect to release dates and the already scheduled jobs). We omit further

details and refer to Borodin and El-Yaniv [3] or Pruhs et al. [22].

In the online-list model, Fiat and Woeginger [11] show that the single machine problem 1 |rj|PCj

does not allow a deterministic or randomized online algorithm with a competitive ratio of log n. In the

online-time model, Anderson and Potts [2] provide a 2-competitive online algorithm for the same problem.

This result is best possible, since Hoogeveen and Vestjens [14] prove a lower bound of 2 on the competitive

ratio of any deterministic online algorithm. For settings with parallel machines, Vestjens [32] proves a

lower bound of 1.309 for the competitive ratio of any deterministic online algorithm for P |rj|PwjCj,

even for unit weights. The currently best known deterministic algorithm for P |rj|PwjCjis 2.62-

competitive, proposed by Correa and Wagner [8]. The currently best known randomized algorithm for

the problem has an expected competitive ratio of 2; see Schulz and Skutella [25].

A model that combines features of stochastic and online scheduling has also been considered by Chou

et al. [7]. They prove asymptotic optimality of the online WSEPT rule for the single machine problem

1|rj|PwjCj, assuming that the weights wjand processing time pjcan be bounded by constants. The

definition of the adversary in their paper coincides with our definition. Hence, asymptotic optimality

means that the ratio of the expected performance of the WSEPT rule over the expected performance of

an optimal stochastic scheduling policy tends to 1 as the number of jobs tends to infinity.

A different type of analysis for stochastic scheduling has been proposed by Steger et al. [24, 30]. Both

papers address the parallel machine model without release dates. They compare the performance of the

(W)SEPT rule to the optimal solution per realization, and take the expectation of this ratio on the basis

of the given processing time distributions. Their analysis is thus different from the traditional stochastic

scheduling model; in particular is it not based upon an comparison to the optimal stochastic scheduling

policy. Although the underlying adversary is stronger than in traditional stochastic scheduling, they

derive constant bounds on what they call the expected competitive ratio.

Results and methodology. We propose simple, combinatorial online scheduling policies for stochas-

tic online scheduling models on parallel machines with and without release dates, and derive constant

4Megow, Uetz, Vredeveld: Models and Algorithms for Stochastic Online Scheduling

performance bounds for these policies.

For identical parallel machine scheduling without release dates, P||E[PwjCj], the performance guar-

antee is

ρ= 1 + (m−1)(∆ + 1)

2m.

Here, ∆ is an upper bound on the squared coefficients of variation of the processing time distributions

Pj, that is,

CV [Pj]2= Var [Pj]/E[Pj]2≤∆ for all jobs j .

This performance guarantee matches the previously best known performance guarantee of M¨ohring et

al. [21]; they obtain the same bound for the performance of the WSEPT rule in the traditional stochastic

scheduling model. However, we derive this bound for a model other than traditional stochastic schedul-

ing. More precisely, we consider a stochastic online model where the jobs are presented to the scheduler

sequentially, and the scheduler must immediately and irrevocably assign jobs to machines, without knowl-

edge of the jobs to come. Therefore we also speak of fixed-assignment policies. Once the jobs are assigned

to the machines, the jobs on each machine can be sequenced in any order. We thus show that there exists

a fixed-assignment policy that achieves the same performance guarantee as the above mentioned bound

for the WSEPT rule. In this context, notice that the traditional WSEPT rule is not a fixed-assignment

policy, since the assignment of jobs to machines depends on the actual realizations of the processing

times.

For the model with release dates, P |rj|PwjCj, we prove a slightly more complicated performance

guarantee that is valid for a class of processing time distributions that we call δ-NBUE, generalizing the

well known class of NBUE distributions (new better than used in expectation).

Definition 1.3 (δ-NBUE) A non-negative random variable Xis δ-NBUE if, for δ≥1,

E[X−t|X > t ]≤δE[X]for all t≥0.

For identical parallel machine scheduling with release dates P |rj|PwjCj, and δ-NBUE distributions,

we obtain a performance guarantee of

ρ= 1 + max 1 + δ

α, α +δ+(m−1)(∆ + 1)

2m.

Here, α > 0 is an arbitrary parameter, and again, ∆ is an upper bound on the squared coefficients of

variation Var[Pj]/E[Pj]2of the processing time distributions Pj. In particular, since we show in the

appendix that Var[Pj]/E[Pj]2≤2δ−1 for δ-NBUE distributions, we get

ρ≤1 + max {1 + δ/α , α +δ(2m−1)/m}.

Optimizing for αyields that ρ < 3/2+(1−1/(2m))δ+√1+4δ2/2. For for ordinary NBUE distributions,

where δ= 1, we thus obtain a performance bound strictly less than (√5+5)/2−1/(2m)≈3.62−1/(2m).

Thereby, we improve upon the previously best known performance guarantee of 4 −1/m for traditional

stochastic scheduling, which was derived for an LP based list scheduling policy [21]. Again, this improved

bound holds even though we consider an online model in which the jobs arrive over time, and the scheduler

does not know anything about the jobs that are about to arrive in the future. Moreover, for deterministic

processing times, where ∆ = 0 and δ= 1, we get ρ= 2 + max{1/α , α + (m−1)/(2m)}; optimizing for

αyields ρ≈3.28, matching the bound from deterministic online scheduling by Megow and Schulz [18].

For both models, our results are in fact achieved by fixed-assignment policies. That is, whenever a job

is presented to the scheduler, it is immediately and irrevocably assigned to a machine. The sequencing

of jobs on the individual machines is in both cases (an online version of) the traditional WSEPT rule.

2. Discussion and further preliminaries. As a matter of fact, results in stochastic scheduling

either rely on the traditional (W)SEPT rule [21, 24, 30, 33, 34] for models without release dates, or they

use linear programming relaxations to define list scheduling policies other than WSEPT [21, 26]. As soon

as we assume that jobs arrive online, these approaches fail: the traditional off-line (W)SEPT rule cannot

be implemented since it requires an a priori ordering of jobs in order of ratios wj/E[Pj]. Moreover, for

the models with release dates, optimal LP solutions are not only required for the purpose of analysis, but

also to define the corresponding list scheduling policies [21]. Hence, it is required to know beforehand the

Megow, Uetz, Vredeveld: Models and Algorithms for Stochastic Online Scheduling 5

set of jobs J, their expected processing times E[Pj], and in the case with release dates also a uniform

upper bound ∆ on the squared coefficient of variation of all processing times distributions. Although

we still use the same linear programming relaxation as M¨ohring et al. [21] within our analysis, the main

difference lies in the fact that the algorithms we propose are purely combinatorial, and do not require

the solution of linear programs in advance.

As in traditional online optimization, the adversary in the SoS model may choose an arbitrary sequence

of jobs as well. These jobs, however, are stochastic, with corresponding processing time distributions.

The actual processing times are realized according to exogenous probability distributions. Thus, the best

the adversary can do is indeed to use an optimal stochastic scheduling policy in the traditional definition

of stochastic scheduling policies by M¨ohring et al. [20]. In this view, our model somewhat compares to

the idea of a diffuse adversary as defined by Koutsoupias and Papadimitriou [16]. Since deterministic

processing times are contained as a special case, however, all lower bounds on the approximability known

from deterministic online scheduling also hold for the SoS model of the present paper. Hence, no SoS

policy can exist with a performance bound better than 1.309 [32].

Observe that the expected performance of any stochastic online policy is by definition no less than the

expected performance of an optimal policy for a corresponding traditional stochastic problem, where the

set of jobs J, their weights wj, and their processing time distributions Pjare given at the outset. Hence,

lower bounds on the expected objective value of an optimal stochastic scheduling policy carry over to the

stochastic online setting that we consider in this paper. Therefore, we have the following lower bound

on the performance of any stochastic online scheduling policy; it is a generalization of a lower bound by

Eastman et al. [10] to stochastic processing times.

Lemma 2.1 (M¨ohring et al. [21]) For any instance of P|rj|E[PwjCj], we have that

E[OPT(P)] ≥X

wjX

k∈H(j)

E[Pk]

m−(m−1)(∆ −1)

2mX

wjE[Pj],

where ∆bounds the squared coefficient of variation of the processing times, that is, Var[Pj]/E[Pj]2≤∆

for all jobs j= 1, . . . , n and some ∆≥0.

Here, we have used a piece of notation that comes handy also later. For a given job j∈J,H(j) denotes

the jobs that have a higher priority in the order of ratios wj/E[Pj], that is

H(j) = k∈J|wk

E[Pk]>wj

E[Pj]∪k≤j|wk

E[Pk]=wj

E[Pj].

Accordingly, we define

L(j) = J\H(j)

as those jobs that have lower priority in the order of ratios wj/E[Pj]. As a tie-breaking rule for jobs k

with equal ratio wk/E[Pk] = wj/E[Pj] we decide depending on the position in the online sequence

relative to j. That is, if k≤jthen kbelongs to set H(j), otherwise it is included in set L(j). Notice

that, by convention, we assume that H(j) contains job j, too.

3. Stochastic online scheduling on a single machine. In this section we consider the stochastic

online scheduling problem on a single machine. When release dates are absent, it is well known that the

WSEPT rule is optimal [23, 29].

For the problem of scheduling jobs with nontrivial release dates on a single machine, the currently

best known result from traditional stochastic scheduling is an LP-based list scheduling algorithm with a

performance bound of 3 [21]. Inspired by a corresponding algorithm for the deterministic online setting

on parallel machines from [18], we propose the following scheduling policy.

Algorithm 1:α-Shift-WSEPT

Modify the release date rjof each job jto r0

j= max{rj, α E[Pj]}, for

some fixed α > 0. At any time t, when the machine is idle, start the

job with highest ratio wj/E[Pj] among all available jobs, respecting

the modified release dates. (In case of ties, smallest index first.)

6Megow, Uetz, Vredeveld: Models and Algorithms for Stochastic Online Scheduling

We first derive an upper bound on the expected completion time of a job, ECα

j, when scheduling jobs

on a single machine according to the α-Shift-WSEPT policy.

Lemma 3.1 Let all processing times be δ-NBUE. Then the expected completion time of job junder α-

Shift-WSEPT on a single machine can be bounded by

ECα

j≤(1 + δ/α)r0

j+X

k∈H(j)

E[Pk].

Proof. We consider some job j. Let Xdenote a random variable measuring the remaining processing

time of a job being processed at time r0

j, if such a job exists. Otherwise Xhas value 0. Moreover, for

any job k, let ξkbe an indicator random variable that equals 1 if and only if job kstarts processing at

the earliest at time r0

j, i.e., ξk= 1 if and only if Sα

k≥r0

j. The start of job jwill be postponed beyond r0

by X, and until there are no more higher priority jobs available. Hence, the expected start time of job j

can be bounded by

ESα

j≤Ehr0

j+X+X

k∈H(j)\{j}

Pkξki

=r0

j+E[X] + X

k∈H(j)\{j}

E[Pkξk]

≤r0

j+E[X] + X

k∈H(j)\{j}

E[Pk],

where the last inequality follows from the fact that Pkξk≤Pkfor any job k.

Next, we show that E[X]≤(δ/α)r0

j. If the machine just finishes a job at time r0

jor is idle at that

time, Xhas value 0. Otherwise, some job `is in process at time r0

j. Note that this job might have

lower or higher priority than job j. Such job `was available at time r0

`< r0

j, and by definition of the

modified release dates, we therefore know that E[P`]≤(1/α)r0

`<(1/α)r0

jfor any such job `. Moreover,

letting t=r0

j−Sα

`, the expected remaining processing time of such job `, given that it is indeed in

process at time r0

j, is E[P`−t|P`> t ]. Due to the assumption of δ-NBUE processing times, we thus

know that

E[P`−t|P`> t ]≤δE[P`]≤(δ/α)r0

for any job `that could be in process at time r0

j. Hence, we obtain E[X]≤(δ/α)r0

j. Finally, the fact

that ECα

j=ESα

j+E[Pj] concludes the proof. 

In fact, it is quite straightforward to use Lemma 3.1 in order to show the following.

Theorem 3.1 The α-Shift-WSEPT algorithm is a (δ+2)-approximation for the stochastic online single

machine problem 1|rj|E[PwjCj], for δ-NBUE processing times. The best choice for αis α= 1.

Proof. With Lemma 3.1 and the definition of modified release dates r0

j= max{rj, α E[Pj]}we can

bound the expected value of a schedule obtained by α-Shift-WSEPT.

wjECα

j≤(1 + δ/α)X

wjmax {rj, α E[Pj]}+X

wjX

k∈H(j)

E[Pk]

wjmax n(1 + δ/α)rj,(α+δ)E[Pj]o+X

wjX

k∈H(j)

E[Pk]

≤max n(1 + δ/α),(α+δ)oX

wj(rj+E[Pj]) + X

wjX

k∈H(j)

E[Pk].

We can now apply the trivial lower bound Pjwj(rj+E[Pj]) ≤E[OPT(P)], and exploit the fact that

PjwjPk∈H(j)E[Pk]≤E[OPT(P)] by Lemma 2.1 (for m= 1), and obtain

wjECα

j≤1 + max n1 + δ

α, α +δoE[OPT(P)] .

Simple analysis shows that α= 1 minimizes the expression above, independently of δ, and the theorem

follows. 

Megow, Uetz, Vredeveld: Models and Algorithms for Stochastic Online Scheduling 7

Note that for NBUE processing times, the result matches the best known performance bound of 3

derived by M¨ohring et. al in [21] for the traditional stochastic scheduling model. In contrast to α-Shift-

WSEPT, however, their LP-based policy requires an a priori knowledge of the set of jobs J, their weights

wj, and their expected processing times E[Pj]. Moreover, in the deterministic online setting, the best

possible algorithm is 2-competitive as shown in [14], hence the corresponding lower bound of 2 holds for

the stochastic online setting as well.

4. Stochastic online scheduling on parallel machines. In this section, we define stochastic

online scheduling policies for the problem on parallel machines. We first consider the problem without

nontrivial release dates, i.e., rj= 0 for all jobs j∈J. Later, we generalize the policy for the problem

with nontrivial release dates.

4.1 Scheduling jobs without release dates. In the case that all jobs arrive at time 0, the problem

effectively turns into a traditional stochastic scheduling problem, P | |E[PwjCj]. For that problem, it

is known that the WSEPT rule yields a (1 + (m−1)(∆ + 1)/(2m))-approximation, ∆ being an upper

bound on the squared coefficients of variation of the processing time distributions [21].

Nevertheless, we consider an online variant of the problem P | |E[PwjCj] that resembles the online-

list model from online optimization. We assume that the jobs are presented to the scheduler sequentially,

and each job must immediately and irrevocably be assigned to a machine: a fixed-assignment policy.

In particular, during this assignment phase, the scheduler does not know anything about the jobs that

are still about to come. Once the jobs are assigned to the machines, the jobs on each machine may

be sequenced in any order. We show that an intuitive and simple fixed-assignment policy exists that

eventually yields the same performance bound as the one proved in [21] for the WSEPT rule. Note,

however, that the WSEPT rule is not a feasible online policy in the model we consider here.

We introduce the following notation: If a job jis assigned to machine i, this is denoted by j→i. Now

we can define the MinIncrease policy as follows.

Algorithm 2:MinIncrease (MI)

When a job jis presented to the scheduler, it is assigned to the machine ithat

minimizes the expression

z(j, i) = wj·X

k∈H(j), k<j, k→i

E[Pk] + E[Pj]·X

k∈L(j), k<j, k→i

wk+wjE[Pj].

Once all jobs are assigned to machines, the jobs on each machine are sequenced in

order of non-increasing ratios wj/E[Pj].

Since WSEPT is known to be optimal on a single machine, MinIncrease in fact assigns each job j

to that machine where it causes the least increase in the expected objective value, given the previously

assigned jobs. This is expressed in the following lemma.

Lemma 4.1 The expected objective value E[MI(P)] of the MinIncrease policy equals Pjminiz(j, i).

Proof. The assignment of jobs to machines is independent of the realization of processing times.

Hence, the expected completion time E[Cj] for some job jthat has been assigned to machine ijby

MinIncrease is

E[Cj] = X

k∈H(j), k→ij

E[Pk],

because all jobs that are assigned to the same machine ijare sequenced in order of non-increasing ratios

wj/E[Pj]. Now, weighted summation over all jobs gives by linearity of expectation

E[MI(P)] = EhXjwjCji

wjX

k∈H(j), k→ij

E[Pk]

wjX

k∈H(j), k→ij,k<j

E[Pk] + X

wjX

k∈H(j), k→ij,k>j

E[Pk] + X

wjE[Pj].

8Megow, Uetz, Vredeveld: Models and Algorithms for Stochastic Online Scheduling

This allows us to apply the following index rearrangement.

wjX

k∈H(j), k>j

E[Pk] = X

E[Pj]X

k∈L(j), k<j

wk.(1)

Thus, we have

E[MI(P)] = X

wjX

k∈H(j), k→ij,k<j

E[Pk] + X

E[Pj]X

k∈L(j), k→ij,k<j

wk+X

wjE[Pj]

jwjX

k∈H(j), k→ij,k<j

E[Pk] + E[Pj]X

k∈L(j), k→ij,k<j

wk+wjE[Pj]

min

iz(j, i),

where the second equality makes use of (1) applied to each individual machine ij, and the last equality

holds since ijis the machine minimizing z(j, i) over all machines i.

Now, we can derive the following performance guarantee for the MinIncrease policy.

Theorem 4.1 Consider the stochastic online scheduling problem on parallel machines, P||E[PwjCj],

as described above. Given that Var[Pj]/E[Pj]2≤∆for all jobs jand some constant ∆≥0, the

MinIncrease policy is a ρ–approximation, where

ρ= 1 + (m−1)(∆ + 1)

2m.

Proof. From Lemma 4.1 we know that E[MI(P)] = Pjminiz(j, i) and, thus,

E[MI(P)] = X

min

iwjX

k∈H(j), k<j, k→i

E[Pk] + E[Pj]X

k∈L(j), k<j, k→i

wk+wjE[Pj]

≤X

mwjX

k∈H(j), k<j

E[Pk] + E[Pj]X

k∈L(j), k<j

wk+X

wjE[Pj],

where the inequality holds because the least expected increase is not more than the average expected

increase over all machines.

Now, we first apply the index rearrangement (1) as in Lemma 4.1, and then plug in the inequality

of Lemma 2.1. Using the trivial fact that PjwjE[Pj] is a lower bound for the expected performance

E[OPT(P)] of an optimal policy, we thus obtain

E[MI(P)] ≤1

jwjX

k∈H(j), k<j

E[Pk] + wjX

k∈H(j), k>j

E[Pk]+X

wjE[Pj]

wjX

k∈H(j)

E[Pk] + m−1

wjE[Pj]

≤E[OPT(P)] + (m−1)(∆ −1)

2mX

wjE[Pj] + m−1

wjE[Pj]

≤1 + (m−1)(∆ + 1)

2m·E[OPT(P)] .



As mentioned above, this performance guarantee matches the currently best known performance guar-

antee for the traditional stochastic setting, which was derived for the performance of the WSEPT rule

in [21]. The WSEPT rule, however, requires the knowledge of all jobs with their weights wjand ex-

pected processing times E[Pj] at the outset. In contrast, the MinIncrease policy decides on machine

assignments online, without any knowledge of the jobs to come. Finally, notice that these two policies

are indeed different; this follows from simple examples.

Megow, Uetz, Vredeveld: Models and Algorithms for Stochastic Online Scheduling 9

Lower bound for fixed assignment policies. The requirement of a fixed assignment of jobs to

machines beforehand may be interpreted as ignoring the additional information that evolves over time in

the form of the actual realization of processing times. In the following, we therefore give a lower bound

on the expected performance E[FIX(P)] of an optimal stochastic scheduling policy FIX that assigns jobs

to machines beforehand. A fortiori, this lower bound holds for the best possible SoS policy, too.

Theorem 4.2 For stochastic parallel machine scheduling with unit weights and i.i.d. exponential pro-

cessing times, P|pj∼exp(1)|E[PCj], there exist instances such that

E[FIX(P)] ≥3(√2−1) ·E[OPT(P)] −ε ,

for any ε > 0. Here, 3(√2−1) ≈1.24. Hence, no policy that uses fixed assignments of jobs to machines

can perform better in general.

Notice that the theorem is formulated for the special case of exponentially distributed processing times.

Stronger bounds can be obtained for arbitrary distributions. However, since our performance guarantees,

as in [21], depend on the coefficient of variation of the processing times, we are particularly interested

in lower bounds for classes of distributions where this coefficient of variation is small. The coefficient

of variation of exponentially distributed random variables equals 1. For example, for the case of m= 2

machines, we get a lower bound of 8/7≈1.14 on the performance of any fixed-assignment policy, and for

that case the performance bound of MinIncrease equals 2 −1/m = 1.5.

Proof of Theorem 4.2. Let us consider an instance with mmachines and n=m+kexponentially

distributed jobs, Pj∼exp(1), where k≥1 is an integer. The optimal stochastic scheduling policy is

SEPT, shortest expected processing time first [4, 35], and the expected performance is (see, e.g., [31,

Cor. 3.5.17])

E[OPT(P)] = E[SEPT(P)] = X

ECSEPT

j=m+

j=m+1

m=m+k+k(k+ 1)

2m.

When, in a fixed assignment, one machine has to process at least two jobs more than another machine,

the assignment can be improved by moving one job from the most loaded machine to the least loaded

machine. Therefore, the best fixed assignment policy tries to distribute the jobs evenly over the machines.

That is, it assigns 1 + bk

mcjobs to m−k+mbk

mcmachines and 1 + dk

mejobs to k−mbk

mcmachines.

Hence, there are mjobs with E[Cj] = l(l= 1, . . . , 1 + bk

mc) and k−mbk

mcjobs with E[Cj] = 2 + bk

mc.

The expected performance for the best fixed assignment policy FIX is

E[FIX(P)] = X

ECFIX

j=m+ 2k+k−m

2−m

2k

m·k

m.

For m < k ≤2m, this value is equal to E[FIX(P)] = 3k. Hence, for m < k ≤2m, the ratio

E[FIX(P)]/E[OPT(P)] is

E[FIX(P)]

E[OPT(P)] =3k

m+k+k(k+ 1)/(2m),

which is maximized for k(m)∈ {b√2mc,d√2me}. With this choice of k, the ratio E[FIX(P)]/E[OPT(P)]

tends to 3√2/(2 + √2) = 3(√2−1) ≈1.24 as mtends to infinity. 

Notice that the lower bound of 1.24 holds whenever m, the number of machines, tends to infinity.

For smaller numbers of machines, e.g. m= 2,3,4, . . . we use smaller numbers k=k(m), namely

k(2) = 1, k(3) = 2, k(4) = 2, . . . , and obtain the lower bounds 8/7≈1.14, 7/6≈1.16, 32/27 ≈1.18, . . . .

Lower bound for MinIncrease.The lower bound on the performance ratio for any fixed assignment

policy given in Theorem 4.2 holds for the MinIncrease policy, too. Hence, MinIncrease cannot be

better than 1.24-approximative. For general (i.e., non-exponential) probability distributions we obtain a

lower bound of 3/2 on the expected performance of MinIncrease relative to the expected performance

of an optimal scheduling policy, as shown by the following instance.

Example 4.1 The instance consists of n−1deterministic unit length jobs and one job with a stochastic

two-point distributed processing time. There are m= 2 machines, and we assume that n, the number

10 Megow, Uetz, Vredeveld: Models and Algorithms for Stochastic Online Scheduling

of jobs is even. The n−1deterministic jobs have unit weight wj= 1; they appear first in the online

sequence. The final job in the online sequence is the stochastic job. It has processing time pj=n2/4with

probability 2/n, and pj= 1 with probability 1−2/n. The weight wjof the stochastic job equals the value

of its expected processing time, i.e. 1−2/n +n/2.

The MinIncrease policy assigns n/2−1 deterministic jobs to one machine, and n/2 deterministic

jobs to the other. The stochastic job is assigned to the machine with n/2−1 deterministic jobs. Hence,

the expected objective value of the schedule under MinIncrease is E[PwjCj]=3n2/4 + o(n2) . An

optimal stochastic policy would start the uncertain job and one deterministic job at time 0. At time

t= 1 it is known if the stochastic job has completed, or if it blocks the machine for another n2/4−1

time units. If the stochastic job has completed then the remaining unit jobs are distributed equally on

both machines, otherwise all deterministic jobs are scheduled on the same machine. Thus, the expected

objective value of an optimal schedule is E[OPT(P)] = n2/2 + o(n2). The ratio of both values tends to

3/2 if the number of jobs tends to infinity.

Notice, however, that this result is less meaningful in comparison to the performance bound of Theo-

rem 4.1, which depends on an upper bound ∆ on the squared coefficient of variation.

4.2 Scheduling jobs with nontrivial release dates. In this section, we consider the setting where

jobs arrive over time, that is, the stochastic online version of P |rj|E[PwjCj]. The main idea is to

adopt the MinIncrease policy to this setting. However, the difference is that we are no longer equipped

with an optimal policy (as it was WSEPT in the previous section) to schedule the jobs that are assigned

to a single machine. Even worse, even if we knew such a policy for a single machine, it would not be

straightforward how to use it in the setting with parallel machines to define a feasible online scheduling

policy. However, we propose to use the α-Shift-WSEPT rule as introduced in Section 3 to sequence

the jobs that we have assigned to the same machine. The assignment of jobs to machines, on the other

hand, remains the same as before in the case without release dates. In a sense, when assigning jobs to

machines, we thus ignore the possible gain of information that occurs over time in the online-time model.

Algorithm 3: Modified MinIncrease

When a job jis presented to the scheduler at its release date rj, it is assigned to

the machine ithat minimizes the expression

z(j, i) = wjX

k∈H(j), k<j, k→i

E[Pk] + E[Pj]X

k∈L(j), k<j, k→i

wk+wjE[Pj].

On each machine, the jobs assigned to this machine are sequenced according to

the α-Shift-WSEPT rule.

The crucial observation is that the α-Shift-WSEPT policy on machine ijlearns about job j’s existence

immediately at time rj. Hence, for each single machine, it is indeed feasible to use the α-Shift-WSEPT

rule, and the so-defined policy is a feasible SoS policy.

Theorem 4.3 Consider the stochastic online scheduling problem on parallel machines with release dates,

P|rj|E[PwjCj]. Given that all processing times are δ-NBUE, the modified MinIncrease policy running

α-Shift-WSEPT on each single machine is a ρ–approximation, where

ρ= 1 + max 1 + δ

α, α +δ+(m−1)(∆ + 1)

2m,

Here, ∆is such that Var[Pj]/E[Pj]2≤∆for all jobs j. In particular, since all processing times Pjare

δ-NBUE, Lemma A.1 yields that ∆≤2δ−1, hence ρ≤1 + max {1 + δ/α, α +δ(2m−1)/m}.

Proof. Let ijbe the machine to which job jis assigned. Then, by Lemma 3.1 we know that

E[Cj]≤1 + δ

αr0

j+X

k∈H(j), k→ij

E[Pk],(2)

Megow, Uetz, Vredeveld: Models and Algorithms for Stochastic Online Scheduling 11

and the expected value of MinIncrease can be bounded by

E[MI(P)] ≤1 + δ

αX

wjr0

j+X

wjX

k∈H(j), k→ij

E[Pk].(3)

For the second part of the right hand side of (3), we can use the same index rearrangement as in the

proof of Theorem 4.1; see (1). We thus obtain

wjX

k∈H(j), k→ij

E[Pk] = X



wjX

k∈H(j), k→ij, k<j

E[Pk] + E[Pj]X

k∈L(j), k→ij, k<j

wk+wjE[Pj]

.

By definition of the modified MinIncrease algorithm, we know that any job jis assigned to the

machine which minimizes the term in parenthesis. Hence, by the same averaging argument as before, we

know that

wjX

k∈H(j), k→ij

E[Pk]≤X



wjX

k∈H(j), k<j

E[Pk]

m+E[Pj]X

k∈L(j), k<j

m+wjE[Pj]



wjX

k∈H(j)

E[Pk]

m+m−1

wjE[Pj],

where the last equality again follows from index rearrangement. Plugging this into (3), leads to the

following bound on the expected performance of MinIncrease.

E[MI(P)] ≤1 + δ

αX

wjr0

j+X

wjX

k∈H(j)

E[Pk]

m+m−1

wjE[Pj].

Plugging the bound of Lemma 2.1 into the above inequality, we obtain

E[MI(P)] ≤1 + δ

αX

wjr0

j+E[OPT(P)] + (m−1)(∆ + 1)

2mX

wjE[Pj]

=E[OPT(P)] + X

wj1 + δ

αr0

j+(m−1)(∆ + 1)

2mE[Pj],(4)

where again, ∆ is an upper bound on the squared coefficient of variation of the processing time distribu-

tions Pj. By bounding r0

jby rj+αE[Pj], we obtain the following bound on the term in parenthesis of

the right hand side of (4).

1 + δ

αr0

j+(m−1)(∆ + 1)

2mE[Pj]

≤1 + δ

αrj+α+δ+(m−1)(∆ + 1)

2mE[Pj]

≤rj+E[Pj]max 1 + δ

α, α +δ+(m−1)(∆ + 1)

2m.

By using this inequality in equation (4), and applying the trivial lower bound Pjwj(rj+E[Pj]) ≤

E[OPT(P)] on the expected optimum performance, we get the claimed performance bound of

ρ= 1 + max 1 + δ

α, α +δ+(m−1)(∆ + 1)

2m.

Since all processing times are δ-NBUE, we know by Lemma A.1 in the appendix that ∆ ≤2δ−1 and

thus the second claim of the theorem follows, namely ρ≤1 + max{1 + δ/α, α +δ(2m−1)/m}.

For NBUE processing times, where ∆ = δ= 1, Theorem 4.3 yields a performance bound of

ρ= 2 + max 1

α, α +m−1

m.

This term is minimal for α= (√5m2−2m+ 1 −m+ 1)/(2m), which yields a ratio of ρ= 2 +

(√5m2−2m+1+m−1)/(2m). This is less than (5 + √5)/2−1/(2m)≈3.62 −1/(2m) improving

12 Megow, Uetz, Vredeveld: Models and Algorithms for Stochastic Online Scheduling

upon the previously best known bound of 4−1/m from [21] for the traditional stochastic problem. More

generally, for δ-NBUE processing times, optimizing the term max{1+δ/α, α+δ(2m−1)/m}for αyields

ρ < 3/2 + δ(2m−1)/2m+√4δ2+ 1/2.

Moreover, for deterministic processing times, where ∆ = 0 and δ= 1, Theorem 4.3 yields a performance

bound of

ρ= 2 + max 1

α, α +m−1

2m.

Optimizing for αyields α= (√17m2−2m+ 1 −m+ 1)/(4m), which yields a ratio of ρ= 2 +

(√17m2−2m+1+m−1)/(4m). This is less than 3.281 for any value of m, leaving only a small gap

to the currently best known bound of 2.62 for deterministic online scheduling [8]. In fact, it matches the

competitive ratio of the deterministic parallel machine version of α-Shift-WSEPT from [18].

4.3 Randomized job assignment. As a matter of fact, the MinIncrease policy can be inter-

preted as the derandomized version of a policy that assign jobs uniformly at random to the machines.

Even though randomly assigning jobs to machines ignores much information, it is nevertheless known to

be quite powerful as has been observed already by, e.g., Schulz and Skutella [25]. They apply a random

assignment strategy, based on the solution of an LP-relaxation, for scheduling jobs with deterministic

processing times on unrelated machines. For the special case of identical machines, their approach corre-

sponds to assigning jobs uniformly at random to the machines. The random assignment strategy for the

stochastic online scheduling problem at hand is as follows.

Algorithm 4: RandAssign

When a job is presented to the scheduler, it is assigned to machine i

with probability 1/m for all i= 1, . . . , m. The jobs assigned to

machine iare scheduled according to the α-Shift-WSEPT policy.

Theorem 4.4 Consider the stochastic online scheduling problem on parallel machines with release dates,

P|rj|E[PwjCj]. Given that all processing times are δ-NBUE, the RandAssign policy running α-Shift-

WSEPT on each single machine is a ρ–approximation, where

ρ= 1 + max 1 + δ

α, α +δ+(m−1)(∆ + 1)

2m,

Here, ∆is such that Var[Pj]/E[Pj]2≤∆for all jobs j. In particular, since all processing times Pjare

δ-NBUE, Lemma A.1 yields that ∆≤2δ−1, hence ρ≤1 + max {1 + δ/α, α +δ(2m−1)/m}.

Proof. Consider a job jand let idenote the machine to which it has been assigned. Let Pr [j→i]

be the probability for job jbeing assigned to machine i. Then, by Lemma 3.1 we know that

E[Cj|j→i]≤1 + δ

αr0

j+X

k∈H(j)

Pr [k→i|j→i]·E[Pk|j→i]

=1 + δ

αr0

j+X

k∈H(j)

Pr [k→i|j→i]·E[Pk].

The probability that a job is assigned to a certain machine is equal for all machines, i.e., Pr [j→i] = 1/m

for all i= 1, . . . , m, and for any job j. Unconditioning the expected value of job j’s completion time

yields

E[Cj] =

i=1

Pr [j→i]·E[Cj|j→i]

≤1 + δ

αr0

i=1

Pr [j→i]·X

k∈H(j)

Pr [k→i|j→i]·E[Pk]

=1 + δ

αr0

j+X

k∈H(j)

E[Pk]

m+m−1

mE[Pj],

Megow, Uetz, Vredeveld: Models and Algorithms for Stochastic Online Scheduling 13

where the last equality is due to the independence of the job assignments to the machines. Then, the

expected objective value of RandAssign,E[RA(P)], can be bounded by

E[RA(P)] = X

wjE[Cj]

≤1 + δ

αX

wjr0

j+X

wjX

k∈H(j)

E[Pk]

m+m−1

wjE[Pj].

This bound equals the upper bound that we achieved on the expected performance of the MinIncrease

policy in the proof of Theorem 4.3. Hence, we conclude the proof in the same way and with the same

result as for MinIncrease.

Acknowledgments. The authors thank the two anonymous referees for valuable comments, and

Martin Skutella for pointing out that the MinIncrease algorithm can be interpreted as the derandom-

ization of an algorithm that distributes jobs to machines at random. Thanks to Rolf H. M¨ohring for

helpful discussions, and Andreas S. Schulz and Sven O. Krumke for pointing out some misinterpretations

in an earlier version of this paper.

References

[1] F. N. Afrati, E. Bampis, C. Chekuri, D. R. Karger, C. Kenyon, S. Khanna, I. Milis, M. Queyranne,

M. Skutella, C. Stein, and M. Sviridenko, Approximation schemes for minimizing average weighted

completion time with release dates, Proceedings of the 40th Annual Symposium on Foundations of

Computer Science (FOCS), 1999, pp. 32–43.

[2] E. J. Anderson and C. N. Potts, On-line scheduling of a single machine to minimize total weighted

completion time, Mathematics of Operations Research 29 (2004), 686–697.

[3] A. Borodin and R. El-Yaniv, Online computation and competitive analysis, Cambridge University

Press, 1998.

[4] J. L. Bruno, P. J. Downey, and G. N. Frederickson, Sequencing tasks with exponential service times

to minimize the expected flowtime or makespan, Journal of the ACM 28 (1981), 100–113.

[5] S. Chakrabarti and S. Muthukrishnan, Resource scheduling for parallel database and scientific appli-

cations, Proc. 8th Ann. ACM Symp. on Parallel Algorithms and Architectures (Padua, Italy), 1996,

pp. 329–335.

[6] C. Chekuri, R. Johnson, R. Motwani, B. Natarajan, B. Rau, and M. Schlansker, An analysis

of profile-driven instruction level parallel scheduling with application to super blocks, Proc. 29th

IEEE/ACM Int. Symp. on Microarchitecture (Paris, France), 1996, pp. 58–69.

[7] M.C. Chou, H. Liu, M. Queyranne, and D. Simchi-Levi, On the asymptotic optimality of a simple on-

line algorithm for the stochastic single machine weighted completion time problem and its extensions,

2005, To appear in Operations Research.

[8] J. Correa and M. Wagner, LP-based online scheduling: From single to parallel machines, Integer

Programming and Combinatorial Optimization (M. J¨unger and V. Kaibel, eds.), Lecture Notes in

Computer Science, vol. 3509, Springer, 2005, pp. 196–209.

[9] M. A. H. Dempster, J. K. Lenstra, and A. H. G. Rinnooy Kan (editors), Deterministic and stochastic

scheduling, D. Reidel Publishing Company, Dordrecht, 1982.

[10] W. Eastman, S. Even, and I. Isaacs, Bounds for the optimal scheduling of njobs on mprocessors,

Management Science 11 (1964), 268–279.

[11] A. Fiat and G. J. Woeginger, On-line scheduling on a single machine: Minimizing the total comple-

tion time, Acta Informatica 36 (1999), 287–293.

[12] R. L. Graham, E. L. Lawler, J. K. Lenstra, and A. H. G. Rinnooy Kan, Optimization and approx-

imation in deterministic sequencing and scheduling: A survey, Annals of Discrete Mathematics 5

(1979), 287–326.

[13] W. J. Hall and J. A. Wellner, Mean residual life, Proc. Int. Symp. on Statistics and Related Topics

(Ottawa, ON, Canada) (M. Cs¨org¨o, D. A. Dawson, J. N. K. Rao, and A. K. Md. E. Saleh, eds.),

North-Holland, Amsterdam, The Netherlands, 1981, pp. 169–184.

14 Megow, Uetz, Vredeveld: Models and Algorithms for Stochastic Online Scheduling

[14] H. Hoogeveen and A. P. A. Vestjens, Optimal on-line algorithms for single-machine scheduling,

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.

[15] A. Karlin, M. Manasse, L. Rudolph, and D. Sleator, Competitive snoopy paging, Algorithmica 3

(1988), 70–119.

[16] E. Koutsoupias and C. H. Papadimitriou, Beyond competitive analysis, SIAM Journal on Computing

30 (2000), 300–317.

[17] E. L. Lenstra, A. H. G. Rinooy Kan, and P. Brucker, Complexity of machine scheduling problems,

Annals of Discrete Mathematics 1(1977), 243–362.

[18] N. Megow and A. S. Schulz, On-line scheduling to minimize average completion time revisited, Op-

erations Research Letters 32 (2004), 485–490.

[19] N. Megow, M. Uetz, and T. Vredeveld, Stochastic online scheduling on parallel machines, Approx-

imation and Online Algorithms (G. Persiano and R. Solis-Oba, eds.), Lecture Notes in Computer

Science, vol. 3351, Springer, 2005, pp. 167–180.

[20] R. H. M¨ohring, F. J. Radermacher, and G. Weiss, Stochastic scheduling problems I: General strategies,

ZOR - Zeitschrift f¨ur Operations Research 28 (1984), 193–260.

[21] R. H. M¨ohring, A. S. Schulz, and M. Uetz, Approximation in stochastic scheduling: the power of

LP-based priority policies, Journal of the ACM 46 (1999), 924–942.

[22] K. Pruhs, J. Sgall, and E. Torng, Online scheduling, Handbook of Scheduling: Algorithms, Models,

and Performance Analysis (J. Leung, ed.), CRC Press, 2004.

[23] M. H. Rothkopf, Scheduling with random service times, Management Science 12 (1966), 703–713.

[24] M. Scharbrodt, T. Schickinger, and A. Steger, A new average case analysis for completion time

scheduling, Proc. 34th Ann. ACM Symp. on the Theory of Computing (Montr´eal, QB, Canada),

2002, pp. 170–178.

[25] A. S. Schulz and M. Skutella, Scheduling unrelated machines by randomized rounding, SIAM Journal

on Discrete Mathematics 15 (2002), 450–469.

[26] M. Skutella and M. Uetz, Stochastic machine scheduling with precedence constraints, SIAM Journal

on Computing 34 (2005), 788–802.

[27] M. Skutella and G.J. Woeginger, A PTAS for minimizing the total weighted completion time on

identical parallel machines, Mathematics of Operations Research 25 (2000), 63–75.

[28] D. Sleator and R. Tarjan, Amortized efficiency of list update and paging rules, Communications of

the ACM 28 (1985), 202–208.

[29] W. Smith, Various optimizers for single-stage production, Naval Research Logistics Quarterly 3

(1956), 59–66.

[30] A. Souza and A. Steger, The expected competitive ratio for weighted completion time scheduling,

Proc. 21st Symp. on Theoretical Aspects of Computer Science (V. Diekert and M. Habib, eds.),

Lecture Notes in Computer Science, vol. 2996, Springer, 2004, pp. 620–631.

[31] M. Uetz, Algorithms for deterministic and stochastic scheduling, Cuvillier Verlag, G¨ottingen, Ger-

many, 2002.

[32] A. P. A. Vestjens, On-line machine scheduling, Ph.D. thesis, Eindhoven University of Technology,

Netherlands, 1997.

[33] G. Weiss, Approximation results in parallel machines stochastic scheduling, Annals of Operations

Research 26 (1990), 195–242.

[34] , Turnpike optimality of Smith’s rule in parallel machines stochastic scheduling, Mathematics

of Operations Research 17 (1992), 255–270.

[35] G. Weiss and M. Pinedo, Scheduling tasks with exponential service times on non-identical processors

to minimize various cost functions, Journal of Applied Probability 17 (1980), 187–202.

Megow, Uetz, Vredeveld: Models and Algorithms for Stochastic Online Scheduling 15

Appendix A. Coefficient of variation for δ-NBUE random variables In this section, we show

the relation between the value of δand the (squared) coefficient of variation CV [X]2= Var [X]/E[X]2

for a δ-NBUE random variable X.

Lemma A.1 Let Xbe a δ-NBUE random variable and let CV[X]denote the coefficient of variation of

X. Then CV[X]2≤2δ−1.

Proof. We prove the lemma for continuous random variables X; the proof for discrete random

variables goes along the same lines. Let Xbe a non-negative δ-NBUE random variable, with cumulative

distribution function Fand density f.

By definition of conditional expectation, we know that

EX−t

X > t=R∞

t(x−t)f(x)dx

1−F(t).(5)

As x−t=Rx−t

0dy, we can write the nominator of the right hand side as

Z∞

x=t

(x−t)f(x)dx =Z∞

x=tZx−t

y=0

f(x)dydx =Z∞

y=0 Z∞

x=y+t

f(x)dxdy

=Z∞

x=t

1−F(x)dx, (6)

where the second equality is obtained by changing the order of integration.

As Xis δ-NBUE, i.e., E[X−t|X > t]≤δE[X], it follows from (5) and (6) that

Z∞

x=t

1−F(x)dx =EX−t

X > t(1 −F(t)) ≤δE[X] (1 −F(t)).(7)

By integrating the right hand side of the above inequality over t, we obtain

δE[X]Z∞

t=0

1−F(t)dt =δE[X]2.(8)

Hall and Wellner [13, Equality (4.1)] showed that integrating the left hand side of (7) over tyields

Z∞

t=0 Z∞

x=t

1−F(t)dt =1

2EX2.(9)

Hence, using (8) and (9) in (7), we have

EX2≤2δE[X]2.

Rearranging terms yields the desired bound on the squared coefficient of variation:

CV[X]2=EX2−E[X]2

E[X]2≤2δ−1.

