Approximating Preemptive Stochastic Scheduling

Research, Preprint OPEN
Megow, N.; Vredeveld, T.;
  • Publisher: METEOR, Maastricht University School of Business and Economics
  • Subject: 2 International | 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.... View more
  • 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
Share - Bookmark