求解模糊柔性作业车间调度的多目标进化算法

doi:10.3969/j.issn.0372-2112.2017.12.012

电子学报 ›› 2017, Vol. 45 ›› Issue (12): 2909-2916.DOI: 10.3969/j.issn.0372-2112.2017.12.012

求解模糊柔性作业车间调度的多目标进化算法

王春¹, 田娜², 纪志成¹, 王艳¹

1. 江南大学教育部物联网技术应用工程中心, 江苏无锡 214122;
2. 江南大学人文学院, 江苏无锡 214122

收稿日期:2016-05-10 修回日期:2016-08-24 出版日期:2017-12-25
- 通讯作者:
- 王艳
- 作者简介:
- 王春,男,1988年2月出生于安徽省淮北市.现为江南大学教育部物联网技术应用工程中心博士研究生.主要研究方向为进化算法及其在生产调度中的应用.E-mail:huaibeifwangchun@163.com;田娜,女,1983年5月出生于河北省石家庄市.博士,现为江南大学人文学院副教授,硕士生导师.主要研究方向为人工智能和数据挖掘.E-mail:tianna@jiangnan.edu.cn;纪志成,男,1959年11月出生于浙江省杭州市.博士,现为江南大学教育部物联网技术应用工程中心教授,博士生导师.主要研究方向为群智能优化算法、智能制造.E-mail:zcji@jiangnan.edu.cn
- 基金资助:
- 国家自然科学基金 (No.61572238）; 江苏省杰出青年基金 (No.BK20160001）

Multi-objective Evolutionary Algorithm to Solve Fuzzy Flexible Job Shop Scheduling Problem

WANG Chun¹, TIAN Na², JI Zhi-cheng¹, WANG Yan¹

1. Engineering Research Center of Internet of Things Technology Applications Ministry of Education, Jiangnan University, Wuxi, Jiangsu 214122, China;
2. School of Humanities, Jiangnan University, Wuxi, Jiangsu 214122, China

Received:2016-05-10 Revised:2016-08-24 Online:2017-12-25 Published:2017-12-25
- Supported by:
- National Natural Science Foundation of China (No.61572238); Outstanding Youth Fund of Jiangsu Province (No.BK20160001)

摘要/Abstract

摘要： 针对实际制造车间中工序加工时间具有不确定性，将加工时间采用模糊数表示，建立一种多目标模糊柔性作业车间调度模型，并提出了有效求解该模型的多目标进化算法.算法采用混合机器分配和工序排序策略的方法产生初始种群，并采用插入空隙法对染色体进行解码.定义一种新的基于可能度的个体支配关系和一种基于决策空间的拥挤算子，并将所提支配关系和拥挤算子运用于快速非支配排序.接着，提出一种基于移动模糊关键工序的局部搜索策略.实验部分首先通过田口试验方法来研究关键参数对算法性能的影响；其次，将所提算法与三种不同的优化算法作对比.实验结果验证了所提算法的有效性.

关键词: 模糊柔性作业车间调度, 局部搜索, 多目标进化算法, 可能度, 模糊关键工序

Abstract: Seeing that the processing time is uncertain in the actual manufacturing workshop,a multi-objective fuzzy flexible job shop scheduling model is established,and then an effective multi-objective evolutionary algorithm (MOEA) is proposed to solve this model.First,a method of mixing different machine allocation and operation sequencing strategies is adopted to generate initial population and a well-designed greedy inserting algorithm is adopted for chromosome decoding.Second,a Pareto dominant relation based on possibility degree and a modified crowding distance measure in decision space are defined and further employed to improve the fast nondominated sorting.Moreover,a problem-specific local search based on fuzzy critical path theory is incorporated into MOEA.Afterwards,the influence of key parameters is investigated based on the Taguchi method of experiment.Finally,extensive comparison with three existing algorithms is carried out,and the results demonstrate the effectiveness of the proposed algorithm.

Key words: fuzzy flexible job shop scheduling, local search, multi-objective evolutionary algorithm, possibility degree, fuzzy critical operation

中图分类号:

TP302

王春, 田娜, 纪志成, 等. 求解模糊柔性作业车间调度的多目标进化算法[J]. 电子学报, 2017, 45(12): 2909-2916.

WANG Chun, TIAN Na, JI Zhi-cheng, et al. Multi-objective Evolutionary Algorithm to Solve Fuzzy Flexible Job Shop Scheduling Problem[J]. Acta Electronica Sinica, 2017, 45(12): 2909-2916.

参考文献

[1] Lei D M.A genetic algorithm for flexible job shop scheduling with fuzzy processing time[J].International Journal of Production Research,2010,48(10):2995-3013.
[2] Lei D M.Co-evolutionary genetic algorithm for fuzzy flexible job shop scheduling[J].Applied Soft Computing,2012,12(8):2237-2245.
[3] Wang L,Zhou G,Xu Y,et al.A hybrid artificial bee colony algorithm for the fuzzy flexible job-shop scheduling problem[J].International Journal of Production Research,2013,51(12):3593-3608.
[4] Palacio J J,González M A,Vela C R,et al.Genetic tabu search for the fuzzy flexible job shop problem[J].Computers & Operations Research,2015,54:74-89.
[5] Gao K Z,Suganthan P N,Pan Q K,et al.An effective discrete harmony search algorithm for flexible job shop scheduling problem with fuzzy processing time[J].International Journal of Production Research,2015,53(19):5896-5911.
[6] Wang S Y,Wang L,Xu Y,et al.An effective estimation of distribution for the flexible job-shop scheduling problem with fuzzy processing time[J].International Journal of Production Research,2013,51(12):3778-3793.
[7] Wang X J,Gao L,Zhang C Y,et al.A multi-objective genetic algorithm for fuzzy flexible job-shop scheduling problem[J].International Journal of Computer Applications in Technology,2012,45(45):115-125.
[8] Wang X J,Li W F,Zhang Y.An improved multi-objective genetic algorithm for fuzzy flexible job-shop scheduling problem[J].Internatinal Journal of Computer Applications in Technology,2013,47(2/3):280-288.
[9] Zheng Y L,Li Y X,Lei D M.Multi-objective swarm-based neighborhood search for fuzzy flexible job shop scheduling[J].International Journal of Advanced Manufacturing Technology,2012,60(9):1063-1069.
[10] Deb K,Pratap A,Agarwal S,et al.A fast and elitist multiobjective genetic algorithm:NSGA-Ⅱ[J].IEEE Transactions on Evolutionary Computation,2002,6(2):182-197.
[11] 赵诗奎,方水良,顾新建.基于极限调度完工时间最小化的机器选择及FJSP求解[J].计算机集成制造系统,2014,20(4):854-865. Zhao S K,Fang S L,Gu X J.Machine selection and FJSP solution based on limit scheduling completion time minimization[J].Computer Integrated Manufacturing Systems,2014,20(4):854-865.
[12] Pezzella F,Morganti G,Cia G.A genetic algorithm for the flexible job-shop scheduling problem[J].Computers & Operations Research,2008,35(10):3202-3212.
[13] Zhang G H,Gao L,Shi Y.An effective genetic algorithm for the flexible job-shop scheduling problem[J].Expert Systems with Applications,2011,38(4):3563-3573.
[14] Yuan Y,Xu H.Multiobjective flexible job shop scheduling using memetic algorithm[J].IEEE Transactions on Automation Science and Enginering,2015,12(1):336-353.
[15] Tan Y Y,Jiao Y C,Li H,et al.MOEA/D+uniform design:a new version of MOEA/D for optimization problems with many objectives[J].Computer & Operations Research,2013,40(6):1648-1660.
[16] Mastrolilli M,Gambardella L M.Effective neighborhood functions for the flexible job shop problem[J].Journal of Scheduling,2000,3(1):3-20.
[17] Ziter E,Thiele L.Multi-objective evolutionary algorithms:A comparative case study and the strength Pareto approach[J].IEEE Transaction on Evolutionary Computation,1999,3(4):257-271.
[18] Bader J,Ziter E.Hype:An algorithm for fast hypervolume-based many-objective optimization[J].Evolutionary Computation,2011,19(1):45-76.

求解模糊柔性作业车间调度的多目标进化算法

Multi-objective Evolutionary Algorithm to Solve Fuzzy Flexible Job Shop Scheduling Problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	张建民, 黎铁军, 马柯帆, 肖立权. 一种加速FPGA布线的不可满足子式求解算法[J]. 电子学报, 2021, 49(6): 1210-1216.
[2]	孙文静, 李军华, 黎明. 基于自适应支配准则的高维多目标进化算法[J]. 电子学报, 2020, 48(8): 1596-1604.
[3]	王金艳, 胡春, 牛当当, 李先贤. 基于IAPS的扩展规则局部搜索算法[J]. 电子学报, 2020, 48(5): 899-905.
[4]	曹玉莲, 李文锋, 张煜. 基于拟熵自适应启动局部搜索策略的混合粒子群算法[J]. 电子学报, 2018, 46(1): 110-117.
[5]	续欣莹, 张扩, 谢珺, 谢刚. 基于互信息下粒子群优化的属性约简算法[J]. 电子学报, 2017, 45(11): 2695-2704.
[6]	叶东毅, 陈昭炯. 最小属性约简问题的一个有效的组合人工蜂群算法[J]. 电子学报, 2015, 43(5): 1014-1020.
[7]	王令赛, 姜淑娟, 张艳梅, 于巧. 基于正交搜索的粒子群优化测试用例生成方法[J]. 电子学报, 2014, 42(12): 2345-2351.
[8]	郑金华, 谢谆志. 关于如何用角度信息引入决策者偏好的研究[J]. 电子学报, 2014, 42(11): 2239-2246.
[9]	尹浩, 张长胜, 张斌, 孙若男, 刘婷婷. 一种求解SLA等级感知服务组合问题的多目标离散粒子群优化算法[J]. 电子学报, 2014, 42(10): 1983-1990.
[10]	莫宏伟, 徐立芳. 基于Memetic算法的电路演化设计研究[J]. 电子学报, 2013, 41(5): 1036-1040.
[11]	郑金华, 刘磊, 刘文盼, 邹娟. 一种自适应小生境分布性保持策略[J]. 电子学报, 2012, 40(11): 2330-2335.
[12]	李密青;郑金华;李珂. 一种非均匀分布问题分布性维护方法[J]. 电子学报, 2011, 39(4): 946-952.
[13]	张雪霞;陈维荣;戴朝华. 带局部搜索的动态多群体自适应差分进化算法及函数优化[J]. 电子学报, 2010, 38(8): 1825-1830.
[14]	鲍培明;朱庆保. 用于多目标进化的归一化排序非支配集构造方法[J]. 电子学报, 2009, 37(9): 2010-2015.
[15]	郑金华;罗彪;周聪;李望移. 用多目标进化算法搜索MOPs的鲁棒Pareto最优解[J]. 电子学报, 2009, 37(12): 2815-2822.