考虑能耗与质量的机床构件生产线多目标柔性作业车间调度方法
|
摘要
针对机床构件的生产存在多品种、小批量、生产能耗大的特点,建立以完工时间、空闲时间、加工质量及机器能耗为目标的多目标柔性作业车间调度模型,提出一种基于直觉模糊集相似度的遗传算法(IFS_GA).该算法将直觉模糊集相似度值作为适应度值来引导算法进化;利用拥挤距离修剪外部档案,提高种群的多样性.此外,为提高初始种群的质量,设计一种基于权重的启发式规则.为提高算法的寻优能力,提出一种新的染色体交叉方法,通过直觉模糊集相似度值选出引导体以引导交叉.最后,在可行的Pareto最优解集中,选择直觉模糊集相似度值最大的解作为最满意解.通过算例测试、实例仿真和QUEST软件验证,结果表明,所提出算法是有效的,并且效果优于NSGAII算法.
A multi-objective flexible job shop scheduling model aiming at the completion time, idle time, processing quality and machine tool energy consumption is established according to the characteristics of machine tool components in production such as multi-varieties, small batch and large production energy consumption. And a genetic algorithm based on intuitionistic fuzzy set similarity(IFS GA) is proposed to solve this scheduling model. The intuitionistic fuzzy set similarity value is used as the fitness value to lead the evolution of the algorithm. The crowd distance is used to trim the external files to improve the diversity of the population. In order to improve the quality of the initial population, a weight-based heuristic rule is proposed. A new chromosome cross method is presented to improve the searching ability of the algorithm. The leader is selected by the intuitionistic fuzzy set similarity value to guide the cross. In the feasible Pareto optimal solution, the solution with the highest similarity value of the intuitionistic fuzzy set is selected as the most satisfactory solution. The proposed algorithm is tested with the verification methods of example simulation, instance simulation and QUEST software. The results show that the IFS GA is effective, and it is better than the NSGAII.
A multi-objective flexible job shop scheduling model aiming at the completion time, idle time, processing quality and machine tool energy consumption is established according to the characteristics of machine tool components in production such as multi-varieties, small batch and large production energy consumption. And a genetic algorithm based on intuitionistic fuzzy set similarity(IFS GA) is proposed to solve this scheduling model. The intuitionistic fuzzy set similarity value is used as the fitness value to lead the evolution of the algorithm. The crowd distance is used to trim the external files to improve the diversity of the population. In order to improve the quality of the initial population, a weight-based heuristic rule is proposed. A new chromosome cross method is presented to improve the searching ability of the algorithm. The leader is selected by the intuitionistic fuzzy set similarity value to guide the cross. In the feasible Pareto optimal solution, the solution with the highest similarity value of the intuitionistic fuzzy set is selected as the most satisfactory solution. The proposed algorithm is tested with the verification methods of example simulation, instance simulation and QUEST software. The results show that the IFS GA is effective, and it is better than the NSGAII.
引文
[1]刘于之,李木国,杜海.具有时延和丢包的NCS鲁棒H∞控制[J].控制与决策,2014,29(3):517-522.(Liu Y Z,Li M G,Du H.Robust H∞control of NCS with delay and packet dropout[J].Control and Decision,2014,29(3):517-522.)
[2]徐华,张庭.混合离散蝙蝠算法求解多目标柔性作业车间调度[J].机械工程学报,2016,52(18):201-212.(Xu H,Zhang T.Hybrid discrete bat algorithm for solving the multi-objective flexible job shop scheduling problem[J].Chinese J of Mechanical Engineering,2016,52(18):201-212.)
[3]赵诗奎,方水良.基于工序编码和邻域搜索策略的遗传算法优化作业车间调度[J].机械工程学报,2013,49(16):160-169.(Zhao S K,Fang S L.Operation-based encoding and neighborhood search genetic algorithm for job shop scheduling optimization[J].Chinese J of Mechanical Engineering,2013,49(16):160-169.)
[4]赵小强,何浩.一种求解柔性作业车间调度问题的改进DRSGA[J].南京理工大学学报:自然科学版,2016,40(3):297-302.(Zhao X Q,He H.Improved DRSGA for flexible job shop scheduling[J].J of Nanjing University of Science and Technology:Nature Science,2016,40(3):297-302.)
[5]彭建刚,刘明周,张铭鑫,等.基于改进非支配排序的云模型进化多目标柔性作业车间调度[J].机械工程学报,2014,50(12):198-205.(Peng J G,Liu M Z,Zhang M X,et al.Cloud model evolutionary multi-objective flexible job-shop scheduling based on improved non-dominated sorting[J].Chinese Jof Mechanical Engineering,2014,50(12):198-205.)
[6]Wang B,Wang X Z,Lan F M,et al.A hybrid local-search algorithm for robust job-shop scheduling under scenarios[J].Applied Soft Computing,2018,62(1):259-271.
[7]王雷,蔡劲草,石鑫.基于改进遗传算法的多目标柔性作业车间节能调度问题[J].南京理工大学学报:自然科学版,2017,41(4):494-502.(Wang L,Cai J C,Shi X.Multi-objective flexible job shop energy-saving scheduling problem based on improved genetic algorithm[J].J of Nanjing University of Science and Technology:Nature Science,2017,41(4):494-502.)
[8]Liu Y,Dong H,Lohse N,et al.An investigation into minimising total energy consumption and total weighted tardiness in job shops[J].J of Cleaner Production,201465(4):87-96.
[9]Dai M,Tang D,Giret A,et al.Energy-efficient scheduling for a flexible flow shop using an improved genetic-simulated annealing algorithm[J].Robotics and Computer-Integrated Manufacturing,2013,29(5):418-429.
[10]蒋增强,左乐.低碳策略下的多目标柔性作业车间调度[J].计算机集成制造系统,2015,21(4):1023-1031.(Jiang Z Q,Zuo L.Multi-objective flexible job-shop scheduling based on low-carbon strategy[J].Computer Integrated Manufacturing Systems,2015,21(4):1023-1031.)
[11]魏鑫,张泽群,唐敦兵,等.面向节能的导弹结构件混线生产作业车间多目标调度研究[EB/OL].机械工程学报,[2018-01-25].http://kns.cnki.net/kcms/detail/11.2187.TH.20171211.1455.082.html.(Wei X,Zhang Z Q,Tang D B,et al.Energy-saving oriented multi-objective shop floor scheduling for mixed-line production of missile components[EB/OL]Chinese J of Mechanical Engineering,[2018-01-25]http://kns.cnki.net/kcms/detail/11.2187.TH.201712111455.082.html.)
[12]张闻强,卢佳明,张红梅.流水车间调度问题的快速多目标混合进化算法[J].计算机应用,2016,36(4):1015-1021.(Zang W Q,Lu J M,Zhang H M.Fast multi-objective hybrid evolutionary algorithm for flow shop scheduling problem[J].J of Computer Applications,2016,36(4):1015-1021.)
[13]王晓兰,刘立强,梁琛,等.基于VEGA的风光蓄联合发电系统多目标容量优化[J].电源技术,2016,40(4):840-843.(Wang X L,Liu L Q,Liang C,et al.Multi-objective capacity optimization for wind-solar-battery hybrid power system based on VEGA[J].Chinese J of Power Sources,2016,40(4):840-843.)
[14]张培文,潘全科,李俊青,等.有限缓冲区流水车间调度的混合人工蜂群算法[J].计算机集成制造系统,2013,19(10):2510-2520.(Zhang P W,Pang Q K,Li J Q,et al.Hybrid artificial bee colony algorithms for flowshop scheduling problem with limited buffers[J].Computer Integrated Manufacturing Systems,2013,19(10):2510-2520.)
[15]Deb K.A fast elitist multi-objective genetic algorithm:NSGA-II[J].IEEE Trans on Evolutionary Computation,2000,6(2):182-197.
[16]Deb K,Jain H.An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach,Part I:Solving problems with box constraints[J].IEEE Trans on Evolutionary Computation,2014,18(4):577-601.
[17]Zitzler E,Laumanns M,Thiele L.SPEA2:Improving the strength pareto evolutionary algorithm[R].Switzerland:Gloriastrasse,2001:1-21.
[18]Zhang Q,Li H.MOEA/D:A multiobjective evolutionary algorithm based on decomposition[J].IEEE Trans on Evolutionary Computation,2007,11(6):712-731.
[19]刘胜,于海强.基于改进遗传算法的多目标FJSP问题研究[J].控制工程,2016,23(6):816-822.(Liu S,Yu H Q.Research on multi-objective FJSPproblem based on improved genetic algorithm[J].Control Engineering of China,2016,23(6):816-822.)
[20]杨进帅,李进,王毅,等.基于直觉模糊遗传的武器-目标分配问题优化[J].计算机应用研究,2018,35(1):31-34.(Yang J S,Li J,Wang Y,et al.Optimization of weapon-Target assignment problem by intuitionistic fuzzy genetic algorithm[J].Application Research of Computers,2018,35(1):31-34.)
[21]Atanassov K.Intuitionistic fuzzy sets[J].Fuzzy Sets and System,1986,20(1):87-96.
[22]贺正洪.直觉模糊聚类及其在信息融合中的应用研究[D].西安:空军工程大学防空导弹学院,2010.(He Z H.Research on intuitionistic fuzzy clustering and its application in information fusion[D].Xi’an:Air Defense Missile Academy,Air Force Engineering University,2010.)
[23]周严伟.基于快速非支配排序遗传算法的多目标流水车间调度研究[D].广州:华南理工大学数学学院,2015.(Zhou Y W.Research of multi-objective flow shop scheduling based on fast non-dominated sorting genetic algorithm[D].Guangzhou:College of Mathenatics,South China University of Technology,2015.)
[24]Brandimarte P.Routing and scheduling in a flexible job shop by tabu search[J].Annals of Operations Research,1993,41(3):157-183.
[25]贺利军,刘超,朱光宇.基于模糊关联熵的高维多目标流水车间调度优化[J].计算机集成制造系统,2015,21(10):2704-2710.(He L J,Liu C,Zhu G Y.High-dimensional multi-objective flow shop scheduling optimization based on relative entropy of fuzzy sets[J].Computer Integrated Manufacturing Systems,2015,21(10):2704-2710.)
[2]徐华,张庭.混合离散蝙蝠算法求解多目标柔性作业车间调度[J].机械工程学报,2016,52(18):201-212.(Xu H,Zhang T.Hybrid discrete bat algorithm for solving the multi-objective flexible job shop scheduling problem[J].Chinese J of Mechanical Engineering,2016,52(18):201-212.)
[3]赵诗奎,方水良.基于工序编码和邻域搜索策略的遗传算法优化作业车间调度[J].机械工程学报,2013,49(16):160-169.(Zhao S K,Fang S L.Operation-based encoding and neighborhood search genetic algorithm for job shop scheduling optimization[J].Chinese J of Mechanical Engineering,2013,49(16):160-169.)
[4]赵小强,何浩.一种求解柔性作业车间调度问题的改进DRSGA[J].南京理工大学学报:自然科学版,2016,40(3):297-302.(Zhao X Q,He H.Improved DRSGA for flexible job shop scheduling[J].J of Nanjing University of Science and Technology:Nature Science,2016,40(3):297-302.)
[5]彭建刚,刘明周,张铭鑫,等.基于改进非支配排序的云模型进化多目标柔性作业车间调度[J].机械工程学报,2014,50(12):198-205.(Peng J G,Liu M Z,Zhang M X,et al.Cloud model evolutionary multi-objective flexible job-shop scheduling based on improved non-dominated sorting[J].Chinese Jof Mechanical Engineering,2014,50(12):198-205.)
[6]Wang B,Wang X Z,Lan F M,et al.A hybrid local-search algorithm for robust job-shop scheduling under scenarios[J].Applied Soft Computing,2018,62(1):259-271.
[7]王雷,蔡劲草,石鑫.基于改进遗传算法的多目标柔性作业车间节能调度问题[J].南京理工大学学报:自然科学版,2017,41(4):494-502.(Wang L,Cai J C,Shi X.Multi-objective flexible job shop energy-saving scheduling problem based on improved genetic algorithm[J].J of Nanjing University of Science and Technology:Nature Science,2017,41(4):494-502.)
[8]Liu Y,Dong H,Lohse N,et al.An investigation into minimising total energy consumption and total weighted tardiness in job shops[J].J of Cleaner Production,201465(4):87-96.
[9]Dai M,Tang D,Giret A,et al.Energy-efficient scheduling for a flexible flow shop using an improved genetic-simulated annealing algorithm[J].Robotics and Computer-Integrated Manufacturing,2013,29(5):418-429.
[10]蒋增强,左乐.低碳策略下的多目标柔性作业车间调度[J].计算机集成制造系统,2015,21(4):1023-1031.(Jiang Z Q,Zuo L.Multi-objective flexible job-shop scheduling based on low-carbon strategy[J].Computer Integrated Manufacturing Systems,2015,21(4):1023-1031.)
[11]魏鑫,张泽群,唐敦兵,等.面向节能的导弹结构件混线生产作业车间多目标调度研究[EB/OL].机械工程学报,[2018-01-25].http://kns.cnki.net/kcms/detail/11.2187.TH.20171211.1455.082.html.(Wei X,Zhang Z Q,Tang D B,et al.Energy-saving oriented multi-objective shop floor scheduling for mixed-line production of missile components[EB/OL]Chinese J of Mechanical Engineering,[2018-01-25]http://kns.cnki.net/kcms/detail/11.2187.TH.201712111455.082.html.)
[12]张闻强,卢佳明,张红梅.流水车间调度问题的快速多目标混合进化算法[J].计算机应用,2016,36(4):1015-1021.(Zang W Q,Lu J M,Zhang H M.Fast multi-objective hybrid evolutionary algorithm for flow shop scheduling problem[J].J of Computer Applications,2016,36(4):1015-1021.)
[13]王晓兰,刘立强,梁琛,等.基于VEGA的风光蓄联合发电系统多目标容量优化[J].电源技术,2016,40(4):840-843.(Wang X L,Liu L Q,Liang C,et al.Multi-objective capacity optimization for wind-solar-battery hybrid power system based on VEGA[J].Chinese J of Power Sources,2016,40(4):840-843.)
[14]张培文,潘全科,李俊青,等.有限缓冲区流水车间调度的混合人工蜂群算法[J].计算机集成制造系统,2013,19(10):2510-2520.(Zhang P W,Pang Q K,Li J Q,et al.Hybrid artificial bee colony algorithms for flowshop scheduling problem with limited buffers[J].Computer Integrated Manufacturing Systems,2013,19(10):2510-2520.)
[15]Deb K.A fast elitist multi-objective genetic algorithm:NSGA-II[J].IEEE Trans on Evolutionary Computation,2000,6(2):182-197.
[16]Deb K,Jain H.An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach,Part I:Solving problems with box constraints[J].IEEE Trans on Evolutionary Computation,2014,18(4):577-601.
[17]Zitzler E,Laumanns M,Thiele L.SPEA2:Improving the strength pareto evolutionary algorithm[R].Switzerland:Gloriastrasse,2001:1-21.
[18]Zhang Q,Li H.MOEA/D:A multiobjective evolutionary algorithm based on decomposition[J].IEEE Trans on Evolutionary Computation,2007,11(6):712-731.
[19]刘胜,于海强.基于改进遗传算法的多目标FJSP问题研究[J].控制工程,2016,23(6):816-822.(Liu S,Yu H Q.Research on multi-objective FJSPproblem based on improved genetic algorithm[J].Control Engineering of China,2016,23(6):816-822.)
[20]杨进帅,李进,王毅,等.基于直觉模糊遗传的武器-目标分配问题优化[J].计算机应用研究,2018,35(1):31-34.(Yang J S,Li J,Wang Y,et al.Optimization of weapon-Target assignment problem by intuitionistic fuzzy genetic algorithm[J].Application Research of Computers,2018,35(1):31-34.)
[21]Atanassov K.Intuitionistic fuzzy sets[J].Fuzzy Sets and System,1986,20(1):87-96.
[22]贺正洪.直觉模糊聚类及其在信息融合中的应用研究[D].西安:空军工程大学防空导弹学院,2010.(He Z H.Research on intuitionistic fuzzy clustering and its application in information fusion[D].Xi’an:Air Defense Missile Academy,Air Force Engineering University,2010.)
[23]周严伟.基于快速非支配排序遗传算法的多目标流水车间调度研究[D].广州:华南理工大学数学学院,2015.(Zhou Y W.Research of multi-objective flow shop scheduling based on fast non-dominated sorting genetic algorithm[D].Guangzhou:College of Mathenatics,South China University of Technology,2015.)
[24]Brandimarte P.Routing and scheduling in a flexible job shop by tabu search[J].Annals of Operations Research,1993,41(3):157-183.
[25]贺利军,刘超,朱光宇.基于模糊关联熵的高维多目标流水车间调度优化[J].计算机集成制造系统,2015,21(10):2704-2710.(He L J,Liu C,Zhu G Y.High-dimensional multi-objective flow shop scheduling optimization based on relative entropy of fuzzy sets[J].Computer Integrated Manufacturing Systems,2015,21(10):2704-2710.)