Achievable Performance of Blind Policies in Heavy Traffic

References

• Aalto S, Ayesta U (2006) Mean delay analysis of multi level processor sharing disciplines. Proc. 25th IEEE Internat. Conf. Comput. Comm., INFOCOM (IEEE, Piscataway, NJ), , 1–11.Google Scholar
• Asmussen S (2003) Applied Probability and Queues (Springer, New York).Google Scholar
• Bansal N (2005) On the average sojourn time under M/M/1/SRPT. Oper. Res. Lett. 33(2):195–200.Crossref, Google Scholar
• Bansal N, Gamarnik D (2006) Handling load with less stress. Queueing Systems 54(1):45–54.Crossref, Google Scholar
• Bansal N, Harchol-Balter M (2001) Analysis of SRPT scheduling: Investigating unfairness. Proc. 2001 ACM SIGMETRICS Internat. Conf. Measurement and Modeling Comput. Systems, SIGMETRICS ’01 (ACM, New York), 279–290.Google Scholar
• Becchetti L, Leonardi S (2004) Nonclairvoyant scheduling to minimize the total flow time on single and parallel machines. J. ACM 51(4):517–539.Crossref, Google Scholar
• Borodin A, El-Yaniv R (1998) Online Computation and Competitive Analysis (Cambridge University Press, Cambridge, UK).Google Scholar
• Boxma O, Zwart B (2007) Tails in scheduling. SIGMETRICS Perform. Eval. Rev. 34(4):13–20.Crossref, Google Scholar
• Conway RW, Maxwell WL, Miller LW (1967) Theory of Scheduling (Addison-Wesley Publishing Company, Reading, MA).Google Scholar
• Corbató FJ, Merwin-Daggett M, Daley RC (1962) An experimental time-sharing system. Proc. May 1–3, 1962, Spring Joint Comput. Conf., AIEE-IRE ’62 (Spring) (ACM, New York), 335–344.Google Scholar
• Fiat A, Woeginger GJ (1998) Online algorithms: The state of the art (Springer, New York), 1442.Crossref, Google Scholar
• Gromoll HC (2004) Diffusion approximation for a processor sharing queue in heavy traffic. Ann. Appl. Probab. 14(2):555–611.Crossref, Google Scholar
• Kalyanasundaram B, Pruhs KR (2003) Minimizing flow time nonclairvoyantly. J. ACM 50(4):551–567.Crossref, Google Scholar
• Kleinrock L (1976) Queueing Systems II: Computer Theory (John Wiley & Sons, New York).Google Scholar
• Lin M, Wierman A, Zwart B (2011) Heavy-traffic analysis of mean response time under shortest remaining processing time. Performance Eval. 68(10):955–966.Crossref, Google Scholar
• Lotov VI (2002) Inequalities for the moments and distribution of the ladder height of a random walk. Siberian Math. J. 43(4):655–660.Crossref, Google Scholar
• Lu D, Sheng H, Dinda P (2004) Size-based scheduling policies with inaccurate scheduling information. DeGroot D, Harrison P, Wijshoff H, Segall Z, eds. Proc. 12th Internat. Workshop Modeling, Anal., and Simulation Comput. Telecomm. Systems, MASCOTS ’04 (IEEE Computer Society, Washington, DC), 31–38.Google Scholar
• Motwani R, Phillips S, Torng E (1994) Nonclairvoyant scheduling. Theoretical Comput. Sci. 130(1):17–47.Crossref, Google Scholar
• Nair J, Wierman A, Zwart B (2010) Tail-robust scheduling via limited processor sharing. Performance Eval. 67(11):978–995.Crossref, Google Scholar
• Nuyens M, Wierman A (2008) The foreground–background queue: A survey. Performance Eval. 65(3):286–307.Crossref, Google Scholar
• Nuyens M, Wierman A, Zwart B (2008) Preventing large sojourn times using SMART scheduling. Oper. Res. 56(1):88–101.Link, Google Scholar
• Pruhs K, Sgall J, Torng E (2004) Online scheduling. Leung J Y-T, ed. Handbook of Scheduling: Algorithms, Models, and Performance Analysis (CRC Press, Boca Raton, FL), 15-1.Google Scholar
• Puha ALet al. (2015) Diffusion limits for shortest remaining processing time queues under nonstandard spatial scaling. Ann. Appl. Probab. 25(6):3381–3404.Crossref, Google Scholar
• Remerova M, Foss S, Zwart B (2014) Random fluid limit of an overloaded polling model. Adv. Appl. Probab. 46(1):76–101.Crossref, Google Scholar
• Righter R, Shanthikumar JG, Yamazaki G (1990) On extremal service disciplines in single-stage queueing systems. J. Appl. Probab. 27(2):409–416.Crossref, Google Scholar
• Schrage L (1968) Letter to the editor—A proof of the optimality of the shortest remaining processing time discipline. Oper. Res. 16(3):687–690.Link, Google Scholar
• Stolyar AL, Ramanan K (2001) Largest weighted delay first scheduling: Large deviations and optimality. Ann. Appl. Probab. 11(1):1–48.Crossref, Google Scholar
• Wierman A, Nuyens M (2008) Scheduling despite inexact job-size information. SIGMETRICS Perform. Eval. Rev. 36(1):25–36.Crossref, Google Scholar
• Wierman A, Zwart AP (2012) Is tail-optimal scheduling possible? Oper. Res. 60(5):1249–1257.Link, Google Scholar
• Wierman A, Harchol-Balter M, Osogami T (2005) Nearly insensitive bounds on SMART scheduling. Eager DL, Williamson CL, Borst SC, Lui JCS, eds. Proc. Internat. Conf. Measurements Modeling Comput. Systems, SIGMETRICS ’05, (ACM, New York), 205–216.Google Scholar