计算机与现代化

• 算法设计与分析 • 上一篇    下一篇

改进多目标进化算法求解柔性作业车间调度问题

  

  1. 无锡科技职业学院,江苏  无锡  214028
  • 收稿日期:2016-12-19 出版日期:2017-09-20 发布日期:2017-09-19
  • 作者简介:张春燕(1982-),女,江苏南通人,无锡科技职业学院讲师,硕士,研究方向:人工智能算法与模式识别,嵌入式计算机控制系统。
  • 基金资助:
    国家自然科学基金资助项目(61300149); 江苏省教育厅高校哲学社会科学研究指导项目(2016SJD880064); 江苏高校品牌专业建设工程资助项目

Improved Multiobjective Evolutionary Algorithm for Solving Flexible Job Shop Scheduling Problem

  1. Wuxi Vocational College of Science and Technology, Wuxi 214028, China
  • Received:2016-12-19 Online:2017-09-20 Published:2017-09-19

摘要: 针对加工时间为模糊数的柔性作业车间调度问题,考虑最小化模糊最大完工时间、模糊机器总负荷、模糊关键机器负荷为优化目标,提出一种有效求解该类优化问题的多目标进化算法。算法采用一种混合不同机器分配和工序排序策略的方法产生初始种群,并采用插入空隙法对染色体进行解码。定义一种新的基于可能度的个体支配关系和一种基于决策空间的拥挤算子,并将所提支配关系和拥挤算子运用于快速非支配排序。接着,提出一种基于移动模糊关键工序的局部搜索策略对种群中的优势个体进行局部搜索。通过试验研究关键参数对算法性能的影响并将所提算法与3种不同的优化算法作对比。结果表明,所提算法能够比其它算法更有效解决多目标模糊柔性作业车间调度优化问题。

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

Abstract: Aiming at the processing time for fuzzy flexible job shop scheduling problem and considering minimizing the fuzzy maximal makespan, fuzzy total workload and fuzzy critical workload as optimization objectives, an effective multiobjective evolutionary algorithm is proposed. A method of mixing different machine allocations and operation sequencing strategies is adopted to generate initial population and a well-designed greedy inserting algorithm is adopted for chromosome decoding. 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 novel local search based on fuzzy critical path theory is first incorporated into MOEA. Afterwards, the influence of key parameters is investigated by designing of the Taguchi method of design of experiment. Finally, extensive comparison with three existing algorithms is carried out, and the results demonstrate the effectiveness of the proposed MOEA in solving multiobjective flexible job shop scheduling problem (MOfFJSP).

Key words: multiobjective fuzzy, flexible job shop scheduling, local search, multiobjective evolutionary algorithm, fuzzy critical operation

中图分类号: