云制造环境下基于蚁群算法资源动态调度优化

江笑妍　李芳

摘 要：动态资源调度是云制造中的一个关键问题。通过对资源动态在云制造环境下服务特点的了解，提出了基于蚁群算法的资源动态调度函数，以云服务提供者找到相对应的云服务使用者进行任务封装的时间最短为目标。通过Matlab优化了原有的资源动态服务模型，达到了预期的效果，对以后云制造下资源动态的调度具有指导意义。

关键词：云制造；蚁群算法；资源动态调度函数；Matlab

中图分类号：F253.9 文献标识码：A

Abstract： Dynamic resource scheduling is a key problem in cloud manufacturing. Based on resources dynamic characteristics under the environment of cloud manufacturing service，proposed based on ant colony algorithm resources dynamic scheduling function，aiming at the cloud service providers to find the corresponding task encapsulates the cloud service users the shortest time. The original resource dynamic service model was optimized by Matlab， reach the expected effect， under the cloud after manufacturing resources dynamic scheduling has a guiding significance.

Key words： cloud manufacturing； ant colony algorithm； resource dynamic scheduling function； Matlab

0 引 言

随着现在科技的飞速发展，制造业开始逐步与新兴云计算、物联网等技术交叉融合，产生一种面向服务的制造新模式——云制造，它一改制造长期以来面向设备、面向资源、面向订单、面向生产等的形态，从而转而真正面向服务、面向需求。在云制造中，一切能封装和虚拟化的都作为制造云服务（包括制造资源作为服务、制造能力作为服务、制造知识作为服务等）这种大转变是作为实现生产型企业向服务型企业转变、实现制造即服务（Manufacturing-as-a-Service， MFGaaS）的基础。在云制造中，通过物联网、虚拟化等技术实现资源的封装、发布、搜索、调度、执行、检测等功能，满足云服务提供者（Cloud Sevice Provide， CSP）和云服务使用者（Cloud Service User， CSU）之间的资源对接。本文重点讨论资源从CSP动态调度到CSU的这个过程，争取云制造资源的利用率达到最优是我们的目标。

目前各学者对云制造进行了相关研究，李伯虎院士为求解更加复杂的制造问题展开大规模协同制造，提出了一种面向服务的网络化制造新模式——云制造。陶飞、张霖等人设计了制造云服务管理原型系统功能结构， 对基于云制造全生命周期运行的云服务组合需求进行了阐述。对云服务组合建模/描述和一致性检查、云服务关联关系、云服务组合柔性、组合网络及其动力学特性、云服务组合建模与评估、组合优选等实现云服务组合的关键问题进行了研究， 为未来实现高效智能化的云制造服务管理提供理论支持[1]；张勇凯、李芳等人用ROV编码对蝙蝠算法进行了重新编码和解码，并且对其进行了混沌序列初始化和自适应变步长的运算步长改进，提高了原蝙蝠算法的收敛速度和最优解的精度[2]，倪志伟、王会颖等人基于云计算技术和云服务技术研究了云服务的动态选择问题，给出了云制造服务层次化模型，提出了一种基于MapReduce和多目标蚁群算法的制造云服务动态选择算法（CSSMA）[3]；武超然、江海涛通过改进蝙蝠算法，实现了供需调度时间的最优[4]；唐海波、黄琼琼等提出了基于负载资源的均衡的动态调度策略，建立了以完成任务的总服务成本为最优化目标的模型，并实际验证了可行性[5]。以上对于云制造资源调度的研究还有很大的发展空间，本文将以云制造资源的利用率为目标进行研究讨论。

1 云制造资源调度过程的描述

云制造资源的调度其实是实现云服务提供者CSP到云服务使用者CSU对接的过程。云服务提供者CSP包括原材料供应商、加工生产商、物流配送商等，他们各自将自身可以提供的资源登记在云服务的平台，等待云制造资源的出租销售；而云制造资源这个虚拟的资源是游离在云服务平台的，毫无序列而言，只等待搜索到相对应的云服务使用者CSC后，封装到某个生产生命周期，供云服务使用者USU使用；而云服务使用者CSU向云服务平台提出自己的需求，等待平台安排相应的云制造资源供其使用。

