基于遗传算法一多智能体的FMS工件调度研究

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

第 38卷 第5期2013年 10月广西大学学报：自然科学版Journal of Guangxi University：Nat Sci EdVo1．38 No．50ct．20l3文章编号：1001-7445(2013)05．1086-06基于遗传算法一多智能体的FMS工件调度研究黄恩洲，吴少雄(福建工程学院 交通运输系，福建 福州 350108)摘要：针对柔性制造系统(FMS)一般调度方法的不足，提出基于全局黑板的多智能体调度系统，该系统建立多智能体交互过程，通过多智能体的合作快速建立调度模型，并通过优化模块对调度模型进行求解，从而获得非劣调度方案。在设计优化模块时，采用遗传算法，针对柔性制造系统调度问题的特点，改进并扩展了基于工序的编码方法 ，引入工序一机器的关系矩阵，从而实现解和染色体的一一对应关系，并设计算法的适值函数、选择方法、交叉和变异方法。仿真结果表明，该调度系统在求解时收敛速度快 、精度较高。最后通过 10个经典的柔性job—shop调度算例，与单纯使用遗传算法和禁忌搜索算法进行比较，目标值平均改善 2．21％和1．04％ 。

关键词：柔性制造系统；调度；遗传算法；智能体中图分类号：TH16 文献标识码 ：AResearch on FMS job scheduling based ongenetic algorithm and multi-agentHUANG En—zhou．WU Shao—xiong(Department of Traffic and Transportation，Fujian University of Technology，Fuzhou 350108，China)Abstract：To overcome the sho~age of general scheduling method of flexible manufacturing system(FMS)，a multi-agent system based on genetic algorithm is proposed．This is a multi—agent interac—ting procedure which can establish a temporary schedule model by cooperation of agents via overall—blackboard for a given task and can call an optimization module to solve the mode1．To design opti—mization module，genetic algorithm is used．According to the characteristic of flexible manufacturingsystem schedule problem ，a special representation of solution modifed through operation—based rep-resentation is proposed． Matrix of process—machine is introduced to establish solution—chromasomerelations．Fitness function and selection method，crossover and mutation operator are designed．Sim—ulation result shows that the proposed system could make a faster rate of convergence and more opti—mal solution．Finally，compared with genetic algorithm and tabu algorithm，this method makes anaverage improvement by 2．21％ and 1．04％ respectively via solving ten typical flexible j0b-shopschedule problems.

Key word：flexible manufacturing system；scheduling；genetic algorithm；agent收稿日期：2013-07—30；修订日期：2013-08-21基金项目：福建省 自然科学基金项目(2009J01309)；福建工程学院科研发展基金项目(GY-21 1057)；福建省教育厅 A类基金(JA11192)通讯联系人：吴少雄(1962-)，男 ，福建寿宁人，福建工程学院教授；E—mail：957035649###qq．con。

第 5期 黄恩洲等 ：基于遗传算法一多智能体的 FMS工件调度研究 10870 前 言柔性制造系统(Flexible Manufacturing System，FMS)调度问题属于柔性作业车间调度问题(Job·Shop Problem，JSP)，由于 FMS存在并行和多功能机器，与一般的JSP问题相比较，柔性 JSP问题具有柔性加工路径，求解更加困难。FMS调度一般分为静态调度和动态调度两类，静态调度从全局考虑 FMS工件的最优调度，事前即确定工件调度方案，但静态调度存在两个方面的应用困难：其一为建模困难，其二由于生产情况的不确定，事前确定的调度方案无法适应变化的环境从而导致方案无法实施。针对这个问题，动态调度应运而生，动态调度虽然比静态调度灵活，但是调度方案往往不是最优，为了解决这个问题，国内外许多学者在动态调度的基础上采用各种优化方法，试图解决最优性和灵活性的问题，最大限度发挥 FMS系统的优点，这些优化方法主要基于：Petri网 J¨、启发式算法 引、智能算法L4 、模糊规则 等。随着智能体技术的发展，多智能体系统被用来模拟、优化、仿真和控制不确定环境下的分布式系统 。文献[11．12]提出了基于合同网协议的多智能体调度系统，证明了多智能体系统用于处理FMS调度问题的优越性。但是由于合同网协议过分强调个体智能体的利益平衡，对小规模 FMS调度问题能够实现 FMS系统的优点，但是随着问题规模的增大，智能体之间“争利”的现象十分突出，从而影响优化的速度和精度。针对这个问题，本文提出基于全局黑板协议的多智能体调度系统，并用遗传算法对调度问题进行优化，避免了智能体之间的争利，强调智能体之间的协作，从而提高 FMS调度的全局最优性和灵活性。

