2014/05/30 by Nicole Megow, Tjark Vredeveld · 2 citations
Business, Management and Accounting · Computer Science · Engineering · #Advanced Queuing Theory Analysis #Optimization and Search Problems #Scheduling and Optimization Algorithms
paper · doi:10.1287/moor.2014.0653
openalex publication_date 2014/05/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider dynamic stochastic scheduling of preemptive jobs with processing times that follow independent discrete probability distributions. We derive a policy with a guaranteed performance ratio of 2 for the problem of minimizing the sum of weighted completion times on identical parallel machines subject to release dates. The analysis is tight. Our policy as well as their analysis applies also to the more general model of stochastic online scheduling. In contrast to previous results for nonpreemptive stochastic scheduling, our preemptive policy yields an approximation guarantee that is independent of the processing time distributions. However, our policy extensively utilizes information on the distributions other than the first (and second) moments. We also 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 policy.