|
Article Excerpt
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 nonpreemptive 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 performance guarantees previously known for stochastic and online parallel machine scheduling, respectively. For processing times that follow new better than used in expectation (NBUE) distributions, we improve upon 2previously best-known performance bounds from stochastic scheduling, even though we consider a more general setting.
Key words: scheduling; stochastic dynamic optimization; online optimization; total weighted completion time; approximation
MSC2000 subject classification: Primary: 90B36; secondary: 68W40, 68W25, 68M20
OR/MS subject classification: Primary: production/scheduling; secondary: approximation/heuristic
History: Received January 6, 2005; revised September 7, 2005.
1. Introduction. Scheduling on identical parallel machines to minimize the total weighted completion time of jobs, P [parallel] [summation] [w.sub.j][C.sub.j] in 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 (Chakrabarti and Muthukrishnan [5]), or compiler optimization (Chekuri et al. [6]). The literature has witnessed many papers on this problem as well as its variant, where the jobs have individual release dates before which they must not be processed, P[absolute value of [r.sub.j]][summation][w.sub.j][C.sub.j]. In the offline (deterministic) setting, where the set of jobs and their characteristics are known in advance, the complexity status of both problems is solved; both are strongly NP- hard (Lenstra et al. [17]) and they admit a polynomial time approximation scheme (Afrati et al. [1], Skutella and Woeginger [28]).
To cope with scenarios where there is uncertainty about the future, there are two major frameworks in the theory of scheduling: (1) stochastic scheduling and (2) 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 distribution functions of 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) (Pruhs et al. [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 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 [w.sub.j], j [member of] J. In the model with release dates, [r.sub.j] denotes the earliest point in time when job j can be started. Each job must be processed nonpreemptively on any of the m identical 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 [[summation].sub.j][w.sub.j][C.sub.j], where [C.sub.j] denotes the completion time of job j. By P j, we denote the random variable for the processing time of job j, by E[[P.sub.j]], its expected processing time, and by [p.sub.j], a particular realization of [P.sub.j]. The processing time distributions [P.sub.j] are assumed to be independent. We assume that the jobs are arriving over time upon their respective release dates [r.sub.j] in the order 1, ..., n. Therefore, we can assume w.l.o.g, that [r.sub.j] [less than or equal to] [r.sub.k] for j < k. Note that the number of jobs n is not known in advance. When a job arrives at time [r.sub.j], the scheduler is informed about its weight [w.sub.j] and its expected processing time, E[[P.sub.j]].
The goal is to find a stochastic online scheduling (SOS) policy that minimizes the expected value of the weighted completion times of jobs, E[[summation][w.sub.j][C.sub.j]]. Our definition of an SOS policy extends the traditional definition of stochastic scheduling policies by M6hring 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 t' > t at which the next action is taken, unless some job is released or ends at time t" < t'. In that case, t" becomes the next decision time. 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 online, thus at any time, it must not utilize any information about jobs that will be released in the future. Moreover, it needs to be nonanticipatory, thus at any time, it must not utilize the actual processing times of jobs that are scheduled (or unscheduled) but not yet completed. An optimal scheduling policy is defined as a nonanticipatory scheduling policy that minimizes the objective function value in expectation. Note that we do not assume that an optimal policy needs to be online. Note also that even an optimal scheduling policy generally fails to yield an optimal solution for all realizations of the processing times; this is because it is nonanticipatory.
For an instance I, consisting of the number of machines m, the set of jobs J together with their release dates [r.sub.j], weights [w.sub.j], and processing time distributions [P.sub.j], let [S.sup.[PI].sub.j](I) and [C.sup.[PI].sub.j](1) denote the random variables for start and completion times of jobs under policy [PI]. We also write [S.sup.[PI].sub.j] and [C.sup.[PI].sub.j] for short. We let
E[[PI](I)] = E[[summation over j [member of] J][w.sub.j][C.sup.[PI].sub.j](I)] = [summation over j [member of] J][w.sub.j]E[[C.sup.[PI].sub.j](I)]
denote the expected performance of a scheduling policy [PI] on instance I. Let us denote the above-defined model as stochastic online scheduling (SOS).
Generalizing the definitions by Mtihring et al. in [21] for traditional stochastic scheduling, we define the performance guarantee of an SOS policy as follows.
DEFINITION 1.1. An SOS policy [PI] is a [rho]-approximation if, for some [rho] [greater than or equal to] 1, and all instances I of the given problem,
E[[PI](I)] [less than or equal to] [rho]E[OPT(I)].
Here, OPT(I) denotes an optimal stochastic scheduling policy on the given instance I, assuming a priori knowledge of the set of jobs J, their weights [w.sub.j], release dates [r.sub.j], and processing time distributions [P.sub.j]. The value [rho] is called the performance guarantee of policy [PI].
Note that the SOS policy [PI] in this definition does not have a priori knowledge of the set of jobs J, their weights [w.sub.j], release dates [r.sub.j], and processing time distributions [P.sub.j]. Policy [PI] is an online policy and only learns about the existence of any job j upon its release date [r.sub.j]. 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 [P.sub.j] of the jobs, the adversary is just as powerful as policy [PI] itself because it does not foresee their...
|