1 柔性制造系统调度问题描述典型的 FMS调度问题可以描述为这样的一个加工任务：有 rt个工件(每个工件有 k道工序)要在m(m >2)台机器上进行加工，工件的每道工序可以在可选的多台机器上加工，每台机器可以加工多种工序。设：① 工件集P={P ，P2，?，P }，P (i=1，2，?，rt)为第 i个工件；② 工序集 0={0。，0 ，?，0 }，0 ={0 0 ，? 0}为工件Pi的第J(J=1，2，?，k)道工序；③ 机器集 M={m ，m ，?，m }，m。( =1，2，?，m)为第 q台机器；④ 工件占用每台机器的时间矩阵为 T，t洳∈T为工件P 的第 道工序占用机器 m 的时间。

另外，该调度问题应满足以下约束条件：①所有工件在初始时刻都可加工；②工件的每个工序在可选机器上的加工时间为常数；③每台机器每次只能加工一个工件；④每个工件一次只能在一台机器上加工；⑤每个工序的加工不可中断；⑥每个工件的加工顺序不可改变。

假设问题的优化目标为最小化全部工件的最大完工时间，即min{max(c )}，i=1，2，?，n，其中，c 为工件P 的完工时间。

2 基于全局黑板的多智能体调度系统结构智能体是某个环境中的计算机系统，多智能体系统是通过某种协议而松散联系的智能体形成的网络，各智能体之间相互合作，共享知识和信息，解决单个智能体不能处理的问题。

FMS调度系统被建模成智能体社会，社会成员可分为三类：订单智能体、机器智能体和运输智能体，如图 1所示。

多智能体系统工作过程如下：① 外部环境向订单智能体提交工件加工订单信息；② 订单智能体的决策模块评估订单的类型，建立工件集P；③ 订单智能体根据工艺数据把接收的订单分解为多道工序，建立工序集 O，评估调度所需的资源，并公布于全局黑板；1088 广西大学学报：自然科学版 第 38卷图1 基于全局黑板的多智能体调度系统结构n昏 1 Glob~·blackboard-based mllti—agent system sched~e~ructure④ 机器智能体读取全局黑板的机器资源需求，根据知识库和资源数据提交各自的的机器资源报表，公布于全局黑板；⑤ 订单智能体根据调度的目标和机器资源约束，通过优化模块对调度问题进行优化，并将结果公布于全局黑板；⑥ 运输智能体读取调度方案，并根据 自身的知识和资源数据库规划运输方案，并反馈至全局黑板。

3 基于遗传算法的优化模块在多智能体调度系统中，智能体之间完成资源的共享和I临时模型的建立，而对模型的优化主要通过订单智能体的优化模块来完成，这里采用遗传算法，遗传算法流程如图2所示 。

遗传算法最关键的是解的编码和解码设计、适值函数和选择算子的设计、交叉和变异方法的设计。

3．1 编码和解码方法在遗传算法中，每一个可行调度通过某种方法编码成一个染色体，对于一般的车间调度问题，往往采用基于工序的编码方法L1 ，但是由于 FMS存在并行机和多功能机，该方法的编码与可行调度之间无法一一对应。对此，本文提出一种改进的工序的编码法，设有 n个工件 m台机器，编码过程为：给每个工件顺序编号(i：1，2，?，n)，工件的工序数量用编号在染色体中出现的次数表示，染色体中出现的第 个i表示工件 i的第． 道工序。为了表示工序与机器的对应关图2 遗传算法流程图F 2 Genetic aIg0rithm flow chaM第5期 黄恩洲等：基于遗传算法一多智能体的FMS工件调度研究 1089系，引入关系矩阵R=[rik] ， 和 k分别是机器和工序编码 ，其中f1，工序 k可以在机器 mf上加工一
10
，
否则 ’则一个可行调度的染色体编码为 [ ]。 ，z=1，2，?，／7,X m，每个基因 对应的加工机器由列向量， ( 表示编码中 出现的次序)中元素 1随机对应的一台机器。

