Models and Algorithms for Stochastic Online Scheduling [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.)

Loading more pages...