文章快速检索     高级检索
  重庆大学学报  2020, Vol. 43 Issue (3): 1-11  DOI: 10.11835/j.issn.1000-582X.2019.004 RIS(文献管理工具)
0

引用本文 

舒萧, 王时龙, 康玲, 杨波, 杨星星, 邹海旭. 面向云制造的有限资源多任务调度博弈[J]. 重庆大学学报, 2020, 43(3): 1-11. DOI: 10.11835/j.issn.1000-582X.2019.004.
SHU Xiao, WANG Shilong, KANG Ling, YANG Bo, YANG Xingxing, ZOU Haixu. Multi-task scheduling game with limited resources for cloud manufacturing[J]. Journal of Chongqing University, 2020, 43(3): 1-11. DOI: 10.11835/j.issn.1000-582X.2019.004.

基金项目

国家科技支撑计划资助项目(2015BAF02B02);教育部创新团队发展计划资助项目(IRT_15R64)

通信作者

王时龙, 男, 教授, 博士生导师, 主要从事先进制造技术研究, (E-mail)slwang@cqu.edu.cn

作者简介

舒萧(1994-), 男, 硕士研究生, 主要从事云制造研究, (E-mail)1012753923@qq.com

文章历史

收稿日期: 2019-03-31
面向云制造的有限资源多任务调度博弈
舒萧 , 王时龙 , 康玲 , 杨波 , 杨星星 , 邹海旭     
重庆大学 机械传动国家重点实验室, 重庆 400044
摘要: 为解决云制造环境下云服务组合优化调度问题,在深入分析目前优化调度问题存在的难点及研究不足的基础上,提出一种云制造环境下有限资源的多任务调度模型。考虑服务需求者间存在的利益冲突及重要的服务评价指标,以每个服务需求者作为博弈参与者,将每个任务的执行制造路径当作博弈策略,把时间、合格率、成本和服务质量组成的综合服务水平看作博弈支付函数,最终把有限资源的多任务调度问题转变为多个静态非合作博弈问题。在此基础上,将求解纯策略纳什均衡解的过程编制为算法,该算法所得的均衡解为每个任务的最终执行制造路径。实验仿真表明该模型及算法具有可行性及有效性。
关键词: 云制造    多任务调度    有限资源    非合作博弈    纳什均衡    
Multi-task scheduling game with limited resources for cloud manufacturing
SHU Xiao , WANG Shilong , KANG Ling , YANG Bo , YANG Xingxing , ZOU Haixu     
State Key Laboratory of Mechanical Transmission, Chongqing University, Chongqing 400044, P. R. China
Abstract: To solve the cloud service composition optimal-selection (CSCOS) problem in cloud manufacturing (CMfg), based on the deep analysis of the difficulties and shortcomings in current researches, an optimization model for multi-task scheduling with limited resources problem (MLSR) is proposed. Considering the interest conflicts of service demanders and important quality of service (QoS) indicators, the multi-task scheduling problem with limited resources is converted into multiple static non-cooperative game, and the service demander (SD), different execution manufacturing path of each task and comprehensive service level (CSL) are considered as game player, game strategy and game payoff of a game, respectively. On this basis, the process to seek the pure strategy Nash Equilibrium (PSNE) solution is compiled into an algorithm, whose solutions are the final manufacturing execution paths for each task. Finally, simulation results show the feasibility, effectiveness of both the model and algorithm.
Keywords: cloud manufacturing    multi-task scheduling    limited resources    non-cooperative game    Nash Equilibrium    

云制造是一种面向服务、高效低耗和基于知识的网络化智能制造新模式。它融合了现有信息化制造、云计算、物联网、语义Web、高性能计算等先进信息技术,通过对现有网络化制造与服务技术进行延伸和变革,将各类制造资源和制造能力虚拟化、服务化,并进行统一、集中的智能化管理和经营,实现智能化、普适化和高效的共享和协同,通过网络为制造全生命周期过程提供可随时获取的、按需使用、优质廉价、安全可靠的服务[1-3]

