Please use this identifier to cite or link to this item: https://doi.org/10.1287/opre.1060.0270
DC FieldValue
dc.titleOn the asymptotic optimality of a simple on-line algorithm for the stochastic single-machine weighted completion time problem and its extensions
dc.contributor.authorChou, M.C.
dc.contributor.authorLiu, H.
dc.contributor.authorQueyranne, M.
dc.contributor.authorSimchi-Levi, D.
dc.date.accessioned2013-10-09T03:25:16Z
dc.date.available2013-10-09T03:25:16Z
dc.date.issued2006
dc.identifier.citationChou, M.C., Liu, H., Queyranne, M., Simchi-Levi, D. (2006). On the asymptotic optimality of a simple on-line algorithm for the stochastic single-machine weighted completion time problem and its extensions. Operations Research 54 (3) : 464-474. ScholarBank@NUS Repository. https://doi.org/10.1287/opre.1060.0270
dc.identifier.issn0030364X
dc.identifier.urihttp://scholarbank.nus.edu.sg/handle/10635/44038
dc.description.abstractWe 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. © 2006 INFORMS.
dc.description.urihttp://libproxy1.nus.edu.sg/login?url=http://dx.doi.org/10.1287/opre.1060.0270
dc.sourceScopus
dc.subjectProduction/scheduling: on-line single-machine and flow shop stochastic sequencing
dc.typeArticle
dc.contributor.departmentDECISION SCIENCES
dc.description.doi10.1287/opre.1060.0270
dc.description.sourcetitleOperations Research
dc.description.volume54
dc.description.issue3
dc.description.page464-474
dc.description.codenOPREA
dc.identifier.isiut000238435100005
Appears in Collections:Staff Publications

Show simple item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

25
checked on Oct 15, 2019

WEB OF SCIENCETM
Citations

16
checked on Oct 15, 2019

Page view(s)

108
checked on Oct 14, 2019

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.