基于非合作博弈批量调度优化

本资料包含pdf文件1个，下载需要1积分

制造车间任务批量调度问题需要在批次划分基础上进行工序排序。源于不同客户的加工任务之间存在竞争关系，各客户都希望 自身利益最大化，同时缩小其他客户任务利益n0。

本文基于博弈论 ，建立制造车间任务非合作博弈批量调度模型，将存在竞争任务批量调度问题求解就转化为寻求非合作博弈模型Nash均衡点。为实现该模型Nash均衡点有效求解，制定批量调度策略，并设计相应遗传算法进行解算。

1 存在竞争的任务批量调度问题描述存在竞争的车间任务批量调度问题可描述为：在某车间中，有m台设备，N种待加工任务，不同种类任务之间存在竞争关系，每种任务批量到来且包含多道工序，任务调度受设备资源限制与总成本影响。车间任务批量调度目标是确定该车间设备上的工序加工顺序和开工时间，在满足约束条件的同时，使得各任务满足交货期且成本最校同时设定如下假设条件：1)工序处于加工状态时不能被中断；2)所有任务机会均等，工件之间无先后约束；3)各任务辅助加工、加工时间已知；4)任务在设备间运输时间确定。

2 非合作博弈批量调度模型2.1批量调度策略与成本计算1)批量调度策略将批量启动辅助加工时间与加工时间分开考虑。同种任务不同工件的同-道工序在同-台设备上连续加工，只计算-个辅助加工时间。采用同批次任务在加工部分后立即转向下道工序加工设备处的多次运输策略及无间隙等量分批策略。

同子批任务加工连续，以保证在工作量增加不多的情况下提高生产率。

2)批次划分依据等量分批策略，当某任务工件总数量小于任务最大运输量二倍时 ，该任务不分批；反之，需要分批。

3)为方便问题描述，采用如下符号和定义：(1)N为任务种类数目，m为设备总数目；(2)a'Ni为任务 的总工件数 ， 为任务 的总工序数，为任务 的子批批数，. ，为任务 的第j道工序；(3) L油为任务 的第b个子批次，，f6为任务的子批次厶， 的工件数量，， 为任务 的最大运输量；(4) 为工序 ，在设备 上加工时间，为设备 与设备 间运输时间，t 为任务 加工完毕总运输时间，f 为工序.，在设备 上准备时间，屹为子批厶 提前完工时间，f，为子批次厶， 拖期时间；(5) 为任务 的子批次厶，工序，到达设备 时刻， 为子批次厶。 工序 ，在设备. 完工时刻， 为子批次三f， 完工时刻，为设备 最早可用时刻 ， ，为任务 完工时刻， 为任务 交货期；(6)rk为设备 加工费率， 为任务 单位时间运输费率，a 为任务拖期-次性惩佛额， 为任务 单位拖期时间惩罚费率， 为任务 提前完工单位时间库存费敢稿日啊：2013-05-10基金项目：国家自然科学基金资助项目 (51175414)；教育部新世纪优秀人才支持计划 (NCET-12-0452)作者简介：王蕊 (1983-)，女，陕西西安人，助教，硕士，研究方向为车间智能生产与控制。

16 第35卷 第7期 2013-07(下)务l造 匐 化率。基于上述定义，则：JN，∑，f6 (1) JL记ceil表示求整，rein表示求余，random表示随机选取-个整数，厶cit(JN，/t[)，Rir - ， t)。如果厶<2，则儿 1，li ；如 果 厶 2 ， 则 random[1，Lf ，ceil(JNJJLf)rem(JN，/JG)。

4)任务 总成本计算任务 总成本由加工成本、运输成本、拖期惩罚/提前库存成本3部分组成。如果任务 子批Lf'b工 序 ，未 加工 需 要调 度 ， 1，否则 0。记 ceil(16/， )，R rem(i6/l )，如果R 0，则 0；反之， 1。f 表示子批 工序 ，，从设备 到设备 运输时间。假设任务 拖期惩罚和提前完工库存费用分别是拖期时间和提前时间的线性函数，则任务 总成本：cf∑∑( )，；，∑∑[ 劈( ) ， rimax(O，巧-叫 (2) 。台 max(o， -巧) I2.2任务非合作博弈批量调度模型任务非合作博弈批量调度模型如下式所示：G：(J， ， ) f31其 中，1)J为参与人 (加工任务 )集 ，记J： ， ， )；2) 为 的可行方案 (对应于可延工设备)集， 为 某-策略，S ∈ ，M为面向任务集合的所有可延工设备的集合，记M( ， ，，厂刖)，l$ls， M且M；Sl x$2×.·xSu：3) 为 的收益函数，UlC 。

如果对于每-参与任务 ， 是给定其他参与人选择的策略组合为s 的情况下的最优策略，即满足式 (4)：( ，s： ) ( ，s： )，V ∈ (4)并受如下约束：1)I≥ (5)- - (6)， (7)则s(Si，s： )为该博弈的-个Nash均衡解。

3 遗传算法3.1编码染色体编码方式如表1所示，染色体前部分字符表示各种类任务所对应予批批数。染色体后部分表示所有子批工序排序，每-基因用 任务编号，-c批次序号”表示。同-批次同-工序在-台设备上连续加工，看作-道子批大工序。任务某子批基因在染色体中出现的次序表示该基因所代表的任务子批的工序。

