Beam-ACO–hybridizing ant colony optimization with beam search: an application to open shop scheduling. (English) Zbl 1122.90427

Summary: Ant colony optimization (ACO) is a metaheuristic approach to tackle hard combinatorial optimization problems. The basic component of ACO is a probabilistic solution construction mechanism. Due to its constructive nature, ACO can be regarded as a tree search method. Based on this observation, we hybridize the solution construction mechanism of ACO with beam search, which is a well-known tree search method. We call this approach Beam-ACO. The usefulness of Beam-ACO is demonstrated by its application to open shop scheduling (OSS). We experimentally show that Beam-ACO is a state-of-the-art method for OSS by comparing the obtained results to the best available methods on a wide range of benchmark instances.


90C59 Approximation methods and heuristics in mathematical programming
90B35 Deterministic scheduling theory in operations research
Full Text: DOI


[1] Papadimitriou, C.H.; Steiglitz, K., Combinatorial optimization—algorithms and complexity, (1982), Dover Publications New York · Zbl 0503.90060
[2] Ginsberg, M., Essentials of artificial intelligence, (1993), Morgan Kaufmann Publishers San Mateo, CA
[3] Aarts E, Lenstra JK, editors. Local search in combinatorial optimization. Series in Discrete Mathematics and Optimization. Chichester, UK: Wiley; 1997. · Zbl 0869.00019
[4] Pinedo, M., Scheduling: theory, algorithms, and systems, (1995), Prentice-Hall Englewood Cliffs · Zbl 1145.90393
[5] Glover F, Kochenberger G, editors. Handbook of metaheuristics. Boston, MA: Kluwer Academic Publishers; 2003. · Zbl 1058.90002
[6] Blum, C.; Roli, A., Metaheuristics in combinatorial optimizationoverview and conceptual comparison, ACM computing surveys, 35, 3, 268-308, (2003)
[7] Glover, F.; Laguna, M., Tabu search, (1997), Kluwer Academic Publishers Boston, MA · Zbl 0930.90083
[8] Kirkpatrick, S.; Gelatt, C.D.; Vecchi, M.P., Optimization by simulated annealing, Science, 220, 4598, 671-680, (1983) · Zbl 1225.90162
[9] Lourenço HR, Martin O, Stützle T. Iterated local search, In: Glover F, Kochenberger G, editors, Handbook of metaheuristics, International series in operations research & management Science, vol. 57, Norwell, MA: Kluwer Academic Publishers; 2002. p. 321-53.
[10] Resende, M.G.C.; Ribeiro, C.C., Greedy randomized adaptive search procedures, (), p219-p250
[11] Focacci F, Laburthe F, Lodi A. Local search and constraint programming. In: Glover F, Kochenberger G, editors, Handbook of metaheuristics, Boston, MA, Kluwer Academic Publishers; 2003, p. 369-404. · Zbl 1137.90729
[12] Dorigo, M.; Di Caro, G., The ant colony optimization meta-heuristic, (), p11-p32
[13] Dorigo M, Stützle T. Ant colony optimization. Boston, MA: MIT Press; 2004. · Zbl 1092.90066
[14] Ow, P.S.; Morton, T.E., Filtered beam search in scheduling, International journal of production research, 26, 297-307, (1988)
[15] Blum C. An ant colony optimization algorithm to tackle shop scheduling problems Technical Report TR/IRIDIA/2003-01, IRIDIA, Université Libre de Bruxelles, Belgium; 2003.
[16] Liaw, C.-.F., A hybrid genetic algorithm for the open shop scheduling problem, European journal of operational research, 124, 28-42, (2000) · Zbl 0960.90039
[17] Prins, C., Competitive genetic algorithms for the open-shop scheduling problem, Mathematical methods of operations research, 52, 3, 389-411, (2000) · Zbl 1023.90030
[18] Maniezzo, V., Exact and approximate nondeterministic tree-search procedures for the quadratic assignment problem, INFORMS journal on computing, 11, 4, 358-369, (1999) · Zbl 1034.90526
[19] Maniezzo, V.; Milandri, M., An ant-based framework for very strongly constrained problems, (), p222-p227
[20] Birattari, M.; Di Caro, G.; Dorigo, M., Toward a formal foundation of ant programming, (), p188-p201
[21] Bertsekas DP. Dynanmic programming and optimal control, vol. 1. Belmont, MA: Athena Scientific; 1995.
[22] Dorigo M, Maniezzo V, Colorni A. Positive feedback as a search strategy. Technical Report 91-016, Dipartimento di Elettronica, Politecnico di Milano, Italy; 1991. · Zbl 0825.90549
[23] Dorigo M. Optimization, learning and natural algorithms. PhD thesis, Dipartimento di Elettronica, Politecnico di Milano, Italy; 1992. 140p. (in Italian)
[24] Dorigo, M.; Maniezzo, V.; Colorni, A., Ant system: optimization by a colony of cooperating agents, IEEE transactions on systems, man and cybernetics—part B, 26, 1, 29-41, (1996)
[25] den Besten ML, Stützle T, Dorigo M. Design of iterated local search algorithms: An example application to the single machine total weighted tardiness problem. In: Proceedings of EvoStim’01, Lecture Notes in Computer Science, Berlin: Springer; 2001, p. 441-52. · Zbl 0978.68750
[26] Merkle, D.; Middendorf, M.; Schmeck, H., Ant colony optimization for resource-constrained project scheduling, IEEE transactions on evolutionary computation, 6, 4, 333-346, (2000)
[27] Colorni, A.; Dorigo, M.; Maniezzo, V.; Trubian, M., Ant system for job-shop scheduling, Belgian journal of operations research, statistics and computer science, 34, 1, 39-54, (1993) · Zbl 0814.90047
[28] Sampels M, Blum C, Mastrolilli M, Rossi-Doria O. Metaheuristics for group shop scheduling. In: Merelo Guervós JJ, et al., editor, Proceedings of PPSN-VII, Seventh International Conference on Parallel Problem Solving from Nature, Lecture Notes in Computer Science, vol. 2439. Berlin, Germany: Springer; 2002. p. 631-40.
[29] Giffler, B.; Thompson, G.L., Algorithms for solving production scheduling problems, Operations research, 18, 487-503, (1960) · Zbl 0248.90022
[30] Blum C, Roli A, Dorigo M. HC-ACO: The hyper-cube framework for ant colony optimization. In: Proceedings of MIC’2001—Meta-heuristics International Conference, vol. 2, Porto, Portugal; 2001, p. 399-403.
[31] Blum C, Dorigo M. The hyper-cube framework for ant colony optimization. IEEE Transactions on Systems, Man and Cybernetics—Part B; to appear. Also available as Technical Report TR/IRIDIA/2003-03, IRIDIA, Université Libre de Bruxelles, Belgium; 2003.
[32] Stützle, T.; Hoos, H.H., \(MAX\)-\(MIN\) ant system, Future generation computer systems, 16, 8, 889-914, (2000)
[33] Harvey WD, Ginsberg ML. Limited discrepancy search. In: Mellish CS, editor, Proceedings of the 14th International Joint Conference on Artificial Intelligence, IJCAI’95, vol. 1. Montréal, Québec, Canada, Los Altos, CA: Morgan Kaufmann; 1995, p. 607-15.
[34] Taillard, E., Benchmarks for basic scheduling problems, European journal of operations research, 64, 278-285, (1993) · Zbl 0769.90052
[35] Brucker, P.; Hurink, J.; Jurisch, B.; Wöstmann, B., A branch & bound algorithm for the open-shop problem, Discrete applied mathematics, 76, 43-59, (1997) · Zbl 0882.90066
[36] Guéret, C.; Prins, C., A new lower bound for the open-shop problem, Annals of operations research, 92, 165-183, (1999) · Zbl 0958.90033
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.