{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,24]],"date-time":"2026-01-24T16:41:59Z","timestamp":1769272919816,"version":"3.49.0"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2018,12,18]],"date-time":"2018-12-18T00:00:00Z","timestamp":1545091200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003407","name":"Ministero dell\u2019Istruzione, dell\u2019Universit\u00e0 e della Ricerca","doi-asserted-by":"crossref","award":["TESUN-83486178370409"],"award-info":[{"award-number":["TESUN-83486178370409"]}],"id":[{"id":"10.13039\/501100003407","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2020,4]]},"DOI":"10.1007\/s10951-018-0597-6","type":"journal-article","created":{"date-parts":[[2018,12,18]],"date-time":"2018-12-18T06:46:52Z","timestamp":1545115612000},"page":"163-176","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":34,"title":["The Longest Processing Time rule for identical parallel machines revisited"],"prefix":"10.1007","volume":"23","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2897-183X","authenticated-orcid":false,"given":"Federico","family":"Della Croce","sequence":"first","affiliation":[]},{"given":"Rosario","family":"Scatamacchia","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,12,18]]},"reference":[{"key":"597_CR1","unstructured":"Abolhassani, M., Chan, T. H., Chen, F., Esfandiari, H., Hajiaghayi, M., Hamid, M., et al. (2016). Beating ratio 0.5 for weighted oblivious matching problems. In P. Sankowski & C. Zaroliagis (Eds.), 24th Annual European symposium on algorithms (ESA 2016) (Vol. 57, pp. 3:1\u20133:18)."},{"key":"597_CR2","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, Y. (1998). Approximation schemes for scheduling on parallel machines. Journal of Scheduling, 1, 55\u201366.","journal-title":"Journal of Scheduling"},{"key":"597_CR3","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, D. (2015). A note on the coffman-sethi bound for LPT scheduling. Journal of Scheduling, 18, 325\u2013327.","journal-title":"Journal of Scheduling"},{"key":"597_CR4","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. Operation Research Letters, 14, 139\u2013142.","journal-title":"Operation Research Letters"},{"key":"597_CR5","volume-title":"Handbook of combinatorial optimization: Volume 1\u20133","author":"B Chen","year":"1999","unstructured":"Chen, B., Potts, C. N., & Woeginger, G. J. (1999). A review of machine scheduling: Complexity, algorithms and approximability. In D. Z. Du & P. M. Pardalos (Eds.), Handbook of combinatorial optimization: Volume 1\u20133. New York: Springer."},{"key":"597_CR6","unstructured":"Chimani, M., & Wiedera, T. (2016). An ILP-based proof system for the crossing number problem. In P. Sankowski & C. Zaroliagis (Eds.), 24th annual European symposium on algorithms (ESA 2016) (Vol. 57, pp. 29:1\u201329:13)."},{"key":"597_CR7","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\u201317.","journal-title":"SIAM Journal on Computing"},{"key":"597_CR8","first-page":"17","volume":"10","author":"EG Coffman Jr","year":"1976","unstructured":"Coffman, E. G, Jr., & Sethi, R. (1976). A generalized bound on LPT sequencing. Revue Francaise d\u2019Automatique Informatique, Recherche Operationelle Supplement, 10, 17\u201325.","journal-title":"Revue Francaise d\u2019Automatique Informatique, Recherche Operationelle Supplement"},{"key":"597_CR9","unstructured":"Della Croce, F., Pferschy, U., & Scatamacchia, R. (2018). Approximation results for the incremental knapsack problem. In Combinatorial algorithms: 28th international workshop, IWOCA 2017, Springer lecture notes in computer science (Vol. 10765, pp. 75\u201387)."},{"key":"597_CR10","first-page":"207","volume":"47","author":"G Dosa","year":"2004","unstructured":"Dosa, G. (2004). Graham example is the only tight one for P\u00a0 $$||$$ | | \u00a0Cmax (in Hungarian). Annales Univ Sci Budapest, 47, 207\u2013210.","journal-title":"Annales Univ Sci Budapest"},{"issue":"1","key":"597_CR11","first-page":"17","volume":"23","author":"G Dosa","year":"2006","unstructured":"Dosa, G., & Vizvari, A. (2006). The general algorithm lpt(k) for scheduling identical parallel machines. Alkamazott Matematikai Lapok, 23(1), 17\u201337. (in Hungarian).","journal-title":"Alkamazott Matematikai Lapok"},{"key":"597_CR12","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/BF02591687","volume":"37","author":"M Fischetti","year":"1987","unstructured":"Fischetti, M., & Martello, S. (1987). Worst-case analysis of the differencing method for the partition problem. Mathematical Programming, 37, 117\u2013120.","journal-title":"Mathematical Programming"},{"key":"597_CR13","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0305-0548(94)90053-1","volume":"21","author":"PM Fran\u00e7a","year":"1994","unstructured":"Fran\u00e7a, P. M., Gendreau, M., Laporte, G., & M\u00fcller, F. (1994). A composite heuristic for the identical parallel machine scheduling problem with minimum makespan objective. Computers & Operations Research, 21, 205\u2013210.","journal-title":"Computers & Operations Research"},{"key":"597_CR14","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1023\/B:JOCO.0000031420.05971.29","volume":"8","author":"A Frangioni","year":"2004","unstructured":"Frangioni, A., Necciari, E., & Scutell\u00e0, M. G. (2004). A multi-exchange neighborhood for minimum makespan parallel machine scheduling problems. Journal of Combinatorial Optimization, 8, 195\u2013220.","journal-title":"Journal of Combinatorial Optimization"},{"key":"597_CR15","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1287\/moor.12.2.241","volume":"12","author":"JBG Frenk","year":"1987","unstructured":"Frenk, J. B. G., & Rinnooy Kan, A. H. G. (1987). The asymptotic optimality of the LPT rule. Mathematics of Operations Research, 12, 241\u2013254.","journal-title":"Mathematics of Operations Research"},{"key":"597_CR16","volume-title":"Computers and intractability","author":"MR Garey","year":"1979","unstructured":"Garey, M. R., & Johnson, D. S. (1979). Computers and intractability. New York: W. H. Freeman."},{"key":"597_CR17","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 multiprocessors timing anomalies. SIAM Journal on Applied Mathematics, 17, 416\u2013429.","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"597_CR18","doi-asserted-by":"crossref","unstructured":"Graham, R. L., Lawler, E. L., Lenstra, J. K., & Rinnooy Kan, A. H. G. (1979). Optimization and approximation in deterministic sequencing and scheduling: a survey. In P. L. Hammer, E. L. Johnson, & B. H. Korte (Eds.), Discrete optimization II, annals of discrete mathematics (Vol. 5, pp. 287\u2013326).","DOI":"10.1016\/S0167-5060(08)70356-X"},{"issue":"1","key":"597_CR19","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1080\/09537280150203951","volume":"12","author":"JND Gupta","year":"2001","unstructured":"Gupta, J. N. D., & 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":"7","key":"597_CR20","doi-asserted-by":"publisher","first-page":"593","DOI":"10.1002\/1520-6750(200010)47:7<593::AID-NAV4>3.0.CO;2-H","volume":"47","author":"Y He","year":"2000","unstructured":"He, Y., Kellerer, H., & Kotov, V. (2000). Linear compound algorithms for the partitioning problem. Naval Research Logistics (NRL), 47(7), 593\u2013601.","journal-title":"Naval Research Logistics (NRL)"},{"key":"597_CR21","volume-title":"Approximation Algorithms for NP-hard Problems","year":"1997","unstructured":"Hochbaum, D. S. (Ed.). (1997). Approximation Algorithms for NP-hard Problems. Boston: PWS Publishing Co."},{"key":"597_CR22","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1145\/7531.7535","volume":"34","author":"DS Hochbaum","year":"1987","unstructured":"Hochbaum, D. S., & Shmoys, D. B. (1987). Using dual approximation algorithms for scheduling problems theoretical and practical results. Journal of the ACM, 34, 144\u2013162.","journal-title":"Journal of the ACM"},{"key":"597_CR23","doi-asserted-by":"crossref","unstructured":"Iori, M., & Martello, S. (2008). Scatter search algorithms for identical parallel machine scheduling problems. In Metaheuristics for scheduling in industrial and manufacturing applications (pp. 41\u201359).","DOI":"10.1007\/978-3-540-78985-7_2"},{"key":"597_CR24","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, 457\u2013485.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"597_CR25","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)."},{"key":"597_CR26","unstructured":"Karmarkar, N., & Karp, R. M. (1982). The differencing method of set partitioning. Technical Report UCB\/CSD 82\/113, University of California, Berkeley."},{"issue":"3","key":"597_CR27","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":"597_CR28","doi-asserted-by":"crossref","DOI":"10.1201\/9780203489802","volume-title":"Handbook of scheduling: Algorithms, models, and performance analysis","author":"J Leung","year":"2004","unstructured":"Leung, J., Kelly, L., & Anderson, J. H. (2004). Handbook of scheduling: Algorithms, models, and performance analysis. Cambridge: CRC Press, Inc."},{"issue":"1","key":"597_CR29","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/s10878-006-9010-z","volume":"13","author":"W Michiels","year":"2007","unstructured":"Michiels, W., Korst, J., Aarts, E., & van Leeuwen, J. (2007). Performance ratios of the Karmarkar\u2013Karp differencing method. Journal of Combinatorial Optimization, 13(1), 19\u201332.","journal-title":"Journal of Combinatorial Optimization"},{"issue":"1","key":"597_CR30","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1287\/opre.45.1.116","volume":"45","author":"P Mireault","year":"1997","unstructured":"Mireault, P., Orlin, J. B., & Vohra, R. V. (1997). A parametric worst-case analysis of the LPT heuristic for two uniform machines. Operations Research, 45(1), 116\u2013125.","journal-title":"Operations Research"},{"issue":"2","key":"597_CR31","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s10852-014-9262-z","volume":"14","author":"G Paletta","year":"2015","unstructured":"Paletta, G., & Ruiz-Torres, A. J. (2015). Partial solutions and multifit algorithm for multiprocessor scheduling. Journal of Mathematical Modelling and Algorithms in Operations Research, 14(2), 125\u2013143.","journal-title":"Journal of Mathematical Modelling and Algorithms in Operations Research"},{"key":"597_CR32","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-26580-3","volume-title":"Scheduling: Theory, algorithms, and systems","author":"ML Pinedo","year":"2016","unstructured":"Pinedo, M. L. (2016). Scheduling: Theory, algorithms, and systems (5th ed.). Berlin: Springer.","edition":"5"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-018-0597-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10951-018-0597-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-018-0597-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,8]],"date-time":"2022-09-08T17:23:19Z","timestamp":1662657799000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10951-018-0597-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,12,18]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,4]]}},"alternative-id":["597"],"URL":"https:\/\/doi.org\/10.1007\/s10951-018-0597-6","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"value":"1094-6136","type":"print"},{"value":"1099-1425","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,12,18]]},"assertion":[{"value":"18 December 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}