（机械制造及其自动化专业论文）网络环境下产品生产链智能调度研究.pdf

矗 j 、 ，莨t _ n b y l ih o n g f e n g s u p e r v i s o r ： a s s o c i a t ep r o f 宅s s o rs h e n gz h o n g q i n 0 r t h e a s t e r nu n i v e r s i t y f e b r u a r y2 0 0 8 本人声明，所呈 得的研究成果除加以 写过的研究成果，也 学位论文作者签名：茗、泼峥 日 期：彻许瑚刀日 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位 论文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印 件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文 的全部或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师不同意网上交流，请在下方签名；否则视为同意。) 学位论文作者签名：导师签名： 签字日期：签字日期： 多 j i - ， k q 酽 、 kiil， ，儿，- l l 0 k k l 东北大学硕士学位论文 摘要 网络环境下产品生产链智能调度研究 摘要 生产调度是现代企业管理不可回避的问题，它是控制与管理一体化的结合部。 向上它要给企业经营战略决策提出依据，向下要安排生产加工任务，指导监督控制 层的运作。随着全球化市场竞争的日趋激烈和顾客需求的多样化，仅仅对于单个车 间的生产调度研究已经渐渐适应不了市场全球化的发展变化。所以本文适时提出基 于产品生产链的调度问题。根据订单需求，将具有某些特定生产能力的企业，组成 一个企业联盟，各企业发挥自身的优势，以期达到资源优化配置，进而更好地完成 任务，从而实现利益共享的目的。同时，产品生产链的生产调度作为供应链管理中 重要的一环，也是供应链管理中需要重点研究的问题。 由于调度问题大多数都是具有n p 难度的组合优化问题，寻找具有多项式复杂 性的优化方法几乎是不可能的。所以许多专家学者在调度方法上做出了许多努力。 其中群体智能算法和基于多智能体技术的调度方法相对于传统的调度方法有诸多优 势，正成为当下的研究热点。本文就是运用群体智能算法中的蚁群算法和蜂群算法 以及多智能体方法解决生产链生产调度中的几类问题。 本文首先给出了生产链的定义、特点及其在供应链管理中的地位，然后以综述 的形式分析对比了传统调度方法和现代智能调度方法的各自特点及调度方法今后的 发展方向。论文主要研究了以下几类问题： 第一类问题：用蚁群算法解决生产链组建，也就是企业伙伴的选择问题。 第二类问题：用蜂群算法解决生产链内部生产任务不定期到达的调度问题。 第三类问题：采用多智能体方法解决生产链柔性调度问题。 关键词：生产调度；生产链；智能方法：蚁群算法；蜂群算法；多智能体 i i l，；f 一。，t夕 ，f厂l，l 东北大学硕士学位论文 r e s e a r c h0 ni n t e l l i g e n j 1 l o 乙n a l nl n p r o d u c t i o ns c h e d u l i n gi so n eo ft h ek e yi s s u e st h a tm o d e r ne n t e r p r i s em a n a g e m e n t c a n tg e ta r o u n d i th a sj o i n e dt h ee n t e r p r i s ec o m r o la n dm a n a g e m e n t i ti st h eb a s ef o r s u p p o r t i n gd e c i s i o n m a k i n go fe n t e r p r i s eo p e r a t i o ns t r a t e g i ca n da r r a n g i n gt a s kf 0 r p r o d u c tp r o c e s s i n g i ta l s os u p e r v i s e so p e r a t i o n so fp r o d u c t i o nc o n t r 0 1 a l o n gw i t ht h e g l o b a lv i g o r o u sc o m p e t i t i o na n dt h ec u s t o m e r s v a r i o u sr e q u i r e m e n t s ，t h es c h e d u l i n g r e s e a r c hju s tf o rjo b s h o pc a nn o tk e e pu pw i t hm a r k e t sd e v e l o p m e n tg r a d u a l l y s ot h i s p a p e rp u t sf o n v a r ds c h e d u l i n gp r o b l e mo r i e n t e do np r o d u c tp r o d u c t i o nc h a i n a c c o r d i n g t ot h eo r d e r ，s o m ee n t e r p r i s e sw h i c hh a v es p e c i f i cp r o d u c t i o nc o m p e t e n c ef o mal e a g u e w h e ne v e r ye n t e 印r i s ee x e r t si t sa d v a n t a g e s ，t h er e s o u r c ei sw e l lu s e d 锄dt h et a s ki sw e l l a c c o m p l i s h e d ，a n de v e r ) ，e n t e 印r i s ec a ns h a r eb e n e f i tb a s e d o nl e a g u e i na d d i t i o n ， p r o d u c t i o nc h a i ni si m p o r t 孤l tt ot h es u p p l yc h a i nm a n a g e m e n t ，w h i c hd e m a n d st ob e s t u d i e dd e e p l y s e e k i n go p t i m i z a t i o nm e t h o dw i t hp o l y n o m i a l c o m p l e x i t yi s a l m o s ti m p o s s i b l e b e c a u s em o s to fs c h e d u l i n gp r o b l e m sa r ec o m b i n a t i o no p t i m i z a t i o np r o b l e m sw h i c ha r e n ph a r d e x p e r t sa n ds c h o l a r sd i dm a n ye f f o r t s i nr e s e a r c ho fs c h e d u l i n gm e t h o d s c o m p a r i n gw i t ht r a d i t i o n a ls c h e d u l i n gm e t h o d s ， s w a r mi n t e l l i g e n t a l g o r i t h m sa n d s c h e d u l i n gt e c h n o l o g yb a s e do nm u l t i - a g e n th a v el o t so fa d v a n t a g e s ，w h i c ha r es t u d i e d c o n t i n u a l l yb yt h er e s e a r c h e r s t h i sp a p e ru s e sa n tc o l o n ya l g o r i t h m ，w a s pc o l o n y a l g o r i t ，a n dm u l t i - a g e n tt os o l v ep r o b l e m so fp r o d u c t i o ns c h e d u l i n g i nt h ef r o n to ft h i sp a p e r ，t h ed e f i n i t i o n ，c h a r a c t e r i s t i c so fp r o d u c t i o nc h a i na n dt h e s t a t u si ns u p p l yc h a i nm a n a g e m e n ta r eg i v e n ；t h e nb o t ht r a d i t i o n a ls c h e d u l i n gm e t h o d a n dm o d e r ns c h e d u l i n gm e t h o da r ed i s c u s s e dc o m p a r a t i v e l y t h et r e n do fs c h e d u l i n g m e t h o dd e v e l o p m e n ti sa l s od i s c u s s e d t h em a i nc o n t e n to ft h i sp a p e rc o n t a i n ss o m e p r o b l e m sa sf o l l o w ： f i r s t l y ，h o wt of o r r nap r o d u c t i o nc h a i nb ya n tc o l o n ya l g o r i t h m i ti st h es a m ea sh o w t oc h o o s eg o o dp a r t e r s - i i i h；蠢 ： -i；v ， 膏 。 一 东北大学硕士学位论文 目录 目录 独创性声明i 摘要i i a b s t r a c t i i i 第一章绪论1 1 1 产品生产链的概念1 1 1 1 产品生产链的定义1 1 1 2 生产链企业联盟的形成2 1 1 3 生产链在供应链中的核心地位3 1 2 生产链企业联盟的生产调度问题4 1 2 1 生产调度问题的提出4 1 2 2 生产调度问题的研究现状5 1 2 3 生产调度问题的分类6 1 2 4 生产调度问题的特点：6 1 3 生产调度问题研究方法综述6 1 3 1 传统调度方法7 1 3 2 智能调度方法8 1 3 3 未来的发展方向1 0 1 4 现有调度管理存在的问题1 1 1 5 本课题的研究意义及主要工作一1 3 1 5 1 本课题的生产实践背景及研究意义1 3 1 5 2 本课题主要的研究工作1 4 第二章产品生产链智能调度研究总体设计1 6 2 1 生产链企业伙伴选择问题研究1 6 2 1 1 问题的产生及研究的必要性1 6 2 1 2 蚁群算法相关问题研究1 7 2 2 生产链生产任务不定期到达的调度问题研究1 9 2 2 1 问题的产生及研究的必要性1 9 2 2 2 蜂群算法产生及其应用1 9 v 东北大学硕士学位论文 目录 2 3 生产链柔性调度问题研究2 0 2 3 1 问题的产生及研究的必要性2 0 2 3 2 多智能体技术相关问题研究2 0 第三章基于蚁群算法的一类生产链调度问题研究- 2 3 3 1 该类调度问题描述及数学模型2 3 3 2 蚁群算法原理2 5 3 3 基于蚁群算法的生产链智能调度的实现2 6 3 3 1 基于蚁群算法的调度原理2 6 3 3 2 基于蚁群算法的调度问题算法设计2 7 3 3 3 算法实现步骤及流程图2 8 3 3 4 调度仿真实例验证3 0 第四章基于蜂群算法的一类生产链调度问题研究3 9 4 1 该类调度问题的描述3 9 4 2 蜂群算法原理4 0 4 3 基于蜂群算法生产链智能调度的实现4 0 4 3 1 基于蜂群算法的调度问题算法设计4 0 4 3 2 算法实现步骤及流程图4 1 4 3 3 调度仿真实例验证4 3 第五章基于多智能体协商的生产链调度问题研究5 2 5 1 该类调度问题的描述5 2 5 2 基于多智能体的生产链调度系统模型5 3 5 2 1 多智能体模型基础5 3 5 2 2 多智能体内部结构? 5 4 5 2 3 生产链调度系统中招标一投标协商模型5 7 5 3 基于多智能体协商的生产链动态调度研究5 8 5 3 1 基于加工资源不确定的多智能体动态调度5 9 5 3 2 基于工件集不确定的多智能体动态调度6 1 第六章结论与展望6 3 参考文献6 4 致谢6 7 硕士期间发表的论文6 8 v i 0 _ ? 夕 。，i1， i - ， 一 东北大学硕士学位论丈 。饕一加 1 1 产品生产链的概念 1 1 1 产品生产链的定义 产品生产链是供应链的一部分。一条完整的供应链应该包括供应商( 原材料供应 商、零部件供应商) 、生产商、销售商和运输商等。由于供应链管理中各领域问题的 复杂性，因而有必要根据供应链上各个阶段的任务不同对供应链管理问题进行分解， 以便得到有效解决。根据供应链管理对象和目标的特殊性，可以将供应链分解成生 产链、销售链和运输链。由此可见，生产链是供应链的起始链，也是一条重要的子 链，生产链管理是否有效对于整个供应链管理的成败有很深刻的影响。 从目前公开发表的论文看，对销售链管理和运输链管理有比较系统的研究。在 销售链管理上，主要强调企业与销售商的集成管理，也就是现代企业比较注重的分 销商的管理，常见的如汽车业。如h o s a n gj u n g 和b o n g j uj e o n g 提出一个生产一 销售计划系统，通过生产商与销售商合作解决供应链上的冲突问题，即解决不完善 的信息共享。而运输链管理多与物流公司合作，其管理则与物流管理有很大的相似 之处。而对于生产链管理方面的研究文献相对比较少见。图1 1 给出了供应链与生 产链的关系。本文给出生产链的定义如下。 供应链管理流程 图1 1 生产链与供应链关系图 f i g 1 1t h er e l a t i o n s h i pb e t w e e np r o d u c t i o nc h a i na n ds u p p l yc h a i n 生产链( p r o d u c t i o nc h a i n ) ，是一个由多个生产商组成的分布式动态生产联盟 网络。这里，生产商为了完成某种产品的生产任务而形成彼此联系的协作关系，而 这种协作关系主要体现在生产过程间的合作与协同。具体的说生产链是围绕核心企 1 东北大学硕士学位论文 第一章绪论 业将复杂零件工艺过程中的部分生产工序分别由网络中多个企业所提供的生产服务 完成，各生产服务之间按一定顺序组合成一个整体的服务链。在该服务链中，每一 个节点都是一个生产服务，节点之间的先后顺序关系由零件的结构特点、技术要求、 生产成本、质量以及交货期来确定的。 根据上述定义，生产链的特点可以归纳为以下几个方面： ( 1 )网络化根据各生产商地理位置分布特点，利用以i n t e r n e t 为标志的信 息高速公路，将分布在不同地理位置的生产资源连接成一个有机的整体，实现信息 交流和资源共享，零件生产通过竞争合作方式进行。 ( 2 ) 虚拟化生产链是基于网络空间的生产活动组织形式，零件生产的各个环 节由不同的企业来完成，采用虚拟企业的形式来组织管理。 ( 3 ) 技术最优化为了生产某种复杂零件或接收某个订单，盟主企业可以在网 络空间中寻求技术设备最好、具有生产能力的合作伙伴，各个企业可以充分发挥其 技术优势，形成最优组合以达到技术的最优化。 ( 4 ) 开放性计算机互联网络的最大特点是开放性，建立在这个基础上的生产 链，也将是一个开放的系统。 ( 5 ) 分布集成性生产链由多个伙伴企业组成，这些企业在空间上分布在不同 的地域甚至跨越国界，这种地域上分散的缺点可以在计算机网络技术支持下通过信 息集成得以弥补。 1 1 2 生产链企业联盟的形成 虚拟企业是当今发达国家和先进企业竞相研发的2 1 世纪企业运行模式。我们可 以把它定义为“一些相互独立的业务实体或企业借助信息网络技术的支持，为迎合 快速变化的市场机遇，实现风险共担、利益共享的目标，对企业核心资源进行整合 而形成的暂时性联盟 【2 1 。由于虚拟企业以信息网络为支持，所以普遍将这些具有 生产能力的企业组成个网络，叫做企业网络。企业网络的主要目的是为虚拟企业 运行的各个阶段做好准备与管理工作。它通过建立企业成员之间的多边协议来对一 些事项进行规范，如通用标准、规程、知识产权以及信息通信技术等。当客户需求 到来时，一些准备与管理工作将会极大简化。企业网络可以看成是为了满足差异化 的客户需求而形成的潜在的虚拟企业的联盟。企业网络等待并寻求市场机遇，当识 别到特定的客户需求后，通过组建虚拟企业来实现市场机遇。在本论文中，我们可 以将这个虚拟企业狭义地理解为生产链。当特定的生产任务完成后，生产链也就解 散了，但企业网络仍然存在。通过企业网络通常可以组建多条生产链。相对于生产 一2 飞 东北大学硕士学位论文第一章绪论 链，企业网络成员具有更为长期的合作关系。在企业网络中组建一条高效的生产链， 关系到整条生产链的运营效率及经营业绩。 1 1 3 生产链在供应链中的核心地位 前已述及生产链的有效管理对于整个供应链管理有很深刻的影响。产品的销售、 运输安排的无论多周密，一旦产品没有按时生产出来，则耗费了比预算大得多的人 力、物力、财力，就注定了整个供应链管理达不到预期的效果。下面，通过汽车行 业的供应链管理来说明生产链在供应链中所处的位置及其重要性。 汽车行业的供应链管理模式是一种最典型的供应链组织结构模式。汽车工业按 照本身的生产与市场发展规律，形成了自己行业的体系结构，即汽车工业的从原材 料供应、零件加工、零部件配套、整车装配到汽车销售乃至售后服务的一整套供应 生产销售售后服务的供应链体系结构。 工艺供应国 并尸 图1 2 以汽车制造企业为核心的供应链管理模式 f i g 1 2t h es u p p l yc h a i nm a n a g e m e n tf o rt h em a n u f a c t u r eo fa u t o m o b i l e 从图1 2 我们可以看出，在这种供应链管理模式中，生产企业是供应链的物流 调度与管理中心，适时地向供应商发出需求指令，向分销商发出供货指令，确保各 个环节的企业都能在合适的时间，得到合适品质、合适数量与合适规模型号的原材 料、零部件或半成品，又不发生库存积压，并使供应链的总成本最小。同时，生产 企业又是供应链的信息集成与交互中心、协调控制中心。生产企业除了能创造特定 价值、长期控制比竞争对手更擅长的核心业务外，还要负责各业务流程的协调与控 制、各功能环节的协调与控制，各节点企业间的权责利关系的协调与控制以及供应 链与外部环境之间的协调与控制，以保证供应链发挥整体最优效果。 所以，在这种模式下，生产商能对供应物流、生产物流以及分销物流拥有完全 3 - 东北大学硕士学位论文第一章绪论 的控制权，能够掌握第一手的客户反馈信息，充分改善客户服务。同时，由于汽车 生产企业，特别是大型汽车集团，在产品设计、生产、装配等方面具有强大优势， 可以拉动上游供应商的原材料供应，也可以推动下游分销商的产品分销及客户服务， 所以，汽车生产企业具备汽车行业供应链的核心企业的特点，它具有一定核心能力， 在供应链上发挥核心主导作用。因此，它也就当仁不让地成为了传统供应链管理模 式下的核心。 1 2 生产链企业联盟的生产调度问题 对生产链的管理包括很多部分，如生产计划的制定、生产任务的分解、生产调 度等。其中，由于市场的瞬息万变、客户的个性化需求以及生产过程中随时可能出 现的突发事件，生产调度管理成为当前的一个研究难点，也是热点。调度就是为了 实现某一目的而对共同使用的资源实施时间的分配【3 1 。一个调度满足问题( 调度问 题) 是一个约束满足问题，它的一个状态是集合r 和t 间的二元关系，其中r 是资 源的集合( 资源空间) ，t 是任务的集合( 任务空间) 。它涉及的范围也相当广泛的， 包括制造业、交通运输业、经济金融业和管理领域等。现实世界中的调度问题各式 各样，如时间表调度( t i m et a b l es c h e d u l i n g ) 、人员调度( c r e ws c h e d u l i n g ) 、 作业车间调度( j o bs h o ps c h e d u l i n g ) 等。调度和优化有着密切的关系。优化是调 度的目的，而调度是优化的一种具体表现形式。所以调度问题又称为优化调度问题。 本文生产链智能调度研究的就是在生产链环境下对下属成员企业的生产任务进行调 度。 至今为止，人们对优化和调度问题的研究己经形成了较为系统的理论体系，很 多成果得到了实际应用。现己开发出了很多基于约束的调度系统，如i s i s 、s o j a 、 f l y p a s t 、s o m a 、d a s 和最近在基于工业的程序设计工具范围内资源约束的实现，如 c h i p 、o z 、c l a i r e 和i l o gs c h e d u l e 等产品【3 】。 1 2 1 生产调度问题的提出 2 1 世纪是技术革新的时代。特别在制造行业，先进的制造技术及理念不断涌出， 如敏捷制造、精益生产、网络化制造、准时制生产和并行工程等。一段时间内，这 些技术的应用为生产效率的提高做出了巨大的贡献。但是，同时人们也发现只有掌 握了先进的调度技术先进的制造技术才会显著地提高生产效率：先进的制造技术只 有在先进的调度系统中才会发出耀眼的光彩，对于提高企业的竞争力，两者缺一不 可。如2 1 世纪先进制造模式之一的敏捷制造，它就综合了准时制生产( j u s ti n 4 东北大学硕士学位论文第一章绪论 t i m e ，j i t ) 、并行工程和精益制造等多种先进制造模式的思想，在信息集成和共享的 基础上，通过分布式结构连接各类企业，构成虚拟制造环境，从而快速高效地实现 企业内外部资源( 包括管理、人员、技术) 合理、优化的配置，以便赢得市场竞争。 在具备了先进制造技术的前提下如何进行组织管理，包括如何组织动态联盟、如何 重构车间和单元、如何安排生产计划和如何进行调度都是我们面临的问题。 1 2 2 生产调度问题的研究现状 调度问题的研究从二十世纪五十年代起就受到应用数学、运筹学、自动化和人 工智能等领域科学家的重视，科学家们利用运筹学中线性规划、整数规划、目标规 划、动态规划及决策分析等方法，研究并解决了一系列具有代表意义的调度和优化 问题。 人们普遍把c o n w a y 、m a x w e l l 和m i l l e r 三人有关调度的研究工作作为调度理论 研究的正式开始，他们三人也被人们称为调度理论的奠基人。按照他们的定义，所 谓调度是指“如何分配一系列资源去完成一系列任务 。在生产系统中，调度被定义 为“如何分配一系列加工资源( 机器) ，使它们在一定的时间内完成一系列的任务订 单 。于是，生产调度表现为一个排序问题。为区别起见，他们把工件在一台机器上 的排产定义为“排序 ，而将对于多个不同机器上工件的排序问题命名为“调度”。 调度的结果是调度时序表。它是一个“任务一时间 表，是一个“关于每一个项目 以及为完成这些项目所采取的必须操作的执行序列随时间分配的计划”。这样，生产 调度问题被描述为一个“在一定的初始条件和约束条件下寻求使某一性能指标最优 的数学问题，即一个最优化计算或最优控制问题。研究证明，这是一类难以解决的 n p 完全问题。 2 0 世纪7 0 年代后期，经典调度理论取得了重要进展，并且作为一门应用数学 学科己经基本成熟，但是实际调度问题与经典调度问题还有相当的距离。严重阻碍 经典调度理论研究取得重大进展和突破的关键还是调度问题的n p 性质。实际调度问 题往往都是非常复杂的，没有确定的物理和自然规律可循，因此是非常难解的，并 且大多是没有精确解的。从2 0 世纪8 0 年代初开始，人们就一直在尝试并致力于解 决实际调度问题，调度研究由理论研究转向应用研究阶段。在这样的历史背景下， 应用人工智能、计算智能和实时智能研究成果，解决实际调度问题的智能调度方法 就走上了历史的舞台。分布式人工智能的发展促使生产调度系统从传统的集中式转 向分布式，其中多智能体技术在调度研究领域的应用研究日益活跃起来，并且开始 成为一个重要的研究方向。 - 5 - 东北大学硕士学位论文 第一章绪论 1 2 3 生产调度问题的分类l 调度问题被认为是典型的n p 岫a r d 问题。生产调度问题的分类方法很多，主要 为以下几类方法：( 1 ) 根据加工系统的复杂程度分为单机、多机并行；( 2 ) 根据性 能指标分为基于调度费用和调度性能的指标两类；( 3 ) 根据生产环境的特点分为确 定性调度和随机性调度；( 4 ) 根据作业加工的特点分为静态调度和动态调度；( 5 ) 一 根据工件的加工路线分为流水车间调度( f l o w s h o p ) ，其各工件的加工路径一致； 作业车间调度( j o b s h o p ) ，各工件的加工路径不一致。 广 1 2 4 生产调度问题的特点 ( 1 ) 高复杂性 调度问题所涉及的变量繁多，由于装卸作业、设备、库房，搬运系统之间的相 互影响、相互作用；每个作业又要考虑到它的到达时间、装卸时间、准备时间、操 作顺序和交货期等，致使实际调度问题相当复杂。这就使得想要精确描述其间的各 种约束关系并建立其数学模型变得困难和复杂。 此外，从计算量来说，调度问题往往是n p c 或n p h a r d 问题，即求其最优化解 的计算量随着问题规模的增长呈指数关系的增长，一般的优化方法对此无能为力。 ( 2 ) 多目标性 调度的目标很多，如最短生产期，最大生产利润，最小拖期惩罚等。这些目标之间 t 往往有抵触，使各个目标都最优是不可能的。目前的优化目标常常是多目标的综合 考虑，包括成本目标、资源利用率目标、利润目标等。 ( 3 ) 动态随机性 在实际的生产调度中存在很多随机的和不确定的因素，比如作业到达时间的不 确定性、作业加工时间的随机性，而且生产系统中常出现一些突发偶然事件，如设 备的损坏维修、交货期的改变等等。 1 3 生产调度问题研究方法综述 生产调度是生产管理的核心内容和关键技术。科学地制定生产调度方案对于控 制在制品库存、提高产品交货期满足率、缩短产品供货周期和提高企业生产率起着 至关重要的作用。传统的对生产调度的研究是在如下假设条件下进行的： 1 ) 被调度的工件集合是确定的； 。 2 ) 工件的加工时间是确定的，并且在安排计划时全部工件都已到达： i 东北大学硕士学位论文 第一章绪论 3 ) 加工工件的机器是连续可用的； 这类调度问题是静态调度问题。 实际生产中的大量问题是随机发生的。如在机械制造业中，由于工件随机到达、 加工机器出现故障等随机事件，使得预调度不能正常执行，这就需要安排重调度。 这类问题是动态环境下生产调度问题。动态调度的概念出现较早，j a c k s o n 【4 j 于1 9 5 7 年便对静态调度和动态调度的概念做了区分。最初的研究主要采用启发式方法或仿 真方法，与实际应用有较大的距离。近年来，计算机技术的迅速发展以及人工智能、 神经网络、遗传算法和仿真技术等新方法的产生和发展，为动态调度的研究开辟了 新思路，也为生产调度的实用化奠定了基础。目前，动态调度已成为生产调度研究 中的热点之一。下文对动态调度的研究方法和最新进展进行系统的介绍，对动态调 度的各种研究方法做了分类，并对各种方法逐一地进行分析。最后指出应进一步研 究的问题和未来可能的发展方向。 本文将研究动态调度的方法分成两大类，即传统方法和智能方法。传统方法包 括最优化方法、仿真方法和启发式方法。智能方法包括专家系统、人工神经网络、 智能搜索算法和多智能体( m u l t i a g e n t ) 方法。 1 3 1 传统调度方法 ( 1 ) 最优化方法 最优化方法主要包括数学规划( 动态规划、混合整数线性规划等) 、分支定界法 和消去法等。这类方法通常基于某些简化的假设，并能产生一个最优调度方案。 现己证明，绝大多数调度问题是n p 问题，随着调度问题规模的增大，上述方法 的求解难度将急剧增加，因而最优化方法往往不能适应生产实际对实时性的要求。 此外，该类方法大多基于某些理想化的假设，远不能充分反映实际生产环境的复杂 性，而且要充分表达实际生产环境的随机性和动态性也极为困难，所以单独使用此 类方法来解决动态调度问题是不现实的。 目前在动态调度的研究中，通常将最优化方法同其它方法相结合，用来解决一 定的问题。例如m a t s u u r a 【6 】提出的重调度算法，首先用分支定界法产生一个调度， 当工况发生变化时，再用调度规则来分配工件。 ( 2 ) 启发式方法 启发式方法针对调度问题的n p 特性，并不企图在多项式内求得问题的最优解， 而是在计算时间和调度效果之间进行折中，以较小的计算量来得到近优或满意解。 启发式方法通常称为调度规则。关于调度规则的研究在很早以前便开始了，例如 7 -o ，- 东北大学硕士学位论文第一章绪论 t o h n s o n 【7 1 于1 9 5 4 年提出的j o h n s o n 算法等。p a n w a l k e r 等【8 1 对1 1 3 个调度规则做了 经典的分类，将调度规则分成3 大类，即优先级规则( 包括简单的优先级规则、简 单优先级规则的组合和加权优先级规则) 、启发式调度规则及其它规则，并对各规则 的适应情况做了总结。关于调度规则比较经典的综述性文献还有文献【9 】。由于调度 规则计算量小、效率高、实时性好，因而在动态调度研究中被广泛采用。但由于它 通常仅对一个目标提供可行解，并且缺乏对整体性能的有效把握和预见能力，因而 在实际应用中常将它与其它方法结合使用，利用其它方法根据具体情况选择合适的 调度规则。此外，新的启发式方法也不断提出。例如a b u m i z a r 等【1 0 j 提出一种重调 度算法，当扰动发生时，不是全部重新调度也不是等扰动解除后再继续原调度，而 是仅仅重新调度那些直接或间接受扰动影响的工件，从而减少了由于扰动引起的生 产周期的增加，同时也减少了与初始调度的偏差，效率和稳定性都较好。 ( 3 ) 仿真方法 仿真方法是动态调度研究中最常用的方法。该方法通过对实际生产环境的建模 来模拟实际生产环境，从而避开了对调度问题进行理论分析的困难。目前，仿真方 法在动态调度研究中主要有以下两方面内容： 1 ) 研究各种仿真参数对仿真结果的影响，以便在进行仿真实验时能做出恰当选 择，从而使仿真所取得的结论更全面、更具说服力。r a m a s h 【5 j 总结了大量的相关文 献，对仿真时应考虑的参数及各参数的取值范围做了详细介绍。 2 ) 将某些方法应用于某个仿真环境，通过仿真评价现有方法之间或新方法与现 有方法之间的优劣，从而总结出各方法的适用范围，或根据结论数据建立知识库或 产生神经网络的训练样本。l i u 等】做了大量仿真实验，从仿真数据中产生出训练 样本用于训练神经网络，并将训练后的神经网络用于动态调度。 由于仿真方法在模拟实际环境时做了某些假设和近似，而且仿真模型的建立较 多地依赖于诸如随机分布等参数的选择，因而仿真结论往往因模型的不同而不同， 很难取得一个一致的结论。然而，对多数生产调度问题而言，在缺乏有效的理论分 析的情况下，仿真仍不失为一种最受欢迎的方法。 1 3 2 智能调度方法 ( 1 )专家系统 专家系统在动态调度研究中占有重要地位，目前已有一些较成熟的调度专家系 统，例如i s i s 和o p i s 等。调度专家系统通常将领域知识和现场的各种约束表示成 知识库，然后按照现场实际情况从知识库中产生调度方案，并能对意外情况采取相 - 8 - 东北大学硕士学位论文 第一章绪论 应的对策。有效的领域模型和知识表示对于动态调度专家系统的设计十分重要。此 外，约束在调度知识库中也占据重要地位，因为调度的好坏在很大程度上依赖于其 对约束的满足程度。动态调度的决策参数具有很强的不确定性，为了有效地表示这 种不确定性，许多学者选择了概率论，而应用模糊集理论则是一种更为有效的方法。 在调度问题中应用模糊方法的优点在于，可为不精确约束的表示和应用提供丰富的 表述语言和系统的框架，并且能对模糊目标进行评价【2 】。 i s i s 【1 0 】是最早的基于人工智能( a r t i f i c i a li n t e l l i g e n c e ，a i ) 的调度系统之 一。该系统采用约束指导的搜索方法产生一个调度，动态情况则由重调度组件进行 处理，当冲突发生时，它通过有选择地放松某些约束来重新调度那些受影响的订单。 基于i s i s 开发的0 p i s 【1 1 1 是现有的基于知识的车间调度系统中最成熟的系统之一， 它根据情况使用面向资源或面向订单的动态调度策略。s o n i a 【1 2 】是一个包含预测和 反应调度组件的单件车间调度系统，反应组件用于解决由于各种原因产生的调度效 果与预期效果间的偏差，系统考虑的意外事件有操作延误、容量冲突和机器故障。 0 p a l 【1 3 】也是一个为单件车间设计的调度系统，它采用调度规则和启发式方法进行调 度。尽管0 p a l 中没有反应调度组件，但是当调度延误时，它可以根据车间的当前状 态重新产生一个调度。 ( 2 ) 神经网络方法 神经网络应用于调度问题已有十多年的历史，它在动态调度研究中的应用主要 集中在以下两方面：1 将调度问题看成一类组合优化问题，利用其并行处理能力来 降低计算的复杂性；2 利用其学习和适应能力将它用于调度知识的获取，以构造调 度决策模型。目前，利用神经网络解决动态调度问题已成为动态调度研究的一个热 点。在动态调度研究中应用最多的是b p 网，通过对它的训练来构造调度决策模型。 s i m 等【1 4 】提出一种专家神经网络方法，该方法用1 6 个神经网络分别从相应的训 练样本集中获取调度知识，用专家系统确定各子网的输入。由于神经网络的训练由 1 6 个子网分担，并且各子网可以并行训练，从而减少了训练时间。c h o 等【1 5 】提出一 种基于神经网络和仿真的鲁棒自适应调度器，该方法根据他人研究的结论确定神经 网络的结构和训练样本。尽管该网络结构具有较强的通用性，但由于每个人研究的 背景不尽相同，因此通过量化他人结论来产生训练样本必然会对网络性能造成影响。 j o n e s 等【1 6 】提出一种解决实时排序和调度问题混合方法的框架，综合运用了神经网 络、遗传算法和实时仿真等方法。但只是提供了一个框架，真正实施起来还需进一 步研究。l i u 等【1 0 1 提出一种用神经网络选择调度规则的方法，神经网络的输入对应 于所有待调度工件的加工路线和加工时间信息，输出对应于待选的调度规则。但该 9 - 东北大学硕士学位论文第一章绪论 方法需要大量的训练样本和很长的训练时间才能保证调度的效果；另外，随着问题 规模的增大，网络的规模也将急剧增大。 ( 3 ) 智能搜索算法 应用于调度问题的智能搜索方法包括模拟退火、禁忌搜索和遗传算法等。目前 在动态调度中使用最多的是遗传算法。遗传算法解决调度问题的优势在于它可以随 机地从一个调度跳到另一个调度，从而可以解决其它方法易于使解陷入局部最优的 问题。此外，它还具有计算速度快且易与其它算法相结合的优点，非常适合于解决 动态调度问题。应用遗传算法解决动态调度的文献较多，其中大多将遗传算法与其 它方法结合使用。l e e 等【1 7 1 用遗传算法和机器学习来解决单件车间的调度问题，用 机器学习来产生将工件下发到车间层的知识库，而用遗传算法在各台机器上分配工 件。j i a n 等提出一种f m s 的调度和重调度算法，该算法考虑了4 种动态事件，即 机器损坏、订单优先级提高、紧急订单下达和订单取消，用稳态遗传算法产生一个 初始调度，当意外事件发生时，根据具体情况仅重新调度那些直接受影响的工序。 ( 4 ) 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 系统的结构，不同的人有不同的观点。例如k o u i s s 等【1 9 1 根 据车间的物理布局来确定系统的结构，为每一个加工中心配备了一个a g e n t ，用于 解决对应加工中心内的调度。另外还设计了一个全局a g e n t ，用于监视整个制造系 统的状态，必要时为满足全局的需要可在各a g e n t 问进行协调。 研究表明，m u l t i a g e n t 特别适用于解决复杂问题，尤其是那些经典方法无法 解决的单元间有大量交互作用的问题。其优点是速度快、可靠性高、可扩展性强、 能处理带有空间分布的问题、对不确定性数据和知识有较好的容错性；此外，由于 是高度模块化系统，因而能澄清概念和简化设计。 1 3 3 未来的发展方向 传统方法中应用最多的是调度规则( 启发式算法) 和仿真方法。仿真方法几乎 在每种方法中都有应用。由于调度规则具有计算量小、效率高和实时性好等优点， 非常适用于动态调度。但它也有明显的缺点，因而通常需要与智能方法结合使用， 通过智能方法根据情况在备选规则间进行选择。典型的研究方法通常同时使用某种 智能方法、仿真方法和调度规则。 1o 东北大学硕士学位论文第一章绪论 智能调度方法如专家系统、神经网络和遗传算法等，既有许多优点，也有各自 的缺点。例如：神经网络的训练时间较长，对结果缺乏解释能力，并且网络结构及 算法参数不易确定；专家系统知识获取的难度大且扩展性较差，当问题偏离知识领 域时系统的性能将急剧下降；遗传算法的适应函数较难选取，处理实际问题时有时 不能满足实时性和调度效果的要求。因此，上述方法经常结合在一起使用，如专家 系统与神经网络相结合【14 1 、遗传算法与神经网络相结合【16 1 、遗传算法与专家系统相 结合等【17 1 。由于m u l t i a g e n t 方法具有速度快、可靠性高、可扩展性强等优点，将 成为研究的热点之一。 在科技日益发达的信息技术时代，动态调度问题必将大量应用于信息流处理。 在充分了解现有研究方法优缺点的基础上，开发新的更有效的动态调度问题的解决 方法十分必要。目前绝大多数调度系统还处于研究原型阶段，工业原型系统也大多 由大学或研究机构承担，真正应用于实际生产的调度系统并不多。因而今后应以研 究能在实际中