云服务的组合优化(CSCOS, cloud service composition optimal-selection)为云制造落地实施的关键技术,目前,绝大多数学者着眼于单制造任务的组合优化研究[4-9],具体的研究方法是把单任务分解为一系列具有逻辑关系的子任务,再将子任务与其对应的候选资源池相匹配(每个候选资源池中均存在多个候选制造资源,即服务需求方(SD, service demander)与服务提供方(SP, service provider)是“一对多”的服务形式),再对每个候选资源进行服务质量(QoS, quality of service)评价,最后采用各种优化算法(混合人工蜂群算法[4]、双层规划[5]、蚁群算法[6]、混合教学算法[7]、混沌控制算法[8]、遗传人工蜂群混合算法[9]等)从候选资源池中选出最优的制造资源提供服务,形成制造执行路径。

此外,还有少数学者对云制造环境下多任务的组合优化问题进行研究。刘卫宁等[10]以单任务的研究为基础,融入多任务多联盟生成问题假设,建立了基于服务质量的多任务云服务组合模型,并采用改进遗传算法对问题进行求解;苏凯凯等[11]采用带精英策略的遗传算法对多任务问题进行求解,并解决了制造服务需求方和云制造服务平台运营方的利益冲突;Liu等[12]提出了一种云制造多任务调度模型,考虑了任务工作负载和基本服务要素,进行了大量的实验仿真,以显示基于不同的工作负载的调度方法的效果。对于多云制造任务调度的研究方法与单任务的研究方法大体相同,SD与SP仍为“一对多”的服务形式。忽略了对于SD与SP之间“多对多”服务形式的研究,即为云制造环境下有限资源的多任务优化调度问题。

研究提出一种面向云制造的有限资源的多任务调度模型(MSLR, multi-task scheduling with limited resources),着眼于解决多个服务需求方对于单个(或多个)云服务同时需求而产生的冲突问题,而博弈论对于解决冲突问题有着天然的优势。服务需求方、每个任务的制造执行路径和综合服务水平被看作是博弈参与者、博弈策略和博弈支付函数,将MSLR问题转化为静态纯策略非合作博弈,并提出了纯策略纳什均衡算法(PSNE, pure strategy Nash Equilibrium algorithm)来解决问题。

1 有限资源多任务调度问题概述

在一个云制造系统中主要由制造服务需求方(SD)、制造资源提供方(SP)及云制造服务平台运营方[1]3个主体组成。SP提供制造服务资源,经由云平台将服务虚拟化、服务化后上传到云端形成资源云池。云服务的组合优化调度问题指的是根据SD提交的不同制造任务,云制造服务平台为其配置合理的制造服务资源或制造资源服务组合,并交由制造资源提供方完成制造任务的过程。云制造讲求分散资源集中使用,而资源的集中是一个相对缓慢的过程,在云制造发展初期会存在多个SD同时需求某服务而产生利益冲突的问题;而当云制造发展到一定程度时,也会存在多个SD对有限的优质资源产生需求的利益冲突问题。笔者提出了面向云制造的有限资源的多任务调度问题,给出以下定义:

定义1 有限资源的多任务调度问题(MSLR):在云制造服务优化调度过程中,能提供的优质服务资源的SP是有限,把多个SD同时需求一个服务或多个服务定义为MSLR。

目前MSLR所存在的难点主要为以下2点:①当多个SD同时需求同一个服务,如何合理分配服务。②当同类多个SD同时提出资源需求,在SP有限时如何安排各个SD的制造过程。为解决以上问题展开研究。

研究采用文献[6]中对调度优化问题中的各对象的定义。分别为物理制造单元(PMU, physical manufacturing unit)、逻辑制造过程(LMP, logical manufacturing process)、逻辑制造任务(LMT, logical manufacturing task)及执行制造路线(EMP, execute manufacturing path)。在多任务优化调度过程中,存在多个LMP,每个LMP又可以分解为多个LMT,由不同的PMU执行每个LMT,进而获得EMP。

面向有限资源的多任务服务优化调度过程如图 1所示。从SP角度出发,制造资源被集中为面向服务的PMU,根据PMU能够独立完成的LMT,将所有的PMU投入不同的物理制造单元组(制造资源候选集)中,以物理制造单元组的形式发布到制造云池中。从SD角度来说,制造任务被抽象为LMP,再将LMP分解为一系列LMT,具有相同任务特性(能被同一PMU加工)的LMT将被投入同一任务池中,制造任务将以任务池的形式发布到云池中。任务池与物理制造单元组的匹配是多任务调度优化问题的基础,接下来则需要从对应的物理制造单元组中为每一LMT选出合理的制造服务以形成EMP。

图 1 MSLR优化过程 Fig. 1 MSLR optimization process
2 有限资源多任务调度数学模型 2.1 模型假设

为了让本模型更加完善,做出以下几个假设:

1) 由毛坯供应所在地(LS)到第一个PMU所在地点的物流时间为2 d,成本为2元/kg;

2) 由最后一个PMU到物流终点LE的物流时间与成本均忽略不计;

3) 工件在加工中的重量损失忽略不计;

4) 每个PMU对不同LMT进行加工需要1 d的准备时间。

2.2 优化目标函数

将物理制造单元PMU表示为

$ {P_{{\rm{PMU}}}}\left( {{L_{{\rm{PMU}}}},{S_{\rm{E}}},P} \right), $ (1)

式中:LPMU表示PMU的位置信息;SE表示PMU参与云制造过程后所获的服务优劣信息;P为合格率,表示提供本次服务的零件合格率信息。

在多任务调度模型中,用GT表示总的制造任务,可由多个单制造任务集表示

$ {G_{\rm{T}}} = \left\{ {{M_1},{M_2}, \cdots ,{M_i}, \cdots ,{M_n}} \right\}, $ (2)

式中,Mi为第i个制造任务,可表示为

$ {M_i}\left( {{L_{\rm{S}}},{L_{\rm{E}}},{Q_{\rm{D}}},{B_{\rm{Q}}},{L_{{\rm{LMP}}}}} \right), $ (3)

式中:LS表示本次服务的物流起始地点(毛坯供应所在地);LE表示本次服务的物流终点(订单交付地点,即SD所在地);QD为订单中零件的数量;BQ为毛坯质量;一个逻辑制造过程LLMPn个逻辑制造任务{LLMT, 1, LLMT, 2, …, LLMT, n}组成,为

$ {L_i} = \left\{ {{L_{{\rm{LMT}},1}}, \cdots ,{L_{{\rm{LMT}},j}}, \cdots ,{L_{{\rm{LMT}},n}}} \right\}, $ (4)

式中,j表示制造任务的逻辑制造先后顺序。在MSLR问题中,每个LMT将会有k个PMU能够提供满足要求的服务,用Pt表示与Li对应的PMU集,Pt为第t个物理制造单元组,为

$ {P_t} = \left\{ {{P_{{\rm{PMU}},1}}\left( {c,q,t} \right), \cdots ,{P_{{\rm{PMU}},k}}\left( {c,q,t} \right)} \right\}, $ (5)

式中,cqt分别表示由PPMU,i完成LLMT, i所承诺的价格、合格率及时间。

为每一LMT选取最优的PMU提供服务,需要对选取QoS评价指标,对PMU进行服务评价。过去很多学者对服务评价的指标进行了研究,笔者采用文献[8]在服务调度优化问题中提出评价指标,即完成时间T、产品质量Q、加工成本C和加工服务水平S,构建面向有限资源的多任务调度模型的优化指标。

2.2.1 完成时间

一个LMT的完成时间T主要包含物流时间TM和制造时间TL。制造时间包含等待时间、准备时间及加工时间等。因此一个制造过程的时间参数可以表示为

$ T = {m_t}\left( {{x_{i,j}}} \right) + {l_t}\left( {{x_{i,j - 1}},{x_{i,j}}} \right), $ (6)

式中:xi, j表示为LLMP, i中的LLMT, j选中的PMU,mt(xi, j)表示由PMU所承诺的完成LLMT, j的制造时间;lt(xi, j-1, xi, j)表示由LLMT, j-1LLMT, j的物流时间。

2.2.2 加工成本

一个制造任务的加工成本C包括了物流成本CM和制造成本CL,为

$ C = {C_{\rm{M}}} + {C_{\rm{L}}} = {Q_{\rm{D}}}\left( {{m_{\rm{c}}}\left( {{x_{i,j}}} \right) + {B_{\rm{Q}}} * {l_{\rm{c}}}\left( {{x_{i,j - 1}},{x_{i,j}}} \right)} \right), $ (7)

式中:mc(xi, j)表示由PMU完成LLMT, j所承诺的制造成本;lc(xi, j-1, xi, j)表示由LLMT, j-1LLMT, j的物流成本。

