{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,13]],"date-time":"2025-12-13T07:17:40Z","timestamp":1765610260031,"version":"3.37.3"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2022,9,3]],"date-time":"2022-09-03T00:00:00Z","timestamp":1662163200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,9,3]],"date-time":"2022-09-03T00:00:00Z","timestamp":1662163200000},"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":["J Comb Optim"],"published-print":{"date-parts":[[2022,12]]},"DOI":"10.1007\/s10878-022-00901-x","type":"journal-article","created":{"date-parts":[[2022,9,3]],"date-time":"2022-09-03T21:02:20Z","timestamp":1662238940000},"page":"3405-3418","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Exponential-time algorithms for parallel machine scheduling problems"],"prefix":"10.1007","volume":"44","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4582-3441","authenticated-orcid":false,"given":"Olivier","family":"Ploton","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7440-2980","authenticated-orcid":false,"given":"Vincent","family":"T\u2019kindt","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,9,3]]},"reference":[{"key":"901_CR1","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":"901_CR2","doi-asserted-by":"publisher","unstructured":"Bjorklund A, Husfeldt T (2006) Inclusion\u2013exclusion algorithms for counting set partitions. In: Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, pp 575 \u2013 582, https:\/\/doi.org\/10.1109\/FOCS.2006.41","DOI":"10.1109\/FOCS.2006.41"},{"key":"901_CR3","doi-asserted-by":"publisher","unstructured":"B\u0142a\u017cewicz J, Ecker K, Pesch E, Schmidt G, Sterna M, Weglarz J (2019) Handbook on Scheduling: From Theory to Practice. International handbooks on information systems, Springer. https:\/\/doi.org\/10.1007\/978-3-319-99849-7","DOI":"10.1007\/978-3-319-99849-7"},{"key":"901_CR4","unstructured":"Brucker P (2010) Scheduling Algorithms, 5th edn. Springer"},{"key":"901_CR5","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1145\/361011.361064","volume":"17","author":"J Bruno","year":"1974","unstructured":"Bruno J, Coffman E Jr, Sethi R (1974) Scheduling independent tasks to reduce mean finishing time. Comm ACM 17:382\u2013387","journal-title":"Comm ACM"},{"key":"901_CR6","doi-asserted-by":"crossref","unstructured":"Fomin F, Kratsch D (2010) Exact Exponential Algorithms. Texts in Theoretical Computer Science, Springer","DOI":"10.1007\/978-3-642-16533-7"},{"issue":"3","key":"901_CR7","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1145\/322077.322090","volume":"25","author":"MR Garey","year":"1978","unstructured":"Garey MR, Johnson DS (1978) \u201cstrong\u2019\u2019 np-completeness results: Motivation, examples, and implications. J ACM 25(3):499\u2013508. https:\/\/doi.org\/10.1145\/322077.322090","journal-title":"J ACM"},{"issue":"2","key":"901_CR8","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","volume":"5","author":"RL Graham","year":"1979","unstructured":"Graham RL, Lawler EL, Lenstra JK, Rinnooy Kan AHG (1979) Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann Discrete Math 5(2):287\u2013326. https:\/\/doi.org\/10.1016\/S0167-5060(08)70356-X","journal-title":"Ann Discrete Math"},{"key":"901_CR9","doi-asserted-by":"crossref","unstructured":"Harvey D, Van Der\u00a0Hoeven J (2020) Integer multiplication in time O(n log n). Annals of Mathematics","DOI":"10.4007\/annals.2021.193.2.4"},{"issue":"2","key":"901_CR10","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1287\/ijoc.13.2.157.10520","volume":"13","author":"H Hoogeveen","year":"2001","unstructured":"Hoogeveen H, Schuurman P, Woeginger GJ (2001) Non-approximability results for scheduling problems with minsum criteria. INFORMS J Comput 13(2):157\u2013168","journal-title":"INFORMS J Comput"},{"key":"901_CR11","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":"901_CR12","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 - 13th International Symposium, Springer, Lecture Notes in Computer Science, vol 8037, pp 439\u2013450, https:\/\/doi.org\/10.1007\/978-3-642-40104-6_38","DOI":"10.1007\/978-3-642-40104-6_38"},{"key":"901_CR13","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. Oper Res Lett 1:49\u201351. https:\/\/doi.org\/10.1016\/0167-6377(82)90044-X","journal-title":"Oper Res Lett"},{"key":"901_CR14","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":"901_CR15","doi-asserted-by":"publisher","first-page":"544","DOI":"10.1287\/mnsc.19.5.544","volume":"19","author":"E Lawler","year":"1973","unstructured":"Lawler E (1973) Optimal sequencing of a single machine subject to precedence constraints. Management Sci 19:544\u2013546","journal-title":"Management Sci"},{"key":"901_CR16","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1016\/S0167-5060(08)70742-8","volume":"1","author":"E Lawler","year":"1977","unstructured":"Lawler E (1977) A pseudopolynomial algorithm for sequencing jobs to minimize total tardiness. Ann of Discrete Math 1:331\u2013342","journal-title":"Ann of Discrete Math"},{"key":"901_CR17","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. Ann Discrete Math 1:343\u2013362. https:\/\/doi.org\/10.1016\/S0167-5060(08)70743-X","journal-title":"Ann Discrete Math"},{"key":"901_CR18","doi-asserted-by":"crossref","unstructured":"Lenstra JK, Shmoys D, Tardos E (1990) Approximation algorithms for scheduling unrelated parallel machines. Mathematical Programming 46","DOI":"10.1007\/BF01585745"},{"key":"901_CR19","unstructured":"Lent\u00e9 C, Liedloff M, Soukhal A, T\u2019Kindt V (2014) Exponential Algorithms for Scheduling Problems. Tech. rep., University of Tours, https:\/\/hal.archives-ouvertes.fr\/hal-00944382"},{"key":"901_CR20","doi-asserted-by":"publisher","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 JH (2004) Handbook of Scheduling: Algorithms, Models, and Performance Analysis. CRC Press Inc, USA"},{"key":"901_CR21","volume-title":"Combinatorics: a Guided Tour","author":"DR Mazur","year":"2010","unstructured":"Mazur DR (2010) Combinatorics: a Guided Tour. Mathematical Association of America, Washington, DC"},{"key":"901_CR22","unstructured":"Nederlof J (2008) Inclusion exclusion for hard problems. Master\u2019s thesis, Utrecht University"},{"key":"901_CR23","doi-asserted-by":"publisher","first-page":"868","DOI":"10.1007\/s00453-012-9630-x","volume":"65","author":"J Nederlof","year":"2013","unstructured":"Nederlof J (2013) Fast polynomial-space algorithms using inclusion-exclusion. Algorithmica 65:868\u2013884. https:\/\/doi.org\/10.1007\/s00453-012-9630-x","journal-title":"Algorithmica"},{"key":"901_CR24","doi-asserted-by":"publisher","unstructured":"Pinedo M (2005) Planning and Scheduling in Manufacturing and Services. Springer Series in Operations Research and Financial Engineering Series, Springer. https:\/\/doi.org\/10.1007\/b139030","DOI":"10.1007\/b139030"},{"key":"901_CR25","doi-asserted-by":"publisher","unstructured":"Pinedo ML (2016) Scheduling: Theory, Algorithms, and Systems, 5th edn. Springer Publishing Company, Incorporated, https:\/\/doi.org\/10.1007\/978-3-319-26580-3","DOI":"10.1007\/978-3-319-26580-3"},{"key":"901_CR26","doi-asserted-by":"publisher","unstructured":"Woeginger GJ (2003) Exact Algorithms for NP-Hard Problems: A Survey, Springer, pp 185\u2013207. https:\/\/doi.org\/10.1007\/3-540-36478-1_17","DOI":"10.1007\/3-540-36478-1_17"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-022-00901-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-022-00901-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-022-00901-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,29]],"date-time":"2022-10-29T09:39:58Z","timestamp":1667036398000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-022-00901-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,3]]},"references-count":26,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["901"],"URL":"https:\/\/doi.org\/10.1007\/s10878-022-00901-x","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2022,9,3]]},"assertion":[{"value":"20 August 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 September 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"}}]}}