[1]HAN Zhonghua,ZHU Yihang,SHI Haibo,et al.A co-evolution CGA solution for the flexible flow shop scheduling problem[J].CAAI Transactions on Intelligent Systems,2015,10(4):562-568.[doi:10.3969/j.issn.1673-4785.201503045]
Copy

A co-evolution CGA solution for the flexible flow shop scheduling problem

CAAI Transactions on Intelligent Systems[ISSN 1673-4785/CN 23-1538/TP] Volume: 10 Number of periods: 2015 4 Page number: 562-568 Column: 学术论文—智能系统 Public date: 2015-08-25
Title:
A co-evolution CGA solution for the flexible flow shop scheduling problem
Author(s):
HAN Zhonghua1; 2; 3;  ZHU Yihang1;  SHI Haibo2; 3;  LIN Shuo1;  DONG Xiaoting1
1. Faculty of Information and Control Engineering, Shenyang Jianzhu University, Shenyang 110168, China;
2. Shenyang Institute of Automation, CAS, Shenyang 110016, China;
3. Key Laboratory of Networked Control System, CAS, Shenyang 110016, China
Keywords:
bi-probabilistic models; dynamic co-evolution; optimal individual inheritance strategy; compact genetic algorithm; flexible flow shop
CLC:
TH186
DOI:
10.3969/j.issn.1673-4785.201503045
Abstract:
In order to solve the flexible flow shop scheduling problem (FFSP), a dynamic co-evolution compact genetic algorithm (DCCGA) is designed as the global optimization algorithm. In DCCGA, a probabilistic model is constructed to describe the distribution of solutions of the problem, and two modifications are incorporated in the standard compact genetic algorithm (CGA) for improving the evolutionary mechanism and individual selection method. DCCGA’s evolutionary process is led by two probabilistic models, which contains the optimal individual inheritance strategy, and communicates with each other at a certain frequency with the population genetic information. Hence, the diversity of the population genetic information is improved during the process, and also the stability of good evolutionary trend and the capacity of continuous evolution are greatly strengthened at the same time. Moreover, the suitable parameter value is suggested based on relative experiments. And, DCCGA is measured by the benchmark problems with comparison of several effective algorithm s. The results show that DCCGA is feasible for solving FFSP.
References:
[1] RUIZ R, VáZQUEZ-RODRíGUEZ J A. The hybrid flow shop scheduling problem[J]. European Journal of Operational Research, 2010, 205(1): 1-18.
[2] JOHNSON S M. Optimal two-and three-stage production schedules with setup times included[J]. Naval Research Logistics Quarterly, 1954, 1(1): 61-68.
[3] HOOGEVEEN J A, LENSTRA J K, VELTMAN B. Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hard[J]. European Journal of Operational Research, 1996, 89(1): 172-175.
[4] SRISKANDARAJAH C, SETHI S P. Scheduling algorithms for flexible flowshops: worst and average case performance[J]. European Journal of Operational Research, 1989, 43(2): 143-160.
[5] ENGIN O, CERAN G, YILMAZ M K. An efficient genetic algorithm for hybrid flow shop scheduling with multiprocessor task problems[J]. Applied Soft Computing, 2011, 11(3): 3056-3065.
[6] SINGH M R, MAHAPATRA S S. A swarm optimization approach for flexible flow shop scheduling with multiprocessor tasks[J]. The International Journal of Advanced Manufacturing Technology, 2012, 62(1/2/3/4): 267-277.
[7] XU Y, WANG L, WANG S Y, et al. An effective immune algorithm based on novel dispatching rules for the flexible flow-shop scheduling problem with multiprocessor tasks[J]. The International Journal of Advanced Manufacturing Technology, 2013, 67(1/2/3/4): 121-135.
[8] 王圣尧, 王凌, 许烨. 求解相同并行机混合流水线车间调度问题的分布估计算法[J]. 计算机集成制造系统, 2013, 19(6): 1304-1312. WANG Shengyao, WANG Ling, XU Ye. Estimation of distribution algorithm for solving hybrid flow-shop scheduling problem with identical parallel machine [J]. Computer Integrated Manufacturing Systems, 2013, 19 (6): 1304-1312.
[9] 王圣尧, 王凌, 方晨,等. 分布估计算法研究进展 [J]. 控制与决策, 2012, 27(7): 961-966, 974. WANG Shengyao, WANG Ling, FANG Chen, et al. Advances in estimation of distribution algorithms [J]. Control and Decision, 2012, 27(7): 961-966, 974.
[10] HARIK G R, LOBO F G, GOLDBERG D E. The compact genetic algorithm[J]. IEEE Transactions on Evolutionary Computation, 1999, 3(4): 287-297.
[11] DELAOSSA L, GáMEZ J A, MATEO J L, et al. Avoiding premature convergence in estimation of distribution algorithms[C]//IEEE Congress on Evolutionary Computation, 2009. Trondheim: IEEE, 2009: 455-462.
[12] LEE J Y, KIM M S, LEE J J. Compact Genetic Algorithms using belief vectors[J]. Applied Soft Computing, 2011, 11(4): 3385-3401.
[13] GALLAGHER J C, VIGRAHAM S, KRAMER G. A family of compact genetic algorithms for intrinsic evolvable hardware[J]. IEEE Transactions on Evolutionary Computation, 2004, 8(2): 111-126.
[14] MORENO-ARMENDáRIZ M A, CRUZ-CORTéS N, DUCHANOY C A, et al. Hardware implementation of the elitist compact Genetic Algorithm using Cellular Automata pseudo-random number generator[J]. Computers & Electrical Engineering, 2013, 39(4): 1367-1379.
[15] NAKATA M, LANZI P L, TAKADAMA K. Simple compact genetic algorithm for XCS[C]//2013 IEEE Congress on Evolutionary Computation (CEC). Cancun: IEEE, 2013: 1718-1723.
[16] 刘昶, 李冬, 彭慧,等. 求解混合流水生产线调度问题的变量相关 EDA 算法[J]. 计算机集成制造系统, 2014:(1):15-18. LIU Chang, LI Dong, PENG Hui, et al. An EDA algorithm with correlated variables for solving hybrid flow-shop scheduling problem [J]. Computer Integrated Manufacturing Systems, 2014:(1):15-18.
[17] CARLIER J, NéRON E. An exact method for solving the multi-processor flow-shop[J]. RAIRO-Operations Research, 2000, 34(1): 1-25.
Similar References:

Memo

-

Last Update: 2015-08-28

Copyright © CAAI Transactions on Intelligent Systems