{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T06:43:01Z","timestamp":1778827381576,"version":"3.51.4"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2017,4,27]],"date-time":"2017-04-27T00:00:00Z","timestamp":1493251200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2018,4]]},"DOI":"10.1007\/s10951-017-0524-2","type":"journal-article","created":{"date-parts":[[2017,4,27]],"date-time":"2017-04-27T06:05:56Z","timestamp":1493273156000},"page":"227-233","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Exact exponential algorithms for 3-machine flowshop scheduling problems"],"prefix":"10.1007","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4395-3226","authenticated-orcid":false,"given":"Lei","family":"Shang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christophe","family":"Lent\u00e9","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mathieu","family":"Liedloff","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vincent","family":"T\u2019Kindt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,4,27]]},"reference":[{"key":"524_CR1","doi-asserted-by":"publisher","unstructured":"Akiba, T., & Iwata, Y. (2015). Branch-and-reduce exponential\/fpt algorithms in practice: A case study of vertex cover. Theoretical Computer Science. doi:\n                        10.1016\/j.tcs.2015.09.023\n                        \n                    . \n                        http:\/\/www.sciencedirect.com\/science\/article\/pii\/S030439751500852X\n                        \n                    .","DOI":"10.1016\/j.tcs.2015.09.023"},{"key":"524_CR2","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1080\/05695557008974749","volume":"2","author":"S Ashour","year":"1970","unstructured":"Ashour, S. (1970). A branch-and-bound algorithm for the flow shop problem scheduling problem. AIIE Transactions, 2, 172\u2013176.","journal-title":"AIIE Transactions"},{"issue":"2","key":"524_CR3","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1057\/jors.1966.25","volume":"17","author":"A Brown","year":"1966","unstructured":"Brown, A., & Lomnicki, Z. (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.","journal-title":"Journal of the Operational Research Society"},{"key":"524_CR4","volume-title":"Scheduling algorithms","author":"P Brucker","year":"2007","unstructured":"Brucker, P. (2007). Scheduling algorithms (5th ed.). Berlin: Springer.","edition":"5"},{"issue":"2","key":"524_CR5","doi-asserted-by":"crossref","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.","journal-title":"European Journal of Operational Research"},{"issue":"3","key":"524_CR6","doi-asserted-by":"crossref","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.","journal-title":"European Journal of Operational Research"},{"issue":"3","key":"524_CR7","doi-asserted-by":"crossref","first-page":"692","DOI":"10.1007\/s00453-012-9694-7","volume":"68","author":"M Cygan","year":"2014","unstructured":"Cygan, M., Pilipczuk, M., Pilipczuk, M., & Wojtaszczyk, J. O. (2014). Scheduling partially ordered jobs faster than \n                        $$2^n$$\n                        \n                            \n                                \n                                    2\n                                    n\n                                \n                            \n                        \n                    . Algorithmica, 68(3), 692\u2013714.","journal-title":"Algorithmica"},{"key":"524_CR8","doi-asserted-by":"crossref","unstructured":"Fomin, F. V., & Kratsch, D. (2010). Exact exponential algorithms. Springer Berlin Heidelberg.","DOI":"10.1007\/978-3-642-16533-7"},{"issue":"12","key":"524_CR9","doi-asserted-by":"crossref","first-page":"1243","DOI":"10.1057\/palgrave.jors.2601784","volume":"55","author":"JM Framinan","year":"2004","unstructured":"Framinan, J. M., Gupta, J. N., & 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.","journal-title":"Journal of the Operational Research Society"},{"issue":"2","key":"524_CR10","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1287\/moor.1.2.117","volume":"1","author":"MR Garey","year":"1976","unstructured":"Garey, M. R., Johnson, D. S., & Sethi, R. (1976). The complexity of flowshop and jobshop scheduling. Mathematics of Operations Research, 1(2), 117\u2013129.","journal-title":"Mathematics of Operations Research"},{"key":"524_CR11","doi-asserted-by":"crossref","unstructured":"Gromicho, J. A., van Hoorn, J. J., da Gama, F. S., & Timmer, G. T. (2012). Solving the job-shop scheduling problem optimally by dynamic programming. Computers & Operations Research, 39(12), 2968\u20132977.","DOI":"10.1016\/j.cor.2012.02.024"},{"issue":"3","key":"524_CR12","doi-asserted-by":"crossref","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.","journal-title":"Operations Research"},{"key":"524_CR13","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1007\/978-3-642-40104-6_38","volume-title":"Algorithms and data structures","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 (Vol. 8037, pp. 439\u2013450)., Lecture notes in computer science Berlin: Springer."},{"issue":"1","key":"524_CR14","doi-asserted-by":"crossref","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.","journal-title":"Naval Research Logistics Quarterly"},{"key":"524_CR15","doi-asserted-by":"crossref","unstructured":"Kelley Jr, J. E., & Walker, M. R. (1959). Critical-path planning and scheduling. In Papers Presented at the December 1\u20133, 1959, Eastern Joint IRE-AIEE-ACM Computer Conference (pp. 160\u2013173), ACM.","DOI":"10.1145\/1460299.1460318"},{"issue":"4","key":"524_CR16","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1145\/321906.321910","volume":"22","author":"HT Kung","year":"1975","unstructured":"Kung, H. T., Luccio, F., & Preparata, F. P. (1975). On finding the maxima of a set of vectors. Journal of the ACM (JACM), 22(4), 469\u2013476.","journal-title":"Journal of the ACM (JACM)"},{"issue":"7","key":"524_CR17","doi-asserted-by":"crossref","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(7), 1831\u20131847.","journal-title":"Computers & Operations Research"},{"issue":"1","key":"524_CR18","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1287\/opre.26.1.53","volume":"26","author":"B Lageweg","year":"1978","unstructured":"Lageweg, B., Lenstra, J., & Rinnooy Kan, A. (1978). A general bounding scheme for the permutation flow-shop problem. Operations Research, 26(1), 53\u201367.","journal-title":"Operations Research"},{"key":"524_CR19","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/j.tcs.2013.05.023","volume":"511","author":"C Lent\u00e9","year":"2013","unstructured":"Lent\u00e9, C., Liedloff, M., Soukhal, A., & T\u2019Kindt, V. (2013). On an extension of the Sort & Search method with application to scheduling theory. Theoretical Computer Science, 511, 13\u201322.","journal-title":"Theoretical Computer Science"},{"key":"524_CR20","unstructured":"Lent\u00e9, C., Liedloff, M., Soukhal, A., & T\u2019Kindt, V. (2014). Exponential algorithms for scheduling problems. \n                        https:\/\/hal.archives-ouvertes.fr\/hal-00944382\n                        \n                    ."},{"issue":"1","key":"524_CR21","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1057\/jors.1965.7","volume":"16","author":"Z Lomnicki","year":"1965","unstructured":"Lomnicki, Z. (1965). A \u201cbranch-and-bound\u201d algorithm for the exact solution of the three-machine scheduling problem. Journal of the Operational Research Society, 16(1), 89\u2013100.","journal-title":"Journal of the Operational Research Society"},{"issue":"3","key":"524_CR22","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1287\/opre.15.3.473","volume":"15","author":"G McMahon","year":"1967","unstructured":"McMahon, G., & Burton, P. (1967). Flow-shop scheduling with the branch-and-bound method. Operations Research, 15(3), 473\u2013481.","journal-title":"Operations Research"},{"issue":"1","key":"524_CR23","doi-asserted-by":"crossref","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.","journal-title":"European Journal of Operational Research"},{"issue":"14","key":"524_CR24","doi-asserted-by":"crossref","first-page":"2895","DOI":"10.1080\/0020754050056417","volume":"43","author":"S Reza Hejazi","year":"2005","unstructured":"Reza Hejazi, S., & Saghafian, S. (2005). Flowshop-scheduling problems with makespan criterion: A review. International Journal of Production Research, 43(14), 2895\u20132929.","journal-title":"International Journal of Production Research"},{"issue":"2","key":"524_CR25","doi-asserted-by":"crossref","first-page":"479","DOI":"10.1016\/j.ejor.2004.04.017","volume":"165","author":"R Ruiz","year":"2005","unstructured":"Ruiz, R., & Maroto, C. (2005). A comprehensive review and evaluation of permutation flowshop heuristics. European Journal of Operational Research, 165(2), 479\u2013494. Project Management and Scheduling.","journal-title":"European Journal of Operational Research"},{"issue":"1","key":"524_CR26","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1016\/S0377-2217(97)00139-2","volume":"109","author":"C Smutnicki","year":"1998","unstructured":"Smutnicki, C. (1998). Some results of the worst-case analysis for flow shop scheduling. European Journal of Operational Research, 109(1), 66\u201387.","journal-title":"European Journal of Operational Research"},{"issue":"1","key":"524_CR27","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1023\/B:ANOR.0000030691.65576.28","volume":"129","author":"M Sviridenko","year":"2004","unstructured":"Sviridenko, M. (2004). A note on permutation flow shop problem. Annals of Operations Research, 129(1), 247\u2013252.","journal-title":"Annals of Operations Research"},{"key":"524_CR28","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1007\/3-540-36478-1_17","volume-title":"Combinatorial optimization\u2014Eureka, you shrink!","author":"GJ Woeginger","year":"2003","unstructured":"Woeginger, G. J. (2003). Exact algorithms for NP-hard problems: A survey. In M. J\u00fcnger, G. Reinelt, & G. Rinaldi (Eds.), Combinatorial optimization\u2014Eureka, you shrink! (Vol. 2570, pp. 185\u2013207)., Lecture notes in computer science Berlin: Springer."},{"key":"524_CR29","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"328","DOI":"10.1007\/978-3-642-45030-3_31","volume-title":"Algorithms and computation","author":"M Xiao","year":"2013","unstructured":"Xiao, M., & Nagamochi, H. (2013). Exact algorithms for maximum independent set. In L. Cai, S. W. Cheng, & T. W. Lam (Eds.), Algorithms and computation (Vol. 8283, pp. 328\u2013338)., Lecture notes in computer science Berlin: Springer."}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10951-017-0524-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-017-0524-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-017-0524-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2018,3,6]],"date-time":"2018-03-06T10:28:08Z","timestamp":1520332088000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10951-017-0524-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,4,27]]},"references-count":29,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,4]]}},"alternative-id":["524"],"URL":"https:\/\/doi.org\/10.1007\/s10951-017-0524-2","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"value":"1094-6136","type":"print"},{"value":"1099-1425","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,4,27]]}}}