2.2.3 产品质量

由SP所承诺的产品制造合格率表示产品的质量水平。一个制造任务的产品质量可表示为

$ Q = q\left( {{x_{i,j}}} \right), $ (8)

式中,q(xi, j)表示完成xi, j的PMU所承诺的合格率。

2.2.4 服务优劣

一个制造任务的服务优劣评价可用表示为

$ S = s\left( {{x_{i,j}}} \right), $ (9)

式中,s(xi, j)表示对完成xi, j的PMU的历史服务水平评价。

文中的优化约束主要是在一个LMP中,一个LLMT, j的开始时间Ts应该大于前一个任务LLMT, j-1的完成时间Tc与其物流时间lt之和,数学表达式为

$ {T_{\rm{s}}}\left( {{x_{i,j}}} \right) \ge {T_{\rm{c}}}\left( {{x_{i,j - 1}}} \right) + {l_t}\left( {{x_{i,j - 1}},{x_{i,j}}} \right)。$ (10)
2.3 参数无量纲化处理

上述4个评价参数具有不同的量纲和变化范围,在处理过程中不能对其进行简单的叠加,需要对其进行无量化处理。将以上4个指标分为2类,并采用文献[13]中的方法其进行处理。①效益指标(越大越):QS;②成本型指标(越小越好):TC。无量纲化处理后的结果为

$ {r_Q}\left( X \right) = \frac{{Q\left( X \right) - Q{{\left( X \right)}_{\min }}}}{{Q{{\left( X \right)}_{\max }} - Q{{\left( X \right)}_{\min }}}}, $ (11)
$ {r_{\rm{S}}}\left( X \right) = \frac{{S\left( X \right) - S{{\left( X \right)}_{\min }}}}{{S{{\left( X \right)}_{\max }} - S{{\left( X \right)}_{\min }}}}, $ (12)
$ {r_{\rm{T}}}\left( X \right) = \frac{{T{{\left( X \right)}_{\max }} - T\left( X \right)}}{{T{{\left( X \right)}_{\max }} - T{{\left( X \right)}_{\min }}}}, $ (13)
$ {r_{\rm{C}}}\left( X \right) = \frac{{C{{\left( X \right)}_{\max }} - C\left( X \right)}}{{C{{\left( X \right)}_{\max }} - C{{\left( X \right)}_{\min }}}}。$ (14)

则优化问题的目标函数可定义为

$ f\left( X \right) = {w_{\rm{Q}}}{r_{\rm{Q}}}\left( X \right) + {w_{\rm{S}}}{r_{\rm{S}}}\left( X \right) + {w_{\rm{T}}}{r_{\rm{T}}}\left( X \right) + {w_{\rm{C}}}{r_{\rm{C}}}\left( X \right), $ (15)

式中,X为LMT,wQwSwTwC分别为加工质量、服务水平、加工成本及加工时间的权重系数,且wQ+wS+wT+wC=1。在求解权重系数中最常用的方法是层次分析法,但在实际情况中,各种指标的分布受各服务需求方不同偏好的影响,由层次分析法所得的权重亦不一定为最优的权重分布。不对各权重系数进行推演,采取文献[6]的权重系数为

$ {w_{\rm{Q}}} = 0.4647;{w_{\rm{S}}} = 0.0634;{w_{\rm{T}}} = 0.1791;{w_{\rm{C}}} = 0.2929。$

由此权重系数可以看出:SD最看重的是制造任务的质量水平,其次是资金成本与时间成本,而服务质量则不被看重。

3 有限资源多任务调度博弈

在MSLR问题中,不能只关注每个独立的LMP的最优制造过程,需化解LMT间的利益冲突问题,需协调、安排每个任务的制造过程,最终获得一个相对最优的结果。博弈论解决这种具有冲突特点的问题有突出优势,所以文中采用博弈论来解决MSLR问题。博弈论是数学经济定律,指的是多个博弈者之间通过改变他们各自的博弈策略来获得最大的博弈支付的问题[14]。目前,博弈论在各种工程问题中得到了广泛的应用[15-16]。文献[11]采用博弈论来解决多任务无限资源的优化调度问题,着眼于化解制造服务需求方和云制造服务平台运营方的利益冲突,而文中则侧重于化解多个服务需求方间的利益冲突。博弈论可分为合作博弈和非合作博弈,在合作博弈中博弈者之间可制定一些具有约束力的协议,而非合作博弈则不能。调度博弈问题可以看作是一个N人参与的非合作博弈,同时博弈者之间的信息是完全公开透明的。笔者将服务需求者看作博弈者,服务需求者通过改变制造策略来获得更好的综合服务质量,则不同的制造调度策略即为博弈策略,综合服务质量为博弈支付。可以将该模型看作一个多元数组,为

