武善玉 张平 李方

（1.华南理工大学 计算机科学与工程学院， 广东 广州510006；2.广东石油化工学院 计算机与电子信息学院， 广东 茂名525000）

随着面向服务架构、云计算、高性能计算、物联网等技术的发展及在制造领域中的应用［1-4］，构造具有开放性、可重构性、互操作性的制造系统的需求和理念不断更新，制造资源服务化的程度也不断加深.李伯虎等［5］最早提出了“云制造”的概念:云制造是一种利用网络和云制造服务平台，按用户需求组织网上制造资源（制造云），为用户提供各类按需制造服务的一种网络化制造新模式.

以制造网格为代表的网络化制造模式主要实现分散制造资源的共享、集成和协同工作，体现的是多对一的服务模式.多用户制造是云制造的典型特征之一［6-7］，因此，如何面向多个制造任务请求，精确调控云制造资源和制造能力，构造整体服务质量最优的组合云服务集合，就成为亟需解决的问题［7］.针对多任务服务组合问题的相关研究未见报道，文献［7］中提出了面向多任务的制造云服务组合问题，并提出了基于矩阵实数编码的遗传算法进行求解.另外，云制造以“制造即服务”的理念为基础，将产品全生命周期需要的一切资源以服务的形式提供给用户，其中包括不受物理位置约束的软件服务，也包括需要具体硬件设备支持的硬件服务.因此，服务间的运输环节不可忽视.王时龙等［8］对考虑运输环节的云制造资源配置问题进行了形式化描述，并对单个任务的资源配置优化问题进行了求解，但未求解多任务调度问题.

文中同时考虑多任务和运输环节两个关键因素，以任务完成时间和成本最优为目标，提出了一种离散粒子群遗传混合算法，以解决云制造多任务调度问题.

1 云制造多任务服务组合优化问题

1.1 问题描述和假设条件

云制造系统面向多任务的服务组合问题综合了制造网格、网络化制造系统面向单用户任务的调度和车间流水线任务调度问题的部分特征［9-12］，但更加复杂.制造网格系统面向单用户任务的调度是从充足的可用资源中选择性能最优的加工路径，车间流水线任务调度则解决x 个包含多道工序的工件在y 台机器上加工的机器分配和工件排序问题.

如图1所示，文中将同类型同优先级的多任务调度问题描述为：在制造系统中，应用层下达的任务中有N 个同类型同优先级生产任务T=｛Ti|i∈［1，N ］｝，其中任务Ti经过分解形成n 个阶段子任务Ti= ｛Tij|j∈［1，n ］｝，Tj*= ｛T1j，T2j，…，TNj｝是所有任务的同一阶段的子任务集，该集合中的所有子任务属于同类型子任务.系统经过服务发现和匹配机制为每个阶段的子任务集筛选出可用服务集合Sj= ｛Sj|kk∈［1，sj］｝，其中sj≥n，Sjk为集合中的第k个服务，相邻两个阶段的子任务对应的服务之间可能存在运输环节.另外，用户与第1 个及最后一个子任务所需服务之间也可能存在运输环节.因此，任务调度即服务组合优化要解决的问题是：为每个阶段子任务集中的子任务分配相应可用集合中的服务，使得最终所有任务完成时间最短，成本最小.该问题的解空间为∏（sj！（sj-N）！）.

图1 问题描述示意图Fig.1 Schematic diagram of problem description

文中假设：①所有等待调度的任务的优先级相同；②所有同批调度的任务具有相同的加工过程；③一个任务的某个加工阶段对应一个子任务；④所有子任务对服务的占用是独占的，直到操作完成才释放该服务；⑤同一任务的子任务之间是顺序关系，即Tij操作完成时间不晚于Ti（j+1）开始时间.

离散粒子群算法和遗传算法等进化算法在车间流水线调度优化中被广泛采用.云制造同类型多任务调度问题中每个阶段子任务的服务分配问题与柔性车间流水线任务调度问题在一定程度上是相似的，但前者包含多个此类加工阶段且还需要考虑相邻加工阶段之间的运输环节，因而要复杂得多.已有相关领域的调度和优化方案不适用于文中要研究的问题，因此针对云制造多任务调度的特点，文中从种群编码、初始化及更新方法等环节考虑，提出了一种离散粒子群遗传混合算法，用于对云制造多任务调度模型进行求解.

1.2 多目标优化模型

