基于多Agent的柔性作业车间调度研究

潘 颖， 孙 伟， 马 跃， 马 沁 怡

（1.大连理工大学 机械工程学院，辽宁 大连 116024；2.大连海洋大学 机械学院，辽宁 大连 116023）

0 引 言

近年来，具有多目标优化的柔性作业车间调度问题（flexible job－shop scheduling problem，简称FJSP）成为研究的热点[1].在实际调度过程中，需要综合考虑生产的各个环节和因素，对多个目标进行分析决策，而通常这些目标之间又是相互冲突的.与传统的作业车间调度比较，FJSP是传统 作 业 车 间 调 度 问 题 （job－shop scheduling problem，JSP）的扩展，是更复杂的 NP－Hard问题[2]，其任务中的每道工序可在多台机床上进行，并且在不同的机床上所需时间不同.FJSP减少了机器约束，扩大了可行解的搜索范围，增加了问题的难度.因此，FJSP除了要解决JSP中的确定加工顺序外，还要解决某工序由哪台机床进行的问题，因而求解更加复杂.

近年来，多目标FJSP的研究出现了很多新的智能优化方法[3～7]，使得多目标FJSP的研究方法向多元化方向发展.其中，遗传算法利用生物进化机制，在一个较大的初始解空间中通过优胜劣汰的方法进行优化求解，具有寻优能力强、计算速度快、原理简单、鲁棒性好、通用性强、不受限制性条件的约束，具有隐含并行性和全局解空间搜索能力的特点，因此，在生产调度领域得到广泛应用，用遗传算法解决FJSP近年也取得了丰硕的成果[8].

同时，多Agent系统（MAS）由于其本身的分散自治性、网络合作性、结构开放性、智能性等特点，也已成为调度研究领域的前沿和热点[9].

针对多目标FJSP的特点，本文提出一种基于多Agent的多目标柔性作业车间调度方法，运用MAS对柔性车间生产调度过程建模，其中特别构建策略Agent来实现调度及生产上的实时调控，并在策略Agent中封装改进的遗传算法，最后通过实例对所提的调度方法进行验证.

1 基于MAS的调度模型

1.1 问题描述

设生产系统有n个工件，每个工件有p个工序.各工序均可在m台设备中的一台或多台上进行.由于各设备的性能、特点不同，某设备k对各个工序Oij的加工时间为Tkij（其中工件号i∈N＝ ｛1，2，…，n｝，工序号j∈P＝ ｛1，2，…，p｝，设备号k∈M＝ ｛1，2，…，m｝）.

取设计变量

其中0－1变量表示工序和设备的选择关系＝1表示工序Oij在设备k上进行；整数变量ORDij表示工序Oij的加工顺序，数值小者顺序靠前.

多目标FJSP优化数学模型如下：式（3）是根据权重W不同，分别取最长完工期、单台设备最大负载、全部设备总负载和总加工成本，或它们的任意组合最小化为优化目标，并计算工序的完成时刻；式（4）表示设备k的工作时间；式（5）表示全部设备的总工作时间；式（6）表示总加工成本；式（7）保证每工序只在一台设备上进行；式（8）保证同一工件各工序的顺序；式（9）保证ORDij取得1～pn的组合；式（10）保证各工序的开始加工时刻或者为零，或者要在同一设备前一工序完工之后.即

式中：中间变量STij、ETij表示工序Oij的加工开始与完成时刻；METk、MWT表示设备k的工作时间和全部设备的总工作时间；COST为总加工成本；Ck为设备k的工时成本.

1.2 基于MAS的车间调度模型

本调度系统主要由设备Agent（device agent，DA）、任务 Agent（task agent，TA）和策略Agent（strategy agent，SA）组成，如图1所示.TA与DA、TA与SA、TA与TA之间可以通信.TA在确定好DA后，会在DA对应的设备时间轴上选择合适的位置，也即安排工序至此设备，实现调度功能.

图1 基于MAS的柔性作业车间调度模型Fig.1 FJSP model based on MAS

1.2.1 设备 Agent 设备 Agent（结构见图2）是车间中加工设备的代理，每台加工设备对应一个设备Agent，设备Agent通过设备接口可获得加工设备的技术参数和设备状态等信息，再把加工任务发送给加工设备执行.设备Agent可与任务Agent交互信息，实现任务资源分配，并向任务Agent反馈状态信息.

图2 设备Agent结构Fig.2 Structure of device agent

Agent可分为慎思型、反应型和混合型.设备Agent本身不需要具有判断和推理能力，它的主要作用是动态地标定自身状态，并激发其他Agent的进程，因此，设备Agent被设计成反应型Agent.

1.2.2 任务 Agent 任务 Agent（结构见图3）为慎思型.它根据到达的任务动态地生成.每道工序会对应一个任务Agent，该工序的生产调度过程及相关数据都由其对应的任务Agent管理.任务Agent撤销即代表该工序已完成.日志数据库中保存生产调度过程中形成的数据.

图3 任务Agent结构Fig.3 Structure of task agent

任务Agent通过与策略Agent交互，将设备Agent投招标和优化目标等信息及时传递给策略Agent，然后从策略Agent得到调度方案后调配，最终将生产任务下达到设备，确定工序的加工设备和开始加工时间.

任务Agent与其他任务Agent交互信息，传递完成任务所必须满足的前继和后继条件，在满足先后顺序约束的条件下使任务能实现实时推进；与设备Agent交互信息，为任务分配适当的资源，并监测和监控任务的执行情况及资源的负载情况；与策略Agent交互信息，实现实时动态调度.

1.2.3 策略 Agent 策略 Agent（结构见图4）为慎思型.其与任务Agent交互可实现动态实时调度，且因其内部封装了算法和调度规则，其在接受任务Agent的信息后，能提供不同调度方案并返回任务Agent；提供人机接口，可调整算法参数，制定新的调度方案.

策略Agent是基于MAS的车间调度核心部分，对车间的动态调度有效执行起关键作用.考虑到job－shop中存在的多目标优化、柔性作业、有JIT要求等调度问题，在策略Agent中特别封装了一种改进遗传算法，以实现车间调度所应达到的高效、稳定.本文并没有把算法规则封装在任务Agent中，而是独立设计了一个策略Agent，这既保证了系统的可重构性、柔性，也便于系统的维护和升级.策略Agent模块中设置了人机接口，保证当生产过程中有插单等紧急情况时，有可提供人工干预调度的能力.

图4 策略Agent结构Fig.4 Structure of strategy agent

1.2.4 Agent间的协作模型 多Agent系统运作的基础是彼此间的通信与协作.本文采用合同网方式实现多Agent的控制，通过任务招标、投标和订立合同进行合作.

（1）Agent间的协作

利用招标－投标－中标机制，任务Agent确定完成某一任务的设备Agent，设备Agent与此任务Agent签订合同后执行相应生产任务.在整个生产过程中，任务Agent将遇到的紧急突发状况（如人员和设备的选择与冲突等）反馈至策略Agent，由策略Agent提供相应解决方案，根据情况或者由系统自带算法调整重排生产任务，或者通过人机交互，手动重排生产任务.

（2）合同网机制

任务 Agent：TA＝ ｛TA1，TA2，…，TA np｝，np为分解后的工序数.传递如下消息内容：｛Qij，Dij，Lij，Cij，DSij｝；Qij为工序Oij的作业量，Dij为该任务所需设备表，Lij为完工期限，Cij为其他约束，DS ij为任务描述.然后由任务Agent并发地向可加工该工序的所有的设备Agent广播，消息格式为｛Qij，Oij，Lij，Cij，DSij｝；Qij为需执行的作业量，Oij为作业名称，Lij为完工期限，Cij为其他约束，DSij为任务描述.设备Agent收到招标书后，根据标书内容（任务时间、优先级等）和自己的能力、状态等决定是否投标.按如下格式返回任务Agent：｛TB k，Qk，T k｝；TB k为该设备可执行的时间段表，Qk为保证期限的最大作业量，Tk为期限截止前该设备可利用时间.任务Agent根据收到的标书和自身的策略进行评价，选出中标者，并将任务分配给中标的设备Agent，确认消息，格式为｛Oij，Qij，Lij，Cij，DSij｝；Oij为作业名称，Qij为需执行的作业量，Lij为完工期限，Cij为任务约束，DSij为任务描述[10].中标者更新自身知识库，执行子任务并返回结果，如果最大作业量小于任务要求作业量，任务Agent会考虑由数个设备承担；如仍无法办到，则通知策略Agent无法承担所分配任务；策略Agent若根据一定的规则调整未果，则发出警报，操作人员可通过人机接口，手动强制执行或调整生产计划，必要时或寻求外协.

最后，任务Agent提交给车间生产任务管理系统任务的完成情况，同时注销相应的任务Agent.在建立合同关系之后，任务Agent还需监测任务的执行情况，只要发现设备Agent处于过载、故障等状态，就必须进行资源的转移分配.如任务Agent自身不能调停处理，需反馈至策略Agent，策略Agent会根据需要修改计划.所采用的多Agent的控制过程（基于合同网机制）如图5所示.

图5 合同网中投招标机制图Fig.5 Tendering－bidding mechanism graph of contract net

2 基于遗传优化的MAS调度算法设计

如前文所述，策略Agent为本MAS调度系统的核心一环，其中封装了改进的遗传算法以解决实际车间多目标优化的柔性作业调度问题，常见柔性作业车间调度加工时间如表1所示.

本文对于非完全柔性工序（即存在某设备k不能用来完成工序Oij），人为地将加工时间T kij改为很大值，如取为1000.这样在优化过程中，算法会自动规避这样的工序设备选择.同时引入对所有设备加工时间都是0的虚工序，可以保证各工件的工序数一致.于是原问题工时表变为表2.

表1 一般的柔性作业车间调度问题加工时间Tab.1 Processing time of general FJSP

表2 规划为标准FJSP后的加工时间表Tab.2 Processing time after transforming into standard FJSP

2.1 多目标优化

实际车间通常会有不同的目标要求，生产中常见的优化目标为最长完工期、单台设备最大负载、全部设备总负载和总加工成本最小化.本文分两步实现多目标规划：第一步分别取各单目标为遗传算法的适应度函数，得到各自的较优值z＊1、z＊2、z＊3和z＊4；第二步取各目标的归一化加权组合作为适应度函数进行遗传优化.权重可根据实际情况进行设置调整，或者自动调整（如侧重总加工成本最小化，可设置其相应权重系数大于其他目标函数权重系数）.实验证明，通过合理调整权重，该方法能较好地协调各目标，快速获得具有实际应用价值的解.

2.2 遗传算法设计

（1）编码方式

本文采用直接编码，由两部分组成：第一部分为基于工序排列的编码，用来确定工序的加工顺序；第二部分为基于机器分配的编码，用来选择每道工序的加工机器.编码

图6 解码流程图Fig.6 Flow chart of decoding

表示工序O31第1个安排，在M4上加工；工序O11第2个安排，在M1上加工；其余依次类推.

（2）群体初始化

随机生成population size个染色体个体.

（3）适应度函数

直接取目标函数为适应度函数.

（4）解码方式

解码分为3个步骤：首先按基因中的顺序与设备选择，依次将各工序投射对应到设备；然后考虑各工序加工时间进行整理，获得各工序的开始和结束时刻、各设备工作时间和结束时刻、车间工作终止时刻ENDTIME；最后按照单目标或多目标要求生成适应度函数.解码过程的流程图如图6所示.PUTIN（x，y）为插入矩阵，x代表插入顺序，PUTIN（x，1）、PUTIN（x，2）、PUTIN（x，3）分别代表工件号、工序号和设备号；ST（i，j）、ET（i，j）、MET（k）、MWT（k）分别代表工序开始时刻、结束时刻、设备空闲时刻和设备工作时间；F（i，j）是工序插入完成标志；pn为工序总数.

（5）遗传算子的设计

①选择算子：选择操作采用精英机制（elite），即直接将适应度最好的elite count个染色体个体直接遗传到下一代.

②交叉与变异算子：交叉操作和变异操作的父代在精英机制后剩下的个体中产生，采用锦标制tournament即从随机选取的tournament size个染色体个体中选择适应度最好的个体作为交叉与变异的父代；在生成的父代中按crossover fraction进行交叉，余下部分进行变异操作.

a.交叉算子

选择两个父代，等比随机进行交叉.有两种方式：总体取父代1，某插入顺序取父代2，这会出现不合理排列，在解码过程会解决；总体取父代1，某设备选择改为父代2.

b.变异算子

按比例随机选择进行3种交叉：调换插入顺序；调换设备；随机更改设备.其中第3条能保证排除弱智方案.

可见，以上的算子可以保证子代的基因值总是有效的，这样就保证了算法运行时不会生成无效基因，从而有利于提高算法的可靠性和效率.

（6）遗传算法的操作步骤

①初始化，随机生成population size个染色体个体；

②求解各单目标最优值；

③构造等权多目标函数；

④利用GA搜索；

⑤判断优化结果能否被接受，是则终止，否则继续；

⑥人工：根据方案指标与实际需求，决定调整方向；自动：根据方案指标与范围约束，决定调整方向，或根据模糊规则决定调整方向；

⑦根据⑥的决策调整权重；

⑧转④.

（7）运行参数

