武善玉 李云鹤

引言

制造业对于社会、经济、环境都有着重大的影响。随着技术的更新，具有高计算能力、通信能力和控制能力的智能化制造设备将成为制造系统新的设备资源。信息物理系统（Cyber-Physical Systems——CPS）[1～5]正是为了解决新型智能物理设备互联问题而提出的，它实现计算资源和物理资源的紧密结合与协同[6]。何积丰院士认为“下一代工业是建立在CPS之上，将来CPS技术的发展和普及，将使得用计算机和网络实现功能扩展的物理设备无处不在” [7]。M-CPS汇聚不同工厂、地域的制造资源，使用多任务加工与运输协同调度思想解决多任务请求下的全局资源统筹分配问题[8]，理论上可以获得全局最优的资源配置方案。本文研究在相近地域范围内，可忽略运输时间的多任务调度问题，但可用服务数量可能少于任务数量，即资源受限条件下面向多任务的资源配置优化问题（Resource-constrainded Multi-task Scheduling Problem， RCMTSP）。

一、RCMTSP问题描述

1.1问题及假设条件

N个同类型任务 同时请求服务，将该类任务分解后，任务Ti由n个子任务组成，其中括号{}表示串行结构模式，[]表示并行结构模式。

集合T中每个任务的第j个子任务属于同类型子任务，组成一个集合。系统根据服务提供者的地理位置信息，为集合T* j选出同一地域范围内可用的服务组成可用服务集，其中Sj，k是可用服务集中的第k个服务，mj是可用服务集中服务的个数。T* j中的每个子任务将在SVRj中选取合适的服务完成加工操作。任意两个服务间的运输环节可忽略。

问题的相关假设如下：

1）所有任务类型相同，具有相同的加工过程;

2） 可用服务是相近地域内的提供者提供的;

3） 同一个任务的邻接子任务间是严格有序的;

4） 一个服务同一时刻只能为一个子任务提供服务;

5） 子任务开始处理后，直到处理结束才释放占用的服务;

6） 为每个子任务集合T * j构建的可用服务集SVRj中的服务数量可能少于子任务数量。

1.2优化目标

优化目标包括：

F1： 所有任务的最大完成时间;F2： 所有任务的平均完成时间;F3： 各关键服务的总负载;F4： 所有服务集的平均负载之和。

任务Ti的完成时间ti由其所有子任务的加工时间和子任务等待处理时的等待时间构成。对任意满足强时序约束的子任务Ti（j-1）和Tij，其完成时间可根据公式（2）计算，而对于任意一个并行子任务集，完成时间为其中所有子任务完成时间的最大值，即：。

二、 MOHSA-DPSO算法框架

RCMTSP问题与柔性车间作业调度问题 （FJSP） [9～13]具有某些相似之处，即二者都包含两个子问题——路径子问题和排序子问题，不同之处在于：FJSP问题解决的是一组工件和对应的一组机器间的资源分配问题，而RCMTSP包含多组（多阶段）子任务，且每组子任务对应一组数量较多的可用服务。

针对问题离散、大规模等特征，提出多目标混合模拟退火-离散粒子群（MOHSA-DPSO）算法，将模拟退火算法与离散粒子群算法混合，并对粒子编码、解码、种群初始化、种群更新、邻域搜索、非劣解集维护等环节进行了详细设计。

2.1粒子编码

RCMTSP问题的一个解决方案需要表达出两个方面的信息：①服务分配;②同一服务上的子任务排序。分别采用服务分配矩阵Xh和子任务序列矩阵Oh表示上述两种信息。服务分配矩阵Xh是n行N列的矩阵，行号表示子任务阶段，列号表示任務序号，矩阵元素xhji∈[1，mj]表示子任务Tij分配到的服务编号。其中h表示种群中第h个粒子。子任务序列矩阵Oh同样为n行N列，ohji∈[1，N]表示子任务排序，即在同阶段子任务中的优先顺序，对于分配到同一个服务上的两个子任务来说，在该服务上的处理顺序按照优先级由高到低进行。

2.2解码

对于多目标问题的解码方法，本文算法按行解析粒子Ph的子任务序列矩阵Oh和服务分配矩阵Xh，按照同一行中子任务的优先级顺序依次选取元素ohji，其值记为b=ohji，及其在Xh中对应的服务编号xhjb;重复确定子任务Tbj的开始时间t s bj和完成时间t  e bj  ，以及服务Sj，k的负载时间tw j，k（任意一个服务的负载初始值为0）。对粒子h解析完毕后，计算出粒子对应的各目标值。

2.3算法基本步骤

MOHSA-DPSO算法基本步骤如下：

第1步，种群初始化：产生初始的粒子;

第2步，设初始种群为当前种群;

第3步，计算各粒子对应的目标函数向量，对每个粒子进行评价，根据评价结果决定是否更新粒子的个体最优位置;选取非劣解更新全局非劣解集档案;

