{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,4]],"date-time":"2025-06-04T08:40:11Z","timestamp":1749026411683,"version":"3.41.0"},"reference-count":29,"publisher":"EDP Sciences","issue":"3","license":[{"start":{"date-parts":[[2025,6,4]],"date-time":"2025-06-04T00:00:00Z","timestamp":1748995200000},"content-version":"vor","delay-in-days":34,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2025,4,8]]},"published-print":{"date-parts":[[2025,5]]},"abstract":"<jats:p>This paper compares three classical lower bounds for the Parallel Machines Scheduling Problem (PMSP). The first lower bound considered is the makespan of Jackson\u2019s Pseudo Preemptive Schedule (JPPS). The second is the preemptive bound, which is obtained by relaxing the non-preemption constraint, and the third is based on Energetic Reasoning (ER). To compare these three bounds, we first provide a rigorous mathematical characterization. Specifically, we introduce a mathematical definition of the ER-derived lower bound as the smallest value of the trial makespan that results in a successful ER feasibility test. This definition relies on the fundamental concepts of critical intervals and specific operations that we called crossing operations, for which we give some theoretical properties. We establish an <jats:italic>Energy theorem<\/jats:italic>, which provides an analytical formulation of the energetic lower bound. In an extension of the JPPS and ER lower bounds, we give an analytical formulation of the preemptive bound. From the analytical characterization of these three bounds, we attempt to analyze their relative performances. In particular, we find that the ER lower bound differs from JPPS because on some machines at least two operations must be scheduled for ER. The preemptive bound differs from JPPS because idle periods may be required in an optimal preemptive schedule. Interestingly, these three characterizations are quite similar, and so can provide insight into the ways in which the bounds differ. Our results can be directly extended to the cumulative scheduling problem, and we report some experimental experiments that compare these bounds and confirm the theoretical results stated above.<\/jats:p>","DOI":"10.1051\/ro\/2025043","type":"journal-article","created":{"date-parts":[[2025,4,9]],"date-time":"2025-04-09T08:03:13Z","timestamp":1744185793000},"page":"1475-1500","source":"Crossref","is-referenced-by-count":0,"title":["Comparison of three classical lower bounds for the Parallel Machines Scheduling Problem"],"prefix":"10.1051","volume":"59","author":[{"given":"Jacques","family":"Carlier","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eric","family":"Pinson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1528-4849","authenticated-orcid":false,"given":"Abderrahim","family":"Sahli","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Antoine","family":"Jouglet","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2025,6,4]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1023\/A:1018995000688","volume":"92","author":"Baptiste","year":"1999","journal-title":"Ann. Oper. Res."},{"key":"R2","doi-asserted-by":"crossref","unstructured":"Baptiste P., Le Pape C. and Nuijten W., Constraint-Based Scheduling: Applying Constraint Programming to Scheduling Problems. Vol. 39. Springer Science & Business Media (2001).","DOI":"10.1007\/978-1-4615-1479-4"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"Beldiceanu N. and Carlsson M., A new multi-resource cumulatives constraint with negative heights, in International Conference on Principles and Practice of Constraint Programming. Springer (2002) 63\u201379.","DOI":"10.1007\/3-540-46135-3_5"},{"key":"R4","unstructured":"Bonifas N., Geometric and dual approaches to cumulative scheduling. Theses, Universit\u00e9 Paris-Saclay (Dec. 2017)."},{"key":"R5","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1051\/ro\/197509V200831","volume":"9","author":"Carlier","year":"1975","journal-title":"Revue fran\u00e7aise d\u2019automatique, informatique, recherche op\u00e9rationnelle. Recherche op\u00e9rationnelle"},{"key":"R6","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1016\/S0377-2217(82)80007-6","volume":"11","author":"Carlier","year":"1982","journal-title":"Eur. J. Oper. Res."},{"key":"R7","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1016\/0377-2217(94)90379-4","volume":"78","author":"Carlier","year":"1994","journal-title":"Eur. J. Oper. Res."},{"key":"R8","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1023\/A:1018968332237","volume":"83","author":"Carlier","year":"1998","journal-title":"Ann. Oper. Res."},{"key":"R9","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1016\/j.dam.2003.09.009","volume":"145","author":"Carlier","year":"2004","journal-title":"Discrete Appl. Math."},{"key":"R10","doi-asserted-by":"crossref","first-page":"468","DOI":"10.1016\/j.ejor.2020.03.079","volume":"286","author":"Carlier","year":"2020","journal-title":"Eur. J. Oper. Res."},{"key":"R11","doi-asserted-by":"crossref","first-page":"3419","DOI":"10.1080\/00207543.2021.1923853","volume":"60","author":"Carlier","year":"2022","journal-title":"Int. J. Prod. Res."},{"key":"R12","doi-asserted-by":"crossref","first-page":"683","DOI":"10.1007\/s10479-023-05596-9","volume":"337","author":"Carlier","year":"2024","journal-title":"Ann. Oper. Res."},{"key":"R13","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1287\/ijoc.7.2.191","volume":"7","author":"Dell\u2019Amico","year":"1995","journal-title":"ORSA J. Comput."},{"key":"R14","doi-asserted-by":"crossref","unstructured":"Derrien A. and Petit T., A new characterization of relevant intervals for energetic reasoning, in International Conference on Principles and Practice of Constraint Programming, edited by O\u2019Sullivan B.. Springer, Springer International Publishing, Lyon, France (2014) 289\u2013297.","DOI":"10.1007\/978-3-319-10428-7_22"},{"key":"R15","first-page":"7","volume":"5","author":"Erschler","year":"1991","journal-title":"Revue d\u2019intelligence artificielle"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"Ford L.R. and Fulkerson D.R., Flows in networks, in Flows in Networks. Princeton University Press (1962).","DOI":"10.1515\/9781400875184"},{"key":"R17","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1002\/jos.103","volume":"5","author":"Gharbi","year":"2002","journal-title":"J. Scheduling"},{"key":"R18","doi-asserted-by":"crossref","first-page":"868","DOI":"10.1016\/j.cor.2005.05.012","volume":"34","author":"Gharbi","year":"2007","journal-title":"Comput. Oper. Res."},{"key":"R19","doi-asserted-by":"crossref","unstructured":"Graham R., Lawler E., Lenstra J. and Kan A., Optimization and approximation in deterministic sequencing and scheduling: a survey, in Discrete Optimization II. Vol. 5 of Annals of Discrete Mathematics, edited by Hammer P., Johnson E. and Korte B.. Elsevier (1979) 287\u2013326.","DOI":"10.1016\/S0167-5060(08)70356-X"},{"key":"R20","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/S0167-6377(02)00177-3","volume":"31","author":"Haouari","year":"2003","journal-title":"Oper. Res. Lett."},{"key":"R21","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1007\/s10951-008-0070-z","volume":"11","author":"Hidri","year":"2008","journal-title":"J. Scheduling"},{"key":"R22","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1002\/nav.3800210113","volume":"21","author":"Horn","year":"1974","journal-title":"Nav. Res. Logistics Q."},{"key":"R23","doi-asserted-by":"crossref","unstructured":"Labetoulle J., Lawler E.L., Lenstra J.K. and Kan A.R., Preemptive scheduling of uniform machines subject to release dates, in Progress in Combinatorial Optimization. Academic Press (1984) 245\u2013261.","DOI":"10.1016\/B978-0-12-566780-7.50020-9"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"Ouellet Y. and Quimper C.-G., A O(n log2 n) checker and O(n2 log n) filtering algorithm for the energetic reasoning, in International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research, edited by van Hoeve W.-J.. Delft, The Netherlands (2018) 477\u2013494.","DOI":"10.1007\/978-3-319-93031-2_34"},{"key":"R25","doi-asserted-by":"crossref","first-page":"326","DOI":"10.1016\/j.orl.2003.08.008","volume":"32","author":"Tercinet","year":"2004","journal-title":"Oper. Res. Lett."},{"key":"R26","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1007\/s10288-006-0017-1","volume":"4","author":"Tercinet","year":"2006","journal-title":"4OR"},{"key":"R27","doi-asserted-by":"crossref","unstructured":"Tesch A., A nearly exact propagation algorithm for energetic reasoning in o(n2 log n), in International Conference on Principles and Practice of Constraint Programming, edited by Rueher M.. Springer International Publishing (2016) 493\u2013519.","DOI":"10.1007\/978-3-319-44953-1_32"},{"key":"R28","doi-asserted-by":"crossref","unstructured":"Tesch A., Improving energetic propagations for cumulative scheduling, in International Conference on Principles and Practice of Constraint Programming, edited by Hooker J.. Springer, Springer International Publishing, Lille, France (2018) 629\u2013645.","DOI":"10.1007\/978-3-319-98334-9_41"},{"key":"R29","unstructured":"Vandevelde A., Minimizing the makespan in a multiprocessor flowshop. Master thesis, Eindhoven University of Technology (1994)."}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2025043\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,4]],"date-time":"2025-06-04T08:05:43Z","timestamp":1749024343000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2025043"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5]]},"references-count":29,"journal-issue":{"issue":"3"},"alternative-id":["ro240466"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2025043","relation":{},"ISSN":["0399-0559","2804-7303"],"issn-type":[{"type":"print","value":"0399-0559"},{"type":"electronic","value":"2804-7303"}],"subject":[],"published":{"date-parts":[[2025,5]]}}}