Greed Works—Online Algorithms for Unrelated Machine Stochastic Scheduling

References

• [1] Anand S, Garg N, Kumar A (2012) Resource augmentation for weighted flow-time explained by dual fitting. Rabani Y, ed. Proc. 23rd Annual ACM-SIAM Sympos. Discrete Algorithms (Association for Computing Machinery, New York), 1228–1241.Google Scholar
• [2] Avrahami N, Azar Y (2007) Minimizing total flow time and total completion time with immediate dispatching. Algorithmica 47(3):253–268.Google Scholar
• [3] Balseiro S, Brown D, Chen C (2018) Static routing in stochastic scheduling: Performance guarantees and asymptotic optimality. Oper. Res. 66(6):1641–1660.Link, Google Scholar
• [4] Bansal N, Srinivasan A, Svensson O (2016) Lift-and-round to improve weighted completion time on unrelated machines. Wichs D, Mansour Y, eds. Proc. 48th Ann. ACM Sympos. Theory Computing (STOC) (Association for Computing Machinery, New York), 156–167.Google Scholar
• [5] Becchetti L, Leonardi S (2001) Non-clairvoyant scheduling to minimize the average flow time on single and parallel machines. Vitter J, Spirakis P, Yannakiakis M, eds. Proc. 33rd Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 94–103.Google Scholar
• [6] Bruno J, Downey PJ, Frederickson G (1981) Sequencing tasks with exponential service times to minimize the expected flowtime or makespan. J. ACM 28(1):100–113.Crossref, Google Scholar
• [7] Chakrabarti S, Phillips CA, Schulz AS, Shmoys DB, Stein C, Wein J (1996) Improved scheduling algorithms for minsum criteria. Meyer auf der Heide F, Monien B, eds. Automata, Languages and Programming—ICALP 1996, Lecture Notes in Computer Science, vol. 1099 (Springer, Berlin), 646–657.Google Scholar
• [8] Cole R, Correa JR, Gkatzelis V, Mirrokni VS, Olver N (2011) Inner product spaces for minsum coordination mechanisms. Fortnow L, Vadhan SP, eds. Proc. 43rd ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 539–548.Google Scholar
• [9] Correa J, Queyranne M (2012) Efficiency of equilibria in restricted uniform machine scheduling with total weighted completion time as social cost. Naval Res. Logist. 59(5):384–395.Crossref, Google Scholar
• [10] Correa J, Wagner M (2008) LP-based online scheduling: From single to parallel machines. Math. Programming 119(1):109–136.Crossref, Google Scholar
• [11] Graham RL, Lawler EL, Lenstra JK, Rinnooy Kan AHG (1979) Optimization and approximation in deterministic sequencing and scheduling: A survey. Ann. Discrete Math. 5:287–326.Crossref, Google Scholar
• [12] Gupta V, Moseley B, Xie Q, Uetz M (2017) Stochastic online scheduling on unrelated machines. Eisenbrand F, Koennemann J, eds. Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science, vol. 10328 (Springer, Berlin), 228–240.Crossref, Google Scholar
• [13] Gupta A, Im S, Krishnaswamy R, Moseley B, Pruhs K (2012) Scheduling heterogeneous processors isn’t as easy as you think. Proc. 23rd Annual ACM-SIAM Sympos. Discrete Algorithms (Association for Computing Machinery, New York), 1242–1253.Google Scholar
• [14] Hall LA, Schulz AS, Shmoys DB, Wein J (1997) Scheduling to minimize average completion time: Off-line and on-line approximation algorithms. Math. Oper. Res. 22(3):513–544.Link, Google Scholar
• [15] Horn W (1973) Minimizing average flowtime with parallel machines. Oper. Res. 21(3):846–847.Link, Google Scholar
• [16] Horowitz E, Sahni S (1976) Exact and approximate algorithms for scheduling nonidentical processors. J. ACM 23(2):317–327.Crossref, Google Scholar
• [17] Im S, Li S (2016) Better unrelated machine scheduling for weighted completion time via random offsets from non-uniform distributions. Dinur I, ed. Proc. IEEE 57th Annual Sympos. Foundations Comput. Sci. (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 138–147.Google Scholar
• [18] Im S, Moseley B, Pruhs K (2011) A tutorial on amortized local competitiveness in online scheduling. SIGACT News. 42(2):83–97.Crossref, Google Scholar
• [19] Im S, Moseley B, Pruhs K (2015) Stochastic scheduling of heavy-tailed jobs. Mayr EW, Ollinger N, eds. Proc. 32nd Sympos. Theoret. Aspects Comput. Sci., vol. 30 (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany), 474–486.Google Scholar
• [20] Im S, Kulkarni J, Munagala K, Pruhs K (2014) Selfishmigrate: A scalable algorithm for non-clairvoyantly scheduling heterogeneous processors. Proc. 55th IEEE Annual Sympos. Foundations Comput. Sci. (Institute of Electrical and Electronics Engineers, Piscataway, NJ) 531–540.Google Scholar
• [21] Jäger S, Skutella M (2018) Generalizing the Kawaguchi-Kyan bound to stochastic parallel machine scheduling. Niedermeier R, Vallée B, eds. 35th Sympos. Theoret. Aspects Comput. Sci., Leibniz International Proceedings in Informatics, vol. 96 (Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany), 43:1–43:14.Google Scholar
• [22] Kalyanasundaram B, Pruhs K (2000) Speed is as powerful as clairvoyance. J. ACM 47(4):617–643.Crossref, Google Scholar
• [23] Kämpke T (1987) On the optimality of static priority policies in stochastic scheduling on parallel machines. J. Appl. Probab. 24(2):430–448.Crossref, Google Scholar
• [24] Lenstra J, Shmoys DB, Tardos É (1990) Approximation algorithms for scheduling unrelated parallel machines. Math. Programming 46:259–271.Crossref, Google Scholar
• [25] Leung JYT, ed. (2004) Handbook of Scheduling: Algorithms, Models, and Performance Analysis (Chapman & Hall/CRC, Boca Raton, FL).Crossref, Google Scholar
• [26] Li S (2017) Scheduling to minimize total weighted completion time via time-indexed linear programming relaxations. Umans C, ed. Proc. 58th IEEE Annual Sympos. Foundations Comput. Sci. (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 283–294.Google Scholar
• [27] Megow N, Schulz A (2004) On-line scheduling to minimize average completion time revisited. Oper. Res. Lett. 32(5):485–490.Crossref, Google Scholar
• [28] Megow N, Vredeveld T (2011) A tight 2-approximation for preemptive stochastic scheduling. Math. Oper. Res. 39(4):1297–1310.Link, Google Scholar
• [29] Megow N, Uetz M, Vredeveld T (2006) Models and algorithms for stochastic online scheduling. Math. Oper. Res. 31(3):513–525.Link, Google Scholar
• [30] Möhring RH, Radermacher FJ, Weiss G (1984) Stochastic scheduling problems I: General strategies. Zeitschrift für Oper. Res. 28:193–260.Google Scholar
• [31] Möhring RH, Radermacher FJ, Weiss G (1985) Stochastic scheduling problems II: Set strategies. Zeitschrift für Oper. Res. 29:65–104.Google Scholar
• [32] Möhring RH, Schulz AS, Uetz M (1999) Approximation in stochastic scheduling: The power of LP-based priority policies. J. ACM 46(6):924–942.Crossref, Google Scholar
• [33] Motwani R, Phillips S, Torng E (1994) Non-clairvoyant scheduling. Theoret. Comput. Sci. 130(1):17–47.Crossref, Google Scholar
• [34] Pruhs K, Sgall J, Torng E (2004) Online scheduling. Leung J Y-T, ed. Handbook of Scheduling: Algorithms, Models, and Performance Analysis (CRC Press Inc., Boca Raton, FL), 115–124.Google Scholar
• [35] Rothkopf MH (1966) Scheduling with random service times. Management Sci. 12(9):703–713.Link, Google Scholar
• [36] Schulz AS (2008) Stochastic online scheduling revisited. Yang B, Du DZ, Wang C, eds. Combinatorial Optimization and Applications, Lecture Notes in Computer Science, vol. 5165 (Springer, Berlin), 448–457.Crossref, Google Scholar
• [37] Schulz AS, Skutella M (2002) Scheduling unrelated machines by randomized rounding. SIAM J. Discrete Math. 15(4):450–469.Crossref, Google Scholar
• [38] Skutella M (2001) Convex quadratic and semidefinite programming relaxations in scheduling. J. ACM 48(2):206–242.Crossref, Google Scholar
• [39] Skutella M, Uetz M (2005) Stochastic machine scheduling with precedence constraints. SIAM J. Comput. 34(4):788–802.Crossref, Google Scholar
• [40] Skutella M, Sviridenko M, Uetz M (2016) Unrelated machine scheduling with stochastic processing times. Math. Oper. Res. 41(3):851–864.Link, Google Scholar
• [41] Uetz M (2003) When greediness fails: Examples from stochastic scheduling. Oper. Res. Lett. 31(6):413–419.Crossref, Google Scholar
• [42] Vestjens A (1997) Online machine scheduling. PhD thesis, TU Eindhoven, Eindhoven, Netherlands.Google Scholar
• [43] Wall Street (1987) Stone O, dir. Twentieth Century Fox, Los Angeles.Google Scholar
• [44] Weber R, Varaiya P, Walrand J (1986) Scheduling jobs with stochastically ordered processing times on parallel machines to minimize expected owtime. J. Appl. Probab. 23(3):841–847.Crossref, Google Scholar
• [45] Weiss G, Pinedo M (1980) Scheduling tasks with exponential service times on non-identical processors to minimize various cost functions. J. Appl. Probab. 17(1):187–202.Crossref, Google Scholar