计算机应用 ›› 2015, Vol. 35 ›› Issue (6): 1617-1622.DOI: 10.11772/j.issn.1001-9081.2015.06.1617

• 人工智能 • 上一篇    下一篇

教与同伴学习粒子群算法求解多目标柔性作业车间调度问题

吴定会1,2, 孔飞1, 田娜3, 纪志成1   

  1. 1. 轻工过程先进控制教育部重点实验室(江南大学), 江苏 无锡 214122;
    2. 江苏省食品先进制造装备技术重点实验室(江南大学), 江苏 无锡 214122;
    3. 江南大学 教育技术系, 江苏 无锡 214122
  • 收稿日期:2015-01-09 修回日期:2015-03-27 发布日期:2015-06-12
  • 通讯作者: 孔飞(1986-),男,安徽合肥人,硕士研究生,主要研究方向:车间优化调度;kongfei0608@126.com
  • 作者简介:吴定会(1970-),男,安徽合肥人,副教授,博士,主要研究方向:智能调度;田娜(1983-),女,河北石家庄人,副教授,博士,主要研究方向:智能计算、模式识别;纪志成(1959-),男,浙江杭州人,教授,博士生导师,博士,主要研究方向:智能调度。
  • 基金资助:

    国家863计划项目(2013AA040405);江苏省食品先进制造装备技术重点实验室开放课题资助项目(FM-201408)。

Teaching and peer-learning particle swarm optimization for multi-objective flexible job-shop scheduling problem

WU Dinghui1,2, KONG Fei1, TIAN Na3, JI Zhicheng1   

  1. 1. Key Laboratory of Advanced Process Control for Light Industry, Ministry of Education (Jiangnan University), Wuxi Jiangsu 214122, China;
    2. Jiangsu Key Laboratory of Advanced Food Manufacturing Equipment and Technology (Jiangnan University), Wuxi Jiangsu 214122, China;
    3. Department of Educational Technology, Jiangnan University, Wuxi Jiangsu 214122, China
  • Received:2015-01-09 Revised:2015-03-27 Published:2015-06-12

摘要:

针对多目标柔性作业车间调度问题,提出了带Pareto非支配解集的教与同伴学习粒子群算法。首先,以工件的最大完工时间、最大机器负荷和所有机器总负荷为优化目标建立了多目标柔性作业车间调度模型。然后,该算法结合多目标Pareto方法和教与同伴学习粒子群算法,采用快速非支配排序算法产生初始Pareto非支配解集,用提取Pareto支配层程序更新Pareto非支配解集,同时采用混合分派规则产生初始种群,采用开口向上抛物线递减的惯性权重选择策略提高算法的收敛速度。最后,对3个Benchmark算例进行仿真实验。理论分析和仿真表明,与带向导性局部搜索的多目标进化算法(MOEA-GLS)和带局部搜索的控制遗传算法(AL-CGA)相比,对于相同的测试实例,该算法能产生更多更好的Pareto非支配解;在计算时间方面,该算法要小于带向导性局部搜索的多目标进化算法。实验结果表明该算法可以有效解决多目标柔性作业车间调度问题。

关键词: 多目标, 柔性作业车间调度, Pareto非支配解集, 教与同伴学习粒子群, 停滞阻止策略

Abstract:

To solve multi-objective Flexible Job-shop Scheduling Problems (FJSP), a Teaching and Peer-Learning Particle Swarm Optimization with Pareto Non-Dominated Solution Set (PNDSS-TPLPSO) algorithm was proposed. First, the minimum completion time of jobs, the maximum work load of machines and the total work load of all machines were taken as the optimization goals to establish a multi-objective flexible job-shop scheduling model. Then, the proposed algorithm combined multi-objective Pareto method with Teaching and Peer-Learning Particle Swarm Optimization (TPLPSO). A fast Pareto non-dominated sorting operator was applied to generate initial Pareto non-dominated solution set, and extracting Pareto dominance layer program was adopted to update Pareto non-dominated solution set. Furthermore, composite dispatching rule was adopted to generate the initial population, and opening up parabola decreasing inertia weigh strategy was taken to improve the convergence speed. Finally, the proposed algorithm was adopted to solve three Benchmark instances. In the comparison experiments with Multi-Objective Evolutionary Algorithm with Guided Local Search (MOEA-GLS) and Controlled Genetic Algorithm with Approach by Localization (AL-CGA), the proposed algorithm can obtain more and better Pareto non-dominated solutions for the same Benchmark instance. In terms of computing time, the proposed algorithm is less than MOEA-GLS. The simulation results demonstrate that the proposed algorithm can solve multi-objective FJSP effectively.

Key words: multi-objective, flexible job-shop scheduling, Pareto non-dominated solution set, Teaching and Peer-Learning Particle Swarm Optimization (TPLPSO), Stagnation Prevention Strategy (SPS)

中图分类号: