A hybrid variable neighborhood search for solving the hybrid flow shop scheduling problem

被引:69
作者
Li, Jun-qing [1 ,2 ]
Pan, Quan-ke [1 ,2 ]
Wang, Fa-tao [2 ,3 ]
机构
[1] Northeastern Univ, State Key Lab Synthet Automat Proc Ind, Shenyang 110819, Peoples R China
[2] Liaocheng Univ, Coll Comp Sci, Liaocheng 252059, Peoples R China
[3] Beijing Univ Posts & Telecommun, Sch Econ & Management, Beijing 100876, Peoples R China
基金
美国国家科学基金会;
关键词
Hybrid flow shop scheduling problem; Chemical-reaction optimization; Estimation of distribution; Variable neighborhood search; DEPENDENT SETUP TIMES; CHEMICAL-REACTION OPTIMIZATION; DISTRIBUTION ALGORITHM; GENETIC ALGORITHM; IMMUNE ALGORITHM; BOUND ALGORITHM; 2-STAGE; SYSTEM; FLOWSHOPS; BRANCH;
D O I
10.1016/j.asoc.2014.07.005
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
This paper proposes a hybrid variable neighborhood search (HVNS) algorithm that combines the chemical-reaction optimization (CRO) and the estimation of distribution (EDA), for solving the hybrid flow shop (HFS) scheduling problems. The objective is to minimize the maximum completion time. In the proposed algorithm, a well-designed decoding mechanism is presented to schedule jobs with more flexibility. Meanwhile, considering the problem structure, eight neighborhood structures are developed. A kinetic energy sensitive neighborhood change approach is proposed to extract global information and avoid being stuck at the local optima. In addition, contrary to the fixed neighborhood set in traditional VNS, a dynamic neighborhood set update mechanism is utilized to exploit the potential search space. Finally, for the population of local optima solutions, an effective EDA-based global search approach is investigated to direct the search process to promising regions. The proposed algorithm is tested on sets of well-known benchmark instances. Through the analysis of experimental results, the high performance of the proposed HVNS algorithm is shown in comparison with four efficient algorithms from the literature. (C) 2014 Elsevier B.V. All rights reserved.
引用
收藏
页码:63 / 77
页数:15
相关论文
共 51 条
[1]   Parallel variable neighborhood search for solving fuzzy multi-objective dynamic facility layout problem [J].
Abedzadeh, Mostafa ;
Mazinani, Mostafa ;
Moradinasab, Nazanin ;
Roghanian, Emad .
INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY, 2013, 65 (1-4) :197-211
[2]   Using ant colony optimization to solve hybrid flow shop scheduling problems [J].
Alaykyran, Kemal ;
Engin, Orhan ;
Doyen, Alper .
INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY, 2007, 35 (5-6) :541-550
[3]   Solving the n-job 3-stage flexible flowshop scheduling problem using an agent-based approach [J].
Babayan, A ;
He, D .
INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2004, 42 (04) :777-799
[4]   Parallel-machine scheduling problems with sequence-dependent setup times using an ACO, SA and VNS hybrid algorithm [J].
Behnamian, J. ;
Zandieh, M. ;
Ghomi, S. M. T. Fatemi .
EXPERT SYSTEMS WITH APPLICATIONS, 2009, 36 (06) :9637-9644
[5]   A variable neighborhood search approach for planning and scheduling of jobs on unrelated parallel machines [J].
Bilyk, Andrew ;
Moench, Lars .
JOURNAL OF INTELLIGENT MANUFACTURING, 2012, 23 (05) :1621-1635
[6]   BRANCH AND BOUND ALGORITHM FOR THE FLOW-SHOP WITH MULTIPLE PROCESSORS [J].
BRAH, SA ;
HUNSUCKER, JL .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1991, 51 (01) :88-99
[7]   An exact method for solving the multi-processor flow-shop [J].
Carlier, J ;
Néron, E .
RAIRO-RECHERCHE OPERATIONNELLE-OPERATIONS RESEARCH, 2000, 34 (01) :1-25
[8]   Variable neighborhood search approaches for scheduling jobs on parallel machines with sequence-dependent setup times, precedence constraints, and ready times [J].
Driessel, Rene ;
Moench, Lars .
COMPUTERS & INDUSTRIAL ENGINEERING, 2011, 61 (02) :336-345
[9]   Variable neighborhood search for the Vertex Separation Problem [J].
Duarte, Abraham ;
Escudero, Laureano F. ;
Marti, Rafael ;
Mladenovic, Nenad ;
Jose Pantrigo, Juan ;
Sanchez-Oro, Jesus .
COMPUTERS & OPERATIONS RESEARCH, 2012, 39 (12) :3247-3255
[10]   A new approach to solve hybrid flow shop scheduling problems by artificial immune system [J].
Engin, O ;
Döyen, A .
FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE, 2004, 20 (06) :1083-1095