基于柔性job shop的集成化工艺规划与生产调度

摘 要：为有效利用车间资源管理系统，在研究基于柔性job shop的工艺规划与生产调度集成问题的基础上，提出基于工艺规划的多agent生产调度系统（Flexible process planning based Multi-Agent production Scheduling System，FMASS）. 该系统综合考虑零件的工艺规划柔性和车间生产柔性，采用混合建模的方法建立4类agent及其行动规则，通过各类agent相互之间的协商与竞争得到零件的工艺规划和工序，从而实现工艺规划与车间调度系统的集成.对工艺规划与车间调度的集成算法进行性能测试，结果表明该系统具有一定的预见性和全局优化能力，且柔性和对动态变化的适应性较好.

关键词：柔性job shop； 集成； 工艺规划； 多agent

中图分类号：TH165； TP391.52文献标志码：A

0 引 言

目前车间调度问题研究正向着集成化、多目标化、动态实用化和高度次优化方向发展. 在全球制造新形势下，探索车间计划与调度问题的集成求解方法是车间生产调度问题的重要发展方向之一.

在传统的job shop调度问题研究中,每个工件具有唯一确定的加工工艺路线，并且工件的每道工序只能在确定的机床上加工，没有考虑工艺规划的灵活性.当今的很多制造系统在工艺规划方面变得日益灵活,每个工件具有多个可供选择的工艺规划；同时,工艺规划与生产调度之间联系紧密，生产调度的优化依赖于工艺规划的结果.因此，工艺规划和生产调度的集成对于制造资源的有效利用显得非常重要.［1］本文设计实现基于工艺路线的多agent生产调度系统，采用多agent协商竞标方法，根据零件工艺网络，在协商中决定零件的加工次序和开始加工时间，初步实现工艺规划与车间生产调度的集成.

1 问题描述与建模

1.1 问题描述

所研究的柔性job shop 调度问题可描述为：1个加工系统有m台机器，要加工n种工件；每个工件包含1道或多道工序；每道工序可以在不同的设备上加工.［2］调度的目标是为每个工件的每道工序选择合适的加工设备和加工开始时间，使系统的设备负载率和工件加工时间等性能指标达到最优.

此外，在加工过程中还要满足以下约束条件：(1)同一时刻同一台机器只能加工1个零件；(2)每个工件在某一时刻只能在1台机器上加工，操作不能被中途中断；(3)同一个工件的工序之间有先后约束，不同工件的工序之间没有先后约束.

1.2 系统建模

所研究的多agent生产调度系统(Flexible process planning based Multi-Agent production Scheduling System,FMASS)采用混合建模的方法将生产调度中的机器、工具和零件等物理实体以及管理、调度等逻辑实体分解成4类agent：资源agent (Resource Agent, RA)，代表1台设备和1个工具等能够提供服务的资源；任务agent(Task Agent, TA)，代表1个或1组要申请服务的工件；任务管理agent(Task Management Agent, TMA)；资源管理agent(Resource Management Agent, RMA).采用混合型体系结构将该系统分为两大子系统：任务子系统和资源子系统.前者包括TMA和TA，后者包括RMA 和RA.TMA和RMA处于高层，TA和RA处于低层［3］，见图1.

图 1 FMASS系统架构

FMASS的层次架构使得高层agent和低层agent之间存在交互关系.TMA 负责创建和管理TA；RMA负责创建和管理RA.管理agent处于高层，从宏观角度评价调度结果并作出决策，具有全局优化功能.

FMASS还具有异构性，在TA和RA之间需要进行类似合同网的协商.RA和TA之间在协商时保持自治，当1个agent出现问题时，并不影响其他agent.该结构同时支持纵向和横向协商，使层次结构和异构结构的优点一并发挥出来.

2 FMASS的协商机制

2.1 协商机制

