Open Access Open Access  Restricted Access Subscription or Fee Access

Solving Job Shop Scheduling using Pheromone Updating Strategy in Ant Colony Optimization

J. Anitha, M. Karpagam

Abstract


Scheduling is considered to be a major task to improve the shop-floor productivity. The job shop problem is under this category and is combinatorial in nature. Research on optimization of job shop problem is one of the most significant and promising areas of optimization. This paper presents an application of the Ant Colony Optimization metaheuristic to job shop problem. The main characteristics of this model are positive feedback and distributed computation. The inspiring source of Ant Colony Optimization is pheromone trail laying and following behavior of real ant. The methods of updating the pheromone have more influence in solving instances of job shop problem. An algorithm is introduced to improve the basic ant colony system by using a pheromone updating strategy. Experiments using well-known bench mark problems show that this approach improves on the performance obtained by the basic ant colony system.

Keywords


Combinatorial Optimization, Job Shop Scheduling, Ant Colony Optimization, Pheromone Updating Strategy.

Full Text:

PDF

References


Anitha J, Karpagam M, 2012. “Priority Dispatching Rules in Solving Job Shop Scheduling Using Ant Colony Optimization”, ICATRPD-2012, Coimbatore.

Garey M. R., Johnson D. S., and Sethi R., 1976. “The complexity of flow shop and job shop scheduling”, Mathematics of Operations Research 1, pp. 117 - 129.

Garey M. R., and Johnson D. S., 1979. “Computers and Intractability, A Guide to the Theory of NP-Completeness”, W.H. Freeman and Company.

Goss S., Aron S., Deneubourg J. L., and Pasteels J. M., 1990. “Self-organized shortcuts in the Argentine Ant ”, Naturwissenschaften, Springer Berlin 76, pp. 579 - 581.

Dorigo M., Maniezzo V., Colorni A.,1996. “The Ant System: Optimization by a colony of cooperating agents”, IEEE Trans. Systems, Man, Cybernetics 26, no.2, pp. 29 - 41.

Dorigo M., Gambardella L. M., 1997. “Ant colony System: A Cooperative Learning Approach to the Travelling Salesman Problem” , IEEE Trans. On Evolutionary Computation 1, no.1 (April) , pp. 53 - 66.

Colorni A., Dorigo M., Maniezzo V., 1991. “Distributed optimization by ant colonies”, In Proceedings of ECAL'91 European Conference on Artificial Life, Elsevier Publishing, Amsterdam, The Netherlands, pp. 134 - 142.

Dorigo M., Maniezzo V., Colorni A., 1992 . “An Investigation of some properties of an Ant Algorithm”, Proceedings of the Parallel Problem Solving From Nature Conference (PPSN92), Brussels, Belgium, Elsevier Publishing, pp. 509 - 520.

Dorigo M., Maniezzo V., Colorni A., 1991. “The ant system: an autocatalytic optimizing process”, Technical Report TR91-016, Politecnico di Milano.

Colorni A., Dorigo M., Maniezzo V., Trubian M., 1993. “Ant system for Job shop Scheduling”; JORBEL- Belgian Journal of Operations Research, Statistics and Computer Science, 34, pp. 39 - 53.

Ho¨lldobler B., and Wilson E . O., 1990. “The ants”, Springer-Verlag.

Beckers R., Deneubourg J. L., Goss S., 1992. “Trails and U-turns in the selection of the shortest path by the ant Lasius niger”, Journal of Theoretical Biology , pp. 397 - 415.

Dorigo M., 1992. “Optimization, Learning and Natural Algorithms”, Ph.D Thesis, Dip. Elettronica e Informazione, Politecnico di Milano, Italy.

Van Der Swaan S., and Marques C., 1999. “Ant Colony optimization for Job shop scheduling”, In Proceedings of the third workshop Genetic Algorithms and Artificial Life (GAAL 1999).

Christian Blum , Michael Samples , 2004 .“An Ant Colony Optimization Algorithm for Shop Scheduling Problems”, Journal of Mathematical Modeling and Algorithms , Kluwer Academic Publishers , Netherlands , 3 , pp. 285 - 308.

Ventresca M., and Ombuki B . M., 2004 . “Ant Colony Optimization for Job Shop Scheduling Problem”, Technical Report #CS-04-04 (February) , Canada.

Jun Zhang , Xiaomin Hu , Tan X ., Zhong J. H., and Huang Q., 2006. “Implementation of an Ant Colony Optimization technique for job shop scheduling problem”, Transactions of the Institute of Measurement and Control , 28 , No.1 , pp. 93 - 108.

Ferdinando Pezzella, Emanuela Merelli ., 2000 “A Tabu Search Method guided by Shifting Bottleneck for the Job Shop Scheduling Problem”, European Journal of Operational Research, Elsevier, Vol. 120, pp. 297-310.


Refbacks

  • There are currently no refbacks.