（管理科学与工程专业论文）基于多agent的柔性车间调度系统研究.pdf

关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：垫这签导师签名：五堡盘壅日期：竺! ! ：兰：! ? 摘要 摘要 生产调度作为企业生产管理的核心，对资源的优化配置和科学运作起着举足 轻重的作用，科学、有效的计划与调度成为企业实现制造系统平稳、高效运转的 关键。作业车间调度问题一直是一个研究热点，但由于作业车间调度问题对机器 加工路线做了限定，已不能满足实际生产的需要。柔性作业车间调度问题是作业 车间调度问题的扩展，允许操作可以在多台机器上进行加工，从而更加接近实际 工作环境，具有重要的理论价值和工程意义。 本文针对柔性作业车间调度问题，利用多a g e n t 理论，在前人研究的基础上， 以标准化加权滞后和为目标函数进行了创新性研究。建立了由工件a g e n t 、生产 单元a g e n t 和全局a g e n t 构成的柔性作业车间调度系统，采用权重式和基于最早 完工时间相结合的调度策略。同时，为了适应车间动态多变的过程，在通过离线 调度得到最优合作权重表的基础上，通过根据车间状态的改变及时调整权重的方 法提高系统对动态环境的适应能力。 本文利用仿真软件a r e n a 对柔性作业车间调度系统进行了仿真实验。首先进 行了在不同的车间负荷和工期紧迫系数下的仿真实验，并将调度结果与利用 w s p t 、e d d 、c o v e r t 、a t c 等经典的分派规则得到的结果进行比较，充分证明 了所提方法的有效性。然后进行了工件到达率改变、工期改变和机器故障三种情 况下合作权重调整的实验，将实验结果与合作权重调整前进行比较，结果证实了 此方法的有效性。通过以上的实验也说明本文所建立的基于多a g e n t 的柔性车间 调度系统具有一定的优化性能，同时能够适应生产车间动态多变的环境。 关键字多a g e n t 系统；柔性车间调度；标准化加权滞后和 北京- r ：, l k 大学管理学硕j ：学位论文 i i a b s t r a c t a b s t r a c t a sac o r ep a r to fp r o d u c t i o nm a n a g e m e n t , p r o d u c t i o ns c h e d u l i n gp l a y sak e yr o l e i no p t i m i z i n gt h ed i s t r i b u t i o no fr e s o u r c e sa n do p e r a t i n gs c i e n t i f i c a l l y p l a n n i n ga n d s c h e d u l i n gs c i e n t i f i c a l l ya n de f f e c t i v e l y i st h e k e yo fk e e p i n g t h e e n t e r p r i s e s m a n u f a c t u r i n gs y s t e ms t a b l ea n do p e r a t i n ge f f i c i e n t l y j o bs h o ps c h e d u l i n gi s a r e s e a r c hh o t s p o t , h o w e v e r , t h el i m i t a t i o no fp r o d u c t i o nr o u t em a d ej o bs h o p s c h e d u l i n gp r o b l e md i t t i c u l tt os a t i s f yt h ea c t u a ln e e d s 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 me x t e n d e df r o mj o bs h o ps c h e d u l i n gp r o b l e m i ta l l o w sj o bt ob ep r o c e s s e d o n m u l t i p l em a c h i n e s t h i sp r o b l e mi sc l o s e rt ot h ea c t u a lw o r k i n ge n v i r o n m e n t t h e r e s e a r c hh a si m p o r t a n tt h e o r e t i c a la n de n g i n e e r i n gs i g n i f i c a n c e b a s e do nm u l t i - a g e n tt h e o r ya n dp r e v i o u ss t u d i e s ，i n n o v a t i v er e s e a r c hw a s c a r r i e do u tf o rf l e x i b l ej o bs h o pp r o b l e mi nt h i sp a p e r t h eo b j e c t i v ef o rt h ep r o b l e m i sn o r m a l i z e dw e i g h t e dt a r d i n e s s af l e x i b l ej o bs h o ps c h e d u l i n gs y s t e mw a s e s t a b l i s h e d t h es y s t e mc o n t a i n e dj o ba g e n t ，u n i ta g e n ta n dg l o b a la g e n t t h e s c h e d u l i n gs t r a t e g yw a sc o m b i n a t i o no fw e i g h t e d b a s e da l g o r i t h ma n de a r l i e s t c o m p l e t i o nt i m es c h e d u l i n gm e t h o d t h e ni no r d e rt oa d a p tt od y n a m i cw o r k s h o p ，a c o o p e r a t i o nw e i g h ta d j u s tm e t h o dw a sp r o p o s e d b yd e t e c t i n gt h es t a t eo fw o r k s h o p ， s e a r c h e dt h eo p t i m a lc o o p e r a t i o nw e i g h ta n da d j u s tt i m e l y t h es y s t e mw a si m p l e m e n t e d 、撕la r e n a f i r s t l y , t h es i m u l a t i o ne x p e r i m e n t s w e r eu n d e rv a r i o u ss h o pl o a dl e v e la n dd u ed a t et i g h t n e s s c o m p a r et h er e s u l t sw i 1 w s p t , e d d ，c o v e r t , a t ca n do t h e rc l a s s i c a ld i s p a t c h i n gr u l e s t h ec o m p a r i s o n s r e s u l t ss h o wt h ep r o p o s e dm e t h o di se x c e l l e n t t h e nt h ea r t i c l em a d es i m u l a t i o na b o u t j o ba r r i v a lr a t ec h a n g e ，j o bd u ed a t ec h a n g ea n dm a c h i n ef a i l u r e t h es i m u l a t i o nr e s u l t c o n f i r m e dt h a tt h es y s t e mw a se x c e l l e n t t h ee x p e r i m e n t sa l s os h o wt h es y s t e mh a s c e r t a i no p t i m a lp e r f o r m a n c ea n dc a na d a p tt ot h ed y n a m i ce n v i r o n m e n ti nw o r k s h o p k e y w 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 bs h o p ；n o r m a l i z e dw e i g h t e d t a r d i n e s s i i i i v 目录 j r _ j - 目录 摘要i a b s t r a c t i i i 第1 章绪论1 1 1 研究的背景和意义1 1 2 车间调度问题描述2 1 2 1j o bs h o p 调度问题2 1 2 2f l e x i b l ej o bs h o p 调度问题3 1 3 国内外研究现状4 1 3 1 柔性作业车间调度的研究现状4 1 3 2 多a g e n t 生产调度系统的研究现状5 1 4 研究内容、方法和结构安排7 1 4 1 研究内容7 1 4 2 研究方法7 1 4 3 创新点8 1 4 4 论文结构9 第2 章相关理论研究1 1 2 1a g e n t 及相关问题1 1 2 1 1a g e n t 的定义1 1 2 1 2a g e n t 的分类1 2 2 2 多a g e n t 系统1 3 2 2 1 多a g e n t 系统的定义1 3 2 2 2 多a g e n t 系统体系结构1 3 2 2 3 多a g e n t 间的协调、协作与协商1 5 2 3 常见的规则调度方法1 7 2 4 本章小结2 0 第3 章多a g e n t 柔性车间调度系统的分析与设计2 1 3 1 系统分析2 l - 3 2 体系结构2 3 3 2 1 生产单元a g e n t 2 4 3 2 2 工件a g e n t 2 5 3 2 3 全局a g e n t 2 6 3 3a g e n t 间的协商机制2 6 3 4 调度策略2 9 3 5 本章小结3 2 第4 章柔性车间调度系统的仿真实验与结果分析3 3 4 1a r e n a 仿真软件的简单介绍3 3 4 1 1a r e n a 软件简介3 3 4 1 2 优化工具0 p t q u e s t 3 4 4 1 3 输出分析器o u t p u ta n a l y z e r 3 4 4 2 仿真实验设置3 4 v 北京t 业大学管理学硕仁学位论文 4 3 仿真实验及结果分析3 6 4 3 1 策略一仿真实验及结果分析3 6 4 3 2 策略二仿真实验及结果分析3 8 4 4 本章小结3 9 第5 章合作权重的实时调整4 卜 5 1 合作权重调整分析4 1 5 2 合作权重调整策略4 1 - 5 2 1 达到率改变的调整策略4 2 5 2 2 工期改变的调整策略4 2 5 2 3 机器故障的调整策略。4 3 5 3 学习机制4 3 5 4 仿真实验与结果分析4 4 5 4 1 工件到达率改变4 4 5 4 2 工件的工期改变4 5 5 4 3 机器故障4 6 5 5 本章小结4 6 结论与展望4 7 参考文献4 9 攻读硕士学位期间发表的学术论文5 5 致谢5 7 v i 第1 章绪论 第1 章绪论 1 1 研究的背景和意义 随着信息技术的发展，现代制造企业的管理模式和产品结构发生了巨大的改 变。客户对产品多样化和个性化的要求促使稳定的传统市场变得动态多变，往常 的大批量生产逐渐变为用户定制和多品种小批量的生产模式，在生产企业中单件 小批生产开始逐渐占据重要位置。 我们以一个中等规模的单件订货型的生产企业为例，在一段时间内企业可能 需要同时加工几十个以至上百个工件，假设每个工件平均由四道工序组成，那么 在制工件包含的工序就有成百上千道。在工期的约束下，能够计算出每个工件的 每道工序的工序完工时间。在企业现有的资源下，根据工件工期的要求，把所有 的工序合理的安排在资源上进行加工就是这一阶段的生产管理目标。这一目标主 要是通过调度人员和车间项目小组的实时调度实现。因为每道工序都包含加工工 期的约束、工艺路线约束、加工设备约束，可以想象成百上千道工序包含的信息 量是多么庞大。因此只靠调度人员的经验来进行工序和资源的分派是无法实现 的，而这个问题也是制造企业面对的一个瓶颈问题。 随着信息技术的快速发展，一些新的概念、思想和管理模式应运而生，从物 料需求计划到制造资源计划，再到企业资源计划，以及准时化生产、敏捷制造， 所有这些新的理念给制造业带来了深刻的变化，提高了他们的信息化水平，进而 也促使管理水平得到大大的提高，而生产调度处于这些新理念的核心地位。可是 这些新的理念真正在企业成功实施的案例还非常之少，其中一个主要的原因是生 产计划子系统与生产调度系统的脱节。生产调度作为e r p 系统的重要组成部分， 调度的合理性将会直接影响到整个系统的质量和性能。目前，生产调度问题已经 成为学术界研究的热点，在调度算法的研究上，常用的有启发式算法、禁忌搜索 法、神经网络法和遗传算法等，这些算法各有优劣，不同的算法可用在不同的场 厶 口0 近几年许多研究人员试图将分布式人工智能研究领域中的多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 方法研究生产调度问题对调度理论的实用化进程具有重要的理论意义 和实践意义。 北京t , i k 大学管理学硕十学位论文 1 2 车间调度问题描述 生产调度问题是指对于某个可以分解的工作，在满足一定的约束条件下，合 理的安排工件组成部分所占用的资源、先后顺序以及加工时间，使某个目标函数 达到最优【l 】。根据加工系统的复杂度，生产调度可以分为单机调度( s i n g l em a c h i n e s c h e d u l i n g ) 、并行机调度( p a r a l l e lm a c h i n es c h e d u l i n g ) 、流水车间调度( f l o ws h o p s c h e d u l i n g ) 、作业车间调度( j o bs h o ps c h e d u l i n g ) 和开放车间调度( o p e ns h o p s c h e d u l i n g ) 。 单机调度是指所有的操作任务都在一台机器上完成，需要对任务进行优化排 队，单机调度是所有机器环境中最简单的，是其他复杂机器环境的特例。并行机 调度是指加工系统有一组功能相同的机器，待加工的工件也都只有一道工序，可 选择任意一台机器来加工工件。流水车间调度是指加工系统有一组功能不同的机 器，代加工的工件包含多道工序，每道工序在一台机器上加工，所有工件的加工 路线都是相同的。开放车间调度是指加工系统有一组机器，每项工作在每台机器 上可以进行多次加工，对每项工作的加工路径没有任何限制，允许调度者为每项 工作确定加工路径，而不同的工作可以有不同的加工路径。 作业车间调度问题是最复杂的调度问题，而且生产车间的大多数调度问题是 作业车间调度，目前大多数研究也都集中在作业车间调度问题上。柔性作业车间 调度是对作业车间调度问题的扩展，是一类更加复杂的调度问题，下面对作业车 间调度问题及柔性作业车间调度问题进行描述。 1 2 1j o bs h o p 调度问题 作业车间调度问题( 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 o bs h o p 调度问题可以描述为：给定一个工件的集 合和一个机器的集合，每个工件包括多道工序，每道工序需要在一台给定的机器 上非间断地加工一段时间；每台机器一次最多只能加工一道工序；调度就是为了 将工件的各道工序合理的安排在各台机器上，同时在满足工件的加工次序的前提 下，合理的安排各工序在机器上的开工时间，满足系统设定的约束条件，优化性 能指标【i j 。 在经典的作业车间调度问题中，除技术条件外，一般还做出如下假设： ( 1 ) 在生产系统的加工过程中，每个工件只能在同一台机器上加工一次； ( 2 ) 同一时刻，每台机器只能加工一个工件，加工过程不问断，整个加工 过程中机器都是可用的； ( 3 ) 各个工件按工艺路线制定的先后次序进行加工； 第l 章绪论 ( 4 ) 工序不允许中断，当一个工序没有加工完，下一道工序需要等待； ( 5 ) 工件的加工时间事先确定，并且在整个加工过程中不变； ( 6 ) 不考虑工件的优先权。 1 2 2flo xibiej o bs h o p 调度问题 在经典的j o bs h o p 调度问题中，刀个工件在m 台机器上加工，每个工件由多 个操作组成，每个操作按照事先制定的加工次序和加工时间进行加工。在j o b s h o 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 ) 是j o bs h o p 调度问题的扩展，是一个更为复杂的调度问题。在对f j s p 问题的研究中，根据 实际生产的情况，不同的学者对柔性的定义不同， 文献 3 】和文献【4 】研究的柔性作业车间调度问题描述如下：柔性加工车间是 加工车间和并行机环境的一般化。代替m 台机器的是c 个加工工作中心，每个工 作中心有许多并行同速或者异速机。每个工件遵循它自己的加工路径通过车间， 工件，只需要在每个工作中心的一台机器上加工，而每一台机器都可以完成该工 作。 文献 5 】将柔性作业车间调度问题细分为完全柔性作业车间调度( t o t a l f l e x i b l ej o bs h o p ，t f j s s ) 问题和部分柔性作业车间调度( p a r t i a lf l e x i b l ej o b s h o p ，p f j s s ) 问题。在完全柔性作业车间调度问题中，工件的每个操作可以在 生产系统中的任意一台设备上加工。而在部分柔性作业车间调度问题中，生产系 统中存在不同类型的加工设备，因此加工的工件对加工设备的要求不同，导致某 些操作可以在生产系统中的任意一台设备上加工，而某些操作只能在系统的设备 集合中的部分设备上加工。 文献 6 】将柔性车间调度问题与工艺路径柔性相结合，设计了一种基于柔性工 艺路线的多a g e n t 生产调度系统。h o y c 曾提出柔性工艺规划网络，可将工艺路 径柔性归为三种：( 1 ) 次序柔性：即一组必须完成但可以以任意次序完成的工序； ( 2 ) 路径柔性：即多组可达到同一目标但是能且只能选择其一进行的工序集， 零件的路径柔性提供了加工该零件的可选路径；( 3 ) 设备柔性：即一个工序可由 多种设备完成。文献 6 研究的问题在柔性车间调度问题的基础上，即每道工序 可以在多台机床上加工，并且在不同的机床上加工所需要的时间不同，增加了工 艺路径的柔性，增加了问题的复杂性。 本文研究的是文献 3 】和文献 4 】中描述的加工车间和并行机环境的一般化的 柔性车间调度问题。 北京- l - , l k 大学管理学硕：e 学位论文 1 3 国内外研究现状 1 3 1 柔性作业车间调度的研究现状 b r u k e r 和s c h l i e 【3 】是最早提出柔性作业车间调度问题的人物之一。它们针 对两个工件的柔性作业车间调度问题提出了多项式算法。后来逐渐提出解决多个 工件的柔性作业车间调度问题的算法，这些算法主要可以分解为两类：分解方法 ( 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 ) ，分配就是为工件的每个工序选择合适 的机器；调度就是对机器上的工序进行排序。也就是说，一旦分配问题解决，柔 性作业车间调度问题就化简为经典的车间调度问题。应用此算法的有 b r a n d i m a r t e 7 。，p a u l i 引，b a r n e s l 9 ，它们都是用分派规则解决分配问题，用不同 的禁忌搜索法解决排序问题。x i a 1 0 】利用粒子群算法将工序分配给机器，用模拟 退伙算法对机器上的工序进行调度。集成方法同时考虑分配问题和调度问题，并 不把它们分开。v a e s s e n s 1 l 】，d a u z e r e p e r e s 1 2 】和m a s t r o l o l l i ，g 锄曲a r d e l l a 【1 3 】 都应用集成方法解决柔性作业车间调度问题。 国内也有学者利用遗传算法，禁忌搜索法，模拟退火等算法来研究f j s p 问 题，如陈耀军等【1 4 】提出了一种面向对象的遗传算法，张超勇等【1 5 】提出了两级遗 传算法，刘晓霞等【l6 】则将遗传算法和模拟退火算法相结合，利用遗传算法快速搜 索一组较好的解，然后利用模拟退火算法进行群体寻优。姜思杰等【1 7 】提出了基于 遗传和禁忌搜索的优化调度算法。 但上述算法的计算量特别大，因此不适合解决实际的、大规模的柔性作业车 间调度问题。已有一部分学者开始着眼于用多a g e n t 理论来解决柔性作业车间调 度问题。 s a a d 掣1 8 】提出了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 ) ，存储列表的每条记录包括工件号，工件开始加工时 间和工件预加工时间。当有一个新的工件到达，所有的机器向工件提交标书，标 书的内容包括最早完成时间和存储列表的长度。工件对所有的标书进行比较，选 择完成时间最早的机器，如果存在两台或两台以上完成时间相同，则选择存储列 表最短的机器。机器将此工件放入存储列表中。工件将重复上述过程，直到把所 有工序分配完。为了测试所提方法的有效性，作者进行了实验。实验设置为：车 间有9 台相同的机器，工件服从指数分布动态的到达，具有相同的优先级。每个 工件要经过5 台不同的机器进行加工，且加工时间相同。将p r 方法与f i f o ， e d d ，s p t 进行比较，结果显示流动时间( f l o w t i m e ) ，平均延迟，工件延迟数 量和w m 数量都有明显的下降，但l e a d t i m e 并没有减少。 第l 蕈绪论 w e i 掣1 9 】兼顾工件选择和机器选择两方面，基于合同网协议和分派规则，提 出了合同网协议交互投标模式。作者构造了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 规则。实验环境 为1 5 种工件在9 台机器进行加工，每个工件必须经过所有机器完成一道加工工 序，将这5 种规则与分派规则比较，以系统加工平均延迟时间为评价标准， c n p e f t 规则调度方法具有最好的调度性能。 k o u s i s 掣2 0 】针对柔性制造系统( f m s ) ，提出了利用a g e n t 动态的选择分派 规则进行调度。在他提出的体系结构中，分为一个管理a g e n t 和多个工作单元 a g e n t ，每个工作单元由一台或多台机器组成。工作单元a g e n t 不断地检测是否有 “症状”发生，然后根据这些“症状”和系统的目标函数动态地选择分派规则。 但这种方法并没有真正的应用到实际的柔性制造系统中，作者也只是选择了j o b s h o p 做为实验环境对所提方法进行了实验。 w u 2 l 】提出了一种解决柔性作业车间e t 调度问题的机制。在此机制中，将 工件分为两类，只有一道工序未加工的工件( s o l j ) ，和多道工序未加工的工件 ( 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 l j 和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 。 乔兵等瞄】提出了一种基于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 ，采用合同网协议确 定各个任务和各个资源之间的分配关系，资源代理计算自己完成任务的奖惩值作 为投标值。作者研究的调度系统已经在北京航空航天大学制造研究所研制开发的 制造经理一制造执行系统中运行。 任海英，商晓坤盟4 1 以平均滞后为目标函数，提出了一种基于市场机制的多 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 多a g e n t 生产调度系统的研究现状 s h a w 2 5 】是较早提出把a g e n t 应用于生产调度与控制方面的人物之一。他指出 一个生产单元可以通过招投标机制，将作业转包给其它生产单元。y e ta n o t h e r m a n u f a c t u r i n gs y s t e m ( y a m s ) t 2 6 】是一个早期被实现的生产调度系统，在此调度系 北京工业大学管理学硕：仁学位论文 统中，将每一个工厂或工厂的组成部分视为一个a g e n t ，每个a g e n t 有自治能力， a g e n t 之间可以协商。 s m i t h 第一个提出了合同网协商机制【2 7 】，之后很多研究人员将合同网协商机 制应用于生产调度系统中，提出了基于合同网协议的多a g e n t 生产调度系统，如 文献【2 8 】。但随着a g e n t 数量的增多，基于合同网的多a g e n t 生产调度系统问题出 现了通信量大等一系列问题，针对这些问题，学者们又提出了合同网协议的改型， 如文献 2 9 提出分级承诺签约，文献 3 0 提出了基于混合式合同网协议，文献 3 1 】 提出只向一定数量的a g e n t 招标，预测招标信息，将a g e n t 合理分组等改进策略。 l i n 和s o l b e r 9 1 3 2 1 提出了基于市场的多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 不断调整自己的成本，从而达到供求上的均衡，实现彼此间 的合作。k i m 等【3 3 】提出了与l i n 类似的基于市场的多a g e n t 生产调度系统，只是 在定价机制和目标函数上与l i i l 不同。 r a b e l o 等【3 4 】提出了层次型多a g e n t 生产调度系统。c a v a l i e r i 3 5 】设计了一项实 验，对l i n 等【3 2 】提出的基于市场的多a g e n t 生产调度系统与r a b d o 等【3 4 】提出的层 次型多a g e n t 生产系统进行了比较。为了对两种系统进行全面的比较，作者设计 了三个实验环境，分别为稳定的加工环境，有紧急工件到达和有机器出现故障。 实验结果显示，在总体上基于市场的调度系统比基于层次的调度系统健壮性好。 y e n 和w u 3 6 】利用多a g e n t 理论提出了一种新的调度模型，网络调度模型。 他将每个独立的调度系统做为网络调度a g e n t ，a g e n t 间基于市场机制进行沟通协 商，更好的分配资源。作者在l e k i n 软件的基础上，开发了原型系统l e k i n e t 。 实验结果显示基于多a g e n t 的网络调度系统是可行的。 很多学者把基于多a g e n t 的调度方法与基于规则的调度策略相结合，如沈阳 自动化研究所的张宇，孙宪鹏7 儿矧，王艳红口引，北京航空航天大学制造系统研究 所的乔东平，杨建军h 0 l ，沈阳工业大学的宋娟h ，他们为解决车间调度问题提出 了一种新的方法。 任海英h 2 1 提出了基于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 o bs h o p 生产系统的最小交工延迟问题， 与启发式算法相比，作业计划的质量有了明显的提高。 饶运清等【4 3 】针对j s p 提出了基于多a g e n t 的车间调度模型，调度系统由设备 a g e n t 和工序a g e n t 组成，p a 与d a ，p a 与p a 之间可以通信。实现了多目标调 第1 苹绪论 度和动态调度，最后通过4 4 的j o bs h o p 调度问题，说明了提出方法的应用。 王媛h 4 1 ，刘艳博h 5 i ，齐新h 6 1 以大连奥托技术有限公司设计和开发的e r 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 间的协商，王媛采 用合同网的协议，刘艳博采用消息报告机制，齐新采用混合合同网机制，同时提 出了决策函数和算法，并给出了异常调度策略。最后都用j a v a 语言实现，与原 e r p 系统进行了无缝链接。李贤h 7 1 针对离散制造行业中的j o bs h o p ，实现了基 于多工艺路线的多a g e n t 生产调度系统，将工序计划与车间调度相集成。a g e n t 之间采用混合合同网协商机制，给出了决策函数和算法。采用j a v a 语言和分布 式r m i 技术，对系统进行仿真实验，与共生进化算法和m a n 算法进行比较，性能 最优。 桂欢欢等利用面向对象的分析方法，建立了一种基于层次代理的生产调度 系统模型。模型有三部分组成，资源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 j s p 问题有重要的理论意义和实践意义。 1 4 研究内容、方法和结构安排 1 4 1 研究内容 本文研究的柔性作业车间调度问题是文献 3 】和文献 4 】中提出的车间环境和 并行机环境一般化的调度问题。利用多a g e n t 理论，提出了权重式机器选择工件 算法和最早完工时间及预测机制的工件选择机器算法。为证实所提方法的有效 性，利用仿真软件a r e n a 对车间环境进行模拟，进行大量的仿真实验。通过分析 实验结果，得出结论，本文提出的基于多a g e n t 的柔性车间调度算法在加权滞后 和问题上要明显优于传统的分派规则。在离线调度的基础上，探测加工车间的状 态，实现合作权重的实时调整，使调度系统更加接近于实际加工环境。 1 4 2 研究方法 本文采用理论研究与仿真实验相结合的方法。首先确定柔性作业车间调度系 统的体系结构，系统由工件a g e n t ，生产单元a g e n t 和一个全局a g e n t 组成。其 次确定调度策略。调度策略首先由空闲机器选择工件，此算法基于文献 4 2 提出 的权重式调度算法，针对柔性车间调度进行改进。在工件选择机器上，首先根据 最早完工时间进行选择，然后在此基础上加入预测机制，并对两种方法进行比较。 利用a r e n a 仿真软件，模拟车间生产环境，进行仿真实验，测试所提方法的有效 性。同时，通过实验可以获得在特定车间负荷水平和工期紧迫性系数下的合作权 北京工业大学管理学硕i ：学位论文 重值。因为实际的生产车间是一个动态的过程，最后可以通过不断探测车间的状 态，根据车间的最新情况调整合作权重值，从而达到实时调度的目的。研究路线 如图卜1 所示： 实调 验度 与策 结略 果的 分设 析计 器工工 磊戒窭 图卜l 研究路线图 f i g u r e l - 1r e s e a r c hr o a d m a p 1 4 3 创新点 本文的创新点在于： ( 1 ) 目前对j o bs h o p 调度问题的研究较为丰富，但由于柔性车间调度问题 的复杂性，用多a g e n t 方法对柔性车间调度问题的研究较少； ( 2 ) 在调度策略上，文献【4 2 】提出权重式调度算法解决j o bs h o p 调度问题， 本文将此算法进一步改进，并与最早完工时间及加入预测机制的机器选择算法结 合，来解决柔性车间调度问题； ( 3 ) 考虑现实车间调度是一个动态多变的过程，可以通过探测车间的状态， 动态的调整合作权重，达到实时调度的目的。 第1 章绪论 1 4 4 论文结构 本文第一章是绪论部分，主要包括文章的研究背景和意义、车间调度的分类、 j o bs h o p 调度问题和f l e x i b l ej o bs h o 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 ( u a ) 、工件a g e n t ( j a ) 和全局 a g e n t ( g 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 柔性车间调度系统进行的仿真实验。利用a r e n a 仿真软 件，对不同车间负荷水平和工期紧迫度系数的车间环境进行了仿真实验，对实验 结果进行分析。 第五章是对合作权重进行实时调整。本章节的内容是在第三、四章内容的基 础上进行研究的，也是本文的重点。通过第四章的实验，已经得到在不同的车间 环境下最优的合作权重值。当车间出现变动时，通过探测车间最新的状态，及时 的调整权重，以适应生产车间动态多变的过程。 北京工业大学管理学硕士学位论史 1 0 第2 章相关理论研究 第2 章相关理论研究 2 1a g e n t 及相关问题 2 1 1a g e n t 的定义 2 0 世纪7 0 年代，美国麻省理工学院的研究人员开展了一系列与分布式人工 智能相关的研究，a g e n t 技术在计算机领域的研究和应用也由此开始。经研究人 员研究发现，通过协作可以将一些简单的信息系统组成一个较大的系统，从而可 以显著提高系统处理复杂问题的能力，而且通过确定合理的协商机制可以提升整 个系统的智力水平。也因此产生了具备一定的智能性，能被动的响应处理要求， 除完成计划的工作外，还能主动预测、积极寻求方法用来支持用户完成工作的软 件a g e n t 概念和方法。 。 关于a g e n t 的定义，学术界还没有统一的概念。在众多的定义中，比较常用 的是w o o l d r i g e 和j e n n i n g s 等人h 如提出的弱定义和强定义。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 是一种能够在特定的环境下感知环境，同时能够自主的运行实现一系 列设计目标的计算机实体或程序【5 0 1 。a g e n t 在一定的目