{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,24]],"date-time":"2025-06-24T07:10:33Z","timestamp":1750749033212,"version":"3.37.3"},"reference-count":42,"publisher":"EDP Sciences","issue":"3","license":[{"start":{"date-parts":[[2024,6,25]],"date-time":"2024-06-25T00:00:00Z","timestamp":1719273600000},"content-version":"vor","delay-in-days":55,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["72271051"],"award-info":[{"award-number":["72271051"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["71832001"],"award-info":[{"award-number":["71832001"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["72071144"],"award-info":[{"award-number":["72071144"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"the Fundamental Research Funds for the Central Universities","award":["2232018H-07"],"award-info":[{"award-number":["2232018H-07"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2024,2,11]]},"published-print":{"date-parts":[[2024,5]]},"abstract":"<jats:p>This work studies the problem of semi-online scheduling on two uniform parallel machines with speeds 1 and <jats:italic>s<\/jats:italic> (\u22652), respectively. We introduce a novel concept of initial lookahead in which any deterministic online algorithm has the full knowledge of the first <jats:italic>k<\/jats:italic> jobs at the beginning, while the remaining jobs are released one-by-one in the online over-list mode. The objective of the considered problem is to minimize the makespan. We focus on the case where the first <jats:italic>k<\/jats:italic> jobs are of a total processing time not less than (<jats:italic>s<\/jats:italic> + 1)\u0394 where \u0394 is the largest job length, and it is assumed that <jats:italic>s<\/jats:italic> is an integer. We prove a lower bound of \n                                (<jats:italic>s<jats:sup>2<\/jats:sup><\/jats:italic>+<jats:italic>s<\/jats:italic>+1)\/(<jats:italic>s<jats:sup>2<\/jats:sup><\/jats:italic>+<jats:italic>s<\/jats:italic>)\n                            , and propose a deterministic semi-online algorithm with competitive ratio of (<jats:italic>s<\/jats:italic>+1)<jats:sup>2<\/jats:sup>\/<jats:italic>s<jats:sup>2<\/jats:sup><\/jats:italic>+<jats:italic>s<\/jats:italic>+1. The ratio is at most 9\/7 and much less than that of 1.618 for the corresponding case without initial lookahead (Cho and Sahni, <jats:italic>SIAM J. Comput<\/jats:italic>. <jats:bold>9<\/jats:bold> (1980) 91\u2013103). Our results demonstrate that a finite ability of initial lookahead can greatly improve the competitiveness of online algorithms.<\/jats:p>","DOI":"10.1051\/ro\/2024042","type":"journal-article","created":{"date-parts":[[2024,2,13]],"date-time":"2024-02-13T14:10:57Z","timestamp":1707833457000},"page":"2621-2630","source":"Crossref","is-referenced-by-count":2,"title":["Semi-online scheduling on two uniform parallel machines with initial lookahead"],"prefix":"10.1051","volume":"58","author":[{"given":"Feifeng","family":"Zheng","sequence":"first","affiliation":[]},{"given":"Yuhong","family":"Chen","sequence":"additional","affiliation":[]},{"given":"Ming","family":"Liu","sequence":"additional","affiliation":[]}],"member":"250","published-online":{"date-parts":[[2024,6,25]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/j.tcs.2007.12.005","volume":"393","author":"Angelelli","year":"2008","journal-title":"Theor. Comput. Sci."},{"key":"R2","unstructured":"Borodin A. and El-Yaniv R., Online Computation and Competitive Analysis. Cambridge University Press (1998)."},{"key":"R3","doi-asserted-by":"crossref","first-page":"105093","DOI":"10.1016\/j.cor.2020.105093","volume":"125","author":"Buchem","year":"2021","journal-title":"Comput. Oper. Res."},{"key":"R4","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1007\/s10878-009-9254-5","volume":"21","author":"Cai","year":"2011","journal-title":"J. Comb. Optim."},{"key":"R5","doi-asserted-by":"crossref","unstructured":"Chadha J.S., Garg N., Kumar A. and Muralidhara V.N., A competitive algorithm for minimizing weighted flow time on unrelated machines with speed augmentation, in Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, May 31\u2013Jun 2. Bethesda, MD, USA (2009) 679\u2013684.","DOI":"10.1145\/1536414.1536506"},{"key":"R6","doi-asserted-by":"crossref","first-page":"1149","DOI":"10.1007\/s10878-020-00633-w","volume":"43","author":"Chen","year":"2022","journal-title":"J. Comb. Optim."},{"key":"R7","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1137\/0209007","volume":"9","author":"Cho","year":"1980","journal-title":"SIAM J. Comput."},{"key":"R8","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1016\/j.jcss.2017.07.006","volume":"91","author":"Choudhury","year":"2018","journal-title":"J. Comput. Syst. Sci."},{"key":"R9","doi-asserted-by":"crossref","first-page":"102","DOI":"10.1016\/j.ipl.2006.02.012","volume":"99","author":"Dolgui","year":"2006","journal-title":"Inf. Process. Lett."},{"key":"R10","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1016\/j.ipl.2018.01.009","volume":"134","author":"Dolgui","year":"2018","journal-title":"Inf. Process. Lett."},{"key":"R11","doi-asserted-by":"crossref","first-page":"642","DOI":"10.1016\/j.tcs.2010.10.019","volume":"412","author":"D\u00f3sa","year":"2011","journal-title":"Theor. Comput. Sci."},{"key":"R12","doi-asserted-by":"crossref","first-page":"1107","DOI":"10.1007\/s10100-018-0536-9","volume":"27","author":"D\u00f3sa","year":"2019","journal-title":"Cent. Eur. J. Oper. Res."},{"key":"R13","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1016\/j.omega.2015.10.009","volume":"63","author":"Dunke","year":"2016","journal-title":"Omega"},{"key":"R14","first-page":"2489","volume":"21","author":"Dunke","year":"2019","journal-title":"Oper. Res."},{"key":"R15","doi-asserted-by":"crossref","first-page":"105646","DOI":"10.1016\/j.cor.2021.105646","volume":"139","author":"Dwibedy","year":"2022","journal-title":"Comput. Oper. Res."},{"key":"R16","doi-asserted-by":"crossref","first-page":"3537","DOI":"10.1007\/s00453-021-00852-5","volume":"83","author":"Englert","year":"2021","journal-title":"Algorithmica"},{"key":"R17","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/s10951-018-0567-z","volume":"21","author":"Epstein","year":"2018","journal-title":"J. Sched."},{"key":"R18","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1002\/jos.60","volume":"4","author":"Epstein","year":"2001","journal-title":"J. Sched."},{"key":"R19","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1016\/j.ipl.2015.11.012","volume":"116","author":"Epstein","year":"2016","journal-title":"Inf. Process. Lett."},{"key":"R20","doi-asserted-by":"crossref","first-page":"1563","DOI":"10.1002\/j.1538-7305.1966.tb01709.x","volume":"45","author":"Graham","year":"1966","journal-title":"Bell Syst. Tech. J."},{"key":"R21","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1007\/s10114-005-0829-5","volume":"23","author":"He","year":"2007","journal-title":"Acta Math. Sin."},{"key":"R22","doi-asserted-by":"crossref","first-page":"1092","DOI":"10.1016\/j.tcs.2010.12.008","volume":"412","author":"Hou","year":"2011","journal-title":"Theor. Comput. Sci."},{"key":"R23","doi-asserted-by":"crossref","first-page":"539","DOI":"10.1007\/s10951-012-0288-7","volume":"16","author":"Je\u017c","year":"2013","journal-title":"J. Sched."},{"key":"R24","doi-asserted-by":"crossref","first-page":"3551","DOI":"10.3934\/jimo.2020132","volume":"17","author":"Jiao","year":"2021","journal-title":"J. Ind. Manage. Optim."},{"key":"R25","doi-asserted-by":"crossref","first-page":"1950024","DOI":"10.1142\/S0217595919500246","volume":"36","author":"Jiao","year":"2019","journal-title":"Asia-Pac. J. Oper. Res."},{"key":"R26","doi-asserted-by":"crossref","first-page":"414","DOI":"10.1137\/S0097539799527969","volume":"27","author":"Li","year":"1998","journal-title":"SIAM J. Comput."},{"key":"R27","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1016\/j.tcs.2014.05.024","volume":"543","author":"Li","year":"2014","journal-title":"Theor. Comput. Sci."},{"key":"R28","first-page":"28","volume":"22","author":"Li","year":"2018","journal-title":"Oper. Res. Trans."},{"key":"R29","doi-asserted-by":"crossref","first-page":"2099","DOI":"10.1016\/j.tcs.2009.01.007","volume":"410","author":"Liu","year":"2009","journal-title":"Theor. Comput. Sci."},{"key":"R30","doi-asserted-by":"crossref","first-page":"104778","DOI":"10.1016\/j.cor.2019.104778","volume":"113","author":"Liu","year":"2020","journal-title":"Comput. Oper. Res."},{"key":"R31","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1016\/j.tcs.2013.04.013","volume":"489\u2013490","author":"Lu","year":"2013","journal-title":"Theor. Comput. Sci."},{"key":"R32","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1007\/s11424-006-0101-9","volume":"19","author":"Luo","year":"2006","journal-title":"J. Syst. Sci. Complexity"},{"key":"R33","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1007\/s10951-010-0192-y","volume":"14","author":"Mandelbaum","year":"2011","journal-title":"J. Sched."},{"key":"R34","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1007\/s10951-010-0177-x","volume":"14","author":"Musitelli","year":"2011","journal-title":"J. Sched."},{"key":"R35","doi-asserted-by":"crossref","first-page":"776","DOI":"10.1016\/j.tcs.2008.11.018","volume":"410","author":"Ng","year":"2009","journal-title":"Theor. Comput. Sci."},{"key":"R36","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1016\/j.ifacol.2021.08.080","volume":"54","author":"Nouinou","year":"2021","journal-title":"IFAC-PapersOnline"},{"key":"R37","doi-asserted-by":"crossref","unstructured":"Pan J. and Xu Y., Online integrated allocation of berths and quay cranes in container terminals with 1-lookahead, in 21st Annual International Computing & Combinatorics Conference, Aug 04\u201306, 2015. Springer International Publishing, LNCS 9198, Beijing, China (2015).","DOI":"10.1007\/978-3-319-21398-9_32"},{"key":"R38","doi-asserted-by":"crossref","first-page":"692","DOI":"10.1016\/j.orl.2005.11.004","volume":"34","author":"Park","year":"2006","journal-title":"Oper. Res. Lett."},{"key":"R39","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1007\/s10878-019-00381-6","volume":"38","author":"Pinson","year":"2019","journal-title":"J. Comb. Optim."},{"key":"R40","first-page":"457","volume":"2","author":"Senthilkumar","year":"2010","journal-title":"Intell. Inf. Manage."},{"key":"R41","doi-asserted-by":"crossref","first-page":"1060","DOI":"10.1007\/s10878-022-00882-x","volume":"44","author":"Zheng","year":"2022","journal-title":"J. Comb. Optim."},{"key":"R42","doi-asserted-by":"crossref","unstructured":"Zheng F.F., Chen Y.H., Liu M. and Xu Y.F., Semi-online scheduling on two identical parallel machines with initial-lookahead information. \n                        Asia-Pac. J. Oper. Res.\n                     (2023). DOI: 10.1142\/S0217595923500033.","DOI":"10.1051\/ro\/2024042"}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2024042\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,25]],"date-time":"2024-06-25T08:17:04Z","timestamp":1719303424000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2024042"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5]]},"references-count":42,"journal-issue":{"issue":"3"},"alternative-id":["ro220704"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2024042","relation":{},"ISSN":["0399-0559","2804-7303"],"issn-type":[{"type":"print","value":"0399-0559"},{"type":"electronic","value":"2804-7303"}],"subject":[],"published":{"date-parts":[[2024,5]]}}}