{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,2]],"date-time":"2026-03-02T22:34:00Z","timestamp":1772490840433,"version":"3.50.1"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,5,11]],"date-time":"2022-05-11T00:00:00Z","timestamp":1652227200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,5,11]],"date-time":"2022-05-11T00:00:00Z","timestamp":1652227200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["N\/A"],"award-info":[{"award-number":["N\/A"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2022,8]]},"DOI":"10.1007\/s10878-022-00865-y","type":"journal-article","created":{"date-parts":[[2022,5,11]],"date-time":"2022-05-11T15:05:18Z","timestamp":1652281518000},"page":"877-893","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Improved approximation algorithms for non-preemptive multiprocessor scheduling with testing"],"prefix":"10.1007","volume":"44","author":[{"given":"Mingyang","family":"Gong","sequence":"first","affiliation":[]},{"given":"Randy","family":"Goebel","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4283-3396","authenticated-orcid":false,"given":"Guohui","family":"Lin","sequence":"additional","affiliation":[]},{"given":"Eiji","family":"Miyano","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,5,11]]},"reference":[{"key":"865_CR1","first-page":"134","volume":"2002","author":"S Albers","year":"2002","unstructured":"Albers S (2002) On randomized online scheduling. Proc ACM STOC 2002:134\u2013143","journal-title":"Proc ACM STOC"},{"key":"865_CR2","first-page":"127","volume":"2020","author":"S Albers","year":"2020","unstructured":"Albers S, Eckl A (2020) Explorable uncertainty in scheduling with non-uniform testing times. WAOA 2020:127\u2013142","journal-title":"WAOA"},{"key":"865_CR3","first-page":"29","volume":"2021","author":"S Albers","year":"2021","unstructured":"Albers S, Eckl A (2021) Scheduling with testing on multiple identical parallel machines. WADS 2021:29\u201342","journal-title":"WADS"},{"key":"865_CR4","first-page":"1","volume":"23","author":"SY Cai","year":"2002","unstructured":"Cai SY (2002) Semi online scheduling on three identical machines. J Wenzhou Teachers College 23:1\u20133 (In Chinese)","journal-title":"J Wenzhou Teachers College"},{"key":"865_CR5","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1016\/0167-6377(94)90071-X","volume":"16","author":"B Chen","year":"1994","unstructured":"Chen B, Vliet A, Woeginger G (1994) New lower and upper bounds for on-line scheduling. Oper Res Lett 16:221\u2013230","journal-title":"Oper Res Lett"},{"key":"865_CR6","unstructured":"D\u00fcrr C, Erlebach T, Megow N, and Mei\u00dfner J (2018) Scheduling with explorable uncertainty. ITCS 2018, LIPIcs 94, pages 30:1\u201330:14,"},{"key":"865_CR7","doi-asserted-by":"publisher","first-page":"3630","DOI":"10.1007\/s00453-020-00742-2","volume":"82","author":"C D\u00fcrr","year":"2020","unstructured":"D\u00fcrr C, Erlebach T, Megow N, Mei\u00dfner J (2020) An adversarial model for scheduling with testing. Algorithmica 82:3630\u20133675","journal-title":"Algorithmica"},{"key":"865_CR8","first-page":"107","volume":"9","author":"U Faigle","year":"1989","unstructured":"Faigle U, Kern W, Turan G (1989) On the performance of on-line algorithms for partition problems. Acta Cybernet 9:107\u2013119","journal-title":"Acta Cybernet"},{"key":"865_CR9","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1002\/1099-1425(200011\/12)3:6<343::AID-JOS54>3.0.CO;2-2","volume":"3","author":"R Fleischer","year":"2000","unstructured":"Fleischer R, Wahl M (2000) On-line scheduling revisited. J Sched 3:343\u2013353","journal-title":"J Sched"},{"key":"865_CR10","doi-asserted-by":"publisher","first-page":"1563","DOI":"10.1002\/j.1538-7305.1966.tb01709.x","volume":"45","author":"RL Graham","year":"1966","unstructured":"Graham RL (1966) Bounds for certain multiprocessing anomalies. Bell Labs Tech J 45:1563\u20131581","journal-title":"Bell Labs Tech J"},{"key":"865_CR11","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1007\/s006070050020","volume":"62","author":"Y He","year":"1999","unstructured":"He Y, Zhang G (1999) Semi online scheduling on two identical machines. Computing 62:179\u2013187","journal-title":"Computing"},{"key":"865_CR12","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/s10951-013-0329-x","volume":"16","author":"K Lee","year":"2003","unstructured":"Lee K, Lim K (2003) Semi-online scheduling problems on a small number of machines. J Sched 16:461\u2013477","journal-title":"J Sched"},{"key":"865_CR13","unstructured":"Rudin JF III (2001) Improved bounds for the on-line scheduling problem. PhD thesis"},{"key":"865_CR14","doi-asserted-by":"publisher","first-page":"717","DOI":"10.1137\/S0097539702403438","volume":"32","author":"JF Rudin III","year":"2003","unstructured":"Rudin JF III, Chandrasekaran R (2003) Improved bound for the online scheduling problem. SIAM J Comput 32:717\u2013735","journal-title":"SIAM J Comput"},{"key":"865_CR15","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1016\/j.orl.2015.07.002","volume":"43","author":"Z Tan","year":"2015","unstructured":"Tan Z, Li R (2015) Pseudo lower bounds for online parallel machine scheduling. Oper Res Lett 43:489\u2013494","journal-title":"Oper Res Lett"},{"key":"865_CR16","first-page":"23","volume":"35","author":"Y Wu","year":"2008","unstructured":"Wu Y, Huang Y, Yang QF (2008) Semi-online multiprocessor scheduling with the longest given processing time. J Zhejiang Univ: Sci Ed 35:23\u201326 (In Chinese)","journal-title":"J Zhejiang Univ: Sci Ed"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-022-00865-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-022-00865-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-022-00865-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,29]],"date-time":"2022-07-29T07:34:04Z","timestamp":1659080044000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-022-00865-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,11]]},"references-count":16,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,8]]}},"alternative-id":["865"],"URL":"https:\/\/doi.org\/10.1007\/s10878-022-00865-y","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,5,11]]},"assertion":[{"value":"21 April 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 May 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}