基于可持续性的云制造多任务调度

何 巍 贾国柱 孔继利 宗恒山

1.北京航空航天大学经济管理学院，北京，100191 2.北京邮电大学自动化学院，北京，100876 3.中国航天系统科学与工程研究院，北京，100048

0 引言

目前，全球制造业正经历新一轮的转型升级，现代企业的服务意识和环境意识逐步提高，制造业的服务化和可持续性引起了广泛关注［1⁃3］。在制造业服务化方面，一种面向服务的网络化制造新模式——云制造正在快速发展，用户可以通过云制造平台获取按需使用的、安全可靠的、优质廉价的制造服务［2⁃3］；在制造业可持续性方面，绿色制造、可持续发展相继被提出。在物联网、云计算等新兴技术的推动下，云制造快速发展作为一种先进的智能制造模式，在满足客户需求的同时，如何实现可持续发展成为一个越来越重要的问题。

影响制造系统可持续性的因素有很多，其中环境、经济和社会因素是三大因素。在已有的可持续性相关研究中，既有学者单独考虑其中某一种因素，也有学者将两种因素组合起来考虑（如环境-经济，环境-社会，经济-社会）［1］。制造系统的可持续性可分为战略、战术和运作三个层面，其中战略层面是目前学者们的关注重点，主要包括供应链设计、布局设计、清洁产品和生产方式设计、回收处理等内容［1⁃4］。然而，提升制造系统的可持续性必须考虑所有相关层面的问题，从而将战略层的全局策略转化为运作层的具体活动。在实际的生产过程中，在运作层中调度是影响生产效率、质量和成本的关键因素之一，不同的调度方案也会对资源消耗和排放产生不同影响。因此，在调度优化过程中考虑可持续性因素对从全局上提升可持续性起到了越来越重要的作用。

云制造环境下的调度问题可以分为单任务调度和多任务调度。其中，多任务调度指的是为了完成一系列制造任务，根据时间的推进来配置服务（或资源）的过程，与此同时考虑满足时间、成本、服务质量和可用性等方面的约束。多任务调度是云制造系统的重要组成部分，对系统性能有着重要影响。目前，云制造环境下多任务调度问题引起了学者们广泛关注。CHENG等［5］从云制造企业的角度研究了多任务虚拟资源整合与调度优化，他们把调度问题聚焦于在交货期限的约束下，利用有限的资源尽可能获得更高的利润。LIU等［6］研究了云制造多任务服务组合问题，目的是最大限度地提高所有任务的总体QoS。赵金辉等［7］应用前景理论构建了一个考虑主体心理的云制造服务选择双层规划模型，优化需求方对服务的心理满意度。赵道致等［8］将主体的偏好序作为依据，基于前景理论设计了云制造资源供求双方的稳定匹配机制。上述研究分别着眼于云制造任务调度过程中多任务协调问题、满意度问题、能量消耗问题、资源利用率问题等［6，9⁃12］，但都没有从完整的可持续性框架来研究如何调度云制造任务。

鉴于此，本文针对云制造多任务调度的实际，结合制造系统的可持续性框架，设计基于可持续性的云制造多任务调度模型，并改进遗传算法对其进行求解。最后，通过实验证明整个模型的可行性和有效性。

1 基于可持续性的云制造调度框架

基于可持续性的云制造多任务调度指的是为了完成一系列云制造任务，根据时间的推进来配置云服务（或资源）的过程，与此同时考虑满足时间、成本服务质量等方面的约束，从而达到合理利用资源，提高环境、经济和社会层面可持续性的目的。

假设云制造平台上有M个注册企业，表示为Ent(M)={E1,…,Ei,…,EM}，见图1。每一个企业Ei(i=1,2,…,M)可以提供Li种不同类型的制造服务，并且用Si,l(l=1,2,…,Li)表示企业Ei的第l个服务。

图1 云制造多任务调度示意图Fig.1 Schematic diagram of CMfg multi-task scheduling

客户将订单发布到云制造服务平台，平台将这些订单处理为不同的任务，这里考虑每一个订单都被处理为一个云制造任务的情况。对于小型任务，平台客户与供应商之间能够根据发布的信息自由选择，而对于不能由一个供应商单独完成的任务，就需要平台方来统一调度。假设某一决策周期内（比如一天内）平台上收到N个任务，用Task(N)={T1,…,Tj,…,TN}表示任务池。每个任务可能需要调用一种或者多种服务，将任务Tj分解为不同粒度的Kj子任务，STj,k（k=1,2,…，Kj）表示任务Tj的第k个子任务，每一个子任务需要一种不同类型的云制造服务。任务由一种特定的顺序、并行、选择和循环4种基本结构的组合而成。