文中同时对任务总完成时间（见式（1））和总成本（见式（2））进行优化.

式中，ti和ci分别为任务Ti的完成时间、完成任务Ti所需的成本.设tij和cij（j=1，2，…，n）分别为子任务Tij的加工时间和成本，ti（j，j+1）和ci（j，j+1）分别为子任务Tij与Ti（j+1）之间的物料运输时间和成本（其中j=0，1，…，n；运输时间和成本的大小与相邻两个加工阶段使用的服务及加工任务的属性相关；当j=0时为用户到第1 个子任务的运输环节，j=n 时为成品交付到用户的运输环节）.不考虑资源受限情形，则

该优化问题属于最小化问题，两个目标之间往往是相互矛盾的，同时对这些目标进行优化，属于多目标优化问题.文中的目标函数为

式中，权重系数w1，w2∈（0，1），且w1+w2=1.

2 离散粒子群遗传混合算法

2.1 个体编码

采用整数编码方法建立粒子的位置矢量与服务组合方案的映射关系，粒子维度D=N，第i 维表示任务Ti的子任务选用的服务序列，则第h 个粒子的位置和速度矢量分别为

其中，第i 行元素对应任务Ti的服务组合序列，xhij的取值范围为［1，sj］，表示子任务Tij在其对应的可用服务集Sj中的第xhij个服务上执行.vhij是［-sj，sj］上的任意整数值.

2.2 解码

子任务集T*j中任意一个子任务Tij在相应可用服务集Sj的所有服务上的执行时间、成本是已知的，可分别表示为向量（tij1，tij2，…，tijsj）、（cij1，cij2，…，cijsj）;对于一个具体的服务来说，服务集Sj中的任意一个服务和服务集Sj+1中的任意一个服务间的运输时间、成本指标可预知分别表示对于任务Ti来说可用服务集Sj中的第kj个服务与Sj+1中的第kj+1个服务间的运输时间、成本，其中j=1，2，…，n-1.

解析第h 个粒子：按行处理第h 个粒子，根据元素值计算行对应任务的时间和成本指标.如读取xhij和xhi（j+1），确定相应子任务的执行时间和成本：tij=tijxhij，cij=cijxhij；确定子任务间的运输时间和成本，分别为

解析完粒子h 的所有元素后，根据式（1）-（4）可计算出目标函数值.

2.3 种群初始化

为了获得尽量接近优化解的初始种群，对于所有粒子的位置，随机采用最短执行时间优先或最低加工成本优先规则进行初始化.以第h 个粒子为例，初始化按列进行，依次对第1 至第n 列进行操作，最短执行时间优先初始化规则的伪代码如下：

最低加工成本优先初始化规则与最短执行时间优先初始化规则相似，唯一的区别在于选取服务的标准是按照子任务在服务上的加工成本.根据两个子目标的重要程度调整采用上述两个规则进行初始化的粒子的比例，可以获得性能均衡的种群.而粒子速度初始化相对简单，即vhij在［-sj，sj］间随机取值.

2.4 种群更新方法

标准粒子群算法的位置、速度更新公式［13-14］适用于求解连续空间问题，文中求解的是使用整数编码的离散问题，因此引入遗传算法的交叉和变异操作［15-16］，得到改进的离散粒子群遗传混合算法.速度和位置的更新公式如下:

式中：rond（）表示取整；rand（）为0～1 之间的随机数；┐表示变异操作，文中随机采用部分“取反”或“倒置”的变异方法，即将原粒子位置矢量的一段元素值用sj-xhij替换xhij或者将一段元素值逆序；⊗表示交叉操作；Pkh、Gkh分别为粒子的局部最优位置和全局最优位置.更新操作是以上更新方式的逐级叠加，即使用当前公式更新粒子位置后，计算目标函数值，若优于该粒子的局部最优位置，则更新局部最优位置后等待下一轮迭代，否则采用下一级公式进行更新.

2.5 粒子位置矩阵元素值校正

