面向云制造服务的制造资源多目标动态优化调度

邰丽君 胡如夫 赵 韩 陈曹维

1.宁波工程学院，宁波，315211 2.合肥工业大学，合肥，230009

0 引言

随着工业化水平的提高和信息技术的高速发展，制造业正从静态、组织内的供求关系向动态、跨组织方向发展。李伯虎等［1］依据网络化制造技术的需求和发展趋势，提出了云制造模式。云制造以云计算为基础，融合了现有的信息化制造技术、物联网技术、面向服务技术、智能科学技术，可随时为用户提供符合客户需求、安全可靠的制造全生命周期服务。

国内外学者对云制造进行了大量的研究［2－9］，但是这些研究只是局限在概念、模型、平台框架结构及相关关键技术，对云制造服务的具体实现过程却鲜有研究。云制造服务过程中，如何通过动态调度对已虚拟化的制造资源和制造能力进行统一的智能化经营和管理，是云制造服务能否实现的关键。目前，对资源调度的研究大量集中于车间内部的生产调度和制造系统服务组合优化，而这些研究方法无法应用于云制造的特殊环境。云制造环境下，由于制造服务周期长、涉及的加工企业众多，因此在执行过程中极易受到负载、故障、环境变化等不确定因素的干扰，这就要求资源调度过程适应动态的制造环境，具有动态再调度功能。同时由于各个制造服务来源于不同的企业，势必产生相应的运输成本。因此，云制造资源调度是一个综合考虑时间、成本、质量和能力的动态多目标调度过程。

本文根据云制造服务的特点，建立云制造环境下制造服务资源多目标动态调度模型，运用遗传蚁群优化算法来解决制造服务资源多目标调度问题。

1 问题分析

假定一个云制造服务平台上有多个制造服务申请，每个制造服务申请经过任务分解后，分为若干个制造服务子任务。每个制造服务子任务包含一道或多道工序（这些工序是预先确定的）。每道工序有多个候选制造资源，可随机在这些候选制造资源上进行制造服务。工序的完成时间是随着制造资源的性能不同而变化的。由于制造资源可能会处于不同的企业，因此不同工序节点处会产生一定的物流成本。制造任务在执行过程中常存在机器故障、交货期提前或延后等突发扰动问题。调度的目标是为每道工序选择最合适的制造资源，确定制造任务中每个制造资源上的最佳加工顺序及加工时间，使制造服务的服务周期和各项性能指标达到最优。为使研究更具可操作性，本文设定以下假设条件：①主要研究云制造企业间的协作调度，不考虑企业内部的调度流程；②同一个制造服务任务只能通过一个制造服务资源完成；③一个制造服务资源至少能完成一个制造服务任务；④不同制造资源之间的运输成本和运输时间、距离成正比，不考虑运输物料材料问题；⑤每个子任务的执行时间根据任务间的关系和执行顺序进行。

2 多目标优化模型

设云制造服务平台有多个制造服务任务，每个服务任务可分为N个子任务，子任务F I有M I个制造服务资源可以完成，I＝1，2，…，N。FIj为子任务F I的第j道工序。T为任务交货时间，L为制造服务能力，Q为制造服务质量，C为制造服务成本。

2.1 目标函数

2.1.1 总制造服务时间

总制造服务时间为用户从云平台客户端提交服务请求到获得资源服务所花费的时间，主要包括制造时间和物流时间。总制造服务时间的目标函数为

式中，x ij为决策变量；tij为制造任务i的第j道工序所需制造时间；t′ij为制造任务i的第j道工序的物流时间；αi为制造任务i的工件数量；δT1、δT2为权重系数；H i为任务i的工序总量；n为制造任务数量；W为阈值。

当工件运输到制造设备资源所需的时间超出阈值时，工件制造时间忽略不计。

2.1.2 制造服务能力

制造服务能力体现了制造服务提供企业完成制造任务的能力水平，包括工艺能力、故障率、废品率、尺寸精度、协作能力、客户信誉水平。根据平台提供的制造能力评判标准，对企业制造服务能力的各个指标进行评价，并构建目标函数：

2.1.3 制造服务质量

制造服务质量体现了用户对制造服务的满意程度，其目标函数为

式中，sij为用户对任务i的第j道工序加工的满意程度；μi为满意程度修正系数。

2.1.4 制造服务成本

