改善式BVEDA求解多目标调度问题

doi:10.6040/j.issn.1672-3961.0.2016.256

山东大学学报(工学版) ›› 2017, Vol. 47 ›› Issue (4): 25-30.doi: 10.6040/j.issn.1672-3961.0.2016.256

改善式BVEDA求解多目标调度问题

裴小兵¹,陈慧芬^1*,张百栈²,陈孟辉²

1. 天津理工大学管理学院, 天津 300384;2. 南昌大学软件学院, 江西南昌 330031

收稿日期:2016-07-14 出版日期:2017-08-20 发布日期:2016-07-14
通讯作者: 陈慧芬(1991— ),女,河南周口人,硕士研究生,主要研究方向为调度算法.E-mail: chenhuifen321@foxmail.com E-mail:peixiaobing100@qq.com
作者简介:裴小兵(1965— ),男,内蒙古呼和浩特人,教授,博士,主要研究方向为调度算法.E-mail:peixiaobing100@qq.com
基金资助:
天津市哲学社会科学基金资助项目(TJYY15-024)

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

PEI Xiaobing¹, CHEN Huifen^1*, ZHANG Baizhan², CHEN Menghui²

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

摘要/Abstract

摘要： 针对以最小化最大完工时间、最小化最大拖期和最小化总流程时间为目标的置换流水车间调度问题(permutation flow shop scheduling problem, PFSP),基于双变量分布估计法(bi-variable estimation of distribution algorithm, BVEDA)提出改善式双变量分布估计算法(Improved BVEDA, IBVEDA)进行求解。利用BVEDA中双变量概率模型进行区块构建,根据组合概率公式进行区块竞争和区块挖掘,借用高质量的区块组合人造解,提高演化过程中解的质量;针对算法多样性较差的特点,设计在组合人造解的过程中加入派工规则最短处理时间、最长处理时间和最早交货期,将上述方法并行演化,通过top10的权重适度值总和动态调整上述方法处理的解的数量,最后利用帕累托支配筛选和保存非支配解。试验使用C++代码在Taillard标准算例上测试,IBVEDA与SPGAⅡ和BVEDA比较,并绘制解的分布图证实算法的有效性。

关键词: 概率模型, 派工规则, 多目标优化, 双变量分布估计算法, 置换流水车间调度

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

中图分类号:

TP301

裴小兵,陈慧芬,张百栈,陈孟辉. 改善式BVEDA求解多目标调度问题[J]. 山东大学学报(工学版), 2017, 47(4): 25-30.

PEI Xiaobing, CHEN Huifen, ZHANG Baizhan, CHEN Menghui. Improved bi-variables estimation of distribution algorithms for multi-objective permutation flow shop scheduling problem[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(4): 25-30.

参考文献

[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.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed

改善式BVEDA求解多目标调度问题

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

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 5

多维度评价

本文评价

推荐阅读 0

[1]	钱淑渠,武慧虹,徐国峰,金晶亮. 计及排放的动态经济调度免疫克隆演化算法[J]. 山东大学学报(工学版), 2018, 48(4): 1-9.
[2]	王飞,徐健,李伟,汪新浩,施啸寒. 基于分布式储能系统的风储滚动优化调度方法[J]. 山东大学学报(工学版), 2017, 47(6): 89-94.
[3]	邓冠龙,杨洪勇,张淑宁,顾幸生. 零等待flow shop多目标调度的混合差分进化算法[J]. 山东大学学报(工学版), 2016, 46(5): 21-28.
[4]	刘淳安. 基于核分布估计的动态多目标优化进化算法[J]. 山东大学学报(工学版), 2011, 41(1): 167-172.
[5]	曲延鹏陈颂英杨新振解富超李文峰宋秀琴. 低比转速离心泵叶轮几何参数多目标优化[J]. 山东大学学报(工学版), 2009, 39(3): 103-105.