Approximating Preemptive Stochastic Scheduling

Research, Preprint OPEN
Megow Nicole ; Vredeveld Tjark (2009)
  • Publisher: METEOR, Maastricht University School of Business and Economics
  • Subject: operations research and management science;
    arxiv: Computer Science::Operating Systems

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.
  • References (36)
    36 references, page 1 of 4

    [1] F. N. Afrati, E. Bampis, C. Chekuri, D. R. Karger, C. Kenyon, S. Khanna, I. Milis, M. Queyranne, M. Skutella, C. Stein, and M. Sviridenko. Approximation schemes for minimizing average weighted completion time with release dates. In Proceedings of the 40th IEEE Symposium on the Foundations of Computer Science, pages 32-43, New York, NY, USA, 1999.

    [2] J. L. Bruno, P. J. Downey, and G. N. Frederickson. Sequencing tasks with exponential service times to minimize the expected flowtime or makespan. Journal of the ACM, 28:100-113, 1981.

    [3] D. Chazan, A. G. Konheim, and B. Weiss. A note on time sharing. Journal of Combinatorial Theory, 5:344-369, 1968.

    [4] C. Chekuri, R. Motwani, B. Natarajan, and C. Stein. Approximation techniques for average completion time scheduling. SIAM Journal on Computing, 31:146-166, 2001.

    [5] C.-F. M. Chou, H. Liu, M. Queyranne, and D. Simchi-Levi. 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, 2006.

    [6] E. G. Coffman Jr., M. Hofri, and G. Weiss. Scheduling stochastic jobs with a two point distribution on two parallel machines. Probability in the Engineering and Informational Sciences, 3:89-116, 1989.

    [7] J. Correa and M. Wagner. LP-based online scheduling: From single to parallel machines. Mathematical Programming, 119:109-136, 2009.

    [8] B. C. Dean. Approximation Algorithms for Stochastic Scheduling Problems. PhD thesis, Massachusetts Institute of Technology, 2005.

    [9] J. C. Gittins. Bandit processes and dynamic allocation indices. Journal of the Royal Statistical Society, Series B, 41:148-177, 1979.

    [10] J. C. Gittins. Multi-armed Bandit Allocation Indices. Wiley, New York, 1989.

  • Metrics
    No metrics available
Share - Bookmark