制造服务成本除了资源设备、夹具、刀具等不同组合产生的生产成本外，还包括工件在不同制造资源之间运输的物流成本，因此，制造服务成本的目标函数可以表示为

式中，cij为任务i的第j道工序的工件所需制造成本；c′ij为任务i的第j道工序的工件运输到制造设备所需的运输成本；δc1、δc2为权重系数。

2.2 约束条件

（1）制造服务任务交货期约束。制造服务任务交货期约束为每个制造服务任务的实际交货期不能超过最迟交货期，即

式中，Timax为制造服务任务i的允许最迟交货时间。

（2）制造服务任务成本约束。制造服务任务成本约束为每个制造服务任务的总服务成本不能超过最高服务成本，即

式中，Cimax为制造服务任务i所能支付的最高服务成本。

（3）制造服务任务区域约束。制造服务任务区域约束为每个制造服务资源的区域距离不能超过所要求的最大距离，即

式中，Yi为制造服务任务i的服务资源的区域距离；Yimax为制造服务任务i所要求的服务资源区域的最大距离。

（4）制造服务任务时序约束。制造服务任务时序约束为有时序约束关系的前一任务的结束时间不能超过下一任务的开始时间，即

式中，de，i为任务i的结束时间；db，i＋1为任务i＋1的开始时间。

（5）制造服务任务服务能力约束。制造服务任务服务能力约束为制造资源的服务能力水平必须满足制造任务的能力需求，即

式中，L′ij、δij分别为制造服务任务i的第j道工序的制造服务能力及其权重；L′i为制造服务任务i需要实现的制造能力。

（6）制造服务任务资源约束。制造服务任务资源约束为同一时间同一服务资源只能完成一个服务任务，即

（7）制造服务任务可信任性约束。制造服务任务可信任性约束为每个制造服务资源的信誉度不能小于所要求的最小信誉度，即

式中，U i为制造服务任务i服务资源的信誉度；U imin为制造服务任务i所要求的服务资源最小信誉度。

2.3 基于Pareto最优集的多目标调度

对于多目标问题，最优解不是一个确定的解而是一个最优解的集合，称这种解为Pareto最优解，该解的集合通常被称为 Pareto最优集［10－11］。Pareto有效解的定义如下［10］：如果对一个可行解向量x＝ （x1，x2，…，x v）∈S（S为可行解空间，v为解向量的维数），当且仅当不存在x∈S，使得目标函数F（X）＝ （f1（X），f2（X），…，f v（X））优于F（x）＝ （f1（x），f2（x），…，f v（x）），那么称x为多目标问题的Pareto非劣解，称集合P＊＝｛x｜x∈S｝为多目标问题的Pareto最优解集。

这里根据制造资源调度的总制造服务时间、制造服务能力、制造服务质量和制造服务成本的目标函数组成最终的多目标优化目标函数F（X）＝（f1（X），f2（X），f3（X），f4（X））。

3 多目标优化动态调度算法

3.1 动态调度策略

云制造环境下，由于涉及的服务企业众多、制造服务执行周期较长、制造现场复杂多变，因此在实际制造服务过程中势必会产生大量的扰动事件。单纯的静态调度无法处理各种实时变化，无法实现自适应调度过程。本文提出动态调度技术，在发生扰动事件时能及时作出反应，通过调整调度方案来保证云制造生产任务按时完成。

3.1.1 调度生命周期的划分

将整个生产调度过程按照整个制造生命周期T划分为若干个时域周期，以滚动的时域周期优化取代一成不变的全局优化。在实际生产中，存在周期性调度和突发事件驱动的适时调度两种情况。因此，设计了周期性调度和适时调度两种调度模式。周期性调度模式按照划分的时域周期，在每个周期内进行调度，适用于生产调度具有规律性的情况，使生产具有一定的稳定性，是实际生产中遇到最多的情况。适时调度模式是由故障、交货期变化等突发事件驱动的调度模式，发生突发事件时可及时进行再调度，以适应变化了的环境。

生命周期T的划分：

式中，g为时域周期数，g∈N。

在时域周期tk内，根据采样情况，采用周期性调度模式，获取该周期内的最优性能，若存在突发事件，则启动适时调度模式，再实行一次调度，获得新的调度结果；若没有突发事件，继续执行本周期内的调度结果。

3.1.2 事件影响关联树分析技术