$ G = \left\{ {N,S,U} \right\}, $ (16)

式中:N为博弈参与者;S为博弈策略;U为博弈支付。

3.1 参与者

在服务调度优化博弈中,SD为追求最优的综合服务质量参与博弈。在算法编制时,把SD的目标赋予物理制造单元组(物理制造单元组中的所有PMU均想为SD提供最优的服务质量),将Pt中的PMU作为博弈参与者。博弈开始时,将有n个PMU,这些物理制造单元将被分到t个物理制造单元组中,每个小组里的PMU在一场博弈中被视作服务候选者。如果某属于物理制造单元组Pt={PPMU, q, PPMU, p, …}的某一PMU可完成加工任务,那么Pt中的所有PMU视为参与第h阶段的博弈。定义博弈者为Nth={PPMU, q, PPMU, p, …},其中Nth表示第h个博弈阶段与Pt对应的博弈参与者集。

3.2 博弈策略

在MSLR博弈开始时, 建立与Pt相匹配的任务池TTP={TTP1, TTP2, …, TTPn},把属于不同逻辑制造过程的第一个逻辑制造任务投入相应的任务池中。当制造过程的某个逻辑任务已在执行,则在下一博弈阶段把此逻辑制造过程的下一逻辑任务投入相应任务池中继续博弈,直到完成整个制造过程。如果在博弈阶段hPt为一组博弈参与者,那可将与Pt对应的任务池看作是博弈策略,即Sth=tpth,其中Sth表示h阶段中相对于Pt的博弈策略,tpth表示h阶段中相对于Pt的任务池。当博弈参与者的数量多于博弈策略时,可在博弈策略集中加入空策略Φ(博弈支付为0的制造任务),以保证博弈的正常进行。在调度优化博弈中,每个SD通过采用合理的加工序列来获得最大化综合服务水平,同时将所有其他博弈者的综合服务水平最小化。因此,博弈收益不仅仅与自身策略有关,还与其他博弈者的博弈策略相关。

3.3 博弈支付

博弈支付是博弈者在博弈阶段h中所获得的红利,可将其看作博弈策略的指示器,博弈者采用最优策略来获得最大的博弈支付。博弈支付即为任务需求方在第h博弈阶段中所获的综合服务水平,为

$ U_k^h(s) = f(X), $ (17)

式中,Ukh(s)表示第h个博弈阶段第k个博弈参与者的博弈支付。

解决云制造环境下有限资源多任务调度博弈问题,其关键点在于将任务池看作是博弈策略集,将综合服务水平看作是博弈支付。在整个博弈过程中,将要经过H个博弈阶段,来完成任务池中所有制造过程。初始博弈阶段为h=1,当所有物理制造单元组中至少有一个PMU完成制造任务时,博弈则进入下个阶段。

3.4 纳什均衡

纳什均衡(NE)被广泛应用于N人非合作博弈中。纳什均衡是所有博弈策略中的均衡点,处于均衡状态时每个博弈参与者不能通过私自修改自身的博弈策略来获得更大的博弈支付,即此时为博弈参与者的相对最优策略。当参与博弈的博弈者数量有限时,此博弈则至少存在一个均衡点。多任务调度博弈可看作是N人静态纯策略博弈,优化求解过程即为均衡点的寻解过程,参考文献[3]给出了N人静态纯策略NE求解方法。

定义  设在n人有限纯策略静态博弈中,第k个博弈者的收益函数为Uk(s), sS。当存在:s*= A1*j1, A2*j2, …, An*jn =(sk-1*, Ak*jk, sk+1*),使得Ui(s*)=Uk(sk-1*, Ak*jk, sk+1*)≥ Uk(sk-1*, Aik, sk+1*), ∀AikSi, i=1, 2, …, n,则称s*n人有限纯策略静态博弈的NE。

