JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE) ›› 2017, Vol. 47 ›› Issue (4): 25-30.doi: 10.6040/j.issn.1672-3961.0.2016.256

Previous Articles     Next Articles

Improved bi-variables estimation of distribution algorithms for multi-objective permutation flow shop scheduling problem

PEI Xiaobing1, CHEN Huifen1*, ZHANG Baizhan2, CHEN Menghui2   

  1. 1. School of Management, Tianjin University of Technology, Tianjin 300384, China;
    2. School of Software, Nanchang University, Nanchang 330031, Jiangxi, China
  • Received:2016-07-14 Online:2017-08-20 Published:2016-07-14

PDF (PC)

494

Abstract: Aiming at permutation flow shop scheduling problem(PFSP)with the minimum maximum makespan, the minimum maximum tardiness and the minimum total flow time as objectives, improved bi-variable estimation of distribution algorithm(IBVEDA)based on bi-variables estimation of distribution algorithm(BVEDA)was proposed. Building blocks was designed using bi-variable probability model of IBVEDA, according to combination probability formula for block competition and block mining, then artificial chromosomes were generated using high quality blocks to improve the quality of solution in the evolution process. To enhance the diversity of algorithm, dispatching rules, the shortest processing time, longest processing time,earliest due date were added in parallel evolution while injecting artificial chromosomes, the number of individual for next iteration processed by the methods above depended on the above methods top 10 total weighted fitness of last iteration to do dynamic adjustment, finally Pareto dominance was used to select and save non-dominated solutions. The experiment used C++ code tested on Taillards standard instances, IBVEDA was compared with SPGAⅡand BVEDA and solution distribution of the three algorithms were plot which the effectiveness of IBVEDA was validated.

Key words: bi-variables estimation of distribution algorithm, permutation flow shop scheduling, dispatching rules, multi-objective optimation, probability model

CLC Number: 

  • TP301