对工序、设备、时间段等事件的调整必然会导致与该工序及设备相关联工序的调整，因此需分析调整的关联影响范围。

根据工件调度工序间的先后时序关系，建立工件调度工序关联树。关联树的根节点（如Pi，j）为发生动态扰动的工序，一阶子节点（如Pi，j＋1）为该工序的后驱工序，二阶子节点（如Pi，j＋2）为后驱工序的下一个后驱工序。逐点建立后续的多阶受影响节点，直至调度方案中不存在后续工序为止。关联树组织结构如图1所示。

3.1.3 效能偏差比较

图1 事件影响关联树组织结构

实际调度过程中存在大量的突发事件。对每一个突发事件都进行动态再调度，不但会造成调度方案的频繁改动，而且会导致整个系统、人员的负担大幅增加，反而降低生产效率。因此，本文提出一种效能偏差比较技术，对每一个扰动事件，先比较再调度过程与原调度方案的效能偏差值，若偏差值大于设定的指标阈值，则进行动态再调度；否则不启动再调度过程，而是通过车间内部调整（如提高设备利用率、加班等方法）消除部分扰动事件，从而降低关联调整的复杂度。

3.1.4 动态调度流程图

设计动态调度流程如下：首先初始化工件、工艺、设备等信息，然后根据制造服务任务划分制造过程的生命周期和时域周期。当时域周期到来时执行周期性调度。在执行周期性调度过程中若发生突发扰动事件，则进入适时调度模式，根据获得的突发事件的工序节点建立工序影响关联树。若关联树存在子节点，则根据关联影响程度判断是否需要调整零件工序，若需要调整，则根据需求调整生成新的调度方案，并将其与原调度方案进行效能偏差的比较。若偏差值小于阈值，则放弃新的调度方案，继续执行周期性调度；反之，则执行新的再调度过程。在执行周期性调度过程中若没有发生突发扰动事件，则继续执行原调度方案，在再调度周期来临时进行周期性再调度，如图2所示。

3.2 遗传－蚁群调度算法

3.2.1 算法描述

将制造资源调度方案转化为类似旅行商问题（travelling salesman problem，TSP）中的一条路径，蚂蚁可任意选择节点，所选的节点路径即为调度方案。蚂蚁选择路径后，信息素留在节点上，而不是路上。

3.2.2 初始信息素浓度生成

在蚂蚁的路径节点集合中，节点i和j间的信息素浓度可表示为τij。初始信息素浓度τij（0）由遗传算法求得，方法如下：

图2 动态调度流程图

（1）编码。本文设计了一种3层矩阵编码方法，第1层编码表示工件，第2层编码表示工序，第3层编码表示设备制造资源。如表1所示，第1个染色体表示工件3的第1道工序由设备制造资源4加工。依次类推，任意基因串的排列与调度方案一一对应。

表1 染色体编码

（2）交叉变异。交叉、变异操作是遗传算法中增加种群多样性、防止算法早熟和停滞的操作。本文针对的多目标优化问题需既考虑种群的多样性又考虑其收敛性，因此采用全交叉方式，交叉概率为1。由于本文采用了3层编码，所以需要对3部分分别进行交叉操作，包括工件交叉、工序交叉和设备交叉，如图3所示。

（3）求解步骤。① 初始化参数，子群个数为A，每个子群产生p个个体，最大进化代数为O；②产生交叉概率Pc、变异概率Pm；③将目标函数作为适应度函数f（x），计算子群每个个体的适应度函数值f（x ij）（i＝1，2，…，n；j＝1，2，…，H i）；④采用轮盘赌选择法进行选择操作；⑤进行交叉变异操作，按照交叉概率Pc从第i个子群中随机对个体进行交叉操作，按照变异概率Pm选择个体进行变异操作；⑥根据适应度值排序选择最优染色体，若满足收敛条件，结束返回最优解，否则退回步骤④；⑦对选出的染色体解码，转化为初始信息化浓度。

图3 交叉示意图

3.2.3 启发式信息

启发式信息与路径长度无关。在云制造环境下，由于涉及的各个机器和工序处于不同的地点，这必然带来额外的物流成本。所以在资源调度中，除了调度时间，成本也是重要的影响因素之一。因此本文将启发式信息定义为

式中，Tij为任务执行时间；Cij为任务执行中产生的成本；α1、β1分别为Tij和Cij的权重系数。

3.2.4 状态转移规则

