A Hybrid Artificial Bee Colony Algorithm for Flexible Job Shop Scheduling Problems
Keywords:
Flexbile job shop scheduling problem, artificial bee colony, multiobjective optimization, hybrid algorithmAbstract
In this paper, we propose a hybrid Pareto-based artificial bee colony (HABC) algorithm for solving the multi-objective flexible job shop scheduling problem. In the hybrid algorithm, each food sources is represented by two vectors, i.e., the machine assignment vector and the operation scheduling vector. The artificial bee is divided into three groups, namely, employed bees, onlookers, and scouts bees. Furthermore, an external Pareto archive set is introduced to record non-dominated solutions found so far. To balance the exploration and exploitation capability of the algorithm, the scout bees in the hybrid algorithm are divided into two parts. The scout bees in one part perform randomly search in the predefined region while each scout bee in another part randomly select one non-dominated solution from the Pareto archive set. Experimental results on the well-known benchmark instances and comparisons with other recently published algorithms show the efficiency and effectiveness of the proposed algorithm.
References
P. Brandimarte. Routing and scheduling in a flexible job shop by tabu search.Annals of Operations Research , Vol 22, pp. 158-183, 1993. http://dx.doi.org/10.1007/bf02023073
M. Mastrolilli and L. M. Gambardella. Effective neighborhood functions for the flexible job shop problem.Journal of Scheduling, Vol. 3(1), pp. 3-20, 2000. http://dx.doi.org/10.1002/(SICI)1099-1425(200001/02)3:13.0.CO;2-Y
J. Q. Li, Q. K. Pan, P. N. Suganthan and T. J. Chua. A hybrid tabu search algorithm with an efficient neighborhood structure for the flexible job shop scheduling problem. International Journal of Advanced Manufacturing Technology. doi: 10.1007/s00170-010-2743-y. http://dx.doi.org/10.1007/s00170-010-2743-y
L. Gao, C. Y. Peng, C. Zhou and P. G. Li. Solving flexible job shop scheduling problem using general particle swarm optimization. In Proceedings of the 36th CIE Conference on Computers & Industrial Engineering, pp. 3018-3027, 2006.
J. Q. Li, Q. K. Pan and S. X. Xie. A hybrid variable neighborhood search algorithm for solving multi-objective flexible job shop problems. ComSIS Computer Science of Software Information and System. doi: 10.2298/CSIS090608017L. http://dx.doi.org/10.2298/CSIS090608017L
N. Liouane, I. Saad, S. Hammadi and P. Borne. Ant Systems & Local Search Optimization for Flexible Job-Shop Scheduling Production. International Journal of Computers, Communications & Control, Vol. 2, pp. 174-184, 2007.
J. Gao, L. Sun and M. Gen. A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems.Computers & Operations Research, Vol. 35(9), pp. 2892-2907, 2008. http://dx.doi.org/10.1016/j.cor.2007.01.001
F. Pezzella, G. Morganti and G. Ciaschetti. A genetic algorithm for the Flexible Job-shop Scheduling Problem.Computers & Operations Research, Vol. 35, pp. 3202-3212, 2008. http://dx.doi.org/10.1016/j.cor.2007.02.014
I. Kacem, S. Hammadi and P. Borne. Pareto-optimality approach for flexible job-shop scheduling problems: hybridization of evolutionary algorithms and fuzzy logic. Mathematics and Computers in Simulation, Vol. 60, pp. 245-276, 2002a. http://dx.doi.org/10.1016/S0378-4754(02)00019-8
I. Kacem, S. Hammadi and P. Borne. Approach by localization and multi-objective evolutionary optimization for flexible job-shop scheduling problems,IEEE Transactions on Systems, Man and Cybernetics, Part C, Vol. 32(1), pp. 408-419, 2002b.
W. J. Xia and Z. M. Wu. An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems.Computers & Industrial Engineering, Vol. 48(2), pp. 409-425, 2005. http://dx.doi.org/10.1016/j.cie.2005.01.018
G. H. Zhang, X. Y. Shao, P. G. Li and L. Gao. An effective hybrid swarm optimization algorithm for multi-objective flexible job-shop scheduling problem. Computers & Industrial Engineering, Vol. 56(4), pp. 1309-1318, 2009. http://dx.doi.org/10.1016/j.cie.2008.07.021
N. B. Ho and J. C. Tay. Solving Multiple-Objective Flexible Job Shop Problems by Evolution and Local Search. IEEE Transactions on Systems, Man, and Cybernetics, Part C:Applications and Reviews, Vol. 38(5), pp. 674-685, 2008. http://dx.doi.org/10.1109/TSMCC.2008.923888
D. Karaboga. An idea based on honey bee swarm for numerical optimization. Technical Report TR06. Computer Engineering Department. Erciyes University. Turkey. 2005.
D. Karaboga and B. Basturk. A powerful and efficient algorithm for numerical function optimization: Artificial Bee Colony (ABC) algorithm.Journal of Global Optimization, Vol. 39(3), pp. 459-171, 2007. http://dx.doi.org/10.1007/s10898-007-9149-x
D. Karaboga and B. Basturk. On The performance of Artificial Bee Colony (ABC) algorithm. Applied Soft Computing, Vol. 8(1), pp. 687-697, 2008. http://dx.doi.org/10.1016/j.asoc.2007.05.007
D. Karaboga and B. Akay. A comparative study of Artificial Bee Colony Algorithm. Applied Mathematics and Computation,Vol. 214, pp. 108-132, 2009. http://dx.doi.org/10.1016/j.amc.2009.03.090
Q. K. Pan, M. F. Tasgetiren, P. N. Suganthan and T. J. Chua. A discrete artificial bee colony algorithm for the lot-streaming flow shop scheduling problem. Information Sciences. doi: 10.1016/j.ins.2009.12.025, 2010. http://dx.doi.org/10.1016/j.ins.2009.12.025
J. Q. Li, Q. K. Pan and Y.C. Liang. An effective hybrid tabu search algorithm for multiobjective flexible job shop scheduling problems. Computers & Industrial Engineering, Vol. 59, pp. 647-662, 2010b. http://dx.doi.org/10.1016/j.cie.2010.07.014
F. Pezzella, G. Morganti and G. Ciaschetti. A genetic algorithm for the Flexible Job-shop Scheduling Problem. Computers & Operations Research, Vol. 35, pp. 3202-3212, 2008. http://dx.doi.org/10.1016/j.cor.2007.02.014
Q. K. Pan, L. Wang, B. Qian. A novel differential evolution algorithm for bi-criteria no-wait flow shop scheduling problems.Computers & Operations Research, Vol. 36(8), pp. 2498 -2511, 2009. http://dx.doi.org/10.1016/j.cor.2008.10.008
L. Wang. Shop scheduling with genetic algorithms. Tsinghua university press, Beijing, China, 2003.
K. Deb, A. Paratap, S. Agarwal and T. Meyarivan. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutinary Computation, Vol. 6(2), pp. 182-197, 2002. http://dx.doi.org/10.1109/4235.996017
N. B. Ho and J. C. Tay. GENACE: An Efficient Cultural Algorithm for solving the Flexible Job-Shop Problem. In Proceedings of the IEEE Congress on Evolutionary Computation (CEC2004) Piscataway, pp.1759-1766, 2004.
Published
Issue
Section
License
ONLINE OPEN ACCES: Acces to full text of each article and each issue are allowed for free in respect of Attribution-NonCommercial 4.0 International (CC BY-NC 4.0.
You are free to:
-Share: copy and redistribute the material in any medium or format;
-Adapt: remix, transform, and build upon the material.
The licensor cannot revoke these freedoms as long as you follow the license terms.
DISCLAIMER: The author(s) of each article appearing in International Journal of Computers Communications & Control is/are solely responsible for the content thereof; the publication of an article shall not constitute or be deemed to constitute any representation by the Editors or Agora University Press that the data presented therein are original, correct or sufficient to support the conclusions reached or that the experiment design or methodology is adequate.