例如，3个工件、3台机器，工件的工序分别是 O。(1，2，3)，o (2，3，1)，03(3，2，1)，工序和机器的足 = ]，即工序 1可以在机器 m。和 m。上加工，工序2可以在 m：和 m。上加工，工序3可以在 m 和 m 上加工。

随机产生一个编码 [3 2 3 1 1 2 3 2 1]，可以得知各工件的加工路径分别为P。：，．。

，
．2 ，_3，P2：，．2一，．3_÷，_l，P3：，．3_ ，．2一 ，．J，然后再随机指定每个列向量， 所对应的可行机器，如P1：m1_÷m3_+m2，P2：m2 m1 m1，P3：m1_ m2 m3，最后根据在编码中所对应的位置关系确定一个可行的调度为：ml：p3 p1_÷p2 p2，m2：p2 p3，m3：p1 p3 p1。

对于染色体 i，根据其解码结果和工序机器对应的加工时间可以确定该染色体所对应的目标函数值 c ，设 c一 为种群中目标函数的最大值，则适值函数为：F(i)=c 一C 。

3．3 选择算子选择是从当前种群中按照某种规则选出优 良个体，这里采用轮盘赌(Roulete Whee1)选择策略，对于个体 k，适值为 F(k)，被选择的概率为P(后)： 。

交叉运算能够使父代的特征遗传给子代，假设两个父代染色体P 和P：，交叉算法如下：① 在父代染色体P。中随机选择一个位置 ，对应工件为 ；② 在P。中找出最临近 的同一工件 ，对应的位置为 ”，两个位置之间的基因(含 )为一个部③ 按同样的方法在父代染色体P 中找出第二个部分调度；④ 交换两个部分调度，得到两个子代 。和 ：；⑤ 修正：删除或添加子代 和 ：中的剩余基因和缺乏基因，使得子代的染色体仍然为可行染色体。

3．5 变异算子为了避免种群近亲繁殖，引入变异算子，变异能够防止遗传运算陷入局部最优。本文的变异算子为随机选择两个代表不一致的工件基因互相交换位置，如图3所示。

4 仿真实例与算例比较[3 2 (2) 1 1 (3) 3 2 1]图3 变异举例Fig．3 Example for chromosome mutation按照图1所示结构建立仿真模型，订单智能体优化算法采用前面第3部分所述的遗传算法，假设某FMS调度系统有5个工件(P 一P )、4个工序(1—4)和6台机器(m，～m )，工序与机器的关系如表 1所示，其中：1表示机器能完成该工序，否则为0。工件的加工工序集如表 2所示，O 表示第 i道工序。

工序加工时间如表3所示，m 一_『表示 mi加工第 道工序。

1090 广西大学学报：自然科学版 第 38卷参数设定如下：种群 PopSize=30，遗传代数 max_generation=50，交叉概率 P =0．7，变异概率P =0．05，调度结果的甘特图如图4所示，最优解收敛过程如图5所示。

053mI~ _ 2l 24011 032 042 024m：： I ■■_ ■■_ 0 4 8 ll l6 23 31051 031 012 023 0430 5 8m 4~02lm ： —■_ 0 70 7 l3 2l 24 29图4 机器调度结果甘特图Fig．4 Gant chart for scheduling reset望靠萋萎迭代次数欣图5 最优解收敛过程Fig．5 Convergence procedure of optimal solution从图4、图5可以看出，遗传算法在迭代10次左右目标值就能够下降到最优值附近，在第 16次即可达到最优值。

为了验证方法的有效性，使用文献[14]中的l0个算例，分别与文献[5]的遗传算法(GA)、文献[6]的禁忌搜索算法(Tabu Search，TS)做比较，结果如表 4所示。