第K只蚂蚁从节点i转移到节点j的概率计算公式为

式中，α2、β2分别为信息素和启发式信息的权重；ηij为节点i到j的启发式信息；wi为第i个工序可选的资源节点的集合。

3.2.5 信息素更新规则

（1）更新策略。信息素是蚂蚁进行路径选择的唯一因素，随着信息素的累积，蚂蚁很容易倾向于信息素量大的节点，忽略实际路径更优、信息素量不大的节点，而陷入局部最优。遗传算法的交叉算子和变异算子可以产生多样性的子代，从而扩大解的搜索空间，因此将其引入蚁群算法的信息素更新策略中，以避免解陷入局部最优。

（2）交叉。首先引入交叉算子对路径节点进行交叉操作，对任意路径随机产生2个交叉节点，交换2个节点的内容，产生新的路径即新的调度方案。若新方案更优则替代原方案，否则不替换。

（3）变异。若某条路径更优而信息素量不够，则将原最优路径上的信息素转移到更优路径上，对新路径上的信息素进行变异操作，保留新的最优路径，调整公式如下：

式中，τi，j为原最优路径 上 的 信 息 素；τ′i，j为 交叉 后 更 优 路径上的信息素；τ′i，j＋1为变异后的新最优路径的信息素。

蚂蚁完成一次循环后，信息素更新公式如下：

4 算法实现

算法实现步骤如下：

（1）初始化α1、β1、ρ、Pc、Pm等参数，置初始迭代次数为0。

（2）由遗传算法产生初始信息素浓度τij（0）。

（3）将所有蚂蚁置于出发点上，初始点位于当前解集中。

（4）按照状态转移规则（式（8））计算每一只蚂蚁的概率选择目标。

（5）按照式（1）计算每个调度路径的目标函数最优值，若新路径更优，按照式（2）变异信息素。

（6）对各路径进行交叉操作，若产生更优解则替换新的交叉点信息，否则转步骤（7）。

（7）按照式（3）更新信息素。

（8）如果迭代次数小于最大迭代次数，则转步骤（2），否则输出目前最优解。

5 实例应用

以汽车零部件云制造平台中某汽车零部件企业为例验证算法的有效性。该企业现有5个生产子任务需要制造服务，其相关信息见表2，在平台中初步搜索到的与这些子任务对应的工序及制造资源集合见表3。

表2 云制造制造服务子任务信息

表3 候选制造资源在资源调度中的部分数据

根据本文提出的调度模型及算法，采用MATLAB编程进行运算，初始化参数如下：遗传算法种群规模最大迭代次数为50，初始交叉概率Pc＝1，初始变异概率Pm＝0.05，蚂蚁个数为20，最大迭代次数为50，α1＝1，β1＝7，ρ＝0.1。生产过程考虑以下扰动因素：资源M1在时刻60h发生故障，在时刻90h得到修复，采用本文提出多目标动态遗传蚁群算法对子任务O3进行优化调度计算，得到静态调度甘特图和动态调度甘特图（图4、图5）。

图4 静态调度甘特图

由图4、图5可以看出，在不考虑机械故障扰动的情况下，静态调度的加工周期为221h；在考虑动态扰动的情况下，加工周期为251h。而动态调度的加工周期为227h，可见动态调度在扰动出现时能大幅缩短加工周期。

为验证算法的性能，将本文所提出的算法（遗传蚁群算法）与改进蚁群算法［12］进行对比分析，结果如表4及图6所示。比较得出，遗传蚁群算法由于充分利用了遗传算法在全局搜索、快速收敛等方面的优势，因此在全局搜索能力及收敛速度上均比改进蚁群算法有明显的提高。

图5 动态调度甘特图

表4 运算结果对比

图6 目标函数变化曲线

从图6可以看出，随着迭代次数的增加，算法趋于稳定，由于基本蚁群算法在进化过程的最优解可能会丢失、造成局部收敛，所以出现最优解跳跃及收敛速度慢的情况；而改进的遗传蚁群算法由于采用了交叉和变异的方法，既继承了最优解，又增大了搜索空间避免进入局部最优，加快了收敛速度。

6 结论

（1）针对云制造环境下制造资源调度的特点，综合考虑影响制造资源调度的主要影响因素（最小化总制造服务时间、最优化制造服务能力、最优化制造服务质量、最小化制造服务成本），建立了一个制造服务多目标调度模型。

