A Hybrid Artificial Bee Colony Algorithm for Flexible Job Shop Scheduling Problems

  • Jun-qing Li School of Computer, Liaocheng University, Liaocheng Liaocheng, 252059, PR China
  • Sheng-xian Xie School of Computer, Liaocheng University, Liaocheng Liaocheng, 252059, PR China
  • Quan-ke Pan 1. School of Computer, Liaocheng University, Liaocheng Liaocheng, 252059, PR China 2. State Key Lab. of Digital Manufacturing Equipment and Technology, Huazhong University of Science and Technology Wuhan, 430074, PR China
  • Song Wang Department of Economic and Management Shandong University of Science and Technology Huangdao, 266510, PR China

Abstract

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

[1] 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

[2] 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:1<3::AID-JOS32>3.0.CO;2-Y

[3] 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

[4] 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.

[5] 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

[6] 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.

[7] 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

[8] 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

[9] 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

[10] 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.

[11] 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

[12] 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

[13] 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

[14] D. Karaboga. An idea based on honey bee swarm for numerical optimization. Technical Report TR06. Computer Engineering Department. Erciyes University. Turkey. 2005.

[15] 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

[16] 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

[17] 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

[18] 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

[19] 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

[20] 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

[21] 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

[22] L. Wang. Shop scheduling with genetic algorithms. Tsinghua university press, Beijing, China, 2003.

[23] 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

[24] 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
2011-06-01
How to Cite
LI, Jun-qing et al. A Hybrid Artificial Bee Colony Algorithm for Flexible Job Shop Scheduling Problems. INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL, [S.l.], v. 6, n. 2, p. 286-296, june 2011. ISSN 1841-9844. Available at: <http://univagora.ro/jour/index.php/ijccc/article/view/2177>. Date accessed: 08 july 2020. doi: https://doi.org/10.15837/ijccc.2011.2.2177.

Keywords

Flexbile job shop scheduling problem, artificial bee colony, multiobjective optimization, hybrid algorithm