基于改进NSGA-Ⅱ的云制造服务组合优化问题研究

工程论文 2020-04-22 09:27138未知xhm
  摘要:为了实现企业在云制造环境下的节能,提出一种新的云制造服务组合优化方法,该方法既能降低能耗,又能在考虑不确定性的情况下提高服务质量。然后利用双目标模型和改进的NSGA-Ⅱ解决制造服务组合优化问题。实例研究结果表明:该模型从云制造服务平台(CMSP)的角度有效地控制了能耗,改进后的NSGA-Ⅱ在解决该问题上具有与MOPSO和标准的NSGA-Ⅱ相比的准确性和收敛性优势。
  关键词:云制造; 服务组合优化; 能耗; 改进的NSGA-Ⅱ;

  1 引言

  近年来,云制造服务及服务组合是云制造模式下供应链资源配置的主要形式[1~2],也是云制造领域中研究的一个热点问题。已有学者对实现云制造服务组合的关键问题进行研究,指出云制造服务组合是实现云制造模式下供应链中各类服务(资源)增值和增效的有效途径之一,并从全制造生命周期的角度出发研究了云制造服务组合的需求。
  服务组合的服务质量关系到云服务最终能否被用户肯定并使用。许多学者将服务质量作为服务组合优化的目标展开研究。其中,刘卫宁等[3]引入了网格制造模式的制造资源服务组合技术,探讨并描述了云制造模式中基于服务质量的制造云服务组合过程。刘志中等[4]使用改进的社会认知算法对服务质量感知的云服务优化组合问题进行了求解。李慧芳等[5]提出了一种基于历史数据的主客观结合服务质量指标权值设定方法。刘翠娟和贾卫兰[6]提出了考虑物流服务影响下的制造云服务组合优选方案,并对物流服务质量指标进行动态评估。张以文等[7]对云服务组合和服务质量进行形式化描述,提出一种改进的基于动态Skyline和多种群遗传粒子群优化的云服务组合优化方法。
  近些年,随着企业对云制造的绿色化和可持续性的不断重视,在服务组合优化过程中,服务及服务组合的能耗也逐步引起业界的关注。其中,陶飞[8]提出了基于组合关联关系的制造资源服务组合网络的动态演化模型和规则,并将研究成果应用到节能减排评估、分析、优化和仿真等服务组合和管理中。向峰等[9]提出了云制造资源服务能耗综合评估框架和能耗计算模型。Singh等[10]应用云计算集成系统对牛肉供应链的碳排放测量及减排问题进行研究。Xing等[11]提出了基于云的生命周期评估平台,用于供应链协作的环境足迹评估。
  通过对已有文献进行梳理发现,首先,云制造服务组合优化模型的研究通常是基于服务质量(Quanlity of Service,QoS)的单目标优化问题,忽略了对服务或者服务组合能耗的关注。其次,以往研究鲜有考虑会给供应链实施过程带来风险的不确定性。最后,用于解决云制造服务组合优化模型的算法在求解速度和质量方面存在缺陷。鉴于此,本文提出了一种新的云制造服务组合优化方法,在考虑QoS、不确定性以及服务及服务组合能耗的基础上建立了云制造服务组合优化的双目标规划模型[12],并使用改进的NSGA-II[13]求解该模型,从而实现节能降耗的目的。

  2 模型和算法

  2.1 问题描述
  云制造模式下供应链的运行要素主要有:
  (1)制造任务
  云制造任务是指在云制造模式下供应链中由云制造服务需求方发起的产品制造需求和任务。根据复杂程度不同,云制造任务可以分为单一和组合任务。
  (2)云制造资源和云制造服务
  云制造资源是指运行于云制造服务平台上基于云制造技术的制造资源。云制造服务是云制造服务平台对云制造资源提供方提交的制造资源虚拟化之后所形成的服务,每一类制造服务可以由多种子制造服务组成。
  (3)云制造服务(资源)组合
  云制造服务(资源)组合是指云制造模式下供应链中为了完成云制造任务而集合在一起的一组制造服务(资源)。它是实现云制造模式下供应链中各类服务(资源)增值和增效的有效途径。
  在云制造模式下的供应链中,云制造服务组合的运作过程为:在一定的云制造任务需求与条件约束下,各类云制造资源虚拟成的服务按照供应链上各环节的顺序规则生成多个服务组合执行路径,然后从所有服务组合执行路径中按照既定任务目标,选择目标最优的路径,从而实现云制造资源—云制造服务—云制造任务之间的合理映射。一般而言,服务组合优化的过程主要针对多个功能需求的任务。多个功能需求的任务被划分为若干个子任务i,其中i=1,2,⋯,m。基于资源的发现机制,云制造服务平台为每个任务返回候选服务,并标记为Rij。{Ri1,Ri2,⋯,Rij,⋯Rini}(j=1,2,⋯,ni)表示任务i的对应候选服务,并且ni是第i个任务的候选服务的数量(如图1所示)。
  2.1.1 QoS的评估
  在云制造服务组合优化过程中,云制造服务需求方主要关注服务的时间、成本、服务质量以及在云制造任务执行过程中出现的将会损害云制造服务平台运营商利益的一系列风险。因此,云制造服务组合优化的QoS的评估应考虑以下四个方面的因素。
  图1 云制造模式下供应链中的服务组合过程
  
  (1)时间T(Rij)
  时间因素主要包括云制造服务的运行时间Tfu(Rij),物流运输时间Ttr(Rij,R(i+1)k)以及每个制造服务的等待时间Twa(Rij),其中Twa(Rij)等于该任务发布时前面等待的所有云制造服务的运行时间总和。
  (2)成本C(Rij)
  云制造服务成本主要包括制造资源Cfu(Rij)的实施成本和物流运输成本Ctr(Rij,R(i+1)k),Cfu(Rij)将随着任务量的变化而变化并呈现梯度变化。
  (3)质量Qse(Rij)
  云制造服务的质量反映了相关任务的质量合格率。
  (4)应对不确定性的能力
  云制造服务提供方应对不确定性的能力是影响云制造模式下供应链提供的云制造服务质量的关键点。其主要体现为以下三个方面:
  1)应对云制造任务变化的响应能力FT(Rij)
  应对云制造任务变化的响应能力主要是指云制造服务提供方在云制造任务发布之后应对云制造任务更改并成功完成云制造任务的能力。该能力主要包括制造资源的功能多样性Ffu(Rij),提供的制造资源的种类数量Fty(Rij)以及同类云制造服务提供方的数量Fco(Rij)。
  2)应对云制造资源变化的响应能力FR(Rij)
  应对云制造资源变化的响应能力是指当云制造任务被分配后,云制造服务中所涉及的制造资源发生变化时,云制造服务提供方能成功完成制造任务的能力。该能力主要包括制造服务的可靠性Fre(Rij)、云制造服务提供方提供的制造服务数量Fsa(Rij)以及同类云制造服务提供方的数量Fco(Rij)。
  3)服务评价指标FE(Rij)
  云制造服务组合优化过程中的服务评价指标由各制造服务的历史服务评价结果表示。各制造服务的历史评价由云制造服务需求方在制造服务过程中提供的满意度评价表示(满意度介于0~1之间)。满意度代表了生产任务过程中的服务态度、服务能力、服务水平以及沟通合作的积极性。满意度越高,说明制造服务对制造任务和制造资源变化的响应能力越强。
  引入决策变量xij,xij,(i+1)k,令xij=1,表示选择第i个子任务中的第j个候选服务,xij=0则表示第i个子任务中的第j个候选服务不被选择;令xij,(i+1)k=1,表示选择第i,j个候选服务到第i+1,k个候选服务,xij,(i+1)k=0表示第i,j个候选服务到第i+1,k个候选服务不被选择。
  综上所述,云制造服务组合优化过程中QoS目标函数如下:
  (1)总完成时间最小化

  
  (2)总成本最小化
  
  (3)总体质量最优,即总质量不合格率最小化
  
  (4)应对制造任务变化的响应能力的最优化
  
  在上面的式中,wfu,wty和wTc分别表示制造资源功能多样性、提供的制造服务的种类数量和同类云制造服务提供方数量的权重系数,并且wfu+wty+w Tc=1。
  (5)应对云制造资源变化的响应能力的最优化

  
  在式中,wre,wsa和wco分别是制造服务可靠性、云制造服务提供方提供的制造服务数量和云制造服务提供方合作企业的数量的权重系数,wre+wsa+wco=1。
  (6)最优化服务评价

  
  2.1.2 服务或服务组合能耗评估
  如文献[9]所述,云制造模式下供应链中服务或服务组合的总能耗主要包括两部分:Enfu和Entr。本文令En表示单个生命周期服务或服务组合的总能耗,Enfu表示服务制造阶段的能耗,Entr表示服务配置和物流运输阶段的能耗。
  Enfu和Entr的数据主要来自于云制造服务平台。在生产过程中,产品的类型、数量以及特性将直接影响能耗的种类以及整个供应链系统的能源效率。不同的服务组合方式,即使对于相同的云制造任务,也会产生不同的能耗值。此外,包装和运输方式将直接或间接地影响供应链系统的总能耗值。
  Enfu评估涉及制造服务的能耗值。因此,必须确定每个制造服务的能耗值,即Enfu(Rij)的值,其中i=1,2,⋯,m,j=1,2,⋯,ni,ni是第i个任务的候选服务的数量。不同云制造服务的服务能力不同,完成云制造任务所需的时间也各不相同,正常负载、空载和超载时的能耗量也不同。假设eRij,c,1,eRi j,c,2和eRi j,c,3分别代表Rij在正常负载、空载和超载时完成制造任务的能耗,其中c=1,2,⋯,q表示能源的类型数,则有如下式:

  
  因此,Enfu(Rij)的值可以由式(8)计算:
  
  在式(8)中,lc是第c种能量的转换系数,并且根据能量的等效值计算。因此,Enfu的值可以通过式(9)计算:
  
  Entr则由两个制造服务之间的物流运输能耗的总和组成。Entr(Rij,R(i+1)k)代表第i个制造服务和第i+1个制造服务之间的物流和运输能耗。因此,Entr的计算如式(10)所示:
  
  则云制造模式下供应链系统的总能耗的计算如式(11)所示:
  
  2.2 云制造服务组合优化模型
  云制造服务组合优化是典型的多目标规划(MOP)问题。云制造模式下供应链的服务组合优化模型可以描述如下:

  
  
  式(16)、(18)、(19)、(20)、(21)、(22)、(23)中,i=1,2,…,m;j=1,2,…ni;
  
  不同的云制造服务需求方在供应链中具有不同的要求和目标。因此,线性加权方法可将MOP转换为单目标问题,并且根据云制造服务需求方的不同需求配置每个目标函数的权重。
  在式(12)中,WT,WC,WQ,WTT,WR和WE分别为时间、成本、质量、应对制造任务变化的响应能力、应对云制造资源变化的响应能力和服务评价的权重系数,并且有WT+WC+WQ+WTT+WR+WE=1。Tmax,Cmax,Qmax,FTmax,FRmax和FEmax分别表示最长时间、最高成本、最优质量、最优应对制造任务变化的能力、最优应对云制造资源变化的响应能力和最优服务评价。S表示既考虑Qos又考虑不确定性的总目标。在式(13)中,En表示能耗目标。
  云制造服务组合优化的约束条件如下所示:
  (1)时间约束
  在式(14)中,云制造服务组合优化模型的总时间T不能超过云制造服务需求方所需的最大交付时间Tmax。
  (2)成本约束
  在式(15)中,云制造服务组合优化模型的总成本C不能高于制云制造服务需求方所需的最大成本Cmax。
  (3)质量约束
  在式(16)中,云制造服务组合优化模型中的任何制造资源的服务质量Qse(Rij)不能小于云制造服务需求方所需的最小服务质量Qmin。
  (4)能耗约束
  在式(17)中,云制造服务组合优化模型的总能耗不能超过云制造服务平台所提出的最大能耗Enmax。
  (5)制造资源的功能多样性约束
  在式(18)中,云制造服务组合优化模型中任何制造资源的功能多样性Ffu(Rij)不小于云制造服务平台运营商要求的最小功能多样性Ffumin。
  (6)制造资源的类型约束
  在式(19)中,云制造服务组合优化模型中的任何云制造资源类型Fty(Rij)不能小于云制造服务平台所要求的最小制造资源类型Ftymin。
  (7)制造资源的可靠性约束
  在式(20)中,云制造服务组合优化模型中任何云制造资源的可靠性Fre(Rij)不能低于云制造服务平台所要求的最小可靠性Ffumin。
  (8)具有相同功能的制造资源的数量约束
  在式(21)中,云制造服务组合优化模型中的任何云制造服务供应商提供的具有相同功能Fsa(Rij)的制造资源的数量不能少于云制造服务平台所要求的最小资源数量Fsamin。
  (9)云制造服务提供方合作企业的数量约束
  在式(22)中,由云制造服务组合优化模型的任何云制造服务供应商提供的合作企业数量Fco(Rij)不能低于云制造服务平台所要求的最小合作企业数量Fcomin。
  (10)服务评估约束
  在式(23)中,云制造服务组合优化模型中的任何制造资源的服务评价值FE(Rij)不能低于云制造服务平台所要求的最低服务评价值FEmin。
  2.3 算法的选择及其流程
  本文提出的云制造服务组合优化模型是一个多目标规划问题(MOP),属于NP难题,因此求解方法比较复杂。NSGA-II[13]是NSGA的改进算法,是多目标优化算法之一。然而,NSGA-II也具有缺陷,例如早熟收敛问题。为了改善标准NSGA-II的早熟收敛问题,本文提出了非支配冗余个体变异策略。
  定义子算法A(P,T,S):
  (1)算法输入种群P和数字T以及S,并设定空集合Pe,T=0表示是生成初代种群任务,T=1表示生成子代种群任务,S表示需要输出多少个满足符合约束条件的解。
  (2)Ps表示P中满足约束条件的个体集合,len(Ps)表示集合Ps中个体数量。
  (3)令Pe=Pe∪Ps,判断len(Pe)>=S是否成立,如果成立则算法结束并输出Pe,否则执行下一步。
  (4)如果T=0,则随机生成种群P替代输入种群P;如果T=1则对输入种群P进行交叉变异操作,然后跳至步骤(2)。
  改进的NSGA-II算法的实施流程为:
  (1)对初始种群进行编码,随机产生数量为N的临时种群Pte,并将初始种群定义为P0=A(Pte,0,N),编码规则为十进制编码,例如候选云制造服务组合MRS1,1-MRS2,2-MRS3,1-MRS4,3所对应的十进制编码为1-2-1-3,其解码规则如下:1)依次读取十进制编码位;2)设当前读取至第i位,其编码为n,则令xin=1,如果当前是最后一位则跳至步骤4),否则执行第3)步;3)设第i+1位编码为k,令xin,(i+1)k=1,跳至第1步;4)令其余决策变量均为0。
  (2)对种群P0进行快速非支配排序并拥挤度计算,如果len(P0)>N,则对P0进行截取操作,截取出N个个体作为P0,截取规则为优先选择非支配层较小的个体,同一非支配层优先选择拥挤度大的个体。
  (3)通过锦标赛从种群Pt中进行选择操作,选择出N个个体组成的种群,并进行交叉和变异,生成数量为N的临时子代种群Qtt,Qtts表示Qtt中满足约束条件的解的集合,如果len(Qtts)=N,令真正子代种群Qt=Qtt,否则Qt=Qtts∪A(Qtt,1,N-len(Qtts))。其中鉴于NSGA-II算法的运行后期,在群体中会产生大量的冗余解,出现新解的可能性降低,本文应用非支配冗余个体变异策略进行变异操作,即每代中具有相同目标向量的非支配解被认为是冗余解,而对于冗余解,监督每一代产生的非支配解,如果包括多余个体,则只保存其中一个个体,剩余的个体将以100%的概率进行突变以保留总群的数量。因此,可以消除每一代种群中的多余个体。此外,多余的个体通过变异被转变为非冗余个体,可以更好地保留原始个体的优势,并避免随机搜索对种群个体进化的影响。
  (4)合并种群Pt和Qt,得到组合种群Rt。
  (5)对种群Rt进行快速非支配排序并计算拥挤度,使用精英保留策略选出最优的N个个体,组成新的种群Pt+1。
  (6)令t=t+1,重复以上(3)至(5),直到到达tmax为止,即得到云制造服务组合Pareto解集。

  3 算例分析

  3.1 数据准备
  在算例中,云制造服务需求方将其制造任务和相应的QoS规范提交给云制造服务平台。随后,云制造服务平台将制造任务划分为四个子任务,每个子任务可以分配候选制造服务,如表1所示。候选制造服务的相关参数如表2所示。
  模型的参数具体如下所示:

  
  3.2 分析和讨论
  3.2.1 非支配冗余个体变异策略的实施及结果分析
  改进的NSGA-II的相关参数设置如下:种群大小为50,迭代次数为100,交叉率为100%。为了验证改进的NSGA-II在解决模型方面的有效性,进行了如下所示的对比试验。场景1表示在不考虑总能耗最低作为目标时使用GA算法的计算结果,情景2表示考虑总能耗最低作为目标时使用改进的NSGA-II算法的计算结果。情景1中的解决方案(单目标云制造服务组合优化问题)与情景2中的解决方案(多目标云制造服务组合优化问题)之间的比较如图2所示。
  表1 候选制造服务
  
  图2显示,与情景1的结果相比,在情景2中使用改进的NSGA-II解决双目标规划问题会出现相当大幅度的能耗降低。总能耗的最大值和最小值分别为443和415,这意味着与情景1相比,情景2中的总能耗值发生了1.56%~7.78%的改善。并且可以观察到S值在改进的NSGA-II中有所增加,即改进的NSGA-II和情景1中的最小值分别为0.576和0.570。上述结果表明,改进的NSGA-II通过牺牲QoS性能有效降低云制造模式下供应链实施过程中的总能耗。事实上,这种牺牲是值得的,如果云制造资源提供方提供服务的能耗较高,即便服务的服务质量上略有优势,云制造平台也不会选择其提供服务。这将更有利于云制造模式下供应链更长时期的绿色可持续且健康发展,更有利于远期经济效益和社会效益的获取。
  图2 情景2和情景1的解决方案比较
  
  3.2.2 算法有效性分析
  在本文中,将通过非支配解的精准性和数量验证算法的有效性。由于多目标粒子群优化算法(MOPSO)和标准NSGA-II通常用于解决MOP问题,因此本文将改进的NSGA-II与MOPSO、标准NSGA-II进行了比较。分析结果如表3所示。
  如表3所示,f1和f2是目标函数,并且算法每轮连续运行10次。改进的NSGA-II中非支配解的数量要多于其他模型的数量。此外,通过改进的NSGA-II获得的非支配解的准确度也要优于或等于MOPSO和标准NSGA-II。显然,非支配冗余个体变异策略能够确保在进化过程中保留优秀个体以维持群体的高度多样性并提高优化结果的准确性。
  为了验证考虑非支配冗余个体突变策略的NSGA-II收敛性是否优于标准NSGA-II,本文用Van Veldhuizen[14]定义的RP指标描述算法的收敛性。标准NSGA-II和改进的NSGA-II的RP值曲线如图3所示,改进的NSGA-II的RP曲线明显高于标准NSGA-II的RP曲线。因此,改进的NSGA-II的非支配解更接近理想点。
  图3 标准NSGA-II和改进的NSGA-II的RP值曲线
  
  表2 候选制造服务的相关参数
  
  
  表3 算例结果的比较
  

  4 结论

  降低云制造模式下的能耗并且保持良好的性能是一个值得长期考虑的难题。针对这一问题,本文提出了一种新的服务组合优化方法,该方法综合考虑了云制造环境中的不确定性、QoS和能耗,随后建立了双目标规划模型,并用改进的NSGA-Ⅱ进行求解,通过分析发现改进的NSGA-Ⅱ与MOPSO和标准的NSGA-Ⅱ相比,在求解质量和算法的收敛性方面更具有优势。未来的实际制造系统越来越向低碳化绿色化方向发展,该模型可以有效嵌入到云制造模式下供应链的ERP系统中,以最低的成本实现云服务实施过程中的节能降耗。

  参考文献
  [1]任磊,任明仑.基于学习与协同效应的云制造任务动态双边匹模型[J].中国管理科学,2018,26(07):63-70.
  [2]吴燕霞,贾国柱,栾世超,等.基于云制造的资源优化配置模型[J].系统工程,2018,36(03):122-128.
  [3]刘卫宁,李一鸣,刘波.基于自适应粒子群算法的制造云服务组合研究[J].计算机应用,2012,32(10):2869-2874,2878.
  [4]刘志中,雷冠军,薛霄,等.Qo S感知的云服务优化组合研究[J].计算机应用研究,2012,29(10):3919-3921.
  [5]李慧芳,宋长刚,董训,等.考虑物流服务的云服务组合Qo S评价方法研究[J].北京理工大学学报,2014,34(2):171-175,191.
  [6]刘翠娟,贾卫兰.物流云服务优选及其在云制造中的应用研究[J].现代电子技术,2016,39(11):120-124.
  [7]张以文,吴金涛,郭星,等.一种基于动态Skyline和遗传粒子群优化的云服务组合方法[J].小型微型计算机系统,2016,37(11):2552-2557.
  [8]陶飞.基于BA模型的制造资源服务组合网络建模与动力学特性研究[J].机械工程学报,2014(24):136-136.
  [9]向峰,胡业发,陶飞,等.云制造资源服务能耗评估及应用[J].计算机集成制造系统,2012,18(9):2109-2116.
  [10]Singh A,Mishran,Alis I,et al.Cloud computing technology:reducing carbon footprint in beef supply chain[J].International Journal of Production Economics,2015,164:462-471.
  [11]Xing K,Qian W,Zaman A U.Development of a cloud-based platform for footprint assessment in green supply chain management[J].Journal of Cleaner Production,2016,139:191-203.
  [12]Bracken J,Mcgill J T.Mathematical programs with optimization problems in the constraints[J].Operations Research,1973,21(1):37-44.
  [13]Deb K,Pratap A,Agarwal S,et al.A fast and elitist multiobjective genetic algorithm:NSGA-II[J].IEEE Transactions on Evolutionary Computation,2002,6(2):182-197.
  [14]Veldhuizen D,Lamont G.Evolutionary Computation and Convergence to a Pareto Front:Proceedings of the Genetic Programming Conference,USA,July 22-25,1998[C].Stanford:Stanford University Bookstore,1998:221-228.

53学术论文网 Copyright @ 53论文网 All Rights Reserved. 版权所有


友情链接: 北京财经网