流水车间调度问题的快速多目标混合进化算法

doi:10.11772/j.issn.1001-9081.2016.04.1015

计算机应用 ›› 2016, Vol. 36 ›› Issue (4): 1015-1021.DOI: 10.11772/j.issn.1001-9081.2016.04.1015

流水车间调度问题的快速多目标混合进化算法

张闻强, 卢佳明, 张红梅

河南工业大学信息科学与工程学院, 郑州 450000

收稿日期:2015-10-02 修回日期:2015-11-11 出版日期:2016-04-10 发布日期:2016-04-08
通讯作者: 卢佳明
作者简介:张闻强(1975-),男,河南新乡人,讲师,博士,主要研究方向:进化计算、调度优化、多目标优化; 卢佳明(1989-),男,河南焦作人,硕士研究生,主要研究方向:进化计算、调度优化; 张红梅(1962-),女,江苏徐州人,教授,硕士,主要研究方向:计算智能。
基金资助:
国家自然科学基金资助项目(U1304609);河南工业大学自然科学基础研究重点培育计划项目(2012JCYJ04);河南省省属高校基本科研业务费专项资金资助项目(2014YWQQ12)。

Fast multi-objective hybrid evolutionary algorithm for flow shop scheduling problem

ZHANG Wenqiang, LU Jiaming, ZHANG Hongmei

College of Information Science and Engineering, Henan University of Technology, Zhengzhou Henan 450000, China

Received:2015-10-02 Revised:2015-11-11 Online:2016-04-10 Published:2016-04-08
Supported by:
This work is partially supported by the National Natural Science Foundation of China (U1304609), Plan of Nature Science Fundamental Research in Henan University of Technology (2012JCYJ04), the Fundamental Research Funds for the Henan Provincial Colleges and Universities (2014YWQQ12).

摘要/Abstract

摘要： 针对最大完工时间最小和总流经时间最小的双目标流水车间调度问题,提出一种快速多目标混合进化算法。算法将矢量评价遗传算法的采样策略与一种新的基于Pareto支配与被支配关系的适应度函数的采样策略进行了融合。新的采样策略弥补了矢量评价遗传算法(VEGA)采样策略的不足。VEGA善于搜索Pareto前沿面的边缘区域,但却忽略了Pareto前沿面的中心区域,而新的采样策略则倾向于Pareto前沿面的中心区域。这两种机制的融合保证了混合算法能够快速平稳地向Pareto前沿区域收敛。此外,由于混合采样策略不需要考虑距离,使得算法效率也得到了很大的提升。在对Taillard基准测试集进行的仿真实验结果显示,相对于非支配排序遗传算法(NSGA-Ⅱ)和强度Pareto进化算法(SPEA2),该快速多目标混合进化算法在收敛性和分布性两方面都有所提高,并且算法的效率也得到了改进。所提出的混合算法能够更好地解决双目标的流水车间调度问题。

关键词: 流水车间调度, 混合进化算法, 采样策略, 矢量评价遗传算法, 多目标优化

Abstract: A fast multi-objective hybrid evolutionary algorithm was proposed for solving bi-criteria Flow shop Scheduling Problem (FSP) with the objectives of minimizing makespan and total flow time. The sampling strategy of the Vector Evaluated Genetic Algorithm (VEGA) and a new sampling strategy according to the Pareto dominating and dominated relationship-based fitness function were integrated with the proposed algorithm. The new sampling strategy made up the shortage of the sampling strategy of VEGA. VEGA was good at searching the edge region of the Pareto front, but it neglected the central area of the Pareto front, while the new sampling strategy preferred the center region of the Pareto front. The fusion of these two mechanisms ensured that the hybrid algorithm can converge to the Pareto front quickly and smoothly. Moreover, the algorithm efficiency was improved greatly without calculating the distance. Simulation experiments on Taillard benchmark sets show that, compared with Non-dominated Sorting Genetic Algorithm-Ⅱ (NSGA-Ⅱ) and Strength Pareto Evolutionary Algorithm 2 (SPEA2), the fast multi-objective hybrid evolutionary algorithm is improved in the performance of convergence and distribution, and the efficiency of the algorithm has been improved. The proposed algorithm can be better at solving the bi-criteria flow shop scheduling problem.

