Industrial applications of the ant colony optimization algorithm

被引:2
作者
Bud Fox
Wei Xiang
Heow Pueh Lee
机构
[1] Institute of High Performance Computing,Department of Mechanical Engineering
[2] National University of Singapore,undefined
来源
The International Journal of Advanced Manufacturing Technology | 2007年 / 31卷
关键词
Ant colony optimization; Combinatorial optimization; Hybrid algorithms; Job shop scheduling problem; Node-arc graphs; Traveling salesperson problem;
D O I
暂无
中图分类号
学科分类号
摘要
The ant colony optimization (ACO) algorithm is a fast suboptimal meta-heuristic based on the behavior of a set of ants that communicate through the deposit of pheromone. It involves a node choice probability which is a function of pheromone strength and inter-node distance to construct a path through a node-arc graph. The algorithm allows fast near optimal solutions to be found and is useful in industrial environments where computational resources and time are limited. A hybridization using iterated local search (ILS) is made in this work to the existing heuristic to refine the optimality of the solution. Applications of the ACO algorithm also involve numerous traveling salesperson problem (TSP) instances and benchmark job shop scheduling problems (JSSPs), where the latter employs a simplified ant graph-construction model to minimize the number of edges for which pheromone update should occur, so as to reduce the spatial complexity in problem computation.
引用
收藏
页码:805 / 814
页数:9
相关论文
共 25 条
[1]  
Blum C(2005)Beam-ACO – hybridizing ant colony optimization with beam search: an application to open shop scheduling Comput Oper Res 32 1565-1591
[2]  
Blum C(2004)The hyper-cube framework for ant colony optimization IEEE Trans Syst, Man Cybern Part B 34 1161-1172
[3]  
Dorigo M(2004)An ant colony optimization algorithm for shop scheduling problems J Math Model Algorithms 3 285-308
[4]  
Blum C(1994)Ant system for job-shop scheduling Belgian J Oper Res, Stats Comput Sci 34 39-53
[5]  
Sampels M(1996)The job shop scheduling problem: conventional and new solution techniques Eur J Operl Res 93 1-33
[6]  
Colorni A(1960)Algorithms for solving production-scheduling problems Oper Res 8 487-503
[7]  
Dorigo M(1991)A computational study of the job-shop scheduling problem Oper Res Soc Am J Comput 3 149-156
[8]  
Maniezzo V(1996)The ant system: optimization by a colony of cooperating agents IEEE Trans Syst, Man Cybern-Part B 26 29-41
[9]  
Trubian M(1997)A new rank based version of the ant system – a computational study Central Eur J Oper Res Econ 7 25-38
[10]  
Blazewicz J(1991)Maintenance scheduling by using simulated annealing IEEE Trans Power Syst 6 850-857