Tk(sk-1, sk+1)={sk-1, Akjl, sk+1|maxAkjlSkUk(sk-1, Akl, sk+1)}, k=1, 2, …, n$\bigcap\limits_{k=1}^{n}{{{T}_{k}}}$则为一个纯策略静态博弈的NE。由于博弈参与者的数量有限,满足均衡解存在条件,所以:$\bigcap\limits_{k=1}^{n}{{{T}_{k}}\ne \Phi }$,即每次博弈都至少存在一个NE。当有多个均衡解时,则每个解的博弈支付相当,文中选取使制造时间更为合理的解。

3.5 纯策略纳什均衡算法(PSNE)

为了方便计算NE,将NE求解过程采用MTLAB R2016a编制算法程序,算法流程如图 2所示。

图 2 纯策略纳什均衡算法流程图 Fig. 2 PSNE algorithm flow chart

步骤1  记录博弈阶段h=1;

步骤2  获取本阶段所有的物理制造单元PMU及所有的任务池;

步骤3  划分物理制造单元组Pt,将物理制造单元组作为博弈参与者;

步骤4  获取所有可行的制造过程,形成任务池,将任务池看作是博弈策略集;并与Pt相匹配;

步骤5  博弈参与者与博弈策略相匹配;

步骤6  建立所有博弈策略的博弈支付函数Ukh(s);