表4中，／'t列表示工件数，m列表示机器数，LB列表示算例已知的下界，GA—MA列为基于遗传算法一多智能体的调度方法求得的最好结果，GA列为文献[5]提供的遗传算法求得的最好结果，rI1S列为文献[6]提供的禁忌搜索算法求得的最好结果，dev为最优解(Opt)偏差的百分比，即de ： [ 坐 × 100％Opt比较算法从表4可以看出，本文提出的方法对复杂的柔性 job．shop问题求解结果基本上不劣于(除了算例03)单纯使用遗传算法和禁忌搜索算法获得的结果，目标值平均改善 2．21％和 1．04％。

一一 1J 2
第 5期 黄恩洲等 ：基于遗传算法一多智能体的 FMS工件调度研究 10915 结 语本文所提出的基于遗传算法一多智能体的FMS调度系统，通过多智能体的交互，充分共享系统当中的所有资源，快速建立调度模型，并且通过各类智能体的合作及时获取系统的现有资源约束，然后通过订单智能体优化模块(遗传算法)，快速优化模型，从而获得较优方案。通过仿真与算例比较可以看出：在柔性 JSP调度问题中，基于全局黑板的多智能体系统优于基于合同网协议的多智能体系统；多智能体调度系统结合遗传算法比单纯使用遗传算法、禁忌搜索方法求解速度更快，精度更高，是复杂调度系统新的研究方向。

参考文献：[1] 彭海波，应保胜，陈馨 ．基于 Petri网的柔性制造系统建模的调度算法[J]．中国机械工程学报，2005，3(2)：220．223.

[2] 高春华，李人厚，陈浩勋 ．智能选择启发规则的 FMS实时调度方法[J]．控制与决策，1998，13(4)：361．364.

[3] HAQ A N，KARTHIKEYAN T，DINESH M．Scheduling decisions in FMS using a heuristic approach[J]． e Internation.

al Journal of Advanced Manufacturing Technology，2003，22(5)：374-379.

[13][14]杨红红，吴智铭 ．基于自适应遗传算法的柔性动态调度研究[J]．中国机械工程，2002，13(21)：1845．1848.

PEZZELLA F，MORGANTI G，CIASCHETH G．A genetic algorithm for the flexible job—shop scheduling problem[J].

Computer&Operations Research，2008，35(10)：3202-3212.

MASTROLILLI M，GAMBARDELLA L M．Effective neighbourhood functions for the flexible job shop problem[J]．Journalof scheduling，2000，3(1)：3-20.

CHAN T S，CHAN H K，KAZEROONI A．Real time fuzzy scheduling rules in FMS[J]．Journal of Intelligent Manufactur-ing，2003，14(3)：341-350.

胡春华 ，吴波，杨叔子 ．基于多自主体的分布式智能制造系统研究[J]．中国机械工程，1998，9(7)：54．57.

ADHAU S，MITrAL M L，MITFAL A．A multi—agent system for distributed multi-project scheduling：An auction-basednegotiation approach[J]．Engineering Applications of Artifcial Inteligence，2012，25(8)：1738．1751.

陈宁江，苏德富 ．基于 Agent的CSCW 系统及其通讯实现[J]．广西大学学报 ：自然科学版，2000，25(2)：94-97.

黄恩洲，史尔维 ．FMS多智能体调度系统的角色建模[J]．电脑开发与应用，2010，23(11)：1_3.

CHEN K Y，CHEN C J．Applying multi—agent technique in multi-section flexible manufacturing system[J]．Expert Systemwith Applications，2010，37(11)：7310-7318.

GEN M，TSUJIMURA Y，KUBOTA E．Solving job·shop scheduling problem using genetic algorithm[C]／／GEM M，KOBAYASHI Proc of 16 International Conference on Computer and Industrial Engineering．New York：PergamonPress，1994：576679.

BRANDIMARTE P．Routing and scheduling in a flexible job shop by tabu search[J]．Annals of Operations Research，1993，41(3)：157—183． (责任编辑 梁 健)1』 1J 1J 1{ 1i } m ¨
r} rL r} rL rL