一个任务被发布到云制造平台以后，首先被分解为子任务，再为每一个子任务搜索可匹配的服务，见图2。

图2 云制造服务搜索与匹配示意图Fig.2 Schematic diagram of CMfg service searching and matching

在云制造任务调度过程中，供应商根据工业产品的工作状态和客户的动态要求，承担着相关的培训、运行、维护、升级、回收再制造等相关服务，相比于客户购买产品的方式，这将减少材料浪费和能源消耗。客户所需的产品服务对维护产品功能和提供更好的解决方案非常重要。此外，与客户的互动和他们在这个阶段的反馈使云制造供应商能够改善他们的产品和服务创新。另一方面，作为一种资源选择或组合问题，资源服务调度对成功的产品服务交付是必不可少的。这些资源的异质性和动态性导致供应商产品服务配置的混乱和低效。此外，在资源方面，客户对产品服务的要求更高，产品服务的数量和容量有限。在传统的资源服务调度方法中，每个客户的需求是由最优服务资源独立满足的。然而，在实际的服务运营中，在一个决策周期内多个客户分别提出需求，产品服务的有限可用资源需要有效分配。此外，服务资源的调度结果应该基于客户满意度，并受产品服务成本和环境因素影响。因此，对于云制造平台而言，如何分配和安排云制造运行阶段的有限资源，必须从经济、环境和社会可持续性的角度来确定，见图3。

图3 制造系统的可持续性框架Fig.3 Framework of sustainability in manufacturing system

2 基于可持续性的云制造调度模型

2.1 基本假设

（1）每一个任务需求都需要考虑可持续性；（2）从服务提供商的角度，任务需求之间相互独立；

（3）每一个任务都需要分解为多个子任务，且每一个子任务都至少有一个可用的服务提供商；

（4）不同服务提供商完成同一个子任务需要的时间和成本不一样；

（5）平台上的供应商都是经过审核的，不会出现不端行为，即使有，也有相应的协议来弥补客户的损失。

2.2 主要符号

2.3 目标函数

基于可持续性的云制造调度需要同时最大化客户满意度，最大化资源利用率，最小化资源服务成本，为了便于求解，本文在目标函数中采用不满意度代替满意度，用设备闲置率代替资源利用率，将目标函数统一为最小化问题。这三个目标分别体现了可持续性的不同层面，共同构成了云制造调度的可持续性目标函数。因此，调度模型的优化目标可以表示为

式中，z为综合的可持续性；CSD为客户的不满意度；RUE表示资源闲置率；RSC为资源服务成本；ω1、ω2和 ω3为权重，满足=1，ωj∈[0,1],∀j。

2.3.1 客户不满意度

客户不满意度CSD源自于客户需求和服务之间的匹配程度，反映了服务提供商与客户之间的相互关系，对可持续性产生了人为影响。因此，CSD能够看作为一种社会层面可持续性的非直接反应。通常，CSD包括服务质量和服务响应速度两个方面。但是目前云制造还处于初级阶段，没有足够的客户评价数据来衡量服务质量的好坏，另一方面客户对服务质量的满意度更多是一种事后评价。因此，这里仅考虑服务响应速度对客户满意度的影响，忽略服务质量的影响只是影响CSD值的大小，并不会影响本文方法的可行性和有效性。CSD表达式为

式中，α、β、λ是参数。

云制造平台在调度多个任务时，目标是保障所有的任务都尽可能在客户期望的时间内完成。因此，当FTj≤ETj时，客户对完成时间完全满意，满意度Stj=1；当 FTj＞ DLj时，任务Tj没有在客户给定的条件内完成，=0；当ETj≤ FTj≤ DLj时，根据式（2），同时考虑到结果的标准化，将客户j对任务Tj完成时间的满意度函数定义为=是客户j对服务响应的心理参数，可以根据客户的订单问卷得到。因此，表示为

为了做对照实验，构建完全基于客户对时间和成本不满意度的优化目标函数：

2.3.2 资源闲置率

最小化资源闲置率RUE意味着使用最少的资源获得最大的效果，从而提升经济层面的可持续性。需要说明的是，在任务不需要分解为子任务的情况下，为了让客户得到及时的服务，通常就需要让资源处于等待状态，这样资源闲置率就不会太低，过低的资源闲置率会导致出现子任务需要花时间等待资源释放的情况，从而降低客户的满意度。但是，这里我们考虑的是每一个任务都需要分解为多个子任务的情况，客户对服务响应的要求是最终完成时间，而具体某一个子任务的等待时间并不会直接影响客户的满意度。相反，过高的资源闲置率会影响到云制造平台经济层面的可持续性。资源闲置率表达式为

