面向大规模并发制造服务请求的资源优化配置
2019-07-31张宏国石岩磊马超张淑丽刘胜辉
张宏国 石岩磊 马超 张淑丽 刘胜辉
摘 要：针对如何高效处理云制造服务平台中大规模时序并发的制造服务请求这一问题，提出了一种面向服务响应时间的制造服务请求分段算法，通过制造任务相似性距离算法来保障分段算法的准确性。在分段算法保证制造服务请求完整性的前提下，构建了制造服务资源的关联区域。在此基础上，进一步提出了一种基于关联区域的制造服务资源分配算法，在时间维度上，保障了制造服务资源提供的公平性，从而提高了资源受限情况下的制造服务资源全局优化配置效率。最后通过实验测试和分析证明了算法的正确性和有效性。
关键词：云制造;大规模请求;制造资源配置
DOI：10.15938/j.jhust.2019.03.002
中图分类号： TP391
文献标志码： A
文章编号： 1007-2683（2019）03-0009-07
Abstract：Aiming at how to efficiently handle the massive temporal sequential manufacturing service request in cloud manufacturing service platform， this paper proposes a service response timeoriented service request segmentation algorithm. The manufacturing task similarity distance algorithm is used to guarantee the segmentation algorithm accuracy. Then the correlated region is constructed under the premise of ensuring the integrity of manufacturing service request. On the basis of this， a manufacturing service resources allocation algorithm based on correlated region is proposed so as to ensure the equal distribution of manufacturing service resources in temporal dimensions， and then to improve the efficiency of the global optimization of the manufacturing service resources in the case of limited resources. Finally， the correctness and validity of the algorithm are proved by experiment and analysis.
Keywords：cloud manufacturing; massive service requests; manufacturing resource allocation
0 引 言
隨着“互联网+”模式被广泛的认同，作为近年来热门研究方向的敏捷化制造获得了更快速的发展。越来越多的世界一流企业、公共机构都在往敏捷化更高的云服务平台上迁移。通过云服务平台可以实现效率的最大化和成本的降低。云制造作为一种先进的敏捷制造模式由李伯虎院士提出，它是对已有网络制造的延续和云升级。云制造是一种面向服务的网络化制造新模式，云制造基于云计算、物联网和大数据等先进的信息化技术，它将传统制造企业分散的制造资源，通过虚拟化的方式接入到云制造服务平台进行统一管理，为制造企业提供全生命周期的制造服务[1]。既实现了同网络化制造一样的“分散资源集中利用”，又实现了“集中资源分散使用”的设计思想。一方面使得接入企业的制造资源可以同时向多个企业提供服务，大大的提高了制造资源的利用率[2-3];另一方面能力有限的企业可以通过使用云制造服务来提高自身的加工能力，提升企业的竞争力和市场占有率，从而提高企业的经济收益。
目前，云制造的研究主要集中在云制造平台的整体架构、制造资源的虚拟化[4]、落地应用[5]等方面。在制造任务的处理和资源的分配方面Lartigau J等[6]提出了一种将制造任务订单分解成多个子任务的云制造任务处理模型，通过多任务去匹配云平台中的制造资源共同执行一个订单任务，实现了一种基于云平台级的云制造资源的配置方法。王时龙等[7]建立了以物料流和信息流的成本和时间为主要影响因素的云制造资源配置模型，以成本最少、时间最短和质量最优为优化目标，采用最大继承法对模型进行求解。苏凯凯等[8]等建立了一种考虑云制造平台服务运营者和服务请求者双方的制造资源配置双层优化模型，以服务质量和柔性指标为优化目标，使用改进的多目标算法对问题进行求解。尹超等[9]针对云制造服务配置过程中多个目标建立了一种面向新产品开发的优选模型，采用灰色关联度方法对模型的求解进行了分析和验证。然而多数学者在制造资源优化配置方面通常都是对单一任务的处理[10]，然而在云制造平台实际运行过程中，将面临着大规模、时序并发性的云制造服务请求处理，这方面的研究却很少受到学者的关注。云制造平台作为开放的平台，如何高效的处理大规模并发的任务请求;同时现代客户对制造服务的需求也从基本功能关注逐渐的转变成了以服务收益和满意度为标准的个性化服务请求[11]，如何提高用户的整体满意度。这些新的问题对云制造平台的落地实施提出新的挑战。
本文从云制造平台的实际运行角度出发，对大规模时序并发制造服务请求的问题分析，设计了一种保证任务完整性的制造服务请求分段方法，并且提出在此基础之上的制造服务资源分配方法，可以在云制造平台的宏观层面上保证用户获得服务的公平性和全局最优，进而提升平台中用户的整体满意度。
1 云制造环境下制造任务与制造资源的虚拟化描述
云制造平台让所有用户与企业的互动集中在同一个平台，使得客户提高了从设计到产品的转换率，企业提高了制造资源利用率，是一个双赢的服务平台。云制造平台结构示意图，如图1所示。通过云制造平台的纽带作用，制造资源服务提供方将资源通过虚拟化接入到平台中供平台调度使用，服务请求方将制造服务请求下达至云制造平台，平台将根据每个制造服务请求生成相应的制造任务订单，粒度大的产品级任务将进行分解成零部件级和工件级然后分配相应的制造资源进行加工，粒度小的任务可以直接参与制造资源的分配和调度。通过实际问题的分析发现，云制造设备资源不像云计算資源可以不受限于服务资源的地理位置，在云制造服务的过程中需要将服务请求者的工件通过物流运输至不同的企业中进行多次车间现场加工，所以配置资源的过程中运输因素也是要充分考虑的一个特点。
云制造服务请求问题可描述为：有n个制造任务{Task1，Task2，…，Taskn}，有m处制造服务资源{Service1，Service2，…，Servicem}可以提供服务，每个制造任务可以通过一个或多个资源进行加工。
首先，对云制造环境下的制造服务请求和制造资源云服务进行虚拟化描述，本文主要研究的制造资源为制造设备资源。
1.1 制造服务请求
每个制造服务请求以制造任务的形式进行表示。制造任务Task描述为一个六元组，Task=
1）TaskID是任务的唯一编号。
2）BAttrInfo是对任务的基本静态属性信息描述，BAttrInfo=（Name， PList， Material， Num， Unit， Grade），分别表示加工任务的名称、工序列表、材料、加工数量、计量单位、任务等级（产品级、零部件级、工序级）。PList 表示工序列表，其中的每一个列表项表示一项待处理的任务，Process=（ProcessID， Name， Precision）分别表示工序唯一编号，名称、加工精度。
3）Constraints表示对任务的加工约束信息描述，Constraints=（maxTime， maxCost， minQuality， minSatisfaction），分别表示任务要求的最大服务完工时间，最多资金花费，最低的质量标准，最低的满意度标准。
4）TraInfoList是对任务的运输相关信息描述，其中每一个列表项表示一个物流信息，TraInfo=（ProcessID， StartLocation， EndLocation， Conveyance， TranTime， TranCost， Remark），分别表示加工任务的工序唯一编号、运输起点企业、到达的终点企业、运输方式、运输花费时间、运输花费资金、特殊的运输说明。
5）DAttrInfo是对任务的动态信息进行描述，DAttInfo=（curProcessID， State， curStartTime， curEndTime），分别表示当前任务的执行状态，有在制、在途、等待、完成四种状态、当前对应工序编号、当前状态开始加工时间、结束时间。
6）AttaInfo是任务的附件信息描述，AttaInfo=（note， URL），分别表示附件信息说明、附件信息网络地址。附件中可以是工件的设计图纸、特殊工艺说明等等。
1.2 制造设备资源云服务
制造设备资源云服务。制造设备资源云服务Service可以定义为一个五元组，Service=
1）ServiceID是设备云服务的唯一编号。
2）BAttrInfo是设备云服务的基本静态属性信息描述，BAttrInfo=（Name， Model， Enterprise， Location， Cost， Unit），分别表示设备云服务的名称、型号、提供企业、物理位置，以“元/单位”表示，单位Unit包括不同的计量方式小时、件等。
3）FunAttrInfo是设备云服务的加工能力描述，FunAttrInfo=（Type， Material， Shape， Size， Precision），分别表示设备云服务的生产类型，对象材料特征，对象形状特征，对象尺寸特征，对象加工精度。
4）EvaList表示用户评价历史集合，每一个列表项表示一次用户评价，Evaluation=（UserID， TaskID， Scores， EvaTime） 分别表示评价的用户编号、任务的唯一编号、评分、评价时间。
5）TList表示动态的任务处理列表，TList=（State， PTask） 其中State表示服务的状态，有空闲、工作、报修、维修四种状态，每一个列表项PTask表示一项处理任务，PTask=（TaskID， Num， State， RemainNum， ProcessID， EsStartTime， MaxResTime），分别表示任务的编号、需要加工数量、任务的执行状态、未处理的数量、工序编号、预计开始加工时间、服务的最大响应时间。
2 大规模时序并发制造服务请求的高效处理
在云制造服务请求过程中不同的制造服务请求者可能在短时间内发出多个服务请求，这些目标不同的请求构成了大规模并发性制造服务请求，由于本文主要考虑的制造资源为制造设备，制造设备资源是有限的所以无法在短时间内满足每个客户的请求。如果使用传统的算法，那么在时间维度上先到达的客户会优先使用全部可用的服务资源，后续的用户优化效果往往都要受限于先前的资源使用情况，可能优化的效果仅仅是局部最优，由此产生的服务优化效果对整体用户的满意度将产生负面的影响。这种资源分配算法无法保证平台可以公平的为每个用户提供不受时间序列限制的服务资源，随着用户的满意度下降最终也将导致平台的收益下降。针对大规模制造服务请求优化问题，在考虑任务的完整性和服务公平性的角度，对大规模请求进行分段处理和分段间制造服务力进行均衡配置，进而达到时间维度的全局最优，提高用户整体满意度。
2.1 制造任务分解方法
在云制造产品生产过程中，加工产品往往是由一组工件组装而成，每个工件的制造过程中还要考虑彼此的约束关系。往往云制造产品的生产规模大、复杂度高、任务粒度粗等特点，本文首先将粒度大的任务订单进行多任务的分解，便于协同加工提高制造效率。根据产品的所处阶段，可以将制造任务分为产品级、零部件级和工件级三层。根据每个子任务的生产工艺分解成一道或多道工序，形成一个整体的工艺加工树状图，从树的叶节点开始执行任务，最终到达根节点完成整个产品。
对已有的分解方法进行研究后[12-13]，本文依据大规模并发任务的特点采用自上而下的分解方法，即根據产品逐层向下细分。在分解过程中会根据平台分解任务的历史记录寻找相似的任务分解方案，形成一定的分解模板。根据新产品的约束条件和目标，在模板上通过局部调整从而生成新产品任务分解结构，通过对任务分解结构模板的利用，可以减少在任务分解中的工作量，提高工作效率。除使用模板外还将结合客户定制计划。当客户对产品的整个生产有详细的分解计划进行服务请求时，平台首先需要分析计划是否可以满足，在满足需求的情况下平台将分配资源去执行加工任务，如果平台无法满足需求则使用平台提供的分解方案进行调整。
2.2 面向服务响应时间的制造服务请求分段算法
传统算法是将整个制造服务请求流进行时间维度的均匀分段处理，然而实际的制造服务请求流中分布可能是不均匀的。图2展示了传统方法处理过程，其中每个文档图标代表一个制造服务请求产生的制造任务，每个分段间由虚线进行分割，左侧部分表示正在接受服务的请求。传统算法针对整个时间维度的请求都进行了均匀分割。图3展示了制造服务请求分段算法处理过程，该方法依据每个请求的服务响应时间上限来进行分段间距控制，保证了每个请求不会因为分段算法而产生服务质量的明显影响。
2.3 制造任务相似性距离
在分段处理过程中，需要对任务的执行时间进行预估，在预估时将使用功能性相似的请求作为参考[14-15]。在制造加工的同一领域中制造服务请求的加工任务规模、涉及的加工工序及流程都是具有较高的相似性，不同的服务请求可能包含的具体工序数目和前后关系不一致，但其执行服务过程中存在大量的重叠部分，这意味着功能性相似的请求间存在大量的相同加工工序和制造设备资源使用，而不同的用户会在服务综合质量上有着各种个性化的要求。因此对同一制造领域中服务请求的相似程度通过请求间的相似距离进行描述，请求间的相似距离通过式（1）进行计算：
其中：Task1、Task2表示需要计算的两个任务，Q+表示对评价有正相关的m个评价指标;Q-表示对评价有负相关的n个评价指标。
Q+包含服务质量和用户满意度。其中服务质量平台根据服务可靠性、设备故障率和可维护性三项指标对资源进行评分。服务质量通过归一化后使用数值[1，10]进行评分，数值越大代表质量越好;用户满意度可以通过资源历史使用者的评价进行计算得出，使用数值[1，5]进行评分，数值越大代表满意度越高。
Q-包含服务完成时间和服务成本。服务执行过程中工件需要在不同地理区域进行运输。其中服务完成时间包括服务执行时间和运输时间。服务成本包括服务执行费用和运输费用。
2.4 基于关联区域的制造服务资源分配算法
在经过请求分段后，第i分段的制造服务请求占用的制造资源所影响区域Srelai，称为第i段的关联区域。如图4所示，图中第i段的关联区域为分段的结束时刻到所有制造服务使用完毕的最晚时刻。所以设分段Si包含n个请求，则Si的关联区域Srelationi=[tei，tei+max{Tk|k=1，2，…，n}]。
3.2 测试与分析
为了验证模型和算法的有效性，通过某电机制造任务数据结合云制造平台的实际特点进行实验设计和测试。使用电机制造过程中常用的车床、钻床、镗床、刨床、铣床等制造设备资源作为制造服务供平台使用，云制造平台中的候选制造服务满足T∈[2，10]C∈[10，20]Q∈[9.5，9.8]S∈[4.5，4.8]。通过随机产生制造任务请求，用户请求要满足T∈（15，20）C∈（1850，2000）S∈（4.40，4.70）Q∈（9.5，9.70），每个单位时间产生[0，4]个新请求。
平台首先在接到任务请求订单后先通过2.1节分解方法进行任务的分解，然后使用请求分段算法对大规模的制造任务请求进行分段，进而进行制造服务资源分配，使用粒子群算法来对方案进行搜索和资源配置[16-9]，设置种群大小为50，进化代数为300。产生120个单位时间的模拟数据，使用前80个单位时间作为历史数据的收集，后40个单位时间作为算法测试。
为了验证算法在不同服务资源条件下的性能，通过设同类型机器分别提供5、10、15 3种并发。图5到图7分别是算法在3种条件下的运算结果。x轴表示时间，y表示该时间点上的评价综合服务质量通过图中结果可以看出传统的方法在制造任务执行的开始阶段由于资源充足，使得加工的服务质量较优，然而随着时间的推移服务资源的短缺，导致服务质量出现明显的波动，造成制造后续到达的用户无法得到高质量的服务。而基于关联区域的制造资源分配算法可以在服务资源充足和不足的情况中均表现出较好的服务质量稳定性，可以为用户提供与到达时间无关的公平资源使用条件。
表3表示两种配置算法在不同条件下的测试结果，数值越大代表综合质量越优。通过服务平均综合质量可以看出分段算法保证了任务的完整性，在配置资源时保证时间维度的加工连续性提高了服务平均综合质量。从服务综合质量标准差可以看出，分段算法和关联区域制造资源分配算法通过对后序制造请求的考虑，保证了加工质量的稳定性，提高了用户的整体满意度。
4 结 论
本文依据云制造平台中任务的特点进行制造任务分解，以此提高加工效率和任务整体稳定性。然后考虑到云制造平台制造任务大规模并发性的特点，对大规模并发任务进行了制造任务分段和服务资源预留的处理，既保证了用户对资源调用的公平性，又保证了有限的服务资源可以在大规模请求序列中达到全局最优，从而提高了用户的整体满意度，可以为平台赢得更多的用户。通过上述算法在实验中的使用，可以证明该方法高效的解决了云制造环境下大规模并发性制造任务请求的制造资源服务全局优化配置问题。
参 考 文 献：
[1] FEI T， HU Y， ZHOU Z.Correlationaware Resource Service Composition and Optimalselection in Manufacturing Grid[J]. European Journal of Operational Research， 2010， 201（1）：129.
[2] SCHULTE S， HOENISCH P， HOCHREINER C， et al. Towards Process Support for Cloud Manufacturing[C]// IEEE International Conference on Enterprise Distributed Object Computing. 2014：142.
[3] 李伯虎，張 霖， 王时龙，等. 云制造—面向服务的网络化制造新模式[J].计算机集成制造系统， 2010， 16（1）： 1.
[4] 任磊， 张霖， 张雅彬，等. 云制造资源虚拟化研究[J]. 计算机集成制造系统， 2011， 17（3）：511.
[5] 万曹雷， 邵俊鹏. 云制造环境下车间制造资源网格管理设计[J]. 哈尔滨理工大学学报， 2013， 18（5）：37.
[6] LARTIGAU J， NIE L， XU X， et al. Scheduling Methodology for Production Services in Cloud Manufacturing[C]// International Joint Conference on Service Sciences. IEEE Computer Society， 2012：34.
[7] 王时龙， 宋文艳， 康玲，等. 云制造环境下的制造资源优化配置研究[J]. 计算机集成制造系统， 2012， 18（7）：1396.
[8] 苏凯凯， 徐文胜， 李建勇. 云制造环境下基于双层规划的资源优化配置方法[J]. 计算机集成制造系统， 2015， 21（7）：1941.
[9] 尹超， 张云， 钟婷. 面向新产品开发的云制造服务资源组合优选模型[J]. 计算机集成制造系统， 2012， 18（7）：1368.
[10]张淑丽， 刘胜辉， 沙晨明. 求解柔性作业车间调度的岛屿模型遗传算法[J]. 哈尔滨理工大学学报， 2016， 21（5）：101.
[11]胡艳娟， 武理哲， 张霖，等. 云制造服务评价理论与方法研究综述[J]. 计算机集成制造系统， 2017， 23（3）.
[12]易树平， 谭明智， 郭宗林，等. 云制造服务平台中的制造任务分解模式优化[J]. 计算机集成制造系统， 2015， 21（8）：2201.
[13]刘明周， 王强， 凌琳. 基于分层任务网络的云制造任务分解方法[J]. 中国机械工程， 2017， 28（8）：924.
[14]王国新， 杜景军， 阎艳，等. 面向加工功能均衡分布的制造系统构形优化[J]. 计算机集成制造系统， 2015， 21（6）：1497.
[15]贺可太，朱道云. 云制造服务质量评价研究[J]. 计算机集成制造系统， 2017.
[16]ZHANG Hongguo， HE Linyan， MA Chao， et al.Improved MultiRulesBased ACO algorithm for FJSS Problem in Cloud Manufacturing Environment [J].International Journal of Hybrid Information Technology 2016：29.
[17]张宏国， 宫雪. Jobshop调度求解的广义蚁群算法[J]. 哈尔滨理工大学学报， 2017， 22（1）：91.
[18]刘胜辉， 李小阳， 张淑丽. 求解车间调度问题的双禁忌表禁忌搜索算法[J]. 哈尔滨理工大学学报， 2016， 21（6）：50.
[19]乔佩利，马丽丽，郑林. 基于改进粒子群算法的车间作业调度问题研究[J]. 哈尔滨理工大学学报，2011，16（2）：35.
（编辑：关 毅）
