{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,4]],"date-time":"2026-06-04T02:09:00Z","timestamp":1780538940152,"version":"3.54.1"},"reference-count":30,"publisher":"World Scientific Pub Co Pte Ltd","issue":"01","funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["71832001"],"award-info":[{"award-number":["71832001"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["72271051"],"award-info":[{"award-number":["72271051"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["72071144"],"award-info":[{"award-number":["72071144"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100012226","name":"Fundamental Research Funds for the Central Universities","doi-asserted-by":"crossref","award":["(2232018H-07"],"award-info":[{"award-number":["(2232018H-07"]}],"id":[{"id":"10.13039\/501100012226","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Asia Pac. J. Oper. Res."],"published-print":{"date-parts":[[2024,2]]},"abstract":"<jats:p> This work investigates a new semi-online scheduling problem with lookahead. We focus on job scheduling on two identical parallel machines, where deterministic online algorithms only know the information of [Formula: see text] initial jobs (i.e., the initial-lookahead information), while the following jobs still arrive one-by-one in an over-list fashion. We consider makespan minimization as the objective. The study aims at revealing the value of knowing [Formula: see text] initial jobs, which are used to improve the competitive performance of those online algorithms without such initial-lookahead information. We provide the following findings: (1) For the scenario where the [Formula: see text] initial jobs are all the largest jobs with length [Formula: see text], we prove that the classical LIST algorithm is optimal with competitive ratio [Formula: see text]; (2) For the scenario where the total length of these [Formula: see text] jobs is at least [Formula: see text], we show that any online algorithm has a competitive ratio at least 3\/2, implying that the initial-lookahead knowledge is powerless since there exists a 3\/2-competitive online algorithm without such information; (3) For the scenario where the total length of these [Formula: see text] jobs is at least [Formula: see text] ([Formula: see text]), we propose an online algorithm, named as LPT-LIST, with competitive ratio of [Formula: see text], implying that the initial-lookahead information indeed helps to improve the competitiveness of those online algorithms lacking such information. <\/jats:p>","DOI":"10.1142\/s0217595923500033","type":"journal-article","created":{"date-parts":[[2023,1,19]],"date-time":"2023-01-19T06:35:27Z","timestamp":1674110127000},"source":"Crossref","is-referenced-by-count":6,"title":["Semi-Online Scheduling on Two Identical Parallel Machines with Initial-Lookahead Information"],"prefix":"10.1142","volume":"41","author":[{"given":"Feifeng","family":"Zheng","sequence":"first","affiliation":[{"name":"Glorious Sun School of Business and Management, Donghua University, Shanghai 200051, P. R. China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuhong","family":"Chen","sequence":"additional","affiliation":[{"name":"Glorious Sun School of Business and Management, Donghua University, Shanghai 200051, P. R. China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ming","family":"Liu","sequence":"additional","affiliation":[{"name":"School of Economics and Management, Tongji University, Shanghai 200092, P. R. China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yinfeng","family":"Xu","sequence":"additional","affiliation":[{"name":"School of Management, Xi\u2019an Jiaotong University, Xi\u2019an, Shaanxi 710049, P. R. China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"219","published-online":{"date-parts":[[2023,3,31]]},"reference":[{"key":"S0217595923500033BIB001","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.03.031"},{"key":"S0217595923500033BIB002","doi-asserted-by":"publisher","DOI":"10.1007\/s10951-007-0023-y"},{"key":"S0217595923500033BIB003","volume-title":"Online Computation and Competitive Analysis.","author":"Borodin A","year":"1998"},{"key":"S0217595923500033BIB004","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-020-00633-w"},{"key":"S0217595923500033BIB005","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.11.018"},{"key":"S0217595923500033BIB006","doi-asserted-by":"publisher","DOI":"10.1007\/s10951-015-0464-7"},{"key":"S0217595923500033BIB007","doi-asserted-by":"publisher","DOI":"10.1007\/s10100-018-0536-9"},{"key":"S0217595923500033BIB008","doi-asserted-by":"publisher","DOI":"10.1016\/j.omega.2015.10.009"},{"issue":"6","key":"S0217595923500033BIB009","first-page":"2489","volume":"21","author":"Dunke F","year":"2019","journal-title":"Operational Research"},{"key":"S0217595923500033BIB010","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2021.105646"},{"key":"S0217595923500033BIB011","doi-asserted-by":"publisher","DOI":"10.1007\/s10951-018-0567-z"},{"key":"S0217595923500033BIB012","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1966.tb01709.x"},{"key":"S0217595923500033BIB013","doi-asserted-by":"publisher","DOI":"10.1137\/0117039"},{"key":"S0217595923500033BIB014","doi-asserted-by":"publisher","DOI":"10.1007\/s11590-018-01384-8"},{"key":"S0217595923500033BIB015","doi-asserted-by":"publisher","DOI":"10.3934\/jimo.2020132"},{"key":"S0217595923500033BIB016","doi-asserted-by":"publisher","DOI":"10.1142\/S0217595919500246"},{"key":"S0217595923500033BIB017","doi-asserted-by":"publisher","DOI":"10.1007\/s10951-015-0430-4"},{"key":"S0217595923500033BIB018","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-012-1271-6"},{"key":"S0217595923500033BIB019","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.07.056"},{"key":"S0217595923500033BIB020","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.05.024"},{"key":"S0217595923500033BIB021","doi-asserted-by":"publisher","DOI":"10.1142\/S0217595915500281"},{"key":"S0217595923500033BIB022","doi-asserted-by":"publisher","DOI":"10.1142\/S0217595915500475"},{"issue":"3","key":"S0217595923500033BIB023","first-page":"28","volume":"22","author":"Li Y","year":"2018","journal-title":"Operations Research Transactions"},{"key":"S0217595923500033BIB024","doi-asserted-by":"publisher","DOI":"10.1007\/s10951-010-0192-y"},{"key":"S0217595923500033BIB025","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21398-9_32"},{"key":"S0217595923500033BIB026","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-019-00381-6"},{"key":"S0217595923500033BIB027","doi-asserted-by":"publisher","DOI":"10.1007\/978-981-16-6890-6_73"},{"key":"S0217595923500033BIB028","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-7997-1_2"},{"key":"S0217595923500033BIB029","doi-asserted-by":"publisher","DOI":"10.1177\/1063293X17728763"},{"key":"S0217595923500033BIB030","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2012.06.003"}],"container-title":["Asia-Pacific Journal of Operational Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0217595923500033","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,14]],"date-time":"2024-02-14T15:57:10Z","timestamp":1707926230000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0217595923500033"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,31]]},"references-count":30,"journal-issue":{"issue":"01","published-print":{"date-parts":[[2024,2]]}},"alternative-id":["10.1142\/S0217595923500033"],"URL":"https:\/\/doi.org\/10.1142\/s0217595923500033","relation":{},"ISSN":["0217-5959","1793-7019"],"issn-type":[{"value":"0217-5959","type":"print"},{"value":"1793-7019","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,3,31]]},"article-number":"2350003"}}