Username   Password       Forgot your password?  Forgot your username? 

A Variable Neighborhood Migrating Birds Optimization Algorithm for Flexible Job Shop Scheduling

Volume 13, Number 7, November 2017 - Paper 3  - pp. 1020-1029
DOI: 10.23940/ijpe.17.07.p3.10201029

Hongchan Lia, Bangqin Caob, Haodong Zhua,*

aSchool of Computer and Communication Engineering, Zhengzhou University of Light Industry, Zhengzhou, Henan, 450002, China
bXinyang Vocational and Technical College, Xinyang, Henan, 464000, China

(Submitted on July 24, 2017; Revised on October 13, 2017; Accepted on October 21, 2017)


A hybrid meta-heuristic named variable neighborhood migrating birds optimization (VNMBO), which is a combination of variable neighborhood search (VNS) and migrating birds optimization (MBO). The main aim of this paper is to provide a new way for MBO to solve the flexible job shop scheduling problem (FJSP). A two-stage population initialization scheme was first adopted to improve the quality of the initial solutions. An individual leaping mechanism was introduced to the algorithm in order to avoid the premature convergence. To search the solution space effectively, three neighborhood structures were designed and a VNS was developed to enhance the local searching ability. Finally, to assess the performance of the proposed VNMBO, some published algorithms were compared by using two famous benchmark data sets. The comparison results show that the proposed VNMBO is effective for solving the FJSP with the objective of minimizing the makespan.


References: 19

        1. P. Brandimarte, “Routing and scheduling in a flexible job shop by tabu search”, Annals of Operations research, vol.41, no.3, pp. 157-183, 1993.
        2. Y. Demir, S. K. İşleyen, “An effective genetic algorithm for flexible job-shop scheduling with overlapping in operations”, International Journal of Production Research, vol.52, no.13, pp. 3905-3921, 2014.
        3. E. Duman, M. Uysal, A. F. Alkaya, “Migrating Birds Optimization: A new metaheuristic approach and its performance on quadratic assignment problem”, Information Sciences, vol.217, pp. 65-77, 2012.
        4. L. Gao, Q. K. Pan, “A shuffled multi-swarm micro-migrating birds optimizer for a multi-resource-constrained flexible job shop scheduling problem”, Information Sciences, vol.372, pp.655-676, 2016.
        5. S. M. Johnson, “Optimal two- and three-stage production schedules with setup times included”, Naval research logistics quarterly, vol.1, no.1, pp.61-68, 1954.
        6. I. Kacem, S. Hammadi, P. Borne, “Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems”, Systems, Man, and Cybernetics, Part C: Applications and Reviews, IEEE Transactions on, vol.32, no.1, pp.1-13, 2002.
        7. I. Kacem, S. Hammadi, 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, no.3, pp.245-276, 2002.
        8. D. Lei, X. Guo, “Variable neighbourhood search for dual-resource constrained flexible job shop scheduling”, International Journal of Production Research, vol.52, no.9, pp.2519-2529, 2014.
        9. J. Li, Q. K. Pan, S. X. Xie, “A hybrid particle swarm optimization and tabu search algorithm for flexible job-shop scheduling problem”,International Journal of Computer Theory and Engineering, vol.2, no.2, pp.1793-1801, 2010.
        10. T. Meng, Q. K. Pan, J. Q. Li,“An improved migrating birds optimization for an integrated lot-streaming flow shop scheduling problem”, Swarm and Evolutionary Computation, in press, 2017.
        11. M. Nouiri, A. Bekrar, A. Jemai, “An effective and distributed particle swarm optimization algorithm for flexible job-shop scheduling problem”, Journal of Intelligent Manufacturing, 2015. doi: 10.1007/s10845-015-1039-3.
        12. Q. K. Pan, Y. Dong, “An improved migrating birds optimisation for a hybrid flowshop scheduling with total flowtime minimisation”, Information Sciences, vol.277, pp. 643-655, 2014.
        13. F. Pezzella, G. Morganti, G. Ciaschetti, “A genetic algorithm for the flexible job-shop scheduling problem”, Computers & Operations Research, vol.35, no.10, pp. 3202-3212, 2008.
        14. M. Prandtstetter, G. R. Raidl,“An integer linear programming approach and a hybrid variable neighborhood search for the car sequencing problem”, European Journal of Operational Research, vol.191, no.3, pp.1004-1022, 2008.
        15. A. Sifaleras, I. Konstantaras, N. Mladenović, “Variable neighborhood search for the economic lot sizing problem with product returns and recovery”, International Journal of Production Economics, vol.160, pp.133-143, 2015.
        16. L. Wei, Z. Zhang, D. Zhang, “A variable neighborhood search for the capacitated vehicle routing problem with two-dimensional loading constraints”, European Journal of Operational Research, vol.243, no.3, pp.798-814, 2015.
        17. Z. P. Xie, Y. Jia, C. Y. Zhang, “Migrating birds optimization for blocking flow shop scheduling with total flowtime minimization”, Computer Integrated Manufacturing Systems, vol.18, no.8, pp. 2099-2107, 2015.
        18. L. N. Xing, Y. W. Chen, P. Wang, “A knowledge-based ant colony optimization for flexible job shop scheduling problems”, Applied Soft Computing, vol.10, no.3, pp.888-896, 2010.
        19. M. Ziaee, “A heuristic algorithm for solving flexible job shop scheduling problem”, The International Journal of Advanced Manufacturing Technology, vol.71, no.4, pp.519-528, 2014.


              Click here to download the paper.

              Please note : You will need Adobe Acrobat viewer to view the full articles.Get Free Adobe Reader

              This site uses encryption for transmitting your passwords.