{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,13]],"date-time":"2025-12-13T07:18:13Z","timestamp":1765610293457,"version":"3.37.3"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,10,18]],"date-time":"2022-10-18T00:00:00Z","timestamp":1666051200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,10,18]],"date-time":"2022-10-18T00:00:00Z","timestamp":1666051200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2023,4]]},"DOI":"10.1007\/s10951-022-00759-1","type":"journal-article","created":{"date-parts":[[2022,10,18]],"date-time":"2022-10-18T12:02:37Z","timestamp":1666094557000},"page":"137-145","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Moderate worst-case complexity bounds for the permutation flowshop scheduling problem using Inclusion\u2013Exclusion"],"prefix":"10.1007","volume":"26","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4582-3441","authenticated-orcid":false,"given":"Olivier","family":"Ploton","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7440-2980","authenticated-orcid":false,"given":"Vincent","family":"T\u2019kindt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,10,18]]},"reference":[{"issue":"2","key":"759_CR1","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1080\/05695557008974749","volume":"2","author":"S Ashour","year":"1970","unstructured":"Ashour, S. (1970). A branch-and-bound algorithm for flow shop scheduling problems. American Institute of Industrial Engineers Transactions, 2(2), 172\u2013176. https:\/\/doi.org\/10.1080\/05695557008974749.","journal-title":"American Institute of Industrial Engineers Transactions"},{"key":"759_CR2","doi-asserted-by":"publisher","unstructured":"Bax, E. (1994). Recurrence-based heuristics for the Hamiltonian path inclusion and exclusion algorithm. Tech. rep., California Institute of Technology, USA. https:\/\/doi.org\/10.7907\/Z9CC0XQ0","DOI":"10.7907\/Z9CC0XQ0"},{"key":"759_CR3","doi-asserted-by":"publisher","unstructured":"Bjorklund, A., & Husfeldt, T. (2006). Inclusion\u2013exclusion algorithms for counting set partitions. In Proceedings\u2014Annual IEEE Symposium on Foundations of Computer Science, FOCS (pp. 575\u2013582). https:\/\/doi.org\/10.1109\/FOCS.2006.41","DOI":"10.1109\/FOCS.2006.41"},{"issue":"1","key":"759_CR4","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1016\/0377-2217(91)90148-O","volume":"51","author":"SA Brah","year":"1991","unstructured":"Brah, S. A., & Hunsucker, J. L. (1991). Branch and bound algorithm for the flow shop with multiple processors. European Journal of Operational Research, 51(1), 88\u201399. https:\/\/doi.org\/10.1016\/0377-2217(91)90148-O.","journal-title":"European Journal of Operational Research"},{"key":"759_CR5","doi-asserted-by":"publisher","unstructured":"Brown, A. P. G., & Lomnicki, Z. A. (1966). Some applications of the \u201cbranch-and-bound\u201d algorithm to the machine scheduling problem. Journal of the Operational Research Society, 17(2), 173\u2013186. https:\/\/doi.org\/10.1057\/jors.1966.25","DOI":"10.1057\/jors.1966.25"},{"issue":"2","key":"759_CR6","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1016\/0377-2217(95)00352-5","volume":"90","author":"J Carlier","year":"1996","unstructured":"Carlier, J., & Reba\u00ef, I. (1996). Two branch and bound algorithms for the permutation flow shop problem. European Journal of Operational Research, 90(2), 238\u2013251. https:\/\/doi.org\/10.1016\/0377-2217(95)00352-5.","journal-title":"European Journal of Operational Research"},{"issue":"3","key":"759_CR7","doi-asserted-by":"publisher","first-page":"578","DOI":"10.1016\/S0377-2217(96)00083-5","volume":"96","author":"J Cheng","year":"1997","unstructured":"Cheng, J., Kise, H., & Matsumoto, H. (1997). A branch-and-bound algorithm with fuzzy inference for a permutation flowshop scheduling problem. European Journal of Operational Research, 96(3), 578\u2013590. https:\/\/doi.org\/10.1016\/S0377-2217(96)00083-5.","journal-title":"European Journal of Operational Research"},{"key":"759_CR8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16533-7","volume-title":"Exact Exponential Algorithms. Texts in Theoretical Computer Science","author":"F Fomin","year":"2010","unstructured":"Fomin, F., & Kratsch, D. (2010). Exact Exponential Algorithms. Texts in Theoretical Computer Science. Cham: Springer."},{"issue":"12","key":"759_CR9","doi-asserted-by":"publisher","first-page":"1243","DOI":"10.1057\/palgrave.jors.2601784","volume":"55","author":"JM Framinan","year":"2004","unstructured":"Framinan, J. M., Gupta, J. N. D., & Leisten, R. (2004). A review and classification of heuristics for permutation flow-shop scheduling with makespan objective. Journal of the Operational Research Society, 55(12), 1243\u20131255. https:\/\/doi.org\/10.1057\/palgrave.jors.2601784.","journal-title":"Journal of the Operational Research Society"},{"key":"759_CR10","doi-asserted-by":"publisher","unstructured":"Garey, M., Johnson, D., & Sethi, R. (1976). The complexity of flowshop and jobshop scheduling. Mathematics of Operations Research, 1(2), 117\u2013129. https:\/\/doi.org\/10.1287\/moor.1.2.117.","DOI":"10.1287\/moor.1.2.117"},{"issue":"3","key":"759_CR11","doi-asserted-by":"publisher","first-page":"814","DOI":"10.1016\/j.ejor.2020.01.039","volume":"284","author":"J Gmys","year":"2020","unstructured":"Gmys, J., Mezmaz, M., Melab, N., & Tuyttens, D. (2020). A computationally efficient Branch-and-Bound algorithm for the permutation flow-shop scheduling problem. European Journal of Operational Research, 284(3), 814\u2013833. https:\/\/doi.org\/10.1016\/j.ejor.2020.01.039.","journal-title":"European Journal of Operational Research"},{"issue":"2","key":"759_CR12","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., & Rinnooy Kan, A. H. G. (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 5(2), 287\u2013326. https:\/\/doi.org\/10.1016\/S0167-5060(08)70356-X.","journal-title":"Annals of Discrete Mathematics"},{"issue":"3","key":"759_CR13","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1287\/opre.13.3.400","volume":"13","author":"E Ignall","year":"1965","unstructured":"Ignall, E., & Schrage, L. (1965). Application of the branch and bound technique to some flow-shop scheduling problems. Operations Research, 13(3), 400\u2013412. https:\/\/doi.org\/10.1287\/opre.13.3.400.","journal-title":"Operations Research"},{"key":"759_CR14","doi-asserted-by":"publisher","unstructured":"Impagliazzo, R., & Paturi, R. (1999). Complexity of k-sat. In Proceedings. Fourteenth Annual IEEE Conference on Computational Complexity (Formerly: Structure in Complexity Theory Conference) (Cat. No. 99CB36317) (pp. 237\u2013240). https:\/\/doi.org\/10.1109\/CCC.1999.766282","DOI":"10.1109\/CCC.1999.766282"},{"key":"759_CR15","doi-asserted-by":"publisher","unstructured":"Jansen, K., Land, F., & Land, K. (2013). Bounding the running time of algorithms for scheduling and packing problems. In Algorithms and Data Structures\u201413th International Symposium, Lecture Notes in Computer Science (Vol. 8037, pp. 439\u2013450). Springer. https:\/\/doi.org\/10.1007\/978-3-642-40104-6_38","DOI":"10.1007\/978-3-642-40104-6_38"},{"issue":"1","key":"759_CR16","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1002\/nav.3800010110","volume":"1","author":"SM Johnson","year":"1954","unstructured":"Johnson, S. M. (1954). Optimal two- and three-stage production schedules with setup times included. Naval Research Logistics Quarterly, 1(1), 61\u201368. https:\/\/doi.org\/10.1002\/nav.3800010110.","journal-title":"Naval Research Logistics Quarterly"},{"key":"759_CR17","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0167-6377(82)90044-X","volume":"1","author":"R Karp","year":"1982","unstructured":"Karp, R. (1982). Dynamic programming meets the principle of inclusion and exclusion. Operations Research Letters, 1, 49\u201351. https:\/\/doi.org\/10.1016\/0167-6377(82)90044-X.","journal-title":"Operations Research Letters"},{"key":"759_CR18","doi-asserted-by":"publisher","unstructured":"Kohn, S., Gottlieb, A., & Kohn, M. (1977). A generating function approach to the traveling salesman problem. In Proceedings of the 1977 Annual Conference, ACM \u201977 (pp. 294\u2013300). New York: Association for Computing Machinery. https:\/\/doi.org\/10.1145\/800179.810218","DOI":"10.1145\/800179.810218"},{"key":"759_CR19","doi-asserted-by":"publisher","unstructured":"Koivisto M (2006) An $$O^*(2^n)$$ algorithm for graph coloring and other partitioning problems via inclusion\u2013exclusion. In: Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, pp 583\u2013590, https:\/\/doi.org\/10.1109\/FOCS.2006.11","DOI":"10.1109\/FOCS.2006.11"},{"key":"759_CR20","doi-asserted-by":"publisher","first-page":"1831","DOI":"10.1016\/j.cor.2003.12.001","volume":"32","author":"T Ladhari","year":"2005","unstructured":"Ladhari, T., & Haouari, M. (2005). A computational study of the permutation flow shop problem based on a tight lower bound. Computers & Operations Research, 32, 1831\u20131847. https:\/\/doi.org\/10.1016\/j.cor.2003.12.001.","journal-title":"Computers & Operations Research"},{"issue":"1","key":"759_CR21","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1287\/opre.26.1.53","volume":"26","author":"BJ Lageweg","year":"1978","unstructured":"Lageweg, B. J., Lenstra, J. K., & Rinnooy Kan, A. H. G. (1978). A general bounding scheme for the permutation flow-shop problem. Operations Research, 26(1), 53\u201367. https:\/\/doi.org\/10.1287\/opre.26.1.53.","journal-title":"Operations Research"},{"key":"759_CR22","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/S0167-5060(08)70743-X","volume":"1","author":"J Lenstra","year":"1977","unstructured":"Lenstra, J., Rinnooy Kan, A., & Brucker, P. (1977). Complexity of machine scheduling problems. Annals of Discrete Mathematics, 1, 343\u2013362. https:\/\/doi.org\/10.1016\/S0167-5060(08)70743-X.","journal-title":"Annals of Discrete Mathematics"},{"issue":"1","key":"759_CR23","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1057\/jors.1965.7","volume":"16","author":"ZA Lomnicki","year":"1965","unstructured":"Lomnicki, Z. A. (1965). A branch-and-bound algorithm for the exact solution of the three-machine scheduling problem. Journal of the Operational Research Society, 16(1), 89\u2013100. https:\/\/doi.org\/10.1057\/jors.1965.7.","journal-title":"Journal of the Operational Research Society"},{"key":"759_CR24","volume-title":"Combinatorics: A guided tour","author":"DR Mazur","year":"2010","unstructured":"Mazur, D. R. (2010). Combinatorics: A guided tour. Mathematical Association of America."},{"issue":"3","key":"759_CR25","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1287\/opre.15.3.473","volume":"15","author":"GB McMahon","year":"1967","unstructured":"McMahon, G. B., & Burton, P. G. (1967). Flow-shop scheduling with the branch-and-bound method. Operations Research, 15(3), 473\u2013481. https:\/\/doi.org\/10.1287\/opre.15.3.473.","journal-title":"Operations Research"},{"key":"759_CR26","unstructured":"Nederlof, J. (2008). Inclusion exclusion for hard problems. Master\u2019s thesis, Utrecht University."},{"key":"759_CR27","doi-asserted-by":"publisher","unstructured":"Nederlof, J. (2013). Fast polynomial-space algorithms using inclusion-exclusion. Algorithmica. https:\/\/doi.org\/10.1007\/s00453-012-9630-x.","DOI":"10.1007\/s00453-012-9630-x"},{"issue":"1","key":"759_CR28","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/0377-2217(80)90069-7","volume":"5","author":"C Potts","year":"1980","unstructured":"Potts, C. (1980). An adaptive branching rule for the permutation flow-shop problem. European Journal of Operational Research, 5(1), 19\u201325. https:\/\/doi.org\/10.1016\/0377-2217(80)90069-7.","journal-title":"European Journal of Operational Research"},{"key":"759_CR29","doi-asserted-by":"publisher","unstructured":"Ritt, M. (2016). A branch-and-bound algorithm with cyclic best-first search for the permutation flow shop scheduling problem. In 2016 IEEE International Conference on Automation Science and Engineering (CASE) (pp. 872\u2013877). https:\/\/doi.org\/10.1109\/COASE.2016.7743493","DOI":"10.1109\/COASE.2016.7743493"},{"issue":"2","key":"759_CR30","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1007\/s10951-017-0524-2","volume":"21","author":"L Shang","year":"2018","unstructured":"Shang, L., Lent\u00e9, C., Liedloff, M., & T\u2019Kindt, V. (2018). Exact exponential algorithms for 3-machine flowshop scheduling problems. Journal of Scheduling, 21(2), 227\u2013233. https:\/\/doi.org\/10.1007\/s10951-017-0524-2.","journal-title":"Journal of Scheduling"},{"key":"759_CR31","doi-asserted-by":"publisher","unstructured":"Williamson, D. P., Hall, L. A., Hoogeveen, J. A., Hurkens, C. A. J., Lenstra, J. K., Sevast\u2019janov, S. V., & Shmoys, D. B. (1997). Short shop schedules. Operations Research, 45(2), 288\u2013294. https:\/\/doi.org\/10.1287\/opre.45.2.288.","DOI":"10.1287\/opre.45.2.288"},{"key":"759_CR32","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/3-540-36478-1_17","volume-title":"Exact algorithms for NP-hard problems: A survey","author":"GJ Woeginger","year":"2003","unstructured":"Woeginger, G. J. (2003). Exact algorithms for NP-hard problems: A survey (pp. 185\u2013207). Cham: Springer. https:\/\/doi.org\/10.1007\/3-540-36478-1_17."}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-022-00759-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10951-022-00759-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-022-00759-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,29]],"date-time":"2023-03-29T07:09:18Z","timestamp":1680073758000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10951-022-00759-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,18]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,4]]}},"alternative-id":["759"],"URL":"https:\/\/doi.org\/10.1007\/s10951-022-00759-1","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"type":"print","value":"1094-6136"},{"type":"electronic","value":"1099-1425"}],"subject":[],"published":{"date-parts":[[2022,10,18]]},"assertion":[{"value":"19 September 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 October 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}