21世纪,随着高新技术应用的推动,制造业的发展步伐也在逐渐加快,不断朝着全球化、专业化和服务化的方向大步迈进。制造企业为了应对知识经济和制造全球化的挑战,同时为了快速响应市场需求和提高企业市场竞争力,以敏捷制造、制造网格(MGrid)和应用服务提供商(ASP)等为代表的网络化制造模式应运而生。尽管经过十几年的发展,制造网格模式在不同领域取得了一定的成果,但仍然在服务模式、制造资源共享和分配技术以及安全问题等方面存在瓶颈。
因此李伯虎等[1]率先提出了一种面向服务的网络化制造新模式——云制造,文中在制造资源共享方面指出,云制造模式不仅要体现“分散资源集中使用”的思想,还要有效的实现“集中资源分散服务”的思想。自云制造理论提出以来,学术界普遍关注其层级结构[2]、典型特征[3]、关键技术[4]、资源虚拟化[5-6]以及运行模式[7]等方面的研究,并且已经取得了大量的理论研究和实际应用成果。然而与之相比,关于云制造环境下制造资源优化配置经济主体与云平台运营方之间行为变化的研究较少。王时龙等[8]在考虑物料流和信息流对时间和成本的实际影响情况下,构建了以成本和时间最小化、质量最优化为目标的资源优化配置模型。李慧芳等[9]在对制造云服务进行形式化的描述基础上,以达到最高匹配度为目标,提出了一种智能化的制造云服务搜索与匹配方法。高一聪等[10]提出了一种基于模糊积分的云制造资源服务匹配方法,研究不同云制造资源之间的相互影响。邰丽君等[11]提出了一种应对突发事件的动态调度技术,并基于云制造服务资源建立了多目标调度模型,作用模型在云制造服务资源的动态调度上有一定的突破。Lin等[12]提出了一种基于遗传算法的资源约束项目调度方法,将云计算系统中资源计算分配问题引入了一些类似增强和局部搜索的新思想,该算法可以最佳地分配计算资源,有效地满足用户需求。Li等[13]为了优化制造资源的配置,提出了一种基于改进免疫算法的云制造服务模式,有效地解决了资源配置的效率问题。赵道致等[14]从经济主体的利益分析角度出发,建立了随机需求下制造资源在两个企业间的转移模型。Seok等[15]以长期期望利润最大化为目标,研究了不联盟、静态联盟和动态联盟3种情况下制造企业对制造服务能力共享应采取的策略,引起了学者的广泛关注。然而云制造平台运营方和制造企业作为参与制造资源优化配置的利益相关者,并没有在上述文献中得到重视,仅有的文献在影响资源配置因素的选择上也不够全面,但是却提供了一些针对性的思路和方法。苏凯凯等[16]在充分考虑制造服务需求方和云制造平台运营方的利益需求的基础上,提出了以服务质量指标和柔性指标多目标优化函数作为博弈双方的收益函数,建立了非合作博弈模型,有效解决了云制造环境下制造资源优化配置问题。夏世洪等[17]构建了兼顾交货期时间最小化、服务成本最低化、服务质量最优化为目标的多目标虚拟资源调度模型,并提出了一种改进的遗传算法,保证了算法的全局与局部搜索能力,提高了算法的适应性。李芳等[18]通过建立供应链选择的三维结构模型,通过蝙蝠算法的量化求解,实现了云制造环境下各个节点企业的快速组合。
上述文献表明当前研究大多只从制造资源需求企业角度考虑时间、成本和质量等因素并建立多目标优化模型,选取的影响因素较为单一,在模型的角度忽略了云制造环境下制造资源优化配置的不确定性,而在建立多目标优化模型之后往往采用加权的方法将多目标问题简化为单目标优化问题,在算法的角度简化了云制造环境下资源优化配置问题实际寻优的复杂性,无法适应云平台的实际运作。这不但让制造企业在制造资源配置实施过程中面临较大的风险,同时也不能反映云平台运营方作为资源配置的重要利益相关者的利益。因此,本文充分考虑云制造环境下制造资源需求企业和云平台运营方的利益,针对无需求偏好的制造资源优化配置问题进行深入研究,全面考虑制造资源配置服务实施过程中涉及到的因素,构建以代表制造资源需求企业和云平台运营方利益的多目标资源优化配置模型,并基于改进的带精英策略的快速非支配排序遗传算法(nondominated sorting genetic algorithm Ⅱ,NSGA-Ⅱ)对模型算例进行寻优求解。
1 云环境下制造资源配置问题描述云制造环境下制造资源优化配置服务实施过程的主体分别是制造资源需求企业、制造资源提供企业和云平台运营方。制造资源提供企业通过借助物联网(internet of things)、信息物理融合系统(cyber physical system)、计算系统虚拟化(virtualization)实现资源的互联、识别、感知以及信息传输,从而实现物理制造资源的虚拟化,完成虚拟制造资源云池的构建。制造资源需求企业根据自身的需求在云平台上发布制造单一制造资源需求任务或者组合资源需求任务。而云平台运营方则主要承担制造资源配置服务过程中可能出现的风险,同时通过约束制造资源提供企业来保证制造资源配置服务顺利进行。因此,在任务需求确定的前提下,如何找到最佳的制造资源服务或服务组合,是云制造环境下制造资源优化配置服务实施过程中急需解决的关键问题。
本文针对无需求偏好的制造资源配置问题,以组合制造资源需求任务为例展开深入研究。制造资源需求企业发布的组合制造资源需求任务通过云制造平台按照一定的规则和一定的时序排列约束被分解为单一制造资源需求子任务(cloud manufacturing sub task,CMST),然后云制造平台为每个子任务分配一个候选制造资源集合,继而在多目标和多约束条件下完成服务路径的寻优。图1为云制造环境下组合制造资源需求任务分解层次。
1) 本文不考虑同一地理位置的资源配置优化组合,只研究跨地理位置的资源优化配置。
2) 制造资源需求企业发布的云需求任务可根据云平台制定的相关工艺规则分解成n个子任务,并且云平台根据已经形成的匹配原则,在虚拟制造资源云池检索并筛选相应的候选制造资源集合。本文的研究则是寻找出最佳的制造资源服务或服务组合。
3) 云制造环境下制造资源优化配置服务实施过程的主体分别是制造资源需求企业、制造资源提供企业和云平台运营方。云平台上,在制造资源配置服务实施过程中,制造资源需求企业只关注制造资源所需的时间(相邻任务之间物流运输时间、加工时间、等待时间)、成本(相邻任务之间物流运输成本、加工成本、相邻任务之间连接成本)和质量(合格率)等服务质量因素(quality of service,QoS),而云平台运营方为了给制造资源需求企业提供最优质的服务,同时也为了保证云平台的健康发展,则比较关注制造资源提供企业的信誉度、可靠度(资源可靠性和技术可靠性)和服务度(服务能力和服务评价)等柔性因素。
2.2 优化配置目标函数$ \min\; T = \min\; \left[ {\sum\limits_{i=1}^n {{T_{\rm w}}\left( i \right) + \sum\limits_{i=1}^n {{T_{\rm m}}\left( i \right)} } + \sum\limits_{i=1}^{n{\rm{ - }}1} {{T_{\rm l}}} \left( {i,i + 1} \right)} \right], $ | (1) |
$ \min \;C = \min\; \left[ {\sum\limits_{i=1}^{n{\rm{ - }}1} {{C_{\rm l}}\left( {i,i + 1} \right) + \sum\limits_{i=1}^n {{C_{\rm m}}\left( i \right)} } + \sum\limits_{i=1}^{n{\rm{ - }}1} {{C_{\rm{j}}}} \left( {i,i + 1} \right)} \right], $ | (2) |
$\qquad\min \;Q = \min\;\left\{ {\sum\limits_{i=1}^n {[1 - Q(i)]/n} } \right\},$ | (3) |
$\qquad\min\; {\rm{Re}} = \min\; \sum\limits_{i=1}^n { {[1 - {\mathop{\rm Re}\nolimits} (i)]/n} } ,$ | (4) |
$\min\; {\rm Te} = \min \;\sum\limits_{i=1}^n { {\omega _r}\left[ {\left( {1 \!-\! {T_{\rm{r}}}\left( i \right)} \right)/n} \right] \!+\! {\omega _{\rm{t}}}\left[ {\left( {1-{T_{\rm{t}}}\left( i \right)} \right)/n} \right] }, $ | (5) |
$\min\;{\rm Se} = \min \sum\limits_{i=1}^n { {\omega _{\rm{e}}}\left[ {\left( {1 \!-\! {S_{\rm{e}}}\left( i \right)} \right)/n} \right] + {\omega _{\rm{v}}}\left[ {\left( {1 \!-\! {S_{\rm{v}}}\left( i \right)} \right)/n} \right] }{\text{。}} \!\!\!\!\!\!\!\!$ | (6) |
其中,式(1)是总时间目标函数,
$\qquad{T_{\max }} {\text{≥}} \left[\sum\limits_{i=1}^n {{T_{\rm l}}(i) +\! \sum\limits_{i=1}^n {{T_{\rm m}}(i)} } +\sum\limits_{i=1}^{n-1} {{T_{\rm w}}} (i,i +1)\right],$ | (7) |
$\qquad{C_{\max }} {\text{≥}} \left[\sum\limits_{i=1}^n {{C_{\rm l}}(i) + \sum\limits_{i=1}^n {{C_{\rm m}}(i)} } + \sum\limits_{i=1}^{n-1} {{C_{\rm{j}}}} (i,i + 1)\right],$ | (8) |
$\qquad\sum\limits_{i=1}^n {Q(i)/n} - {Q_{\min }} {\text{≥}} 0,$ | (9) |
$\qquad\sum\limits_{i=1}^n {{\mathop{\rm Re}\nolimits} (i)/n} - {{\mathop{\rm Re}\nolimits} _{\min }} {\text{≥}}0,$ | (10) |
$\qquad\sum\limits_{i=1}^n {\left[ {{\omega _{\rm r}}\left( {{T_{\rm{r}}}\left( i \right)/n} \right) + {\omega _{\rm t}}\left( {{T_{\rm{t}}}\left( i \right)/n} \right)} \right]} -{{\rm Te}_{\min }} {\text{≥}} 0,$ | (11) |
$\qquad\sum\limits_{i=1}^n {\left[ {{\omega _{\rm e}}\left( {{S_{\rm{e}}}\left( i \right)/n} \right) + {\omega _{\rm v}}\left( {{S_{\rm{v}}}\left( i \right)/n} \right)} \right]} -{{\rm Se}_{\min }} {\text{≥}} 0{\text{。}}$ | (12) |
其中,式(7)为总时间约束,即云需求任务分解下的子任务相对应的制造资源完成交货的总时间不能大于最迟交货时间
MOP(multi-objective optimization problems)问题为NP-Hard问题,本文构建的模型目标函数就是属于MOP问题,因此问题的求解十分复杂。目前解决MOP问题的多目标优化算法有很多,而Kalyanmoy[19]提出的带精英策略的快速非支配排序遗传算法(nondominated sorting genetic algorithm Ⅱ,NSGA-Ⅱ)无疑是其中应用最广泛也是最成功的一种。因此本文提出了一种基于NSGA-Ⅱ的改进算法,在父子种群合并时,需要在两倍于种群大小的个体中修剪出个数等于种群大小的个体,NSGA-Ⅱ算法在修剪种群时只对最后进入新种群的前端进行拥挤排序,严重破坏了种群的多样性。图2为传统NSGA-Ⅱ算法种群修剪示意图。
为了在修剪种群时保证种群的多样性,不破坏已有的种群结构且达到精简种群大小的目的,本文设定最优前端个体系数,来计算第一前端中允许被保留的个体数目,并按照一定的公式来计算其他前端中可以被保留的数目。因此,某个前端中保留的个体数目为min {允许保留的个体数目,现存个体数目}。即当允许被保留的数目小于现存个体的数目时,所设定的最优前端个体系数对该前端个体数目具有限制作用,因此最优前端个体系数的设定对第一前端的个体数目具有直接决定作用,对于其他前端也有类似作用。图3为改进NSGA-Ⅱ算法种群修剪示意图。
解决优化配置问题的一般流程如图4,图中g为遗传迭代数,gmax为最大遗传迭代数。
步骤1 针对每个子任务随机选择候选制造资源服务进行整数型编码,每个编码位置对应该子任务候选服务序号,编码数值则对应该子任务候选制造资源服务序号,例如:4-3-2-1-5-4则表示第1个子任务选择对应的候选制造资源服务为第4个,第2个子任务选择对应的候选制造资源服务为第3个,以此类推。
步骤2 以式(7)~(12)为约束类型,将变量x限定在搜索范围内,随机产生初始种群P。
步骤3 根据适应度函数式(1)~(6)分别计算不同适应度函数下种群P的非支配前端排序并根据排序分别计算每个前端中个体的拥挤度。
步骤4 根据步骤2的种群P中的非支配排序和每个前端中的个体拥挤度,采用锦标赛函数进行选择操作,然后进行交叉、变异操作,产生新种群G,并与种群P合并,得到合并种群PG。
步骤5 据适应度函数式(1)~(6)分别计算不同适应度函数下种群PG的非支配前端排序并根据排序分别计算每个前端中个体的拥挤度,根据设定的最右前端个体系数,修剪种群PG产生新种群newP。
步骤6 重复步骤3~5,直至g满足最大迭代数gmax,输出Pareto解。
4 实例验证制造资源需求企业在云平台上发布了组合资源任务需求,首先云平台按照一定的规则和一定的时序排列约束将组合资源任务分解为5个单一制造资源需求子任务,分别为CMST1、CMST2、CMST3、CMST4、CMST5。其中,对于每个子任务CMSTn(n表示子任务的序号)按照匹配机制筛选出符合要求的候选制造资源CMRSnm(m表示子任务n对应的候选制造资源),如表1所示,与候选制造资源相关参数如表2所示。
资源配置优化模型中的各参数均由制造资源需求方和云平台运营方根据制造任务的类型和具体内容共同决定。本文假设模型中的各参数如下:
为了验证模型的适用性,针对上述实例,运行算法得到结果(如表3)。由于多目标算法最终得到的不是一个最优解,而是一个非劣解集,因此更加贴合企业实际情况,企业可根据自身实际情况的需要从非劣解集中选择一个解作为该问题的最终解。同时,为了检验算法的有效性和稳定性,本文针对上述实例,将所提出的改进的NSGA-Ⅱ算法与传统的NSGA-Ⅱ算法进行性能对比分析,将两种算法分别运行50次,得到结果如表4所示。改进的NSGA-Ⅱ算法得到的Pareto解在均值方面均优于传统的NSGA-Ⅱ算法,这说明改进的NSGA-Ⅱ算法在有效性方面有明显的提高;同时改进NSGA-Ⅱ算法和传统的NSGA-Ⅱ算法求出Pareto解平均遗传代数分别为22代和34代,相对于传统的NSGA-Ⅱ算法,改进的NSGA-Ⅱ算法有较大幅度的提高,这说明改进的NSGA-Ⅱ算法在稳定性方面有明显的提高。
本文针对云制造环境下制造资源优化配置问题,全面分析了复杂的制造资源服务过程,考虑了制造资源需求企业的服务质量因素和云平台运营方的柔性因素,构建了兼顾时间、成本、质量、信誉度、可靠度、服务性6个方面的多目标优化资源配置模型,并基于改进NSGA-Ⅱ算法对模型做出了算例求解。计算结果表明本文提出的模型和改进NSGA-Ⅱ算法有效地解决了云制造环境下复杂的制造资源优化配置问题。下一步工作将继续研究云制造环境下动态资源优化配置问题,优化资源配置模型的参数和变量,提高模型、算法的适用性、有效性和稳定性,使其更加贴近于企业的实际情况。
[1] |
李伯虎, 张霖, 王时龙, 等. 云制造—面向服务的网络化制造新模式[J].
计算机集成制造系统, 2010, 16(1): 1-7.
LI Bohu, ZHANG Lin, WANG Shilong, et al. Cloud manufacturing: a computing and service-oriented manufacturing model[J]. Computer Integrated Manufacturing Systems, 2010, 16(1): 1-7. |
[2] |
TAO F, ZHANG L, VENKATESH V C. Cloud manufacturing: a computing and service-oriented manufacturing model[C/OL]. (2011-08-22). https://journals.sagepub.com/doi/abs/10.1177/0954405411405575
|
[3] |
李伯虎, 张霖, 任磊. 云制造典型特征、关键技术与运用[J].
计算机集成制造系统, 2012, 18(7): 1345-1356.
LI Bohu, ZHANG Lin, REN Lei, et al. Typical characteristic, technologies and applications of cloud manufacturing[J]. Computer Integrated Manufacturing Systems, 2012, 18(7): 1345-1356. |
[4] |
陶飞, 张霖, 郭华, 等. 云制造特征及云服务组合关键问题研究[J].
计算机集成制造系统, 2011, 17(3): 477-486.
TAO Fei, ZHANG Lin, GOU Hua, et al. Typical characteristic of cloud manufacturing and several key issues of cloud services composition[J]. Computer Integrated Manufacturing Systems, 2011, 17(3): 477-486. |
[5] |
LIU N, LI X.A resource virtualization mechanism for cloud manufacturing systems[C/OL]. (2012-11-07). https://link.springer.com/book/10.1007/978-3-642-33068-1#about.
|
[6] |
LIU N, LI X.A resource & capability virtualization method for cloud manufacturing systems[C/OL]. (2012-11-21).https://ieeexplore.ieee.org/document/6083800.
|
[7] |
WU D, THAMES J L, ROSEN D W. Towards a cloud-based design and manufacturing paradigm: looking backward, looking forward[C/OL]. (2012-10-12).http://proceedings.asmedigitalcollection.asme.org/proceeding.aspx?articleid=1736119.
|
[8] |
王时龙, 宋文艳. 云制造环境下制造资源优化配置研究[J].
计算机集成制造系统, 2012, 18(7): 1396-1405.
WANG Shilong, SONG Wenyan. Manufacturing resources allocation based on cloud manufacturing[J]. Computer Integrated Manufacturing Systems, 2012, 18(7): 1396-1405. |
[9] |
李慧芳, 董训. 制造云服务智能搜索与匹配方法[J].
计算机集成制造系统, 2012, 18(7): 1485-1493.
LI Huifang, DONG Xun. Intelligent searching and matching approach for cloud manufacturing service[J]. Computer Integrated Manufacturing Systems, 2012, 18(7): 1485-1493. |
[10] |
高一聪, 冯毅雄, 谭建荣, 等. 制造资源耦合映射与模糊匹配技术研究[J].
计算机辅助设计与图形学学报, 2012, 24(3): 290-298.
GAO Yicong, FENG Yixiong, TAN Jianrong, et al. Research on coupled mapping and service matching technology of cloud manufacturing based on fuzzy integral[J]. Journal of Computer-Aided Design and Computer Graphics, 2012, 24(3): 290-298. DOI: 10.3969/j.issn.1003-9775.2012.03.002. |
[11] |
邰丽君, 胡如夫, 赵韩, 等. 面向云制造服务的制造资源的多目标动态优化调度[J].
中国机械工程, 2013, 24(012): 1616-1622.
TAI Lijun, HU Rufu, ZHAO Han, et al. Multi-objective dynamic scheduling of manufacturing resources to cloud manufacturing services[J]. China Mechanical Engineering, 2013, 24(012): 1616-1622. |
[12] |
LIN Y K, CHONG C S. Fast GA-based project scheduling for computing resources allocation in a cloud manufacturing system[C/OL]. (2017-04-08).https://link-springer-com-443.webvpn.usst.edu.cn/article/10.1007/s10845-015-1074-0.
|
[13] |
LI Yuan, TAO F. A study of optimal allocation of computing resources in cloud manufacturing systems[C/OL]. (2012-02-15).https://link-springer-com-443.webvpn.usst.edu.cn/ article/10.1007/s00170-012-3939-0.
|
[14] |
赵道致, 杜其光. 物联网平台下企业之间制造资源转移策略[J].
系统工程, 2015, 33(1): 87-93.
ZHAO Daozhi, DU Qiguang. Manufacturing resources transshipment based on internet of things platform[J]. Systems engineering, 2015, 33(1): 87-93. DOI: 10.3969/j.issn.1009-6744.2015.01.016. |
[15] |
SEOK H, NOF S Y. Dynamic coalition reformation for adaptive demand and capacity sharing[C/OL]. (2013-09-19).https://doi.org/10.1016/j.ijpe.2013.09.003.
|
[16] |
苏凯凯, 徐文胜, 李建勇. 云制造环境下基于非合作博弈的资源优化配置方法[J].
计算机集成制造系统, 2015, 21(8): 2228-2239.
SU Kaikai, XU Wensheng, LI Jianyong. Manufcacturing resource allocation method based on non-cooperative game in cloud manufacturing[J]. Computer Integrated Manufacturing Systems, 2015, 21(8): 2228-2239. |
[17] |
夏世洪, 石宇强, 吴双, 等.云制造环境下面向多目标优化的虚拟资源调度研究[J/OL]. (2018-04-08).http://kns.cnki.net/kcms/detail/51.1196.TP.20180408.1050.056.html.
|
[18] |
李芳, 武超然. 云制造环境下供应链节点企业的优化组合[J].
计算机应用研究, 2014, 31(6): 1644-1647.
LI Fang, WU Chaoran. Optimal composition of supply chain node enterprise in cloud manufacturing[J]. Application Research of Computers, 2014, 31(6): 1644-1647. DOI: 10.3969/j.issn.1001-3695.2014.06.009. |
[19] |
KALYANMOY D, AMRIT P, SAMEER A. A fast and elitist multiobjective genntic algorithm: NSGA-Ⅱ[J/OL]. (2002-08-07).https://ieeexplore.ieee.org/document/996017.
|