{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,24]],"date-time":"2026-01-24T17:58:46Z","timestamp":1769277526579,"version":"3.49.0"},"publisher-location":"Cham","reference-count":22,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030856649","type":"print"},{"value":"9783030856656","type":"electronic"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-85665-6_4","type":"book-chapter","created":{"date-parts":[[2021,8,28]],"date-time":"2021-08-28T03:06:52Z","timestamp":1630120012000},"page":"55-69","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Update on the Asymptotic Optimality of LPT"],"prefix":"10.1007","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":[[2021,8,25]]},"reference":[{"key":"4_CR1","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.: Comparison of heuristics for identical parallel machine scheduling. Adv. Mater. Res. 488\u2013489, 1708\u20131712 (2012)","journal-title":"Adv. Mater. Res."},{"key":"4_CR2","doi-asserted-by":"publisher","unstructured":"Benoit, A., Canon, L.C., Elghazi, R., H\u00e9am, P.C.: Artifact and instructions to generate experimental results for the Euro-Par 2021 paper: \u201cUpdate on the Asymptotic Optimality of LPT\u201d. https:\/\/doi.org\/10.6084\/m9.figshare.14755296","DOI":"10.6084\/m9.figshare.14755296"},{"key":"4_CR3","doi-asserted-by":"crossref","unstructured":"Benoit, A., Canon, L.C., Elghazi, R., H\u00e9am, P.C.: Update on the Asymptotic Optimality of LPT. Research report, Inria (2021). https:\/\/lccanon.github.io\/report_LPT_conv.pdf","DOI":"10.1007\/978-3-030-85665-6_4"},{"key":"4_CR4","series-title":"NATO Advanced Study Institutes Series (Series C \u2013 Mathematical and Physical Sciences)","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/978-94-009-7801-0_18","volume-title":"Deterministic and Stochastic Scheduling","author":"EG Coffman","year":"1982","unstructured":"Coffman, E.G., Frederickson, G.N., Lueker, G.S.: Probabilistic analysis of the LPT processor scheduling heuristic. In: Dempster, M.A.H., Lenstra, J.K., Rinnooy Kan, A.H.G. (eds.) Deterministic and Stochastic Scheduling. NATO Advanced Study Institutes Series (Series C \u2013 Mathematical and Physical Sciences), vol. 84, pp. 319\u2013331. Springer, Dordrecht (1982). https:\/\/doi.org\/10.1007\/978-94-009-7801-0_18"},{"key":"4_CR5","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.: An application of bin-packing to multi-processor scheduling. SIAM J. Comput. 7, 1\u201317 (1978)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"4_CR6","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1287\/mnsc.34.3.266","volume":"34","author":"EG Coffman, Jr.","year":"1988","unstructured":"Coffman, Jr., E.G., Lueker, G.S.: Asymptotic methods in the probabilistic analysis of sequencing and packing heuristics. Manage. Sci. 34(3), 266\u2013290 (1988)","journal-title":"Manage. Sci."},{"key":"4_CR7","unstructured":"Cooper, K.D., Schielke, P.J., Subramanian, D.: An Experimental Evaluation of List Scheduling. Technical report 98-326, Rice Computer Science (1998)"},{"issue":"2","key":"4_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.: The longest processing time rule for identical parallel machines revisited. J. Sched. 23(2), 163\u2013176 (2020). https:\/\/doi.org\/10.1007\/s10951-018-0597-6","journal-title":"J. Sched."},{"issue":"4","key":"4_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., et al.: Analysis of heuristics for stochastic programming results for hierarchical scheduling problems. Math. Oper. Res. 8(4), 525\u2013537 (1983)","journal-title":"Math. Oper. Res."},{"issue":"10","key":"4_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.: Experience with using the parallel workloads archive. J. Parallel Distrib. Comput. 74(10), 2967\u20132982 (2014)","journal-title":"J. Parallel Distrib. Comput."},{"key":"4_CR11","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511801655","volume-title":"Analytic Combinatorics","author":"P Flajolet","year":"2009","unstructured":"Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press, Cambridge (2009)"},{"issue":"2","key":"4_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.: A calculus for the random generation of labelled combinatorial structures. Theor. Comput. Sci. 132(2), 1\u201335 (1994)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"4_CR13","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.: The asymptotic optimality of the LPT rule. Math. Oper. Res. 12(2), 241\u2013254 (1987)","journal-title":"Math. Oper. Res."},{"issue":"2","key":"4_CR14","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.: The rate of convergence to optimality of the LPT rule. Discrete Appl. Math. 14(2), 187\u2013197 (1986)","journal-title":"Discrete Appl. Math."},{"key":"4_CR15","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.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discrete Math. 5, 287\u2013326 (1979)","journal-title":"Ann. Discrete Math."},{"issue":"2","key":"4_CR16","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1137\/0117039","volume":"17","author":"RL Graham","year":"1969","unstructured":"Graham, R.L.: Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math. 17(2), 416\u2013429 (1969)","journal-title":"SIAM J. Appl. Math."},{"issue":"1","key":"4_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.: A LISTFIT heuristic for minimizing Makespan on identical parallel machines. Prod. Plan. Control 12(1), 28\u201336 (2001)","journal-title":"Prod. Plan. Control"},{"issue":"2","key":"4_CR18","first-page":"151","volume":"11","author":"D Laha","year":"2017","unstructured":"Laha, D., Behera, D.K.: A comprehensive review and evaluation of LPT, MULTIFIT, COMBINE and LISTFIT for scheduling identical parallel machines. Int. J. Inf. Commun. Technol. (IJICT) 11(2), 151\u2013165 (2017)","journal-title":"Int. J. Inf. Commun. Technol. (IJICT)"},{"issue":"3","key":"4_CR19","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., David Massey, J.: Multiprocessor scheduling: combining LPT and MULTIFIT. Discrete Appl. Math. 20(3), 233\u2013242 (1988)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"4_CR20","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1287\/moor.9.1.142","volume":"9","author":"R Loulou","year":"1984","unstructured":"Loulou, R.: Tight bounds and probabilistic analysis of two heuristics for parallel processor scheduling. Math. Oper. Res. 9(1), 142\u2013150 (1984)","journal-title":"Math. Oper. Res."},{"key":"4_CR21","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.: Performance ratios for the Karmarkar-Karp differencing method. Electron. Notes Discrete Math. 13, 71\u201375 (2003)","journal-title":"Electron. Notes Discrete Math."},{"issue":"6","key":"4_CR22","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.: Parallel machine scheduling: a probabilistic analysis. Naval Res. Logist. (NRL) 43(6), 897\u2013916 (1996)","journal-title":"Naval Res. Logist. (NRL)"}],"container-title":["Lecture Notes in Computer Science","Euro-Par 2021: Parallel Processing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-85665-6_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,27]],"date-time":"2025-08-27T22:02:24Z","timestamp":1756332144000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-85665-6_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030856649","9783030856656"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-85665-6_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"25 August 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"Euro-Par","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"European Conference on Parallel Processing","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Lisbon","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Portugal","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"1 September 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3 September 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"europar2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/2021.euro-par.org\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"136","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"38","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"28% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"4","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"6","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"The conference was held virtually due to the COVID-19 pandemic.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}