遗传算法的运行参数为populationsize＝200，elitecount＝ 7，tournamentsize＝ 3，crossoverfraction＝0.2，generations＝200.

3 实例验证

山西太原某公司机械车间的调度属于典型的多目标柔性job－shop调度，该制造单元有9台进口设备，包括并行机和多功能加工中心，各加工设备代号、每单位工时的加工成本，及对不同工件各工序的加工时间如表3、4和5所示.

应用本文提出的基于多Agent的车间调度模型及优化调度算法开发了生产管理软件.图7为多目标调度参数界面，可选择调度任务，并可选择预调度先查看调度结果.如有不合适之处，可人工调整；如果符合，则可选择正式调度并执行“开始”.在优化参数一栏，可人工修改遗传算法参数，否则就是系统默认的参数值.优化目标部分，在各优化目标后面方框中的数字代表不同权重，数值大小可调.优化参数和优化目标权重值的调整会影响调度时间和结果，可根据工厂车间实际要求做出调整.多目标优化的选择，只要在优化目标处勾选相应的目标即可.如图8显示的是以成本和工期最小为多目标优化的甘特图，在优化目标处选中“最小成本”和“最短工期”，“0%”表明该道工序尚未进行，完成进度为0.图9显示的是最小成本、最短工期和最小全部设备负载为多目标的优化调度甘特图.调度结果显示为不同设备加工不同工序的甘特图.

表3 设备代号对应表Tab.3 Corresponding device code

表4 设备加工成本Tab.4 Processing cost of device

表5 设备加工时间表Tab.5 Processing time of device

综上可知，该车间优化调度系统可动态及时调整调度结果，并可人工调整相应参数以满足不同的调度要求，最终实现车间实时动态多目标调度.

图7 多目标调度参数界面Fig.7 Parameters interface of multi－objective scheduling

图8 多目标优化（成本＋工期最小）调度结果Fig.8 Scheduling result of multi－objective optimization（minimum cost and makespan）

图9 多目标优化（成本＋总负载＋工期最小）调度结果Fig.9 Scheduling result of multi－objective optimization （minimum cost，total load and makespan）

4 结 论

本文针对多目标柔性作业车间调度问题提出的基于多Agent的车间调度系统结构简单，便于系统维护和升级，并保证了系统的可重构性和柔性，能满足车间柔性作业、多目标优化等实际问题的要求.实践证明，该调度系统适用于复杂的柔性车间作业调度环境，适应性和自治性较高，能保证车间生产持续优化地进行，应用前景广阔.

[1]GAO Jie，GEN Mitsuo，SUN Lin－yan，etal.A hybrid of genetic algorithm and bottleneck shifting for multiobjective flexible job shop scheduling problems[J].Computers ＆ Industrial Engineering，2007，53（3）：149－162

[2]BLAZEWICZ J，FINKE G，HAOPT G.New trends in machine scheduling [J].European Journal of Operational Research，1988，37（2）：303－317

[3]CHEN H，IHLOW J，LEHMANN C.A genetic algorithm for flexible job－shop scheduling [C]//IEEE International Conference on Robotics and Automation.Detroit：IEEE，1999：1120－1135

[4]JIA H Z，NEE A Y C，FUH JY H，etal.A modified genetic algorithm for distributed scheduling problems[J].International Journal of Intelligent Manufacturing，2003，14（3）：351－362

[5]HO N B，TAY J C.GENACE：An efficient cultural algorithm for solving the flexible job－shop problem[C]//IEEE International Conference on Robotics and Automation.Detroit：IEEE，2004：1759－1766

[6]KACEM I，HAMMADI S，BORNE P.Approach by localization and multiobjective evolutionary optimization for flexible job－shop scheduling problems[J].IEEE Transactions on Systems， Man，and Cybernetics，Part C，2002，32（1）：1－13

[7]KACEM I，HAMMADI S，BORNE P.Pareto —optimality approach for flexible job－shop scheduling problems：hybridization of evolutionary algorithms and fuzzy logic[J].Mathematics and Computers in Simulation，2002，60（2）：245－276

[8]PEZZELLA F，MORGANTI G，CIASCHETTI G.A genetic algorithm for the flexible job－shop scheduling problem [J].Computers ＆ Operations Research，2008，35（5）：3202－3212

[9]饶运清，谢 畅，李淑霞.基于多Agent的Job Shop调度方法研究[J].中国机械工程，2004，15（5）：873－877

[10]潘 颖，张文孝.基于多agent的离散制造业制造执行系统框架研究[J].计算机应用研究，2009，26（1）：244－249