This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Chou, M. C. Articles by Simchi-Levi, D. Search for Related Content

On the Asymptotic Optimality of a Simple On-Line Algorithm for the Stochastic Single-Machine Weighted Completion Time Problem and Its Extensions

Department of Decision Sciences, National University of Singapore, 117591 Singapore
Verizon Laboratories, Boston, Massachusetts
Sauder School of Business, University of British Columbia, Vancouver, British Columbia, Canada
Engineering Systems Division and the Department of Civil and Environmental Engineering, Massachusetts Institute of Technology, Cambridge, Massachusetts
mabelchou{at}nus.edu.sg
hui.liu{at}verizon.com
maurice.queyranne{at}sauder.ubc.ca
dslevi{at}mit.edu

We consider the stochastic single-machine problem, when the objective is to minimize the expected total weighted completion time of a set of jobs that are released over time. We assume that the existence and the parameters of each job including its release date, weight, and expected processing times are not known until its release date. The actual processing times are not known until processing is completed. We analyze the performance of the on-line nonpreemptive weighted shortest expected processing time among available jobs (WSEPTA) heuristic. When a scheduling decision needs to be made, this heuristic assigns, among the jobs that have arrived but not yet processed, one with the largest ratio of its weight to its expected processing time. We prove that when the job weights and processing times are bounded and job processing times are mutually independent random variables, WSEPTA is asymptotically optimal for the single-machine problem. This implies that WSEPTA generates a solution whose relative error approaches zero as the number of jobs increases. This result can be extended to the stochastic flow shop and open shop problems, as well as models with stochastic job weights.

Subject classifications: production/scheduling; on-line single-machine and flow shop stochastic sequencing.
History: Received August 2004; revision received April 2005; accepted April 2005.

This article has been cited by other articles:

				P. Jaillet and M. R. Wagner Generalized Online Routing: New Competitive Ratios, Resource Augmentation, and Asymptotic Analyses Operations Research, May 1, 2008; 56(3): 745 - 757. [Abstract] [PDF]

				N. Megow, M. Uetz, and T. Vredeveld Models and Algorithms for Stochastic Online Scheduling Mathematics of Operations Research, August 1, 2006; 31(3): 513 - 525. [Abstract] [PDF]