{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T04:56:37Z","timestamp":1755838597894},"publisher-location":"Cham","reference-count":35,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319592497"},{"type":"electronic","value":"9783319592503"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-59250-3_19","type":"book-chapter","created":{"date-parts":[[2017,5,23]],"date-time":"2017-05-23T13:04:39Z","timestamp":1495544679000},"page":"228-240","source":"Crossref","is-referenced-by-count":9,"title":["Stochastic Online Scheduling on Unrelated Machines"],"prefix":"10.1007","author":[{"given":"Varun","family":"Gupta","sequence":"first","affiliation":[]},{"given":"Benjamin","family":"Moseley","sequence":"additional","affiliation":[]},{"given":"Marc","family":"Uetz","sequence":"additional","affiliation":[]},{"given":"Qiaomin","family":"Xie","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,5,24]]},"reference":[{"key":"19_CR1","doi-asserted-by":"crossref","unstructured":"Anand, S., Garg, N., Kumar, A.: Resource augmentation for weighted flow-time explained by dual fitting. In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, pp. 1228\u20131241 (2012)","DOI":"10.1137\/1.9781611973099.97"},{"key":"19_CR2","doi-asserted-by":"crossref","unstructured":"Avrahami, N., Azar, Y.: Minimizing total flow time and total completion time with immediate dispatching. In: Proceedings of the 15th Symposium on Parallelism in Algorithms and Architectures (SPAA 2003), pp. 11\u201318. ACM (2003)","DOI":"10.1145\/777412.777415"},{"key":"19_CR3","unstructured":"Balseiro, S., Brown, D., Chen, C.: Static routing in stochastic scheduling: Performance guarantees and asymptotic optimality. Technical report (2016)"},{"key":"19_CR4","doi-asserted-by":"crossref","unstructured":"Bansal, N., Srinivasan, A., Svensson, O.: Lift-and-round to improve weighted completion time on unrelated machines. In: Proceedings of 48th Annual ACM Symposium Theory Computing (STOC), pp. 156\u2013167. ACM (2016)","DOI":"10.1145\/2897518.2897572"},{"key":"19_CR5","doi-asserted-by":"crossref","unstructured":"Becchetti, L., Leonardi, S.: Non-clairvoyant scheduling to minimize the average flow time on single and parallel machines. In: STOC, pp. 94\u2013103 (2001)","DOI":"10.1145\/380752.380782"},{"key":"19_CR6","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1145\/322234.322242","volume":"28","author":"J Bruno","year":"1981","unstructured":"Bruno, J., Downey, P.J., Frederickson, G.: Sequencing tasks with exponential service times to minimize the expected flowtime or makespan. J. ACM 28, 100\u2013113 (1981)","journal-title":"J. ACM"},{"key":"19_CR7","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/s10107-007-0204-7","volume":"119","author":"J Correa","year":"2008","unstructured":"Correa, J., Wagner, M.: LP-based online scheduling: from single to parallel machines. Math. Program. 119, 109\u2013136 (2008)","journal-title":"Math. Program."},{"key":"19_CR8","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","volume":"5","author":"RL Graham","year":"1979","unstructured":"Graham, R.L., Lawler, E.L., Lenstra, J.K., Kan, A.H.G.R.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discrete Math. 5, 287\u2013326 (1979)","journal-title":"Ann. Discrete Math."},{"key":"19_CR9","doi-asserted-by":"crossref","unstructured":"Gupta, A., Im, S., Krishnaswamy, R., Moseley, B., Pruhs, K.: Scheduling heterogeneous processors isn\u2019t as easy as you think. In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, pp. 1242\u20131253 (2012)","DOI":"10.1137\/1.9781611973099.98"},{"key":"19_CR10","doi-asserted-by":"crossref","unstructured":"Gupta, V., Moseley, B., Uetz, M., Xie, Q.: Stochastic online scheduling on unrelated machines. arXiv preprint arXiv:1703.01634 (2017)","DOI":"10.1007\/978-3-319-59250-3_19"},{"key":"19_CR11","doi-asserted-by":"crossref","first-page":"846","DOI":"10.1287\/opre.21.3.846","volume":"21","author":"W Horn","year":"1973","unstructured":"Horn, W.: Minimizing average flowtime with parallel machines. Oper. Res. 21, 846\u2013847 (1973)","journal-title":"Oper. Res."},{"issue":"2","key":"19_CR12","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1145\/321941.321951","volume":"23","author":"E Horowitz","year":"1976","unstructured":"Horowitz, E., Sahni, S.: Exact and approximate algorithms for scheduling nonidentical processors. J. ACM 23(2), 317\u2013327 (1976)","journal-title":"J. ACM"},{"key":"19_CR13","doi-asserted-by":"crossref","unstructured":"Im, S., Kulkarni, J., Munagala, K., Pruhs, K.: Selfishmigrate: a scalable algorithm for non-clairvoyantly scheduling heterogeneous processors. In: 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pp. 531\u2013540 (2014)","DOI":"10.1109\/FOCS.2014.63"},{"issue":"2","key":"19_CR14","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1145\/1998037.1998058","volume":"42","author":"S Im","year":"2011","unstructured":"Im, S., Moseley, B., Pruhs, K.: A tutorial on amortized local competitiveness in online scheduling. SIGACT News 42(2), 83\u201397 (2011)","journal-title":"SIGACT News"},{"key":"19_CR15","unstructured":"Im, S., Moseley, B., Pruhs, K.: Stochastic scheduling of heavy-tailed jobs. In: STACS (2015)"},{"issue":"4","key":"19_CR16","doi-asserted-by":"crossref","first-page":"617","DOI":"10.1145\/347476.347479","volume":"47","author":"B Kalyanasundaram","year":"2000","unstructured":"Kalyanasundaram, B., Pruhs, K.: Speed is as powerful as clairvoyance. J. ACM 47(4), 617\u2013643 (2000)","journal-title":"J. ACM"},{"key":"19_CR17","doi-asserted-by":"crossref","first-page":"430","DOI":"10.1017\/S0021900200031077","volume":"24","author":"T K\u00e4mpke","year":"1987","unstructured":"K\u00e4mpke, T.: On the optimality of static priority policies in stochastic scheduling on parallel machines. J. Appl. Probab. 24, 430\u2013448 (1987)","journal-title":"J. Appl. Probab."},{"key":"19_CR18","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1007\/BF01585745","volume":"46","author":"J Lenstra","year":"1990","unstructured":"Lenstra, J., Shmoys, D.B., Tardos, \u00c9.: Approximation algorithms for scheduling unrelated parallel machines. Math. Program. 46, 259\u2013271 (1990)","journal-title":"Math. Program."},{"volume-title":"Handbook of Scheduling: Algorithms, Models, and Performance Analysis","year":"2004","key":"19_CR19","unstructured":"Leung, J.Y.-T. (ed.): Handbook of Scheduling: Algorithms, Models, and Performance Analysis. Chapman & Hall\/CRC, Boca Raton (2004)"},{"key":"19_CR20","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1016\/j.orl.2003.11.008","volume":"32","author":"N Megow","year":"2004","unstructured":"Megow, N., Schulz, A.: On-line scheduling to minimize average completion time revisited. Oper. Res. Lett. 32, 485\u2013490 (2004)","journal-title":"Oper. Res. Lett."},{"issue":"3","key":"19_CR21","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1287\/moor.1060.0201","volume":"31","author":"N Megow","year":"2006","unstructured":"Megow, N., Uetz, M., Vredeveld, T.: Models and algorithms for stochastic online scheduling. Math. Oper. Res. 31(3), 513\u2013525 (2006)","journal-title":"Math. Oper. Res."},{"key":"19_CR22","doi-asserted-by":"crossref","first-page":"1297","DOI":"10.1287\/moor.2014.0653","volume":"39","author":"N Megow","year":"2011","unstructured":"Megow, N., Vredeveld, T.: A tight 2-approximation for preemptive stochastic scheduling. Math. Oper. Res. 39, 1297\u20131310 (2011)","journal-title":"Math. Oper. Res."},{"key":"19_CR23","first-page":"193","volume":"28","author":"RH M\u00f6hring","year":"1984","unstructured":"M\u00f6hring, R.H., Radermacher, F.J., Weiss, G.: Stochastic scheduling problems I: general strategies. ZOR - Z. Oper. Res. 28, 193\u2013260 (1984)","journal-title":"ZOR - Z. Oper. Res."},{"key":"19_CR24","first-page":"65","volume":"29","author":"RH M\u00f6hring","year":"1985","unstructured":"M\u00f6hring, R.H., Radermacher, F.J., Weiss, G.: Stochastic scheduling problems II: set strategies. ZOR - Z. Oper. Res. 29, 65\u2013104 (1985)","journal-title":"ZOR - Z. Oper. Res."},{"key":"19_CR25","doi-asserted-by":"crossref","first-page":"924","DOI":"10.1145\/331524.331530","volume":"46","author":"RH M\u00f6hring","year":"1999","unstructured":"M\u00f6hring, R.H., Schulz, A.S., Uetz, M.: Approximation in stochastic scheduling: the power of LP-based priority policies. J. ACM 46, 924\u2013942 (1999)","journal-title":"J. ACM"},{"issue":"1","key":"19_CR26","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/0304-3975(94)90151-1","volume":"130","author":"R Motwani","year":"1994","unstructured":"Motwani, R., Phillips, S., Torng, E.: Non-clairvoyant scheduling. Theor. Comput. Sci. 130(1), 17\u201347 (1994)","journal-title":"Theor. Comput. Sci."},{"key":"19_CR27","volume-title":"Handbook of Scheduling: Algorithms, Models and Performance Analysis","author":"K Pruhs","year":"2004","unstructured":"Pruhs, K., Sgall, J., Torng, E.: Online scheduling. In: Leung, J. (ed.) Handbook of Scheduling: Algorithms, Models and Performance Analysis. CRC Press, Boca Raton (2004)"},{"key":"19_CR28","first-page":"703","volume":"12","author":"MH Rothkopf","year":"1966","unstructured":"Rothkopf, M.H.: Scheduling with random service times. Manage. Sci. 12, 703\u2013713 (1966)","journal-title":"Manage. Sci."},{"key":"19_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1007\/978-3-540-85097-7_42","volume-title":"Combinatorial Optimization and Applications","author":"AS Schulz","year":"2008","unstructured":"Schulz, A.S.: Stochastic online scheduling revisited. In: Yang, B., Du, D.-Z., Wang, C.A. (eds.) COCOA 2008. LNCS, vol. 5165, pp. 448\u2013457. Springer, Heidelberg (2008). doi: 10.1007\/978-3-540-85097-7_42"},{"key":"19_CR30","doi-asserted-by":"crossref","first-page":"206","DOI":"10.1145\/375827.375840","volume":"48","author":"M Skutella","year":"2001","unstructured":"Skutella, M.: Convex quadratic and semidefinite programming relaxations in scheduling. J. ACM 48, 206\u2013242 (2001)","journal-title":"J. ACM"},{"issue":"3","key":"19_CR31","doi-asserted-by":"crossref","first-page":"851","DOI":"10.1287\/moor.2015.0757","volume":"41","author":"M Skutella","year":"2016","unstructured":"Skutella, M., Sviridenko, M., Uetz, M.: Unrelated machine scheduling with stochastic processing times. Math. Oper. Res. 41(3), 851\u2013864 (2016)","journal-title":"Math. Oper. Res."},{"key":"19_CR32","doi-asserted-by":"crossref","first-page":"788","DOI":"10.1137\/S0097539702415007","volume":"34","author":"M Skutella","year":"2005","unstructured":"Skutella, M., Uetz, M.: Stochastic machine scheduling with precedence constraints. SIAM J. Comput. 34, 788\u2013802 (2005)","journal-title":"SIAM J. Comput."},{"key":"19_CR33","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1016\/S0167-6377(03)00047-6","volume":"31","author":"M Uetz","year":"2003","unstructured":"Uetz, M.: When greediness fails: examples from stochastic scheduling. Oper. Res. Lett. 31, 413\u2013419 (2003)","journal-title":"Oper. Res. Lett."},{"key":"19_CR34","doi-asserted-by":"crossref","first-page":"841","DOI":"10.1017\/S0021900200112008","volume":"23","author":"R Weber","year":"1986","unstructured":"Weber, R., Varaiya, P., Walrand, J.: Scheduling jobs with stochastically ordered processing times on parallel machines to minimize expected owtime. J. Appl. Probab. 23, 841\u2013847 (1986)","journal-title":"J. Appl. Probab."},{"key":"19_CR35","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1017\/S0021900200046921","volume":"17","author":"G Weiss","year":"1980","unstructured":"Weiss, G., Pinedo, M.: Scheduling tasks with exponential service times on non-identical processors to minimize various cost functions. J. Appl. Probab. 17, 187\u2013202 (1980)","journal-title":"J. Appl. Probab."}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-59250-3_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,24]],"date-time":"2019-09-24T23:50:05Z","timestamp":1569369005000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-59250-3_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319592497","9783319592503"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-59250-3_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}