1.1 质量检测机制。在已经匹配好的一系列生命周期的生产工序中，前一个云服务提供者CSP完成这一项工序后要被检测合格后才可转交给下一个云服务提供者CSP进行下一项工序，否则重新完成。这样既可保证服务质量，又可减少损失，如若没有合格标准检测机制，不光会导致整条服务的不合格，云服务使用者不满意，而且无法完成这一项任务，整个生命周期需要的云服务提供者CSP都要重新来过，浪费了其他云服务提供者CSP的时间，降低了整个云服务资源的利用率。

1.2 原始资源动态调度过程。由于云服务平台数据处理的冗杂性，将有相同需求的云服务使用者CSU作为同一批次进行处理，通过关键词搜索需要的一系列云制造资源，将它们进行封装，作为一个整体完成任务。只有当所有的云服务使用者CSU的任务需求全部完成时，云服务提供者CSP才可以被释放，成为原来的游离状态，即可以继续下一批次的任务所搜索，继而封装在另一个整体工作。endprint

从图1可知，第一批次是有5个云服务提供者CSP1，2，3，4，5完成云服务使用者CSU1，2，3，4，5，6，7，8的任务，随机产生的任务安排为2，4，1，3，3，5，1，2表示第一个任务由CSP2完成，第二个任务由CSP4完成，第三个任务由CSP1完成，第四、五个任务都由CSP3完成，第六个任务由CSP5完成，第七个任务由CSP1完成，最后一个任务由CSP2完成。

1.3 改进后的资源动态调度过程。通过原始的资源动态调度过程图解可以看出，CSP1在完成第七个任务后闲置了一个工序，CSP2一直要完成最后一次才可被释放，CSP3在完成第五个任务后闲置了三个工序，CSP4在完成第二个任务后闲置了六个工序，CSP5在完成第六个任务后闲置了两个工序。由此可知，大部分的CSP是闲置的。

现在就将封装中的CSP进行改进优化，如果某个CSP在完成整个封装中的任务且通过质量监测后可变成游离状态，即可开始搜索CSU进行下一批次的封装任务。假设：

CSP

在每个CSP从任务完成变成游离状态时，它的相应的编码状态也从1变成0，我们在每个批次的封装任务的最后一道工序设置一个可通过CSP状态为0时通过，即可以进行下一批次任务搜索，然后如此循环往复。所以改进后的资源动态调度过程如图2所示：

2 云资源动态调度函数

提高云制造资源的利用率实际上是尽量让每个CSP都在任务中，即大部分时间都在工作，减少不必要的时间浪费，所以我们通过CSP完成一定数量的任务时间来检测云制造资源的利用率。

其中，R是云制造资源利用率，MaxR是我们的优化目标；t 是CSP 完成任务的时间，t 是CSP 通过质量检测的时间，t 包括CSP搜索到匹配的CSU的时间以及等待浪费时间的两部分时间；CSP 代表CSP状态，为0时是闲置状态，即此CSP在本次封装任务中不需要，反之，若为1则是任务状态，即此CSP不能进行搜索本次封装任务。这个时间的比率即可代表云制造资源的利用率。

下面，我们通过将t 最小化来达到整体提高云资源利用率的目标，因为在一定数量任务前提下，完成任务的时间越短，其浪费的等待时间就越少，云资源的利用率就越高。

3 通过蚁群算法进行优化

3.1 蚁群算法的基本思想。蚁群算法（Ant Colony Algorithm， ACA）是由意大利学者M.Dorigo等人提出的一种模拟进化算法，其真实的模拟了自然界蚂蚁群体的觅食行为。蚂蚁在寻找食物时，会在其经过的路上释放一种信息素，并能够感知其他蚂蚁释放的信息素。信息素的浓度的大小表征路径的远近，信息素浓度越高，表示对应的路径距离越短。蚂蚁在路径上前进时会根据前边走过的蚂蚁所留下的分泌物选择其要走的路径。其选择一条路径的概率与该路径上分泌物的强度成正比。因此，由大量蚂蚁组成的群体的集体行为实际上构成一种学习信息的正反馈现象：某一条路径走过的蚂蚁越多，后面的蚂蚁选择该路径的可能性就越大。蚂蚁的个体间通过这种信息的交流寻求通向食物的最短路径。

将蚁群算法应用于解决优化问题的基本思路为：用蚂蚁的行走路径表示优化问题的可行解，整个蚂蚁群体的所有路径构成优化问题的解空间，路径较短的蚂蚁释放的信息素较多，随着时间的推进，较短的路径上累积的信息素浓度逐渐提高，选择该路径的蚂蚁个数也愈来愈多。最终，整个蚂蚁群体会在正反馈的作用下集中到最佳路径上，此时对应的便是待优化问题的最优解。