第4步，为每个粒子选取全局最优位置;

第5步，判断终止条件，若满足则算法终止;否则更新粒子的位置，并返回到第3步。

三、多目标混合粒子群优化算法MOHSA-DPSO

3.1种群初始化

初始种群对算法性能有着极大的影响。同时考虑接近最优解和粒子多样性两个问题，本文算法采用以下几种规则产生初始种群。

（1）采用三类经验法则产生初始粒子。最短子任务加工时间法则;最长子任务加工时间法则;最短交货期优先法则。

（2）采用完全随机方法：每个阶段子任务随机排序，并将此排序作为优先级排序，将子任务按优先顺序分配到当前加工时间最短的服务上。

（3）先到先服务方法：将第一阶段子任务进行排序和服务分配，第二阶段按照第一段子任务完成时间从小到大排列，并将此排序作为优先级排序，并分配到当前加工时间最短的服务上。其他阶段依此类推。

以上几种方法同时使用，分别承担种群中一部分粒子的生成，比如三大类方法分别用于40%、20%、40%粒子的生成，其中第一类方法中的三种法则分别用于产生20%、10%、10%的粒子;采用“先到先服务方法”的粒子中第一阶段子任务分配规则采用不同法则的比例分别为10%。

3.2种群更新策略

本文MOHSA-DPSO中，粒子的更新分成“交叉”和“变异”两类操作。其中“交叉”操作依赖粒子的历史最优位置和全局最优位置，粒子的速度依赖于粒子与两个最优位置的相似度，表示粒子向二者前进的可能性。变异操作则是为了避免早熟收敛而针对RCMTSP特定问题特点提出的对倾向停滞的粒子采用的干扰机制。

（1）更新子任务序列矩阵。

MOHSA-DPSO算法中，每个粒子的更新包含两个方面：更新子任务序列和更新服务分配。子任务序列的更新：对于第α代种群中的粒子Pα h的子任务序列矩阵Oα h的更新是按行从上到下进行的。

（2）更新服务分配矩阵。

对于粒子的服务分配矩阵的更新按行从上到下进行的，并且同样依赖于相似度概念，但对于历史最优位置和全局最优位置的继承将分别取决于粒子与两者各自的相似度。

（3）变异操作。

为了避免早熟收敛，本文算法使用干扰机制对倾向停滞的粒子进行变异操作。停滞状态的识别基于粒子局部最优位置没有被刷新的连续最大代数gmax，变异概率设为（gh/gmax），其中gh表示到目前为止粒子局部最优位置没有刷新的进化代数。

（4）邻域搜索。

本文算法采用模拟退火算法对新种群进行邻域搜索。模拟退火算法是一种模拟固体物质退火过程的启发式随机搜索算法，广泛应用于求解组合优化问题。算法从一较高温度开始，随着逐渐冷却，在解空间中随机寻找全局最优解，并以按某种规律变化的概率接受较差的新状态而避免算法陷入局部最优。

本文使用模拟退火算法对当前解作邻域搜索，即对当前解做小的局部调整产生一个新的解，为了使算法能够跳出局部最优，以随温度Tc变化的概率接受较差的新解。算法基本思想为：对于粒子，产生其邻域内的新解，判断二者之间的优劣关系，如果新解支配初始解则接受新解，否则以与当前温度Tc相关的概率exp（-Δ/Tc）接受新解。

3.3选取非劣解

本文提出的MOHSA-DPSO算法使用一个Pareto非劣解集档案保存搜索到的非劣解。每次粒子更新后，都要判断是否非劣解，根据判断结果对档案进行更新。更新的步骤如下：

（1）将新解与当前Pareto非劣解集档案中的解进行比较，判断新解是否非劣解;

（2）根据判断结果对档案进行更新：

①新解与档案中的某个解相同：放弃新解，更新结束;

②新解被档案中的一或多个解支配：放弃新解，更新结束;

③新解支配档案中的解：将新解加入档案，同时删除档案中被新解支配的所有解，更新结束;

④新解与档案中的任何解互不支配：将新解加入档案，更新结束。

3.4更新粒子个体最优位置

当前种群中任一个粒子更新后产生一个新的解，这个解与其个体最优位置Pbh之间的关系决定了Pbh的更新。根据支配概念的定义，粒子每次更新后如果支配Pbh，则用更新Pbh，否则Pbh不变。

3.5选择粒子全局最优位置

每次迭代后，需要从非劣解集档案中为当前粒子选择一个全局最优位置。OHSA-DPSO算法中，为当前粒子选择全局最优位置是依据粒子之间的拥挤度来进行的。拥挤度基于两个粒子之间的距离，用于衡量粒子的拥挤程度。粒子Ph与Ph之间的拥挤度与两个因素相关：粒子间的欧氏距离和汉明距离。其中粒子Ph与Ph间的欧氏距离，两者间的汉明距离为两个粒子位置矩阵对应元素不相同的個数，而拥挤度是上述两个距离规一化之后的平均值。计算当前粒子与非劣解集档案中任意粒子之间的拥挤度，选择拥挤度最大的粒子作为当前粒子的全局最优位置。

