{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,31]],"date-time":"2026-01-31T05:43:57Z","timestamp":1769838237466,"version":"3.49.0"},"reference-count":13,"publisher":"World Scientific Pub Co Pte Lt","issue":"05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Asia Pac. J. Oper. Res."],"published-print":{"date-parts":[[2017,10]]},"abstract":"<jats:p> In this paper, we consider the online single machine scheduling problem to minimize the maximum starting time of the jobs. For the non-preemptive model, we show that there is no determined or randomized online algorithm with a bounded competitive ratio. For the preemption-resume model, we show that the well-known SRPT rule yields an optimal schedule. For the preemption-restart model, we show that any determined online algorithm has a competitive ratio of at least 2 and present an online algorithm with the best-possible competitive ratio of 2. <\/jats:p>","DOI":"10.1142\/s0217595917500221","type":"journal-article","created":{"date-parts":[[2017,9,5]],"date-time":"2017-09-05T01:26:06Z","timestamp":1504574766000},"page":"1750022","source":"Crossref","is-referenced-by-count":3,"title":["Online Single Machine Scheduling to Minimize the Maximum Starting Time"],"prefix":"10.1142","volume":"34","author":[{"given":"Lingfa","family":"Lu","sequence":"first","affiliation":[{"name":"School of Mathematics and Statistics, Zhengzhou University, Zhengzhou, Henan 450001, P. R. China"}]},{"given":"Liqi","family":"Zhang","sequence":"additional","affiliation":[{"name":"College of Information and Management Science, Henan Agricultural University, Zhengzhou, Henan 450003, P. R. China"}]}],"member":"219","published-online":{"date-parts":[[2017,10,9]]},"reference":[{"key":"S0217595917500221BIB001","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1040.0092"},{"key":"S0217595917500221BIB002","volume-title":"Introduction to Sequencing and Scheduling.","author":"Baker KR","year":"1974"},{"key":"S0217595917500221BIB003","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2004.09.001"},{"key":"S0217595917500221BIB004","doi-asserted-by":"publisher","DOI":"10.1007\/s00236-004-0145-z"},{"key":"S0217595917500221BIB005","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1966.tb01709.x"},{"key":"S0217595917500221BIB006","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480196296823"},{"key":"S0217595917500221BIB007","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(00)00061-4"},{"key":"S0217595917500221BIB008","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.19.5.544"},{"key":"S0217595917500221BIB009","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585872"},{"key":"S0217595917500221BIB010","doi-asserted-by":"publisher","DOI":"10.1002\/1099-1425(200011\/12)3:6<333::AID-JOS53>3.0.CO;2-8"},{"key":"S0217595917500221BIB011","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.10.001"},{"key":"S0217595917500221BIB013","doi-asserted-by":"publisher","DOI":"10.1007\/s10951-010-0172-2"},{"key":"S0217595917500221BIB014","doi-asserted-by":"publisher","DOI":"10.1002\/nav.5"}],"container-title":["Asia-Pacific Journal of Operational Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0217595917500221","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T01:40:30Z","timestamp":1565142030000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0217595917500221"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,10]]},"references-count":13,"journal-issue":{"issue":"05","published-online":{"date-parts":[[2017,10,9]]},"published-print":{"date-parts":[[2017,10]]}},"alternative-id":["10.1142\/S0217595917500221"],"URL":"https:\/\/doi.org\/10.1142\/s0217595917500221","relation":{},"ISSN":["0217-5959","1793-7019"],"issn-type":[{"value":"0217-5959","type":"print"},{"value":"1793-7019","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,10]]}}}