3.2 改进后蚂蚁个数的设定。蚂蚁群在觅食时，分开各自寻找食物，并通过释放信息素通知其他蚂蚁的路径情况，由于蚂蚁个体寻找路径的不同，寻找到食物的先后顺序是不同的，先找到食物的蚂蚁，会在其经过的路径上释放较高浓度的信息素来通知其他蚂蚁，在其找到食物到达巢穴的最佳途径后便不再外出觅食，此时还在外面觅食的蚁群数量则会相应减少，但整个蚁群的数量是一定的。

原始的蚁群算法在整个过程中，蚂蚁的数量是一成不变的。在本文中，假设在一定的时间内，云资源使用者CSU的个数是一定的，云资源提供者CSP（即虚拟的蚂蚁）的个数是不定的，即随着搜索封装任务的进行，有一部分的CSP是在任务状态的，不能参与搜索任务，但是总的CSP的个数上限是一定的，即在所有的CSP开始和结束任务搜索时的个数是一定的，即CSP没有任务搜索时的个数是一定的。

3.3 算法过程描述。云制造环境下应用蚁群算法解决云资源的动态调度过程可以在图形的帮助下转化为蚁群觅食网络。由CSP1，2，3，4，…，m的集合组成蚂蚁群，与之相对应的是由一系列小节点组成的CSU大节点，按照任务类型的不同，分成不同的小节点，而其中的每一个小节点都是要求类似的CSU群，这一系列的CSU群按照在云平台登记的时间先后排列。CSP集合中的每个个体对CSU群进行搜索，然后按照时间顺序进行任务封装。S代表虚拟起点，E代表虚拟终点，所以本文的云资源的动态调度问题就转化为了寻找从S到E的最短路径问题。蚁群算法对云制造下资源调度过程的描述如图3所示。

3.4 蚁群算法解决云制造下资源调度问题的基本原理。设整个蚂蚁群体中的蚂蚁数量为m，即云制造环境中云制造资源的提供者CSP的数量为m，云制造资源的使用者CSU的数量为n，使用者CSU 与CSU 之间的先后到达时间差为t ，t时刻CSU 与CSU 连接过程中的信息素浓度为τ t。初始时刻，各个CSU之间连接过程中的信息素浓度相同，设为τ 0= τ 。

提供者Kk=1，2，3，…，m根据各个与使用者之间连接过程中的信息素浓度决定下一个搜索的使用者，设P t表示t时刻提供者K从使用者i转移到使用者j的概率，其计算公式为：

其中，μ t为启发函数，μ t=1/t ，表示提供者从使用者i转移到使用者j的期望程度；allow k=1，2，3，…，m为提供者K待访问使用者的集合，开始时，allow 中有n-1个元素，即包括除了提供者K除搜索使用者之外的其他使用者，随着时间的推进，allow 中的元素不断减少，直至为空，即表示所有的使用者搜索完毕；α为信息素重要程度因子，其值越大，表示信息素的浓度在转移中起的作用越大；β为启发函数重要程度因子，其值越大，表示启发函数在转移中的作用越大，即提供者会以较大的概率转移到距离较短的使用者。endprint

如上所述，在提供者释放信息素的同时，各个使用者之间的连接过程上的信息素逐渐消失，设参数ρ（0<ρ<1）表示信息素的挥发程度。因此，当所有提供者完成一次循环后，各个使用者之间连接过程上的信息素浓度需进行实时更新，即：

其中，Δτ 表示第k个提供者在使用者i与使用者j搜索过程中释放的信息素浓度；Δτ 表示所有提供者在使用者i与使用者j搜索过程中释放的信息素浓度之和。

3.5 蚁群算法的优化结果。第一次迭代时，云资源提供者CSP的个数是满值30个，随着CSP在搜索匹配的云资源使用者CSU的过程中，有部分CSP已经搜索到匹配的CSU，即从不匹配的CSU 转移到匹配的CSU ，所以剩下的还未搜索到匹配的CSU的CSP的个数就产生了变化，在本文中，对云资源提供者CSP的个数（蚂蚁数量）采用实时更新机制，使其更符合实际的云资源调度过程。

下面是改进后CSP搜索匹配到匹配的CSU的过程：

图4、图5是改进前、后迭代最短距离与平均距离对比。