[1] MINELLA G, RUIZ R, CIAVOTTA M. A review and evaluation of multi-objective algorithms for the flow shop scheduling problem[J].Informs Journal on Computing, 2008, 20(3):451-471.
[2] SUN Y, ZHANG C, GAO L, et al. Multi-objective optimization algorithms for flow shop scheduling problem: a review and prospects[J].The International Journal of Advanced Manufacturing Technology, 2011, 55(5):723-739.
[3] 赵诗奎.基于遗传算法的柔性资源调度优化方法研究[D].杭州:浙江大学,2013. ZHAO Shikui. Research on flexible resource scheduling optimization method based on genetic algorithm[J]. Hangzhou: Zhejiang University, 2013.
[4] YENISEY M M, YAGMAHAN B. Multi-objective permutation flow shop scheduling problem: Literature review, classification and current trends[J].Omega, 2014, 45(2):119-135.
[5] 刘莹,谷文祥,李向涛.置换流水线车间调度问题的研究[J].计算机科学,2013,40(11):1-7. LIU Ying, GU Wenxiang, LI Xiangtao. Research on the permutation flow shop scheduling problem[J].Computer Science, 2013, 40(11):451-471.
[6] MUHLENBEIN H, PAA G. From recombination of genes to the estimation of distributions I:binary parameters[J]. Parallel Problem Solving from Nature-PPSN IV, 1996, 34:178-187.
[7] 萧鸿锦.二元变量分配估计算法应用于流程型排程问题[D].台湾:元智大学,2013. XIAO Hongjin. Bi-variate estimation of distribution algorithm for flow shop problem[D]. Taiwan:Yuan Ze University, 2013.
[8] CHEN Y M, CHEN M C, CHANG P C, et al. Extended artificial chromosomes genetic algorithm for permutation flowshop scheduling problems[J].Computers & Industrial Engineering, 2012, 62(2):536-545.
[9] CHEN S, CHEN M C. Addressing the advantages of using ensemble probabilistic models in estimation of distribution algorithms for scheduling problems[J].International Journal of Production Economics, 2013, 141(141):24-33.
[10] CHANG P C, HUANG W H, WU J L, et al. A block mining and re-combination enhanced genetic algorithm for the permutation flow shop scheduling problem[J].Int J Production Economics, 2013, 141(1):45-55.
[11] REEVES C R. A genetic algorithm for flow shop sequencing[J].Computers and Operations Research, 1995, 5(1):5-13.
[12] TSUTSUI S. Probabilistic model-building genetic algorithms in permutation representation domain using edge histogram[C] //International Conference on Parallel Problem Solving From Nature. [S.l.] :Springer-Verlag, 2002:224-233.
[13] ARROYO J E, ARMENTANO V A. Genetic local search for multi-objective flowshop scheduling problems[J].European Journal of Operational Research, 2005, 167(3):717-738.
[14] ARROYO J E C, PEREIRA A A D S. A GRASP heuristic for the multi-objective permutation flowshop scheduling problem[J]. The International Journal of Advanced Manufacturing Technology, 2011, 55(5):741-753.
[15] ISHIBUCHI H, YOSHIDA T, MURATA T. Balance between genetic local search in memetic algorithms for multi-objective permutation flow shop scheduling[J].IEEE Trans Evol Comput, 2003, 7(2):204-223.
[16] AL-FAWZAN M A, HAOUARI M. A bi-objective model for robust resource-constrained project scheduling[J].International Journal of Production Economics, 2005, 96(2):175-187.
[17] TAILLARD E. Benchmarks for basic scheduling problems[J].European Journal of Operational Research, 1993, 64(2):278-285.
[18] CHANG P C, CHEN S H.The development of a sub-population genetic algorithm II(SPGA II)for multi-objective combinatorial problems[J].Applied Soft Computing, 2009, 9(1):173-181.
[19] 徐麟.以柴比雪夫分群法建构子群体权重矢量求解多目标问题[D].台湾:元智大学,2011:6. XU Lin. Sub-population genetic algorithm II for multi-objective parallel machine scheduling problems[D].Taiwan:Yuan Ze University, 2011:6.
[20] ZHANG Qingfu, LI Hui. MOEA/D: a multiobjective evolutionary algorithm based on decomposition[J].IEEE Transactions on Evolutionary Computation, 2007, 11(6):712-731.
[1] Dong YANG,Shiwen WANG,Yong WANG,Bo CHEN,Tianru ZHENG,Ning ZHOU,Tian XIAO,Yawen ZHAO. Optimal complementary photovoltaic capacity configuration for grid-connected wind farms expansion [J]. Journal of Shandong University(Engineering Science), 2019, 49(5): 44-51.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] LI Kan . Empolder and implement of the embedded weld control system[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2008, 38(4): 37 -41 .
[2] SHI Lai-shun,WAN Zhong-yi . Synthesis and performance evaluation of a novel betaine-type asphalt emulsifier[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2008, 38(4): 112 -115 .
[3] LAI Xiang . The global domain of attraction for a kind of MKdV equations[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(1): 87 -92 .
[4] YU Jia yuan1, TIAN Jin ting1, ZHU Qiang zhong2. Computational intelligence and its application in psychology[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(1): 1 -5 .
[5] CHEN Rui, LI Hongwei, TIAN Jing. The relationship between the number of magnetic poles and the bearing capacity of radial magnetic bearing[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2018, 48(2): 81 -85 .
[6] WANG Bo,WANG Ning-sheng . Automatic generation and combinatory optimization of disassembly sequence for mechanical-electric assembly[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(2): 52 -57 .
[7] JI Tao,GAO Xu/sup>,SUN Tong-jing,XUE Yong-duan/sup>,XU Bing-yin/sup> . Characteristic analysis of fault generated traveling waves in 10 Kv automatic blocking and continuous power transmission lines[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(2): 111 -116 .
[8] ZHANG Ying,LANG Yongmei,ZHAO Yuxiao,ZHANG Jianda,QIAO Peng,LI Shanping . Research on technique of aerobic granular sludge cultivationby seeding EGSB anaerobic granular sludge[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(4): 56 -59 .
[9] Yue Khing Toh1， XIAO Wendong2， XIE Lihua1. Wireless sensor network for distributed target tracking: practices via real test bed development[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(1): 50 -56 .
[10] SUN Weiwei， WANG Yuzhen. Finite gain stabilization of singlemachine infinite bus system subject to saturation[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(1): 69 -76 .
Copyright 2018 © Editorial office of Journal of Shandong University (Engineering Science)
Supported by Beijing Magtech Co.Ltd