An effective new island model genetic algorithm for job shop scheduling problem

被引:83
|
作者
Kurdi, Mohamed [1 ]
机构
[1] Adnan Menderes Univ, Dept Comp Engn, TR-09010 Aydin, Turkey
关键词
Job shop scheduling; Island model; Parallel genetic algorithm; Evolutionary computation; SEARCH ALGORITHM; OPTIMIZATION;
D O I
10.1016/j.cor.2015.10.005
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
This paper presents an effective new island model genetic algorithm to solve the well-known job shop scheduling problem with the objective of minimizing the makespan. To improve the effectiveness of the classical island model genetic algorithm, we have proposed a new naturally inspired evolution model and a new naturally inspired migration selection mechanism that are capable of improving the search diversification and delaying the premature convergence. In the proposed evolution model, islands employ different evolution methods during their self-adaptation phases, rather than employing the same methods. In the proposed migration selection mechanism, worst individuals who are least adapted to their environments migrate first, hoping in finding a better chance to live in a more suitable environment that imposes a more suitable self-adaptation method on them. The proposed algorithm is tested on 52 benchmark instances, with the proposed evolution model and migration selection mechanism, and without them using the classical alternatives, and also compared with other algorithms recently reported in the literature. Computational results verify the improvements achieved by the proposed evolution model and migration selection mechanism, and show the superiority of the proposed algorithm over the others in terms of effectiveness. (C) 2015 Elsevier Ltd. All rights reserved.
引用
收藏
页码:132 / 142
页数:11
相关论文
共 50 条
  • [2] An effective hybrid genetic algorithm for the job shop scheduling problem
    Chaoyong Zhang
    Yunqing Rao
    Peigen Li
    The International Journal of Advanced Manufacturing Technology, 2008, 39 : 965 - 974
  • [3] An effective hybrid genetic algorithm for the job shop scheduling problem
    Zhang, Chaoyong
    Rao, Yunqing
    Li, Peigen
    INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY, 2008, 39 (9-10): : 965 - 974
  • [4] An effective asexual genetic algorithm for solving the job shop scheduling problem
    Amirghasemi, Mehrdad
    Zamani, Reza
    COMPUTERS & INDUSTRIAL ENGINEERING, 2015, 83 : 123 - 138
  • [5] An effective genetic algorithm for the flexible job-shop scheduling problem
    Zhang, Guohui
    Gao, Liang
    Shi, Yang
    EXPERT SYSTEMS WITH APPLICATIONS, 2011, 38 (04) : 3563 - 3573
  • [6] A new hybrid genetic algorithm for job shop scheduling problem
    Ren Qing-dao-er-ji
    Wang, Yuping
    COMPUTERS & OPERATIONS RESEARCH, 2012, 39 (10) : 2291 - 2299
  • [7] An effective genetic algorithm for job shop scheduling
    Wang, W
    Brunn, P
    PROCEEDINGS OF THE INSTITUTION OF MECHANICAL ENGINEERS PART B-JOURNAL OF ENGINEERING MANUFACTURE, 2000, 214 (04) : 293 - 300
  • [8] A new immune genetic algorithm for job shop scheduling problem
    Ren, Qing-Dao-Er-Ji
    Wang, Yuping
    Journal of Computational Information Systems, 2013, 9 (03): : 1011 - 1018
  • [9] A Parallel Genetic Algorithm for the Job Shop Scheduling Problem
    Nguyen Huu Mui
    Vu Dinh Hoa
    Luc Tri Tuyen
    2012 IEEE INTERNATIONAL SYMPOSIUM ON SIGNAL PROCESSING AND INFORMATION TECHNOLOGY (ISSPIT), 2012, : 19 - 24
  • [10] A hybrid genetic algorithm for the job shop scheduling problem
    Gonçalves, JF
    Mendes, JJDM
    Resende, MGC
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2005, 167 (01) : 77 - 95