（机械制造及其自动化专业论文）基于多智能体的车间调度系统的研究.pdf

# f 北r 业人学硕士学位论文 基于多智能体车间调度的研究 摘要 2 1 世纪是信息时代，激烈的市场竞争向制造业提出新的挑战，旧的生产模式已经不适 应现代化生产的要求，大规模信息制造系统的研究也已经成为当前的热点问题。但是信息 制造系统内容复杂、范围广泛，很多领域的研究还很薄弱，车问调度系统的研究就是其中 之一。车间是制造系统的基本单元，车间的控制结构影响着整个系统的性能，然而车问调 度问题中大多具有n p 困难特性，有效的调度方法与优化己经成为先进制造技术的关键和 基础。当前制造业的发展以网络化、智能化和敏捷化为主要方向。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 y s t e m ) 的车间调度系统模型， 系统的智能化通过招标一一投标过程来体现，系统的动态性、多目标优化性、全局最优化 性，通过套奖罚制度和综合评价标准来具体实现，本文对其数学模型做出了详细介绍。 奖罚制度和综合评价标准，能够很好的满足现代制造系统的要求，很好的解决复杂车问的 调度问题，对于实现车间调度智能化起到了重要作用。 文章首先介绍了m u l t i - a g e n ts y s t 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 接收到任务招 标书时资源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 c c e s s 数据库，v i s u a l b a s i c 语言，在w i n d o w s 2 0 0 0 的平台下开发。 关键词：m u l t i a g e n t ，招标一一投标，奖罚系数，综合评价指标，动态调度 兰兰童堡墼竺竺鍪鱼堡塞垂丝塑堡垒 s t u d y o nt h es h o p s c h e d u l i n gs y s t e m b a s e do nm u i j l a g e n tt e c h n o l o g y a b s t r a c t t h e2 1s tc e n t u r yi sa ni n f o r m a t i o nt i m e s ，v e h e m e n tm a r k e tc o m p e t i t i o nt a k en e wc h a l l e n g e s t om a n u f a c t u r e s ot h eo l dp r o d u c t i v em o d e lh a s n ta d a p tt o 也er e q u i r e m e n to ft h em o d e r n i z e d m a n u f a c t u r e ，a n dt h es t u d yo fl a r g es c a l ei n f o r m a t i o n a lm a n u f a c t u r es y s t e mh a sb e e nt h et o p i c a l p r o b l e m b u t ，b e c a u s eo fc o m p l e xc o n t e n t sa n dw i d e s p r e a dr a n g e , t h es t u d i e si ns o m ef i e l d so f i n f o r m a t i o n a lm a n u f a c t u r es y s t e ma r ep o o r ；j o b s h o ps c h e d u l i n gi so n eo ft h es t u d i e s t h e j o b s h o pi st h ec e l lo f t h em a n u f a c t u r es y s t e m ，t h ec o n t r o lo f w h i c h e f f e c tt h ep e r f o r m a n c eo f t h e w h o l es y s t e m ，h o w e v e r , t h es c h e d u l i n gp r o b l e mh a st h ec h a r a c t e ro fn u m e r i c a lp r o b l e m ，s ot h e a f f e c t i v em e t h o d sa n dt h eo p t i m i z a t i o no fs c h e d u l i n gb e c o m et h ek e y n o w a d a y s ，t h e d e v e l o p m e n to fm a n u f a c t u r ef o c u s e so nn e t w o r k ，i n t e l l i g e n ta n da g i l 晦t h ea g e n tt e c h n o l o g y p r e s e n t san e wa p p r o a c hf o rt h es t u d yo f j o b - s h o ps c h e d u l i n g a g e n th a sb e c o m eah o tt e r mi nt h ed i s t r i b u t e d e n v i r o n m e n ta n do n eo f t h et o p i c si nt i l ea r t i f i c i a li n t e l l i g e n c ef i e l d a c c o r d i n gt ot h en a t i o n a la n di n t e r n a t i o n a lr e s e a r c h , t h i sp a p e ra n a l y s e st h et r a d i t i o n a l j o b s h o ps c h e d u l i n gs y s t e md e e p l na n d ，c r e a t e sam o d e lo f j o b - s h o ps c h e d u l i n gs y s t e mb a s e do n m u l t i a g e n ts y s t e m t h ei n t e l f i g e n tc h a r a c t e ri se m b o d i e db yi n v i t i n gt op u b l i cb i d d i n g ；t h e d y n a m i c ，m u l t ia i m sa n dg l o b a lo p t i m i s mc h a r a c t e ri sr e a l i z e db yas e to fr e w a r d - p u n i s h p r i n c i p l ea n ds y n t h e s i si n d e x ，o fw h i c hm a t h e m a t i c a l m o d e li si n t r o d u c e di np a p e r t h e r e w a r d - p u n i s hp r i n c i p l ea n ds y n t h e s i si n d e xc a r lm e e tt h en e e d so fm o d e m m a n u f a c t u r es y s t e m ， s o l v et h ec o m p l e xj o b s h o ps c h e d u l i n gp r o b l e m sa n dr e a c to nt h ei n t e l l i g e n t i z a t i o no f j o b s h o p s c h e d u l i n g ，w h i c hb a s e d o nm u l t i a g e n ts y s t e m t h ep a p e ri n t r o d u c e ss t r u c t u r a lm o d e lo fm u l t i a g e n ts y s t e m ，c o o p e r a t i v em e c h a n i s mo f a g e n t sa n dc o n t a c tn e tm o d e lt h a tf i t s t ot h ed i s t r i b u t e dc o n t r 0 1 t h es y s t e mi sb a s e do nt a s k a g e n t ，m a c h i n ea g e n ta n dh a r m o n i z a t i o nm a n a g e m e n ta g e n t i nt h es c h e d u l i n gs y s t e m ，t h e p r o g r a mo fi n v i t i n g t op u b i cb i d d i n gi sr e a l i z e dt h r o u g ht h r e ep r o c e d u r e s f i r s t ，t a s ka g e n t d i s a s s e m b l e st h et a s k ，t h e na c c o r d i n gt ot h ec h a r a c t e ro fe a c ht a s kd i s t r i b u t e sa n n o u n c e m e n to f t e n d e r ；s e c o n d l y , m a c h i n ea g e n tw i l le v a l u a t et h ea b i l i t yo f b i d ，w h e ni tr e c e i v e st h ei n v i t e ，t h e n s e n dt h eb i dt ot h eh a r m o n i z a t i o nm a n a g e m e n ta g e n t ；t h i r d l y , t h eh a r m o n i z a t i o nm a n a g e m e n t a g e n tv e r d i c tt h et e n d e ra c c o r d i n gt ot h es y n t h e s i si n d e x t h et a s ka g e n ta n dm a c h i n ea g e n tw i l l m o n i t o rp r o c e s s i n ga tt i m e s , w h i c hw i l lr e f l e c ti fa c c i d e n tc a s eh a p p e n s ；t h eh a r m o n i z a t i o n 型! ! 三些查兰丝圭兰些篁苎 m a n a g e m e n ta g e n tm e m o r i z e s t h es c h e d u l i n gr e c o r d e rt or e a l i z et h ei n t e l l i g e n l i z a t i o n l a s t l y ，b a s eo nt h es t u d yo nz h a n g j i a k o uc o l l i e r ym a c h i n ec o l t d ，d e v e l o pt h ea r t i f i c i a l i n t e l l i g e n ts c h e d u l i n gs y s t e ms o f t w a r eo nt h ef l a to fw i n d o w s2 0 0 0 t h ed a t a b a s ei sa c c e s sa n d t h ea d v a n c e dl a n g u a g ei sv i s u a lb a s i c k e y w o r d s ：m u l t i a g e n t ，i n v i t et op u b l i cb i d d i n g ，r e w a r d p u n i s h ，s y n t h e s i si n d e x ，d y n a m i c s c h e d u l i n g j j j 河北工业大学硕士学位论文 第一章绪论 1 1 引言 随着世界进入信息时代，制造业面i 瞄着新的挑战。制造业所处的环境不断改变，用户对产品的需求 也是千变万化，各不相同，今后的产品将是要按特定顾客的特殊需求设计与制造，产品趋于多样化，企 业面临着不断设计新产品的需求：每件产品的生产加工过程也各不相同，企业面临着不断重构制造系统 的需求。此种情况下，生产模式己经由单品种大批量生产转向多品种小批量生产。 激烈的市场竞争向制造业提出新的挑战专家预测在未来的几十年里，制造业的竞争焦点是制造系 统的柔性和对全球市场的快速反映。到了2 0 世纪中叶，现代化生产设备已经发展到了数控( n c ) 机床、 计算机数控( c n c ) 机床时代，使单机自动化技术水平发展到当代最高峰。借助于计算机技术和信息 处理技术，制造自动化在计算机辅助工艺和计算机辅助设计规划中得到长足发展，人们不断提出、建立 符合时代特征的制造系统新概念、新模式、新技术和新思想，极大的推动了制造业的发展。这些新思想 新技术包括：柔性制造系统( f m s ) 、敏捷锩4 造( a m ：a g i l e m a n u f a o t u r i n g ) 、精良生产皿p ：l e a n p r o d u c t i o n ) 、 并行工程( c e ：c o n c u r r e n te n g i n e e r i n g ) 、虚拟制造( v m ：v t r n t a lm a n u f a c t u r i n g ) 、快速成型制造( r p m ： r a p i dp r o t o t y p e ) 、多智能体系统( m a s ：m u l t i - a g e n ts y s t e m ) 、智能制造系统( i m s ：i n t e l l i g e n tm a n u f a c t u r i n g s y s t e m ) 等等。它们在不同时期、不同程度上推动了制造业的发展。 r a t a r i 等”熄出按照订单制造( m t o ：m a d e - t o o r d e r ) 的概念，以满足用户需求为宗旨来获得更多的 订单；1 w a t a t 2 1 在他提出的随机制造系统( r m s ：r a n d o m m a n u f a c t u r i n g s y s t e m ) 中强调按照订单生产( p t o ： p r o d u c t - t o - o r d e r ) ，使得制造系统需要对随机到达的订单或订单的变化做出及时反映；m i t c h e l l 等1 3 l 提出 企业要像“裁缝”那样制定满足顾客个性化要求的产品。这些思想和方法给制造业适应多变的市场提出 了比较好的解决方案，另一方面，也反映了市场要求企业向柔性化、快速反映方向发展a 1 2 车间调度的现状与发展 1 2 1 车间调度的定义 车间调度就是对一个可用的加工机床集在时间上进行加工任务集分配以满足一个性能指标集。它 实际是对于具体生产环境中复杂的、动态的、多目标的调度问题的一种抽象和简化。根据加工对象的加 工需求，运用不同的润度决策规贝l j ，规划系统加工事件，并根据系统动态仿真运行的结果或者优化结果 彤成最佳的生产加工顺序，同时实现设备集和任务集的最优化结合。典型的车间生产调度问题包括一个 耍完成的作业集，每个作业由一个操作集组成，各操作的完成需臻占用机床或其它资源，并且必须按一 些可行的工艺次序进行加j 二；每台机床可加工零件的若干操作，并且在不同机床上能加工的操作集可以 珂北工业大学硕士学位论文 第一章绪论 1 1 引言 随着世界进入信息时代，制造业面临着新的挑战。制造业所处的环境不断政变，用户对产品的需求 也是千变几化，粹不相同令后的产品将是要按特定顾客的特殊需求设计与制造，产品趋子多样化，企 业面临着不断设计新产品的需求 每件产品的生产加工过程也各不相同，企业面临着不断重构制造系统 的需求。此种情况f ，生产模式已经由孽品种大批量生产转向多品种小批量生产。 激烈的市场竞争向制造业提出新的挑战，专家预测在未来的几十年里，制造业的竞争焦点是制造系 统的柔性和对全球市场的快速反映。到了2 0 世纪中叶，现代化生产设备已经发展到了数控( n c ) 机床、 计算机数控( c n c ) 机床时代，使单机自动化技术水平发展到当代最高峰。借助于计算机技术和信息 处理技术，制造自动化在计算机辅助工艺和计算机辅助设计规划中得到长足发展，人们不断提出、建立 符合时代特征的制造系统新概念、新模式、新技术和新思想，极大的推动了制造业的发展。这些新思想 新技术包括：柔性制造系统( f m s ) 、敏捷制造( a m ：a 西l e m a n u f a c t u r i n g ) 、精良生产( l p ：l e a n p r o d u c t i o n ) 、 并行t 程( c e ：c o n c u r r e n te n g i n e e r i n g ) 、虚拟制造f v m ：v i r t u a lm a n u f a e u w i n g o 、快速成型制造( r p m ： r a p i dp r o t o t y p e ) 、多智能体系统( m a s ：m u l t i a g e n ts y s 略m ) 、智能制造系统o m s , i n t e l l i g e n tm a n u f a c t u r i n g s y s t e m ) 等等。它们在不同时期、不同程度上推动了制造业的发展。 r a t a r i 等”1 提出按照订单制造( m t o ；m a d e - t o - o r d e r ) 的概念，以满足用户需求为宗旨来获得更多的 订单；1 w a t a b l 在他提出的随机制造系统艰m s ：r a n d o ml v l m l u f a e t m i n gs y s t e m ) 中强调按照订单生产口t o ： p r o d u c t t o - o r d e r ) ，使得制造系统需要对随机到达的订单或订单的变化做出及时反映im i t c h e l l 等p 1 提出 企业耍像“裁缝”那样制定满足顾客个性化要求的产品。这些思想和方法给制造业适应多变的市场提出 了比较好的解决方案，另一方面，也反映了市场要求企业向柔性化、快速反映方向发展。 1 2 车间调度的现状与发展 1 21 车间调度的定义 车间调度就是对一个可用的加工机床集在时间上进行加工任务集分配，以满足一个性能指标集，它 实际是对于具体生产环境中复杂的、动态的、多目标的调度问题的一种抽象和简化。根据加工对象的加 工需求，运用不同的调度决策规则，规划系统加工事件，并根据系统动态仿真运行的结果或者优化结果 形成最佳的生产加工顺序，同时实现设备集和任务集的最优化结合。典型的车间生产调度问题包括一个 要完成的作业集每个作业由一个操作集组成，各操作的完成需要占用机床或其它资源，并且必须按 些可行的工艺次序进行加t ；每台机床可加t 零件的若干操作，并且在不同机床上能加工的操作集可匕上 些可行的工艺次序进行加t ；每台机床可加t 零件的若干操作，并且在不同机床上能加工的操作集可匕上 量兰耋型璧竺塑三塑型塞垂竺竺型塞 不同。在约束条件下，调度的目标是将作业合理地安排到各机床，并合理安排作业的加丁次序和加丁开 始时间，同时优化一些性能指标i “。 1 2 2 乍闯调皮问题的分类与特点 当前，车间调度问题按不同的分类标准，可以分为以下几种类型口l ： 1 ， 根据需求产生的来源可分为开环车间和闭环车闷。 2 根据加工系统的复杂度分为单台处理机。多台并行机、f l o ws h o p 和j o bs h o p 。所谓f l o ws h o p 问题是指所有的作业都在同样的机器上加工，并且有一致的加工顺序和加工操作；j o bs h o p 则是最一般 的车间调度类型，它不要求作业的顺序和加工操作一致，并且允许一个作业加工具有不同的加工路径。 3 根据性能指标可以分为基丁凋度费刚和调度性能的指标。 4 根据生产环境的特点将调度问题分为确定性调度、随机性调度。 5 根据作业的加工特点分为静态调度、动态调度。静态调度是指所有加工的作业都处于待加工状 态，因此进行一次调度后所有作业的各个加工都被确定下来，而且在以后的加工过程中不再改变：动态 调度是指作业依次进入加工系统进行加工完成加工的作业依次离开，同时还要考虑实际加工环境中不 断出现的动态扰动，如作业的加工超时、机床损坏等。因此动态调度要根据系统中作业、机床等状况不 断地进行重新调度。 6 有序加工和无序加工。 在实际的工业环境中，现代车间调度类型往往是j o bs h o p 型的，且是动态的。实际的车间调度问题 有以下特点： 1 复杂性。车间中的制造过程是一个复杂的系统工程，用系统的观点来看，既要考虑系统整诔目 标的实现，又要注意子系统的具体特性的局部目标的实现。必须加以协调和平街，才能实现整个系统的 最优调度。车间中的作业、加工设备、搬运系统之间往往是相互作用的，同时每个作业又要考虑它的到 达时间、加工时间、安装时间、操作顺序以及交货日期等，由于车间调度问题是在等式或不等式约束下 求性能指标的优化，在计算量上往往是n p 完全问题，即随着问题规模的增大，对于求解最优化的计算 量呈指数增长，因丽使得一些常规的最优化方法往往无能为力。 2 动态随机性。动态随机性首先表现在由于一些临时、突发事件。如急件的加入或者交货日期的 提前，所以加工任务携带着动态、随机等特点；其次设备以及其它资源的临时故障等会迫使对原有的调 度结果进行修改或者重新分配。 3 多约束。在研究调度问题时，不仅要考虑机器约束和加工过程的时间约束，同时还要考虑其它 约束条件，如人员、工具、物流系统等。 4 多目标。调度的目标多种多样，在实际的调度中需要综合考虑各种目标。一次调度往往具有多 个目标，如加工时间最短、利润晟大、生产成本最低等，而且这多个目标之间有时互相冲突，需要对不 同目标加以协调，再次调度时，目标可能变化，因此需要动态调整目标。 1 2 3 车间调度问题的现状 车间调度问题从2 0 世纪5 0 年代开始被广泛研究，几十年的研究实践证明，有效的调度方法与优化 2 河北工业人学i 受士学位论文 技术己经成为先进制造技术的关键和基础，因此j ：间调度问题一直是人们广泛关注的问题“。随着制 造业的发展，大规模定制生产、全球化制造等对车间调度问题提出了新的要求。如何利用现有的资源， 在各种制约条件r ，高质量、高效率地完成制造任务，就成为现代企业在急剧变化的制造环境中，生存 和取得竞争优势的重要问题9 j 。 由于调度问题中大多具有n p 困难特性【9 l ，至今尚未形成一套系统的方法和理论，理论研究与实际 应川之间还存在着根人著距。导致不同的研究者从不同的角度研究某一方面的问题，产生了许多的车间 调度问题的类型和方法，并随着对各类调度问题研究的深入及各种交叉学科的发展，涌现出了许多新的 车间调度理论与方法1 9 l “。 传统的静态调度问题对生产调度的研究是在如下假设条件下进行的： 1 被调度的工件集合是确定的。 2 1 件的加丁时间是确定的。 3 加工工件的机器是无故障运行的。 然而，实际生产中的大量问题是随机发生的，例如有急件加工、设备故障或检修等随机事件和干扰 因素的存在，使得调度必须能够根据实际生产情况的变化进行调整。 车间调度问题研究方法最初是集中在整数规划、仿真和简单的规则上，存在调度结果不理想或对复 杂问题无能为力等问题，与实际应用有较大的距离。j a c k s o n 予1 9 5 7 年便对静态调度和动态调度的概念 做了区分。传统方法中应用最多的是调度规则( 启发式算法) ，它具有计算量小、效率高和实时性好等 优点，非常适合动态调度。但经常要与智能方法结合使用，通过智能方法根据情况在各选规则间进行选 择。 目前大多数文献都是对静态问题开展讨论，关于动态调度研究方法的研究已经成为国内外生产调度 研究的重点问题。近年来，随着相关科学和计算机技术的发展，出现了许多新的车间调度优化方法，比 如确定性最优化方法、基于启发式规则的调度方法、遗传算法、基于知识的调度方法、禁忌搜索法、仿 真调度法、神经网络优化法、启发式图搜索法、模拟退火法、拉氏松弛法以及基于离散事件动态系统 ( d e d s ) 的解析模型等方法，使得车间调度问题的研究方法向多元化方向发展。由于车间调度问题的 复杂性和解决方法的多样性，因此形成了各种研究方法和策略指导，目前车间调度的策略有多目标优化 策略、并行或分布策略、动态重调度策略、分解与成组策略、人机交互策略等等。这些方法大大发展了 动态调度理论，但是与实际车间调度应用还有较大距离，还有待于进一步研究。 1 2 4车问调度的优化目标与建模 车间调度的目的就是使资源得到最优的利用，关键问题也是瓶颈问题就是调度模型和算法建立，不 同规模的企业，考虑的优化目标是不同的，不同的优化目标下建立模型与算法就不尽相同，考虑的目标 越多调度算法和模型就越复杂。一般的优化目标有以下几种： 1 在一定时间周期内系统的产出最高。 2 系统生产所花的成本撮少。 3 系统内设备的利用率最高。 4 系统内的在制品最少。 3 基十多智能仆的车问调度系统的研究 5 加l ：单个零件时通过系统的时间最短。 制造系统车间调度建模的复杂性还体现在随着系统规模的扩大，所要考虑的信息呈爆炸性增欧的趋 势，与此同时，又要兼顾到调度方案的实时性和良好的调度效果，非常难于解决，目前尚未见到好的解 决方案和宴例。 到目前为f r ，研究调度问题的主要理论还是经典调度理论( c l a s s i c a ls c h e d u l i n g t h e o r y ) ，调度理论 的珂究是从五十年代开始，经过儿十年的研究，当前形成了几种有代表性的技术：排队法，循环网络法， 遗传算法，人上神经网络，p e t r i 网，模糊数学和系统仿真，同时学者们还在继续研究其它的各种启发 式算法。但到目前为止，尽管人们不断地提出新的优化算法，或将其它方面的一些思想和技术应用到调 度理论中去，也有人认为生产调度问题的研究方法和范围已有所扩大，但总的来说，调度问题的研究仍 然停留在经典调度理论研究的框架内，还没有出现重大的理论性突破。 1 排队法：排队法的制造模型是撮早将数学解析方法用于制造系统特性分析的模型，它建模方法 简单，求解方式简单，但是随着系统规模的加大，考虑的优化目标增多，排队法的求解速度会大人降低， 不能满足现在调度系统的要求。 2 循环网络法：认为系统中的每一种实体都按各自的方式循环地发生变化，而在这一循环中只有 静止和括动两种状态，这两种状态交替地出现。循环网络法能够直观地看出每一活动的主体，以及该活 动得以实现的条件，但是这种方法当系统过于庞大复杂事，系统的活动循环会十分复杂，也不利于计算 机求解。 3 p e 订i 刚：p e t r i 网有严密的数学基础，多种抽象层次的通用网论，对伟i 造系统建模不但能够清 晰地反映出系统的静态结构，还能反映出动态的系统部件之间的相互联系，因而被广泛地应用于复杂系 统的设计和作业调度分析之中。 4 人工神经网络：神经网络理论研究是近年来的一个热点，它被引入制造系统中，由于它是并行 的方法，速度很快而且适应性强，使得系统能够解决许多不同类型的调度问题，而且能够从全局来掌握、 实现综合调度，但是这种理论尚不成熟。 5 人工智能技术：多智能体系统的研究目前是分布式人工智能领域的研究热点。由于调度问题的 复杂性和并发性等特点，多智能体在调度上的应用较多。它将调度过程描述成满足约束的解空间中搜索 的过程，它利用智能表达技术把人的知识包括进去，同时使用各种搜索技术，力求给出一个令人满意的 解，另外，专家系统的研制给调度问题指明了一条通向应用的途径。 6 虚拟制造技术：利用计算机集成技术对所有必须的生产和制造括动进行全面建模和仿真，可以 加大企业柔性估测生产制造的环境负效应，但是我国虚拟制造技术的研究刚刚起步，这项技术尚没有成 功案例。 1 3 人工智能技术的发展 2 1 世纪人类社会将进入信息社会，信息成为屋重要的战略资源，它将转化为现代的智能工具。1 ： 业化社会将转向信息化社会，信息科学成为高新技术的源泉。农业社会，人们消费农产品，： 业社会消 费一l ：业产品，而在信息社会“比特”将成为主要消费品。人类对智能化的追求将导致“智能革命”。人 4 河北工业大学硕士学位论文 ：【智熊是“智能革命”的核心。无论是a t ( a r t i f i c i a li n t e l l i g e n c e ，人工智能) 还是d a l ( d i s t r i b u t e da r t i f i c i a l i n t e l l i g e n c e ，分布式人j ：智能) 、d c s ( d i s t r i b u t e dc o n t r o ls y s t e m ，分布式控制系统) 的发展方向均是智能 化。a g e n t 技术的诞生为分，布式人一1 智能、分布式控制系统的智能化提供了新的发展思路。分布式人工 智能发展的结果就是a g e n t 和m a s ( m u l t i a g e n ts y s t e m ) 的产生。控制系统的智能化也可以把a g e n t 和m a s 技术引入d c s 系统中，即控制子系统发展成为单个a g e n t ，而d c s 发展为m a s 。有关a i ，d a i 的研究成果为a g e n t ，m a s 的研究提供了丰厚的理论基础和应用前景。 1 3 1人f 智能的发展历程 2 0 世纪4 0 年代，在人工智能的萌芽时期，有两种不同的研究智能的途径，一是根据神经心理学的 研究，通过为神经活动建立数学模型来表现智能行为，这是智能结构的微观研究观点，如1 9 4 3 年w m c c u l l o c h 与p i t t s 为神经元建立的数学模型和w i e n e r 的控制论；二是从智能行为的角度来研究智能， 而不介意这种行为的产生原因，是智能的行为研究观点，如t u r i n g 实验。1 9 5 6 年，在美国的d a r t m o n t h 讨论会上，j m c c a r t h y ，h ，s i m o n ，a n e w e l l 与m m i n s h y 等学者提出了“人工智能”的术语。6 0 年 代，j m c c a r t h y 发表的符号处理语言原型，提供了用计算机程序设计作为人工智能的符号处理基础。 1 9 6 9 年，m m i n s k y 和s p a p e r t 合写了感知器，这本书提出了感知机算法存在的问题。基于上述一 系列研究的基础之上，e f e i g e n b a u g n 提出了第一个专家系统d e n d r a l ，用于分析化学分子。8 0 年代， 掀起了被称为连接机制的研究高潮，即h o p f i e l d 和d r u m e l h a l t 等人对神经网络的研究。符号机制和连 接机制采用了完全不同的表示方法，两者互相结合、互为补充，推动了人工智能的发展。8 0 年代后期， h h o l l a n d 提出的基于自然选择的遗传进化模型，使用类似基因结构的表示法来发现新的规则。二十世 纪九十年代，随着计算机网络、计算机通信等技术的发展。对于a g e n t 的研究成为分布式人工智能的一 个热点。 1 3 2 人工智能研究的主要内容 人工智能主要研究知识表示，自动推理和搜索方法，机器学习和知识获取，知识处理系统，自然 语言理解，计算机视觉，智能机器人，软件自动化等方面。 1 知识表示是基本问题之一，推理和搜索都与表示方法密切相关。常用的知识表示方法有：逻辑 表示法、产生式表示法、语义网络表示法和框架表示法等，近年来，使用图像、图形直接表示知识并参 加推理的直接表示法得到人们的关注。知识可以分为三个层次l “1 ：常识层次：指人们直觉的、日常 使用的那些非专业知识，它们不一定在任何情况下正确，但是常常对问题的求解起到关键性的作用，最 低层，推理能力最强：知识层次：中层：行为层次：最高层。 2 推理过程一般可分为演绎推理和非演绎推理。谓词逻辑是演绎推理的基础。结构化表示下的继 承推理是非演绎性推理。近年来，提出了多种非演绎性推理的方法，如连接机制推理、类比推理、基于 事例的推理、反绎推理和受限推理等。 3 搜索是人：l ：智能的一种问题求解方法，搜索策略决定着在问题求解的一个推理步骤中知识被使 用的优先次序。可分为无信息导引的盲目搜索和利用经验知识导引的启发式搜索。通常用启发式函数表 示启发式知识。 5 基于多智能体的车间调度系统的埘l 究 4 机器学习指在一定的知识表示意义下获得新知识的过程。按学习机制可分为：归纳学习、分析 学习、连接机制学习和遗传学习等。 5 知识处理系统主要有知识库和推理机组成。知识库中存储着系统所需的知识。推理机在问题求 解时，规定使用知识的基本方法和策略，记录推理过程中的结果或通信结果需设数据库或采用黑板通信 机制。如果在知识库中存储的知识是某一领域的专家知识的话，则系统就成为专家系统。 6 人与机器进行自然的对话，利用能被机器理解的自然语言来描述现实世界。自然语言的理解包 括语法分析、语义分析和语用分析。好多有关a g e n t 的研究是基于语义分析的l 】。”】。 1 4 本课题的研究意义与主要研究内容 1 4 1 课题研究意义 目前，我国一般企业中，生产调度的工作是由老技术工人来完成，他们完全靠经验米安排。如今， 随着企业之间的竞争越来越激烈，产品的寿命周期变得越来越短，产品的品种变得越来越复杂多样，以 往的大批量少品种的生产模式渐渐变成了小批量多品种的生产模式；不仅每天的生产品种在不断地改 变，而且在客户就是上帝的口号下，己经安排好的调度计划会突然由于客户需求的改变而改变。于是调 度t 作也逐渐变成一项纷繁复杂的日常性工作。面对着这些变化和随时可能发生的生产加工环境的改 变，如机床设备的突然损坏等等情况要使企业的生产能力和效率始终保持较高的水平，仅仅依靠经验 是不能胜任的。在技术装备较为先进的企业中，它们一般拥有m r p i i 或e r p 等生产管理软件，但这些 软件都不具各对生产车间级的调控管理功能，所以同样面临着与一般企业相同的问题。如何较好地解决 这一问题是当前企业界与学术界都十分紧迫的任务之一。 自从我国成功加入了w t o 。国内市场国际化与国际竞争国内化己让国内制造业感到了迎面而来的 压力。为了在激烈的竞争中立于不败，光靠低廉的劳动力是远远不够的；对于制造企业而言，保持生产 车间较高的生产能力和效率是当务之急。研究多资源生产动态优化调度问题，对促进企业中车间级生产 管理的发展和各种生产资源的合理优化配置，对提高我国制造业入世后的竞争力都具有重要的意义。 当前，我国制造业正处于一个重大的历史变革时期。国有大中型制造企业生产经营模式的改造已 经刻不容缓。同时，信息网络技术的迅速发展，使m u l t i a g e n t 制造模式成为可能，为智能制造系统的 研究提供了广阔空间。我们应该抓住这个难得的机遇。尽快完成生产经营模式的转变，迅速投入国际化 竞争环境中去，振兴我国的制造行业。 i 4 2课题来源与主要j 二作 本课题是天津市教委科研基金项目，以张家口煤矿机械有限公司为对象，借鉴国内外相关的研究 成果，以现有的资源和生产为基础，提出了一种新的将多智能体技术应用于车间调度的调度模型。具体 研究内容如一f ： 第一章绪论 第二章介绍了代理( a g e n t ) 的概念和特点，分析单个a g e n t 的结构模型和多代理系统( m u l t i a g e n t s y s t e m ) 的结构模型。详细介绍合同网模型，分析了合同网模型的一r 作机制。 6 f 町北工业大学顺上学位论史 第三章介绍午间凋度的基本框架和调度系统的机构与功能。提出基于m u l t i a g e n t 的车间调度系 统模型。本章还耍介纠各个a g e n t 之间的相互协作、调度机制和嘲度规则。 第四章土耍建立基t - m u l t i a g e n t 技术的招标一一投标调度模型。此外，本章还将提出几种动态 调度的策略。最后提i u 一种简单的自学习模型，使系统具有了简单的记忆性。 第五章建立基于多智能体的车间调度系统。详细介绍智能调度系统的开发与功能实现。 第六章对本课题的研究做总结，提出存在问题。 7 幕十多智能体的车问调度系统的研究 第二章 a g e n t 与m u l t i a g e n t 模型 2 1 智能体( a g e n t ) 的概念 a g e n t 技术是一个迅速发展的领域。a i ( a r t i f i c i a li n t e l l i g e n c e ，人工智能) 和d a i ( d i s t r i b u t e d a r t i f i c i a l i n t e l l i g e n c e ，分布式人工智能) 的发展和研究成果为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 技术做基本介绍。 2 1 1 a g e n t 的定义 1 9 8 6 年，美国m i n s k y 教授在心智社会( ”t h es o c i e r y o f m i n d ”) 一书中提出了a g e n t 概念【i 7 1 。 用它来描述一个具有自适应、自治能力的硬件、软件或其它任何自然物和人造物，并认为a g e n t 是有技 能的个体，应具有社会交互性和智能性。而a g e n t 最初的思想可以追溯到二十世纪七十年代h e w i t t 对 分布式人工智能的研究，特别是他的并行行动者模型，对a g e n t 的提出起到了很大的推动作用i l 。 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 的研究不仅成为分布 式人上智能的一个热点，而且也是信息技术、制造技术等相关技术领域关注的一个热点1 1 9 - 2 2 。 尽管代理现在己被j “泛地应用在相关的领域，但是它还没有一个统一明确的定义。通过文献“ “j 中所述定义，本文将代理( a g e n t ) 概括为是一个充分自治的、具有感知性、自主性和协作性的实体， 能够根据对所处环境和与外界交互所获取的信息来决策和控制行为。 2 1 2 a g e n t 的特点与分类 2 1 2 1 智能体的特点 到目前为i l ，l 4 1 j 己经对代理达成了某些共识。一般认为，代理具有以下的一些基本属性陋3 8 河北丁业大学坝学位论文 l ， 自卡性( a u t