（2）根据云制造环境下极易发生突发扰动事件的特点，提出了一种动态调度技术。该技术将整个制造服务全生命周期中的调度分为周期性调度和适时调度两种模式。当发生扰动时，首先根据扰动事件建立事件影响关联树，在此关联树的基础上分析再调度的效能偏差，根据与阈值的比较结果决定下一步调度过程，通过调整调度方案，来保证云制造生产任务按时完成。

（3）提出了基于遗传蚁群算法的制造资源调度算法。该算法利用遗传算法的优势对蚁群算法进行改进，弥补了蚁群算法存在的不足，使整个调度过程能快速地收敛于最优解。

（4）以某汽车零部件企业为例进行仿真实验，仿真结果证明了该算法的有效性和可行性。

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

Li Bohu，Zhang Lin，Wang Shilong，et al.Cloud Manufacturing：a New Service－oriented Manufacturing Model［J］.Computer Integrated Manufacturing Systems，2010，16（1）：1－7.

［2］王正成，黄洋.面向服务链构建的云制造资源集成共享技术研究［J］.中国机械工程，2012，23（11）：1323－1331.

Wang Zhengcheng，Huang Yang.Research on Integration Sharing Technology of Cloud Manufacturing Resource Oriented to Service Chain Construction［J］.China Mechanical Engineering，2012，23（11）：1323－1331.

［3］陶飞，张霖，郭华，等.云制造特征及云服务组合关键问题研究［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.

［4］程功勋，刘丽兰，林智奇，等.面向用户偏好的智能云服务平台研究［J］.中国机械工程，2012，23（11）：1315－1322.

Cheng Gongxun，Liu Lilan，Lin Zhiqi，et al.Intelligent Cloud Service Platform for Customer Preference［J］.China Mechanical Engineering，2012，23（11）：1315－1322.

［5］Zhang Qian，Qi Deyu.Service－oriented Collaborative Design Platform for Cloud Manufacturing［J］.Journal of South China University of Technology：Natural Science，2011，39（12）：75－81.

［6］尹超，黄必清，刘飞，等.中小企业云制造服务平台共性关键技术体系［J］.计算机集成制造系统，2011，17（3）：495－503.

Yin Chao，Huang Biqing，Liu Fei，et al.Common Key Technology System of Cloud Manufacturing Service Platform for Small and Medium Enterprises［J］.Computer Integrated Manufacturing Systems，2011，17（3）：495－503.

［7］张霖，罗永亮，陶飞，等.制造云构建关键技术研究［J］.计 算 机 集 成 制 造 系 统，2010，16（11）：2510－2520.

Zhang Lin，Luo Yongliang，Tao Fei，et al.Study on the Key Technologies for Construction of Manufacturing Cloud［J］.Computer Integrated Manufacturing Systems，2010，16（11）：2510－2520.

［8］贺东京，宋晓，王琪，等.基于云服务的复杂产品协同设计方法［J］.计算机集成制造系统，2011，17（3）：533－539.

He Dongjing，Song Xiao，Wang Qi，et al.Method for Complex Product Collaborative Design Based on Cloud Service［J］.Computer Integrated Manufacturing Systems，2011，17（3）：533－539.

［9］尹胜，尹超，刘飞，等.云制造环境下外协加工资源集成服务模式及语义描述［J］.计算机集成制造系统，2011，17（3）：525－532.

Yin Sheng，Yin Chao，Liu Fei，et al.Outsourcing Resources Integration Service Mode and Semantic Description in Cloud Manufacturing Environment［J］.Computer Integrated Manufacturing Systems，2011，17（3）：525－532.

［10］Khalid K，Henri P，Nasser M.Using Multi－agent Architecture in FMS for Dynamic Scheduling［J］.Journal of Intelligent Manufacturing，1997，8（1）：41－47.

［11］Zitzler E.Evolution Algorithms for Multi－objective Optimization［D］.Zurich：Swiss Federal Institute of Technology，1999.

［12］胡凯林，李平.基于改进蚁群算法的炼铁原料混匀过程调度优化［J］.上海交通大学学报（自然科学版），2011，45（8）：1105－1112.

Hu Kailin，Li Ping.The Optimized Scheduling for Iron－making Bulk Ore Blending Process Based on Improved Ant Colony Optimization［J］.Journal of Shanghai Jiao Tong University（Science），2011，45（8）：1105－1112.