3.6混合算法流程

模拟退火算法与粒子群算法混合在一起，粒子群算法迭代次数由模拟退火算法的温度控制，而种群更新产生的粒子则由模拟退火算法作进一步优化。算法总体流程如下：

（1）参数初始化：初始化种群规模SwarmSize、初始温度T0、终止温度Tend、温度调整参数B及其他相关参数;

（2）产生初始种群：

1、根据3.1的方法产生初始种群Swarm（0）;

2、对每个粒子进行解码并计算各粒子对应的目标函数向量，用模拟退火算法对每个粒子进行邻域搜索;

3、对每个粒子进行评价，根据评价结果决定是否更新粒子的个体最优位置;

4、选取非劣解更新全局非劣解集档案;

5、为每个粒子选取全局最优位置;

（3）种群更新：在满足T0

1、根据粒子自身位置、个体最优位置、全局最优位置更新粒子;

2、在满足KL

3、对粒子进行评价，根据评价结果决定是否更新粒子的个体最优位置;

4、选取非劣解更新全局非劣解集档案;

5、为粒子选取全局最优位置;

（4）输出优化结果。

四、小结

本文研究了在同一地域范围内、可忽略运输时间、但可用服务数量可能少于任务数量的多任务调度问题，即资源受限条件下面向多任务的资源配置优化问题（RCMTSP），提出了面向RCMTSP问题的多目标混合模拟退火-离散粒子群算法 MOHSA-DPSO。

针对问题的离散特性，同时为了提高算法的搜索能力，本文将SA嵌入到离散PSO算法框架中;由于RCMTSP问题规模较大，不易求解，因此对种群初始化方法进行了深入研究，使用多种经验法则产生尽可能接近最优解的初始种群。 与经典的求解FJSP问题的类似群智能算法相比，在两个较为典型的不同规模的实例中，本文提出的算法具有较好的搜索能力。

参  考  文  献

[1] LEE E A. Cyber Physical Systems： design challenges[C]. Proceeding of the 11th IEEE international symposium on object oriented real-time distributed computing. Los Alamitos， CA： IEEE Computer Society， 2008：363-369

[2] KLESH A T， CUTLER J W， ATKINS E M. Cyber-physical challenges for space systems [A]. 2012 IEEE/ACM third international conference on cyber-physical systems [C]. Beijing， China： IEEE/ACM， 2012：45-54

[3] Tan Y， Goddard S， Prez L C. A prototype architecture for cyber-physical systems[J]. ACM SIGBED Review， 2008， 5（1）： Article No. 26

[4] 李建中， 高宏， 于博. 信息物理融合系统（CPS）研究进展[C]. 2009中国计算机科学技术发展报告， 北京： 机械工业出版社， 2010： 1-20

[5] Huang Ben-xiong. Cyber physical systems： A Survey[R]. Stavanger： Smart Home Workshop， 2008.

[6] NSF Directorate for computer & information science & engineering. NSF Directorate for engineering. Cyber-Physical Systems （CPS） [EB/OL]. available： http：//www.nsf.gov/pubs/2011/nsf11516/nsf11516.htm. 2011.

[7] 何積丰.Cyber-physical systems [J]. 中国计算机学会通讯， 2010， 6（1）： 25-29

[8] WU Shan-yu， ZHANG Ping， LI Fang， GU Feng， PAN Yi. A hybrid discrete particle swarm optimization-genetic algorithm for task scheduling problem in service oriented manufacturing systems[J]. Journal of Central South University， 2016，23（2）： 421-429

[9] PEZZELLA F，MORGANTI G，CIASCHETTI G. A genetic algorithm for the flexible job-shop scheduling problem[J]. Computers & Operations Research， 2008， 35 （10）：3202–3212

[10] Driss I， Mouss KN， Laggoun A. A new genetic algorithm for flexible job-shop scheduling problems[J]. Journal of Mechanical Science and Technology， 2015， 29（3）： 1273-1281

[11] Yuan Y， Xu H. An integrated search heuristic for large-scale flexible job shop scheduling problems[J]. Computers & Operations Research， 2013， 40（12）： 2864-2877

[12] Brandimarte P. Routing and scheduling in a flexible job shop by tabu search. Annals of Operations Research， 1993， 41（3）：157–183

[13] Gao K Z，  Suganthan P N，  Pan Q K， et al. Pareto-based grouping discrete harmony search algorithm for multi-objective flexible job shop scheduling[J]. Information Sciences， 289（24）： 76-90