（机械制造及其自动化专业论文）mes生产调度系统的研究.pdf

摘要 摘要 摘要；m e $ ( 镦造执行系统) 处于计划层和控制层之闯，在企业信息化中起着承 上启下的桥梁作用，它主要的功能是生产调度指挥，因此本文把生产调度系统作 为m e s 研究的重点本文首先介绍了m e s 的产生、定义、发展历程、功能及其 发展现状。同时也分析了i v i e s 生产调度问题的各种解决方法及其存在的问题；接 着以c ym e s ( 某烟厂制造执行系统) 为背景介绍了其支撑平台s 硪t 觚wr r 平 台的功能及其各组成部分，以及c ym e g 的s i m a t i ci t 整体解决方案；紧接着 在s n 订a t i cr r 平台基础上，针对该烟厂的生产实际情况，设计了c ym e s 生产 调度系统的软件结构、功能结构、工单和予工单的数据结构和制丝与卷包生产调 度的实现方式；最后，在比较了各种生产调度建模方法的利弊和对该烟厂制丝生 产工艺流程深入研究后，利用p e t r i 网建立了制丝生产调度模型，为了避免大量无 效个体的出现，对基本遗传算法进行了改进，采用单个体遗传算法对这个p e t r i 网 模型进行了优化，并给出了调度结果的对比。运行实例和仿真结果表明：p e t r i 网 模型和单个体遗传算法的结合对于制丝生产调度问题的解决是合适的，对其他类 似生产调度问题的解决也有一定的借鉴意义。 关键词：m e s ( 制造执行系统) ；生产调度；p e t r i 网；遗传算法 分类号：f 2 7 0 7 a b s t ra c t a b s t r a c t ：m 匣s ( m a n u f a c t u r i n ge x e c u t i o ns y s t e m ) t i e sb 吐w o 姐p l a nm a n a g c r m e n t l e v e la n dp r o d 眦- t i o nc o n t r o ll e v e l , w o r k s 勰雒i n f o r m a t i o nb r i d g ei n 缸e n t e f p f i s e s i n f o r m a t i o n i z a t i o n i t sm a i nf i m c t i o ni sp r o d u c t i o ns c h e d u l i n g , 的t h i sd i s s e r t a t i o n s t u d i e sm e se m p h a s e si ni t sp l d d t l ( 冠o ns c h e d u l i n gs y s t e m t h i sd i s s e r t a t i o nf i s t l y i n t r o d u c e s i p 锄n c 。，d e f i n i t i o n , d w e l o p m e n tp _ o i 鼯，f i m c 吐啷a n ds t a t u so fm e s ， a l s oa n a l y s e sm e t h o d sa n de x i s t t m tp r o b l e m so fm e s p r o d u c t i o ns c h e d u l i n g ；勰f o l l o w , 诅t h eb a c k g r o u n do fc ym e s ( 矗钿溆p r i ，sm a n u f a c t m - i n ge x e c u t i o ns y s t e m ) , i n t r o d u c e sm a i nf u n c t i o na n db u i l d u po f i t ss u p p o r tp l a t f o r m s m t i cr la n dw h o l c s t n l c t m eo fc ym e s ；蚰删a r d s ，f o rs p e c i a lp r o d u c t i o ni l l s t , l m c o ft h e t c r p f i 鸭 d e s i g n sp r o d u 面o ns c h e d u l i n gs y s t v ms o i w a r e 蜕n l c h h 氐f u n c t i o ns t r u c t u r e , d a t a s t r u c t u r eo fo r d e ra n de n t r ya n dr o a l i z a t i o l lo fs i l kp r o d u c t i o na n dp a c k i n gp r o d u c t i o n s c h e d u l i n gb a s e d0 1 1s i m a t ci t ；f i n a l l y , a f t e rc o n t r a s to f m a n ym o d e l i n gm e t h o d sa n d c a r e f u lr e s e a r c ho fs i l kp r o d u c t i o nf l o wo ft h ee n t e r p r i s e , s e l e c t sp e t r in e tt om o d e lt h e s i l kp r o d u c t i o ns c h e d u l i n g , f o rt h es a k eo f a v o i d i n gm a n ye n ! o fc h r o m o s o m e s i m p r o v e s o nt h eb a s i cg e n e t i ca l g o r i t h m , u s 髂s i g l eu n i tg e n e t i ca l g o r i t h mt o0 l m m i z et h ep e t r in e t m o d e l ，l i s t st h ec o n t r a s to fs c h e d u l i n gr e s u l t s r u n i n gi n s t a n c ea n ds i m u l a t i o n p r o g r a m m ei n d i c a t e st h a t , c o m b i n a t i o no fp e t r in e ta n dg e n e t i ca l g o r i t h mi sp r o p e rt o s o l v es i l kp r o d u c t i o ns c h e d u l i n g , a n d 啪b eu s e df o rr e f c r e n c ci no t h e rs i m i l a r p r o d u c t i o ns c h e d u l i n g k e y w o r d s ：m e s ( m a n u f a c t u r i n g e x e c u t i o ns y s t e m ) ；p r o d u c t i o ns c h e d u l i n g ；p e t r i n e t ；g e n e t i ca l g o r i t h m ( g a ) c l a s s n o ：f 2 7 0 7 致谢 本论文的研究工作是在我的导师鄂明成副教授的悉心指导下完成的，鄂明成 副教授严谨的治学态度和科学的工作方法给了我极大的帮助和影响。在此衷心感 谢三年来鄂老师对我的关心和指导 同时，还要特别感谢实验室查建中教授、李建勇教授，姚燕安副教授、刘阶 萍副教授以及王恒博士，感谢老师们在生活和学习上给予的各种关心、帮助和指 导。 实习单位中科久辉的白小波老师、卓之兵博士、许力平老师、周齐心工程师、 杨辉工程师、赵秀娟工程师，须小萍工程师以及部门经理王军工程师对于我的科 研工作和论文都提出了许多的宝贵意见并给予了很大的帮助，在此表示衷心的感 谢。 在实验室工作及撰写论文期间，王兵师兄、陈智新、付长平、薛家兵、王倩 等同学对我论文中的研究工作给予了热情帮助，在此向他们表达我的感激之情 另外我要深深感谢父母多年来的操劳和挂念，他们的理解和支持使我能够在 学校专心完成我的学业。 作者：谢五峰 二零零六年十二月 1 绪论 1 绪论 1 1 制造执行系统( h e s ) 概述 1 1 1n e s 的产生及定义 制造业是国民经济的基础，制造业的发展也直接反映着一个国家综合国力的 强弱，如何不断提高制造业的信息化和自动化水平，一直是包括中国在内的世界 各国不断追求的目标经过各国坚持不懈的努力，先进制造企业大都已经建立了 以企业资源计划( 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 t ) 为代表的上层计划管理信息 系统，它主要的功能是宏观计划和财务管理，在底层的过程控制领域p l c 和d c $ 的大量应用提高了企业的底层自动化水平但是，e r p 注重的是企业的计划管理，。 它可以预测明天发生的各种变化并对昨天发生的生产过程作历史分析，但对今天 发生的事情留下了难以弥补的缺口，它的时间尺度一般是月、季度或周；底层控 制系统的控制系统的精度较高，它的时间精度一般为秒甚至是毫秒。这样，计划 管理系统和底层控制系统就出现了一个鸿沟，缺乏紧密的联系，当然也就无法满 足市场快速多变的需求。最先认识到这一问题并着手解决的是美国，上世纪8 0 年 代末9 0 年代初，美国在总结了e r p 实施成功率低的经验教训并吸取了日本的准时 制生产系统的经验基础上，提出了既重视计划又重视执行的企业管理理念，此时 连接计划管理和底层生产控制的制造执行系统( m a n u f a c t u r i n ge x e c u t i o ns y s t e m , m e s ) 应运而生f l l l 2 】【3 硅4 1 。 美国先进制造机构( a d v a n c e dm a n u f a c t u r i n gr e s e a r c h , a m r ) 将m e s 定义为 “位于上层计划管理系统与底层工业控制之间的，面向车间层的管理信息系统”， m e s 为操作人员、管理人员提供计划的执行、跟踪以及所有资源( 人、设备、物 料、客户需求等方面) 的当前状态信息。a m r 继1 9 9 0 年提出m e s 概念后，1 9 9 2 年又紧接着提出企业三层模型，如图1 所示。 制造执行系统协会( m a n u f a c t u r i n ge x e c u t i o ns y s t e m a s s o c i a t i o n , m e s a ) 也给 m e s 做出定义：“m e s 能通过信息传递，对从订单下达到产品完成整个的生产过 程进行优化管理，当工厂里面有实时事件发生时，m e s 能对此及时作出反应、报 告，并用当前的准确数据对它们进行指导和处理”l f l 6 。 从以上两个机构对m e s 的定义可以看出，m e s 和制造企业其它信息系统的区 别主要表现在：( 1 ) 更加重视实际计划的执行，更着重于实时信息的加工与处理； 北京交通大学硕士学位论文 ( 2 ) m e s 的主要功能是资源的优化配置和生产过程的优化管理，也就是说调度指 挥是其核心。 图la m r 企业三层模型 f 适le n t e r p r i s e t h r e e - l e v e lm o d e lo f a m r 1 1 2m e s 的发展历程 m e s 的概念虽然到上个世纪9 0 年代初才出现，但在7 0 年代末的时候，西方 发达国家部分企业已经出现具有m e s 功能系统的端倪。在开发m e s 方面，要首 数西门子公司。m a n n e s m a n n 钢管厂和钢板厂是西门子最早的客户之一，1 9 7 5 年 m a n n e s m a n n 委托西门子开发具有m e s 功能的管材管理系统，其他功能由西门予 逐步完善。在国内，应用最早的要数上海宝山钢铁公司。1 9 9 2 年，西门子取得的 宝山冷轧带钢厂和1 9 9 4 年宝山热轧带钢厂m e s 订单，这是中国最早的m e s 系统。 m e s 的发展大概可以分为两个时期和三个阶段： ( 1 ) 上世纪7 0 年代末一上世纪9 0 年代末，传统的m e s ( t r a d i t i o n a l m e s , t - m e s ) 时期。 该时期的m e s 大体可以分为两类，即前两个阶段：专用m e s 系统( p o i n t m e s ) 和集成m e s 系统( i n t e g r a t e dm e s ) 。前者是为了解决某个特定领域的问题而设计 和开发的自成一体的系统，例如某个企业的车问维护、生产监控等；而后者起初 是针对一个特定的、规范化的环境而设计的，目前已经拓展到许多领域，如航空、 装配、半导体、食品和卫生等行业，在功能上已实现了与上层事务处理和下层实 时控制系统的集成。前者能够为某一特定环境提供最好的性能，却常常难以与其 他应用系统集成。集成的i v i e s ，比专用m e s 迈进了一大步，具有很多优点：如单 2 l 绪论 一的逻辑数据库、系统内部具有良好的集成性、统一的数据模型等 ( 2 ) 本世纪初一可集成的i v i e s ( h t c g r a t a b l em e s ，i i v i e s ) 时期 这时i v i e s 能将模块化组件技术应用到系统开发中，是前两类t - - i v i e s 的结合 从表现形式上看，具有专用m e s 的特点，即i - m e s 的部分功能作为可重用组件单 独销售；同时又具有集成的m e s 的特点，即能实现上下两层的集成此外，i m e s 还能实现客户化、可重构、可扩展和互操作等特性，能方便地实现不同厂商 之问的集成和遗产系统的保护，以及即插即用等功能p j 1 3m e s 的功能 m e s 不仅仅是一项单独的功能，它考虑工厂中的各种绩效评价指标，具有支 持、指导、跟踪各项重要生产活动的功能。m e s a 定义的m e s 系统适用于各种类 型的工厂，包括以下1 1 种功能： ( 1 ) 资源配置与状态管理( r e s o u r c e a l l o c a t i o n a n d s t a t u s ) 管理人员、设备、 物料等各项资源，指示、跟踪并记录各项工作； ( 2 ) 作业计划( o p e r a t i o n s d e t a i l e ds c h c d u l t n g ) 确定各项生产活动的顺 序和时间，实现资源约束条件下的工厂绩效优化； ( 3 ) 生产调度( d i s p a t c h i n gp r o d u c t i o nu n i m ) 调度作业计划，进行动态调度、 控制在制品库存；， ( 4 ) 文档管理( d o c u m e n tc o n t r 0 1 ) 控制与生产单元相关的记录，编辑和下 达生产指令； ( 5 ) 数据采集( d a t ac o l l e c t i o n a c q u i s i t i o n ) 监测，采集和组织生产数 据： ( 6 ) 人员管理( l a b o r m a n a g e m e n t ) 指导人员的使用、跟踪和提供人员的有 关状态； ( 7 ) 质量管理( q i l a l 时m a n a g e m e n t ) 记录、跟踪和分析质量数据： ( 8 ) 过程管理( p r o c e s sm a n a g e m e n t ) 根据生产计划和实际生产活动指导生 产进程； ( 9 ) 维护管理( m a i n t e n a n c em a n a g e m e n t ) 计划和执行设备维护活动，维护 历史数据i ( 1 0 ) 产品跟踪( p r o d u c t t r a c k i n ga n d g e n e a l o g y ) 跟踪并显示产品的时空位 置，生产历史记录，以便对产品过程溯源； ( 1 1 ) 绩效分析( p e r f o r m a n c ea n a l y s i s ) 通过对信息的汇总分析，以离线或 在线的形式提供对当前生产绩效的评价结果。 北京交通大学硕士学位论文 m e s 系统的这1 1 项功能为工厂的运作提供了信息基础的核心，质量、维护， 文档以及计划等各方面的管理者都可以在m e s 平台上找到相应的工具。所有这些 功能在逻辑上都是相辅相成的，例如，数据采集能够自动地为产品跟踪、设备维 护等提供输入数据，质量管理可以为绩效分析以及维护管理等提供趋势数据，作 业计划则驱动生产调度和资源分配f s 卿 1 1 4m e s 发展状况及存在的问题 美日欧等工业发达国家都非常重视对m e s 技术的研究与系统开发，并形成了 m e s 软件产业，从8 0 年代后期到1 9 9 4 年，国际上m e s 的市场销售以2 3 的比 例递增，达到1 3 亿美元f 1 0 1 国外有很多优秀的m e s 产品，如西门子公司s i m a t i ci tp r o d u c t i o ns u i t e 产 品，它是基于i s a - 9 5 标准开发的，它涵盖了m e s 的所有基本功能，企业用户可 以根据自己的需要选择几个功能组件【l 。h o n 自f w e l l 公司其m e s 产品是从2 0 世纪 9 0 年代末开始，先由单一的m e s 功能模块发展到整体解决方案，该产品将经营目 标转化为生产操作目标，同时将经过处理验证的生产绩效数据进行反馈，从而形 成计划管理层、生产执行层和过程控制层三个层次的周期循环。美国a s p e nt e c h 公司是化学工业领域著名的流程模拟、先进控制和供应链管理优化软件公司，近 几年经过并购和整合，也定位在m e s 解决方案供应商，它提出了企业运营管理的 理念并开发集成了相应的软件产品，把e r p 层、m e s 层和d c s 层进行整合，高 效地设计、管理和运营制造与供应链的相关业务，即智能工厂解决方案i 。日本 的制造科学技术中心受日本信息技术促进局委托在电子商业公共基础设施建设项 目中提出了o p mm e s 框架规范。其规范由电子元件制造过程抽象而来，为了实 现框架的平台无关性，采用了c o r b a 技术。该框架文档主要是给那些想独立开 发应用项目的组织提供一个易于理解的概念性的o p m e s 框架，但没有包含具 体实施的细节州。 我国i v i e s 的发展起步较晚，发展水平还远不如国外发达国家，但“十五”以 来，m e s 的发展得到了足够的重视，国家8 6 3 计划也专门针对m e s 列出了许多课 题和专题项目。经过软件提供商、企业和科研院校的共同努力，我国m e s 在理论 研究和技术应用上都取得了一定的成绩，初步形成了自己的软件产品，如以d c s 起家的和利时公司研发了流程行业生产管理系统h o l l i a sm e s ，它包含了实时信 息监控、生产计划与统计、生产调度、质量管理、设备管理、能源管理、生产物 流管理、批量生产管理和进销存管理等功能模块，并广泛应用于石油、化工、电 力、制药、建材、冶金、造纸和食品等流程企业【1 3 l ；专注于烟草企业信息化的中 4 l 绪论 科久辉公司开发出了j l r i - m e s ，它负责填充烟草企业e r p 系统和p c s 系统之间的 空挡，负责与生产密切相关的生产指挥调度等实时性较强的各项工作，并具有与 e r p 系统、生产自动化系统、物流自动化系统的接口，以实现整个企业的信息集 成和协调运行，其主要功能为：优化捧产、生产调度、数据收集、生产过程监控， 质量监控、物料跟踪、异常处理、设备状态监控、生产人员管理、生产查询、生 产成本统计和工厂效能分析【川；宝信公司开发的用于钢铁行业的m e s 产品1 1 习；石 化盈科公司开发的用户石化行业的m e $ 产品【城。 总的来说，我国m e s 技术研究已经取得了一些成果，但仍然存在以下闯题： ( 1 ) m e s 的目标是生产过程优化、降低能耗物耗，但多数m e s 系统并没有 重点实现这功能。举个例子，2 0 0 4 年我国进口原油加上国产的原油有将近2 7 - 2 8 亿吨，在生产过程中，我们比国外多浪费掉o 5 ，2 7 - 2 8 亿吨生产过程中，接近 3 0 0 万吨的油没有了。并且在生产过程中我们生产的汽油的品质不如人家，我们生 产出来的塑料不如人家，生产过程决定了产品质量的提高、能耗的降低，这些问 题的出现，都是m e s 功能不足造成的。 ( 2 ) m e s 的智能化问题。过去，生产过程管理，凭借管理人员和操作人员的 经验，我国v i e s 系统仅仅提供了一个替代经验管理方式的操作系统平台，但是， 如何将生产管理者的经验固化在m e s 系统中，在我国m e s 研究开发中还没有涉 及。m e $ 智能化问题是未来我国m e s 发展实现跨越发展的主要方向。 ( 3 ) m e s 的合作开发问题。当今，m e $ 系统的开发实施工作主要是软件开 发商的事，软件开发商按照一般软件开发的流程根据用户的需求进行m e s 系统的 设计、开发和调试等工作。软件开发商并没有很好地得到企业在生产业务流程上 的支持，也没有得到m e s 科研工作者在理论上的支持，这样开发出的m e g 系统 很难发挥出它应有的效果。所以，柴天佑院士就指出m e s 系统的进步要靠m e s 的研究者、软件开发商与企业的共同努力，这样的m e $ 系统才是我们希望得到的 ( 4 ) 离散制造业m e $ 的滞后。我国离散制造业的首要矛盾是产品设计，并 且，企业生产制造端，即企业底层自动化、信息化距离实施m e s 的差距比较大， 相当多的企业设计、制造和管理没有实现集成、一体化，相应地，i d e s 在离散制 造业还没有被提到相当重要的位置。这就要求离散制造企业加大企业信息化建设 的力度，为尽快实施i v i e s 垫平道路【1 7 1 【1 3 】。 1 2m e s 生产调度问题概述 1 2 1 生产调度问题及常用解决方法简介 5 北京交通大学硕士学位论文 在过去的几十年中，人们对调度问题进行了大量的研究工作，从上个世纪5 0 年代起，调度问题的研究受到应用数学、运筹学、工程技术等领域科学家的重视， 科学家利用运筹学中的线性规划、整数规划、目标规划，动态规划及决策分析方 法，研究并解决了一系列有代表意义的调度和优化问题。但是，人们普遍把 c o n w a y ，m a x w e l l 和m i l l e r 三人有关调度的研究工作作为调度理论的正式开始， 他们3 人被人们称为调度理论的奠基人，此后3 0 多年的调度理论和应用研究都受 他们的影响。2 0 世纪7 0 年代，人们开始注意并重视调度复杂性的研究，提出了用 于研究算法有效性和问题难度的计算复杂度理论，许多调度问题被证明为n p 完全 问题。2 0 世纪7 0 年代后期，经典调度理论取得了重要进展，并且作为一门应用数 学学科已经基本成熟，但是实际调度问题与经典调度问题还有相当的距离。因此， 从2 0 世纪8 0 年代开始，人们一直在尝试并致力于解决实际调度问题，调度理论 由理论研究转向应用研究阶段。在这样的应用背景下，应用人工智能、计算智能 和实时智能研究成果，解决实际调度问题的智能调度方法就走向了历史的舞台， 同时，基于反馈控制的实时调度算法也初步显示了解决实际调度问题的强大威力 因此，可以说，智能调度方法和基于反馈控制的实时调度理论的方法为解决实际 调度问题展示了光明的前景。 在生产调度中，可以这样描述调度问题：“在一定时间期限内分配一组机器来 执行生产订单任务”。针对当今先进制造模式，可以把生产调度定义的更详细一些： “生产调度是针对一项可分解的生产任务，探讨在尽可能满足约束条件( 如交货 期、工艺路线和资源情况等) 的前提下，通过下发生产指令，安排其组成部分( 操 作) 使用哪些资源、其加工时间及加工顺序，以获得生产任务执行时间或成本的 最优化”。 生产调度问题的分类方法很多，根据加工系统的复杂度，可以分为单机调度、 l o b - s h o p 调度、f l o w s h o p 调度等；根据优化准则，可以分为基于代价和性能的调 度两大类；根据生产环境的特点，可分为确定性调度和随机调度；根据加工任务 后被加工工件的特征，可分为静态调度和动态调度 生产调度问题的研究最初集中在整数规划、仿真和简单的规则等方法上，这 些方法不是调度结果不理想，就是难以解决复杂的问题。近年来，在生产调度领 域出现了许多新的优化方法，比如神经网路法、遗传算法等，使得生产调度问题 的研究方法走向了多元化，对现有的生产调度的研究方法总结如下【1 0 2 0 1 1 2 1 l ： ( 1 ) 基于运筹学( o r ) 的方法 o r 方法是将生产调度问题简化为数学规划模型，采用基于枚举思想的分枝定 界法或动态规划法进行求解。这类方法通常是一种解决小规模问题的有效算法。 唐国春针对装卸工人的调配问题建立了问题求解的数学模型，并用运筹学的方法 6 1 绪论 给出了闯题的求解，收到了良好的效果【篮l ；陈婷和何中元针对车辆调度问题建立 了一个动态的、开放的现代智能车辆管理系统模型，最后用线性规划法求解该阔 题并得到好的计算结果 2 3 1 但是由于生产调度是一种组合优化闯题，属于n p 完全问题，随着问题规模的 扩大，会发生组合爆炸，以致很难用来求解大规模的调度问题。此外，就是o r 方法自身的局限性，人们在运用o r 方法时，不得不附加一些脱离实际环境的假设， 这在一定程度上导致了其理论研究与实际应用之间的差距 ( 2 ) 基于启发式规则法 启发式调度算法就是将人们在生产实际中所总结、提炼的很多行之有效的经 验和规则( 通常称为调度规则) 应用于调度问题中，其本质为按照规则从尚未调 度的工序的一个子集选择一个工序进行调度，直到所有的工序都被调度为止 郝文育等人针对离散制造车间的特点，提出了一种启发式调度算法，在保证 交货期的前提下，使得总的生产周期达到最短，并且设备的平均利用率达到最大， 在该算法的数学模型中，对于“时闻”进行了细致的描述，讨论了工序问物料转 移的“平行顺序逆向移动”方式提出了工时变动容忍系数、批量拆分次数等参 数，从而更加符合实际要求【2 4 】；孙海英等人根据炼油行业的实际情况，即调度问 题可以分为炼油生产过程、原油存贮过程、成品油存贮过程以及成品油流通过程 的优化调度，提出了一种线性规划与启发式规则相结合的解决方案，并利用仿真 结果证明了该方法的可行性和时效性网。 由于启发式算法计算复杂度低，易于实现等原因，因此被广泛应用于动态实 时调度系统中，启发式方法的主要缺点是求出的解不一定满足所有的约束条件， 并且无法确定解的优劣，常常需要专家的介入 ( 3 ) 系统仿真的方法 大多数制造系统非常复杂，很难用一个精确的解析模型来进行描述和分析， 而通过仿真模型来收集数据，邸可对实际系统进行性能、状态方面的分析，从而 对系统采用合适的控制调度方法，基于仿真的方法不单纯追求系统的数学描述， 尤其是离散系统仿真，侧重于对系统运行过程中逻辑关系的描述，仿真技术不仅 能对生产调度方案进行评价与选择，分析系统的动态性能，而且能够选择系统的 结构参数 顾华平和莫锦秋根据半导体生产的实际情况，同时考察机器在不同种类产品 切换时问，建立仿真模型，通过仿真结果得出系统的主要生产性能参数；王刚和 张多林提出了分级调度的仿真调度算法，并详细介绍了算法的基本思想，给出了 算法的步骤和流程图，这给系统仿真在生产调度中的应用提供了很大的便利 2 6 1 。 当前仿真方法也有其不可避免的不足之处：由于仿真本身具有的实验性，导 北京交通大学硕士学位论文 致其缺乏一定的理论意义；仿真模型运行时间长，费用高，导致其应用于生产调 度的成本也高；仿真的精确性受到编程人员判断能力和技术水平的限制；每一次 仿真只是对实际加工过程的一次抽样，因此即使高精度的仿真模型也不能保证得 到最优甚至较优的调度方案。 ( 4 ) 基于d e d s 的解析模型法 由于制造系统是一类典型的离散事件系统，因此，可以应用研究离散事件系 统的方法和解析模型来探讨生产调度问题，诸如q n 、极大代数法、动态规划法、 p e h i 网等，其中前三者都只适合于制造系统的性能分析 p e h i 网作为一种图形建模工具，能形象地表示和分析f m s 生产线中加工过程 的并发和分别的特征以及多项作业共享资源的冲突现象。建模能力强，能快速反 映制造系统实时调度的离散性和随机性，所以它和其他方法的结合在调度问题中 得到了广泛的应用。目前p 曲i 网用于生产调度中所存在的问题为：节点语义的单 义性，使得所携带的系统信息不够丰富；重用性差，很难对高级的调度规则加以 建模 陈进等人根据机床对工件加工条件准则和加工过程路径规则引入工艺路线矩 阵、加工顺序矩阵以控制设备、零件的状态向量的递推过程，从而建立起状态向 量的递推方程；重新定义极大代数法的乘法和加法规则，以满足上述的两个准则， 规定零元的运算规律，形成线性矩阵形式的状态矩阵的递推公式，该模型是d e d s 领域j o b s h o p 的描述和优化调度的新平台 2 7 1 ( 5 ) 基于人工智能的方法 人工智能的方法就是利用模型和知识，通过模拟、推理等手段为人的决策行 为提供支持，从而使人们可以根据车间的不同情况作出相应的更符合实际的决策。 近年来，基于知识的智能调度系统的方法和研究取得了很大的发展，其中最 常见的就是专家系统。专家系统作为一种较好的调度方法也存在着不容忽视的缺 点：对新的调度环境的适应性差；开发周期长，费用高；专家系统是基于知识的 系统，但是人们对经验和知识的获取受到历史条件的限制 较新的智能调度方法就是基于多代理技术的合作求解，它以分布式人工智能 中的多代理机制作为新的生产组织与运行模式，通过a g e n t 之间的合作以及m a s ( m u l t i - - a g e n ts y s t e m ) 系统来协调完成生产任务的调度。 张字和孙宪鹏把基于多代理技术的j o bs h o p 动态调度方法与基于规则的调度 策略相结合，在提出的基于多代理的j o bs h o p 动态调度系统结构的基础上，研究 了规则调度策略在各级a g e n t 行为设计中的应用，提出了a g e n t 之间竞争与协作方 式及投标计算方法，并在实验系统中对仿真结果进行了分析，为解决车问零件加 工动态调度问题提供了种新的方法【硼；李铁克等人通过对炼钢连铸生产调度问 3 1 绪论 题的分析后，提出炼钢一连铸生产调度的多代理体系框架，各个代理的功能及主要 代理的详细设计，探讨了基于多代理的炼钢连铸生产调度机制，并给出了一个简 单的炼钢连铸生产调度的实例分析结果删：凌亚群和陈伟达针对典型作业车间调 度( j o bs h o ps c h e d u l i n g ) 闯题的局限性，结合实际生产情况，提出了基于多代理 机制的供应链环境下的企业问的协同生产调度( c o o p e r a t e dp r o d u c t i 蚰s c h e d u l i n g ) 系统的体系结构，结合多代理的灵活性和遗传算法的全局优化性，阐述了一种基 于多代理和遗传算法的协同调度系统，并寻求了一种适合于这种供应链环境的优 化调度方案嗍 ( 6 ) 遗传算法( g a ) g a 的基本思想是基于d a r w i n 的进化论和m e n d e l 的遗传学说。g a 将问题的 求解表示成一群“染色体”，并将他们置于问题的环境中，根据“适者生存”的原 则，从中选择适应环境的“染色体”进行复制，通过交叉、变异等操作产生新一 代更适应环境的“染色体”群，通过这样一代代不断的进化，最后收敛到一个最 适应环境的个体上，即为问题的最优解。遗传算法的最大优点是通过群体阃的相 互作用，保持已经搜索到的信息，这是基于单次搜索过程优化方法所无法比拟的 遗传算法的进化过程一般包括以下几个主要步骤： l ，随机产生初始种群，个体数目一定，每个个体表示为染色体的基因编码； 2 、计算个体的适应度，并判断是否符合优化准则，若符合，输出最佳个体及 其代表的最优解，结束计算，否则转向步骤3 ； 3 、依据适应度选择再生个体，适应度高的个体被选中的概率高，适应度低的 个体可能被淘汰； 4 、按照一定的交叉概率和交叉方法，生成新的个体； 5 、按照一行的变异概率和变异方法，生成新的个体； 6 、由交叉和变异产生新一代的种群，返回到步骤2 。 图2 遗传算法的一般流程 f i 9 2c o m m o nf l o wo f g e n e t i ca l g o r i t h m 遗传算法的一般流程如图2 1 3 1 1 。以上所描述的是基本遗传算法的步骤，根据实 际生产调度问题，系统设计者要对遗传算法进行一定的改进，包括种群数量、交 9 北京交通大学硕士学位论文 叉算子、交叉概率、变异算子、变异概率、个体选择算子甚至是算法流程的优化 本文用到的就是单个体遗传算法，在这个算法流程中。为了避免大量无效编码的 出现删去了交叉步骤并对变异操作进行了改进，详细内容见第4 章。 g a 是一种通用的优化算法，其编码技术和遗传操作比较简单，优化不受限制 性条件的约束，而其二个最大的特点则是隐含并行性和全局性解空间搜索。遗传 算法被用来解决所有组合优化问题，这其中就包括调度问题。遗传算法的最早应 用可以追朔到上世纪六十年代，但直到八十年代末期，随着g o l d b e r g 研究成果的 发表，遗传算法的运用才在工业界获得认可 f a l k e n a u e r 和b o u f f o u i x 采用遗传算法分别研究了小规模、中规模和大规模的 车间调度问题【司；r e e v e s 应用遗传算法来优化流水车间的生产周期( m a k e s p a n ) 【，】；m u r a t a 等人采用遗传算法来求解流水车间的多目标优化问题，他们研究的目 标有最短生产周期、总延误时间和流动时问总和l 蚓：j a i n 和e i m a r a g h y 采用遗传 算法研究了柔性制造系统中的调度问题，他们研究表明由于遗传算法是多点搜索， 与其他单点搜索的方法相比较，在计算时间方面有较大的优势p 卯。 在国内近年来遗传算法用于生产调度的求解已成为一大研究热点，王万良等 人提出了一种双倍体遗传算法，该算法提供了一种记忆以前有用基因块的功能， 保留了某些低适应度染色体中的一些局部基因块，构成最优解中的基因片段，提 高遗传算法的适应能力，与已有算法相比，基于双倍体遗传算法的车问作业调度 方法，显著提高了搜索效率，改进了收敛性能i 蚓；贺东风和田乃媛首先建立了两 流薄板连铸连轧流程生产规则库，然后根据该生产流程的特点，提出了遗传算法 新的编码、交叉、变异操作及改良的概念，并在遗传算法的初始种群建立和改良 过程中引入调度规则，在此基础上，利用调度规则和遗传算法相结合的混合遗传 算法建立了两流薄板连铸连轧流程生产调度系统，该调度系统可以较好地解决两 流薄板连铸连轧流程的动态调度问题，进一步优化生产组织口h ；蔡兰等人根据多 任务，小批量流水线生产的特点，改进常规遗传算法，设计出一种基于交货期的 遗传算法，可以很快地搜索到最优个体，并实例证明了其可行性；由于高度的复 杂性，混合流水车问调度问题很难求得最优解，启发式算法和遗传算法结合起来 求解这类问题的有效性和实用性已被证实唧】。常俊林等人提出了一种基于遗传算 法的求解方法，在由染色体换成可行调度的过程中引入工件插入方法，同时设计 了一种新的交叉算子，通过大量的数值计算表嚷，该算法的优化质量大大优于传 统的遗传算法和启发式算法1 3 9 ：陈伟达和达庆利提出了一种将遗传算法与启发式 规则、模拟退火法等搜索方法结合在一起的杂合遗传算法，将该方法应用于求解 某双极集成电路制造企业的车间生产调度问题，仿真结果表明，它是有效和可行 的【椰j ；本实验室王兵师兄用改进的遗传算法，对北京交通大学机电学院现代制造 i o 1 绪论 技术综合实验中心f m $ 系统的多资源调度问题进行了优化，该系统有l 台数控铣 床、1 台数控车床、1 个环形轨道的物料运输设备，2 辆物料运输小车( r a i lg u i d e d v e h i c l er g v ) 、1 个自动立体仓库、1 台自动包装机和两个分管物料传送的机器人 组成，该系统的优化调度问题是典型的多资源调度问题，遗传算法的应用收到了 良好的效果3 1 1 2 2m e s 生产调度问题难点 生产调度是m e s 的核心功能，所以基于m e $ 的车间生产调度问题的研究一 直是m e s 科研工作者研究的热点南京航空航天大学的许文砚通过对现代企业生 产管理特点的分析，提出了面向m e s 的车间生产调度系统的设计思想，他认为系 统应包括系统管理、基础数据管理、调度数据管理、算法设计、加工调度、人工 调整、车间信息显示、检测加工冲突和调度结果输出等模块，该原型系统针对不 同优化目标对零件进行计算机排序结合手工调整，从而合理安排生产过程和机床 负荷，减轻调度人员的负担，优化车间生产运作，提高生产效率【4 l l ；北京科技大 学的李铁克在m e $ 的框架下，分析了炼钢车间生产调度系统的外部环境。运用面 向对象技术建立系统结构模型和动态行为模型，着重描述了人机交互、信息集成 以及实用算法方面的实现技术。该系统的主要设计思想是借助以甘特图为核心的 入机交互界面，对计划结果进行确认和调整，针对紧急订单、设备故障、质量偏 差、计划执行过程中的超前后滞后等因素，利用人机交互机锖动态调整作业计划 嗍：沈阳工业大学的张德胜结合沈阳重型机器制造公司制造一车间的技术改造， 对m e s 进行了实现，开发了沈重制造车问的生产调度系统，系统主要功能包括： 基础信息管理模块、生产计划管理模块、生产调度管理模块、生产过程控制模块 等，该系统的目标是把生产管理人员从繁重的手工作业解脱出来，利用可视化基 面的直观性，可以提高生产计划实施与控制的水平降低信息传递的时问和误差， 从而提高企业的竞争力m l ；沈阳工业大学的王伟玲结合沈阳重型机械集团有限责 任公司机械加工车间的生产实际，在分析车间生产调度现状的基础上，以机械加 工车间主要工件如双进双出磨煤机、滚盘式磨煤机、立式水泥磨、烧结机等为研 究对象，讨论了缩短零件加工周期、减少在制品、实现均衡生产的调度方法，重 点论述了适用予单件生产车闯的作业计划法，彼得罗夫哈姆算法，实现均衡生产 启发式规则和成组技术相结合的调度方法，以及基于交货期的逆序算法，在上述 基础上建立了车间生产调度与控制系统模型 4 4 1 ；浙江大学的蔡韵首先研究了流程 企业m e s 生产调度系统的特点，分析了实现生产调度的一些现有方法，然后从青 山纸业为背景，针对面向订单的排产和纸卷切割优化问题建模，应用搁置适当的 北京交通大学硕士学位论文 方法需求最优解，得到了满意的效果，论文根据实际企业背景分三种情况进行建 模，因为青纸实际生产的排产问题并不能简单清晰的用线性规划公开描述，同时 遗传算法对这类问题又具有搜索空间大，自适应和鲁棒性强的特点，所以选用了 遗传算法求解，在此基础上，根据模型讨论了算法中的遗传操作以改善求解效果， 从而解决了订单排产问题，并给出了仿真实例【4 5 1 m e s 生产调度问题基本上和其他调度问题的研究方法是一致的，但它的研究 难点如下： ( 1 ) m e s 调度的目标是全局的过程优化。每一个生产单元或生产车间的优化 的组合不一定能产生全局的优化，在工厂的整个生产计划范围内设计一个单一的 调度方案也是不可能实现的，这样调度问题的求解空问需要分解成生产单元以及 计划区间，以利于求解。此外，m e s 系统要同时与e r p 系统和底层p c s 系统发生 交互，这就要求研究者充分认识到把调度问题与企业的组织结构和决策层进行关 联的重要性。 ( 2 ) m e s 调度目标的多样化。i v i e s 调度的目标的时间、能耗、物耗、机器 利用率等凡个指标的综合，如何在这个几个指标之问进行权衡以达到最好的效果 是要重点考虑的。 ( 3 ) i v i e s 调度问题的理论研究和应用的脱节调度问题的研究起源于上个实 际5 0 年代，经过半个多世纪的研究，调度理论已日趋成熟，但真正用到实际生产 中，而且应用到i v i e s 系统中并收到良好效果的很少 ( 4 ) m e $ 是不确定调度和动态调度的综合。m e s 调度闯题的数据来源于实 际生产车间，而生产现场的数据具有不确定性、不完整性和多样化等特点；同时 m e s 要求调度系统能实现动态调度，要能随时响应车间的不断变化。这样，m e s 调度问题就会难上加难。 1 3 论文的研究意义和章节安排 1 3 1 论文研究的背景 为了使自己的研究工作不脱离实践，所以本人论文研究期间在中科久辉公司 实习了近一年的时问。实习期问主要参与了某烟厂制造执行系统( 以下简称 c ym e s ) ，c ym e s 项目是中科久辉信息自动化公司和西门子工厂自动化工程有 l 绪论 限公司共同承担的，它是西门子平台在烟草m e s 上的首次尝试 该烟厂拥有镧丝和卷包两个车间：翻丝生产是典型的连续型生产，它经过一系 列的物理和化学反应，把烟叶变成不同牌号的烟丝，制丝的工序一般为：烟叶出 库、切片、时片加料、切丝、烘丝、多丝掺配和烟丝入库；卷包生产是离散型生 产，它将烟丝经过几道工序最终变为成品并进入到成品立库，卷包的工序一般为： 卷接、包装和装封箱 除了生产调度系统外，c ym e s 的其他功能都是由西门子现成模块通过配置 实现的生产调度系统是由中科久辉、西门子和该烟厂信息中心三方开发人员根 据烟厂生产的实际情况共同完成的