（控制科学与工程专业论文）基于multiagent的铝型材表面处理自动生产线的动态调度.pdf

摘要 随着市场经济的发展，制造企业面临一系列的挑战，客户对产 品的质量要求越来越高，产品价格由于竞争而降低，并迫切要求企 业降低生产成本，增强企业的竞争力。 生产调度是制造系统中一个重要的环节，正确处理好车间调度 问题，可以为企业节约大量的人力、物力，使制造设备和资源可以 得到更加充分地利用，提高企业的生产效率，增强企业的竞争力。同 时由于车间生产调度问题是一个典型的n p h a r d 问题，对它的研究 具有很高的理论意义和实际意义。 本文首先深入研究了m u l t i a g e n t 理论，然后以南平铝厂的铝型 材表面处理自动生产线为研究对象，将m u l t i a g e n t 技术应用于该生 产线的生产调度之中。建立了基于m u l t i 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 ，重点分析了这四种智能体间的通信和协商机制，研究了 一种基于合同网的招标一投标机制，调度优化通过一个综合指标来 实现。最后运用l a bw i n d o w s c v i 开发出仿真系统，通过仿真实现 系统生产调度的优化，仿真系统的开发对生产实际具有重大的指导 意义。该调度算法的研究对优化和改进车间调度算法，具有重要的 参考价值。同时能够充分发挥设备的可利用性，提高调度速度，增 强企业生产效率，最大限度的获得经济效益。 关键词：生产调度，多智能体，合同网协议，招标一投标机制，仿 真系统 a bs t r a c t w i t ht h ed e v e l o p m e n to ft h em a r k e te c o n o m y , m a k i n gi n d u s t r y m a yf a c eas e r i e so fc h a l l e n g e s t h eq u a l i t yo fc l i e n t s d e m a n di sm o r e a n dm o r eh i g n ，b e c a u s et h ec o m p e t i t i o n ，i tr e d u c et h e p r i c eo ft h e p r o d u c t i o n ，a n dp r e s sf o rt h ei n d u s t r yt of a l lt h em a n u f a c t u r ec o s t ，a n d e n h a n c ei t sc o m p e t i t i o n p r o d u c t i o ns c h e d u l i n gi sa ni m p o r t a n ti n g r e d i e n ti nt h em a k i n g s y s t e m ，i fd e a l i n gw i t ht h ep r o b l e mo fp r o d u c t i o ns c h e d u l i n gw i t ht h e r i g h tm e t h o d ，i tw i l ls a v eam a s so fp e o p l ea n ds u b s t a n c e m a d et h e m a n u f a c t u r ee q u i p m e n ta n dr e s o u r c e g e t t i n ge n o u g hu t i l i z e ，i m p r o v et h e e n t e r p r i s e sp r o d u c ee f f i c i e n c y , a n de n h a n c et h ei n d u s t r y sc o m p e t i t i o n a tt h es a m et i m e ，t h ep r o b l e mo fp r o d u c t i o ns c h e d u l i n gi sat y p i c a l n p h a r dp r o b l e m ，s oi th a si m p o r t a n tm e a n i n gi nt h e o r ya n d p r a c t i c a l i t y t oi n v e s t i g a t e f i r s t ，t h ep a p e ri n v e s t i g a t et h em u l t i a g e n tt e c h n o l o g y , a n dt h e n t a k et h es u r f a c e d i s p o s a l e da u t o m a t i cp r o d u c t i o nl i n ei nn a n p i n g a l u m i n i u mw o r k sa st h er e s e a c h o b j e c t ，a p p l y t h e m u l t i a g e n t t e c h n o l o g yt ot h ea u t o m a t i cp r o d u c t i o nl i n e i te s t a b l i s h e daf r a m e w o r k m o d u l es y s t e m ，w h i c hb a s e do nm u l t i a g e n tt e c h n o l o g y , t r a n s f o r m e d t h e c o m p l i c a t e dp r o b l e mo fp r o c u c t i o ns c h e d u l i n gt ot h em a t t e ro f m a n a g e n ta g e n t 、p r o c e s sa g e n t 、w o r k p i e c ea g e n ta n dt r a n s p o r ta g e n t ， a n a l y s e dt h ef o u ra g e n t s c o m m u n i c a t i o na n dn e g o t i a t i o n ，i n v e s t i g a t ea k i n do fm e c h a n i s mb a s e do nc o n t r a c tn e tp r o t o c o lo fi n v i t e p u b l i c b i d d i n gm e c h a n i s m ，a c t u a ls c h e d u l i n go p t i m i z eb yas y n t h e s i si n d e x l a s t ，t h ep a p e rd e v e l o p st h es i m u l a t i o ns y s t e mu s i n gl a bw i n d o w s c v i ， i ti ss i g n i f i c a n tf o ra c t u a lp r o d u c t i n gt oo p t i m i z et h es y s t e ms c h e d u l i n g m e t h o dt h r o u g hs i m u l a t i o n t h er e s e a c ho ft h i s s c h e d u l i n ga l g o r i t h m w i l l o p t i m i z e t h e w o r k s h o pa l g o r i t h m ，a n d m a d e g r e a t c o n s u l t s i g n i f i c a n c e ，a tt h es a m et i m e ，i tw i l la v a i lo fa l lt h ee q u i p m e n t ，o b t a i n t h em a x i m u m e c o n o m y b e n e f i t 1 i k e yw o r d s ：p r o d u c t i o ns c h e d u l i n g ，m u l t i - a g e n t ，c o n t r a c tn e t p r o t o c o l ，i n v i t ep u b l i cb i d d i n gm e c h a n i s m ，s i m u l a t i o ns y s t e m l l i 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名銎堡邀 日期：4 年上月堑日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 作者虢监导师签名皿嗍争年月日 中南人学硕士学位论文 第一章绪论 1 1 引言 第一章绪论弟一早珀t 匕 由于铝具有重量轻、易成型、强度高、耐蚀性好等特点而获得广泛的应用。 以铝代钢、铜和木材成为当今世界的发展趋势。中国有色金属加工工业协会轻 金属分会发布了2 0 0 3 年铝加工企业产量统计结果，西南铝业集团有限公司等 l o 家企业位居前列，铝材产量总计为7 5 2 4 万吨，占全国铝材产量的2 0 ；产 量3 万吨及其以上的企业达到2 5 家，中国铝材产业集中度进一步提高。 2 0 0 3 年1 0 大铝型材生产企业依次为辽宁忠旺1 0 3 5 万吨，广东凤铝5 8 4 万吨， 广东坚美5 0 1 万吨，广东兴发4 8 7 万吨，台山金桥4 1 6 万吨，亚洲铝业4 0 2 万吨， 淄博松竹4 0 0 万吨，南山铝业3 5 8 万吨；苏州罗普斯金3 5 万吨，福建南平铝业3 0 8 万吨【1 1 。 从铝锭到铝型材的一般生产工序为铝锭铸棒挤压表面处理。铝的表面处理 方法很多，如，氧化着色、粉末喷涂、电泳涂漆等【2 】。氧化处理可采用化学氧化 或阳极氧化，形成一层致密的氧化膜，从而提高铝型材的耐蚀性、耐磨性及耐候 性。着色处理【3 1 有化学染色法、自然着色法和电解着色法。其中，电解着色是将 阳极氧化后的铝制品置于含有重金属盐的电解质溶液中作为一个电极，对极可以 是碳棒、不锈钢。通以交流电，溶液中的金属离子渗到膜孔隙底部，还原沉积使 膜层着色。 电泳涂漆的基本原理1 4 j 是将经过阳极氧化处理的铝型材作为阳极浸渍在水 溶性涂料中，在铝材和对应的阴级端通以直流电，阴离子树脂微粒朝阳极( 铝材) 移动即电泳。由于电泳移动，树脂微粒电析沉积在铝材表面上，推动电荷而形成 一层均匀的树脂膜，即电析沉积；水分从树脂涂膜中逸出，涂膜充分地聚集在一 起，即电渗；最后，在一定条件下，进行烘烤固化，就在铝材基体表面上涂敷一 层坚而硬的漆膜。电泳涂层透明度高，金属质感好，高耐候性和耐蚀性，是最具 发展前景的表面处理技术。并且电泳涂装法工艺实施容易，只要在原生产线上增 加电泳槽和若干个水槽即可与氧化着色形成流水生产线。 南平铝业有限公司1 9 9 8 年从意大利渥太尔公司引进的万吨生产线是一条 铝型材氧化着色生产线，增加了电泳槽后，形成的铝型材电泳柔性生产线；另 外还有一条单独生产氧化材的生产线。 随着人们生活水平的不断提高与建筑业的飞速发展，室内外装饰的档次也 越来越高，人们已不满足于单一色调的铝合金装饰材料。因此，铝型材花色品 中南大学硕十学位论文 第一章绪论 种呈现出多样化与个性化的发展趋势。总的来说，建筑业对于铝型材表面处理 提出的新要求【5 j 是： 1 ) 表面更加均匀一致，没有缺陷和条纹； 2 ) 颜色更加丰富多样，突破单一古铜色系； 3 ) 使用性能更加优越，抵挡大气污染和腐蚀； 4 ) 产品质量更加稳定； 5 ) 环境保护更加完善。 因此，未来铝型材将向以下五个方向发展【6 】： 1 ) 磨砂面铝型材。机械预处理是消除表面条纹最有效和经济的方法。相比 传统的化学处理法，机械预处理可以完全去除表面条纹，而且经机械预处理的 铝型材表面的某些物化性能，如表面硬度抗砂浆能力均有不同程度提高。机械 预处理难于处理复杂形状的型材，只能处理外露的平表面，好在型材的装饰面 通常是平表面。 2 ) 多色调表面型材。目前铝型材单调的银白色和茶色已不能满足与建筑物 外墙装饰面砖、外墙乳胶漆的配合。新型的不锈钢色、香槟色、金黄色、钦金 色、红色系列( 酒红色、枣红色) 、黑色、紫色等加上彩色玻璃色彩能使建筑物 的装饰效果更理想。阳极氧化电解着色、静电喷涂等技术都可以获得多色彩表 面的铝合金型材。 3 ) 粉末静电喷涂型材。静电喷涂的生产过程主要分二步：第一、经化学氧 化在型材表面生成一层具有吸附性能的铬化膜；第二、在高压直流电场作用下 将热固性粉末树脂涂料喷涂在铝型材工件上，形成均匀的表面涂层，然后高温 固化形成各种色彩的涂装粉饰表面。粉末静电喷漆型材抗腐蚀性能优良，耐酸 碱盐雾能力大大优于氧化着色型材。由于这种型材的生产采用绿色环保工艺， 占地面积小，工艺流程简单，操作方便，节约能源和资源，投资少，见效快， 喷涂效率高，应用广，已被世界各地所采用。 4 ) 电泳涂漆型材。电泳涂漆( e l e c t r i c d e c o r ) 属于有机涂层封孔方法之一。相 比其它技术，电泳涂装法有以下优点：涂膜均匀致密；涂料的利用率高；安全 性和环保性；涂膜质量好；无需封孔，省时省力。同时在铝型材行业电泳涂装 发展还要注意几个方面：开发新断面，促进铝型材的新发展；丌发铝型材 加工技术，提高电泳材合格率；提高电泳漆的品质，扩大电泳漆种类。 。 5 ) 等离子体增强电化学表面陶瓷化涂漆型材。这种型材产品质量优良，达 到目前国际先进水平，但成本较高。它具有2 0 多种色调，最大的特点是可根据 需要像印花布一样套色，型材色彩缤纷，装饰效果极佳。由于型材表面是由高 密度能量的弧光放电烧结而形成的陶瓷膜层，光洁度高且膜厚而致密，耐腐蚀。 2 中南大学硕十学位论文第一章绪论 这一技术已通过中国腐蚀协会与防护学会的鉴定，并被确定为阳极氧化的更新 换代技术。 1 2 选题背景与意义 生产调度一直是制造系统的研究热点，也是理论研究中最为困难的问题之 一。它是针对产品生产探讨在一定的约束条件下，如何安排其组成部分所占用 的资源、加工时间及先后顺序，以获得产品制造时间或成本最优化。生产作业 调度问题的研究在理论与实际上都意义重大。生产调度问题的解决本身具有现 实的应用价值，车间调度的合理化、自动化、集成化，可以使供需紧密连接， 保持物流的一贯性，充分提高设备的利用率，减少供需等的时问，降低物耗和 能耗，减少库存，缩短交货期，从而降低成本，提高企业竞争力，给企业带来 极大的经济效益。 本论文的研究背景为福建南平铝业有限公司的铝型材表面处理自动生产 线。是由一条氧化生产线和一条氧化着色生产线增加了电泳槽后形成的铝型材 电泳柔性生产线组成。此生产线可生产6 种不同类型的型材：氧化材、着色材、 透明氧化电泳材、透明着色电泳材、有色氧化电泳材以及有色着色电泳材。 铝型材表面处理自动生产线都是一类具有并行工艺槽的柔性自动生产线， m 个槽位，n 个料架，a 台天车。每个槽位只能处理一挂料，每台行车只能运 送一挂料。需加工的型材料架在上料区固定好后，逐次，在各工艺槽中进行化 学处理，当规定的处理时间完成后，由相应的天车将其吊起，并放入下一工序 槽处理。被加工型材在各工艺槽问移动是通过在同一轨道上的多部天车的协同 调度与运输实现的。我们需要解决的问题是：运输铝型材的料架要尽量按处 方的要求进行处理；合理为a 台天车分配任务；保证生产线中天车运送料 架的流畅性；料架不能堆积在某些工艺槽位；随机事件如机器故障、槽故 障或紧急订单等的处理。可见天车的调度是整个自动生产系统中最重要的部分。 可是，由于天车运行区间的可重叠性和天车本身尺寸的限制，使得两台天车在 执行相邻或交叉槽位的任务时存在冲突。另外，由于机器故障、定单随机到达 等随机事件的影响，致使系统的调度环境和任务存在着较大的扰动，按预先确 定好的天车预调度通常是不能正常进行的。 南平铝业有限公司的铝型材表面处理自动生产系统现采用的是基于启发式 的调度规则在r s v i e w 3 2 的开发平台上，利用v b a 的灵活编程及事件驱动实现 天车的动态调度。规则调度简单明确、容易实现。但这种调度方法通常仅对一个 目标提供可行解，缺乏对整体性能的有效把握和预见能力。并且多品种、小批量 的生产方式应用越来越多，系统并存着异步推进的不同工艺流，并发、共享和加 3 中南大学硕+ 学位论文 第一章绪论 工路径的多样性，使系统管理面临更多新的挑战。 m u l t i a g e n t 系统由多个独立的、相互协调的智能体( a g e m ) 组成，各a g e n t 具有不同的求解方法，按照事先约定的协议进行通信，相互合作，以实现生产 线的调度优化。本论文采用了基于m u l t i a g e n t 技术的调度方法，该方法特别适 用于解决复杂问题，尤其是那些经典方法无法解决的单元问有大量交互作用的 问题。其优点是速度快、可靠性高、可扩展性强、能处理带有空间分布的问题、 对不确定性数据和知识有较好的容错性。 基于m u l t i a g e n t 技术的调度方法若能在南平铝业有限公司铝型材表面处 理自动生产系统中实施成功，将大大优化系统的运行效率。为快速响应市场变 化，及时生产出多样化、个性化的产品类型，使企业在激烈的市场竞争中立于 不败之地，对该生产系统进行国产化改造与丌发有重大意义。 1 3 生产调度理论及研究现状 总的说来，生产调度就是对一个可用的加工设备集在时间上进行加工零件 集的分配，以满足一个性能目标集。具体的提法是：有若干台设备，每台设备 可进行若干工序，有若干个零件，每个零件又由若干工序构成，要求如何将零 件分配到各台设备，每台设备上的零件的加工次序和零件的各工序的开始加工 时间该如何安排，使约束条件得到满足，同时使一些性能指标得到优化。 生产调度问题一般以c o n w a y 等人提出的方法来表示【_ 。这个方法只用4 个参数就可以表示大多数不同的调度问题。4 参数表示法为：n m a b ，其中n 为零件数，m 为设备数，a 为车间类型，在a 的位置若标以“f ”，则代表流水 作业调度( f l o w s h o p ) ；若标以“p ”，则代表流水作业排列调度问题( p e r m u t a t i o n f l o ws h o p ) ，若标以“j ”，则表示单件作业调度问题( j o b s h o p ) 。b 为优化指标的 目标函数，通常是使其值最小，常见的优化指标种类有：有效利用研究的资 源；快速响应需求；遵守交货期。 传统的生产调度确定了被调度的工件集合、工件的加工时间及加工工件机 器的连续性，这类调度问题被成为静态调度。然而实际生产中的大量问题是随 机发生的。如在机械制造业中，由于工件随机到达，加工机器出现故障等随机 事件，使得预调度不能正常执行，这就需要安排重调度。1 9 5 7 年j a c k s o n l 8 】对静 态调度和动态调度的概念做了区分。动态环境下生产调度问题应具有以下特点 桫j ：能够在线产生实时调度；对随机扰动实现在线辨识，并能快速进行自动重 调度。目前，动态调度已成为生产调度中研究的热点。 动态调度的方法分两大类，即传统调度方法和智能调度方法l l 例。传统的调 度方法一般包括启发式方法、仿真方法和确定性最优化方法等；智能的调度方 4 中南大学硕士学位论文 第一章绪论 法一般包括专家系统、智能搜索算法、人工神经网络和m u l t i a g e n t 方法等。 1 3 1 传统的动态调度算法 ( 1 ) 启发式方法 当有多个工序可以用同一台设备加工时，但又不能同时开始，出现资源约 束。无论是前向调度还是后向调度，当可以开工集合中不止一个工序等待在同 一设备上加工，即当可开工工序集合存在资源冲突时，如何选择下一个工序， 则可根据启发式规则进行处理，或根据随机法则选择一个工序。 启发式算法是一种根据已有的信息进行推理和计算，从而获得近似最优解 的方法，用于调度问题求解的启发式调度算法主要有调度规则、启发图搜索算 法和拉格朗日松弛算法。调度规则的特点是算法简单、计算复杂度低、精确性 不高，但是基本调度规则经过适当的组合和变形往往可以得到非常好的调度效 果，有时甚至能得到问题的最优解，比较有代表性的瓶颈转移法( s h i f t i n g b o t t l e n e c kh e u r i s t i c ) 源于a d a m s ，b a l a s 和z a w a c k 的文献，是目前车间调度 问题最有效的启发式调度方法。拉格朗同松弛算法由于其能在较短的时间内获 得高质量的次优解，并能进行性能评价等优点，受到了学术界的广泛重视，近 年来已经成为解决复杂车间调度问题的一种重要方法，如l u h 等在研究并行机 器调度问题时使用了拉格朗日松弛技术【l2 1 ，熊锐等用这种方法求解了集成车间 计划与调度问题i l 引。 ( 2 ) 仿真方法 仿真方法是动态调度研究中最常用的方法【1 4 1 。由于制造系统的复杂性，很 难用一个精确的解析模型来进行描述分析。而通过对仿真模型的运行收集数据， 就能对实际系统进行性能、状态方面的分析，从而能对系统采用合适的控制调 度方法。a l i s k i r a i l i l 5 j 等回顾和总结了动态环境下基于纯仿真的j o b s h a p 调度问 题的研究状况。文中提出的基于纯仿真模型的调度方法，即在一个较短的时间 段内用仿真来评价一个分派规则集，选取最小代价的规则，以适应系统状态的 变化。基于仿真调度系统的常见结构如图1 1 所示。其调度过程为：当仿真器 接收到选择规则请求时，按照可选规则的优先级执行一系列的仿真；选择器从 仿真结果中选出最佳的分配规则来调度制造系统的任务；最后，当系统出现异 常，控制系统发送一个信号给规则选择器；规则选择器根据异常的类型向仿真 器发送一个新的请求。 5 中南人学硕十学位论文第一章绪论 配 图l 一1 基于仿真调度系统的一般结构 w us y d e t a l 提出了基于纯仿真模型的调度方法【1 6 】，即在一个较短的时间 段内用仿真来评价一个分派规则集选取最小代价的规则，以适应系统状态的变 化。l e u n gl c e t a l 运用纯仿真模型【1 7 】，同时解决f m s 中作业调度和搬运小车 及刀具的资源分配问题。 基于仿真法虽然可以包含解析模型无法描述的因素，并且可以提供给使用 者一个调度性能测试的机会，但其不可避免地存在以下问题：缺乏理论意义；系 统更新频繁，使选择规则的时间少于评估规则的时间；仿真的准确性很大程序 受编程人员的判断和技巧的限制；系统短暂改变时，不能避免分配规则的不必 要的修改；检测待选规则集合中的规则性能需要时间，难以进行实时调度。 ( 3 ) 确定性最优化方法 主要包括数学规划( 动态规划、混合整数线性规划等) 、分支定界法【l8 】和消 去法等。这类方法主要是通过对调度问题建立一个整数规划模型，采用基于枚 举思想的分支定界法或动态规划算法进行求解9 1 。 分支定界法1 2 0 j 由两个基本步骤组成，分枝和定界。分枝是将一个大问题分 成两个或者更多的子问题，然后，再用相同的方法将子问题分成子问题的子问 题等。而定界则是计算每个分枝上子问题的最优值，以此作为问题的下界，分 枝步骤可以表示为查找树，分枝定界法的计算复杂性也是指数型的。动态规划 法用计算调度这一组合优化问题时，为了计算k 阶段的任意一个最优的评判指 标值，必须先知道k 一1 阶段的每一个最优的评判指标值。因此，如果由n 个元 素组成，子集的数量应该是2 ，即动态规划的计算复杂性是指数型的。 现已证明，绝大多数调度问题是n p ( n o n d e t e r m i n i s t i cp o l y n o m i c a l ，非确定 型多项式) 问题，随着调度问题规模的增大，上述方法的求解难度将急剧增加， 因而最优化方法往往不能适应生产实际对实时性的要求。此外，该类方法大多 6 中南人学硕士学位论文 第一章绪论 基于某些理想化的假设，远不能充分反映实际生产环境的复杂性，而且要充分 表达实际生产环境的随机性和动态性也极为困难，所以单独使用此类方法来解 决动态调度问题是不现实的。通常将最优化方法同其它方法相结合，用来解决 一定的问题。例如m a t s u u r a 2 提出的重调度算法，首先用分支定界法产生一个 调度，当工况发生变化时，再用调度规则来分配工件。 1 3 2 智能调度方法 ( 1 ) 专家系统 专家系统【冽【2 3 】可以产生比优先规则更复杂的基于对整个系统的启发式规 划，并能从数据库、知识库中获取大量信息。专家系统在动态调度研究中占有 重要地位，目前已有一些较成熟的调度专家系统，例如i s i s t 2 4 】和o p i s 等。调 度专家系统通常将领域知识和现场的各种约束表示成知识库，然后按照现场实 际情况采取相应的对策。它主要由知识库和推理机组成，知识库中存放着求解 问题所需的知识，而推理机则负责使用知识去解决实际问题。专家系统的一个 重要特征是知识库与推理机分离，系统允许在运行过程中不断修改知识，增加 新知识，使系统性能不断提高。 i s i s 是最早的基于a i ( a r t i f i c i a li n t e l l i g e n t ) 的调度系统之一。该系统采用 约束指导的搜索方法产生一个调度，动态情况则有重调度组件进行处理，当冲 突发生时，它通过有选择地放松某些约束来重新调度那些受影响的订单。基于 i s i s 开发的o p i s 是现有的基于知识的车间调度系统中最成熟的系统之一，它 根据情况使用面向资源或面向订单的动态调度策略。s o n i a 2 5 】是一个包含预测 和反应调度组件的单车间调度系统，反应组件用于解决由于各种原因产生的调 度效果与预期效果间的偏差，系统考虑的意外事件有操作延误、容量冲突和机 器故障。o p a l 2 6 】也是一个为单件车间设计的调度系统，它采用调度规则和启 发式方法进行调度。尽管o p a l 中没有反应调度组件，但是当调度延误时，它 可以根据车问的当前状态重新产生一个调度。 虽然已有一些成功的例子，但也存在不少的困难。专家系统的适应性差， 且有许多专家对制定调度方案有无专家表示怀疑。他们认为，一方面，复杂性 已完全超出专家的认识能力，另一方面，生产环境的动态特性使表达的知识很 快就过时。 ( 2 ) 智能搜索算法 禁忌搜索( t s ) ：禁忌搜索是局部邻域搜索算法的推广。最早由g l o v e r 2 7 】 提出，它是一种全局逐步寻优算法，也是人工智能在组合优化算法中的一个成 功应用。g l o v e r 在1 9 8 6 车首次提出这一概念，进而形成一套完整算法。禁忌搜 7 中南大学硕士学位论文第一章绪论 索算法的特点是采用了禁忌技术。所谓禁忌就是禁止重复前面的工作。为了回 避局部邻域搜索陷入局部最优的不足，禁忌搜索算法用一个禁忌表一记录下已 经到达过的局部最优点，在下一次搜索中，利用禁忌表中的信息或有选择地搜 索这些点，以此来跳出局部最优点。在禁忌搜索算法中，要想得到全局最优解， 必须做到使它的可行解区域是连通的。由于这一点的限制，使禁忌搜索算法的 应用广泛性得到限制。 模拟退火算法：s i m u l a t e da n n e a l i n g ( 简称s a ) 是一种基于统计力学和热力学 的退火原理而建立的随机搜索算法。该算法可以被看成局部搜索方法的改进。 s a 是2 0 世纪8 0 年代发展起来的一种随机搜索优化方法，它根据物理系统 退火使金属晶体有序重列的自然机理，利用m e t r o p o l i s 算法适当控制温度的下 降过程实现模拟退火。算法引入一定的随机因素，迭代过程接受“好”解的同时 以一定概率接受使目标函数的值，变“差”的解，在概率意义上能为求得全局最优 提供保证，但由于算法搜索过程缓慢，工业实际应用困难。一些学者针对算法 优化速度由退火温度更新函数决定的特点，通过构造新的温度更新函数，解决 温度下降过于缓慢问题，提出一些新的模拟退火算法。 p e t e r 2 引、田澎等【2 9 l 构造了车间调度问题的模拟退火算法，研究结果表明， 该算法总的来说能够渐近收敛于全局最优解，并具有多项式计算复杂特性，但 它的收敛速度较慢，难以用于实时动态调度环境，这成为了s a 进一步应用的 阻力。 遗传算法：遗传算法( g a ，g e n e t i ca l g o r i t h m ) 是一种新的并行优化搜索方 法，是一种借鉴生物界自然选择和自然遗传机制的随机化搜索算法，早在2 0 世 纪6 0 年代初，b a g l e y 就提出了遗传算法的术语，并将它用于自动博弈的研究， 到了2 0 世纪7 0 年代，r o s e n b e r g ，c a v i c c h i o ，w e i n b e r g 等人分别在不同的领域中 应用过遗传算法，但他们还只是以模拟生物进化为主，而并没有涉及到遗传操 作的本质特征。当时人们还不知道遗传操作在干什么、为什么干得那么出色。 直到1 9 7 5 年，美国m i c h i g a n 大学的j h o l l a n d 教授出版了著名专著自然系统 和人工系统的适配。该书系统地阐述了遗传算法的基本理论和方法，并首次确 认了结构重组遗传操作对于隐并行性的重要性。它对以后开发出的其它遗传操 作具有积极的指导作用。进入2 0 世纪8 0 和9 0 年代，遗传算法掀起了一个发展 的高峰期，无论理论研究还是应用研究都形成了系统性的课题。它的应用研究 从最初的组合优化领域扩展到控制、规划、设计、图象处理、信号处理、机器 人、人工生命等多个领域【3 0 1 。 标准遗传算法( s g a ) 至今仍是国内外g a 应用中常用的实施方案。研究表 明，在实际应用s g a 时，为增强s g a 的全局寻优能力，必须扩大群体规模n ， 8 中南大学硕士学位论文第一章绪论 提高杂交概率p c 和变异概率p m ，以增强群体在s g a 演化过程中的多样性。因 此在这些方面对s g a 进行改造是非常必要的。 解决标准遗传算法存在的局部搜索能力较差的途径有两种，一种方法是对 标准遗传算法进行改进，如增加交叉约束算子，使交叉操作限制在基因型相似 的染色体之间，这样在一定程度上能够改善遗传算法的局部搜索能力；另一种 方法则是将遗传算法与启发式规则或其它搜索算法相结合构成混合遗传算法， 以改善标准算法的局部搜索能力，进一步提高优化质量和搜索效率，同时可以 弥补单一优化方法的某些不足。赵博提出了算法集成概念【3 1 1 ，对虚拟车间智能 调度问题进行了研究；i l o g 公司还：开发了一整套优化组件，为企业的长期 计划、调度及其他的资源配置问题提供支持【3 2 】。 ( 3 ) 神经网络方法 神经网络 3 3 1 在生产调度上的应用已有十多年的历史，利用指导学习神经网 络找到系统输入、输出之间的关系，输入特性包含作业特性( 如数量、路径、交 货期和处理时间) ，输出为相关排序和性能指标。它在动态调度研究中应用主要 集中在两个方面：将调度问题看成一类组合优化问题，利用其并行处理能力来 降低计算的复杂性；利用其学习和适应能力将它用于调度知识的获取，以构造 调度决策模型。 目前多层前馈的b p 网络是应用最广泛的网络之一，通过对它的训练来构 造调度决策模型。h o p f i e l d 神经网络模型的提出为求解各种有约束优化问题开 辟了一条新途径。文章【3 4 】介绍了k h 用h o p f i e l d 网络来解决j o b s h o p 调度问题 的方法。s i m 等1 3 5 j 提出一种专家神经网络方法，该方法用1 6 个神经网络分别从 相应的训练样本集中获取调度知识，用专家系统确定各子网的输入。由于神经 网络的训练由1 6 个子网分担，并且各子网可以并行训练，从而减少了训练时间。 c h u 等【3 6 j 提出了一种基于神经网络和仿真的鲁棒自适应调度器，该方法根据他 人研究结论确定神经网络的结构和训练样本。尽管该网络结构具有较强的通用 性，但由于每个人研究的背景不尽相同，因此通过量化他人结论来产生训练样 本必然会对网络性能造成影响。j o n e s 等【3 7 】提出了一种解决实时排序和调度问题 混合方法的框架，综合运用了神经网络、遗传算法和实时仿真等方法，但是只 是提供一个框架，还需要进一步研究。 神经网络方法计算时产生大量不可行解且计算时间较长，致使其解决实际 调度问题的效率不高，而指导学习神经网络试图通过训练类型找出输入输出之 间的关系，随着问题规模的增大，网络的规模也急剧增大。另外，神经网络方 法还存在易陷入局部最小和全局搜索能力弱等不足。 ( 4 ) 基于m u l t i a g e n t 的调度方法 9 中南人学硕士学位论文第一章绪论 上述生产调度方法大多集中于单个车间环境下如何利用有限制造资源最优 地完成生产任务，调度者对制造资源有完全的支配权，并且可获得足够的生产 作业过程信息，能对作业过程进行集中式的控制。而在分布式环境下，调度具 有不确定性和动态性，这些调度方法难以适用。为此，近年来很多研究人员试 图将分布式人工智能研究领域中的多智能体系统( m u l t i a g e n ts y s t e m ，m a s ) 理 论运用于分布式调度问题，并研究基于该框架的制造活动协调与调度问题。 基于m u l t i a g e n ts y s t e m 技术的调度求解方法提供了一种动态灵活、快速 响应市场的生产调度机制，它以分布式人工智能中的m u l t i a g e n t 机制作为新的 生产组织与运行模式，通过a g e n t 之间的合作以及m a s 系统协调来完成生产任 务的调度，并达到预先规定的生产目标及生产状态。 p a u l o 提出用多智能体封装任务和资源单元，采用合同网协议来进行分布式 问题求解，提出新的体系结构和协商协议来处理生产系统的动态调度问题【3 8 1 。 a l a i n 采用遗传算法进行调度优化，建立基于合同网的动态模型，通过协商来获 得新的调度【3 9 1 。王丹【4 0 】提出了一种用多智能体技术解决虚拟企业调度冲突的方 法。将m u l t i a g e n t 技术和传统的调度优化方法相结合是当前作业车间调度问题 研究的一个新的解决方案【4 。基于多智能体协商的调度方法重点在于增强调度 系统的适应性和实时反应性，而不是进行方案的优化，更适用于动态调度，而 遗传算法、模拟退火算法等着重方案的优化。在作业车间调度问题中，不但需 要动态调度，同时也需要方案的优化。t h o u r a y a 提出了智能体协商和模拟退火 相结合的调度方法【4 2 j 。 b u t l e r l 4 3 j 提出了用于分布式动态调度的m u l t i a g e n t 体系结构 a d d y m s ( a r c h i t e c t u r ef o rd i s t r i b u t e dd y n a m i cm a n u f a c t u r i n gs c h e d u l i n g ) ，将调 度分为两个层次，第一层通过a g e n t 的协商机制。以一种分布式的方法将制造 单元分配给作业，第二层对共享制造资源进行动态分配。s h e n 和n o r r i e l 4 4 1 等在 m e t a m o r p h l i 系统中提出了一种基于混合型中介a g e n t 体系结构的协调模型， 采用基于合同网协议的投标机制，进行制造调度和再调度研究。s h e n 列举了近 3 0 个国际上已经开展或正在进行的运用a g e n t 技术进行生产规划、调度、控制 的研究项目，从这些研究项目可以看出，运用a g e n t 技术进行生产规划、调度、 控制等问题的研究，其常见的做法是用a g e n t 来表示制造中的各种物理资源或 逻辑资源，如设备、物料运输设备、机器人、订单、b o 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 技术在作业车间调度方面的研究，如南京 1 0 中南大学硕士学位论文第一章绪论 航空航天大学进行了基于a g e n t 的分布式动态作业车间调度的研究，并提出了 一种基于合同网协议投标机制的m u l t i a g e n t 分布式动态作业车间调度方案；南 京理工大学进行了代理技术在作业车间调度问题中的应用研究，分析了基于代 理技术的分布式作业车间调度结构，提出了自主调度执行的概念，给出了一种 基于扰动分析的自主调度执行算法，以使调度执行代理对系统扰动自主地作出 快速和优化的决策。 m u l t i a g e n t 技术是目前分布式人工智能的研究热点。由于m a s 能够充分 体现人类的社会智能，对开放、动态的现实环境具有良好的灵活性和适应性， 因此m a s 理论受到重视并得到迅速发展，并在制造领域( 如车间资源配置、 生产调度与控制、生产管理决策等) 获得越来越多的应用。 目前大多数基于m u l t i a g e n t 的生产调度系统集中于a g e n t 之间协调机制的 研究，研究者注意到，由于生产调度特别是动态调度中存在的不确定性因素导 致很难采用数学建模的方法，m a s 技术的采用降低了动态调度的复杂性；另一 方面，由于采用协商机制解决调度决策中的各类冲突，基于m a s 的调度系统 能够较好地适应车间制造环境的变化，从而增强了调度系统的敏捷性和鲁棒性。 南平铝业有限公司的铝型材表面处理自动生产系统现采用的是基于启发式 的调度规则在r s v i e w 3 2 的开发平台上，利用v b a 的灵活编程及事件驱动实现 天车的动态调度。这种调度方法通常仅对一个目标提供可行解，缺乏对整体性 能的有效把握和预见能力，使系统管理面临很多困难和挑战。 本论文采用了基于m u l t i a g e n t 技术的调度方法，该方法特别适用于解决复 杂问题，尤其是那些经典方法无法解决的单元间有大量交互作用的问题。其优 点是速度快、可靠性高、可扩展性强、能处理带有空问分布的问题、对不确定 性数据和知识有较好的容错性。该调度方法若能在南平铝业有限公司铝型材表 面处理自动生产系统中实施成功，将大大优化系统的运行效率。 1 4 本文主要工作及安排 本课题主要研究内容：以铝型材表面处理自动生产线为对象，采用 m u l t i a g e n t 技术应用于生产线的动态调度中，以提高该生产线的智能化程度， 发挥各个a g e n t 协调动作来优化系统调度，达到最优化控制，最大程度的提高 生产效率。根据铝型材表面处理自动生产线的结构布局，划分为几个智能体， 各个智能体互相通讯，相互协调构成一个m u l t i a g e n t 系统。 全文工作及安排如下： 第一章绪论，首先概述了铝型材的生产现状及未来的发展方向，并由此引 出本文的选题背景与意义。通过综述生产调度中各种调度算法的国内外研究现 中南大学硕士学位论文第一章绪论 状及各种算法在研究发展和应用方面的优缺点，提出了本文的研究思路、主要 内容及体系结构。 第二章铝型材表面处理自动生产系统及调度问题分析，介绍了铝型材表面 处理自动生产线的构成，并介绍了生产线的控制结构。对生产线作了预处理， 建立了生产线的规划模型；分析了天车调度在生产系统中的重要性。 第三章m u l t i a g e n t 系统的理论研究，对a g e n t 及m u l t i - a g e n t 技术进行了 深入研究，描述了它们的定义，并分析了它们的基本特征，制定了a g e n t 的基 本功能结构，阐述了m u l t i a g e n t 的协作层次，基于合同网的协作协议，会话机 制以及通信语言，为后两章的研究工作做了很好的铺垫。 第四章生产系统中m u l t i 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 2 中南大学硕士学位论文第二章铝型材表面处理自动生产系统及调度问题分析 第二章铝型材表面处理自动生产系统及调度问题分析 2 1 自动生产线简介 2 1 1 生产线工艺流程 h 拦鳓嘲嘲圉卜全土