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

Blum, Christian

Comput. Oper. Res. 32, No. 6, 1565-1591 (2004).

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.

MSC:

90C59	Approximation methods and heuristics in mathematical programming
90B35	Deterministic scheduling theory in operations research

Keywords:

Ant colony optimization; Beam search; Tree search; Open shop scheduling

Software:

HC-ACO; Tabu search; Beam-ACO

References:

[1]	Papadimitriou, C. H.; Steiglitz, K., Combinatorial optimization—algorithms and complexity (1982), Dover Publications: Dover Publications New York · Zbl 0503.90060
[2]	Ginsberg, M., Essentials of artificial intelligence (1993), Morgan Kaufmann Publishers: Morgan Kaufmann Publishers San Mateo, CA
[4]	Pinedo, M., Scheduling: theory, algorithms, and systems (1995), Prentice-Hall: Prentice-Hall Englewood Cliffs · Zbl 1145.90393
[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: 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
[10]	Resende, M. G.C.; Ribeiro, C. C., Greedy randomized adaptive search procedures, (Glover, F.; Kochenberger, G., Handbook of metaheuristics (2003), Kluwer Academic Publishers: Kluwer Academic Publishers Boston, MA), p219-p250 · Zbl 1102.90384
[12]	Dorigo, M.; Di Caro, G., The ant colony optimization meta-heuristic, (Corne, D.; Dorigo, M.; Glover, F., New ideas in optimization (1999), McGraw Hill: McGraw Hill London, UK), p11-p32
[14]	Ow, P. S.; Morton, T. E., Filtered beam search in scheduling, International Journal of Production Research, 26, 297-307 (1988)
[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, (Dorigo, M.; Di Caro, G.; Sampels, M., Proceedings of ANTS2002—From Ant Colonies to Artificial Ants: Third International Workshop on Ant Algorithms. Proceedings of ANTS2002—From Ant Colonies to Artificial Ants: Third International Workshop on Ant Algorithms, Lecture Notes in Computer Science, vol. 2463 (2002), Springer: Springer Berlin, Germany), p222-p227
[20]	Birattari, M.; Di Caro, G.; Dorigo, M., Toward a formal foundation of ant programming, (Dorigo, M.; Di Caro, G.; Sampels, M., Proceedings of ANTS 2002—Third International Workshop on Ant Algorithms. Proceedings of ANTS 2002—Third International Workshop on Ant Algorithms, Lecture Notes in Computer Science, vol. 2463 (2002), Springer: Springer Berlin, Germany), p188-p201
[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)
[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
[29]	Giffler, B.; Thompson, G. L., Algorithms for solving production scheduling problems, Operations Research, 18, 487-503 (1960) · Zbl 0248.90022
[32]	Stützle, T.; Hoos, H. H., \(MAX-MIN\) ant system, Future Generation Computer Systems, 16, 8, 889-914 (2000)
[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