Asymptotic optimality of SEPT in Bayesian Scheduling
AbstractWe consider a stochastic scheduling problem in which there is uncertainty about parame-ters of the probability distribution of the processing times. We restrict ourselves to the setting in which there are two different classes of jobs. The processing times of the jobs are assumed to be exponentially distributed with parameters v and µ, depending on the class of the job. We consider a Bayesian framework in which µ is assumed to be known, whereas the value of v is unknown. However, the scheduler has certain beliefs about this parameter and by processing jobs from this class, the scheduler can update his beliefs about v.For the traditional stochastic scheduling variant, in which the parameters are known, ofthe problem under consideration, the policy that always processes a job with shortest expected processing time (SEPT) is an optimal policy. However, it has been shown that in the Bayesian framework, it is not an optimal policy. Therefore, we analyze the quality of SEPT. We show that SEPT is at most a factor 5/4 worse than an optimal policy and that it is asymptotically optimal.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoPaper provided by Maastricht : METEOR, Maastricht Research School of Economics of Technology and Organization in its series Research Memoranda with number 051.
Date of creation: 2010
Date of revision:
Contact details of provider:
Web page: http://www.maastrichtuniversity.nl/web/UMPublications.htm
operations research and management science;
This paper has been announced in the following NEP Reports:
- NEP-ALL-2010-12-04 (All new papers)
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Megow, Nicole & Vredeveld, Tjark, 2006.
"Approximation Results for Preemptive Stochastic Online Scheduling,"
053, Maastricht : METEOR, Maastricht Research School of Economics of Technology and Organization.
- Megow, Nicole & Vredeveld, Tjark, 2006. "Approximation results for preemptive stochastic online scheduling," Open Access publications from Maastricht University urn:nbn:nl:ui:27-17092, Maastricht University.
- Megow, Nicole & Uetz, Marc & Vredeveld, Tjark, 2006.
"Models and algorithms for stochastic online scheduling,"
Open Access publications from Maastricht University
urn:nbn:nl:ui:27-12045, Maastricht University.
- Megow, Nicole & Uetz , Marc & Vredeveld, Tjark, 2004. "Models and algorithms for stochastic online scheduling," Open Access publications from Maastricht University urn:nbn:nl:ui:27-5884, Maastricht University.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Charles Bollen).
If references are entirely missing, you can add them using this form.