（计算机应用技术专业论文）多agent生产调度系统的设计与实现.pdf

大连理r 人学硕十学位论文 摘要 针对生产调度系统在制造业企业中起到的核心作用，以及经典调度理论存这方面遇 到的困难，本文对多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 生产调度模型( m u l t i a g e n ts c h e d u l i n gm o d e l ，m a s m ) ，将每个任务和资源都对应为一个 a g e n t ，分别称为t a 和r a 。模型中还增加了两个管理a g e n t 对t a 和r a 进行控制。模 型采用混合架构，通过高层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 之间采用基于合同网的协议进行协商，通过多次交互达成协议，得到调度计划。 在协商过程中，r a 收到一批任务的第一个请求后首先等待，j 、段时间，当这批批任务的 工序全部进入等待队列之后，再按照优先级由高到低的顺序安排加j i ：时间；t a 收到其下 所有工序的安排后才开始查看可能出现的重叠。以上几种机制大大减少了a g e n t 之问的通 信次数，提高了系统效率。 本文采用u m l 对模型进行了设计与描述，用j a v a 语吉加以实现，a g e n t 之间使用 r m i 方式进行远程通信，并利用j a v a 多线程的特点实现系统的并行性。由于采用了多 a g e n t 技术，本系统具有固有的分布性与智能性，对于生产环境中的1 扰及其变化具有良 好的适应性和扩展性。此外，本系统可以与企业原有的d i s c r e t ee r p 系统无缝衔接。测 试结果汪明，系统可以为企业提供个较合理的调度，在一定程度上减轻管理人员的负 担，提高工作效率和资源利用率。 关键词：多a g e n t 系统；生产调度；合同网协议；e i 问题 多a g e n t 生产调度系统的没计与实现 d e s i g n a n d i m p l e m e n t o fam u l t i - a g e n t s c h e d u h n gs y s t e m a b s t r a c t a s t u d yo nm o d e l i n ga n di m p l e m e n t i n gf lm u l t i - a g e n ts c h e d u l i n gs y s t e mi sc a r r i e do u t c o n s i d e r i n g t h ec o r ee f f e c to fs c h e d u l i n g s y s t e m i n m a n u f a c t u r i n ge n t e r p r i s e s a n dt h e d i f f i c u l t i e sc l a s s i cs c h e d u l i n gt h e o r i e sm e e t t h e p r o b l e m s e x i s ti nt r a d i t i o n a ls c h e d u l i n g s y s t e m s a r ea n a l y z e df i r s t l yi nt h i sp a p e r , t h e n t h el o g i cr e a s o n i n gm o d e lo f a g e n t ，t h ea r c h i t e c t u r eo fm u l t i a g e n ts y s t e ma n dt h ei n t e r a c t i o n b e t w e e na g e n t sa r es t u d i e dd e e p l y ，c o m b i n e dw i t ht h et h e o r i e st h a th a v eb e e nd e v e l o p e d ，a m u l t i a g e n ts c h e d u l i n gm o d e l ( m a s m ) i sp r o p o s e d ，i nw h i c ha g e n t sa r ec r e a t e df o re a c h t a s k sa n dr e s o u r c e s ，a n dt h e ya r ec a l l e dt aa n dr a r e s p e c t i v e l y t w os u p e r v i s o ra g e n t sa r e a d d e di n t ot h em o d e 】t oc o n t r o lt aa n dr a t h ea r c h i t e c t u r eo f t h i sm o d e li sh y b r i d i nw h i c h h j 曲一l e v e la g e n t sc a i s u p e r v i s el o w l e v e la g e n t st oi m p r o v e t h eg l o b a lp e r s p e c t i v eo ft h er e s u l t a 【t h es a r n et i m e t h ea u t o n o m o u so f a g e n ti sr e g a r d e dt oi n c r e a s et h er o b u s t n e s sa n df l e x i b i l i t y o f t h es y s t e mt h e a g e n t si nt h i sm o d e l h a v ear e a c t i o ns t r u c t u r eo rh y b ds t r u c t u r e a c c o r d i n g t o p r a c t i c en e e d s a g e n t sn e g o t i a t ew j me a c ho t h e rb a s eo nc o n t r a c t - n e tp r o t o c o la f t e rs e v e r a lt i m e s i n t e r a c t i o n s 。t h es c h e d u l i n gp l a nc a nb ep u r s u e d d u r i n gt h en e g o t i a t i o n ，r aw a i l sal i t t l e m o m e n ta f t e ri tr e c e i v e st h ef i r s tr e q u e s to ft h eb a t c h ，t h e r e f o r ei tc a ns c h e d u l ea c c o r d i n g t ot h e p r i o r i t ya f t e r a l l s t e p so f t h i sb a t c hh a v eb e e np u ti n t ot h e q u e u e t ac h e c k st h ec o n f l i c t s b e t w e e n s t e p so n l ya f t e ra l lt h es t e p so f t h i st a s kh a v er e c e i v e da p r o p o s a lf i o mr a t h ea b o v e m e c h a n i s m sc a ng r e a t l yd e c r e a s et h et i m e so fi n t e r a c t i o na m o n ga g e n t sa n di m p r o v es y s t e m e f f i c i e n c y t h em o d e li sd e s i g n e da n dd e s c r i b e du s i n gu m la n di m p l e m e n t e dw i t i lj a v ar m ia n d m u l t i - t h r e a d st e c h n o l o g i e sa r eu s e dt oi m p l e m e mt h ed i s t r i b u t e dc o m m u n i c a t i o na n dp a r a l l e l p r o c e s s i n go ft h es y s t e m t h a n k st ot h em u l t i - a g e n tt e c h n o l o g y ，t h i ss y s t e mi si n h e r e n t l y d i s t r i b u t e da n di n t e l l i g e n t i ta l s oo f f e r sa d a p t a b i l i t ya n de x p a n s i b i l i t ya g a i n s td i s r u p t i o n sa n d c h a n g e si nm a n u f a c t u r i n ge n v i r o n m e n t m o r e o v e r ，t h i ss y s t e mc a l lb ei n t e g r a t e dt ot h el e g a c y d i s c r e t ee r p s y s t e ms m o o t h l y t h et e s to ft h es y s t e ms h o w st h a ti tc a no f f e rar e a s o n a b l e s c h e d u l i n gp l a n ，d e c r e a s et h eb u r d e no fm a n a g e m e n tp e o p l ea n di m p r o v et h ee f f i c i e n c yo f p r o d u c t i o n a n dr e s o u r c e s k e yw o r d s ：m u l t i a g e n ts y s t e m ；s c h e d u l i n g ；c o n t r a c t - n e tp r o t o c o l ；e tp r o b l e m i i 独创性说明 作者郑重声明：本硕士学位论文是我个人在导帅指导下进行的研究 工作及取得研究成果。尽我所知，除了文中特别加以标注和致i 勇j _ 的地方 外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得 大连理工大学或其他单位的学位或证书所使用过的材料。与我一同工作 的同志对本研究所做的贡献均已在论文中做了明确的说明并表j ；了谢 意。 作者签名：型叁日期：也心；f作者签名：“友一日期：也心；f 大连理i ：大学硕卜学位论文 引言 1 课题背景 信息技术的发展深刻影响着现代制造业的牛存环境，使制造业的产品结构和管理模 式发生了深刻的变化，如表0 1 1 所示。消费者对产品个性化、多样化的要求使得相对稳 定的传统市场更加动态多变，以往的大批量生产( m a s sp r o d u c t i o n ) 逐渐转变为大批量用，、 定制( m a s sc u s t o m i z a t i o n ) 圳, 及多品种、小批量的生产模式，基于订单的生产( p r o j e c t b a s e d p r o d u c t i o n ) 成为主流，企业需要更加实时地对相关信息加以掌握和分析。同时，全球经济 一体化的形成和制造系统的分散化使得企业要求新的分布式计划和决策系统，来代替以 往的集中式系统。 表0 1 制造业环境的变化 传统经济时代信息化技术叫代 随着信息技术和经济全球化的快速发展，准时( j u s t i n - t i m e ，j 1 7 r ) 生产、敏捷制造、 e r p 、实时企业等理念应运而生，而生产调度f 是这些理念的核心。然而在当前的制造 业信息系统，尤其是e r p 的实施中，在生产调度方面并没有收到良好的效果。这丰要因 为要实现一个优秀的生产调度系统，不仅需要建立详细的、符合企业实际的生产模型， 而且需要对生产流程加以优化。可是在生产过程的最佳顺序求取过程中，往往遇到非常 棘手的组合爆炸问题，属于不存在多项式优化解法的n p 问题；加之在生产调度中需要 考虑各种复杂的约束条件，需要较高级的数学基础和算法理论，因此这方面的研究还只 是停留在建模和试验阶段。 多a g e n t 生产调度系统的设计与实现 2 0 世纪5 0 年代到8 0 年代，企业主要是通过管理信息系统( m a n a g e m e n ti n f o r m a t i o n s y s t e m ，m i s ) 来完成基本的数据录入、存储传输、加工处理、查询统讨等功能。进入8 0 年代，m i s 进入了决策支持系统( d e c i s i o ns u p p o r t i n gs y s t e m ，d s s ) 领域；刷时，人卜智 b ( a r t i f i c i a li n t e l l i g e n c e ，a i ) 的发展，导致了专家系统( e x p e r ts y s t e m ) 技术在企业信息化方 面的应用，出现了智能制造系统( i n t e l l i g e n tm a n u f a c t u r i n g ) ；在这个时期，还出现r 准时 生产、敏捷制造等概念，阻适应市场的多变性。到了9 0 年代，伴随着i n t e m e t 技术的发 展和电子商务的热潮，在制造资源计划( m a n u f a c t u r i n g r e s o u r c e p l a n n i n g ，m r p i i ) 基础上发 展起来的企业资源计戈l j ( 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 ) 、客户关系管理( c l i e n tr e l a t i o n m a n a g e m e n t ，c r m ) * d 供应链管理( s u p p o r tc h a i nm a n a g e m e n t ，s c m ) ，使企业把客户需求 和氽业内部的经营活动以及供应商的资源融合在起，出现了大型的集成的信息系统。 进入2 1 世纪，又出现了实时企业( r e a l t i m ee n t e r p r i s e ，r 1 1 e ) 和子整体制造系统( h o l o n i c m a n u f a c t u r i n gs y s t e m ，h m s ) 的概念，以提高系统的快速反应能力、适应性和柔性。顾客 需求的个性化、多样化，使得客户化、小批量、多品种、快速交货的生产要求不断增加， 传统集中式、层次化的制造模式越来越不能满足产品创新和快速响应市场等全球竞争的 要求。 制造型企业的生产方式从产品类型和生产工艺组织方式上，可分为流程生产行、i k 和 离散制造行业。典型的离散制造业主要包括机械制造、电子电器、汽车制造等行业，这 些企业既有按定单生产，也有按库存生产，既有批量生产、单件小批量生产、大批最流 水生产和大规模定制，也有上述类型的混合制造模式。根据客户定单介入生产过程的不 同又分为按库存生产、按定单装配、按定单生产和按定单设计的管理模式。本文主要针 对的是离散制造业中的小批量客户定制生产，需要根据客户的订单进行设计、生产和装 配。 生产调度系统作为制造系统的有机组成部分，一直是学术界研究的热点，更是e r p 系统的核心，调度的合理性直接影晌到整个系统的性能和质量。目前的e r p 系统中与牛 产计划相关的部分主要是主生产计划子系统、能力需求计划予系统管理了系统，缺少对 生产的详细排产。生产调度这个e r p 系统的关键环节现在已经成为e r p 的瓶颈，是世界 性的技术难题 2 。一个优秀的生产调度系统，不仅需要建立详细的、符合企业实际的生 产模型，而且需要对生产流程加以优化。而这个难题的关键是算法，对此，固外已经做 出了很多年的努力，其研究成果已形成了多个a p s ( a d v a n c e d p l a n n i n ga n d s c h e d u l i n g ，高 级计划调度) 产品，发展出了几十种先进生产排产算法，比较常用的有启发式图搜索法、 2 大连理工大学硕士学位论文 禁忌搜索法、神经网络优化、遗传算法等，这些算法各有优劣，可用在不同场合。2 0 世 纪8 0 年代，m a s 被引入生产调度领域，多代理调度系统( m u l t ia g e n ts c h e d u l i n gs y s t e m ， m a s s ) 具有良好的分布行、适应性和鲁棒性，目前已经引起了学术界的广泛关注，并取 得了一些成果，但主要还是停留在建模和实验阶段。 2 m a s s 的研究现状 在经典调度理论中，调度问题仅仅被看作组合优化问题，致使其在实际生产中的应 用受到了较大的局限。2 0 世纪8 0 年代，人工智能的蓬勃发展为生产调度注入了新鲜的 血液，进化算法、禁忌搜索算法、人工神经网络、模拟退火算法等得到了广泛的研究， 并取得了丰硕的成果，应该说，这方面的经典调度理论已经比较成熟了，但是在实际应 用中的效果并不理想，其原因可以归纳为模型过于简化、方法过于单一、适用范围狭窄 等。分布式人工智能( d i s t r i b u t e da r t i f i c i a li n t e l l i g e n c e ，d a i ) 的发展促使生产调度系统从传 统的集中式转向分布式，其中m a s 技术在调度研究领域的应用研究中日益活跃起来，并 且开始成为一个重要的研究方向。在调度系统中应用多a g e n t 技术，主要是针对不确定的 和不断变化的制造系统环境下比较复杂的调度问题，尤其是那些短期的、敏捷性要求较 高的动态调度。相对于传统的调度方法和系统，m a s s 具有较好的分布性、实时胜、健 壮性和适应性。 国外对于m a s 的研究起步较早，大约在2 0 世纪8 0 年代m a s 技术逐渐渗透到调度 领域【3 】。到2 0 世纪9 0 年代后，对m a s s 的研究呈现迅速增长的趋势，很多文献都提出 了基于多a g e n t 的调度模型，他们通常把调度行为中的物理实体，如作业、制造设备、运 输设备等，映射为a g e n t ，并赋予它们一定的信念、状态、愿望、规划，通过a g e n t 之间 的协作对问题进行求解。如文献【4 】在提出的m a s 框架中，将制造系统中的各个功能和 实体( 如资源、任务、运输工具等) 都映射为a g e n t ，并采用基于价格机制( p r i c em e c h a n i s m ) 的拟市场模型( m a r k e t - l i k em o d e l ) 来实现a g e n t 之间的协商。也有的研究者将a g e n t 对应为 一个过程，如文献 5 】贝0 将遗传算法封装到a g e n t 中，用于求解c i m s ( 计算机集成制造系 统) 中的j o b - s h o p 问题( 异序生产问题) 。文献【6 】提出了以一个任务a g e n t 和多个资源a g e n t 为核心的柔性制造系统调度框架，并使用了改进的合同网策略。 进入2 1 世纪，对m a s s 已经形成一股热潮，并且更加细化、更加具体。文献【7 1 采 用层次化架构，将制造资源映射为m r a ( m a n u f a c t u r i n g r e s o u r c e a g e n t ) ，每个m r a 和一 个a g e n t 机器接口a m i ( a g e n tm a c h i n ei n t e r f a c e ) 组成一个简单联盟s c ( s i m p l e c o n s o r t i t m a ) 。其中m r a 专注于协商，a m i 则专注于和车间控制器之间的接口，将控制 一3 - 多a g e n t 生产调度系统的设计与实现 器的功能向外发布。多个s c 又可以组成复杂联盟c c ( c o m p l e xc o n s o r t i u m ) 。文献 8 】使 用分布式多a g e n t 方法提出了一个协作的项目调度和管理系统架构。该系统分为三层架 构：首先是一个遗留系统a g 朗h a g e n t ( l e g a c y s y s t e m ) ，它将遗留系统与整个项目调 度和管理系统架构进行打包和集成，l - a g e n t 与系统其它组件交换的信息有产品零件规 格、用户定单中的支付日期和关于工程变化的信息；一个l - a g e n t 与多个项目a g e n 卜一 p - a g e n t ( a g e n t f o rp r o j e c tm a n a g e m e n ta n ds c h e d u l i n g ) 交互，p - a g e n t 根据用户订单的信息 配置新的项目，根据工程规格和专家经验初始化一些必要的参数，此外还要进行项目调 度和分布式资源能力的分析和平衡；最下面一层是若干d - a g e n t ( a g e n tf o rp r o j e c t m a n a g e m e n ta n ds c h e d u l i n g ) ，d a g e n t 位于各制造节点上，主要用于为各个制造资源 ( m a n u f a c t u r i n gr e s o u r c e ) 分配生产任务，它们与p - a g e n t 进行通讯以更有效的利用资源并 满足项目的支付日期。文献 9 】着重研究了两种a g e 时机器a g e n t ( m a ) 和工件a g e n t ( p a ) 。 m a 是与制造业工厂中在车间执行的作业相关联的软件控制者。m a 的任务是为每个要 在这个相关联的机器上加工的工件指定一个优先级( 价格) ，它根据价格策略出售操作。价 格策略依据以下因素：如当前负荷、上个工件和下一工件的安装时间、估计的运送时 间等。m a 的目的是使利润最大，并使安装时间和空闲时间最少。p a 的目的是获得所要 求的操作，并尽可能缩短工件的加工时间，同时使费用最低。该文在p a 的价格评价和 m a 的定价策略中都用到了模糊集理论进行多目标决策。文献【1 0 】没计了一种用于反应式 制造条件下的基于多a g e n t 的控制策略架构，该系统中包含四种管理a g e n t ：资源管理 a g e n t ( r e s o u r c em a n a g e ra g e n t , r m a ) ，产品管理a g e n t ( p r o d u c tm a n a g e ra g e n t , p m a ) ，任 务管理a g e n t ( t a s km a n a g e ra g e n t , t m a ) 和执行管理a g e n t ( e x e c u t i o nm a n a g e ra g e n t , e m a ) 。管理a g e n t 之间相互交互以实现前面提到的目标。在每个管理a g e n t 的下面，还 有多个子a g e n t 供它支配，如过程a g e n t ( p r o c e s sa g e n t ) ，机器组a g e n t t w l a c h i n eg r o u p i n g a g e n t ) 和优化a g e n t ( o p t i m i z a t i o n a g e n t ) 。文献【l l 】针对e t 调度提出了一种m a s s 。 国内对于多a g e n t 系统的研究起步于9 0 年代。如文献 1 2 】在1 9 9 7 年针对日益突出的 电力系统智能“孤岛”闯题，基于已有的三个独立的运行于电力调度中心的专家系统， 研究了电网调度管理多a g e n t 系统，分析了m a s 的成员及其协作关系，给出了能集成电 力系统中现有智能软件的m a s 的实现框架和协作问题求解方法。1 9 9 8 年中国科学院技 术研究所研制了多主体开发工具a o s d e ( a g e n to r i e a t e d s o i t w a m d e v e l o p i n g e n v i r o n m e n t ) j 1 3 。该系统用j a v a 编写以保证主体的可移植性和异构环境下的互操作性， 并支持i n t e m e t 上的基于主题的分布式计算。a o s d e 有四部分组成：主体通信语言s a c l ， 正 大连理工大学硕士学位论文 主体描述语言a d l ，通用主体模板和主体服务器。2 0 0 0 年以后关于m a s s 韵文献大量 出现，如文献 1 4 】研究了针对敏捷化调度的特殊要求，提出了综合运用多代理机制与 规则调度实现敏捷化制造车间生产过程动态调度的方法，建立了基于多代理生产组织 和运行模式的生产过程动态调度系统框架结构，研究了在多代理结构的基础上实现规 则调度的方法，创建了适应实际生产环境的代理的模型结构，并以一类敏捷加工车间 动态调度的仿真研究说明所提出方法的思路和可行性。文献0 5 在复杂适应系统和组 织学习理论的基础上，探讨了一种基于组织学习的自适应系统体系结构。在这种体系 结构中，通过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 调度系统。 目前对m a s s 研究的焦点主要集中在a g e n t 之间的协商机制。如a n t o n i ob o c c a l a t t e 和a n d r e ag o z z i 在文献 1 6 q 提出了种扩展的、启发式的协商机制，并在协商中为每个 任务a g e n t 赋予一个初始的虚拟货币，代表它们的优先级。文献【1 7 】着重讨论了a g e n t 之 间的内部依赖( i n t e r d e p e n d e n c y ) 。文献 9 在协商中引入了模糊集和模糊逻辑理论( f u 盟y s e t s a n d f u z z y l o g i c ) ，在工件a g e n t 的价格评价和机器a g e n t 的定价决策中对多个模糊集 进彳亍。t 模( t - n o r m ) 。以往的调度方法主要是将市场机制与a g e n t 的局部决策计划( 1 0 c a l d e c i s i o ns c h e m e ) 相结合 1 8 ，1 9 ，2 0 ，2 1 ，近年来，这方面的研究又引入了拍卖与拉格朗日 松弛( l a g r a n g i a nr e l a x a t i o n ) 的结合 2 2 ，2 3 ，2 4 ，2 5 ，2 6 。 3 课题描述及研究意义 根据当前e r p 向小型化发展的趋势，以及我国制造业的蓬勃发展，本课题在本实验 室为大连奥托技术有限公司设计和开发的基于分布式对象技术的d i s c r e t ee r p 系统的基 础上，构造了一个基于多a g e n t 的生产调度系统。大连奥托技术有限公司是一家以生产汽 车配件为主的中小型离散制造业企) k ( d i s c r e t em a n u f a e t u r k n 4 j ) ，其生产方式是基于订单的 生产。订单的规模往往较小，而且品种繁多，因此具有业务多变、管理灵活等特点。而 这些特点恰好需要前面提到的现代管理思想加以解决，包括敏捷制造、实时企业等。因 此对该公司调度系统的研究和开发，具有较强的普遍性和社会意义，也是对我国中小型 离散制造业信息化系统的很有意义的尝试。 公司现有系统主要是对生产任务的计划开工时间加以预测，具备粗能力需求计划 ( r o u g h - c u tc a p a b i l i t yp l a n n i n g ，r c c p ) 的功能，但不能将生产任务加以调度，也不具备优 5 多a g e n t 生产调度系统的设计与实现 化功能，不能充分的解决生产部的调度安排问题，总调度对生产任务的安排仍然具有较 大的随意性和不合理性，生产资源不能得到充分的利用，对于生产中的突发事件，如设 计更改、设备损坏等不能很好的应对。正是基于这种考虑，本文希望在已有的e r p 模块 的基础上，建立一个新的具有一定的分布性、智能性和实时往的生产调度系统，该系统 将具有较好的适应性和健壮性，可以随时感知外部环境的变化并做出反应；总调度可以 对系统得到的结果加以调整。在具有一定智能性的基础上，系统将据此得知用户的偏好， 并应用到以后的调度安排中。 本文对a g e n t 及m a s 的推理模型进行了一定的研究，建立了符合项目实际情况的系 统架构，提出了一种可以大幅度减少协商次数的协商策略；在论文的最后，还对该系统 进行了实现，一些关键的技术问题得到了解决。本课题的研究意义可以归纳为以下几点： 1 ) 符合我国当前制造业信息系统的发展趋势 近年来，我国带4 造信息系统需求呈增长态势，然而，大型制造企业管理信息系统建 设主要集中在财务管理、管理信息系统( m 【s ) 、办公自动化系统( o a ) 等初级应用方面，众 多名牌e r p 系统也无法做到对生产进行详细排产，远未达到与生产融合的高度。与当前 b o m - m r p 的简单运算和进销存财务功能相比，生产计划系统将成为连接计划管理与车 间生产的纽带，对企业信息化系统的建设起关键作用。本系统是基于m a s 的，具有固有 的分布性和并行性，符合管理经营信息系统从边缘应用向高端应用发展的趋势，调度系 统对现有信息的充分利用将为企业实现实时企业的提供有力的支持。目前很多国外企业 已开始研制结合a p s ( a d v a n c e dp l w i n ga n ds c h e d u l i n g , 高级计划调度) 核心功能的e r p 软件，拥有这种功能的e r p 公司在市场竞争中占有很大优势。 2 ) 关注工序执行顺序的e 厂r 调度 现有大多数关于e 厂r 问题的文献将延迟量与提前量都作为决策变量，而在本文研究 的问题中将到期1 3 作为约束变量，即延迟量不可以大于零；本文在注重交货时间的同时， 也尽量使完成时间接近到期日以减少库存。这是达到准时制造和敏捷生产的前提条件。 对于延迟量大于零的任务，本模型通过t m a 对任务的调整及外协来加以解决。 以往对f i r 调度研究的对象主要是一组互不相关的作业j = 1 ，2 ，n ，目的是将它们 安排到m 台机器上并使系统代价最小。在本文研究的问题中，被调度的对象是将一组互 不相关的任务t = l ，2 ，n ，每个任务都有一个工序序列，这些工序之间不能打乱顺序， 调度目的是将这些工序安排到m 类资源上，同时使系统的代价最小。这个问题所有可能 的解有! ) ”个，属于n p 困难问题。这类问题到目前为止并没有被广泛研究。由于当前 6 大连理工大学硕士学位论文 制造业生产多为拉动式生产，注重供、产、销几个环节的紧密结合，阻此e t 调度具有 积极的现实意义。 3 ) 针对动态调度问题 调度问题可以被分为反应式的( r e a c t i v e ) 和预动式( p r e d i c t i v e ) 。前者在静态环境中进 行，在初始时刻就可以得到所有的任务，它们的加工时间也是确定的和可知的，机器或 者其它资源在整个调度过程中都是可用的；而后者是在动态环境中进行的，任务随机到 达，加工时间总的来说并不是确定的，有可能随机出现不可预料的事件，如机器故障和 维修、任务取消或更改等。 在本文关注的中小型离散制造业中，任务往往是分批下达的，并且在生产过程中任 务的到期日等有可能发生变化，因此属于动态环境中的调度。对于这种问题的解决方法 可以分为两种：一种是加入作业调度中，已 0 0 bd i s p a t c h i n g ) ，这是彻底的反应式调度；另 一种则是在出现中断( d i s r u p t i o n ) 时通过控制策略对以前的调度进行调整 2 6 】。本文采用的 是第二种方法。 4 ) 对m a s s 进行了有意义的探索 。对a g e n t 和m a s 的研究和应用是当前学术界的热点问题。自2 0 世纪8 0 年代m a s 技术编渗透到调度领域后，对m a s s 的研究一直呈献迅速增长的趋势，形成了异构型 ( h e t e r a r c h i c a l ) 和层次型( h i e r a r c h i c a l ) 两种典型的组织结构。随着分布式人工智能在基础 性研究方面与应用性研究方面的进步，不同种类、不同自治实体之间相互合作的分布协 同式控制方法展现了巨大的应用潜力。对m a s 系统的研究涉及人工智能、分布式计算、 社会科学、经济学、哲学、逻辑学、知识工程等多个领域，具有深刻的学术意义。虽然 关于m a s s 的文献多不胜数，但是真正加以实现的却很少。本文不仅对系统进行了详细 的建模和设计，而且予以了实现，对于m a s s 的研究起到了一定的推动作用。 5 ) 与企业现有系统无缝连接 本课题是基于本研究室以往开发的d i s c r e t ee r p 系统，研究和服务的主要对象是大 连奥托技术有限公司，但也具有一定的普遍性，适合大多数中小型离散制造业企业。公 司原有的d i s c r e t e e r p 系统包含若干e r p 的核心模块，如物料清单i l l o f m a t e r i a l s ，b o m ) 管理模块、物料需求计戈l j ( m a t e r i a lr e q u i r e m e n tp l a n n i n g , m r p ) 模块、粗能力计划模块 ( r o u g h - c u tc a p a b i l i t yp l a n n i n g ) 、生产计划模块和车间跟踪模块等，但是缺少主生产计划， 只能为总调度安排生产提供有限的参考。因此，我们在现有系统的基础上进一步开发生 产调度系统，一方面节省了重新调研和设计的时间，另一方面可以利用现有的数据库和 7 多a g e n t 生产调度系统的设计与实现 已有模块，通过一定的整合，就可以投入使用，大大减少的开发的时间、风险和费用。 现在两个系统可以无缝衔接。 8 大连理工大学硕士学位论文 l 传统生产调度系统及其发展 1 1 生产调度术语 生产调度着眼于研究解决生产组织过程中的时间和资源等的合理安排问题，目的是 提高企业的劳动生产率和设备利用率，缩短生产周期，加速流动资金周转速度，降低产 品成本等 2 7 。生产调度中经常遇到一些术语： 1 任务：指对一批相同零件的加工，包括该零件的所有工序。一种零件可以对 应多个任务。 2 工作中心：指能够完成一个特定工序的一组资源，通常包括多个设备。 3 处理机：即用于加工零件的设备( 机器) 。在多机排序问题中，如果所有的处 理机都具有相同的功能，称它们为同类机或平行机( p a r a l l e lm a c h i n e ) 。同类机按处理 速度又分为三种类型：如果所有的处理机具有相同的速度，称之为同速机；如果处理 机的速度不同，但是每个处理机都是常数，不依赖被加工的任务，称它们为恒速机； 如果处理机的速度依赖加工的任务，则称之为变速机。 对调度问题的描述通常包括下面三个方面： 1 机器和任务的数目：这里的机器指用于加工零件的资源。机器和任务的数目 决定问题的规模大小，影响到问题求解时算法的选择。根据机器的数目可以将调度问 题分为单机问题和多机问题。根据需要加工的零件的工艺的不同，多机问题又可分为 流水线生产问题、异序作业问题、开放作业问题和柔性流水作业问题。如果每个作业 需要在每个处理机上加工，而且每个作业的工序也相同，即在处理机上加工的顺序相 同，则称之为同顺序生产或流水生产( f l o ws h o p ) 。如果每个零件需要在每个处理机上 加工，每个作业有自己的加工顺序，称为异序生产( j o bs h o p ) ，也叫混流生产。如果每 个零件需要在每个处理机上加工，每个零件可按任意顺序加工，把它称为自由顺序生 产或开放生产( o p e ns h o p ) 。多处理机中，更复杂的一种情况是柔性流水生产( f l e x i b l e f l o w s h o p ) ，它是流水生产和平行机的推广。 2 工艺约束：每项任务都需要按照它的工艺路线依次完成各道工序。 3 目标函数：调度问题涉及到了产品的交货期和成本等诸多因素，因此是个 多目标决策问题。通常最主要的目标有两个：基于时间的目标和基于成本的目标，此 外还可能包括加工质量等因素。 1 2 制造业的发展 9 多a g e n t 生产调度系统的设计与实现 近三十年来，随着经济全球化和信息技术的发展，在制造行业出现了很多新的理念， 下面对这些新出现的概念加以解析，以更好的了解生产调度系统的需求。 1 准时( j u s t i n t i m e ，j i t ) 生产：准时生产起源于本世纪7 0 年代的日本。j i t 认为，一个企业中所有的活动只有当需要进行的时候才进行，才不至于造成浪费。传 统的生产系统采用的是由前向后推动式的生产方式，而j r r 是一种拉式管理，由顾客 需求开始，按照订单一产成品一组件一配件一零件和原材料的顺序安排计划，最后到 供应商。整个生产是动态的，逐个向前逼进的。上道工序提供的要正好是下道工序所 需要的，且时间上准时，数量上正好。j i t 系统要求企业的供、产、销各环节紧密配 合，大大降低了库存，从而降低成本，提高了生产效率和效益。 2 敏捷制造( a g i l em a n u f a c t u r i n g ，a m ) ：敏捷制造起源于美国国会于1 9 8 6 年要 求美国国防部拟定的一份发展制造技术的长期规划，其目的是以提高美国企业的全球 竞争力。1 9 9 1 年美国里海大学在研究和总结美国制造业的现状和潜力后，发表了具 有划时代意义的“2 1 世纪制造企业发展战略”报告 2 8 】，提出了敏捷制造和虚拟企业 的新概念，其核心观点是除了学习日本的成功经验外，更要利用美国信息技术的优势， 夺回制造业的世界领先地位。敏捷制造将柔性的先进制造技术，熟练掌握生产技能、 有知识的劳动力，以及促进企业内部和企业之间的灵活管理三者集成在一起，将以往 制造单纯注目于生产过程转变为以市场为导向的产品实现过程，利用信息技术对千变 万化的市场机遇做出快速响应，最大限度地满足顾客的需求，并有机融合了质量管理 的丰富内涵。 3 企业资源计划( e n t e r p r i s e r e s o u r c e p l a n n i n g ，e r p ) ：就目前而言，企业开展信 息化建设的主要工作即实施e r p 系统。e r p 应用程序软件包是一套事先做好的、完 备的集成应用程序模块，它对应于企业的所有业务功能，并且具有高度的灵活性，能 够对软件包中的各种功能进行动态配置和定制，以满足企业的特殊需求。实施e r p 可以产生以下的经营优势和技术优势 2 9 】：( 1 ) 协调和优化不同部门的目标之间的冲 突：( 2 ) 规范企业各部门和站点的业务流程以提高他们的效率及实践能力；( 3 ) 把职能 导向的组织转变为更加基于团队的、跨职能和流程导向的组织，企业成为更加灵活、 扁平化和高度一体化的组织；( 4 ) 提供一个反应迅速的媒介以保证各种业务改进程序 和方法的实施。包括流程创新、流程改进、业务流程等。 4 实时企业( r e a l t i m ee n t e r p r i s e ，r t e ) ：实时企业是世界知名的r r 咨询顾问公 司g a r t n e r 在经过大量不同背景、不同学科的分析员长期的调查研究，在2 0 0 2 年底总 1 0 大连理工大学硕士学位论文 结归纳出的业务概念。g a r t n e r 将实时企业定义为：通过使用最新信息来积极地消除 其关键性业务流程中的管理与执行中的延迟，从而展开竞争的企业。实时企业的内涵 是充分而深刻的利用现代信息技术和管理手段，使业务和生产更加灵活。实时的企业 内部和外部信息，将为企业管理者提供决策的合理依据：通过对原有信息系统的集成， 优化供应链管理，对客户需求进行快速反应，缩短从原材料定购到产品发货的时间周 期。实施实时企业的关键有以下四点：( 1 ) 掌握实时信息，消除关键业务的延迟；( 2 ) 事件驱动；( 3 ) 业务集成，协同商务，集中管理；( 4 ) i t 支持。 5 子整体制造系统( h o l o n i c m a n u f a c t u r i n gs y s t