Template-type: ReDif-Paper 1.0
Author-Name: Marbán Sebastián 
Author-Name: Rutten Cyriel 
Author-Name: Vredeveld Tjark 
Author-workplace-name: METEOR
Title: Asymptotic optimality of SEPT in Bayesian Scheduling
Abstract: We 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.
Keywords: operations research and management science; 
Series: Research Memoranda
Creation-Date: 2010
Number: 051
File-URL: http://digitalarchive.maastrichtuniversity.nl/fedora/objects/guid:331298ae-5352-4259-9fbd-dc6768b13fb0/datastreams/ASSET1/content
File-Format: application/pdf
File-Size: 328730
Handle: RePEc:unm:umamet:2010051