2.3.3 资源服务成本

资源服务成本RSC是用实际服务成本TC的标准化处理来表示。TC由服务成本、物流成本和环境成本三个部分组成。在计算TC时，服务过程中的碳排放被考虑进去并转换为环境成本。因此，RSC能够综合反映云制造调度过程中经济和环境层面可持续性，表达式如下：

式中，TC、TCmin和TCmax分别为实际的服务成本、可选择的最小服务成本和最大服务成本；SCj、LCj和ECj分别为任务Tj的服务成本、物流成本和环境成本；为决策变量；是任务成本和 b为决策变量，用于判断任务Tj的两个相邻子任务分别被分配给哪两个企业，然后根据前一个子任务STj,k的单位距离物流费用η和这两个企业之间的距离di,i′计算物流成本；为服务l执行任务STj,k的环境成本。

2.4 约束条件

（1）时间约束。任务Tj的完成时间FTj由三部分组成：服务时间STj、物流时间LTj和等待时间WTj。startTj,k是子任务 STj,k的结束时间，end Tj,k是子任务STj,k的结束时间。

对于任意一个服务，后一个任务的开始时间大于前一个任务的结束时间，即满足

在基于可持续性和基于满意度的调度模型中都要求每一个任务完成时间小于客户要求的最终期限：FTj＜ DLj。

（2）成本约束。在基于可持续性模型中，任务Tj的成本Cj包括服务成本、物流成本和环境成本，在基于满意度的模型中，只考虑服务成本和物流成本，环境成本不作为优化目标。在基于满意度的调度模型中每一个任务完成时间小于客户要求的最终期限：FTj＜DLj。而在基于可持续性模型中，关注整体成本，不强调单个任务成本约束。

（3）任务约束。任务被分解后，云制造平台为每一个子任务搜索和匹配服务，见图2。每一个子任务只能分配给一个企业，且任务分配后，执行该任务不中断直到任务完成。如果服务Si,l被选择用于完成子任务STj,k，那么=1，否则=0。只允许匹配一个服务来执行子任务STj,k，对于任意给定的 j和k，都有

3 解决办法

3.1 个体编码

采用基于多层整数编码的方式对染色体编码。当待调度的任务总数为N，任务的子任务个数为j时，个体的长度为其中，染色体的前半部分表示所有任务在企业上的服务顺序，后半部分表示任务每个子任务匹配的企业服务。如个体[1 2 3 42 4 3 1 2 2 1 3 1 3 3 2],该个体表达了4个子任务个数为2的任务在3个企业的服务顺序。其中，前8位表示任务的调度顺序，为任务1⁃2⁃3⁃4⁃2⁃4⁃3⁃1；9到16位表示服务企业，依次为2⁃2⁃1⁃3⁃1⁃3⁃3⁃2。

3.2 适应度值

染色体的适应度值为所有客户总的不满意度，适应度值计算公式为

式中，U为所有客户对调度方案的总的可持续性。

3.3 选择操作

选择操作采用轮盘赌法选择适应度较好的染色体，个体选择概率为

式中，pi(i)为染色体i在每次选择中被选中的概率。

3.4 交叉操作

交叉操作采用整数交叉法。步骤是首先从种群中随机选取两个染色体，并取出每个染色体的位，然后随机选择交叉位置进行交叉。交叉后某些任务的子任务多余或者缺失，因此，需要把多余的子任务调整为缺失的子任务，并调整对应的服务。交叉操作见图4。

图4 遗传算法交换操作图Fig.4 The crossover operation

3.5 变异操作

变异算子的步骤首先是从种群中随机选取变异个体，然后随机选择变异位置1和2，最后把个体中这两个子任务以及对应的服务序号交换。如果变异后的工序不符合要求，则进行调整。变异操作见图5。

图5 遗传算法变异操作图Fig.5 The mutation operation

基于多层编码遗传算法的云制造任务调度算法流程见图6。

图6 遗传算法流程图Fig.6 Flow chart of genetic algorithm

4 模拟实验

为了验证调度模型和遗传算法的有效性，在MATLAB（R2016a）上设计了模拟实验。实验分为两个部分，第一部分考虑的是本文提出的基于可持续性的调度模型（下文称实验一），第二部分将基于满意度的调度模型作为对照（下文称实验二）。