FMASS采用混合合同网协商机制，具体协商协议见图2.图中描述每类agent的内部状态转换和处理过程，以及通过各类agent之间的合作［4］完成协商的具体过程.图中圆角矩形表示agent的状态，矩形表示agent的处理过程.下面详细介绍某批工件从进入系统到完成加工的协商过程：(1)系统初始化.对所有RA进行初始化，RA将自己的状态信息注册给RMA，RMA统计所有RA的注册信息后，发出所有RA已经就绪的通知，使RA进入等待投标请求(Wait_RFB)状态，等待TA的加工请求.(2)任务到达后，TMA根据任务产生规则创建TA，对TA进行初始化并启动，TA进入等待加工开始状态(Wait_START).(3)当调度机制调度到该TA时，TA根据工艺选择算法选择当前可加工的工序，并向RA发送投标邀请(Request for Bid，RFB)，进入等待标书状态(Wait_BID)，等待RA出价.若在规定时间内没有收到任何标书，则重新协商.(4)收到投标请求的RA根据任务选择算法，从等待队列中选择任务为其分配资源.RA计算出标价，并将可能的建议(包括开始时间、结束时间和标价)发送给所选择的TA.进入等待录用状态(Wait_OFFER)，等待TA 的回复或者超时.(5)TA收集所有投标信息，并根据标书评价函数选择1个最好的，向RA发送确认信息的同时向其他RA发送拒绝信息.TA判断该任务是否已经加工完成，如果完成则终止，否则回到等待开始状态，从第(3)步开始继续下一道工序的安排.

图 2 混合合同网协商协议

2.2 协商中相关的决策函数和算法设计

2.2.1 TA的工序选择算法

工件的工艺路线在参与调度时尚未选定，因此调度时需要通过工序选择算法选择［5］，具体步骤如下:(1)生成1个初始可用工序集，该工序集中的元素都没有前驱.(2)如果可用集为空，中止；否则转第(3)步.(3)把可用集中的所有工序投放到协商中去，向相应的RA发送投标邀请.(4)从可用集中移除第（3）步选取的操作,并将此操作后所有可以开始的后续操作添加到可用集中，返回到第（2）步.

2.2.2 RA的任务选择算法

1个零件有多种加工方法，每个加工操作j可以在多台机器上执行.在提出的系统中，agent通过协商选择1台特定机器执行1个特定操作.RA对所要加工工序的选择基于1个假想代价［6］

根据以上流通函数，具有较低临界率(较高优先级)或较长处理时间的工序将会导致较高的代价.代价越小，被选中的几率越大.

2.2.3 TA的标书评价函数

TA接收到几个RA的投标后，会根据下面的标书评价函数评价所有标书，并选择1个最好的.

资源评价函数oijk考虑操作的等待时间、延期时间和标价因素.权值可随着调度目标的不同作出相应修改.

3 试验仿真

为验证所提出的基于多工艺路线的FMASS的可行性和有效性，对6台设备和16个零件任务的调度问题进行仿真实验，其中每个零件对应1个工艺网络.初始数据见表1.任务运行情况甘特图和设备分配甘特图见图3和4.从甘特图的调度结果可以直观地看出：系统的资源利用率很高,同类资源的负载也接衡，假如没有瓶颈资源，所有任务均可按时完成.任务在设备上的安排也十分紧密，设备利用率很高，任务的各道工序依据优先顺序在设备上加工，这说明该仿真系统可以完成调度系统的基本目标.

4 结 论

设计的工艺路线选择与车间调度相结合的车间管理系统，运用多agent建模方法建立工艺规划与车间调度集成的多agent生产调度系统FMASS，提出多agent的体系结构和协商机制，建立agent行动规则.该系统具有一定的预见性和全局优化性能,同时还具有柔性和对动态变化的适应性.

参考文献：

［1］ WONG T N, LEUNG C W, MAK K L. Dynamic shop floor scheduling in multi-agent manufacturing systems［J］. Expert Syst Applications, 2006, 31(3): 486-494.

［2］ KIM Y K, PARK K, KO J. A symbiotic evolutionary algorithm for the integration of process planning and job shop scheduling［J］. Comput Operations Res, 2003, 30(8): 1151-1171.

［3］ ZHU H, TANG W S. Job shop scheduling problem with continuous stochastic processing time［J］. Syst Eng Electron, 2007, 29(5): 759-763.

［4］ 田颖, 江平宇, 周光辉, 等. 基于遗传算法的工艺规划与调度集成方法［J］. 西安交通大学学报, 2006, 40(9): 1 041-1 044.

［5］ CHEN K J, JI P. A genetic algorithm for Dynamic Advanced Planning and Scheduling (DAPS) with a frozen interval［J］. Expert Syst Applications, 2007, 33(4): 1 004-1 010.