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
 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.
 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.
 D. Chazan, A. G. Konheim, and B. Weiss. A note on time sharing. Journal of Combinatorial Theory, 5:344-369, 1968.
 C. Chekuri, R. Motwani, B. Natarajan, and C. Stein. Approximation techniques for average completion time scheduling. SIAM Journal on Computing, 31:146-166, 2001.
 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.
 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.
 J. Correa and M. Wagner. LP-based online scheduling: From single to parallel machines. Mathematical Programming, 119:109-136, 2009.
 B. C. Dean. Approximation Algorithms for Stochastic Scheduling Problems. PhD thesis, Massachusetts Institute of Technology, 2005.
 J. C. Gittins. Bandit processes and dynamic allocation indices. Journal of the Royal Statistical Society, Series B, 41:148-177, 1979.
 J. C. Gittins. Multi-armed Bandit Allocation Indices. Wiley, New York, 1989.