（管理科学与工程专业论文）基于市场机制的多Agent柔性车间调度.pdf

独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 关于论文使用授权的说明 口f p 6 co 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：导师签名：堑垒盘杰日期： 摘要 摘要 产品的供货周期、质量和售后服务水平，而先进 个重要手段。生产调度是生产管理的核心内容和 调度，对于生产系统的正常运行有重大影响。 术和现代管理技术的核心技术，国内外许多学者 进行了研究，并取得丰富的理论成果，但是大多数研究针对的是经典车间调度问 题( j o b s h o ps c h e d u l i n gp r o b l e m ，j s p ) 的优化。在经典j s p 问题中，每个工件 的每道工序只能在指定的机器上加工，这在许多实际生产环境中显得不够灵活。 而柔性作业车间调度问题( f l e x i b l ej o b s h o ps c h e d u l i n gp r o b l e m ，f j s p ) 允许工 序在多台机器中的任意一台加工，从而符合更多的实际生产情况，但同时也增加 了问题的难度。 f j s p 不仅需要确定工序加工的顺序，还要给每道工序分配机器，因此是比 j s p 更复杂的问题。本文针对f j s p 的特点，提出了一种分布式多a g e n t 柔性作 业车间调度系统，系统由工件a g e n t 和机器a g e n t 组成，采用基于市场的协议进 行协商。各类a g e n t 通过发送消息和响应消息的方式进行交互，在各a g e n t 内部 设计了一个或多个消息接口，并在每个接口中封装相应的消息响应函数。这些函 数能帮助各a g e n t 按照其独立、局部的信息和目标，并兼顾系统的性能进行决策。 工件a g e n t 通过招投标的方式，选择合适的机器完成加工任务，机器a g e n t 按照 市场机制通过自由竞争来获得工件的加工权，并使自己的收益最大。 良好的协商机制是各类a g e n t 有效完成调度任务的基础，也是解决不同问题 的调度策略的基础。协商策略是本文研究的一个重要内容，本文在基于市场协议 的基础上设计了a g e n t 间的协商策略，并重新设计了a g e n t 协商时的价格函数。 该协商策略有助于a g e n t 快速准确地做出决策，大大减少系统的协商次数，提高 了算法的性能。 最后用j a v a 语言进行程序设计和实现了基于市场机制的多a g e n t 柔性作业 车间调度系统，并对柔性作业车间调度的平均滞后、最大完工时间和平均等待时 间等问题进行仿真实验，并与传统的分派规则进行比较，结果显示基于市场机制 的柔性作业车间调度方法明显优于传统的分派规则。同时，系统也具有良好的稳 定性和一定的优化性能。 关键字：多a g e n t 系统：柔性作业车间调度；市场机制 i i a b s t r a c t a b s t r a c t t h ec o m p e t i t i o no fm a n u f a c t u r i n gd e p e n d sm a i n l yo np r o d u c td e l i v e r yc y c l e ， q u a l i t ya n da f t e r - s a l e ss e r v i c e a d v a n c e dp r o d u c t i o nm a n a g e m e n ti sa ni m p o r t a n t m e a n st oa c h i e v et h i sg o a l a st h ec o r ea n d k e yt e c h n o l o g i e sf o rp r o d u c t i o n m a n a g e m e n t ，t i m e l y , a c c u r a t ea n de f f i c i e n ts c h e d u l i n gh a sam a j o ri m p a c to n p r o d u c t i o ns y s t e m s p r o d u c t i o ns c h e d u l i n g o p t i m i z a t i o ni st h ec o r eo fa d v a n c e d m a n u f a c t u r i n g t e c h n o l o g y m a n yr e s e a r c h e r ss t u d i e do nt h i st o p i ca n do b t a i n e dp l e n t yo ft h e o r e t i c a l r e s u l t s b u tm o s to ft h e mo n l yf o c u so nt h ej o b s h o ps c h e d u l i n g p r o b l e m ( j s p ) i na c l a s s i cj s p , o p e r a t i o n so fap a r tm u s tb ep r o c e s s e do nas e to fm a c h i n e st h a t a r e c o n t i n u o u s l ya v a i l a b l e i ti sn o ta g i l ee n o u g hi nt h ea c t u a lp r o d u c t i o ne n v i r o n m e n t i n af l e x i b l ej o b s h o ps c h e d u l i n gp r o b l e m ( f j s p ) ，s o m eo ra l lo p e r a t i o n so fe a c hp a r t a r ea l l o w e dt ob ep r o c e s s e do na l t e r n a t i v em a c h i n e s s of j s pc a nm e e tm o r eo ft h e a c t u a lp r o d u c t i o n ，b u ta l s oi n c r e a s e st h ed i f f i c u l t yo ft h ep r o b l e m i naf j s p , i tn o to n l yn e e d st od e t e r m i n et h es e q u e n c eo fo p e r a t i o n s ，b u ta l s ot o a l l o c a t e a p p r o p r i a t em a c h i n ef o re a c ho p e r a t i o n b a s e do nt h ec h a r a c t e r i s t i c so f f l e x i b l ej o b s h o ps c h e d u l i n g ，ad i s t r i b u t e dm u l t i a g e n tb a s e df l e x i b l ej o bs h o p s c h e d u l i n gs y s t e mi sp r o p o s e d t h es y s t e mc o n t a i n sp a r ta g e n t sa n dm a c h i n ea g e n t s t h en e g a t i o np r o t o c o li sb a s e do nm a r k e ts c h e m e a g e n t si n t e r a c tw i t he a c ho t h e r t h r o u g hs e n d i n ga n dr e s p o n d i n gt om e s s a g e s e a c ha g e n th a so n eo rm o r em e s s a g e i n t e r f a c e si nw h i c hc o r r e s p o n d i n gr e s p o n s ef u n c t i o n sa r ee n c a p s u l a t e d i tc a nm a k e d e c i s i o n sb a s e do na g e n t s i n d e p e n d e n t ，l o c a li n f o r m a t i o n t o g e t h e rw i t hg l o b a l p e r f o r m a n c e t h r o u g hb i d i n g , p a r ta g e n t ss e l e c tt h ea p p r o p r i a t em a c h i n e m a c h i n e a g e n t ss e l e c tt h ea p p r o p r i a t ep a r tb yc o m p e t i n gw i t ho t h e r sb a s e do nm a r k e t b a s e d s c h e m et om a x i m i z ei t si n c o m e e f f e c t i v en e g o t i a t i o nm e c h a n i s mi st h eb a s e m e n to fa l lk i n d so f a g e n t st o c o m p l e t es c h e d u l i n gt a s k n e g o t i a t i o ns t r a t e g yi sa ni m p o r t a n tp a r to ft h i sp a p e r a n e g o t i a t i o ns t r a t e g yb a s e do nm a r k e t b a s e dn e g o t i a t i o ns c h e m ei sp r o p o s e d p r i c e n e g o t i a t i o nf u n c t i o ni sd e s i g n e da g a i n t h ep r o p o s e ds t r a t e g yi sb e n e f i c i a lt om a k e d e c i s i o n sa c c u r a t e l ya n dq u i c k l yf o rt h ea g e n t s a tt h es a m et i m e ，d e c r e a s et h e n u m b e ro fn e g o t i a t i o na n di n c r e a s et h ep e r f o r m a n c eo fs c h e d u l i n ga l g o r i t h m t h es y s t e mi si m p l e m e n t e dw i t hj a v aa n ds i m u l a t e du n d e rv a r i o u sf l e x i b l ei o b s h o ps e t t i n g sw i t hm e a nt a r d i n e s so b j e c t i v e ，m a k e s p a na n dm e a nw a i t i n gt i m e t h e r e s u l t ss h o wt h a tt h e p r o p o s e d m a r k e t - b a s e d s c h e d u l i n gm e t h o ds i g n i f i c a n t l y i i i 0 u t p e r f o r m st r a d i t i o n a ld i s p a t c h i n gr u l e s a tt h es a m et i m e ，t h es y s t e ma l s oh a sg o o d s t a b i l i t ya n d ac e r t a i no p t i m a lp e r f o r m a n c e k e yw o r d sm u l t i - a g e n ts y s t e m ；f l e x i b l ej o b s h o ps c h e d u l i n gp r o b l e m ：m a r k e t b 舔e ds c h e m e i v 目录 目录 摘要i a b s t r a c t i 第1 章绪论1 1 1 研究背景1 1 2 研究现状2 1 3 研究方法及主要工作5 1 3 1 研究内容5 1 3 2 研究方法与技术路线图6 1 3 3 创新点6 1 3 4 论文主要结构7 第2 章相关理论9 2 1a g e n t 的相关理论9 2 1 1a g e n t 的概念9 2 1 2a g e n t 的属性9 2 1 3a g e n t 的结构模型1 1 2 2 多a g e n t 系统1 2 2 2 1 多a g e n t 系统1 2 2 2 2 多a g e n t 系统的体系结构1 3 2 2 3 多a g e n t 系统的协商机制1 4 2 2 4 多a g e n t 系统的交互协议1 7 2 3 调度算法1 8 2 3 1 基于规则的调度算法1 8 2 3 2 基于市场机制的调度算法1 9 2 4 本章小结2 2 第3 章多a g e n t 柔性车间调度系统2 3 3 1 柔性车间调度系统2 3 3 1 1 问题描述2 3 3 1 2 系统分析2 4 3 1 3 系统模型2 5 3 2 柔性车间调度系统中a g e n t 结构模型2 6 3 2 1 工件a g e n t 2 6 3 2 2 机器a g e n t 2 8 3 3 基于多a g e n t 的柔性车间调度系统体系结构2 9 3 4 协商机制3 0 3 4 1 工件a g e n t 的协商策略3 1 3 4 2 机器a g e n t 的协商策略3 1 3 5 本章小结3 2 第4 章多a g e n t 柔性车间调度系统设计3 5 4 1 多a g e n t 系统的开发技术3 5 4 2 多a g e n t 柔性车间调度系统的面向对象设计。3 6 v 北京工业大学管理学硕七学位论文 4 3 协商价格函数和算法设计3 7 4 3 1 工件a g e n t 的货币携带函数3 8 4 3 2 机器a g e n t 的等待时间函数3 8 4 3 3 机器a g e n t 的索取成本函数3 9 4 3 4 工件a g e n t 的决策函数3 9 4 4 多a g e n t 柔性车间调度系统具体协商机制4 0 4 5 多a g e n t 柔性车间调度系统通信实现4 2 4 6 本章小结4 4 第5 章仿真实验及结果分析4 5 5 1 仿真实验4 5 5 1 1 仿真实验实例及设置4 5 5 1 2 仿真实现4 5 5 2 实验结果分析4 9 5 2 1 平均延迟时间( m t ) 4 9 5 2 2 最大完工时间( m a k e s p a n ) ：5 2 5 2 3 平均等待时间( m w t ) 5 6 5 3 本章小结5 9 结论与展望6 1 参考文献6 3 攻读硕士学位期间发表的学术论文6 7 致谢6 9 v i 第1 章绪论 1 1 研究背景 第1 章绪论 随着信息技术和经济全球化的快速发展，准时( j u s t i n t i m e ，。j r r ) 生产、 敏捷制造、企业资源计划( e n t e r p r i s er e s o u r c ep l a n n i n g ，e r p ) 、实时企业等理 念应运而生，而生产调度正是这些理念的核心。企业采用合理的生产调度系统， 能使企业缩短其产品制造周期、减少在制品、减少库存、提高其生产资源利用率 除此之外，还能提高制造系统生产率。 所谓生产调度，就是针对某项可以分解的生产任务，探讨在满足某些约束条 件( 例如工期、工艺路线、交货期和资源情况等) 的前提下，通过下达生产指令， 安排其组成部分( 操作) 使用哪些资源，其加工时间以及加工顺序，使生产任务 的执行时间和加工成本最优【1 1 。车间调度问题( j o bs h o ps c h e d u l i n gp r o b l e m ，j s p ) 是具有特殊工件特征和加工环境的最典型和最重要的调度问题【2 】，也是最困难的 组合优化问题之一，它作为多种调度问题的一般模型而著称，常用来检验各种求 解方法的性能。 j s p 一直是一个研究热点，已经取得了丰硕的成果。但由于经典车间调度问 题对工件加工路线做了限定，不能满足生产实际的需要，调度系统需要更高的柔 性和效率，因此柔性作业车间调度问题( f l e x i b l ej o bs h o ps c h e d u l i n gp r o b l e m ， f j s p ) 应运而生。柔性作业车间调度的概念是由b r u k e r 和s c h l i e 在1 9 9 0 年首次 提出，柔性作业车间调度是对经典j s p 的重要扩展，不但继承了j s p 的所有特征， 而且增加了新的特征：一道工序可以在多台机器上加工，该特征体现了工序加工 路线的柔性。f j s p 问题是对经典j s p 问题的重要扩展，它允许一道工序可以在 多台机器上加工，更符合实际的生产环境，也因此f j s p 问题的解决变得更加复 杂。 现有求解f j s p 的文献主要集中在规划方法和元启发式算法上，计算量特别 大，只适合处理中小型调度问题。基于多a g e n t 的调度算法提供了一种动态灵活、 快速响应市场的生产调度机制，该方法使用分布式人工智能中的多a g e n t 机制为 生产组织与运行模式，并通过a g e n t 间的合作特性以及多a g e n t 系统的协调功能 完成生产任务的调度，以达到预先设定的生产目标。而采用多a g e n t 的方法解决 f j s p 问题的关键在于如何选择a g e n t 之间的协商机制。如今得到广泛应用的是 s m i t h i 3 】提出的合同网协议和l i l l 【4 】提出的基于市场的协议。基于市场和a g e n t 的 方法在提高系统整体性能方面具有很多优点，具有很好的速度、稳定性、可扩展 性和健壮性。而且目前基于市场和多a g e n t 的研究非常少，尤其是解决f j s p 的 文献更少。因此用基于市场机制和多a g e n t 的方法研究f j s p 问题有很重要的理 北京工业大学管理学硕士学位论文 论意义和现实价值。 1 2 研究现状 b r u k e r 和s c h l i e 【5 j 最早提出柔性作业车间调度问题，他们首先采用多项式 算法求解了只有两个工件的柔性作业车间调度问题。后来研究学者逐渐提出解决 多个工件的柔性作业车间调度问题的算法，通过对现有文献的分析，这些算法主 要分为分解方法( h i e r a r c h i c a la p p r o a c h e s ) 和集成方法( i n t e g r a t e da p p r o c h e s ) 等 两大类。分解方法的原理主要基于每道工序的加工机器确定后，柔性作业车间调 度问题就转化为经典的车间调度问题。最典型的分解方法就是分配调度法 ( a s s i g n t h e n s e q u e n c e ) ，其中分配就是为每道工序选择合适的机器，调度就是对 机器上的工件进行排序。p a u l i 6 1 ，b 锄鹳【7 】和b r 姐d h n a n e 【8 】都采用这种方法来求 解柔性作业车间调度问题，他们首先采用分派规则解决分配问题，然后用不同的 禁忌搜索法解决后面的排序问题。x i a 9 】利用粒子群算法将工序分配给机器，用 模拟退火算法对机器上的工序进行调度。陈亮【l o 】使用分派规则解决分配问题，使 用基于智能式的启发算法解决调度问题。而集成方法同时考虑了分配问题和调度 问题，并没有把它们分开。m a s t r o l o l l i ，g a m b a r d e l l a 1 l 】，d a u z e r e p e r e s 1 2 】和v a e s s e n s 【1 3 】都应用集成方法解决柔性作业车间调度问题。 除了上述学者采用分解和集成的方法解决柔性作业车间调度问题之外，国内 有些学者主要采用遗传算法，禁忌搜索法和模拟退火等算法来求解柔性作业车间 调度问题。例如杨晓梅等【1 4 】提出了一种遗传算法，张超勇等【1 5 】提出了两级遗传 算法，刘晓霞等【1 6 】则将遗传算法和模拟退火算法相结合，利用遗传算法快速搜索 一组较好的解，然后利用模拟退火算法进行群体寻优。姜思杰等旧提出了基于遗 传和禁忌搜索的优化调度算法。 然而上述这些算法的计算量比较大，不太适合解决大规模的柔性作业车间调 度问题，一些学者开始寻找其他新的解决方法，使用多a g e n t 理论来求解柔性作 业车间调度问题应运而生。 自从s m i t h l 2 1 提出合同网协议之后，研究学者将合同网协议和多a g e n t 理论 结合起来求解柔性作业车间调度问题。例如，w d 等【l8 】考虑了工件选择和机器选 择两方面并基于合同网协议和分派规则，提出了合同网协议交互投标模式。作者 构造了5 种合同网规则，c n p c r 规则，c n p f c f s 规则，c n p e f t 规则， c n p - e d d 规则，c n p s p t 规则。实验环境为15 种工件在9 台机器进行加工， 每个工件必须经过所有机器完成一道加工工序，将这5 种规则与分派规则比较， 以系统加工平均延迟时间为评价标准，c n p e f t 规则调度方法具有最好的调度 性能。 k o u s i s 等【i 州针对柔性制造系统，提出了利用a g e n t 的智能性来动态的选择分 第1 章绪论 派规则进行调度。在他提出的体系结构中，分为一个管理a g e n t 和多个工作单元 a g e n t ，每个工作单元由一台或多台机器组成。工作单元a g e n t 不断地检测是否 有“症状”发生，然后根据这些“症状”和系统的目标函数动态地选择分派规则。 但这种方法并没有真正的应用到实际的柔性制造系统中，作者也只是选择了车间 调度做为实验环境对所提方法进行了实验。 s a a d 掣2 0 】提出了p r ( p r o d u c t i o nr e s e r v a t i o n ) 机制，即每台机器对应一个 存储列表( r e s e r v a t i o nl i s t ) ，存储列表中记录了每个工件的i d 号，工件的开始加 工时间和工件的加工时间。每个时间点上当有新的工件到达或者工件的某道工序 完成加工时，所有的机器想工件提交标书，标书的内容包括最早完工时间和存储 列表的长度。工件对所有的标书进行比较，选择完成时间最早的机器，如果存在 两台或两台以上完成时间相同，则选择存储列表最短的机器。机器将此工件放入 存储列表中。同时作者通过实验验证了其所提的p r 算法的有效性。实验设置为： 车间有9 台相同的机器，工件服从指数分布动态的到达，具有相同的优先级。每 个工件要经过5 台不同的机器进行加工，且加工时间相同。将p r 方法与f i f o ， e d d ，s p t 进行比较，结果显示流动时间( f l o w t i m e ) ，平均延迟，工件延迟数 量和w d 数量都有明显的下降，但l e a d t i m e 并没有减少。 乔兵等【2 l 】提出了一种基于a g e n t 的分布式动态柔性作业车间调度方案。作业 车间调度系统为异构的体系结构，包括工作单元a g e n t ，作业a g e n t 和事件a g e n t 。 整个多a g e n t 系统通过基于合同网协议的招投标机制进行作业调度。 韦文斌【2 z 】等为车间控制系统引入管理a g e n t ，任务a g e n t 和资源a g e n t ，采 用合同网协议确定各个任务和各个资源之间的分配关系，资源代理计算自己完成 任务的奖惩值作为投标值。作者研究的调度系统已经在北京航空航天大学制造研 究所研制开发的制造经理一制造执行系统中运行。 w u 2 3 】提出了一种解决柔性作业车间e t 调度问题的机制。在此机制中，将 工件分为两类，只有一道工序未加工的工件( s o u ) ，和多道工序未加工的工件 ( t o l j ) 。系统中包含工件a g e n t 和机器a g e n t ，工件a g e n t 负责为工序选择合适 的机器，机器a g e n t 负责对工序进行排序，决定工序的开始加工时间。对于s o u 和t o l l ，工件a g e n t 和机器a g e n t 分别用不同的算法。实验环境为5 个工作单 元组成的柔性作业车间，每个工作单元有两台不同速度的并行机器。当目标函数 为w t ，作者提出的多a g e n t 方法优于p r 和s s p r 。 任海英等【2 4 】提出了一种新的分布式多a g e n t 通用计划作业编制体系，称为 “权重式多a g e n t 计划编制系统”( m u t i a g e n ts c h e d u l i n gs y s t e m ，m a s s ) 。并为 体系中每个设备、任务和控制中心设计了计划编制a g e n t ，以计算竞争作业的评 价指数，根据车间的特征决定各a g e n t 的权重，用加权平均方式确定各竞争作业 的最终评价指数。将这种策略应用与j o bs h o p 生产系统的最小交工延迟问题。 任海英，孙宏玲【2 5 】利用多a g e n t 理论，提出了权重式机器选择工件算法和最 北京工业大学管理学硕士学位论文 早完工时间及预测机制的工件选择机器算法。为证实所提方法的有效性，并进行 了大量的仿真实验。他们提出的基于多a g e n t 的柔性作业车间调度算法在加权滞 后和问题上要明显优于传统的分派规则。 王媛【z 6 1 ，刘艳博【2 7 j 以大连奥托技术有限公司设计和丌发的e r p 系统为背景， 建立了多a g e n t 生产调度系统。李贤【2 8 】针对离散制造行业中的j o bs h o p 问题， 实现了基于多工艺路线的多a g e n t 生产调度系统。王艳红等人【2 9 】研究了敏捷制造 环境下制造车间生产过程的动态调度问题，提出了综合运用多a g e n t 技术与规则 调度解决这一动态调度问题的方法。 良好的协商策略是采用多a g e n t 方法求解调度问题时的关键问题。很多研究 学者致力于设计更好的协商策略来解决柔性作业车间调度问题。l i n 3 0 】提出了基 于市场的协议之后，为使用多a g e n t 理论求解柔性作业车间调度问题带来新的思 路。基于市场和a g e n t 的方法是一类源于人工智能领域的技术。这种技术基于一 种假设，这些调度过程是基于市场机制下，每一项工作都要进行投标，且要为所 占用的机器时间付费。 l i n 和s o l b e r g 3 0 提出了基于市场机制的多a g e n t 柔性作业车间调度系统， 在其提出的多a g e n t 系统( m u l t i a g e n ts y s t e m ，m a s ) 框架中将制造系统中的 各个功能和实体( 机器设备和工件等) 都予以a g e n t 化，并采用基于价格机制的 市场模型实现a g e n t 之间的协商。它将每个工件a g e n t 看作买主，带着一定数量 的货币进入市场，购买机器a g e n t 提供的服务，使自己的某些目标达到最大。机 器a g e n t 相当于卖主，它根据自己的状态确定成本，并向工件a g e n t 出售自己的 服务，使自己的收益最大化。工件a g e n t 不断调整自己的目标，机器a g e n t 不断 调整自己的成本，从而达到供求上的均衡，实现彼此间的合作。他们开发了一个 柔性加工路径控制仿真系统( f r c s ) ，采用工件控制器和机器控制器谈判的方式 解决工件分配问题。接下来l i na n ds o l b e r g 3 0 】( 1 9 9 2 ) 文献中提出了一个基于自 治智能体的综合车间控制和仿真系统来探究柔性路径问题。l i n 是最早提出工件 携带一定量的货币进入系统，通过与机器进行谈判以确定分配给哪台机器，她还 提出工件发出标书，以机器为中心和机器发出标书，以工件为中心的两种谈判机 制。 m a c c h i a r o l i ，r 和r i m e m a , s 1 3 1 在l i l l 文献的基础上进行了改进，根据第一种 谈判机制，提出了机器和工件之间谈判时的定价机制，设计了相应的算法并与分 派规则进行了比较，他的算法在系统整体性能方面显示出很大的优越性，但是在 平均延迟、最大延迟等具体目标方面并没有显示出优越性。 t s i w a m o g s a t h a m l 3 2 在m a c c h i a r o l i 文献的基础上进行了改进，提出一种基于 拍卖的谈判机制，并将m a c c h i a r o l i 最初提出的模型中的成本函数进行改进，引 入时间作为首要标准。成本函数中的系数也进行了校正，从而提高了方法的有效 性。仿真结果表明，基于拍卖的方法大多情况下要优于分派规则。 第l 章绪论 k r o t h a p a l l ii j 驯也提出了与l i n 类似的基于市场的车间调度系统，但是他采用 效用理论进行定价，提出了e x p e c t e dv a l u e 、e x p e c t e du t i l i t y 、r a n kd e p e n d e n t e x p e c t e du t i l i t y 和p r o s p e c t t h e o r y 等四种效用函数。此外还设计了三种不同的协 商机制，分别为最小加工时间机制、货币机制和优先处理机制，通过在面向对象 的s w a r m 平台上仿真，结果表明a g e n t 之间的协商机制采用优先处理机制时取 得的效果比较好。 k i m 掣3 4 】提出了与l i n 类似的基于市场的多a g e n t 生产调度系统，只是在定 价机制和目标函数上与l i n 不同。c a v a l i e r i 3 5 】把l i n 提出的基于市场的多a g e n t 生产调度系统与r a b e l o 3 6 】提出的层次型多a g e n t 生产系统进行了比较。实验结 果显示基于市场的多a g e n t 生产调度系统比层次型生产调度系统更具健壮性。 目前，国内对基于市场机制和a g e n t 在调度上的研究也相继开展开来。大连 理工大学的刘艳博【27 】以大连奥拓技术有限公司设计和开发的基于分布式对象技 术的d i s c r e t ee r p 系统为背景，利用多a g e n t 理论，结合企业的生产实际建立了 多a g e n t 生产调度系统( m a s s ) ，并为设计了一些用于在不同类型a g e n t 协商过 程中的决策函数和算法。比如任务a g e n t 的标书评价函数和资源a g e n t 的任务选 择算法。这些决策函数可以辅助各a g e n t 做出更加合理的决策，使其在满足局部 利益的同时也能够使全局性能较优。他采用基于消息报告的协商机制，但是这种 机制不能充分发挥系统中a g e n t 的特性。 南京航空航天大学进行了基于a g e n t 的分布式动态车间调度的研究，提出一 种基于合同网协议投标机制的多a g e n t 分布式动态车间调度方案【3 7 】。 这表明采用基于市场机制和多a g e n t 的方法受到越来越来的研究人员的关 注，但是在柔性调度方面的研究比较少，还需进一步的研究。 1 3 研究方法及主要工作 1 3 1 研究内容 论文采用基于市场和a g e n t 的方法研究f l e x i b l ej o bs h o ps c h e d u l i n g p r o b l e m ，设有两个a g e n t ，分别代表工件和机器。工件a g e n t 带着一定数量的货 币和加工计划进入系统，机器a g e n t 通过提供相应的服务而获得收益。工件a g e n t 和机器a g e n t 之间的协商机制采用基于市场和优先处理的协商机制，工件发出标 书，机器竞标，经过一定轮回的谈判后，工件选择合适的机器进行加工。当工件 的工期非常接近时，工件与所选机器进行谈判，确定是否可以提前加工，并支付 一定的货币，如果当前机器不能满足它的加工要求，工件则重新寻找新的机器。 尽管国内外已有学者对基于市场协议中的价格协商函数进行了研究，但是如 何设计价格协商函数以有效的确定每道工序的加工机器，仍被认为是一个具有挑 北京工业大学管理学硕七学位论文 战意义的课题。论文在基于市场协议的基础上，设计了a g e n t 间的协商策略，并 重新设计了a g e n t 协商时的价格函数以有效的确定每道工序的加工机器，并通过 实验验证价格协商函数的有效性。 1 3 2 研究方法与技术路线图 论文的研究方法是首先采用文献研究法了解目前解决f l e x i b l ej o bs h o p s c h e d u l i n gp r o b l e m 方法的研究现状，在遗传算法、神经网络、蚁群算法和多智 能体等智能求解方法中，a g e n t 以其高度自治性、智能性、协作性、交互性、适 应性等特点，较好的满足了实际车间生产管理的需要，多智能体方法在降低系统 复杂性方面有很大的优势。论文在此基础上引入市场机制，采用基于市场和基于 智能体的方法研究f l e x i b l ej o bs h o ps c h e d u l i n gp r o b l e m ，参考了文献 3 3 】中提出 的价格协商函数，对其进行改进，并设计出基于价格机制的算法，最后采用面向 对象的j a v a 语言编写仿真程序，通过与传统的分派规则进行比较，以验证算法 的有效性。 技术路线图如图1 1 所示： 1 3 3 创新点 图1 1 研究路线图 f i g 1 - 1r e s e a r c hr o a d m a p 本文的创新点在于： 国内外大多采用分派规则与多a g e n t 系统的方法研究生产调度问题，但是采 用市场作为a g e n t 之间的协商策略并且用于解决f l e x i b l ej o bs h o ps c h e d u l i n g 第1 章绪论 p r o b l e m 的比较少。市场协议的关键在于设计良好的价格协商函数。论文主要使 用基于价格机制的市场模型实现a g e n t 之间的协商及采用一种基于机器和工时 定价的方法研究柔性作业车间调度问题，并在此基础上重新设计了a g e n t 间的价 格协商函数，同时采用招投标的方法解决工件选择机器的问题。其次，为实现多 a g e n t 系统，国内外研究学者主要研究面向a g e n t 的程序设计方法，但是这些研 究目前还处于模型的研究上，并没有稳定的产品。a g e n t 在封装性、继承性和多 态性等方面与对象有许多共同之处，因此本文使用面向对象的技术来设计并实现 多a g e n t 系统柔性车间调度系统，此外j a v a 是面向对象的程序设计语言，并且 便于描述和表达a g e n t 的拟人智能性，因此采用面向对象的编程语言一a v a 来 编写仿真程序。 1 3 4 论文主要结构 第一章，绪论。对现有的车间调度的理论与成果进行研究，主要分析了柔性 作业车间调度的研究背景和意义及研究现状，并简述了论文的主要研究方法、文 章的创新点和技术路线图等内容。 第二章，相关理论。详细介绍了a g e n t 的概念、特征，及多a g e n t 系统的概 念及多a g e n t 之间相互合作的相关理论知识，此外还详细介绍了调度的相关算 法。总体上看，第一、二章是本文的基础研究部分，是下面的研究做铺垫。 第三章，多a g e n t 柔性车间调度系统。结合生产实际情况，详细阐述了本课 题研究的具体问题，并运用面向a g e n t 建模方法，建立了工件a g e n t 、机器a g e n t 的结构模型，接着以此为基础建立了一种基于市场机制的多a g e n t 柔性车间调度 系统，同时引入基于市场的协议作为a g e n t s 之间的协商机制。基于市场的协商 机制类似于人的决策方式，容易理解，便于实现。 第四章，多a g e n t 柔性车间调度系统设计。使用j a v a 编写仿真程序设计和 实现了多a g e n t 柔性车间调度系统，并详细阐述了a g e n t 在协商时的价格协商函 数和算法。这些函数和算法有助于a g e n t 的自主决策，并且还能大大减少协商次 数。此外，还详细阐述了本课题的协商机制及a g e n t 之间的通信机制。 第五章，仿真实验及结果分析。以平均延迟时间、最大完工时间和平均等待 时间为目标函数的实际问题设计了一系列仿真实验，并对实验结果进行分析，通 过与传统分派规则的对比，验证所提算法的可行性和有效性，检验其优化性能。 北京t 业大学管理学硕士学位论文 8 第2 章相关理论 第2 章相关理论 a g e n t 是一个软件模块，具有独立的功能，是一个抽象的实体，它能作用于 自身和环境，并能对环境做出反应。a g e n t 应具有知识、目标和能力，具有同其 他a g e n t 进行通信和协同求解的能力。本章将主要介绍本论文研究的理论基础知 识，主要包括：a g e n t 理论、多a g e n t 系统理论及相关的调度算法等。 2 1a g e n t 的相关理论 2 1 1a g e n t 的概念 a g e n t 是一个发展非常迅速的领域。随着分布式人工智能技术、现代计算机 和通信技术的迅速发展，a g e n t 已成为它们发展的必然结果。2 0 世纪7 0 年代初， 美国麻省理工学院的研究人员开展了一系列有关分布式人工智能技术的研究，从 这个时候开始，a g e n t 技术才开始应用于计算机领域【3 引。然而到目前为止，a g e n t 的研究还未完全成熟，关于a g e n t 的定义学术界还