Key words: flow shop scheduling, hybrid evolutionary algorithm, sampling strategy, vector evaluated genetic algorithm, multi-objective optimization

中图分类号:

TP18

张闻强, 卢佳明, 张红梅. 流水车间调度问题的快速多目标混合进化算法[J]. 计算机应用, 2016, 36(4): 1015-1021.

ZHANG Wenqiang, LU Jiaming, ZHANG Hongmei. Fast multi-objective hybrid evolutionary algorithm for flow shop scheduling problem[J]. Journal of Computer Applications, 2016, 36(4): 1015-1021.

参考文献

[1] PINED M.调度:原理、算法和系统[M]. 张智海, 译.北京:清华大学出版社, 2007:1-7.(PINEDO M. Scheduling:Theory, Algorithms and Systems[M]. ZHANG Z H, translated. Beijing:Tsinghua University Press, 2007:1-7.)
[2] GONZALEZ T, SAHNI S. Flow shop and job shop schedules:complexity and approximation[J]. Operations Research, 1978, 26(1):36-52.
[3] ZIAEIFAR A, TAVAKKOLI-MOGHADDAM R, PICHKA K. Solving a new mathematical model for a hybrid flow shop scheduling problem with a processor assignment by a genetic algorithm[J]. International Journal of Advanced Manufacturing Technology, 2012, 61(1):339-349.
[4] GAO K, PAN Q, SUGANTHAN PN, et al. Effective heuristics for the no-wait flow shop scheduling problem with total flow time minimization[J]. International Journal of Advanced Manufacturing Technology, 2013, 66(9):1563-1572.
[5] GAO K, PAN Q, LI J. Discrete harmony search algorithm for the no-wait flow shop scheduling problem with total flow time criterion[J]. International Journal of Advanced Manufacturing Technology, 2011, 56(5):683-692.
[6] BERTOLISSI E. Heuristic algorithm for scheduling in the no-wait flow shop[J]. Journal of Materials Processing Technology, 2000, 107(3):459-465.
[7] LAHA D, CHAKRABORTY U K. A constructive heuristic for minimizing make-span in no-wait flow shop scheduling[J]. International Journal of Advanced Manufacturing Technology, 2009, 41(1):97-109.
[8] SPANOS A C, PONIS S T, TATSIOPOULOS I P, et al. A new hybrid parallel genetic algorithm for the job shop scheduling problem[J]. International Transactions in Operational Research, 2014, 21(3):479-499.
[9] 杨开兵. 基于进化计算的多目标流水车间批组调度问题研究[D]. 大连:大连理工大学, 2011:31-52.(YANG K B. Research on multi-objective flowshop scheduling with batching based on evolutionary algorithm[D]. Dalian:Dalian University of Technology, 2011:31-52.)
[10] 何启巍, 张国军, 朱海平, 等. 一种多目标置换流水车间调度问题的优化算法[J]. 计算机系统应用, 2013, 9(1):111-118, 110.(HE Q W, ZHANG G J, ZHU H P, et al. A hybrid particle swarm optimization algorithm for multi-objective permutation flows shop scheduling problem[J]. Computer Systems & Application, 2013, 9(1):111-118, 110.)
[11] 周晏明.基于改进遗传算法的多目标作业车间调度研究[D]. 哈尔滨:东北林业大学, 2013:8-19.(ZHOU Y M. Research on multi-objective job shop scheduling problem based on the improved genetic algorithm[D]. Harbin:Northeast Forestry University, 2013:8-19.)
[12] SCHAFFER J D. Multiple objective optimization with vector evaluated genetic algorithms[C]//Proceedings of the 1st International Conference on Genetic Algorithms Table of Contents. Hillsdale, NJ:Lawrence Erlbaum Associates, 1985:93-100.
[13] DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multi-objective genetic algorithm:NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2):182-197.
[14] ZITZLER E, LAUMANS M, THIELE L. SPEA2:improving the strength Pareto evolutionary algorithm[EB/OL].[2015-02-10]. http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.112.5073.
[15] WEI X, ZHANG W, WENG W, et al. Multi-objective local search combined with NSGA-Ⅱ for bi-criteria permutation flow shop scheduling problem[J]. IEEE Transactions on Electronics, Information and Systems, 2011, 132(1):32-41.
[16] GOLDBERG D E, LINGLE R. Alleleslociand the traveling salesman problem[C]//Proceedings of 1st International Conference on Genetic Algorithms. Hillsdale, NJ:Lawrence Erlbaum Associates, 1985:154-159.
[17] TAILLARD E. Benchmarks for basic scheduling problems[J]. European Journal of Operational Research, 1993, 64(2):278-285.

