{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:34:46Z","timestamp":1740123286570,"version":"3.37.3"},"reference-count":68,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2024,9,30]],"date-time":"2024-09-30T00:00:00Z","timestamp":1727654400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,9,30]],"date-time":"2024-09-30T00:00:00Z","timestamp":1727654400000},"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":["Ann Oper Res"],"published-print":{"date-parts":[[2024,12]]},"DOI":"10.1007\/s10479-024-06289-7","type":"journal-article","created":{"date-parts":[[2024,9,30]],"date-time":"2024-09-30T21:01:59Z","timestamp":1727730119000},"page":"753-783","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Moderate exponential-time algorithms for scheduling problems"],"prefix":"10.1007","volume":"343","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7440-2980","authenticated-orcid":false,"given":"Vincent","family":"T\u2019kindt","sequence":"first","affiliation":[]},{"given":"Federico","family":"Della\u00a0Croce","sequence":"additional","affiliation":[]},{"given":"Mathieu","family":"Liedloff","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,9,30]]},"reference":[{"key":"6289_CR1","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1007\/s10951-018-0581-1","volume":"22","author":"S Bessy","year":"2020","unstructured":"Bessy, S., & Giroudeau, R. (2020). Parameterized complexity of a coupled-task scheduling problem. Journal of Scheduling, 22, 305\u2013313. https:\/\/doi.org\/10.1007\/s10951-018-0581-1","journal-title":"Journal of Scheduling"},{"issue":"1","key":"6289_CR2","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1109\/FOCS.2010.24","volume":"43","author":"A Bj\u00f6rklund","year":"2014","unstructured":"Bj\u00f6rklund, A. (2014). Determinant sums for undirected Hamiltonicity. SIAM Journal on Computing, 43(1), 280\u2013299. https:\/\/doi.org\/10.1109\/FOCS.2010.24","journal-title":"SIAM Journal on Computing"},{"key":"6289_CR3","first-page":"198","volume-title":"Automata, languages and programming\u201435th International colloquium, ICALP 2008, proceedings","author":"A Bj\u00f6rklund","year":"2008","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., et al. (2008). The traveling salesman problem in bounded degree graphs. In L. Aceto, I. Damgard, L. Goldberg, et al. (Eds.), Automata, languages and programming\u201435th International colloquium, ICALP 2008, proceedings (Vol. 5125, pp. 198\u2013209). Springer."},{"issue":"2","key":"6289_CR4","doi-asserted-by":"publisher","first-page":"546","DOI":"10.1137\/070683933","volume":"36","author":"A Bj\u00f6rklund","year":"2009","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., & Koivisto, M. (2009). Set partitioning via Inclusion\u2013Exclusion. SIAM Journal on Computing, 36(2), 546\u2013563. https:\/\/doi.org\/10.1137\/070683933","journal-title":"SIAM Journal on Computing"},{"key":"6289_CR5","doi-asserted-by":"publisher","first-page":"541","DOI":"10.1007\/s00453-014-9889-1","volume":"71","author":"E Bonnet","year":"2015","unstructured":"Bonnet, E., Escoffier, B., Kim, E., et al. (2015). On subexponential and FPT-time inapproximability. Algorithmica, 71, 541\u2013565. https:\/\/doi.org\/10.1007\/s00453-014-9889-1","journal-title":"Algorithmica"},{"key":"6289_CR6","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/j.jcss.2017.09.009","volume":"92","author":"E Bonnet","year":"2018","unstructured":"Bonnet, E., Lampis, M., & Paschos, V. (2018). Time-approximation trade-offs for inapproximable problems. Journal of Computer and System Science, 92, 171\u2013180. https:\/\/doi.org\/10.1016\/j.jcss.2017.09.009","journal-title":"Journal of Computer and System Science"},{"key":"6289_CR7","volume-title":"Scheduling algorithms","author":"P Brucker","year":"2007","unstructured":"Brucker, P. (2007). Scheduling algorithms. Springer."},{"key":"6289_CR8","doi-asserted-by":"publisher","unstructured":"Cygan, M., Pilipczuk, M., & Pilipczuk, M., et\u00a0al. (2011). Scheduling partially ordered jobs faster than $$2^n$$. In Demetrescu, C., & Halldorsson, M. M. (Eds.), Proceedings of 19th annual European symposium (ESA 2011), lecture notes in computer science (Vol. 6942, pp. 299\u2013310). https:\/\/doi.org\/10.1007\/978-3-642-23719-5_26","DOI":"10.1007\/978-3-642-23719-5_26"},{"key":"6289_CR9","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1007\/978-3-319-21275-3_14","volume-title":"Lower bounds based on the exponential-time hypothesis","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F. V., Kowalik, \u0141, et al. (2015). Lower bounds based on the exponential-time hypothesis (pp. 467\u2013521). Cham: Springer. https:\/\/doi.org\/10.1007\/978-3-319-21275-3_14"},{"key":"6289_CR10","doi-asserted-by":"publisher","DOI":"10.1145\/2925416","author":"M Cygan","year":"2016","unstructured":"Cygan, M., Dell, H., Lokshtanov, D., et al. (2016). On problems as hard as CNF-SAT. ACM Transactions on Algorithms. https:\/\/doi.org\/10.1145\/2925416","journal-title":"ACM Transactions on Algorithms"},{"key":"6289_CR11","unstructured":"Da\u00a0Silva, D. (1854). General properties and direct resolution of binomial congruences. Real Academia das Ciencias de Lisboa."},{"key":"6289_CR12","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1145\/321033.321034","volume":"7","author":"M Davis","year":"1960","unstructured":"Davis, M., & Putnam, H. (1960). A computing procedure for quantification theory. Journal of the ACM, 7, 201\u2013215. https:\/\/doi.org\/10.1145\/321033.321034","journal-title":"Journal of the ACM"},{"key":"6289_CR13","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1145\/368273.368557","volume":"5","author":"M Davis","year":"1962","unstructured":"Davis, M., Logemann, G., & Loveland, D. (1962). A machine program for theorem-proving. Communications of the ACM, 5, 394\u2013397. https:\/\/doi.org\/10.1145\/368273.368557","journal-title":"Communications of the ACM"},{"key":"6289_CR14","doi-asserted-by":"publisher","DOI":"10.1016\/j.amc.2020.125888","author":"F Della Croce","year":"2021","unstructured":"Della Croce, F., T\u2019kindt, V., & Ploton, O. (2021). Parallel machine scheduling with minimum number of tardy jobs: Approximation and exponential algorithms. Applied Mathematics and Computation. https:\/\/doi.org\/10.1016\/j.amc.2020.125888","journal-title":"Applied Mathematics and Computation"},{"issue":"2","key":"6289_CR15","doi-asserted-by":"publisher","first-page":"629","DOI":"10.1016\/j.ejor.2020.09.042","volume":"291","author":"M de Weerdt","year":"2021","unstructured":"de Weerdt, M., Baart, R., & He, L. (2021). Single-machine scheduling with release times, deadlines, setup times, and rejection. European Journal of Operational Research, 291(2), 629\u2013639. https:\/\/doi.org\/10.1016\/j.ejor.2020.09.042","journal-title":"European Journal of Operational Research"},{"key":"6289_CR16","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized complexity","author":"R Downey","year":"1999","unstructured":"Downey, R., & Fellows, M. (1999). Parameterized complexity. Springer."},{"key":"6289_CR17","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16533-7","volume-title":"Exact exponential algorithms","author":"F Fomin","year":"2010","unstructured":"Fomin, F., & Kratsch, D. (2010). Exact exponential algorithms. Springer."},{"issue":"5","key":"6289_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1552285.1552286","volume":"56","author":"F Fomin","year":"2009","unstructured":"Fomin, F., Grandoni, F., & Kratsch, D. (2009). A measure & conquer approach for the analysis of exact algorithms. Journal of the ACM, 56(5), 1\u201332. https:\/\/doi.org\/10.1145\/1552285.1552286","journal-title":"Journal of the ACM"},{"key":"6289_CR19","volume-title":"Computers and intractability: A guide to the theory of NP-completeness","author":"M Garey","year":"1979","unstructured":"Garey, M., & Johnson, D. (1979). Computers and intractability: A guide to the theory of NP-completeness. Freeman."},{"key":"6289_CR20","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/j.tcs.2018.05.040","volume":"745","author":"M Garraffa","year":"2018","unstructured":"Garraffa, M., Shang, L., Della Croce, F., et al. (2018). An exact exponential branch-and-merge algorithm for the single machine total tardiness problem. Theoretical Computer Science, 745, 133\u2013149. https:\/\/doi.org\/10.1016\/j.tcs.2018.05.040","journal-title":"Theoretical Computer Science"},{"key":"6289_CR21","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., et al. (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 5, 287\u2013326. https:\/\/doi.org\/10.1016\/S0167-5060(08)70356-X","journal-title":"Annals of Discrete Mathematics"},{"issue":"1\u20132","key":"6289_CR22","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/BF01585870","volume":"82","author":"L Hall","year":"1998","unstructured":"Hall, L. (1998). Approximability of flow shop scheduling. Mathematical Programming, Series B, 82(1\u20132), 175\u2013190. https:\/\/doi.org\/10.1007\/BF01585870","journal-title":"Mathematical Programming, Series B"},{"key":"6289_CR23","unstructured":"Heeger, K., & Molter, H. (2024). Minimizing the number of tardy jobs with uniform processing times on parallel machines (p.\u00a015). arXiv, arXiv:2404.14208"},{"key":"6289_CR24","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/s10479-018-2852-9","volume":"298","author":"D Hermelin","year":"2021","unstructured":"Hermelin, D., Karhi, S., Pinedo, M., et al. (2021). New algorithms for minimizing the weighted number of tardy jobs on a single machine. Annals of Operations Research, 298, 271\u2013287. https:\/\/doi.org\/10.1007\/s10479-018-2852-9","journal-title":"Annals of Operations Research"},{"issue":"103","key":"6289_CR25","first-page":"533","volume":"144","author":"D Hermelin","year":"2024","unstructured":"Hermelin, D., Itzhaki, Y., Molter, H., et al. (2024). On the parametrized complexity of interval scheduling with eligible machines. Journal of Computer and System Sciences, 144(103), 533.","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"6289_CR26","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1137\/120868177","volume":"43","author":"T Hertli","year":"2014","unstructured":"Hertli, T. (2014). 3-SAT faster and simpler-unique-SAT bounds for PPSZ hold in general. SIAM Journal on Computing, 43(2), 718\u2013729. https:\/\/doi.org\/10.1137\/120868177","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"6289_CR27","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1145\/321812.321823","volume":"21","author":"E Horowitz","year":"1974","unstructured":"Horowitz, E., & Sahni, S. (1974). Computing partitions with applications to the knapsack problem. Journal of the ACM, 21(2), 277\u2013292. https:\/\/doi.org\/10.1145\/321812.321823","journal-title":"Journal of the ACM"},{"issue":"2","key":"6289_CR28","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., & Paturi, R. (2001). On the complexity of k-SAT. Journal of Computer and System Sciences, 62(2), 367\u2013375. https:\/\/doi.org\/10.1006\/jcss.2000.1727","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"6289_CR29","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., & Zane, F. (2001). Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4), 512\u2013530. https:\/\/doi.org\/10.1006\/jcss.2001.1774","journal-title":"Journal of Computer and System Sciences"},{"key":"6289_CR30","first-page":"108","volume-title":"Computing and combinatorics\u201413th Annual international conference, COCOON 2007, proceedings","author":"K Iwama","year":"2007","unstructured":"Iwama, K., & Nakashima, T. (2007). An improved exact algorithm for cubic graph TSP. In G. Lin (Ed.), Computing and combinatorics\u201413th Annual international conference, COCOON 2007, proceedings (Vol. 4598, pp. 108\u2013117). Springer."},{"issue":"2","key":"6289_CR31","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1137\/S0895480199363908","volume":"16","author":"K Jansen","year":"2003","unstructured":"Jansen, K., Solis-Oba, R., & Sviridenko, M. (2003). Makespan minimization in job shops: A linear time approximation scheme. SIAM Journal on Discrete Mathematics, 16(2), 288\u2013300. https:\/\/doi.org\/10.1137\/S0895480199363908","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"6289_CR32","first-page":"281","volume-title":"Algorithms and data structures\u201413th International symposium","author":"K Jansen","year":"2013","unstructured":"Jansen, K., Land, F., & Land, K. (2013). Bounding the running time of algorithms for scheduling and packing problems. In F. Dehne, R. Solis-Oba, & J. R. Sack (Eds.), Algorithms and data structures\u201413th International symposium (Vol. 8037, pp. 281\u2013290). Berlin: Springer."},{"issue":"1","key":"6289_CR33","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1002\/nav.3800010110","volume":"1","author":"S Johnson","year":"1954","unstructured":"Johnson, S. (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"},{"issue":"2","key":"6289_CR34","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(2), 49\u201351. https:\/\/doi.org\/10.1016\/0167-6377(82)90044-X","journal-title":"Operations Research Letters"},{"key":"6289_CR35","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1007\/s10951-017-0550-0","volume":"21","author":"D Knop","year":"2018","unstructured":"Knop, D., & Koutecky, M. (2018). Scheduling meets $$n$$-fold integer programming. Journal of Scheduling, 21, 493\u2013503. https:\/\/doi.org\/10.1007\/s10951-017-0550-0","journal-title":"Journal of Scheduling"},{"key":"6289_CR36","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10107-019-01402-2","volume":"184","author":"D Knop","year":"2020","unstructured":"Knop, D., Koutecky, M., & Mnich, M. (2020). Combinatorial $$n$$-fold integer programming and applications. Mathematical Programming, 184, 1\u201334. https:\/\/doi.org\/10.1007\/s10107-019-01402-2","journal-title":"Mathematical Programming"},{"key":"6289_CR37","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1016\/0020-0190(76)90065-X","volume":"5","author":"E Lawler","year":"1976","unstructured":"Lawler, E. (1976). A note on the complexity of the chromatic number problem. Information Processing Letters, 5, 66\u201367. https:\/\/doi.org\/10.1016\/0020-0190(76)90065-X","journal-title":"Information Processing Letters"},{"key":"6289_CR38","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. Annals of Discrete Mathematics, 1, 331\u2013342. https:\/\/doi.org\/10.1016\/S0167-5060(08)70742-8","journal-title":"Annals of Discrete Mathematics"},{"key":"6289_CR39","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.tcs.2013.05.023","volume":"511","author":"C Lente","year":"2013","unstructured":"Lente, C., Liedloff, M., Soukhal, A., et al. (2013). On an extension of the Sort & Search method with application to scheduling theory. Theoretical Computer Science, 511, 13\u201322. https:\/\/doi.org\/10.1016\/j.tcs.2013.05.023","journal-title":"Theoretical Computer Science"},{"key":"6289_CR40","unstructured":"Lente, C., Liedloff, M., & Soukhal, A., et\u00a0al. (2014). Exponential algorithms for scheduling problems. HAL https:\/\/hal.archives-ouvertes.fr\/hal-00944382"},{"issue":"1","key":"6289_CR41","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1093\/comjnl\/bxm048","volume":"51","author":"D Marx","year":"2008","unstructured":"Marx, D. (2008). Parameterized complexity and approximation algorithms. The Computer Journal, 51(1), 60\u201378. https:\/\/doi.org\/10.1093\/comjnl\/bxm048","journal-title":"The Computer Journal"},{"key":"6289_CR42","unstructured":"Marx, D. (2011). Fixed-parameter tractable scheduling problems. In Jansen, K., Mathieu, C., Shachnai, H., & Young, N. E. (Eds.), Packing and scheduling algorithms for information and communication services, Dagstuhl reports (Vol. 1, No. 2, p.\u00a086)."},{"key":"6289_CR43","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1016\/j.cor.2018.07.020","volume":"100","author":"M Mnich","year":"2018","unstructured":"Mnich, M., & van Bevern, R. (2018). Parameterized complexity of machine scheduling: 15 Open problems. Computers & Operations Research, 100, 254\u2013261. https:\/\/doi.org\/10.1016\/j.cor.2018.07.020","journal-title":"Computers & Operations Research"},{"key":"6289_CR44","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1007\/s10107-014-0830-9","volume":"154","author":"M Mnich","year":"2015","unstructured":"Mnich, M., & Wiese, A. (2015). Scheduling and fixed-parameter tractability. Mathematical Programming, 154, 533\u2013562. https:\/\/doi.org\/10.1007\/s10107-014-0830-9","journal-title":"Mathematical Programming"},{"key":"6289_CR45","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.dam.2020.11.024","volume":"290","author":"A Munier","year":"2021","unstructured":"Munier, A. (2021). A fixed-parameter algorithm for scheduling unit dependent tasks on parallel machines with time windows. Discrete Applied Mathematics, 290, 1\u20136. https:\/\/doi.org\/10.1016\/j.dam.2020.11.024","journal-title":"Discrete Applied Mathematics"},{"key":"6289_CR46","unstructured":"Nederlof, J., & Swennenhuis, C. M. F. (2020). On the fine-grained parameterized complexity of partial scheduling to minimize the makespan. In Cao, Y., & Pilipczuk, M. (Eds.), 15th International symposium on parameterized and exact computation (IPEC 2020), Leibniz international proceedings in informatics (LIPIcs) (Vol. 180, pp. 1\u201317). Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik."},{"key":"6289_CR47","doi-asserted-by":"publisher","unstructured":"Nederlof, J., & Wegrzycki, K. (2021). Improving Schroeppel and Shamir\u2019s algorithm for subset sum via orthogonal vectors. In Proceedings of the 53rd annual ACM SIGACT symposium on theory of computing. Association for computing machinery, STOC 2021 (pp. 1670\u20131683). https:\/\/doi.org\/10.1145\/3406325.3451024","DOI":"10.1145\/3406325.3451024"},{"key":"6289_CR48","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to fixed-parameter algorithms","author":"R Niedermeier","year":"2006","unstructured":"Niedermeier, R. (2006). Invitation to fixed-parameter algorithms. Oxford University Press."},{"issue":"3","key":"6289_CR49","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1007\/s10288-015-0294-7","volume":"13","author":"V Paschos","year":"2015","unstructured":"Paschos, V. (2015). When polynomial approximation meets exact computation. 4OR, 13(3), 227\u2013245. https:\/\/doi.org\/10.1007\/s10288-015-0294-7","journal-title":"4OR"},{"key":"6289_CR50","volume-title":"Scheduling\u2014Theory, algorithms, and systems","author":"M Pinedo","year":"2016","unstructured":"Pinedo, M. (2016). Scheduling\u2014Theory, algorithms, and systems. Springer."},{"key":"6289_CR51","unstructured":"Ploton, O. (2022). Contribution of inclusion-exclusion to exact or approximate solution of scheduling problems. PhD thesis, University of Tours."},{"key":"6289_CR52","doi-asserted-by":"publisher","first-page":"3405","DOI":"10.1007\/s10878-022-00901-x","volume":"44","author":"O Ploton","year":"2022","unstructured":"Ploton, O., & T\u2019kindt, V. (2022). Exponential-time algorithms for parallel machine scheduling problems. Journal of Combinatorial Optimization, 44, 3405\u20133418. https:\/\/doi.org\/10.1007\/s10878-022-00901-x","journal-title":"Journal of Combinatorial Optimization"},{"key":"6289_CR53","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1007\/s10951-022-00759-1","volume":"26","author":"O Ploton","year":"2023","unstructured":"Ploton, O., & T\u2019kindt, V. (2023). Moderate worst-case complexity bounds for the permutation flowshop scheduling problem using inclusion-exclusion. Journal of Scheduling, 26, 137\u2013145. https:\/\/doi.org\/10.1007\/s10951-022-00759-1","journal-title":"Journal of Scheduling"},{"issue":"3","key":"6289_CR54","doi-asserted-by":"publisher","first-page":"444","DOI":"10.1287\/opre.26.3.444","volume":"26","author":"L Schrage","year":"1978","unstructured":"Schrage, L., & Baker, K. R. (1978). Dynamic programming solution of sequencing problems with precedence constraints. Operations Research, 26(3), 444\u2013449.","journal-title":"Operations Research"},{"issue":"3","key":"6289_CR55","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1137\/0210033","volume":"10","author":"R Schroeppel","year":"1981","unstructured":"Schroeppel, R., & Shamir, A. (1981). A $${T}={O}(2^\\frac{n}{2})$$, $${S}={O}(2^\\frac{n}{4})$$ algorithm for certain NP-complete problems. SIAM Journal on Computing, 10(3), 456\u2013464. https:\/\/doi.org\/10.1137\/0210033","journal-title":"SIAM Journal on Computing"},{"issue":"1\u20132","key":"6289_CR56","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/BF01585871","volume":"82","author":"S Sevastianov","year":"1998","unstructured":"Sevastianov, S., & Woeginger, G. (1998). Makespan minimization in open shops: A polynomial time approximation scheme. Mathematical Programming, 82(1\u20132), 191\u2013198. https:\/\/doi.org\/10.1007\/BF01585871","journal-title":"Mathematical Programming"},{"issue":"2","key":"6289_CR57","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., et al. (2018). Exact exponential algorithms for 3-machines flowshop scheduling problems. Journal of Scheduling, 21(2), 227\u2013233. https:\/\/doi.org\/10.1007\/s10951-017-0524-2","journal-title":"Journal of Scheduling"},{"issue":"1\u20132","key":"6289_CR58","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1002\/mcda.1660","volume":"26","author":"L Shang","year":"2019","unstructured":"Shang, L., & T\u2019kindt, V. (2019). A Sort & Search method for multicriteria optimization problems with applications to scheduling theory. Journal of Multi-Criteria Decision Analysis, 26(1\u20132), 84\u201390. https:\/\/doi.org\/10.1002\/mcda.1660","journal-title":"Journal of Multi-Criteria Decision Analysis"},{"key":"6289_CR59","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2020.105171","author":"L Shang","year":"2021","unstructured":"Shang, L., T\u2019kindt, V., & Della Croce, F. (2021). Branch & Memorize exact algorithms for sequencing problems: Efficient embedding of memorization into search trees. Computers & Operations Research. https:\/\/doi.org\/10.1016\/j.cor.2020.105171","journal-title":"Computers & Operations Research"},{"issue":"5","key":"6289_CR60","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/S0167-6377(96)00031-4","volume":"19","author":"W Szwarc","year":"1996","unstructured":"Szwarc, W., & Mukhopadhyay, S. (1996). Decomposition of the single machine total tardiness problem. Operations Research Letters, 19(5), 243\u2013250. https:\/\/doi.org\/10.1016\/S0167-6377(96)00031-4","journal-title":"Operations Research Letters"},{"issue":"3","key":"6289_CR61","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1137\/0206038","volume":"6","author":"R Tarjan","year":"1977","unstructured":"Tarjan, R., & Trojanowski, A. (1977). Finding a maximum independent set. SIAM Journal on Computing, 6(3), 537\u2013546. https:\/\/doi.org\/10.1137\/0206038","journal-title":"SIAM Journal on Computing"},{"key":"6289_CR62","volume-title":"Multicriteria scheduling: Theory, models and algorithms","author":"V T\u2019kindt","year":"2006","unstructured":"T\u2019kindt, V., & Billaut, J. C. (2006). Multicriteria scheduling: Theory, models and algorithms (2nd ed.). Springer.","edition":"2"},{"issue":"1","key":"6289_CR63","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1287\/ijoc.1050.0167","volume":"19","author":"V T\u2019kindt","year":"2007","unstructured":"T\u2019kindt, V., Della Croce, F., & Bouquard, J. L. (2007). Enumeration of Pareto optima for a flowshop scheduling problem with two criteria. INFORMS Journal on Computing, 19(1), 64\u201372. https:\/\/doi.org\/10.1287\/ijoc.1050.0167","journal-title":"INFORMS Journal on Computing"},{"key":"6289_CR64","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1007\/s10288-022-00525-1","volume":"20","author":"V T\u2019kindt","year":"2022","unstructured":"T\u2019kindt, V., Della Croce, F., & Liedloff, M. (2022). Moderate exponential-time algorithms for scheduling problems. 4OR, 20, 533\u2013566. https:\/\/doi.org\/10.1007\/s10288-022-00525-1","journal-title":"4OR"},{"key":"6289_CR65","doi-asserted-by":"publisher","first-page":"764","DOI":"10.1007\/s10878-019-00512-z","volume":"39","author":"V T\u2019kindt","year":"2020","unstructured":"T\u2019kindt, V., Shang, L., & Della, Croce F. (2020). Exponential time algorithms for just-in-time scheduling problems with common due date and symmetric weights. Journal of Combinatorial Optimization, 39, 764\u2013775. https:\/\/doi.org\/10.1007\/s10878-019-00512-z","journal-title":"Journal of Combinatorial Optimization"},{"issue":"2003","key":"6289_CR66","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/3-540-36478-1_17","volume":"2570","author":"G Woeginger","year":"2003","unstructured":"Woeginger, G. (2003). Exact algorithms for NP-hard problems: A survey. Lecture Notes in Computer Science, 2570(2003), 185\u2013207. https:\/\/doi.org\/10.1007\/3-540-36478-1_17","journal-title":"Lecture Notes in Computer Science"},{"key":"6289_CR67","first-page":"281","volume-title":"Parameterized and exact computation\u20141st International workshop, IWPEC 2004, proceedings","author":"G Woeginger","year":"2004","unstructured":"Woeginger, G. (2004). Space and time complexity of exact algorithms: Some open problems. In R. Downey, M. Fellows, & F. Dehne (Eds.), Parameterized and exact computation\u20141st International workshop, IWPEC 2004, proceedings (Vol. 3162, pp. 281\u2013290). Berlin: Springer."},{"issue":"1","key":"6289_CR68","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1016\/j.ic.2017.06.001","volume":"255","author":"M Xiao","year":"2017","unstructured":"Xiao, M., & Nagamochi, H. (2017). Exact algorithms for maximum independent set. Information and Computation, 255(1), 126\u2013146. https:\/\/doi.org\/10.1016\/j.ic.2017.06.001","journal-title":"Information and Computation"}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-024-06289-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10479-024-06289-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-024-06289-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,16]],"date-time":"2024-12-16T12:18:47Z","timestamp":1734351527000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10479-024-06289-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,30]]},"references-count":68,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["6289"],"URL":"https:\/\/doi.org\/10.1007\/s10479-024-06289-7","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"type":"print","value":"0254-5330"},{"type":"electronic","value":"1572-9338"}],"subject":[],"published":{"date-parts":[[2024,9,30]]},"assertion":[{"value":"18 June 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 September 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 September 2024","order":3,"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"}},{"value":"This article does not contain any studies with human participants or animals performed by any of the authors.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical approval"}}]}}