每次更新后，粒子位置矩阵同列元素值可能出现重复现象，这意味着相同阶段多个子任务选取了同一服务，因此需要对粒子元素取值进行校正.校正过程以列为单位进行，对于每一列进行如下操作：①扫描该列所有元素取值，将相应服务集Sj中未分配的服务加入集合Uj；②将同列中取值相同的元素行号作为一个集合，集合中行号按照对应子任务在所分配服务上的加工性能（随机使用时间或成本指标）从优到劣排列，那么有可能存在多组元素行号的集合，记为SA1，SA2，…，SAl；③将集合SA1，SA2，…，SAl随机排列，按排列顺序依次处理；④对任意SAa，保留其中第1 个行号对应粒子位置元素的服务分配，而后为该集合中其他行号对应的粒子随机分配Uj中的服务，并将已分配的服务从Uj中删除.重复第④步，直到粒子所有列校正完成为止.

2.6 算法流程

云制造系统面向多任务调度的离散粒子群遗传混合算法的伪代码如下:

3 算例仿真

以包含4 个子任务的某产品制造过程为例，设有5 个任务同时请求服务，每个子任务对应的可用云制造服务集中包含多个性能不同的服务.为验证文中算法的有效性和执行效率，设计了3 个实验.

实验中用到的各种参数按标准粒子群算法、遗传算法参数的常用取值范围取值或随机取值；权重系数表明不同子目标在总体性能中所占的权重，本实验设定两个子目标的重要程度相等；输入数据即子任务对应的可用服务集及在每个服务上的执行时间和成本等信息是已知的，本实验采用随机生成的一组加工时间、运输时间（取值范围分别为1～100h，1～120h）和加工成本、运输成本（取值范围为50～1000 元）数据.

仿真实验参数设置为：N=5，n=4，s1=6，s2=7，s3=7，s4=6，w1=w2=0.5；粒子群算法中w=0.7298，c1=c2=2；遗传算法中pm=0.03，pc=0.8.

仿真实验环境：Intel 酷睿i3 380UM 处理器，1.33 GHz 主频，2 GB 内存，Windows7 系统，Matlab7.0.

3.1 算法的有效性验证

为验证文中算法的有效性，采用文中算法与标准粒子群算法、遗传算法各进行50 次实验，迭代次数为500，种群规模为200，3 种算法的50 次实验均使用同一组输入数据.以求得最优目标值的大小及最优结果的迭代次数为指标，3 种算法的实验结果如图2所示.

图2 3 种算法的最优目标值及迭代次数比较Fig.2 Comparison of optimum target values and iterations among three algorithms

可以看出，求解云制造系统多任务调度问题时，遗传算法容易早熟收敛，标准粒子群算法易陷入局部极值，而文中算法求得实际最优目标值的次数占实验总次数的百分比（96%）远远高于标准粒子群算法和遗传算法.

3.2 算法执行效率验证

影响算法有效性和执行效率的因素主要有种群规模和迭代次数，由于文中算法比标准粒子群算法和基本遗传算法更复杂，种群规模和迭代次数的增长对算法效率的影响从理论上来推断会更为显著.为了验证算法的执行效率，文中分别考察种群规模和迭代次数的增长对算法执行时间的影响.

（1）迭代次数固定为500，种群规模分别取100、200、300、400、500、600 时，离散粒子群遗传混合算法的执行时间呈线性增长，如图3（a）所示.

（2）种群规模固定为200，迭代次数分别取100、200、300、400、500、600 时，离散粒子群遗传混合算法的执行时间的增长较为缓慢，如图3（b）所示.

图3 种群规模和迭代次数对文中算法执行时间的影响Fig.3 Effects of population size and iterations on execution time of the proposed algorithm

以上两组结果表明，迭代次数和种群规模的增长对算法执行时间的影响在合理范围内，算法执行时间可以满足文中求解问题的需求.

3.3 种群初始化环节对算法性能的影响

分别采用文中初始化方法得到的种群与随机初始化方法得到的种群作为初始种群，使用文中提出的更新算法各进行20 次实验，结果如图4所示，可见“好”的初始种群对算法的有效性有着重要的影响.

4 结论

图4 初始种群对文中算法性能的影响Fig.4 Effect of initial population on the performance of the proposed algorithm

文中研究了云制造系统面向多任务的服务组合问题，同时考虑多任务和子任务间的运输环节，建立了以任务完成时间和成本最小为目标的多目标优化调度数学模型；提出了粒子群遗传混合算法并用于求解系统多任务调度问题，为保持种群多样性、避免早熟收敛，按条件采用标准粒子群位置、速度更新公式、交叉、变异更新方法对种群进行“逐级叠加”式地更新.算例仿真结果验证了该算法的有效性和优越性.今后将进一步研究服务争用条件下的多任务调度优化问题，除任务加工和运输所用时间/成本外，还将考虑等待时间/成本对生产效率的影响.

