{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,19]],"date-time":"2025-12-19T09:19:14Z","timestamp":1766135954081},"publisher-location":"Berlin, Heidelberg","reference-count":39,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540782940"},{"type":"electronic","value":"9783540782957"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-78295-7_4","type":"book-chapter","created":{"date-parts":[[2008,8,11]],"date-time":"2008-08-11T13:20:59Z","timestamp":1218460859000},"page":"85-116","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":21,"title":["Hybridizations of Metaheuristics With Branch & Bound Derivates"],"prefix":"10.1007","author":[{"given":"Christian","family":"Blum","sequence":"first","affiliation":[]},{"given":"Carlos","family":"Cotta","sequence":"additional","affiliation":[]},{"given":"Antonio J.","family":"Fern\u00e1ndez","sequence":"additional","affiliation":[]},{"given":"Jos\u00e9 E.","family":"Gallardo","sequence":"additional","affiliation":[]},{"given":"Monaldo","family":"Mastrolilli","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"4_CR1_1","volume-title":"Data structures and algorithms","author":"A Aho","year":"1983","unstructured":"A. Aho, J. Hopcroft, and J. Ullman. Data structures and algorithms. Addison-Wesley, Reading, MA, 1983."},{"key":"4_CR2_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"318","DOI":"10.1007\/978-3-540-28646-2_30","volume-title":"Proceedings of ANTS 2004 \u2013 4th International Workshop on Ant Colony Optimization and Swarm Intelligence","author":"S Al-Shihabi","year":"2004","unstructured":"S. Al-Shihabi. Backtracking ant system for the traveling salesman problem. In M. Dorigo, M. Birattari, C. Blum, L. M. Gambardella, F. Mondada, and T. St\u00fctzle, editors, Proceedings of ANTS 2004 \u2013 4th International Workshop on Ant Colony Optimization and Swarm Intelligence, volume 3172 of Lecture Notes in Computer Science, pages 318\u2013325. Springer-Verlag, Berlin, 2004."},{"key":"4_CR3_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"160","DOI":"10.1007\/978-3-540-24653-4_17","volume-title":"Applications of Evolutionary Computing, Proceedings of EvoWorkshops 2004","author":"MJ Blesa","year":"2004","unstructured":"M. J. Blesa and C. Blum. Ant colony optimization for the maximum edge-disjoint paths problem. In G. R. Raidl et al., editors, Applications of Evolutionary Computing, Proceedings of EvoWorkshops 2004, volume 3005 of Lecture Notes in Computer Science, pages 160\u2013169. Springer-Verlag, Berlin, 2004."},{"key":"4_CR4_1","doi-asserted-by":"publisher","first-page":"1565","DOI":"10.1016\/j.cor.2003.11.018","volume":"32","author":"C Blum","year":"2005","unstructured":"C. Blum. Beam-ACO\u2013hybridizing ant colony optimization with beam search: an application to open shop scheduling. Computers and Operations Research, 32:1565\u20131591, 2005.","journal-title":"Computers and Operations Research"},{"key":"4_CR5_1","series-title":"Lecture Notes in Computer Science","first-page":"14","volume-title":"Proceedings of ANTS 2006 \u2013 Fifth International Workshop on Swarm Intelligence and Ant Algorithms","author":"C Blum","year":"2006","unstructured":"C. Blum, J. Bautista, and J. Pereira. Beam-ACO applied to assembly line balancing. In M. Dorigo, L. M. Gambardella, A. Martinoli, R. Poli, and T. St\u00fctzle, editors, Proceedings of ANTS 2006 \u2013 Fifth International Workshop on Swarm Intelligence and Ant Algorithms, volume 2463 of Lecture Notes in Computer Science, pages 14\u201327. Springer-Verlag, Berlin, Germany, 2006."},{"key":"4_CR6_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1007\/978-3-540-71615-0_4","volume-title":"Proceedings of EvoCOP 2007 \u2013 Seventh European Conference on Evolutionary Computation in Combinatorial Optimisation","author":"C Blum","year":"2007","unstructured":"C. Blum, C. Cotta, A. J. Fern\u00e1ndez, and J. E. Gallardo. A probabilistic beam search algorithm for the shortest common supersequence problem. In C. Cotta et al., editor, Proceedings of EvoCOP 2007 \u2013 Seventh European Conference on Evolutionary Computation in Combinatorial Optimisation, volume 4446 of Lecture Notes in Computer Science, pages 36\u201347. Springer-Verlag, Berlin, Germany, 2007."},{"issue":"2","key":"4_CR7_1","doi-asserted-by":"publisher","first-page":"1161","DOI":"10.1109\/TSMCB.2003.821450","volume":"34","author":"C Blum","year":"2004","unstructured":"C. Blum and M. Dorigo. The hyper-cube framework for ant colony optimization. IEEE Transactions on Systems, Man, and Cybernetics \u2013 Part B, 34(2):1161\u20131172, 2004.","journal-title":"IEEE Transactions on Systems, Man, and Cybernetics \u2013 Part B"},{"key":"4_CR8_1","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/BF01545528","volume":"20","author":"J Branke","year":"1998","unstructured":"J. Branke, M. Middendorf, and F. Schneider. Improved heuristics and a genetic algorithm for finding short supersequences. OR-Spektrum, 20:39\u201345, 1998.","journal-title":"OR-Spektrum"},{"key":"4_CR9_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1007\/978-3-540-45157-0_15","volume-title":"Proceedings of PATAT 2002 \u2013 4th International Conference on Practice and Theory of Automated Timetabling","author":"S Casey","year":"2003","unstructured":"S. Casey and J. Thompson. GRASPing the examination scheduling problem. In E. K. Burke and P. De Causmaecker, editors, Proceedings of PATAT 2002 \u2013 4th International Conference on Practice and Theory of Automated Timetabling, volume 2740 of Lecture Notes in Computer Science, pages 232\u2013246. Springer-Verlag, Berlin, 2003."},{"key":"4_CR10_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1007\/3-540-44869-1_41","volume-title":"Proceedings of the 7th International Work-Conference on Artificial and Natural Neural Networks (IWANN 2003)","author":"C Cotta","year":"2003","unstructured":"C. Cotta. Protein structure prediction using evolutionary algorithms hybridized with backtracking. In J. Mira and J. R. \u00c1lvarez, editors, Proceedings of the 7th International Work-Conference on Artificial and Natural Neural Networks (IWANN 2003), volume 2687 of Lecture Notes in Computer Science, pages 321\u2013328. Springer-Verlag, Berlin, 2003."},{"key":"4_CR11_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1007\/11499305_9","volume-title":"Artificial Intelligence and Knowledge Engineering Applications: a Bioinspired Approach","author":"C Cotta","year":"2005","unstructured":"C. Cotta. Memetic algorithms with partial lamarckism for the shortest common supersequence problem. In J. Mira and J. R. \u00c1lvarez, editors, Artificial Intelligence and Knowledge Engineering Applications: a Bioinspired Approach, number 3562 in Lecture Notes in Computer Science, pages 84\u201391, Berlin Heidelberg, 2005. Springer-Verlag."},{"key":"4_CR12_1","doi-asserted-by":"crossref","unstructured":"M. Dorigo and T. Stuetzle. Ant Colony Optimization. MIT Press, 2004.","DOI":"10.7551\/mitpress\/1290.001.0001"},{"key":"4_CR13_1","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/BF01096763","volume":"6","author":"TA Feo","year":"1995","unstructured":"T. A. Feo and M. G. C. Resende. Greedy randomized adaptive search procedures. Journal of Global Optimization, 6:109\u2013133, 1995.","journal-title":"Journal of Global Optimization"},{"issue":"2\u20133","key":"4_CR14_1","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/0004-3702(92)90016-Q","volume":"57","author":"DE Foulser","year":"1992","unstructured":"D. E. Foulser, M. Li, and Q. Yang. Theory and algorithms for plan merging. Artificial Intelligence, 57(2-3):143\u2013181, 1992.","journal-title":"Artificial Intelligence"},{"key":"4_CR15_1","unstructured":"C. B. Fraser. Subsequences and supersequences of strings. PhD thesis, University of Glasgow, 1995."},{"issue":"1","key":"4_CR16_1","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1109\/TSMCB.2006.883266","volume":"37","author":"JE Gallardo","year":"2007","unstructured":"J. E. Gallardo, C. Cotta, and A. J. Fern\u00e1ndez. On the hybridization of memetic algorithms with branch-and-bound techniques. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 37(1):77\u201383, 2007.","journal-title":"IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics"},{"key":"4_CR17_1","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on Strings, Trees, and Sequences","author":"D Gusfield","year":"1997","unstructured":"D. Gusfield. Algorithms on Strings, Trees, and Sequences. Computer Science and Computational Biology. Cambridge University Press, Cambridge, 1997."},{"key":"4_CR18_1","unstructured":"M. T. Hallet. An integrated complexity analysis of problems from computational biology. PhD thesis, University of Victoria, 1996."},{"key":"4_CR19_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-32363-5","volume-title":"Recent Advances in Memetic Algorithms","author":"WE Hart","year":"2005","unstructured":"W. E. Hart, N. Krasnogor, and J. E. Smith. Recent Advances in Memetic Algorithms. Springer-Verlag, Berlin Heidelberg, 2005."},{"key":"4_CR20_1","unstructured":"J. N. Hooker. Unifying local and exhaustive search. In L. Villase\u00f1or and A. I. Martinez, editors, Proceedings of ENC 2005 \u2013 Sixth Mexican International Conference on Computer Science, pages 237\u2013243. IEEE press, 2005."},{"issue":"1","key":"4_CR21_1","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1162\/evco.1997.5.1.31","volume":"5","author":"C Houck","year":"1997","unstructured":"C. Houck, J. A. Joines, M. G. Kay, and J. R. Wilson. Empirical investigation of the benefits of partial lamarckianism. Evolutionary Computation, 5(1):31\u201360, 1997.","journal-title":"Evolutionary Computation"},{"key":"4_CR22_1","unstructured":"K. Huang, C. Yang, and K. Tseng. Fast algorithms for finding the common subsequences of multiple sequences. In Proceedings of the International Computer Symposium, pages 1006\u20131011. IEEE press, 2004."},{"issue":"5","key":"4_CR23_1","doi-asserted-by":"publisher","first-page":"474","DOI":"10.1109\/TEVC.2005.850260","volume":"9","author":"N Krasnogor","year":"2005","unstructured":"N. Krasnogor and J. E. Smith. A tutorial for competent memetic algorithms: model, taxonomy, and design issues. IEEE Transactions on Evolutionary Computation, 9(5):474\u2013488, 2005.","journal-title":"IEEE Transactions on Evolutionary Computation"},{"key":"4_CR24_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1007\/BFb0040803","volume-title":"Proceedings of Evolutionary Programming VII, 7th International Conference","author":"GB Lamont","year":"1998","unstructured":"G. B. Lamont, S. M. Brown, and G. H. Gates Jr. Evolutionary algorithms combined with deterministic search. In V. W. Porto, N. Saravanan, D. E. Waagen, and A. E. Eiben, editors, Proceedings of Evolutionary Programming VII, 7th International Conference, volume 1447 of Lecture Notes in Computer Science, pages 517\u2013526. Springer-Verlag, Berlin, 1998."},{"issue":"4","key":"4_CR25_1","first-page":"669","volume":"4","author":"E Lawler","year":"1966","unstructured":"E. Lawler and D. Wood. Branch and bound methods: A survey. Operations Research, 4(4):669\u2013719, 1966.","journal-title":"Operations Research"},{"key":"4_CR26_1","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1145\/322063.322075","volume":"25","author":"D Maier","year":"1978","unstructured":"D. Maier. The complexity of some problems on subsequences and supersequences. Journal of the ACM, 25:322\u2013336, 1978.","journal-title":"Journal of the ACM"},{"issue":"4","key":"4_CR27_1","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1287\/ijoc.11.4.358","volume":"11","author":"V Maniezzo","year":"1999","unstructured":"V. Maniezzo. Exact and Approximate Nondeterministic Tree-Search Procedures for the Quadratic Assignment Problem. INFORMS Journal on Computing, 11(4):358\u2013369, 1999.","journal-title":"INFORMS Journal on Computing"},{"key":"4_CR28_1","doi-asserted-by":"publisher","first-page":"927","DOI":"10.1016\/S0167-739X(00)00046-7","volume":"16","author":"V Maniezzo","year":"2000","unstructured":"V. Maniezzo and A. Carbonaro. An ANTS heuristic for the frequency assignment problem. Future Generation Computer Systems, 16:927\u2013935, 2000.","journal-title":"Future Generation Computer Systems"},{"key":"4_CR29_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1007\/3-540-45724-0_19","volume-title":"Proceedings of ANTS 2002: 3rd International Workshop on Ant Algorithms","author":"V Maniezzo","year":"2002","unstructured":"V. Maniezzo and M. Milandri. An ant-based framework for very strongly constrained problems. In M. Dorigo, G. Di Caro, and M. Sampels, editors, Proceedings of ANTS 2002: 3rd International Workshop on Ant Algorithms, volume 2463 of Lecture Notes in Computer Science, pages 222\u2013227. Springer-Verlag, Berlin, 2002."},{"key":"4_CR30_1","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0304-3975(92)00074-2","volume":"125","author":"M Middendorf","year":"1994","unstructured":"M. Middendorf. More on the complexity of common superstring and supersequence problems. Theoretical Computer Science, 125:205\u2013228, 1994.","journal-title":"Theoretical Computer Science"},{"key":"4_CR31_1","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/0-306-48056-5_5","volume-title":"Handbook of Metaheuristics","author":"P Moscato","year":"2003","unstructured":"P. Moscato and C. Cotta. A gentle introduction to memetic algorithms. In Handbook of Metaheuristics, pages 105\u2013144. Kluwer Academic Press, Boston, Massachusetts, USA, 2003."},{"issue":"2","key":"4_CR32_1","doi-asserted-by":"publisher","first-page":"797","DOI":"10.1287\/mnsc.42.6.797","volume":"42","author":"E Nowicki","year":"1996","unstructured":"E. Nowicki and C. Smutnicki. A fast taboo search algorithm for the job-shop problem. Management Science, 42(2):797\u2013813, 1996.","journal-title":"Management Science"},{"key":"4_CR33_1","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1080\/00207548808947840","volume":"26","author":"PS Ow","year":"1988","unstructured":"P. S. Ow and T. E. Morton. Filtered beam search in scheduling. International Journal of Production Research, 26:297\u2013307, 1988.","journal-title":"International Journal of Production Research"},{"key":"4_CR34_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/11499305_5","volume-title":"Artificial Intelligence and Knowledge Engineering Applications: a Bioinspired Approach","author":"J Puchinger","year":"2005","unstructured":"J. Puchinger and G. R. Raidl. Combining metaheuristics and exact algorithms in combinatorial optimization: A survey and classification. In J. Mira and J. R. \u00c1lvarez, editors, Artificial Intelligence and Knowledge Engineering Applications: a Bioinspired Approach, number 3562 in Lecture Notes in Computer Science, pages 41\u201353, Berlin Heidelberg, 2005. Springer-Verlag."},{"issue":"2","key":"4_CR35_1","doi-asserted-by":"publisher","first-page":"ii156","DOI":"10.1093\/bioinformatics\/btg1073","volume":"19","author":"S Rahmann","year":"2003","unstructured":"S. Rahmann. The shortest common supersequence problem in a microarray production setting. Bioinformatics, 19(Suppl. 2):ii156\u2013ii161, 2003.","journal-title":"Bioinformatics"},{"key":"4_CR36_1","unstructured":"S. J. Russell and P. Norvig. Artificial Intelligence: A Modern Approach. Prentice Hall, 2003."},{"issue":"1","key":"4_CR37_1","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/S1570-8667(03)00011-X","volume":"1","author":"JS Sim","year":"2003","unstructured":"J. S. Sim and K. Park. The consensus string problem for a metric is NP-complete. Journal of Discrete Algorithms, 1(1):111\u2013117, 2003.","journal-title":"Journal of Discrete Algorithms"},{"issue":"1","key":"4_CR38_1","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0022-2836(81)90087-5","volume":"147","author":"T Smith","year":"1981","unstructured":"T. Smith and M. Waterman. Identification of common molecular subsequences. Journal of Molecular Biology, 147(1):195\u2013197, 1981.","journal-title":"Journal of Molecular Biology"},{"key":"4_CR39_1","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1007\/BF01075212","volume":"25","author":"VG Timkovsky","year":"1990","unstructured":"V. G. Timkovsky. Complexity of common subsequence and supersequence problems and related problems. Cybernetics, 25:565\u2013580, 1990.","journal-title":"Cybernetics"}],"container-title":["Studies in Computational Intelligence","Hybrid Metaheuristics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-78295-7_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,3,17]],"date-time":"2020-03-17T19:22:19Z","timestamp":1584472939000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-78295-7_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540782940","9783540782957"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-78295-7_4","relation":{},"ISSN":["1860-949X"],"issn-type":[{"type":"print","value":"1860-949X"}],"subject":[],"published":{"date-parts":[[2008]]},"assertion":[{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}