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)

434

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] LI Xinyu, XU Guiyun, REN Shijin, YANG Maoyun. Discriminative manifold-based uncorrelated sparse projective nonnegative matrix factorization [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2015, 45(5): 1-12.
[2] LIANG Zehua, CUI Yaodong, ZHANG Yu. The one-dimensional cutting stock problem with sequence-dependent cut losses [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2018, 48(3): 75-80.
[3] WU Hongyan, JI Junzhong. Flower pollination algorithm-based functional module detection in protein-protein interaction networks [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2018, 48(1): 21-30.
[4] ZHOU Zhijie, ZHAO Fujun, HU Changhua, WANG Li, FENG Zhichao, LIU Taoyuan. Failure prognosis method based on evidential reasoning for aerospace relay [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(5): 22-29.
[5] REN Yongfeng, DONG Xueyu. An image saliency object detection algorithm based on adaptive manifold similarity [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(3): 56-62.
[6] ZHAI Jiyou, ZHOU Jingbo, REN Yongfeng, WANG Zhijian. A visual saliency detection based on background and foreground interaction [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(2): 80-85.
[7] WU Huimin, WU Jingli. An improved cycle basis algorithm for haplotyping a diploid individual [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2016, 46(4): 9-14.
[8] ZHU Jie, WANG Jing, LIU Fei, GAO Guandong, DUAN Qing. Object classification method based on component pyramid matching [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2016, 46(2): 14-21.
[9] JING Yunge, LI Tianrui. An incremental approach for reduction based on knowledge granularity [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2016, 46(1): 1-9.
[10] WANG Lihong, LI Qiang. A selective ensemble method for traveling salesman problems [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2016, 46(1): 42-48.
[11] REN Yongfeng, ZHOU Jingbo. An image saliency object detection algorithm based on information diffusion [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2015, 45(6): 1-6.
[12] GAO Yanpu, WANG Xiangdong, WANG Dongqing. Maximum likelihood identification method for a multivariable controlled autoregressive moving average system [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2015, 45(2): 49-55.
[13] LU Wenyang, XU Jiayi, YANG Yubin. LDA-based link prediction in social network [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2014, 44(6): 26-31.
[14] JIANG Weijian1,2, GUO Gongde1,2*, LAI Zhiming1,2. An improved adaboost algorithm based on new Haar-like feature for face detection [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2014, 44(2): 43-48.
[15] CHEN Wen-qiang1, LIN Chen1,2, CHEN Ke3, CHEN Jin-xiu1, ZOU Quan1,2*. Distributed affinity propagation clustering algorithm based on GraphLab [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2013, 43(5): 13-18.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright 2018 © Editorial office of Journal of Shandong University (Engineering Science)
Supported by Beijing Magtech Co.Ltd