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

2013-10-15周光辉

制造业自动化 2013年14期

关键词：批量染色体工序

王蕊，周光辉

(1. 西安建筑科技大学理学院，西安 710055；2. 西安交通大学机械制造系统工程国家重点实验室，西安 710049；3. 西安交通大学机械工程学院，西安 710049)

0 引言

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

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

1 存在竞争的任务批量调度问题描述

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

2 非合作博弈批量调度模型

2.1 批量调度策略与成本计算

1) 批量调度策略

将批量启动辅助加工时间与加工时间分开考虑。同种任务不同工件的同一道工序在同一台设备上连续加工，只计算一个辅助加工时间。采用同批次任务在加工部分后立即转向下道工序加工设备处的多次运输策略及无间隙等量分批策略。同子批任务加工连续，以保证在工作量增加不多的情况下提高生产率。

2) 批次划分

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

3)为方便问题描述，采用如下符号和定义：(1) N为任务种类数目，m为设备总数目；(2)JNi为任务的总工件数，JOi为任务的总工序数，JLi为任务的子批批数，为任务的第j道工序；(3)为任务的第b个子批次，lib为任务的子批次的工件数量，为任务的最大运输量；(4)为工序在设备上加工时间，twk为设备与设备间运输时间，为任务加工完毕总运输时间，为工序在设备上准备时间，为子批提前完工时间，为子批次?拖期时间；(5)为任务的子批次工序到达设备时刻，为子批次工序在设备完工时刻，为子批次完工时刻，为设备最早可用时刻，为任务完工时刻，?为任务交货期；(6)为设备加工费率，为任务单位时间运输费率，为任务拖期一次性惩罚金额，为任务单位拖期时间惩罚费率，为任务提前完工单位时间库存费率。基于上述定义，则：

2.2 任务非合作博弈批量调度模型

任务非合作博弈批量调度模型如下式所示：

如果对于每一参与任务，是给定其他参与人选择的策略组合为的情况下的最优策略，即满足式（4）：

并受如下约束：

3 遗传算法

3.1 编码

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

表1 染色体编码示意

3.2 解码

采用SPT调度规则，对染色体后部分p进行解码：

1）设W为后部分染色体长度，。

2）取出p未排工序中第一道工序，计算该工序在所有可选加工设备上的完工时刻。

该工序在可选设备上完工时刻：

设备最早可用时刻：

任务第b个批次完工时刻：

任务完工时刻：

3.3 适应度函数

为实现各任务利益最大化，达到利益均衡目标，设计适应度函数如下：

对于每种任务当满足式（17）时，认为达到工程意义上Nash均衡：

3.4 遗传操作

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

4 实例仿真

4.1 初始条件

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

表2 任务基本工艺信息

表3 任务属性信息

4.2 仿真结果与分析

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

图1 不分批与分批批量调度甘特图

“a/b” 表示同一种制造任务的未分批数据a和分批数据b。任务 - 完工时间分别为、、、、、，总成本分别为、、、、、。在未分批调度中，各任务均拖期，且总成本远高于分批调度。在分批调度中各任务达到Nash均衡后，均满足各任务交货期，且收益相当。由此可见，基于非合作博弈任务分批批量调度方案优于不分批批量调度。