{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:18:43Z","timestamp":1759637923961,"version":"3.41.2"},"reference-count":25,"publisher":"World Scientific Pub Co Pte Ltd","issue":"05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Asia Pac. J. Oper. Res."],"published-print":{"date-parts":[[2021,10]]},"abstract":"<jats:p> This paper investigates a classic online scheduling problem with learning effect on a single machine. Specifically, a number of independent jobs that arrive online over time will be processed on a single machine and learning effect implies that the real processing time of job [Formula: see text] is a non-increasing function of its position [Formula: see text], i.e., [Formula: see text], where [Formula: see text] is the basic processing time of job [Formula: see text] and [Formula: see text] is the learning index. Our goal is to minimize the total completion time of all jobs. For the problem, we develop a deterministic polynomial time online algorithm called Delayed Shortest Basic Processing Time (DSBPT) and state that it is an online algorithm with a competitive ratio of 2, which matches the lower bound of the online scheduling problem we focus on. <\/jats:p>","DOI":"10.1142\/s0217595921400029","type":"journal-article","created":{"date-parts":[[2021,1,27]],"date-time":"2021-01-27T03:59:21Z","timestamp":1611719961000},"source":"Crossref","is-referenced-by-count":1,"title":["An Optimal Online Algorithm for Scheduling with Learning Consideration"],"prefix":"10.1142","volume":"38","author":[{"given":"Ran","family":"Ma","sequence":"first","affiliation":[{"name":"School of Management Engineering, Qingdao University of Technology, Qingdao 266525, P. R. China"},{"name":"University Research Center for Smart City, Construction and Management of Shandong, Province, Qingdao 266525, P. R. China"}]},{"given":"Wenwen","family":"Han","sequence":"additional","affiliation":[{"name":"School of Management Engineering, Qingdao University of Technology, Qingdao 266525, P. R. China"},{"name":"University Research Center for Smart City, Construction and Management of Shandong, Province, Qingdao 266525, P. R. China"}]},{"given":"Cuixia","family":"Miao","sequence":"additional","affiliation":[{"name":"School of Mathematical Sciences, Qufu Normal University, Qufu 273165, P. R. China"}]},{"given":"Juan","family":"Zou","sequence":"additional","affiliation":[{"name":"School of Mathematical Sciences, Qufu Normal University, Qufu 273165, P. R. China"}]}],"member":"219","published-online":{"date-parts":[[2021,5,26]]},"reference":[{"key":"S0217595921400029BIB001","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(98)00246-X"},{"key":"S0217595921400029BIB002","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2007.05.040"},{"key":"S0217595921400029BIB003","doi-asserted-by":"publisher","DOI":"10.1007\/s11590-012-0574-5"},{"key":"S0217595921400029BIB004","doi-asserted-by":"publisher","DOI":"10.1016\/j.ijpe.2012.03.027"},{"key":"S0217595921400029BIB005","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2008.02.002"},{"key":"S0217595921400029BIB006","doi-asserted-by":"publisher","DOI":"10.3934\/jimo.2017085"},{"key":"S0217595921400029BIB007","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-017-0536-7"},{"key":"S0217595921400029BIB008","doi-asserted-by":"publisher","DOI":"10.1007\/s10951-008-0064-x"},{"key":"S0217595921400029BIB009","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-61310-2_30"},{"key":"S0217595921400029BIB010","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2007.04.007"},{"key":"S0217595921400029BIB011","doi-asserted-by":"publisher","DOI":"10.1142\/S0217595915500335"},{"key":"S0217595921400029BIB012","doi-asserted-by":"publisher","DOI":"10.1016\/j.amc.2015.10.058"},{"key":"S0217595921400029BIB013","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-016-0083-z"},{"key":"S0217595921400029BIB014","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2020.08.009"},{"key":"S0217595921400029BIB015","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(02)00358-2"},{"key":"S0217595921400029BIB016","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2012.04.037"},{"key":"S0217595921400029BIB017","doi-asserted-by":"publisher","DOI":"10.1142\/S021759590700122X"},{"key":"S0217595921400029BIB018","doi-asserted-by":"publisher","DOI":"10.1111\/itor.12323"},{"key":"S0217595921400029BIB019","doi-asserted-by":"publisher","DOI":"10.3934\/jimo.2016060"},{"key":"S0217595921400029BIB020","doi-asserted-by":"publisher","DOI":"10.1057\/palgrave.jors.2601856"},{"key":"S0217595921400029BIB021","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2013.07.001"},{"key":"S0217595921400029BIB022","doi-asserted-by":"publisher","DOI":"10.1016\/j.apm.2007.03.001"},{"key":"S0217595921400029BIB023","doi-asserted-by":"publisher","DOI":"10.1007\/s00521-015-1910-3"},{"key":"S0217595921400029BIB024","doi-asserted-by":"publisher","DOI":"10.1057\/jors.2012.46"},{"key":"S0217595921400029BIB025","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2016.04.021"}],"container-title":["Asia-Pacific Journal of Operational Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0217595921400029","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,11]],"date-time":"2021-10-11T08:58:52Z","timestamp":1633942732000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0217595921400029"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,26]]},"references-count":25,"journal-issue":{"issue":"05","published-print":{"date-parts":[[2021,10]]}},"alternative-id":["10.1142\/S0217595921400029"],"URL":"https:\/\/doi.org\/10.1142\/s0217595921400029","relation":{},"ISSN":["0217-5959","1793-7019"],"issn-type":[{"type":"print","value":"0217-5959"},{"type":"electronic","value":"1793-7019"}],"subject":[],"published":{"date-parts":[[2021,5,26]]},"article-number":"2140002"}}