武善玉 李云鹤

引言

制造业对于社会、经济、环境都有着重大的影响。随着技术的更新，具有高计算能力、通信能力和控制能力的智能化制造设备将成为制造系统新的设备资源。信息物理系统（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中选取合适的服务完成加工操作。任意两个服务间的运输环节可忽略。

问题的相关假……