流水车间调度问题的快速多目标混合进化算法

Fast multi-objective hybrid evolutionary algorithm for flow shop scheduling problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	罗明宇, 骆晓萌, 朱文敏, 张磊, 范秀敏. 船舶狭小空间虚拟人维修姿态建模技术[J]. 计算机应用, 2021, 41(8): 2466-2472.
[2]	张闻强, 邢征, 杨卫东. 基于多区域采样策略的混合粒子群优化求解多目标柔性作业车间调度问题[J]. 计算机应用, 2021, 41(8): 2249-2257.
[3]	张祥飞, 鲁宇明, 张平生. 基于协同进化的约束多目标优化算法[J]. 计算机应用, 2021, 41(7): 2012-2018.
[4]	乔钢柱, 王瑞, 孙超利. 基于分解的高维多目标改进进化算法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3097-3103.
[5]	李二超, 李康伟. 基于最小距离和聚合策略的分解多目标进化算法[J]. 计算机应用, 2021, 41(1): 22-28.
[6]	李二超, 杨蓉蓉. 基于自适应反向学习的多目标分布估计算法[J]. 计算机应用, 2021, 41(1): 15-21.
[7]	王博, 刘连生, 韩绍程, 祝世兴. 基于多策略融合的混合多目标蝗虫优化算法[J]. 计算机应用, 2020, 40(9): 2670-2676.
[8]	张凯, 周德云, 杨振, 潘潜. 多约束集群目标下武器-目标分配问题[J]. 计算机应用, 2020, 40(3): 902-911.
[9]	郝秦霞. 基于R2指标的高维多目标差分进化推荐式课程系统[J]. 计算机应用, 2020, 40(10): 2951-2959.
[10]	刘明, 董明刚, 敬超. 基于定期竞争学习的多目标粒子群优化算法[J]. 计算机应用, 2019, 39(2): 330-335.
[11]	林立, 孟学雷, 宋仲仲. 考虑区域协调性的城际列车开行方案优化[J]. 计算机应用, 2019, 39(2): 598-603.
[12]	蔺凯青, 李志华, 郭曙杰, 李双俐. 云环境中多目标优化的虚拟机放置算法[J]. 计算机应用, 2019, 39(12): 3597-3603.
[13]	谭阳, 唐德权, 曹守富. 基于超球形模糊支配的高维多目标粒子群优化算法[J]. 计算机应用, 2019, 39(11): 3233-3241.
[14]	刘宝, 董明刚, 敬超. 改进的排序变异多目标差分进化算法[J]. 计算机应用, 2018, 38(8): 2157-2163.
[15]	赵云钦, 蔡超, 王厚军, 李东武. 基于带电粒子搜索的无人潜航器航路规划方法[J]. 计算机应用, 2018, 38(7): 2107-2112.