本例中共有4家企业，5个任务，每家企业分别能够提供3种类型的云制造服务，每个任务分别包含6个子任务，任务与服务的对应关系见表1。其中，企业 E2提供 S11、S12和 S133 种服务，任务T1的第一个子任务ST1,1可选的服务有S11和S31两种。

表1 任务可选服务表Tab.1 List of available services for the tasks

在云制造环境下，任务中通常都包含了客户的个性化需求，而每一个企业的能力和所提供的个性化服务特色也不会相同，因此同一个子任务采用不同的服务，其时间和成本也会不一样，本例中任务成本和任务时间信息见表2和表3。这两个表中的信息和表1是相互对应的，如任务T1的第5个子任务ST1,5在服务S23中成本和时间分别为673和26。

表2 任务成本信息Tab.2 Task cost information

表3 任务时间信息Tab.3 Task cost information

在基于可持续性的调度模型中，考虑了不同任务采用不同服务时，面临着不一样的环境成本，这个成本与任务成本虽然形式是一样的，但其意义体现在对环境的重视，因此不能简单地纳入任务成本范围内。在实验一中，环境成本纳入了可持续性优化目标，而在实验二中，环境成本不计入客户应该承担的成本范围。本例中具体的环境成本信息见表4。其中，任务T3的第3个子任务ST3,3在服务S42中的环境成本为23。

表4 环境成本信息Tab.4 Environmental cost information

企业之间的地理距离见表5。其中，企业2和企业5之间的距离为468.02。本例中假设所有服务之间都需要有物流过程，单位距离的物流费用为0.008，物流成本为0.005。

表5 企业间的地理距离Tab.5 Geographic distance between enterprises

在实验一中，客户对服务时间的不满意度被认为是可持续性的一个方面，而服务成本则纳入整体优化的范畴；在实验二中，则以完全最优化客户对时间和成本的不满意度作为目标。本例中考虑的客户与任务是一一对应的，即客户3的任务称为任务3，客户的心理期望见表6。其中，客户2的期望时间ET2为160，最终期限DL2为370，期望成本EC2为5 260，最高成本HC2为5 960，对时间的心理期望参数为2.9，对成本的心理期望参数为2.4，系统给定的重要程度μ2为0.27。

表6 客户心理期望Tab.6 Customer psychological expectation

在两组实验中，遗传算法的基本参数设置如下：种群数量为60，最大进化次数为50，交叉概率为0.8，变异概率为0.6。

首先在实验一中，以优化可持续性为目标进行模拟实验。我们将客户对时间的不满意度、资源服务闲置率和总成本的权重分别设为0.2、0.5和0.3。从图7中可以看出种群的平均值和最优值都得到了有效的降低，最优解从最初的0.44降到了0.36，种群的平均值也从0.55降到了0.49。

图7 基于可持续性目标的迭代过程（实验一）Fig.7 Iterative process based on sustainability goals（experiment one）

在基于可持续性的调度模型中，同样考虑了任务时间的客户满意度，并且将任务成本纳入整体优化。因此，基于客户满意度的调度模型的最优解也随着可持续性的优化过程而逐步变小，见图8。但由于客户满意度不是实验一的唯一优化目标，因此种群的平均适应度波动相对较大。

图8 基于满意度目标的迭代过程（实验一）Fig.8 Iterative process based on satisfaction goals（experiment one）

实验一得出的最优解的调度甘特见图9和图10。其中，图9从企业的角度展示了调度过程，图10则是从任务的角度展示了调度过程，调度任务之间的深色部分表示了物流过程。可以看出各任务依次进行，等待时间相对较少。

图9 企业角度的调度甘特图（实验一）Fig.9 Gantt chart of enterprise perspective（experiment one）

图10 任务角度的调度甘特图（实验一）Fig.10 Task scheduling Gantt chart（experiment one）

图11 和图12分别展示了对时间和成本的优化程度。总体来看，调度结果都尽可能满足了客户的期望，但优化目标强调整体的成本，因此在最优方案中出现了任务1的成本超过客户设定范围的情况。在实际中，实验一对应的情况很可能是客户先提出服务时间和成本，并交纳了定金，因此即使在整体调度过程中，服务成本超过了客户的预期，也很有必要完成任务，否则可能面临更高的违约惩罚。

图11 任务时间优化效果（实验一）Fig.11 Optimization effect of task time（experiment one）

图12 任务成本优化效果（实验一）Fig.12 Optimization effect of task cost（experiment one）

在实验一中，环境成本和资源闲置率都是优化目标的一部分，最优解的情况见图13和图14。

图13 环境成本分布（实验一）Fig.13 Environmental cost distribution（experiment one）

