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

• 学术论文 • 上一篇    下一篇

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

王春1, 田娜2, 纪志成1, 王艳1   

  1. 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 Chun1, TIAN Na2, JI Zhi-cheng1, WANG Yan1   

  1. 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: 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

中图分类号: