{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T05:38:19Z","timestamp":1776749899617,"version":"3.51.2"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,1,23]],"date-time":"2026-01-23T00:00:00Z","timestamp":1769126400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,23]],"date-time":"2026-01-23T00:00:00Z","timestamp":1769126400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"name":"EUR-EIPHI Graduate School"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2026,4]]},"DOI":"10.1007\/s10951-025-00862-z","type":"journal-article","created":{"date-parts":[[2026,1,23]],"date-time":"2026-01-23T00:57:01Z","timestamp":1769129821000},"page":"125-141","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["An update on the asymptotic optimality of the longest processing time heuristic"],"prefix":"10.1007","volume":"29","author":[{"given":"Anne","family":"Benoit","sequence":"first","affiliation":[]},{"given":"Louis-Claude","family":"Canon","sequence":"additional","affiliation":[]},{"given":"Redouane","family":"Elghazi","sequence":"additional","affiliation":[]},{"given":"Pierre-Cyrille","family":"H\u00e9am","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2026,1,23]]},"reference":[{"key":"862_CR1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-58412-1","volume-title":"Complexity and approximation: Combinatorial optimization problems and their approximability properties","author":"G Ausiello","year":"1999","unstructured":"Ausiello, G., Protasi, M., Marchetti-Spaccamela, A., Gambosi, G., Crescenzi, P., & Kann, V. (1999). Complexity and approximation: Combinatorial optimization problems and their approximability properties (1st ed.). Berlin: Springer.","edition":"1"},{"key":"862_CR2","doi-asserted-by":"publisher","first-page":"1708","DOI":"10.4028\/www.scientific.net\/AMR.488-489.1708","volume":"488\u2013489","author":"DK Behera","year":"2012","unstructured":"Behera, D. K., & Laha, D. (2012). Comparison of heuristics for identical parallel machine scheduling. Advanced Materials Research, 488\u2013489, 1708\u20131712.","journal-title":"Advanced Materials Research"},{"key":"862_CR3","doi-asserted-by":"crossref","unstructured":"Benoit, A., Canon, L.-C., Elghazi, R., & H\u00e9am, P.-C. (2021). Update on the asymptotic optimality of LPT. In Proceedings of EuroPar\u201921.","DOI":"10.1007\/978-3-030-85665-6_4"},{"key":"862_CR4","doi-asserted-by":"crossref","unstructured":"Berger, V. W., & Zhou, Y. (2014). Kolmogorov\u2013Smirnov Test: Overview. Wiley StatsRef: Statistics reference online.","DOI":"10.1002\/9781118445112.stat06558"},{"key":"862_CR5","doi-asserted-by":"crossref","unstructured":"Coffman, E. G., Frederickson, G. N., & Lueker, G. S. (1982). Probabilistic analysis of the LPT processor scheduling heuristic. In Deterministic and stochastic scheduling (pp. 319\u2013331). Springer.","DOI":"10.1007\/978-94-009-7801-0_18"},{"key":"862_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/0207001","volume":"7","author":"EG Coffman","year":"1978","unstructured":"Coffman, E. G., Garey, M. R., & Johnson, D. S. (1978). An application of bin-packing to multiprocessor scheduling. SIAM Journal of Computing, 7, 1\u201317.","journal-title":"SIAM Journal of Computing"},{"issue":"3","key":"862_CR7","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1287\/mnsc.34.3.266","volume":"34","author":"EG Coffman Jr","year":"1988","unstructured":"Coffman, E. G., Jr., Lueker, G. S., & Rinnooy Kan, A. H. G. (1988). Asymptotic methods in the probabilistic analysis of sequencing and packing heuristics. Management Science, 34(3), 266\u2013290.","journal-title":"Management Science"},{"issue":"2","key":"862_CR8","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":"4","key":"862_CR9","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1287\/moor.8.4.525","volume":"8","author":"MAH Dempster","year":"1983","unstructured":"Dempster, M. A. H., Fisher, M. L., Jansen, L., Lageweg, B. J., Lenstra, J. K., & Rinnooy Kan, A. H. G. (1983). Analysis of heuristics for stochastic programming: Results for hierarchical scheduling problems. Mathematics of Operations Research, 8(4), 525\u2013537.","journal-title":"Mathematics of Operations Research"},{"issue":"10","key":"862_CR10","doi-asserted-by":"publisher","first-page":"2967","DOI":"10.1016\/j.jpdc.2014.06.013","volume":"74","author":"DG Feitelson","year":"2014","unstructured":"Feitelson, D. G., Tsafrir, D., & Krakov, D. (2014). Experience with using the parallel workloads archive. Journal of Parallel and Distributed Computing, 74(10), 2967\u20132982.","journal-title":"Journal of Parallel and Distributed Computing"},{"key":"862_CR11","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511801655","volume-title":"Analytic combinatorics","author":"P Flajolet","year":"2009","unstructured":"Flajolet, P., & Sedgewick, R. (2009). Analytic combinatorics. Cambridge University Press."},{"issue":"2","key":"862_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(94)90226-7","volume":"132","author":"P Flajolet","year":"1994","unstructured":"Flajolet, P., Zimmermann, P., & Cutsem, B. V. (1994). A calculus for the random generation of labelled combinatorial structures. Theoretical Computer Science, 132(2), 1\u201335.","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"862_CR13","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/0166-218X(86)90060-0","volume":"14","author":"JBG Frenk","year":"1986","unstructured":"Frenk, J. B. G., & Rinnooy Kan, A. H. G. (1986). The rate of convergence to optimality of the LPT rule. Discrete Applied Mathematics, 14(2), 187\u2013197.","journal-title":"Discrete Applied Mathematics"},{"issue":"2","key":"862_CR14","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(2), 241\u2013254.","journal-title":"Mathematics of Operations Research"},{"issue":"2","key":"862_CR15","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":"862_CR16","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","volume":"5","author":"RL Graham","year":"1979","unstructured":"Graham, R. L., Lawler, E. L., Lenstra, J. K., & Kan, A. H. G. R. (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 5, 287\u2013326.","journal-title":"Annals of Discrete Mathematics"},{"issue":"1","key":"862_CR17","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"},{"key":"862_CR18","unstructured":"Karmarkar, N., & Karp, R. M. (1982). The differencing method of set partitioning. Computer Science Division (EECS). University of California Berkeley."},{"key":"862_CR19","doi-asserted-by":"crossref","unstructured":"Laha, D., & Behera, D. K. (2017). A comprehensive review and evaluation of LPT, MULTIFIT, COMBINE and LISTFIT for scheduling identical parallel machines. International Journal of Information and Communication Technology (IJICT) 11(2).","DOI":"10.1504\/IJICT.2017.086246"},{"issue":"3","key":"862_CR20","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/0166-218X(88)90079-0","volume":"20","author":"C-Y Lee","year":"1988","unstructured":"Lee, C.-Y., & David Massey, J. (1988). Multiprocessor scheduling: Combining LPT and MULTIFIT. Discrete Applied Mathematics, 20(3), 233\u2013242.","journal-title":"Discrete Applied Mathematics"},{"issue":"1","key":"862_CR21","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1287\/moor.9.1.142","volume":"9","author":"R Loulou","year":"1984","unstructured":"Loulou, R. (1984). Tight bounds and probabilistic analysis of two heuristics for parallel processor scheduling. Mathematics of Operations Research, 9(1), 142\u2013150.","journal-title":"Mathematics of Operations Research"},{"key":"862_CR22","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/S1571-0653(04)00442-1","volume":"13","author":"W Michiels","year":"2003","unstructured":"Michiels, W., Korst, J., Aarts, E., & van Leeuwen, J. (2003). Performance ratios for the Karmarkar\u2013Karp differencing method. Electronic Notes in Discrete Mathematics, 13, 71\u201375.","journal-title":"Electronic Notes in Discrete Mathematics"},{"issue":"6","key":"862_CR23","doi-asserted-by":"publisher","first-page":"897","DOI":"10.1002\/(SICI)1520-6750(199609)43:6<897::AID-NAV7>3.0.CO;2-#","volume":"43","author":"N Piersma","year":"1996","unstructured":"Piersma, N., & Romeijn, H. E. (1996). Parallel machine scheduling: A probabilistic analysis. Naval Research Logistics (NRL), 43(6), 897\u2013916.","journal-title":"Naval Research Logistics (NRL)"},{"key":"862_CR24","doi-asserted-by":"crossref","unstructured":"Yakir, B. (1996). The differencing algorithm LDM for partitioning: A proof of a conjecture of Karmarkar and Karp. Mathematics of Operations Research, 21(1), 85\u201399.","DOI":"10.1287\/moor.21.1.85"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-025-00862-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10951-025-00862-z","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-025-00862-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T04:51:36Z","timestamp":1776747096000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10951-025-00862-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1,23]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,4]]}},"alternative-id":["862"],"URL":"https:\/\/doi.org\/10.1007\/s10951-025-00862-z","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"value":"1094-6136","type":"print"},{"value":"1099-1425","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,1,23]]},"assertion":[{"value":"18 March 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 October 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 January 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}