通过Matlab进行仿真实验后，得出两个结论：

①最短距离的对比

②局部最优的改进

改进前，在100次迭代中，第40次已达到最优，但此时的最优往往是局部最优，未能找到全局最优；改进后，大概在第72次迭代达到最优，避免局部最优，找到更好的最优解。

我们在初始设置了以月（30）为单位和以天（24）为单位的30组数据，以蚁群算法为基础进行仿真，在100次迭代后，得到了100.8135这个最短距离的最优解，比之前的105.3275的更优化，迭代次数由40增加到72，能够更大可能的找到全局最优解，达到了优化的目的。

通过在Matlab中的仿真实验，发现了改进后，云服务提供者CSP搜索到匹配的云服务使用者CSU的最短距离缩短了，相应的所耗时间也减少了，因为twi包括CSP搜索到匹配的CSU的时间以及等待浪费时间的两部分时间，所以在这里我们便减少了搜索的时间，即减小了twi，在云资源利用率最大化中，成功的提高了利用率R，达到了预期的目标。

4 结 论

本文针对云平台上云资源提供者CSP搜索匹配云资源使用者CSU并进行任务封装的过程，提出了基于蚁群算法的解决方法。通过Matlab的仿真实验，量化数据的前后对比，表明本文对于云资源调度过程的改进是可行的，能够在更短的时间内对云资源提供者CSP和云资源使用者CSU进行匹配，并且避免了局部最优，使得出的最优解更具有说服力，对以后的云资源动态调度过程有一定指导意义。

参考文献：

[1] 陶飞，张霖，郭华，等. 云制造特征及云服务组合关键问题研究[J]. 计算机集成制造系统，2011，17（3）：477-486.

[2] 张勇凯，李芳，等. 改进蝙蝠算法在云制造供应链中的应用[J]. 数学理论与应用，2015，35（2）：83-94.

[3] 倪志伟，王会颖，等. 基于MapReduce和多目标蚁群算法的制造云服务动态选择算法[J]. 中国机械工程，2014，10（20）：2751

-2760.

[4] 武超然，江海涛，等. 云制造平台下基于蝙蝠算法的供需调度时间优化[J]. 现代情报，2014，10（10）：35-40.

[5] 唐海波，黄琼琼，等. 云制造环境下资源动态调度系统研究[J]. 机械工程与自动化，2014，12（6）：4-6.

[6] 付超，肖明. 云制造环境下的云服务组合优选方法[J]. 计算机应用研究，2014，6（6）：1744-1751.

[7] 李芳，单大亚，马婷. 基于多智能体的虚拟企业群协同生产调度模式研究[J]. 计算机应用研究，2013，30（6）：1624-1629.

[8] 吴昊，倪志伟，王会颖. 基于MapReduce的蚁群算法[J]. 计算机集成制造系统，2012，16（7）：1503-1509.

[9] 李伯虎，张霖，王时龙，等. 云制造——面向服务的网络化制造新模式[J]. 计算机集成制造系统，2010，16（1）：1-7，16.

[10] 李伯虎，张霖，任磊，等. 云制造典型特征、关键技术与应用[J]. 计算机集成制造系统，2012，18（7）：1345-1356.

[11] 蔡坦，刘卫宁，等. 一种新的基于直觉模糊集的制造云服务优选方法[J]. 中国机械工程，2014，2（3）：352-356.

[12] 刘卫宁，李一鸣，刘波. 基于自适应粒子群算法的制造云服务组合研究[J]. 计算机集成制造系统，2012，18（10）：2869-2874.

[13] 李京生，王爱民. 基于动态资源能力服务的分布式协同调度技术[J]. 计算机集成制造系统，2012（7）：1563-1574.

[14] 葛江华，孙月洲. 云制造车间资源调度与配置模型及优化研究[D]. 哈尔滨：哈尔滨理工大学（硕士学位论文），2012：59.

[15] Udhayakumar P， Kummana N N S. Sequencing and scheduling of job and tool in a flexible manufacturing system using ant colony optimization algorithm[J]. International Journal of Advanced Mancturing Technology， 2010，50（9-12）：1075-1084.

[16] TAO Fei， ZHAO Dongmi ng， ZHANG Lin. Resource service optimal-selection based on intuitionistic fuzzy set and non-functionality QoS in manufacturing grid system[J]. Knowledge and Informai on Systems， 2010，25（1）：185-208.endprint