表1 染色体编码示意，2 子批工序编码2 I I 1 2 1 I I 1 2 1 2 2 13.2解码采用S 同度规则，对染色体后部分p进行解码：1)设W为后部分染色体长度，U1。

2)取出p未排工序中第-道工序，计算该工序在所有可延工设备上的完工时刻。

若该工序为子批第-道工序，则 0；否则，设该工序相邻上道工序在设备 上加工，计算如下：若lit， ，则加工完本子批所有工件该道工序后送往下道工序相应设备。

n眦l ，磁1) J%l (川 (8)若 > ，则加工完子本批次中-个运输批量任务后立即送往下道工序相应设备：当 ( -1) ≤ ， m ax[ ，磁川 tiP(j-1) (9)当ti(j-)m>tijk， ( (，1) - ) 、该工序在可选设备 上完工时刻：max ， J缘 (11)当设备 上前-道工序与本道工序相同时，缘0；反之，f ≠0。

3)选取最早完成该工序的加工设备，记该设备为 ，则该工序最早完工时刻：% min7 (12)设备 最早可用时刻： (13)任务 第b个批次完工时刻： m ) (14)任务 完工时刻：max ) (15)4)U，当 ，重复步骤 2)、3)；当U> ，终止解码。

第35卷 第7期 2013-07(下) [171务I 訇 似3.3适应度函数为实现各任务利益最大化，达到利益均衡目标，设计适应度函数如下：F ( ，u ，， )T - J√喜(式中： 为任务 第k代收益值；0 为任务f理想收益值，来源于假定车间仅存在任务 时总成本C 最小时的效益值，通过遗传算法求解。

对于每种任务 当满足式 (17)时，认为达到工程意义上Nash均衡：( - f) 薯f (17)其中，芎 为用以确定求解Nash均衡点的阈值。在本文中，令号 2- Ⅳ。

3.4遗传操作选择操作采用比例选择法，染色体被选中的概率与适应都成正比叉操作对染色体前后两部分分别进行：前部分采用两点交叉法，对被交叉的染色体后部分进行修复；后部分采用文献4集合交叉法。变异操作抑前后两部分进行：前部分根据各任务批次划分过程，在其可选子批批数中随机选取-个子批数，并对染色体后部分进行修复；后部分采用反转变异法。

4 实例仿真4.1初始条件假定有6位客户向车间提交了6种不同种类批量加工任务，每种任务包含30个工件，该车间包含6台设备。每位客户都希望自己所提交的任务利益最高并且尽量使得其它客户利益最低。表2、表3列出了任务、设备相关信息。表2中圆括弧内数字为任务工序编号，方括弧为任务工序在相应可选加工设备上的加工时间。所有工序辅助加工时间均为1，设备间运输时间均为2，6台设备加工费率分别为13、12、14、14、11、15。

表2 任务基本工艺信息K181 第35卷 第7期 2013-07(下)表3 任务属性信息j L J 3 j J， j4 6 5 5 5 4口： 26 24 29 29 29 267 8 6 6 9 7- 1 3 1 2 2 26 4 6 5 5 61000 950 850 1050 1050 10004.2仿真结果与分析仿真结果如图1所示，上方甘特图为不分批批量调度结果，下方甘特图为分批批量调度结果。

甘特图中每-长方条代表某种任务某-批次某道工序排序，其上方数字自上而下分别表示该长方条所代表的任务、批次、工序编号。由图1可见，不分批调度设备处于空闲等待状态较多，各任务完工时间较晚，分批调度设备利用率高，任务完工时间明显早于未分批任务。

图1 不分批与分批批量调度甘特图a/b” 表示同-种制造任务的未分批数据a和 分批 数 据b。任务 - 完 工 时 间分 别为1 183/912、 l 122/987、 1089/701 1299/914、1088/937 、 1240/941 ， 总 成 本 分 别 为8347348978、 84510/52036 、 7909255143、915l2/59526、 59305/45190、 86248/45550。

在未分批调度中，各任务均拖期，且总成本远高于分批调度。在分批调度中各任务达到Nash均衡后，均满足各任务交货期，且收益相当。由此可见，基于非合作博弈任务分批批量调度方案优于不分批批量调度。

下转第33页参l 匐 化表10 候选云服务QoS集合评价值计算结果从表l0输 出的结果可以看出，候选云服务S 10QoS综合评价值最高，S6的QoS综合评价值最低 。

4 结束语在云制造服务平台中，云服务QoS综合评价对云服务方案优选以及云服务调度等问题都具有重要意义。本文通过研究云制造服务平台特性，提出基于制造资源特性和网络服务特性的云服务QoS综合评价指标体系。然后针对云制造平台的实际情况以及云服务QoS评价指标体系的特点，提出了基于多元统计主成分分析法的候选云服务QoS综合评价算法。在评价方法中充分考虑了评价指标的正、逆特性，以及云服务评价历史数据的时效性对评价结果的影响等因素，使得综合评价结果更有效。

当然，本文也存在很多有待完善之处，在以后的研究中会考虑候选云服务较少时的评价方法；以及对候选云服务QoS评价指标的差异化评价方法。