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

Jun-qing Li, Sheng-xian Xie, Quan-ke Pan, Song Wang

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.


Keywords


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

Full Text:

PDF

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:1<3::AID-JOS32>3.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.




DOI: https://doi.org/10.15837/ijccc.2011.2.2177



Copyright (c) 2017 Jun-qing Li, Sheng-xian Xie, Quan-ke Pan, Song Wang

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

CC-BY-NC  License for Website User

Articles published in IJCCC user license are protected by copyright.

Users can access, download, copy, translate the IJCCC articles for non-commercial purposes provided that users, but cannot redistribute, display or adapt:

  • Cite the article using an appropriate bibliographic citation: author(s), article title, journal, volume, issue, page numbers, year of publication, DOI, and the link to the definitive published version on IJCCC website;
  • Maintain the integrity of the IJCCC article;
  • Retain the copyright notices and links to these terms and conditions so it is clear to other users what can and what cannot be done with the  article;
  • Ensure that, for any content in the IJCCC article that is identified as belonging to a third party, any re-use complies with the copyright policies of that third party;
  • Any translations must prominently display the statement: "This is an unofficial translation of an article that appeared in IJCCC. Agora University  has not endorsed this translation."

This is a non commercial license where the use of published articles for commercial purposes is forbiden. 

Commercial purposes include: 

  • Copying or downloading IJCCC articles, or linking to such postings, for further redistribution, sale or licensing, for a fee;
  • Copying, downloading or posting by a site or service that incorporates advertising with such content;
  • The inclusion or incorporation of article content in other works or services (other than normal quotations with an appropriate citation) that is then available for sale or licensing, for a fee;
  • Use of IJCCC articles or article content (other than normal quotations with appropriate citation) by for-profit organizations for promotional purposes, whether for a fee or otherwise;
  • Use for the purposes of monetary reward by means of sale, resale, license, loan, transfer or other form of commercial exploitation;

    The licensor cannot revoke these freedoms as long as you follow the license terms.

[End of CC-BY-NC  License for Website User]


INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL (IJCCC), With Emphasis on the Integration of Three Technologies (C & C & C),  ISSN 1841-9836.

IJCCC was founded in 2006,  at Agora University, by  Ioan DZITAC (Editor-in-Chief),  Florin Gheorghe FILIP (Editor-in-Chief), and  Misu-Jan MANOLESCU (Managing Editor).

Ethics: This journal is a member of, and subscribes to the principles of, the Committee on Publication Ethics (COPE).

Ioan  DZITAC (Editor-in-Chief) at COPE European Seminar, Bruxelles, 2015:

IJCCC is covered/indexed/abstracted in Science Citation Index Expanded (since vol.1(S),  2006); JCR2018: IF=1.585..

IJCCC is indexed in Scopus from 2008 (CiteScore2018 = 1.56):

Nomination by Elsevier for Journal Excellence Award Romania 2015 (SNIP2014 = 1.029): Elsevier/ Scopus

IJCCC was nominated by Elsevier for Journal Excellence Award - "Scopus Awards Romania 2015" (SNIP2014 = 1.029).

IJCCC is in Top 3 of 157 Romanian journals indexed by Scopus (in all fields) and No.1 in Computer Science field by Elsevier/ Scopus.

 

 Impact Factor in JCR2018 (Clarivate Analytics/SCI Expanded/ISI Web of Science): IF=1.585 (Q3). Scopus: CiteScore2018=1.56 (Q2); Editors-in-Chief: Ioan DZITAC & Florin Gheorghe FILIP.