{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T11:21:32Z","timestamp":1757589692883,"version":"3.37.3"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2022,6,28]],"date-time":"2022-06-28T00:00:00Z","timestamp":1656374400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,6,28]],"date-time":"2022-06-28T00:00:00Z","timestamp":1656374400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100002701","name":"Ministry of Education","doi-asserted-by":"publisher","award":["NRF-2019R1A2C1004789"],"award-info":[{"award-number":["NRF-2019R1A2C1004789"]}],"id":[{"id":"10.13039\/501100002701","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2022,12]]},"DOI":"10.1007\/s10951-022-00742-w","type":"journal-article","created":{"date-parts":[[2022,6,28]],"date-time":"2022-06-28T11:05:55Z","timestamp":1656414355000},"page":"721-740","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Tight approximation bounds for the LPT rule applied to identical parallel machines with small jobs"],"prefix":"10.1007","volume":"25","author":[{"given":"Myungho","family":"Lee","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3526-9865","authenticated-orcid":false,"given":"Kangbok","family":"Lee","sequence":"additional","affiliation":[]},{"given":"Michael","family":"Pinedo","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,6,28]]},"reference":[{"issue":"1","key":"742_CR1","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1002\/(SICI)1099-1425(199806)1:1<55::AID-JOS2>3.0.CO;2-J","volume":"1","author":"N Alon","year":"1998","unstructured":"Alon, N., Azar, Y., Woeginger, G. J., & Yadid, T. (1998). Approximation schemes for scheduling on parallel machines. Journal of Scheduling, 1(1), 55\u201366.","journal-title":"Journal of Scheduling"},{"issue":"3","key":"742_CR2","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/s10951-015-0419-z","volume":"18","author":"JD Blocher","year":"2015","unstructured":"Blocher, J. D., & Sevastyanov, S. (2015). A note on the Coffman-Sethi bound for LPT scheduling. Journal of Scheduling, 18(3), 325\u2013327.","journal-title":"Journal of Scheduling"},{"issue":"3","key":"742_CR3","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/0167-6377(93)90024-B","volume":"14","author":"B Chen","year":"1993","unstructured":"Chen, B. (1993). A note on LPT scheduling. Operations Research Letters, 14(3), 139\u2013142.","journal-title":"Operations Research Letters"},{"key":"742_CR4","doi-asserted-by":"crossref","unstructured":"Coffman, E. G., & Sethi, R. (1976). A generalized bound on LPT sequencing. In: Proceedings of the 1976 ACM SIGMETRICS conference on Computer performance modeling measurement and evaluation (pp. 306\u2013310).","DOI":"10.1145\/800200.806205"},{"issue":"1","key":"742_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/0207001","volume":"7","author":"EG Coffman Jr","year":"1978","unstructured":"Coffman, E. G., Jr., Garey, M. R., & Johnson, D. S. (1978). An application of bin-packing to multiprocessor scheduling. SIAM Journal on Computing, 7(1), 1\u201317.","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"742_CR6","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/s10951-018-0597-6","volume":"23","author":"F Della Croce","year":"2020","unstructured":"Della Croce, F., & Scatamacchia, R. (2020). The longest processing time rule for identical parallel machines revisited. Journal of Scheduling, 23(2), 163\u2013176.","journal-title":"Journal of Scheduling"},{"issue":"2","key":"742_CR7","doi-asserted-by":"publisher","first-page":"608","DOI":"10.1007\/s10878-019-00399-w","volume":"38","author":"F Della Croce","year":"2019","unstructured":"Della Croce, F., Scatamacchia, R., & T\u2019kindt, V. (2019). A tight linear time $$\\frac{13}{12}$$-approximation algorithm for the $$P2||C_{\\max }$$ problem. Journal of Combinatorial Optimization, 38(2), 608\u2013617.","journal-title":"Journal of Combinatorial Optimization"},{"issue":"4","key":"742_CR8","doi-asserted-by":"publisher","first-page":"797","DOI":"10.1287\/opre.41.4.797","volume":"41","author":"BT Eck","year":"1993","unstructured":"Eck, B. T., & Pinedo, M. (1993). On the minimization of the makespan subject to flowtime optimality. Operations Research, 41(4), 797\u2013801.","journal-title":"Operations Research"},{"issue":"2","key":"742_CR9","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1287\/moor.12.2.241","volume":"12","author":"J Frenk","year":"1987","unstructured":"Frenk, J., & Rinnooy Kan, A. (1987). The asymptotic optimality of the LPT rule. Mathematics of Operations Research, 12(2), 241\u2013254.","journal-title":"Mathematics of Operations Research"},{"issue":"3","key":"742_CR10","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1145\/322077.322090","volume":"25","author":"MR Garey","year":"1978","unstructured":"Garey, M. R., & Johnson, D. S. (1978). \u201cStrong\u2019\u2019 NP-completeness results: motivation, examples, and implications. Journal of the ACM, 25(3), 499\u2013508.","journal-title":"Journal of the ACM"},{"issue":"2","key":"742_CR11","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1137\/0117039","volume":"17","author":"RL Graham","year":"1969","unstructured":"Graham, R. L. (1969). Bounds on multiprocessing timing anomalies. SIAM Journal on Applied Mathematics, 17(2), 416\u2013429.","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"742_CR12","doi-asserted-by":"crossref","unstructured":"Graham, R. L., Lawler, E. L., Lenstra, J. K., & Kan, A. R. (1979). Optimization and approximation in deterministic sequencing and scheduling: a survey. In Annals of Discrete Mathematics (Vol.\u00a05, pp. 287\u2013326). Elsevier.","DOI":"10.1016\/S0167-5060(08)70356-X"},{"issue":"1","key":"742_CR13","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1080\/09537280150203951","volume":"12","author":"JN Gupta","year":"2001","unstructured":"Gupta, J. N., & Ruiz-Torres, A. J. (2001). A LISTFIT heuristic for minimizing makespan on identical parallel machines. Production Planning & Control, 12(1), 28\u201336.","journal-title":"Production Planning & Control"},{"issue":"2","key":"742_CR14","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1145\/322003.322011","volume":"24","author":"OH Ibarra","year":"1977","unstructured":"Ibarra, O. H., & Kim, C. E. (1977). Heuristic algorithms for scheduling independent tasks on nonidentical processors. Journal of the ACM (JACM), 24(2), 280\u2013289.","journal-title":"Journal of the ACM (JACM)"},{"issue":"2","key":"742_CR15","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1137\/090749451","volume":"24","author":"K Jansen","year":"2010","unstructured":"Jansen, K. (2010). An EPTAS for scheduling jobs on uniform processors: using an MILP relaxation with a constant number of integral variables. SIAM Journal on Discrete Mathematics, 24(2), 457\u2013485.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"742_CR16","unstructured":"Jansen, K., Klein, K. M., & Verschae, J. (2017). Improved efficient approximation schemes for scheduling jobs on identical and uniform machines. In: Proceedings of the 13th workshop on models and algorithms for planning and scheduling problems (MAPSP 2017) (pp. 77\u201379)."},{"issue":"3","key":"742_CR17","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/0166-218X(88)90079-0","volume":"20","author":"CY Lee","year":"1988","unstructured":"Lee, C. Y., & Massey, J. D. (1988). Multiprocessor scheduling: combining LPT and MULTIFIT. Discrete Applied Mathematics, 20(3), 233\u2013242.","journal-title":"Discrete Applied Mathematics"},{"key":"742_CR18","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511921735","volume-title":"The Design of Approximation Algorithms","author":"DP Williamson","year":"2011","unstructured":"Williamson, D. P., & Shmoys, D. B. (2011). The Design of Approximation Algorithms (1st ed.). Cambridge: Cambridge University Press.","edition":"1"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-022-00742-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10951-022-00742-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-022-00742-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,31]],"date-time":"2022-10-31T18:30:05Z","timestamp":1667241005000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10951-022-00742-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,28]]},"references-count":18,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["742"],"URL":"https:\/\/doi.org\/10.1007\/s10951-022-00742-w","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"type":"print","value":"1094-6136"},{"type":"electronic","value":"1099-1425"}],"subject":[],"published":{"date-parts":[[2022,6,28]]},"assertion":[{"value":"13 May 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 June 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}