{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:20:50Z","timestamp":1740122450147,"version":"3.37.3"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,6,30]],"date-time":"2022-06-30T00:00:00Z","timestamp":1656547200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,6,30]],"date-time":"2022-06-30T00:00:00Z","timestamp":1656547200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["71771048"],"award-info":[{"award-number":["71771048"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100014718","name":"Innovative Research Group Project of the National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["71832001"],"award-info":[{"award-number":["71832001"]}],"id":[{"id":"10.13039\/100014718","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100012226","name":"Fundamental Research Funds for the Central Universities","doi-asserted-by":"publisher","award":["2232018H-07"],"award-info":[{"award-number":["2232018H-07"]}],"id":[{"id":"10.13039\/501100012226","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,9]]},"DOI":"10.1007\/s10878-022-00882-x","type":"journal-article","created":{"date-parts":[[2022,6,30]],"date-time":"2022-06-30T07:02:53Z","timestamp":1656572573000},"page":"1060-1076","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Competitive analysis of online machine rental and online parallel machine scheduling problems with workload fence"],"prefix":"10.1007","volume":"44","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1603-4163","authenticated-orcid":false,"given":"Feifeng","family":"Zheng","sequence":"first","affiliation":[]},{"given":"Yuhong","family":"Chen","sequence":"additional","affiliation":[]},{"given":"Ming","family":"Liu","sequence":"additional","affiliation":[]},{"given":"Yinfeng","family":"Xu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,6,30]]},"reference":[{"key":"882_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2012.03.031","volume":"443","author":"S Albers","year":"2012","unstructured":"Albers S, Hellwig M (2012) Semi-online scheduling revisited. Theoret Comput Sci 443:1\u20139","journal-title":"Theoret Comput Sci"},{"issue":"2","key":"882_CR2","doi-asserted-by":"publisher","first-page":"492","DOI":"10.1007\/s00453-016-0172-5","volume":"78","author":"S Albers","year":"2017","unstructured":"Albers S, Hellwig M (2017) Online makespan minimization with parallel schedules. Algorithmica 78(2):492\u2013520","journal-title":"Algorithmica"},{"key":"882_CR3","unstructured":"Arnold TJR, Chapman SN, Clive LM (2012) Introduction to materials management, 7th edn. Prentice Hall"},{"issue":"4","key":"882_CR4","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/s10951-007-0023-y","volume":"10","author":"E Angelelli","year":"2007","unstructured":"Angelelli E, Nagy \u00c1B, Speranza MG, Tuza Z (2007) Semi-online scheduling on three processors with known sum of the tasks. J Sched 10(4):263\u2013269","journal-title":"J Sched"},{"issue":"2","key":"882_CR5","doi-asserted-by":"publisher","first-page":"472","DOI":"10.1007\/s10878-018-0309-3","volume":"36","author":"X Chai","year":"2018","unstructured":"Chai X, Li W (2018) Online scheduling with chain precedence constraints of equal-length jobs on parallel machines to minimize makespan. J Comb Optim 36(2):472\u2013492","journal-title":"J Comb Optim"},{"key":"882_CR6","doi-asserted-by":"publisher","unstructured":"Chen C, Zhang HL, Xu YF (2020) Online machine minimization with lookahead. J Comb Optim. https:\/\/doi.org\/10.1007\/s10878-020-00633-w","DOI":"10.1007\/s10878-020-00633-w"},{"key":"882_CR7","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1016\/j.tcs.2004.11.018","volume":"337","author":"TCE Cheng","year":"2005","unstructured":"Cheng TCE, Kellerer H, Kotov V (2005) Semi-on-line multiprocessor scheduling with given total processing time. Theoret Comput Sci 337:134\u2013146","journal-title":"Theoret Comput Sci"},{"issue":"5","key":"882_CR8","doi-asserted-by":"publisher","first-page":"1035","DOI":"10.1137\/S009753970343395X","volume":"33","author":"G D\u00f6sa","year":"2004","unstructured":"D\u00f6sa G, He Y (2004) Better online algorithms for scheduling with machine cost. SIAM J Comput 33(5):1035\u20131051","journal-title":"SIAM J Comput"},{"key":"882_CR9","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/j.disopt.2010.02.005","volume":"7","author":"G D\u00f6sa","year":"2010","unstructured":"D\u00f6sa G, Tan ZY (2010) New upper and lower bound for online scheduling with machine cost. Discret Optim 7:125\u2013135","journal-title":"Discret Optim"},{"key":"882_CR10","doi-asserted-by":"publisher","first-page":"1107","DOI":"10.1007\/s10100-018-0536-9","volume":"27","author":"G D\u00f6sa","year":"2019","unstructured":"D\u00f6sa G, Fuegenschuh A, Tan ZY, Tuza Z, Weske K (2019) Tight upper bounds for semi-online scheduling on two uniform machines with known optimum. CEJOR 27:1107\u20131130","journal-title":"CEJOR"},{"key":"882_CR11","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1016\/j.omega.2015.10.009","volume":"63","author":"F Dunke","year":"2016","unstructured":"Dunke F, Nickel S (2016) A general modeling approach to online optimization with lookahead. Omega 63:134\u2013153","journal-title":"Omega"},{"key":"882_CR12","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2021.105646","volume":"139","author":"D Dwibedy","year":"2022","unstructured":"Dwibedy D, Mohanty R (2022) Semi-online scheduling: A survey. Comput. Oper. Res. 139:105646","journal-title":"Comput Oper Res"},{"issue":"3","key":"882_CR13","doi-asserted-by":"publisher","first-page":"1220","DOI":"10.1137\/130919738","volume":"43","author":"M Englert","year":"2014","unstructured":"Englert M, Oezmen D, Westermann M (2014) The power of reordering for online minimum makespan scheduling. SIAM J Comput 43(3):1220\u20131237","journal-title":"SIAM J Comput"},{"key":"882_CR14","doi-asserted-by":"publisher","first-page":"3537","DOI":"10.1007\/s00453-021-00852-5","volume":"83","author":"M Englert","year":"2021","unstructured":"Englert M, Mezlaf D, Westermann M (2021) Online makespan scheduling with job migration on uniform machines. Algorithmica 83:3537\u20133566","journal-title":"Algorithmica"},{"issue":"3","key":"882_CR15","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/s10951-018-0567-z","volume":"21","author":"L Epstein","year":"2018","unstructured":"Epstein L (2018) A survey on makespan minimization in semi-online environments. J Sched 21(3):269\u2013284","journal-title":"J Sched"},{"issue":"2","key":"882_CR16","first-page":"107","volume":"9","author":"U Feigle","year":"1989","unstructured":"Feigle U, Kern W, Turan G (1989) On the performance of on-line algorithms for partition problems. Acta Cybernet 9(2):107\u2013119","journal-title":"Acta Cybernet"},{"issue":"1","key":"882_CR17","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1007\/s00224-013-9528-2","volume":"55","author":"SPY Fung","year":"2014","unstructured":"Fung SPY, Poon CK, Zheng FF (2014) Improved randomized online scheduling of intervals and jobs. Theory Comput Syst 55(1):202\u2013228","journal-title":"Theory Comput Syst"},{"key":"882_CR18","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 Syst Tech J 45:1563\u20131581","journal-title":"Bell Syst Tech J"},{"issue":"5","key":"882_CR19","doi-asserted-by":"publisher","first-page":"2140003","DOI":"10.1142\/S0217595921400030","volume":"38","author":"S Guo","year":"2021","unstructured":"Guo S, Ma R, Zhang Y, Fan B (2021) A semi-online algorithm for single machine scheduling with rejection. Asia-Pacific J Oper Res 38(5):2140003","journal-title":"Asia-Pacific J Oper Res"},{"issue":"1","key":"882_CR20","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/s10479-018-2928-6","volume":"298","author":"NG Hall","year":"2021","unstructured":"Hall NG, Posner ME, Potts CN (2021) Online production planning to maximize the number of on-time orders. Ann Oper Res 298(1):249\u2013269","journal-title":"Ann Oper Res"},{"issue":"9","key":"882_CR21","first-page":"2070","volume":"157","author":"C Imreh","year":"2006","unstructured":"Imreh C (2006) Online scheduling with general machine cost functions. Electr Notes Discrete Math 157(9):2070\u20132077","journal-title":"Electr Notes Discrete Math"},{"issue":"6","key":"882_CR22","doi-asserted-by":"publisher","first-page":"3551","DOI":"10.3934\/jimo.2020132","volume":"17","author":"CW Jiao","year":"2021","unstructured":"Jiao CW, Feng Q (2021) Research on the parallel-batch scheduling with linearly lookahead model. J Ind Manag Optim 17(6):3551\u20133558","journal-title":"J Ind Manag Optim"},{"issue":"5","key":"882_CR23","doi-asserted-by":"publisher","first-page":"1950024","DOI":"10.1142\/S0217595919500246","volume":"36","author":"CW Jiao","year":"2019","unstructured":"Jiao CW, Yuan JJ, Feng Q (2019) Online algorithms for scheduling unit length jobs on unbounded parallel-batch machines with linearly lookahead. Asia-Pacific J Oper Res 36(5):1950024","journal-title":"Asia-Pacific J Oper Res"},{"issue":"1\u20134","key":"882_CR24","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/BF01762111","volume":"3","author":"AR Karlin","year":"1988","unstructured":"Karlin AR, Manasse MS, Rudolph L, Sleator DD (1988) Competitive snoopy caching. Algorithmica 3(1\u20134):79\u2013119","journal-title":"Algorithmica"},{"issue":"6","key":"882_CR25","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1007\/s10951-015-0430-4","volume":"18","author":"H Kellerer","year":"2015","unstructured":"Kellerer H, Kotov V, Gabay M (2015) An efficient algorithm for semi-online multiprocessor scheduling with given total processing time. J Sched 18(6):623\u2013630","journal-title":"J Sched"},{"key":"882_CR26","doi-asserted-by":"crossref","unstructured":"Khanafer A, Kodialam M, Puttaswamy KPN, (2013) The constrained Ski-Rental problem and its application to online cloud cost optimization. (2013) IEEE INFOCOM, 14\u201319 April 2013. Italy, Turin, pp 1492\u20131500","DOI":"10.1109\/INFCOM.2013.6566944"},{"issue":"1","key":"882_CR27","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/s10479-012-1271-6","volume":"204","author":"K Lee","year":"2013","unstructured":"Lee K, Leung JYT, Pinedo ML (2013) Makespan minimization in online scheduling with machine eligibility. Ann Oper Res 204(1):189\u2013222","journal-title":"Ann Oper Res"},{"key":"882_CR28","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1016\/j.tcs.2014.05.024","volume":"543","author":"WH Li","year":"2014","unstructured":"Li WH, Yuan JJ, Yang SF (2014) Online scheduling of incompatible unit-length job families with lookahead. Theoret Comput Sci 543:120\u2013125","journal-title":"Theoret Comput Sci"},{"issue":"6","key":"882_CR29","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1142\/S0217595915500475","volume":"32","author":"WH Li","year":"2015","unstructured":"Li WH, Yuan JJ (2015) An improved online algorithm for the online preemptive scheduling of equal-length intervals on a single machine with lookahead. Asia-Pacific J Oper Res 32(6):1\u20139","journal-title":"Asia-Pacific J Oper Res"},{"key":"882_CR30","unstructured":"Lucarelli G, Thang NK, Srivastav A, Trystram D (2016) Online non-preemptive scheduling in a resource augmentation model based on duality. 24th Annual European Symposium on Algorithms (ESA 2016), 22-24 Aug 2016, Aarhus, Denmark, 17 pages"},{"key":"882_CR31","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1007\/s10951-010-0192-y","volume":"14","author":"M Mandelbaum","year":"2011","unstructured":"Mandelbaum M, Shabtay D (2011) Scheduling unit length jobs on parallel machines with lookahead information. J Sched 14:335\u2013350","journal-title":"J Sched"},{"issue":"18","key":"882_CR32","doi-asserted-by":"publisher","first-page":"2546","DOI":"10.1016\/j.dam.2007.07.004","volume":"155","author":"J Nagy-Gy\u00f6gy","year":"2007","unstructured":"Nagy-Gy\u00f6gy J, Imreh C (2007) Online scheduling with machine cost and rejection. Discret Appl Math 155(18):2546\u20132554","journal-title":"Discret Appl Math"},{"issue":"1","key":"882_CR33","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1007\/s10878-019-00381-6","volume":"38","author":"N Pinson","year":"2019","unstructured":"Pinson N, Spieksma FCR (2019) Online interval scheduling on two related machines: the power of lookahead. J Comb Optim 38(1):224\u2013253","journal-title":"J Comb Optim"},{"issue":"5","key":"882_CR34","doi-asserted-by":"publisher","first-page":"849","DOI":"10.1057\/jors.2009.38","volume":"61","author":"AJ Ruiz-Torres","year":"2010","unstructured":"Ruiz-Torres AJ, L\u00f3pez FJ, Wojciechowski PJ, Ho CJ (2010) Parallel machine scheduling problems considering regular measures of performance and machine cost. J Oper Res Soci 61(5):849\u2013857","journal-title":"J Oper Res Soci"},{"key":"882_CR35","unstructured":"Shah A, Rajkumar A (2021) Sequential ski rental problem. 20th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2021), 3-7 May 2021, London, UK, 10 pages"},{"key":"882_CR36","doi-asserted-by":"publisher","unstructured":"Tan ZY, Zhang A (2013). Online and semi-online scheduling. In Pardalos P, Du DZ, Graham R (eds) Handbook of Combinatorial Optimization, Springer, New York, NY, https:\/\/doi.org\/10.1007\/978-1-4419-7997-1_2","DOI":"10.1007\/978-1-4419-7997-1_2"},{"key":"882_CR37","unstructured":"Wang SF, Li J, Wang SQ (2020) Online algorithms for multi-shop ski renal with machine learned advice. 34th Conference on Neural Information Processing Systems (NeurIPS 2020) 6-12 Dec 2020, Vancouver, Canada, 11 pages"},{"key":"882_CR38","unstructured":"Wu BH, Bao W, Yuan D (2021) Competitive analysis for two-level ski-rental problem. 35th AAAI Conference on Artificial Intelligence (AAAI 2021) 2-9 Feb 2021, Online, pp. 12034-12041"},{"issue":"4","key":"882_CR39","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1177\/1063293X17728763","volume":"25","author":"ZZ Xu","year":"2017","unstructured":"Xu ZZ, Chen X, Xu XJ, Zhao XW, Dai J, Jia MF (2017) A look-ahead algorithm for online multiple workflow scheduling problem in heterogeneous systems. Concurr Eng Res Appl 25(4):331\u2013342","journal-title":"Concurr Eng Res Appl"},{"key":"882_CR40","doi-asserted-by":"publisher","unstructured":"Zhang XY, Ma R, Sun J, Zhang ZB (2020) Randomized selection algorithm for online stochastic unrelated machines scheduling. J Comb Optim. https:\/\/doi.org\/10.1007\/s10878-020-00542-y","DOI":"10.1007\/s10878-020-00542-y"},{"issue":"1","key":"882_CR41","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1016\/j.cor.2012.06.003","volume":"40","author":"FF Zheng","year":"2013","unstructured":"Zheng FF, Cheng YC, Liu M, Xu YF (2013) Online interval scheduling on a single machine with finite lookahead. Comput Oper Res 40(1):180\u2013191","journal-title":"Comput Oper Res"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-022-00882-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-022-00882-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-022-00882-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,13]],"date-time":"2022-08-13T06:16:19Z","timestamp":1660371379000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-022-00882-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,30]]},"references-count":41,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,9]]}},"alternative-id":["882"],"URL":"https:\/\/doi.org\/10.1007\/s10878-022-00882-x","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2022,6,30]]},"assertion":[{"value":"20 June 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 June 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 have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}