Template-type: ReDif-Paper 1.0
Author-Name: Megow Nicole 
Author-Name: Vredeveld Tjark 
Author-workplace-name: METEOR
Title: Approximating Preemptive Stochastic Scheduling
Abstract: We present constant approximative policies for preemptive stochastic scheduling. We derive policies with a guaranteed performance ratio of 2 for scheduling jobs with release dates on identical parallel machines subject to minimizing the sum of weighted completion times. Our policies as well as their analysis apply also to the recently introduced more general model of stochastic online scheduling. The performance guarantee we give matches the best result known for the corresponding deterministic online problem. In contrast to previous results for non-preemptive stochastic scheduling, our preemptive policies yield an approximation guarantee that is independent of the processing time distributions. However, our policies extensively utilize information on the distributions other than the first (and second) moments. To obtain our results, we introduce a new nontrivial lower bound on the expected value of an unknown optimal policy. It relies on a relaxation to the basic problem on a single machine without release dates, which is known to be solved optimally by the Gittins index priority rule. This dynamic priority index is crucial to the analysis and also inspires the design of our policies.
Keywords: operations research and management science; 
Series: Research Memoranda
Creation-Date: 2009
Number: 054
File-URL: http://digitalarchive.maastrichtuniversity.nl/fedora/objects/guid:7427f9b7-1177-43cd-9616-1edfe5551f7c/datastreams/ASSET1/content
File-Format: application/pdf
File-Size: 415247
Handle: RePEc:unm:umamet:2009054