Publication: IIE Transactions
Publication Date: 01-MAY-07
Delivery: Immediate Online Access
Author: Chen, Gang ; Shen, Zuo-Jun Max
Article Excerpt
1. Introduction
In the stochastic online scheduling environment, a set of jobs N = {1, 2,..., n} arrive over time and must be processed nonpreemptively on one or more of m machines. The release time and weight of every job j [member of] N remain unknown until job j arrives. In addition, the processing requirement of every job j [member of] N is a random variable whose actual value remains unknown until job j is finished. The processing time of job j is equal to its processing requirement divided by the speed of the machine on which it is processed. In this paper we study nondelay algorithms, i.e., algorithms that keep the machine(s) busy as long as there is work available for processing (see, e.g., Pinedo (1995)), for three different stochastic online scheduling problems. They are the stochastic online single machine problem, uniform parallel machine problem and flow shop problem. In the single machine problem, all the jobs must be processed, one at a time, on a single machine with a unit speed. In the uniform parallel machine problem, there are m machines each with a constant speed [s.sub.i] > (i [member of] {1, 2,..., m}) and each job j (j [member of] {1, 2,..., n}) has to be processed on one of the m machines. In the flow shop problem, each of the m machines has a unit speed and each job j [member of] N must visit the machines 1, 2,..., m in that same order.
With the objective of minimizing the total weighted completion time, the stochastic online single machine problem, uniform parallel machine problem and flow shop problem can be denoted, in standard scheduling notation (see, e.g., Graham et al. (1979)), by 1|[x.sub.j] ~ stoch, [r.sub.j]| [summation] [w.sub.j][C.sub.j], Qm|[x.sub.j] ~ stoch, [r.sub.j]|[summation] [w.sub.j][C.sub.j] and Fm|[x.sub.ji] ~ stoch, [r.sub.j]| [summation] [w.sub.j][C.sub.j], respectively, where [x.sub.j] is the processing requirement of job j. Note that in the flow shop problem [x.sub.j] = [[summation].sub.i=1.sup.m] [x.sub.ji], where [x.sub.ji] is the processing requirement of job j on machine i. The deterministic variants of these problems, in which the exact processing requirement of every job j is known upon job j's arrival at time [r.sub.j], are denoted respectively by 1|[r.sub.j]| [summation] [w.sub.j][C.sub.j], Qm|[r.sub.j]|[summation] [w.sub.j][C.sub.j] and Fm|[r.sub.j]|[summation][w.sub.j][C.sub.j].
In this paper we say that a job is waiting at time t if it is released but not being processed at time t. We say that a job is in the system at time t if it has been released but not finished by time t. We say that a certain amount of processing requirement is waiting at time t if it has been released but not finished by time t. Furthermore, throughout this paper we assume that the weights and processing requirements of all jobs are bounded, that is, there exist constants [bar.w] [greater than or equal to] [w.bar] > and [bar.x] [greater than or equal to] [x.bar] > such that [w.bar] [less than or equal to] [w.sub.j] [less than or equal to] [bar.w] and [x.bar] [less than or equal to] [x.sub.j] [less than or equal to] [bar.x] for every job j [member of] N. We also assume that the machine(s) in each problem has (have) adequate capacity. That is, in the long run the mean rate at which jobs arrive is strictly less than the mean rate at which the machine(s) is (are) capable of processing. We justify this assumption by observing that, with this assumption being unsatisfied, the number of jobs that are waiting for processing will keep increasing and will eventually approach infinity in any feasible schedule. This means that, after a certain period of time, there will always be an extremely large number of jobs waiting for processing and the vast majority of job information is known whenever a decision is to be made. Such kind of problems bear more characteristics of an stochastic offline problem than an online problem and should be regarded more appropriately as an offline problem and thus will not be considered in this paper.
For the deterministic online scheduling problems 1|[r.sub.j]| [summation] [w.sub.j][C.sub.j] and Qm|[r.sub.j]| [summation][w.sub.j][C.sub.j] with bounded processing requirements and bounded weights, Chou, Queyranne and Simchi-Levi (2005) show that the nondelay algorithm Weighted Shortest Processing Requirement among Available jobs (WSPRA) is asymptotically optimal. In the WSPRA rule, whenever a machine is available, the job with the largest ratio [w.sub.j]/[x.sub.j] among all the waiting jobs is selected to be processed next. If there is no job waiting, then the machine remains idle until the next job arrives. For the deterministic online flow shop problem Fm|[r.sub.j]| [summation][w.sub.j][C.sub.j], Liu et al. (2005) show that three nondelay algorithms extended from WSPRA are asymptotically optimal, with the assumptions that job weights are bounded and independent and identically distributed (i.i.d.), processing requirements are bounded and i.i.d. across all the machines and jobs, and job release times increase in the order of O(n). As an extension, in this paper we show that any nondelay algorithm is asymptotically optimal for the single machine problem 1|[x.sub.j] ~ stoch, [r.sub.j]| [summation] [w.sub.j][C.sub.j], the flow shop problem Fm|[x.sub.j] ~ stoch, [r.sub.j]| [summation] [w.sub.j][C.sub.j], and the uniform parallel machine problem Qm|[x.sub.j] ~ stoch, [r.sub.j]| [summation] [w.sub.j][C.sub.j] as long as job weights are bounded, processing requirements are bounded and i.i.d. across all the jobs and all the machines (for the flow shop problem only), job interarrival times are i.i.d., and machine capacity is adequate.
The contribution of this paper is three-fold. First, it generalizes or complements some of the existing asymptotic results on online scheduling problems. In some of these papers, e.g., Gazmuri (1985) and Liu et al. (2005), assumptions similar to or even stronger than the assumptions made in this paper were made in order to prove results that are either special cases of or similar to the results shown in this paper. In other papers, e.g., Chou, Queyranne and Simchi-Levi (2005), assumptions weaker than the assumptions in this paper were made to prove weaker results. This paper provides some insights on why these results hold. Second, it shows that, if the weighted completion time is used as the objective, then any nondelay algorithm, like the simple First-Come First-Serve (FCFS) rule, provides good performance as long as the number of jobs is reasonably large (> 100) and the jobs possess certain characteristics. Finally, it points out that, in the online scheduling, the popular weighted completion time objective fails to differentiate the performances of different nondelay algorithms and therefore more sensitive objectives need to be identified and analyzed. Two potential alternative objectives are the total weighted flow time and total weighted stretch. The flow time of a job is defined to be the difference of its release time and its completion time. The stretch of a job is the ratio of its flow time to its processing time.
The rest of this paper is organized as follows. In Section 2 we briefly review related results in the literature. In Section 3 and Section 4 we prove the asymptotic optimality results for the single machine problem and flow shop problem respectively. In Section 5 we show that a special nondelay algorithm, the FCFS rule, is asymptotically optimal for the uniform parallel machine problem. In Section 6 we show that any nondelay algorithm is asymptotically optimal for the uniform parallel machine problem. In Section 7 we present our simulation studies which show that two generic nondelay algorithms converge very fast. Finally, we discuss our results and suggest future research directions in Section 8.
2. Literature review
Online scheduling problems are defined in contrast to offline scheduling problems. In an offline scheduling problem, all the job information, especially the job release times, are known a priori, so that a global (sometimes optimal) decision can be made at time by considering all the jobs, including those that have not been released. In an online scheduling problem, the job information is usually presented piece by piece and decisions have to be made based only on the information that is available at any given moment. Typically, the existence of a job is not known until it is released to the system.
An offline scheduling algorithm considers all the jobs, including those that have not been released. An online algorithm considers only jobs that have been released at the time of decision. Clearly, while offline algorithms can only be applied to offline scheduling problems, online algorithms can be applied to both online and offline scheduling problems. Of course, for offline problems, although online algorithms are applicable, offline algorithms should provide better solutions. In this paper, we restrict our discussion to online algorithms applied to online problems. Hence, we will review related work by putting them in the context of solving online scheduling problems.
Asymptotic performance analysis is widely used to evaluate the performance of an algorithm on large-sized instances. We also note that most, if not all, results on online scheduling problems in the literature concern nondelay algorithms. Gazmuri (1985) studies the single machine problem 1|[r.sub.j]| [summation][C.sub.j] under the assumptions that all job processing requirements are bounded i.i.d. integers, all interarrival times are i.i.d. integers, and processing requirements and interarrival times are independent of each other. He considers two different cases where in the first case the expected job processing requirement is strictly less than the expected interarrival time and in the second case the expected job processing requirement is strictly greater than the expected interarrival time. An asymptotically optimal offline algorithm is given for the first case, while an asymptotically optimal online algorithm is given for the second case. More recently, Kaminsky and Simchi-Levi (2001a) study the same single machine problem 1|[r.sub.j]| [summation] [C.sub.j] and show that the Shortest Processing Time among Available jobs (SPTA) rule is asymptotically optimal for this problem as long as all job processing requirements are bounded. Building on the results of Goemans (1997) and Goemans et al. (1999), Chou, Queyranne and Simchi-Levi (2005) show that a generalized version of SPTA rule, the WSPRA, is asymptotically optimal for the weighted version of the uniform parallel machine problem Qm|[r.sub.j]| [summation][w.sub.j][C.sub.j] with bounded weights and processing requirements. These authors also derive an upper bound on the maximum delay that any amount of work can incur in the WSPRA schedule, relative to the linear programming relaxation presented by Goemans (1997). They then derive from this bound the asymptotic optimality of the WSPRA algorithm for the uniform parallel machine problem. Chou (2001) and Chou, Liu, Queyranne and Simchi-Levi (2005) also extend this result to the stochastic version of the single machine, flow shop, and open shop problems, where the objective is to minimize the expected total weighted completion time, E[[summation][w.sub.j][C.sub.j]]. They prove that the nondelay algorithm Weighted Shortest Expected Processing Time is asymptotically optimal for 1|[x.sub.j] ~ stoch, [r.sub.j]|E[[summation][w.sub.j][C.sub.j]] as long as the job weights and processing requirements are bounded and the processing requirements are independently distributed with known mean values.
For shop problems, Kaminsky and Simchi-Levi (2001b) study the flow shop problem Fm|| [summation] [C.sub.j] and show that the...
NOTE: All illustrations and photos have been removed from this article.
More articles from
IIE Transactions
Locating capacitated facilities to maximize captured demand, 01-NOV-07
Erratum, 01-NOV-07
Sequencing with limited flexibility, 01-OCT-07
Looking for additional articles?
Click here to search our database of over 3 million articles.
Looking for more in-depth information on this industry?
Click here to search our complete database of Industry & Market reports by text, subject, publication name or publication date.
About Goliath
Whether you're looking for sales prospects, competitive information, company analysis or best practices in managing your organization, Goliath can help you meet your business needs.
Our extensive business information databases empower business professionals with both the breadth and depth of credible, authoritative information they need to support their business goals. Whether it be strategic planning, sales prospecting, company research or defining management best practices - Goliath is your leading source for accurate information. |
