Comparison of firefly and cockroach algorithms in selected discrete and combinatorial problems

• Autorzy: Kwiecień J. , Filipowicz B.

Identyfikatory

DOI

10.2478/bpasts-2014-0087

• Języki publikacji: EN

Abstrakty

EN

In recent years, newer algorithms inspired by nature have been created and used to solve various problems. Therefore, in the paper we present the application of firefly and cockroach algorithms to optimize two queueing systems and permutation flow shop problems with the objective of minimizing the makespan. The article briefly describes these algorithms to solve selected problems and their results. Because these algorithms were originally developed for continuous optimization problems, we introduce a new formula to transform the position of ith individual to solve the discrete problems.

Słowa kluczowe

EN

queueing systems; flow shop scheduling; firefly algorithm; cockroach algorithm

PL

systemy kolejkowe; planowanie przepływów; algorytm świetlika; algorytm karaluch

• Wydawca: Polska Akademia Nauk, Wydział IV Nauk Technicznych
• Czasopismo: Bulletin of the Polish Academy of Sciences. Technical Sciences
• Rocznik: 2014
• Tom: Vol. 62, nr 4
• Strony: 797--804
• Opis fizyczny: Bibliogr. 26, tab.

Twórcy

autor

Kwiecień J.

• AGH University of Science and Technology, 30 Mickiewicza Ave., 30-059 Krakow, Poland

autor

Filipowicz B.

• AGH University of Science and Technology, 30 Mickiewicza Ave., 30-059 Krakow, Poland

Bibliografia

• [1] J. Kennedy and R. Eberhart, “Particle swarm optimization”, Proc. IEEE Int. Conf. on Neural Networks 4, 1942-1948 (1995).
• [2] M. Dorigo, “Optimization, learning and natural algorithms”, PhD Thesis, Politecnico di Milano, Milano, 1992.
• [3] M. Dorigo and L.M. Gambardella, “Ant colony system: a cooperative learning approach to the traveling salesman problem”, IEEE Trans. on Evolutionary Computation 1 (1), 53-66 (1997).
• [4] D.T. Pham, A. Ghanbarzadeh, E. Koc, S. Otri, S. Rahim, and M. Zaidi, “The bees algorithm - a novel tool for complex optimisation problems”, in Technical Note, Manufacturing Engineering Centre, Cardiff University, Cardiff, 2005.
• [5] B. Basturk and D. Karaboga, “An artificial bee colony (ABC) algorithm for numeric function optimization”, Proc. IEEE Swarm Intelligence Symp. 1, CD-ROM (2006).
• [6] D. Karaboga and B. Basturk, “A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm”, J. Global Optimization 39 (3), 459-471 (2007).
• [7] X.S. Yang, Nature-Inspired Metaheuristic Algorithms, Luniver Press, Frome, 2008.
• [8] Z. Chen and H. Tang, “Cockroach swarm optimization”, II Int. Conf. on Computer Engineering and Technology 6, 652-655 (2010).
• [9] S. Łukasik and S. Żak, “Firefly algorithm for continuous constrained optimization task”, Computational Collective Intelligence. Semantic Web, Social Networks and Multiagent Systems LNCS 5796, 97-106 (2009).
• [10] Z. Chen, “A modified cockroach swarm optimization”, Energy Procedia 11, 4-9 (2011).
• [11] L. Cheng, Z. Wang, S. Yanhong, and A. Guo, “Cockroach swarm optimization algorithm for TSP”, Advanced Engineering Forum 1, 226-229 (2011).
• [12] C. Smutnicki, Scheduling Algorithms, Exit, Warsaw, 2002, (in Polish).
• [13] B. Filipowicz, Operational Research. Selected Methods and Algorithms. Part 1, F.H.U. Poldex, Cracow, 1999, (in Polish).
• [14] G. Bolch, S. Greiner, H. de Meer, and K.S. Trivedi, Queueing Networks and Markov Chains. Modeling and Performance Evaluation with Computer Science Applications, Wiley, New York, 1998.
• [15] B. Filipowicz, Modelling and Optimization of Queueing Systems. Part 1. Markov Systems, F.H.U. Poldex, Cracow, 1999, (in Polish).
• [16] J. Kwiecień and B. Filipowicz, “Firefly algorithm in optimization of queueing systems”, Bull. Pol. Ac.: Tech. 60 (2), 363-368 (2012).
• [17] R. Ruiz and C. Maroto, “A comprehensive review and evaluation of permutation flowshop heuristics”, Eur. J. Operational Research 165 (2), 479-494 (2005).
• [18] S.R. Hejazi and S. Saghafian, “Flowshop-scheduling problems with makespan criterion: a review”, Int. J. Production Research 43 (14), 2895-2929 (2005).
• [19] M. Ben-Daya and M. Al-Fawzan, “A tabu search approach for the flow shop scheduling problem”, Eur. J. Operational Research 109 (1), 88-95 (1998).
• [20] J. Grabowski and M. Wodecki, “A very fast tabu search algorithm for the permutation flow shop problem with makespan criterion”, Computers & Operations Research 31 (11), 1891-1909 (2004).
• [21] E. Nowicki and C. Smutnicki, “A fast search algorithm for the permutation flow-shop problem”, Eur. J. Operational Research 91 (1), 160-175 (1996).
• [22] Z. Lian, X. Gu, and B. Jiao, “A similar particle swarm optimization algorithm for permutation flowshop scheduling to minimize makespan”, Applied Mathematics and Computation 175 (1), 773-785 (2006).
• [23] C. Rajendran and H. Ziegler, “Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs”, Eur. J. Operational Research 155 (2), 426-438 (2004).
• [24] M.K. Sayadi, R. Ramezanian, and N. Ghaffari-Nasab, “A discrete firefly meta-heuristic with local search for makespan minimization in permutation flow shop scheduling problems”, Int. J. Industrial Engineering Computations 1 (1), 1-10 (2010).
• [25] E. Taillard, “Benchmarks for basic scheduling problems”, Eur. J. Operational Research 64 (2), 278-285 (1993).
• [26] Ch.H. Lin and J.Ch. Ke, “Optimization analysis for an infinite capacity queueing system with multiple queue-dependent servers: genetic algorithms”, Int. J. Computer Mathematics 88 (7), 1430-1442 (2011).