云制造环境下面向多目标优化的虚拟资源调度研究
|
摘要
为解决云制造环境下虚拟资源调度存在的算法求解效率不高、模型建立缺乏考虑任务间关系约束和任务间及子任务间的物流时间及成本因素等不足,构建了兼顾交货期时间最小化、服务成本最低化、服务质量最优化为目标的多目标虚拟资源调度模型;采用一种基于项目阶段的双链编码方式进行编码,并提出自适应交叉与变异概率公式,以避免交叉、变异概率始终不变导致算法效率下降与过早收敛的问题;在此基础上利用基于项目阶段的多种交叉变异策略相结合的改进遗传算法进行求解,保证了算法的全局与局部搜索性能。实例结果表明,相比于传统的模型与算法,该模型适用性更强,改进的遗传算法在求解效率、准确度与稳定性方面均有较大提高。
In virtual resources scheduling of cloud manufacturing,algorithms were often inefficient; relational constraints between tasks,as well as logistics time and cost between tasks and sub-tasks,were not fully considered while modeling. In order to solve these problems,this paper constructed a multi-objective virtual resources scheduling model with the goal of minimizing the delivery time,minimizing the service cost and optimizing the quality of service. It used a double-stranded coding method based on project stage,and proposed an adaptive crossover and mutation probability formula,so as to avoid the low efficiency or premature convergence of algorithm caused by the invariance of crossover and mutation probability. On this basis,to guarantee the global and local search algorithm performance,it used an improved genetic algorithm combined with multiple crossover and mutation strategies based on project phase. The example shows that this model is more applicable than the traditional ones,and the improved genetic algorithm has considerable improvement in efficiency,accuracy and stability.
In virtual resources scheduling of cloud manufacturing,algorithms were often inefficient; relational constraints between tasks,as well as logistics time and cost between tasks and sub-tasks,were not fully considered while modeling. In order to solve these problems,this paper constructed a multi-objective virtual resources scheduling model with the goal of minimizing the delivery time,minimizing the service cost and optimizing the quality of service. It used a double-stranded coding method based on project stage,and proposed an adaptive crossover and mutation probability formula,so as to avoid the low efficiency or premature convergence of algorithm caused by the invariance of crossover and mutation probability. On this basis,to guarantee the global and local search algorithm performance,it used an improved genetic algorithm combined with multiple crossover and mutation strategies based on project phase. The example shows that this model is more applicable than the traditional ones,and the improved genetic algorithm has considerable improvement in efficiency,accuracy and stability.
引文
[1]Xu Xun.From cloud computing to cloud manufacturing[J].Robotics and Computer Integrated Manufacturing,2012,28(1):75-86.
[2]李伯虎,张霖,任磊,等.云制造典型特征、关键技术与应用[J].计算机集成制造系统,2012,18(7):1345-1356.(Li Bohu,Zhang Lin,Ren Lei,et al.Typical characteristics,technologies and applications of cloud manufacturing[J].Computer Integrated Manufacturing System,2012,18(7):1345-1356.)
[3]熊永华,王静,吴敏,等.面向多目标优化的云制造虚拟资源调度方法[J].计算机集成制造系统,2015,21(11):3079-3087.(Xiong Yonghua,Wang Jing,Wu Min,et al.Virtual resource scheduling method of cloud manufacturing oriented to multi-objective optimization[J].Computer Integrated Manufacturing System,2015,21(11):3079-3087.)
[4]李慧芳,董训,宋长刚.制造云服务智能搜索与匹配方法[J].计算机集成制造系统,2012,18(7):1485-1493.(Li Huifang,Dong Xun,Song Changgang.Intelligent searching and matching approach for cloud manufacturing service[J].Computer Integrated Manufacturing System,2012,18(7):1485-1493.)
[5]Lartigau J,Nie Lanshun,Xu Xiaofei,et al.Scheduling methodology for production service in cloud manufacturing[C]//Proc of International Joint Conference on Service Sciences.Piscataway,NJ:IEEEPress,2012:34-39.
[6]Tai Lijun,Hu Rufu,Chen Caowei,et al.Manufacturing resources and demand intelligent matching in cloud manufacturing environment[C]//Proc of the 2nd International Conference on Energy,Environment and Sustainable Development.Piscataway,NJ:IEEE Press,2012:2101-2104.
[7]周龙飞,张霖,刘永奎.云制造调度问题研究综述[J].计算机集成制造系统,2017,23(6):1147-1166.(Zhou Longfei,Zhang Lin,Liu Yongkui.Survey on scheduling problem in cloud manufacturing[J].Computer Integrated Manufacturing System,2017,23(6):1147-1166.)
[8]张卫,潘晓弘,刘志,等.基于云模型蚁群优化的制造服务调度策略[J].计算机集成制造系统,2012,18(1):201-207.(Zhang Wei,Pan Xiaohong,Liu Zhi,et al.Manufacturing service scheduling strategy based on cloud model ant colony optimization[J].Computer Integrated Manufacturing System,2012,18(1):201-207.)
[9]Laili Yuanjun,Zhang Lin,Tao Fei.Energy adaptive immune genetic algorithm for collaborative design task scheduling in cloud manufacturing system[C]//Proc of IEEE International Conference on Industrial Engineering and Engineering Management.Piscataway,NJ:IEEEPress,2011:1912-1916.
[10]Jian Chengfeng,Wang Yong.Batch task scheduling-oriented optimization modelling and simulation in cloud manufacturing[J].International Journal of Simulation Modelling,2014,13(1):93-101.
[11]邰丽君,胡如夫,赵韩,等.面向云制造服务的制造资源多目标动态优化调度[J].中国机械工程,2013,24(12):1616-1622.(Tai Lijun,Hu Rufu,Zhao Han,et al.Multi-objective dynamic scheduling of manufacturing resource to cloud manufacturing services[J].China Mechanical Engineering,2013,24(12):1616-1622.)
[12]Gen M,Zhang Wenqiang,Lin Lin,et al.Recent advances in hybrid evolutionary algorithms for multi-objective manufacturing scheduling[J].Computers&Industrial Engineering,2017,112(10):616-633.
[13]杨从锐,钱谦,王锋,等.改进的自适应遗传算法在函数优化中的应用[J].计算机应用研究,2018,35(4):1042-1045.(Yang Congrui,Qian Qian,Wang Feng,et al.Application of improved adaptive genetic algorithm in function optimization[J].Computer Application Research,2018,35(4):1042-1045.)
[14]王军强,郭银洲,崔福东,等.基于多样性增强的自适应遗传算法的开放式车间调度优化[J].计算机集成制造系统,2014,20(10):2479-2493.(Wang Junqiang,Guo Yinzhou,Cui Fudong,et al.Diversity enhancement-based adaptive genetic algorithm for openshop scheduling problem[J].Computer Integrated Manufacturing System,2014,20(10):2479-2493.)
[15]黄江波,付志红.基于自适应遗传算法函数优化与仿真[J].计算机仿真,2011,28(5):237-240.(Huang Jiangbo,Fu Zhihong.Simulation and adaptive genetic algorithm used in function optimization[J].Computer Simulation,2011,28(5):237-240.)
[16]郑卫.云制造模式下的云资源服务优化调度研究[D].杭州:浙江大学,2015.(Zheng Wei.Research on the cloud resource and service optimal scheduling under cloud manufacturing mode[D].Hangzhou:Zhejiang University,2015.)
[17]赵诗奎.基于遗传算法的柔性资源调度优化方法研究[D].杭州:浙江大学,2013.(Zhao Shikui.Research on the optimization method of flexible resource scheduling based on genetic algorithm[D].Hangzhou:Zhejiang University,2013.)
[2]李伯虎,张霖,任磊,等.云制造典型特征、关键技术与应用[J].计算机集成制造系统,2012,18(7):1345-1356.(Li Bohu,Zhang Lin,Ren Lei,et al.Typical characteristics,technologies and applications of cloud manufacturing[J].Computer Integrated Manufacturing System,2012,18(7):1345-1356.)
[3]熊永华,王静,吴敏,等.面向多目标优化的云制造虚拟资源调度方法[J].计算机集成制造系统,2015,21(11):3079-3087.(Xiong Yonghua,Wang Jing,Wu Min,et al.Virtual resource scheduling method of cloud manufacturing oriented to multi-objective optimization[J].Computer Integrated Manufacturing System,2015,21(11):3079-3087.)
[4]李慧芳,董训,宋长刚.制造云服务智能搜索与匹配方法[J].计算机集成制造系统,2012,18(7):1485-1493.(Li Huifang,Dong Xun,Song Changgang.Intelligent searching and matching approach for cloud manufacturing service[J].Computer Integrated Manufacturing System,2012,18(7):1485-1493.)
[5]Lartigau J,Nie Lanshun,Xu Xiaofei,et al.Scheduling methodology for production service in cloud manufacturing[C]//Proc of International Joint Conference on Service Sciences.Piscataway,NJ:IEEEPress,2012:34-39.
[6]Tai Lijun,Hu Rufu,Chen Caowei,et al.Manufacturing resources and demand intelligent matching in cloud manufacturing environment[C]//Proc of the 2nd International Conference on Energy,Environment and Sustainable Development.Piscataway,NJ:IEEE Press,2012:2101-2104.
[7]周龙飞,张霖,刘永奎.云制造调度问题研究综述[J].计算机集成制造系统,2017,23(6):1147-1166.(Zhou Longfei,Zhang Lin,Liu Yongkui.Survey on scheduling problem in cloud manufacturing[J].Computer Integrated Manufacturing System,2017,23(6):1147-1166.)
[8]张卫,潘晓弘,刘志,等.基于云模型蚁群优化的制造服务调度策略[J].计算机集成制造系统,2012,18(1):201-207.(Zhang Wei,Pan Xiaohong,Liu Zhi,et al.Manufacturing service scheduling strategy based on cloud model ant colony optimization[J].Computer Integrated Manufacturing System,2012,18(1):201-207.)
[9]Laili Yuanjun,Zhang Lin,Tao Fei.Energy adaptive immune genetic algorithm for collaborative design task scheduling in cloud manufacturing system[C]//Proc of IEEE International Conference on Industrial Engineering and Engineering Management.Piscataway,NJ:IEEEPress,2011:1912-1916.
[10]Jian Chengfeng,Wang Yong.Batch task scheduling-oriented optimization modelling and simulation in cloud manufacturing[J].International Journal of Simulation Modelling,2014,13(1):93-101.
[11]邰丽君,胡如夫,赵韩,等.面向云制造服务的制造资源多目标动态优化调度[J].中国机械工程,2013,24(12):1616-1622.(Tai Lijun,Hu Rufu,Zhao Han,et al.Multi-objective dynamic scheduling of manufacturing resource to cloud manufacturing services[J].China Mechanical Engineering,2013,24(12):1616-1622.)
[12]Gen M,Zhang Wenqiang,Lin Lin,et al.Recent advances in hybrid evolutionary algorithms for multi-objective manufacturing scheduling[J].Computers&Industrial Engineering,2017,112(10):616-633.
[13]杨从锐,钱谦,王锋,等.改进的自适应遗传算法在函数优化中的应用[J].计算机应用研究,2018,35(4):1042-1045.(Yang Congrui,Qian Qian,Wang Feng,et al.Application of improved adaptive genetic algorithm in function optimization[J].Computer Application Research,2018,35(4):1042-1045.)
[14]王军强,郭银洲,崔福东,等.基于多样性增强的自适应遗传算法的开放式车间调度优化[J].计算机集成制造系统,2014,20(10):2479-2493.(Wang Junqiang,Guo Yinzhou,Cui Fudong,et al.Diversity enhancement-based adaptive genetic algorithm for openshop scheduling problem[J].Computer Integrated Manufacturing System,2014,20(10):2479-2493.)
[15]黄江波,付志红.基于自适应遗传算法函数优化与仿真[J].计算机仿真,2011,28(5):237-240.(Huang Jiangbo,Fu Zhihong.Simulation and adaptive genetic algorithm used in function optimization[J].Computer Simulation,2011,28(5):237-240.)
[16]郑卫.云制造模式下的云资源服务优化调度研究[D].杭州:浙江大学,2015.(Zheng Wei.Research on the cloud resource and service optimal scheduling under cloud manufacturing mode[D].Hangzhou:Zhejiang University,2015.)
[17]赵诗奎.基于遗传算法的柔性资源调度优化方法研究[D].杭州:浙江大学,2013.(Zhao Shikui.Research on the optimization method of flexible resource scheduling based on genetic algorithm[D].Hangzhou:Zhejiang University,2013.)