［1］Karnouskos S，Baecker O，de Souza L M S，et al.Integration of SOA-ready networked embedded devices in enterprise systems via a cross-layered web service infrastructure ［C］//Proceedings of the 12th IEEE Conference on Emerging Technologies and Factory Automation.Patras：IEEE，2007：25-28.

［2］Fox A.Cloud computing：what’s in it for me as a scientist？［J］.Science，2011，331（6016）：406-407.

［3］Jayavardhana Gubbi，Rajkumar Buyyab，Slaven Mrusic，et al.Internet of things （IoT）：a vision，architectural elements，and future directions ［J］.Future Generation Computer Systems，2013，29：1645-1660.

［4］Dillon T，Zhuge H，Wu C.Web-of-things framework for cyber-physical systems ［J］.Concurrency Computation：Practice and Experience，2011，23（7）：905-923.

［5］李伯虎，张霖，王时龙，等.云制造：面向服务的网络化制造新模式［J］.计算机集成制造系统，2010，16（1）：1-7.Li Bo-hu，Zhang Lin，Wang Shi-long，et al.Cloud manufacturing：a new service-oriented networked manufacturing model［J］.Computer Integrated Manufacturing Systems，2010，16（1）：1-7.

［6］陶飞，张霖，郭华，等.云制造特征及云服务组合关键问题研究［J］.计算机集成制造系统，2011，17（3）：477-486.Tao Fei，Zhang Lin，Guo Hua，et al.Typical characteristics of cloud manufacturing and several key issues of cloud service composition［J］.Computer Integrated Manufacturing Systems，2011，17（3）：477-486.

［7］刘卫宁，刘波，孙棣华.面向多任务的制造云服务组合研究［J］.计算机集成制造系统，2013，19（1）：200-209.Liu Wei-ning，Liu Bo，Sun Di-hua.Study on multitask oriented service composition in cloud manufacturing ［J］.Computer Integrated Manufacturing Systems，2013，19（1）：200-209.

［8］王时龙，宋文艳，康玲，等.云制造环境下制造资源优化配置研究［J］.计算机集成制造系统，2012，18（7）：1396-1405.Wang Shi-long，Song Wen-yan，Kang Ling，et al.Research of manufacturing resource allocation based on cloud manufacturing ［J］.Computer Integrated Manufacturing Systems，2012，18（7）：1396-1405.

［9］Tao F，Zhao D，Hu Y，et al.Resource service composition and its optimal-selection based on particle swarm optimization in manufacturing grid system ［J］.IEEE Transactions on Industrial Informatics，2008，4（4）：315-327.

［10］马雪芬，戴旭东，孙树栋.面向网络化制造的制造资源优化配置研究［J］.计算机集成制造系统，2004，10（5）：523-527.Ma Xue-fen，Dai Xu-dong，Sun Shu-dong.Optimization deployment of networked manufacturing resources ［J］.Computer Integrated Manufacturing Systems，2004，10（5）：523-527.

［11］韦韫，李东波，童一飞.面向服务的网络化协同制造资源多目标重组优化调度［J］.农业机械学报，2012，43（3）：193-199.Wei Yun，Li Dong-bo，Tong Yi-fei.Multi-objective reconfiguration and optimal scheduling of service-oriented networked collaborative manufacturing resource ［J］.Transactions of the Chinese Society for Agricultural Machinery，2012，43（3）：193-199.

［12］Minella G，Ruiz R，Ciavotta M.A review and evaluation of multi-objective algorithms for the flowshop scheduling problem［J］.Informs Journal on Computing，2008，20（3）：451-471.

［13］Eberhart R C，Kennedy J.A new optimizer using particle swarmtheory ［C］//Proceedings of the 6th International Symposium on Micromachine and Human Science.Nagoya：IEEE，1995：39-43.

［14］Kennedy J，Eberhart R C.Particle swarm optimization［C］//Proceedings of the IEEE International Conference on Neural Networks.Perth：IEEE，1995：1942-1948.

［15］Holland J H.Adaptation in natural and artificial system［M］.Ann Arbor：University of Michigan Press，1975.

［16］Goldberg D E.Genetic algorithms in search，optimization＆machine learning ［M］.Upper Saddle River：Addison-Wesley Professional，1989.