{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T12:29:07Z","timestamp":1759667347059,"version":"3.37.3"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2020,2,18]],"date-time":"2020-02-18T00:00:00Z","timestamp":1581984000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,2,18]],"date-time":"2020-02-18T00:00:00Z","timestamp":1581984000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"Natural Science Foundation of China","doi-asserted-by":"crossref","award":["11871280","11971349"],"award-info":[{"award-number":["11871280","11971349"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"Natural Science Foundation of China","doi-asserted-by":"crossref","award":["11501171","11771251"],"award-info":[{"award-number":["11501171","11771251"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100013088","name":"Qing Lan Project","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100013088","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Key Scientific Research Project of Guangdong Province","award":["2018GKZDXM004"],"award-info":[{"award-number":["2018GKZDXM004"]}]},{"name":"the Talent Project of Guangdong Industry Polytechnic","award":["RC2016-004","KYRC2018-001"],"award-info":[{"award-number":["RC2016-004","KYRC2018-001"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2022,10]]},"DOI":"10.1007\/s10878-020-00542-y","type":"journal-article","created":{"date-parts":[[2020,2,18]],"date-time":"2020-02-18T10:02:51Z","timestamp":1582020171000},"page":"1796-1811","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Randomized selection algorithm for online stochastic unrelated machines scheduling"],"prefix":"10.1007","volume":"44","author":[{"given":"Xiaoyan","family":"Zhang","sequence":"first","affiliation":[]},{"given":"Ran","family":"Ma","sequence":"additional","affiliation":[]},{"given":"Jian","family":"Sun","sequence":"additional","affiliation":[]},{"given":"Zan-Bo","family":"Zhang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,2,18]]},"reference":[{"key":"542_CR1","doi-asserted-by":"publisher","first-page":"686","DOI":"10.1287\/moor.1040.0092","volume":"29","author":"EJ Anderson","year":"2004","unstructured":"Anderson EJ, Potts C (2004) Online scheduling of a single machine to minimize total weighted completion time. Math Oper Res 29:686\u2013697","journal-title":"Math Oper Res"},{"key":"542_CR2","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/S0097539797327180","volume":"31","author":"C Chekuri","year":"2001","unstructured":"Chekuri C, Motwani R, Natarajan B, Stein C (2001) Approximation techniques for average completion time scheduling. SIAM J Comput 31:146\u2013166","journal-title":"SIAM J Comput"},{"key":"542_CR3","doi-asserted-by":"publisher","first-page":"464","DOI":"10.1287\/opre.1060.0270","volume":"54","author":"M Chou","year":"2006","unstructured":"Chou M, Liu H, Queyranne M, Simchi-levi D (2006) On the asymptotic optimality of a simple on-line algorithm for the stochastic single-machine weighted completion time problem and its extensions. Oper Res 54:464\u2013474","journal-title":"Oper Res"},{"key":"542_CR4","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1007\/s10107-005-0588-1","volume":"106","author":"M Chou","year":"2006","unstructured":"Chou M, Queyranne M, Simchi-Levi D (2006) The asymptotic performance ratio of an on-line algorithm for uniform parallel machine scheduling with release dates. Math Program 106:137\u2013157","journal-title":"Math Program"},{"key":"542_CR5","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/s10107-007-0204-7","volume":"119","author":"JR Correa","year":"2009","unstructured":"Correa JR, Wagner MR (2009) LP-based online scheduling: from single to parallel machines. Math Program 119:109\u2013136","journal-title":"Math Program"},{"unstructured":"Edmonds J (1970) Submodular functions, matroids, and certain polyhedra. In: Proceedings of the international conference on cumbinatorics (Calgary Canada), pp 69\u201387","key":"542_CR6"},{"key":"542_CR7","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1137\/S089548019936223X","volume":"15","author":"MX Goemans","year":"2002","unstructured":"Goemans MX, Queyranne M, Schulz AS, Skutella M, Wang Y (2002) Single machine scheduling with release dates. SIAM J Discrete Math 15:165\u2013192","journal-title":"SIAM J Discrete Math"},{"key":"542_CR8","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","volume":"5","author":"RL Graham","year":"1979","unstructured":"Graham RL, Lawler EL, Lenstra JK, Rinnooy Kan AHG (1979) Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann Discret Math 5:287\u2013326","journal-title":"Ann Discret Math"},{"key":"542_CR9","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/s10479-011-0985-1","volume":"191","author":"MZ Gu","year":"2011","unstructured":"Gu MZ, Lu XW (2011) Asymptotical optimality of WSEPT for stochastic online scheduling on uniform machines. Ann Oper Res 191:97\u2013113","journal-title":"Ann Oper Res"},{"doi-asserted-by":"crossref","unstructured":"Gupta V, Moseley B, Uetz M, Xie Q (2017) Stochastic online scheduling on unrelated machines. In: International conference on integer programming and combinatorial optimization, IPCO 2017 book series: lecture notes in computer science, vol 10328, pp 228\u2013240","key":"542_CR10","DOI":"10.1007\/978-3-319-59250-3_19"},{"key":"542_CR11","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1287\/moor.22.3.513","volume":"22","author":"LA Hall","year":"1997","unstructured":"Hall LA, Schulz AS, Shmoys DB, Wein J (1997) Scheduling to minimize average completion time: off-line and online approximation algorithms. Math Oper Res 22:513\u2013544","journal-title":"Math Oper Res"},{"key":"542_CR12","doi-asserted-by":"publisher","first-page":"404","DOI":"10.1007\/3-540-61310-2_30","volume":"1084","author":"JA Hoogeveen","year":"1996","unstructured":"Hoogeveen JA, Vestjens APA (1996) Optimal on-line algorithms for single-machine scheduling. Lect Notes Comput Sci 1084:404\u2013414","journal-title":"Lect Notes Comput Sci"},{"key":"542_CR13","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/S0167-5060(08)70743-X","volume":"1","author":"JK Lenstra","year":"1977","unstructured":"Lenstra JK, Rinoooy Kan AHG, Brucker P (1977) Complexity of machine scheduling problems. Ann Discret Math 1:343\u2013362","journal-title":"Ann Discret Math"},{"key":"542_CR14","doi-asserted-by":"publisher","first-page":"2647","DOI":"10.1016\/j.cor.2008.11.008","volume":"36","author":"PH Liu","year":"2009","unstructured":"Liu PH, Lu XW (2009) Online scheduling of parallel machines to minimize total completion time. Comput Oper Res 36:2647\u20132652","journal-title":"Comput Oper Res"},{"key":"542_CR15","doi-asserted-by":"publisher","first-page":"95","DOI":"10.3934\/jimo.2009.5.95","volume":"5","author":"PH Liu","year":"2009","unstructured":"Liu PH, Lu XW (2009) Online scheduling of two uniform machines to minimize total completion times. J Ind Manag Optim 5:95\u2013102","journal-title":"J Ind Manag Optim"},{"key":"542_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2996800","volume":"13","author":"E L\u00fcbbecke","year":"2016","unstructured":"L\u00fcbbecke E, Maurer O, Megow N, Wiese A (2016) A new approach to online scheduling: approximating the optimal competitive ratio. ACM Trans Algorithms 13:1\u201334","journal-title":"ACM Trans Algorithms"},{"key":"542_CR17","doi-asserted-by":"publisher","first-page":"497","DOI":"10.3934\/jimo.2017057","volume":"14","author":"R Ma","year":"2018","unstructured":"Ma R, Tao JP (2018) An improved 2.11-competitive algorithm for online scheduling on parallel machines to minimize total weighted completion time. J Ind Manag Optim 14:497\u2013510","journal-title":"J Ind Manag Optim"},{"key":"542_CR18","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1016\/j.orl.2003.11.008","volume":"32","author":"N Megow","year":"2004","unstructured":"Megow N, Schulz AS (2004) Online scheduling to minimize average completion time revisited. Oper Res Lett 32:485\u2013490","journal-title":"Oper Res Lett"},{"key":"542_CR19","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1287\/moor.1060.0201","volume":"31","author":"N Megow","year":"2006","unstructured":"Megow N, Uetz M, Vredeveld T (2006) Models and algorithms for stochastic online scheduling. Math Oper Res 31:513\u2013525","journal-title":"Math Oper Res"},{"key":"542_CR20","doi-asserted-by":"publisher","first-page":"924","DOI":"10.1145\/331524.331530","volume":"46","author":"RH Mohring","year":"1999","unstructured":"Mohring RH, Schulz A, Uetz M (1999) Approximation in stochastic schedule: the power of LP-based priority policies. J ACM 46:924\u2013942","journal-title":"J ACM"},{"key":"542_CR21","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1287\/moor.1060.0239","volume":"32","author":"H Moulin","year":"2007","unstructured":"Moulin H (2007) On scheduling fees to prevent merging, splitting, and transferring of jobs. Math Oper Res 32:266\u2013283","journal-title":"Math Oper Res"},{"key":"542_CR22","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1007\/978-3-642-13036-6_31","volume":"6080","author":"R Sitters","year":"2010","unstructured":"Sitters R (2010) Efficient algorithms for average completion time scheduling. Lect Notes Comput Sci 6080:411\u2013423","journal-title":"Lect Notes Comput Sci"},{"key":"542_CR23","doi-asserted-by":"publisher","first-page":"851","DOI":"10.1287\/moor.2015.0757","volume":"41","author":"M Skutella","year":"2016","unstructured":"Skutella M, Sviridenko M, Uetz M (2016) Stochastic scheduling on unrelated machines. Math Oper Res 41:851\u2013864","journal-title":"Math Oper Res"},{"key":"542_CR24","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/nav.3800030106","volume":"3","author":"W Smith","year":"1956","unstructured":"Smith W (1956) Various optimizers for single stage production. Naval Res Logist Q 3:59\u201366","journal-title":"Naval Res Logist Q"},{"key":"542_CR25","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/j.cor.2013.09.016","volume":"43","author":"JP Tao","year":"2014","unstructured":"Tao JP (2014) A better online algorithm for the parallel machine scheduling to minimize the total weighted completion time. Comput Oper Res 43:215\u2013224","journal-title":"Comput Oper Res"},{"key":"542_CR26","doi-asserted-by":"publisher","first-page":"185","DOI":"10.3934\/jimo.2015.11.185","volume":"11","author":"JP Tao","year":"2015","unstructured":"Tao JP, Huang RH, Liu TD (2015) A 2.28-competitive algorithm for online scheduling on identical machines. J Ind Manag Optim 11:185\u2013198","journal-title":"J Ind Manag Optim"},{"unstructured":"Vestjens APA (1997) On-line machine scheduling. Ph.D. thesis. Eindhoven University of Technology, Netherlands","key":"542_CR27"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00542-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-020-00542-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00542-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,28]],"date-time":"2022-09-28T08:46:26Z","timestamp":1664354786000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-020-00542-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,18]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,10]]}},"alternative-id":["542"],"URL":"https:\/\/doi.org\/10.1007\/s10878-020-00542-y","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2020,2,18]]},"assertion":[{"value":"18 February 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}