步骤7  计算纯策略集:Tkh(sk-1, sk+1, k=1, 2, …, n,记录下每个Tkh;

步骤8  计算$\bigcap\limits_{k=1}^{{{n}_{t}}}{T_{h}^{k}}$,记录下本阶段的博弈均衡解;

步骤9  博弈阶段加1,循环步骤2~8直到完成所有阶段的博弈。

4 算例分析 4.1 初始条件

本算例中包括6个PMU(如表 1所示),随机的分布在6个城市,共有3个物理制造单元组分别为:P1={PPMU1, PPMU2},P2={PPMU3, PPMU4},P3={PPMU5, PPMU6}。每个城市之间的物流成本如表 2所示,数据由国内的某物流商提供。本模型中总共有9个逻辑制造过程,每个过程分为3个逻辑制造任务,任务的详细信息由表 3给出,表中T11PPMU1列所对应的数据3/0.90/209表示由PPMU1加工完成T11所需的加工时间为3 d、合格率为0.90和加工成本为209元/件。表 3中时间、合格率和报价数据均在一定范围内,由正太分布生成。表 4为加工毛坯零件的质量和数量。

表 1 PMU信息 Table 1 PMU information
表 2 物流时间与成本 Table 2 Logistics time and cost  
表 3 制造时间(天)/合格率/成本(元) Table 3 Manufacturing time (days) / pass rate / cost (yuan)
表 4 毛坯质量及数量 Table 4 Blank quality and quantity
4.2 结果分析

利用PSNE算法得到的结果是一个考虑了时间、合格率、成本和服务质量综合优度的结果,不仅是时间最优结果。而对于一般的调度问题,甘特图能够直观地表现调度结果。如图 3所示,图中横轴为时间(d),纵轴为PMU,总的调度时间为39 d。下面对博弈过程进行简要说明,在第一博弈阶段中,物理制造单元组P1={PPMU1, PPMU2}在所对应的任务池为tp11={T11, T71, T81},经过博弈后所得到的NE为{T71, T81}与{T81, T71},而{T81, T71}在本次博弈中的所需的制造时间更短,被选定为本次博弈结果,即PPMU1加工完成T81PPMU2加工完成T71。当博弈进入下一阶段时则把T82T72分别投入相应的任务池中,而T11则投入tp12中。

图 3 多任务调度博弈结果 Fig. 3 Multi-task scheduling game result

图 3的结果中,逻辑制造过程T1T9在与其他LMP匹配中所获得的综合服务水平低于其他制造过程,导致了T1T9的制造延后。在实际情况中,某些任务具有完成时间限制,文中把T1T9加入优先制造序列,即每个博弈阶段优先为优先制造序列中的制造过程寻找服务,再对其余的制造过程进行博弈,优化结果如图 4所示,总的调度时间为43 d。在T1T9加入优先制造序列情况下,为保证所在制造任务所获得综合服务水平,在调度时间上有所牺牲。

图 4 优先制造序列 Fig. 4 Priority manufacturing sequence

图 5表示所有逻辑制造过程的综合服务水平对比图,虚线表示在正常调度结果下所有LMP获得综合服务水平,实线表示优先制造序列下所有LMP获得的综合服务水平。由图 5可看出,将T1T9加入优先制造序列会使得,T3T5T7T8所获得的综合服务水平降低,T1T6T9所获得的综合服务水平保持不变,T2T4所获得的综合服务水平略微增加,所有逻辑制造过程获得的总综合服务水平下降了3.42%。文中经过多次实验总结如下规律,将某逻辑制造过程加入优先制造序列,会使得所有的逻辑制造过程获得的总综合服务水平下降。

图 5 综合服务水平对比图 Fig. 5 Comprehensive service level comparison chart

为了评估博弈调度算法的优越性,将文中的调度策略与以下已提出的调出策略进行比较,例如由张超勇等[17]提出的改进非支配遗传算法调度策略(NSGA-Ⅱ)及由He等[18]提出的右移调度策略(Right Shift)。结果对比如图 6所示,3种调度策略所获得的总综合服务水平如表 5所示。

图 6 多种方法调度结果 Fig. 6 Multiple methods scheduling results
表 5 总综合服务水平 Table 5 Total comprehensive service level

图 6可以得出在调度时间上:tNSGA-ⅡtPSNEtRightShift,即由非支配遗传算法调出策略得出的调度时间最优。由表 5可以得出所有任务获得的总综合服务水平对比为:tNSGA-ⅡtRightShifttPSNE,由PSNE计算获得的解为最优综合服务水平解。虽然NSGA-Ⅱ在调度时间上最优,但却牺牲了其他指标的收益,所获得的总综合服务水平最低。而文中所提出的博弈调度法所获得总综合服务水平最高,表明了该方法的优越性。

5 结论

提出了面向多任务的有限资源的优化调度模型,将以往对于多任务资源优化调度中SD与SP“一对多”服务模式转化为本文的“多对多”“多对一”形式。采用了非合作博弈的方法,将服务需求方作为博弈参与者,以每个任务的制造执行路径作为博弈策略,把时间、合格率、成本和服务组成的综合服务水平作为博弈支付函数,建立一种多任务资源优化调度的博弈决策数学模型。采用PSNE算法获得纯策略非合作博弈的纳什均衡解,均衡解即为最终的制造执行路径。算例论证结果表明文中提出的面向多任务的有限资源优化调度博弈法能够有效地解决MSLR问题,合理地化解了各SD间的利益冲突,算例论证了该模型及算法的有效性及可行性。

参考文献
[1]
李伯虎, 张霖, 王时龙, 等. 云制造:面向服务的网络化制造新模式[J]. 计算机集成制造系统, 2010, 16(1): 1-7, 16.
LI Bohu, ZHANG Lin, WANG Shilong, et al. Cloud manufacturing:a new service-oriented networked manufacturing model[J]. Computer Integrated Manufacturing Systems, 2010, 16(1): 1-7, 16. (in Chinese)
[2]
李伯虎, 张霖, 任磊, 等. 再论云制造[J]. 计算机集成制造系统, 2011, 17(3): 449-457.
LI Bohu, ZHANG Lin, REN Lei, et al. Further discussion on cloud manufacturing[J]. Computer Integrated Manufacturing Systems, 2011, 17(3): 449-457. (in Chinese)
[3]
李正龙. 一种n人静态博弈纯策略纳什均衡存在性判别法[J]. 运筹与管理, 2004, 13(1): 33-37.
LI Zhenglong. An existence distinguishing method for pure strategy Nash equilibrium existence in n-person static games[J]. Operations Research and Management Science, 2004, 13(1): 33-37. (in Chinese) DOI:10.3969/j.issn.1007-3221.2004.01.007
[4]
Zhou J J, Yao X F. Multi-objective hybrid artificial bee colony algorithm enhanced with Lévy flight and self-adaption for cloud manufacturing service composition[J]. Applied Intelligence, 2017, 47(3): 721-742. DOI:10.1007/s10489-017-0927-y
[5]
苏凯凯, 徐文胜, 李建勇, 等. 云制造环境下基于双层规划的资源优化配置方法[J]. 计算机集成制造系统, 2015, 21(7): 1941-1952.
SU Kaikai, XU Wensheng, LI Jianyong, et al. Manufacturing resource allocation method based on bi-level programming in cloud manufacturing[J]. Computer Integrated Manufacturing Systems, 2015, 21(7): 1941-1952. (in Chinese)
[6]
Cao Y, Wang S L, Kang L, et al. A TQCS-based service selection and scheduling strategy in cloud manufacturing[J]. International Journal of Advanced Manufacturing Technology, 2016, 82(1-4): 235-251. DOI:10.1007/s00170-015-7350-5
[7]
Zhou J, Yao X. Hybrid teaching-learning-based optimization of correlation-aware service composition in cloud manufacturing[J]. International Journal of Advanced Manufacturing Technology, 2017, 1-19.
[8]
Huang B Q, Li C H, Tao F. A chaos control optimal algorithm for QoS-based service composition selection in cloud manufacturing system[J]. Enterprise Information Systems, 2014, 8(4): 445-463. DOI:10.1080/17517575.2013.792396
[9]
Xue X, Wang S F, Lu B Y. Manufacturing service composition method based on networked collaboration mode[J]. Journal of Network and Computer Applications, 2016, 59: 28-38. DOI:10.1016/j.jnca.2015.05.003
[10]
刘卫宁, 刘波, 孙棣华. 面向多任务的制造云服务组合[J]. 计算机集成制造系统, 2013, 19(1): 199-209.
LIU Weining, LIU Bo, SUN Dihua, et al. Multi-task oriented service composition in cloud manufacturing[J]. Computer Integrated Manufacturing Systems, 2013, 19(1): 199-209. (in Chinese)
[11]
苏凯凯, 徐文胜, 李建勇. 云制造环境下基于非合作博弈的资源优化配置方法[J]. 计算机集成制造系统, 2015, 21(8): 2228-2239.
SU Kaikai, XU Wensheng, LI Jianyong. Manufacturing resource allocation method based on non-cooperative game in cloud manufacturing[J]. Computer Integrated Manufacturing Systems, 2015, 21(8): 2228-2239. (in Chinese)
[12]
Liu Y K, Xu X, Zhang L, et al. Workload-based multi-task scheduling in cloud manufacturing[J]. Robotics and Computer-Integrated Manufacturing, 2017, 45: 3-20. DOI:10.1016/j.rcim.2016.09.008
[13]
马文龙, 王铮, 赵燕伟, 等. 基于改进蚁群算法的制造云服务组合优化[J]. 计算机集成制造系统, 2016, 22(1): 113-121.
MA Wenlong, WANG Zheng, ZHAO Yanwei, et al. Optimizing services composition in cloud manufacturing based on improved ant colony algorithm[J]. Computer Integrated Manufacturing Systems, 2016, 22(1): 113-121. (in Chinese)
[14]
Rasmusen E. Games and information:an introduction to games theory[J]. The Economic Journal, 1989, 99(397): 864. DOI:10.2307/2233782
[15]
Nawa N E. Agents that acquire negotiation strategies using a game theoretic learning theory[J]. International Journal of Intelligent Systems, 2006, 21(1): 5-39. DOI:10.1002/int.20119
[16]
Marco G D, Romaniello M. Beliefs correspondences and equilibria in ambiguous games[J]. International Journal of Intelligent Systems, 2012, 27(2): 86-107. DOI:10.1002/int.21515
[17]
张超勇, 董星, 王晓娟, 等. 基于改进非支配排序遗传算法的多目标柔性作业车间调度[J]. 机械工程学报, 2010, 46(11): 156-164.
ZHANG Chaoyong, DONG Xing, WANG Xiaojuan, et al. Improved NSGA-Ⅱ for the multi-objective flexible job-shop scheduling problem[J]. Journal of Mechanical Engineering, 2010, 46(11): 156-164. (in Chinese)
[18]
He W, Sun D H. Scheduling flexible job shop problem subject to machine breakdown with route changing and right-shift strategies[J]. International Journal of Advanced Manufacturing Technology, 2013, 66(1-4): 501-514. DOI:10.1007/s00170-012-4344-4