{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,2]],"date-time":"2026-03-02T11:09:29Z","timestamp":1772449769050,"version":"3.50.1"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,9,2]],"date-time":"2025-09-02T00:00:00Z","timestamp":1756771200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,9,2]],"date-time":"2025-09-02T00:00:00Z","timestamp":1756771200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"name":"NSERC Canada"},{"name":"NNSF China","award":["12371316, 12471301"],"award-info":[{"award-number":["12371316, 12471301"]}]},{"name":"NNSF China","award":["61972329"],"award-info":[{"award-number":["61972329"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[2026,3]]},"DOI":"10.1007\/s10479-025-06804-4","type":"journal-article","created":{"date-parts":[[2025,9,2]],"date-time":"2025-09-02T15:52:22Z","timestamp":1756828342000},"page":"71-101","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Randomized algorithms for fully online multiprocessor scheduling with testing"],"prefix":"10.1007","volume":"358","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-9040-3437","authenticated-orcid":false,"given":"Mingyang","family":"Gong","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3061-1171","authenticated-orcid":false,"given":"Zhi-Zhong","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3013-3325","authenticated-orcid":false,"given":"Guangting","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4283-3396","authenticated-orcid":false,"given":"Guohui","family":"Lin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4344-8791","authenticated-orcid":false,"given":"Lusheng","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,9,2]]},"reference":[{"key":"6804_CR1","first-page":"134","volume":"2002","author":"S Albers","year":"2002","unstructured":"Albers, S. (2002). On randomized online scheduling. In Proceedings of ACM STOC, 2002, 134\u2013143.","journal-title":"In Proceedings of ACM STOC"},{"key":"6804_CR2","doi-asserted-by":"crossref","unstructured":"Albers, S., & Eckl, A. (2020) Explorable uncertainty in scheduling with non-uniform testing times. In Proceedings of WAOA 2020, LNCS 12806, pages 127\u2013142, A full version appears as \u201carXiv : 2009.13316\u201d in Computing Research Repository.","DOI":"10.1007\/978-3-030-80879-2_9"},{"key":"6804_CR3","doi-asserted-by":"crossref","unstructured":"Albers, S., & Eckl, A. (2021) Scheduling with testing on multiple identical parallel machines. In Proceedings of WADS 2021, LNCS 12808, pages 29\u201342, A full version appears as \u201carXiv.2105.02052\u201d in Computing Research Repository.","DOI":"10.1007\/978-3-030-83508-8_3"},{"key":"6804_CR4","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1006\/inco.1999.2809","volume":"158","author":"Y Bartal","year":"2000","unstructured":"Bartal, Y., Chrobak, M., & Larmore, L. L. (2000). A randomized algorithm for two servers on the line. Information and Computation, 158, 53\u201369.","journal-title":"Information and Computation"},{"key":"6804_CR5","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1006\/jcss.1995.1074","volume":"51","author":"Y Bartal","year":"1995","unstructured":"Bartal, Y., Fiat, A., Karloff, H. J., & Vohra, R. (1995). New algorithms for an ancient scheduling problem. Journal of Computer and Systems Science, 51, 359\u2013366.","journal-title":"Journal of Computer and Systems Science"},{"key":"6804_CR6","doi-asserted-by":"crossref","unstructured":"Buld, F., & Schulz, A.\u00a0S. (2025) Scheduling with testing: Competitive algorithms for minimizing the total weighted completion time in the adversarial model. In Proceedings of IJTCS-FAW 2025, LNCS 15828, pages 64\u201377","DOI":"10.1007\/978-981-96-8312-3_5"},{"key":"6804_CR7","unstructured":"D\u00fcrr, C., Erlebach, T., Megow, N., & Mei\u00dfner, J. (2018) Scheduling with explorable uncertainty. In Proceedings of ITCS 2018, LIPIcs 94, pages 30:1\u201330:14"},{"key":"6804_CR8","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":"6804_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. Journal of Scheduling, 3, 343\u2013353.","journal-title":"Journal of Scheduling"},{"key":"6804_CR10","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1007\/s10878-007-9131-z","volume":"16","author":"S Fung","year":"2008","unstructured":"Fung, S., Poon, C., & Zheng, F. (2008). Online interval scheduling: Randomized and multiprocessor cases. Journal of Combinatorial Optimization, 16, 248\u2013262.","journal-title":"Journal of Combinatorial Optimization"},{"key":"6804_CR11","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-completeness. San Francisco: W. H. Freeman and Company."},{"key":"6804_CR12","doi-asserted-by":"publisher","first-page":"1400","DOI":"10.1007\/s00453-023-01198-w","volume":"86","author":"M Gong","year":"2024","unstructured":"Gong, M., Chen, Z.-Z., & Hayashi, K. (2024). (a.k.a. G.\u00a0Lin) Approximation algorithms for multiprocessor scheduling with testing to minimize the total job completion time. Algorithmica, 86, 1400\u20131427.","journal-title":"Algorithmica"},{"key":"6804_CR13","unstructured":"Gong, M., Fan, J., Lin, G., Su, B., Su, Z., & Zhang, X. (2025) Multiprocessor scheduling with testing: Improved approximation algorithms and numerical experiments. Journal of Scheduling, 2025. Accepted for publication on July 1, also available at arxiv:2204.03299."},{"key":"6804_CR14","doi-asserted-by":"publisher","first-page":"877","DOI":"10.1007\/s10878-022-00865-y","volume":"44","author":"M Gong","year":"2022","unstructured":"Gong, M., Goebel, R., Lin, G., & Miyano, E. (2022). Improved approximation algorithms for non-preemptive multiprocessor scheduling with testing. Journal of Combinatorial Optimization, 44, 877\u2013893.","journal-title":"Journal of Combinatorial Optimization"},{"key":"6804_CR15","doi-asserted-by":"crossref","unstructured":"Gong, M., & Lin, G. (2021) Improved approximation algorithms for multiprocessor scheduling with testing. In Proceedings of FAW 2021, LNCS 12874, pages 65\u201377","DOI":"10.1007\/978-3-030-97099-4_5"},{"key":"6804_CR16","first-page":"1563","volume":"45","author":"RL Graham","year":"1966","unstructured":"Graham, R. L. (1966). Bounds for certain multiprocessing anomalies. Bell Labs Technical Journal, 45, 1563\u20131581.","journal-title":"Bell Labs Technical Journal"},{"key":"6804_CR17","doi-asserted-by":"publisher","first-page":"776","DOI":"10.1287\/mnsc.2017.2973","volume":"65","author":"R Levi","year":"2019","unstructured":"Levi, R., Magnanti, T., & Shaposhnik, Y. (2019). Scheduling with testing. Management Science, 65, 776\u2013793.","journal-title":"Management Science"},{"key":"6804_CR18","doi-asserted-by":"crossref","unstructured":"Liu A.\u00a0H.-H, Liu F.-H, Wong P.\u00a0W.\u00a0H, Zhang X.-O (2023) The power of amortization on scheduling with explorable uncertainty. In Proceedings of WAOA 2023, LNCS 14297, pages 90\u2013103","DOI":"10.1007\/978-3-031-49815-2_7"},{"key":"6804_CR19","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/BF01294261","volume":"11","author":"N Reingold","year":"1994","unstructured":"Reingold, N., Westbrook, J. R., & Sleator, D. D. (1994). Randomized competitive algorithms for the list update problem. Algorithmica, 11, 15\u201332.","journal-title":"Algorithmica"},{"key":"6804_CR20","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/s004530010014","volume":"28","author":"SS Seiden","year":"2000","unstructured":"Seiden, S. S. (2000). Online randomized multiprocessor scheduling. Algorithmica, 28, 173\u2013216.","journal-title":"Algorithmica"},{"key":"6804_CR21","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1023\/A:1022960526107","volume":"6","author":"SS Seiden","year":"2003","unstructured":"Seiden, S. S. (2003). Barely random algorithms for multiprocessor scheduling. Journal of Scheduling, 6, 309\u2013334.","journal-title":"Journal of Scheduling"},{"key":"6804_CR22","first-page":"222","volume":"1977","author":"AC Yao","year":"1977","unstructured":"Yao, A. C. (1977). Probabilistic computations: Toward a unified measure of complexity. In Proceedings of FOCS, 1977, 222\u2013227.","journal-title":"In Proceedings of FOCS"}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-025-06804-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10479-025-06804-4","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-025-06804-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,2]],"date-time":"2026-03-02T10:43:56Z","timestamp":1772448236000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10479-025-06804-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,2]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,3]]}},"alternative-id":["6804"],"URL":"https:\/\/doi.org\/10.1007\/s10479-025-06804-4","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"value":"0254-5330","type":"print"},{"value":"1572-9338","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,9,2]]},"assertion":[{"value":"7 January 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 August 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 September 2025","order":3,"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 interests"}}]}}