图14 资源闲置率优化效果（实验一）Fig.14 Optimization effect of resource idle rate（experiment one）

最后在实验一中，以优化可持续性为目标，进行500次模拟，每一次都按照实验二的参数求出客户的不满意度，其统计结果见图15和图16。可以看出可持续性适应度分布在0.365的次数最多，而满意度适应度分布在0.035的次数最多。

在实验二中，以优化所有客户总的满意度为目标进行模拟实验。遗传算法的搜索过程见图17。从图中可以看出种群的平均值和最优值同样得到了有效降低。相比于实验一（图8），种群平均值的变化更加稳定，且最优解效果更好。

图15 可持续性适应度的统计结果（实验一）Fig.15 Statistical results of sustainability fitness（experiment one）

图16 满意度适应度的统计结果（实验一）Fig.16 Statistical results of satisfaction degree of fitness（experiment one）

图17 基于满意度目标的迭代过程（实验二）Fig.17 Iterative process based on satisfaction goals（experiment two）

同样，在优化客户满意度的过程中，可持续性指标也逐步变小，但达到最优解的速度更慢，同时种群平均值也波动较大，见图18。

实验二的调度甘特图见图19和图20。其中，图19从企业的角度展示了调度过程，图20则是从任务的角度展示了调度过程，同样用深色表示任务之间的调度过程。

图18 基于可持续性目标的迭代过程图（实验二）Fig.18 Iterative process based on sustainability goals（experiment two）

图19 企业角度的调度甘特图（实验二）Fig.19 Gantt chart of enterprise perspective（experiment two）

图20 任务角度的调度甘特图（实验二）Fig.20 Task scheduling Gantt chart（experiment two）

图21 和图22分别展示了对时间和成本的优化程度，将优化的时间成本与客户期望值与最大值作比较，总体来看，调度结果都很接近客户的期望值。相比于实验一，这里并没有出现成本时间超过客户设定界线的情况，因为那样会导致目标函数的恶化。最优方案通过折中平衡各个客户的利益，尽可能满足每一个客户。

实验二中的环境成本和资源闲置率见图23和图24，与图13和图14相比较，可以发现在实验一中，环境成本得到有效降低，而完全闲置的资源数量也只有1个，少于实验二中的3个。

图21 任务时间优化效果图（实验二）Fig.21 Optimization effect of task time（experiment two）

图22 任务成本优化效果图（实验二）Fig.22 Optimization effect of task cost（experiment two）

图23 环境成本分布图（实验二）Fig.23 Environmental cost distribution（experiment two）

图24 资源闲置率优化效果图（实验二）Fig.24 Optimization effect of resource idle rate（experiment two）

最后在实验二中，以优化总体不满意度为目标，进行500次模拟，每一次都按照实验一的参数求出可持续性，其统计结果见图25和图26。可以看出实验二中客户总体满意度分布在0.03的最多，可持续性在0.39的最多，和实验一相比较，实验二在优化可持续性过程中客户的满意度没有明显降低，而可持续性则有所优化。

图25 满意度适应度的统计结果图（实验二）Fig.25 Statistical results of satisfaction degree of fitness（experiment two）

图26 可持续性适应度的统计结果图（实验二）Fig.26 Statistical results of sustainability fitness（experiment two）

通过两组实验可以看出，在实验一中以优化可持续性为目标，调度方案能够在客户满意度、资源利用率和服务成本方面实现整体优化，虽然忽略了客户对服务成本的要求，但对于平台运营者来说这是合理的，一方面能够按时完成任务，不会有违约金，另一方面平台并没有因为一个任务成本偏高而引起整体成本上升；在实验二中，同时考虑客户的时间和成本心理期望，将降低客户总体不满意度作为优化目标，调度结果符合每一个客户的要求，并且非常接近客户的期望目标，但是设备闲置率和环境成本相比于实验一要高。随着云制造的发展，不同的服务模式得到应用，经济、社会和环境可持续性将会是不可忽略的因素，而基于可持续性的调度模型的优势也会越来越明显。

5 结论

对云制造平台多任务调度流程和可持续性框架进行分析，构建了基于可持续性的云制造多任务调度模型。设计了改进的遗传算法来有效解决调度模型的求解问题。通过两组对比实验，分析了可持续性因素对调度结果的影响。通过模拟实验可知，在只考虑客户满意度的情况下，调度结果能够实现每一个客户期望的优化，但从整体的可持续发展来看，其设备闲置率和环境成本相对较高；而设计的基于可持续性的调度模型，能够在不损失客户满意度的前提下，同时降低环境成本和设备闲置率，保障平台整体的可持续运行。