On the Asymptotic Optimality of a Simple On-Line Algorithm for the Stochastic Single-Machine Weighted Completion Time Problem and Its Extensions
Authors:
- 1 June 2006
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 54 (3) , 464-474
Abstract
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.Keywords
This publication has 15 references indexed in Scilit:
- Asymptotically optimal schedules for single-server flow shop problems with setup costs and timesOperations Research Letters, 2005
- From Fluid Relaxations to Practical Algorithms for High-Multiplicity Job-Shop Scheduling: The Holding Cost ObjectiveOperations Research, 2003
- Single Machine Scheduling with Release DatesSIAM Journal on Discrete Mathematics, 2002
- Asymptotic analysis of an on-line algorithm for the single machine completion time problem with release datesOperations Research Letters, 2001
- On the Asymptotic Optimality of the SPT Rule for the Flow Shop Average Completion Time ProblemOperations Research, 2000
- Approximation in stochastic schedulingJournal of the ACM, 1999
- Probabilistic Analysis and Practical Algorithms for the Flow Shop Weighted Completion Time ProblemOperations Research, 1998
- Chernoff–Hoeffding Bounds for Applications with Limited IndependenceSIAM Journal on Discrete Mathematics, 1995
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey1979
- Complexity of Machine Scheduling Problems1977