（机械制造及其自动化专业论文）面向单件生产模式的调度系统研究.pdf

摘要 摘要 由于个性化需求的发展，多品种、小批量已逐渐成为主流生产方式。随着 这种生产方式的转变，企业在工作效率和应变能力等方面承受着更大的压力。 因此，研究一套科学有效的调度方法和相应的计算机调度系统对提高企业的工 作效率和应变能力具有非常重要的作用。 锅炉压力容器生产企业的生产模式是面向工程的生产，属于单件生产。本 文根据锅炉压力容器生产企业的特点，建立了单件小批量生产调度的数学模型， 探索出了单件生产车间的调度算法，对单件生产的调度系统进行了系统建模， 研究开发出了一套车间生产调度的原型系统，并对该系统与m e s 及其它系统的 集成技术进行了研究。 在理论方面，总结了现今调度问题的各种建模、求解方法与策略。从调度 可行性出发，在保证交货期的前提下提出了基于优先规则的排产算法，针对作 业控制层的要求，给出了相应的调度策略，以甘特图、报表等形式跟踪加工执 行的状况，形成生产过程的闭环控制。这些都为解决车间一级的作业调度问题 提供了有效的解决方案。 详细研究了面向单件生产模式的车间生产调度问题，并对调度理论作了一 个深入细致的研究，通过在调度过程中的资源约束条件，对比较复杂的车间调 度问题的进行优化，利用遗传算法、结合规则式的方法对车问土，溯度i 工进 行了分配。阐述了基于单件小批量模式的车间生产调度系统的设计思想，利用 具体建模工具对该系统进行分析和建模，详细介绍了系统的功能模块与关键技 术，开发了较为实用的生产调度原型系统。该系统已在企业运行，取得了良好 的收益，提高了企业的生产效益，降低了生产成本。 关键词：单件生产；遗传算法：车间生产调度；系统集成 a b s t r a c t a b s t r a c t a st h ed e m a n df o r t h ed e v e l o p m e n to fp e r s o n a l i z e d ，m u l t i - s p e c i e s ，s m a l l q u a n t i t i e sh a v eg r a d u a l l yb e c o m et h em a i nm o d eo fp r o d u c t i o n w i t ht h i sc h a n g ei n p r o d u c t i o nm e t h o d s ，t h ee n t e r p r i s eu n d e r t a k e sp r e s s u r ei ne f f i c i e n c ya n da d a p t a b i l i t y t h e r e f o r e ，i ti sv e r yi m p o r t a n tt od e v e l o pas e to fe f f e c t i v es c h e d u l i n gs y s t e mi no r d e r t oi m p r o v et h ee f f i c i e n c ya n da b i l i t yt os o l v ep r o b l e m t h ep r o d u c t i o nm o d e lo fv e s s e la n dp r e s s u r e e n t e r p r i s e i so r i e n t e dt o e n g n e e r i n g ( o t e ) ，b e l o n g i n gt oas i n g l ep r o d u c t i o n i nt h i sp a p e r , a c c o r d i n gt ot h e c h a r a c t e r i s t i co fv e s s e la n dp r e s s u r ee n t e r p r i s e ，s e tu pt h em a t h e m a t i c a lm o d e lo f j o b s h o ps c h e d u l i n g t oe x p l o r et h es c h e d u l i n ga l g o r i t h mo fj o bs h o p ，a n ds e tu pt h e s y s t e mm o d e lo f j o bs h o ps y s t e m ，d e v e l o p e das c h e d u l i n gs y s t e m ，a n dr e s e a r c h e dt h e i n t e g r a t i o no f j o bs h o ps y s t e mw i t hm e s a n do t h e rs y s t e m s i nt h e o r y , t h r e ea s p e c t so nj o b - s h o ps c h e d u l i n g m o d e l i n g ，s c h e d u l i n gm e t h o d s a n ds t r a t e g i e sa r es u m m e d t h e nb yc o n s i d e r i n gt h ef e a s i b i l i t yo fs c h e d u l i n g ，t h e b a c k w a r ds c h e d u l i n ga l g o r i t h m , b a s e do np r i o r i t yd i s p a t c h e rr u l e si sp u tf o r w a r dt o e n s u r et h ed e l i v e r yt i m e a n da c c o r d i n gt ot h er e q u e s to fp r o d u c t i o nc o n t r o ll a y e r , t h i sp a p e rp r o p o s e st h es c h e d u l i n gs t r a t e g i e sa n dt r a c k sp r o c e s s i n ge x e c u t i o nw i t ht h e f o r mo fg a n t tc h a r t ，r e p o r ta n ds oo n ，w h i c hf o r m st h ec l o s e d - l o o pc o n t r o li n p r o d u c t i o n t h e s e c a l ls o l v ee f f e c t i v e l yt h ep r o b l e mo fj o b - s h o pp r o d u c t i o n s c h e d u l i n g a n dr e s e a r c h i n gt h es c h e d u l i n go fj o bs h o pp r o b l e mb a s e do nt h es m a l lb a t c h , t h e n , m a d ead e e pr e s e a r c ho fs c h e d u l i n gt h e o r y t h r o u g ht h er e s t r i c tc o n d i t i o no f r e s o u r c ei ns c h e d u l i n g ，t oo p t i m i z ec o m p l e xp r o b l e mi nt h es c h e d u l i n g ，a n dd i s t r i b u t e t h et a s ks c h e d u l i n gi nj o bs h o pt h r o u g hm e t h o do ft h eg e n e t i ca l g o r i t h m sa n d h e u r i s t i cr u l e t h e n , t h i sp a p e rd i s c u s s e dt h ed e s i g ns c h e m eo f p r o d u c t i o ns c h e d u l i n g s y s t e mi nt h es m a l lb a t c hw o r k s h o p t h es y s t e mi sa n a l y z e da n dd e s i g n e db y m o d e l i n gt o o l s t h ef u n c t i o nm o d u l e s a n dt h er e a l i z i n gt e c h n o l o g i e sa r ei n t r o d u c e di n d e t a i l ap r o t o t y p es y s t e mi sd e v e l o p e d t h es y s t e mh a sb e e nu s e di nt h ee n t e r p r i s e ， a n dh a v ea c h i e v e dg o o de f f e c t ，g r e a t l yi m p r o v e dt h ee f f e c t i v e n e s so ft h ee n t e r p r i s e ， r e d u c i n gp r o d u c t i o nc o s t s k e y w o r d ：m a k et oo r d e r ；g e n e t i ca l g o r i t h m s ；j o bs h o ps c h e d u l i n g ；s y s t e mi n t e g r a t i o n i i 学位论文独创性声明 学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得直昌太堂或其他教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确 的说明并表示谢意。 学位论文作者签名( 手写) ：妻吏摧签字日期：矽呷年易月1 2 - 日 学位论文版权使用授权书 + 本学位论文作者完全了解直昌太堂有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权直昌太堂可以将学位论文的全 部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编本学位论文。同时授权中国科学技术信息研究 所将本学位论文收录到中国学位论文全文数据库，并通过网络向 社会公众提供信息服务。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：丑交彩藩导师签名：f 豹 签字日期：沙口夕年易月肠日 签字日期： 9 年石月嵋 第1 章绪论 第1 章绪论 1 1 制造业现代管理模式的发展概况 制造业的管理由传统的人工管理模式，逐渐向现代化的管理模式发展。在 国际发展的大环境下，人们不断提出符合时代特征的企业的生产模式，使得在 实际的生产中，通过企业的信息化管理的应用，大大的提高了企业的生产管理 能力，一定程度上节省了人力和物力，并使得现代企业的生产和管理向前迈出 了一大步，极大的提高了企业的工作效率和企业的快速应变能力。 2 0 世纪7 0 年代末、8 0 年代初，物料需求计划m r p 经过发展和扩充逐步形 成了制造资源计划的生产管理方式。制造资源计划( m a t e r i a lr e s o u r c ep l a n n i n g ， 称为m r p i i ) 是由美国著名的管理专家、m r p 的鼻祖奥列弗怀特( o l i v e rw w i g h t ) 在物料需求计划( m a t e r i a lr e q u i r e m e n tp l a n n i n g ，m r p ) 的基础上提出的一 种现代生产管理模式和组织生产方式【l 2 】。它是以物料需求计划( m r p ) 为核心 闭环生产计划与控制系统，它比物料需求计划具有更丰富的内容。m r p i i 是计 算机集成制造系统( c i m s ) 的重要单元技术，也是企业资源计划( m r p ) 重要 的核心组成部分。 制造资源计划的基本思想是：基于企业经营目标制定生产计划，围绕物料 转化组织制造资源，实现按需要按时进行生产。按照基于产品结构的物料需求 组织生产，根据产品完工日期和产品结构规定生产计划；根据产品结构的层次 从属关系，以产品零件为计划对象，以完工日期为计划基准倒排计划，按各种 零件与部件的生产周期反推出它们生产与投入时间和数量，按提前期长短区别 各种物料下达订单的优先级，保证在生产需要时所有物料都能配套齐备，不需 要时不要过早积压，达到减少库存和占用资金的目的。具体的说，是将企业产 品中的各种物料分为独立需求物料和相关需求物料，并按时间段确定不同时期 的物料需求，从而解决库存物料订货与组织生产问题。 随着对企业的要求不断提高，近年来出现的准时制生产( j i t ) 、最优生产技 术( o p t ) 、约束理论( t o c ) 、精益生产( l p ) 、敏捷制造( a m ) 等是目前被广泛引 入到生产管理系统中的一些热点技术，它们不断地与企业生产资源计划和生产 计划相结合，使得生产管理新思想的更加实用化。 第1 章绪论 1 f i t 3 】 准时制生产( j u s ti n t i m e ，j i t ) 是2 0 世纪8 0 年代初由日本丰田公司创造的一 种以消除制造过程中的一切浪费为宗旨的生产管理思想。其基本思想是在正确 的时间、正确的地点做正确的事情，以期达到零库存、无缺陷、低成本的理想 生产模式。j i t 是一种提高整个生产管理水平和消除浪费的严谨方法。其宗旨是 使用最少量的设备、装置、物料和人力资源，在规定的时间、地点，提供必要 数量的零部件，达到以最低成本、最高效益最好质量、零库存进行生产和完成 交货。j i t 生产管理模式的最终目标是彻底降低成本，获取企业的最大利润。 实行j i t 生产方式必须满足：生产计划平稳、减少调整准备时间、提高工人 素质、生产车间即时布局、准时采购、消除原材料和外构件的库存、加强质量 管理、消除废品。目前中国企业要实现j i t 模式生产还是缺乏很多的基础条件， 难以全面实现。 2 o p t 厂r o c 最优生产技术( o p t i m i z e dp r o d u c t i o nt e c h n o l o g y , 简称o p t ) 开创于2 0 世纪 7 0 年代，o p t 认为，一个企业的计划与控制的目标就是寻求顾客需求与企业能 力的最佳配合，一旦一个被控制的工序建立了一个动态的平衡，其余的工序应 相继地与这一被控制的工序同步。其指导思想是对要生产的产品，找出产品生 产中影响生产进度的最薄弱环节，集中主要精力保证最薄弱环节满负荷工作， 不至于影响生产进度，它可以使生产周期缩至最短，使在制品库存降至最低。 约束理论( t h e o r yo fc o n s t r a i n t s ，简称t o c ) 是o p t 技术的发展和延续，是 关于进行改进和如何最好地实施这些改进的管理理念和管理原则，可以帮助企 业识别出在实现目标的过程中存在着哪些“约束因素，并进一步指出如何实 施必要的改进来一一消除这些约束，从而更有效地实现企业目标。其目的是找 出各种条件下生产的内在规律，寻求一种分析生产经营问题的科学逻辑思维方 式和解决问题的有效方法。 3 l p 精益生产( l e a np r o d u c t i o n ，简称l p ) 表示用尽善尽美的生产方式达到高 效益。精益生产的特点是充分发挥员工的主动性和创造性，采用t ，实现了高 效、低库存的多品种混合生产，简化组织机构以及一切不增值的环节，强调一 体化的质量保证体系，与客户长期保持联系，以尽善尽美为目标，追求最大限 度的客户满意度。 2 第1 章绪论 4 a m 敏捷制造( a g i l em a n u f a c t u r i n g ，简称a m ) 是1 9 8 8 年美国通用汽车公司( g m ) 与里海( l e h i g h ) 大学共同提出的一种新的制造企业战略。该模式是一种直接面向 用户不断变化的修改化需求，完全按订单生产的可重新设计、重新组合、连续 更换的新的信息密集的制造系统。敏捷制造的提出者认为：敏捷制造是能在不 可预测、持续变化的竞争环境中使企业繁荣和成长，并具有面对顾客需求和市 场变化做出迅速响应的能力。 敏捷制造的主要特点有，以强大的信息交换能力为基础的虚拟公司成为经 营实体的主要组织形式；在组织和技术上具有很大的灵活性的应变能力；并行 工程和多功能项目组是产品开发的主要方式与组织形式；把知识、技术和信息 作为最重要的财富，发挥人的创造性。敏捷制造代表着2 1 世纪制造业的发展方 向，敏捷性由可重构( r e c o n f i g u r a b l e ) 、可重用( r e u s a b l e ) 和可扩充( s c a l a b l e ) 共同 构成，它是企业驾驭变化能力的反映。因此，实行有效的信息管理就更为重要， 确切地说，就是要为制造资源集成过程中的各种决策活动提供实用、准确、及 时和适量的信息。 这些先进的管理思想和方法在企业和生产中得到了广泛的应运，但是， 2 0 世纪8 0 年代后期，全球市场竞争激烈，上层的生产计划管理系统受市场影响越 来越大，计划的适应性也逐渐成为生产中调度中的一个突出的问题，由于生产 任务的即时性和随机性越来越大，明显感到在制定一个完善的生产计划，也逐 渐成为企业和生产者所要讨论的一个重要问题，企业的决策者逐渐认识到计划 的制定和执行要依赖于市场和实际作业执行状态，而不能完全以物料和库存回 报来控制生产。随着各种特殊调度问题的攻克和新方法、新设备的出现，车间 调度研究正在向着动态、敏捷、多重入、多资源、智能化的方向发展。 1 2 生产模式类别及发展趋势 1 2 1 车间生产模式的分类 现代的企业生产中，车间生产的柔性化制造成为越来越关键的技术，而车间 生产调度，作为柔性化制造执行系统的一个关键模块，体现了制造执行系统在 现代化生产中的高效性和先进。它的任务就是“如何安排加工作业的顺序并合 理地分配目前有限的制造资源从而使加工作业在合理的时间内加工完成 。高效 3 第l 章绪论 合理的调度方法和优化技术的研究与应用，是实现先进制造生产并提高生产效 益的基础和关键。由此可见，车间调度的方法对于优化车间生产性能，提高企 业生产质量有着重要意义。 车间调度问题根据设备种类和数量的不同，可分为单台设备的调度问题和 多台设备的调度问题。对于多台设备的调度问题，根据工件j u t 路线的特征和 设备环境的不同，又可分成单件车间( j o bs h o p ) 调度问题、流水车间( f l o ws h o p ) 调度问题和开放式车间( o p e ns h o p ) 调度问题三种类型。 在不同的生产车间中，对于工件的调度目标，也不相同，并且在实际的生 产中，要合理的安排车间的加工作业，就必须要有适合于车间的生产调度系统， 由于生产中要考虑到各种因素的影响，我们要寻找出一个最优化的调度方法， 也是一项很复杂的工作。车间调度存在约束性、复杂性、离散性、动态多变性 和多目标等特性。这些年以来，各个领域的研究人员都在深入的研究车间调度 的策略和算法，其中，一些优化的算法解决了车间调度一些问题，但同时，在 车间调度中，随着调度规模的增加，问题的解空间也呈非线性剧增，要在一个 合理的时间内获得较为满意的结果相当困难。实际生产中还存在着由以上两种 或三种调度类型共同组成的混合型调度问题，研究这类问题的调度，就更为复 杂。当前，主要从事的是单件小批量生产的研究，并且已经取得了很大的研究 成果。 单件生产企业要比大规模式批量制造企业具有更高柔性，以便适应用户和 重构需求变化。在生产的过程当中，要根据用户的特定要求，进行单件生产产 品的订单下达和任务生产，单件小批生产一般具有以下特点【4 ，5 ，6 1 ：高度客户 化，在设计和生产的过程中，来自客户的影响始终存在；根据客户的需求来进 行产品的开发，客户的需求在单件产品生产的过程中，自始自终都起到很重要 的指导作用；产品品种多、数量少、规格多变，并且通常是以批次单件生产 为主；产品设计和制造周期长，合理的使用最优化的生产技术和资源，尽可 能的去缩短生产) j u t 时间，以保证尽可能早的交货，提高产品的生产效率； 进行生产计划和控制要有很强的自适应性，设计方案通常是根据客户的具体需 求来定；产品各部件之间的时序约束关系和成套性要求严格，瓶颈设备的能力 平衡和利用率是生产计划与控制的关键环节。 4 第1 章绪论 1 2 2 生产模式对生产调度存在决定作用 现代制造企业的管理方式也随着生产模式的变革一同发生了变化。企业必 须把客户需求作为生产管理的中心，以最快的速度来响应客户需求变化，争取 在市场竞争中取胜。为此，许多企业引入了先进的生产管理方式，通过实施企 业资源计划( 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 p ) 和制造资源计划( m a n u f a c t u r i n g r e s o u r c ep l a n n i n g ，m r p i i ) 来加强管理，使企业生产能够更加科学地反映市场 需求。由于上层生产计划受市场影响越来越大，而e r p m r pi i 软件的主要作用 是针对资源计划，对于生产现场的管理无法直接进行控制，使得上层计划和底 层控制之间出现脱节现象，因此企业通过制造执行系统( m a n u f a c t u r i n ge x e c u t i o n s y s t e m ，m e s ) 来连接上层计划管理与底层工业控制，对车间层的生产信息进 行管理与控制，为操作人员和管理人员提供计划的执行、跟踪及所有资源的当 前状态 7 1 。 车间是制造企业的中心，在执行生产计划和反馈生产信息的过程中，会产 生大量的生产实时信息，其调度与控制系统的敏捷性在一定程度上决定着整个 企业生产的敏捷性。我国制造企业的管理模式相对落后，尤其是以单件小批为 主要生产模式下的企业，车间的组织与控制方式对其生产调度有着更高的要求。 这是因为单件小批生产车间的产品种类多、数量少，生产重复性小，工艺过程 经常变更，无法采用高效率的专用生产设备和工艺装置，工作场地的专业化程 度不高，生产准备工作量大，生产能力的瓶颈多变。因此，需要一个先进实用 的调度系统，通过计算机进行准确的数据处理，对下达的生产任务进行一定程 度上的智能优化调度，最大程度地减少生产过程中的准备时间，实现加工生产 的高效率、高柔性和高可靠性。由此可见车间调度的方法对于优化车间生产性 能，提高企业生产质量有着重要意义。 1 2 3 单件生产成为企业生产的发展趋势 全球经济的高速发展和人们生活水平的提高，世界的市场结构发生了巨大 变化。一方面，信息技术的发展以及各国贸易限制的减少加快了生产竞争全球 化的进程；另一方面，消费者的需求日趋个性化和多样化，使得市场的发展也 要求多样化，以满足广大消费者日益增长的物质文化需求。在这种情况下，制 造业面临着一个由消费者占主导地位、变化迅速且无法预测的市场。传统的大 批大量生产模式对此难以适应，于是，多品种、单件小批生产逐渐成为当今大 5 第1 章绪论 多数企业的主要生产模式。 1 2 4 研究单件生产调度问题的重要性 我国制造企业的管理模式相对落后，尤其是以单件小批为主要生产模式下 的企业，车间的组织与控制方式对其生产调度有着更高的要求【8 1 。这是因为单件 小批生产车间的产品种类多、数量少、生产重复性小、工艺过程经常变更，无 法采用高效率的专用生产设备和工艺装置，工作场地的专业化程度不高，生产 准备工作量大，生产能力的瓶颈多变。因此需要一个先进实用的调度系统，通 过计算机进行准确的数据处理，对下达的生产任务进行一定程度上的智能优化 调度，最大程度地减少生产过程中的准备时间，实现加工生产的基于单件小批 生产模式的车间调度方法研究和系统开发高效率、高柔性和高可靠性。 目前，我国机械制造企业，尤其是压力容器制造企业，主要从事单件、小 批量，按订单组织的生产形式，生产过程中存在着不确定因素，生产调度和控 制的工作主要靠车间管理人员的经验来安排，生产作业的管理任务复杂而繁重。 因此，研究车间生产调度问题，并实现以人机交互方式对车间作业生产进行实 时动态控制，有助于促进生产调度系统与其他系统集成能力，为车间的生产调 度系统的发挥作用提供了一个车间层的平台，对于调度与计划、调度与控制的 全集成和制造企业生产管理水平的提高具有重要意义。对于调度方法和优化技 术的研究与应用，是实现先进制造和提高生产效益的基础和关键。改善生产调 度方案，可大大提高企业生产效益和资源利用率，进而增强企业的竞争能力， 帮助企业获得进一步发展，使得企业具有更强的市场竞争力。 1 3 锅炉压力容器企业生产模式描述 锅炉压力容器企业的生产方式属于工程式生产，工程式生产的特点是，在 生产的过程中，生产订单的交货期是一个时间段，而不是一个时间点。由于工 程生产的安装过程比较复杂，在装配的过程中，很难一次性装配到位，有很多 复杂的中间过程，所以这就使得工件的交货期是在一个时间段里面完成的。 锅炉压力容器的生产以单件生产为主，每个生产订单的内容都不相同，所 以在接受企业的订单之前，都要去企业作相关的需求分析，然后对订单进行一 个成本和进程的评估，评估之后向企业提交方案，方案里包括报价和加工进度 的安排。由企业来对提交的方案进行讨论，如果能够满足工程工期要求，则可 6 第1 章绪论 以根据方案进行投产，如果不能满足工程工期，就要重新提交方案，再由企业 审核，审核通过以后，企业才开始下订单，接受企业的订单，对订单进行任务 的分解，然后分配到车间，通过车间调度系统的调度得出调度结果，进行生产。 主要的流程图如下图1 1 所示： 是 图1 1 工程式生产的企业流程图 本文主要是针对压力容器企业单件生产的特点，对于单件生产调度问题作 了深入的研究和探讨。 1 4 本文的选题意义及主要研究内容 1 4 1 选题意义 随着市场竞争的日益激烈和客户需求多元化的不断发展，大多数企业的生 产模式已由过去的大批大量生产转化为单件小批生产，因此j o bs h o p 调度问题 已经成为最具吸引力的研究领域之一。合理的调度方案可以有效地提高生产效 率、均衡资源利用率，为企业带来很大的经济效益，所以研究此类调度问题具 有重要的理论意义和实用价值。 j o bs h o p 调度问题是一类具有时间约束、次序约束和资源约束的组合优化问 题。目前国内外对j o bs h o p 调度问题的研究大多满足几点基本约束，其中重要 一点就是：工件的每道工序只能在指定的设备上完成。然而在实际生产中，为 7 季暴 第1 章绪论 了使加工任务尽快完成，通常配置较多的设备去完成较费时的工序，这时此约 束就改成：每道工序可以在一台或多台可完成相同操作的设备上加工。这类问 题放宽了资源约束条件，因而具有更大的寻优空间，是实际中存在得更为广泛 的一类调度问题，也是本文所研究的重点。 同时，随着信息技术在企业中的广泛应用，有关产品制造各个过程的实时 数据会越积越多，人们希望能够对数据背后隐藏着的许多重要信息进行更高层 次的分析，以供调度决策之用。目前国内外在这方面的研究成果还比较少，对 不同工序竞争同一台加工设备的情况，从历史数据中提取出隐含的排序规则来 解决加工冲突问题。将数据挖掘技术应用于生产中，发现数据中存在的关系和 规则，根据现有的数据预测未来的发展趋势，不仅是形势发展的需要，也是实 现企业管理向现代化、智能化发展的重要标志。 1 4 2 本文的主要研究内容 本课题来源于与某企业的合作项目。根据该企业的业务特点可知，该企业 的主要生产方式是单件工程式生产。单件工程式生产的特点是每件产品生产都 是设计开始，几乎没有两件一样的产品。这样我们就可以将每一件产品的生产 认为是一个工程项目。 本文是以锅炉的加工装配车间为现实的物理模型，从中抽象出一般单件小 批量生产车间的简化模型，对于单件小批量车间生产的调度算法深入了研究， 本文主要探讨了启发式规则的遗传算法在实际生产调度中的运用，并讨论了在 车间调度的过程中，怎样根据已知的约束条件，求解生产调度过程中的较优解， 满足在生产的过程中尽量缩短生产时间、提前交货期，以提高单件小批量生产 装配车间的生产效率。 建立车间生产调度原型系统，从车间生产和管理的全局出发，将优化规则 调度与层次控制相结合，对车间作业排产算法以及动态调度策略进行了深入研 究，开发出一套适合于工程生产的单件小批量生产的车间生产调度系统，由于 本人能力及时间的限制，主要工作包括： 1 分析锅炉压力容器企业的生产特点并建立单件生产车间的调度模型 在工程生产的过程中，通常都是在接到用户下达订单之后，根据车间实际 的生产能力来进行评估，制定一个生产车间的主生产计划，这个主生产计划要 满足用户的交货期的要求，并且不能超过该车间的加工生产能力。当用户的需 8 第1 章绪论 求发生变化时，车间的主生产计划要能够根据用户的要求做出及时的调整，这 就要求生产车间要有灵活高效的调度系统，而不是像传统的靠人来进行调度， 车间生产调度系统作为本文的研究对象。根据单件生产车间的特点来建立调度 模型。 2 研究生产车间的调度理论并探索单件生产理论车间调度算法 研究车间生产调度的理论和各种研究方法，建立起以缩短零件的完工时间 的优化目标，完成车间级的作业排序与作业控制的实施过程，探索出符合车间 生产调度的算法，提出基于复合规则的逆序作业调度算法。 3 建立单件车间生产调度的系统模式 通过对于整个系统所要实现的功能分析，从理论上建立起车间生产调度系 统的模型，并把系统的框架图建立起来。 4 研究开发单件车间调度的原形 通过对系统的设计，利用面向对象技术进行系统结构设计与软件开发，包 括建立用于生产调度决策的基础数据库，选择实用的作业排序方法，输出工件 进度甘特图以及对实际情况的信息反馈。 5 研究单件生产调度系统与其它系统的集成技术 本文开发的车间生产调度系统是m e s 系统的子模块，通过m e s 与其它系 统的集成，把车间生产调度系统与其它信息系统集成起来，可以在系统之间进 行数据库信息的共享，通过集成来提高企业内部的资源共享，以此来提高企业 的工作效率，使得企业尽可能的获得最大效益。 9 第2 章理论基础及算法 第2 章理论基础及算法 车间调度主要是针对可分解的工作，探讨在尽可能满足约束条件的前提下， 通过下达生产指令，安排其组成部分使用哪些资源、加工时间及加工的先后顺 序，以获得产品制造时间或成本的最优化。在理论研究中，车间调度问题常被 称为排序问题或资源分配问题或组合优化问题。从数学规划的角度看，车间调 度问题可表达为在等式或不等式约束下，对目标函数的优化。典型的车间调度 问题包括一个要完成的作业集，每个作业由一个操作集组成，各操作的加工需 要占用机床或其它生产资源，并且必须按一些可行的工艺次序进行加工。 2 1 车间生产调度问题的概述 车间是生产制造企业的加工中心，在执行生产计划和反馈生产进度的过程 中，会产生大量的生产实时的信息，企业可以通过车间反馈的信息对车间生产 实施实时的监控，而一个企业的生产调度与控制系统的敏捷制造在一定程度上 决定了制造企业的敏捷性。 在这里，引入一个关于调度的概念，所谓调度，是指为了实现某个目的而 对共同使用的资源实行时间分配【9 】。车间调度指根据车间实际加工过程中随时出 现的情况，对车间作业计划做出调整和修改，使车间生产得以顺利进行，保证 生产的产品能够按时交货。车间调度作为m e s 中的重要模块，对应于生产管理系 统的短期计划安排，主要目标是通过良好的作业加工排序最大限度减少生产过程 中的准备时间，优化某一项或几项生产目标，为生产计划的执行和控制提供指 导。车间调度贯穿于企业的整个生产过程中，是保证车间生产在动态实时环境 下能够高效可靠运行的关键。 2 1 1 车间生产调度的特点 1 ) 建模计算的复杂性 车间中机器、工件，以及一些中间步骤之间的关系复杂，多样化的生产方 式和一些现场生产因素都会造成影响。车间生产调度问题是在一定的约束下优 化某些性能指标，往往是通过等式或不等式的约束条件来计算的，属于典型 n p h a r d 问题。因此，在求解车间调度问题上，通常无法用一些常用的优化方法 1 0 第2 章理论基础及算法 来解决车间调度问题，这样就涉及到要建立复杂的模型来解决调度问题，加大 了计算的难度。 2 ) 约束性 车间调度问题中会受到很多条件的约束，例如：车间的加工能力、车间的 调配能力、工件的工艺、工件的装配次序以及工件的交货期等，还有一些其它 的因素，如设备的事故率，人员的技术水平，此外，还要求机器上的负荷要平 衡等。 3 ) 多目标性 生产调度中同时有多个调度目标，而其相互之间在调度过程中，往往又会 相互冲突。车间生产调度往往是同时调度多个目标，可分为基于作业交货期的 目标、基于作业完成时间的目标、基于生产成本的目标。 4 ) 动态随机性 动态调度中会存在很多动态性和不确定性，系统中常有突发偶然事件，如 机器故障、作业交货期的改变等因素。生产中会有一些紧急订单的插入、人员 误操作等不可预见性，并且实际工件加工时间也有一定的随机性。因此，生产 调度需要根据生产情况做出动态调整。 5 ) 离散性 在生产加工的过程中，工件的生产、存储以及运输都是发生在不同的时间 点，设备的故障、订单的变化、以及人员的调整都是不确定的，这些都属于离 散性事件。车间生产也能看成是一个离散性生产过程，这样我们就可以找出一 些优化的算法来解决车间调度的问题。 2 1 2 车间生产调度的现状 车间调度问题本身源于实际生产需求，从车间生产的实际过程来看，不确 定性是调度的最大难点，也是任何现代化的企业所无法回避的，由于车间生产 的过程中一些随机事故的存在，随时出现的任何情况都有可能打乱原先所做出 的零件排序和负荷均衡。目前所研究的调度问题大多是将实际生产情况进行简 化，把复杂问题转化为现有方法可以解决的简单问题，绝大多数调度理论和算 法都不能够对实际问题进行全面而有效的求解，它们只对某种特定或简单情况 有效，却无法同样有效地解决动态环境下的其它问题。因此人们在静态调度问 题的研究基础上，不断增加问题的约束条件并提出面对意外事件的处理方法， 第2 章理论基础及算法 使所构建的系统尽量接近实际生产，做到可靠实用。 2 1 3 车间生产的几种模型 车间调度问题根据设备种类和数量的不同，可分为单台设备的调度问题和 多台设备的调度问题。对于多台设备的调度问题，根据工件加工路线的特征和 设备环境的不同，又可分成单件车间( j o bs h o p ) 调度问题、流水车间( f l o ws h o p ) 调度问题和开放式车间( o p e ns h o p ) 调度问题三种模型。 在流水车间中，所有工件的工艺路线都是相同的，即有一致的加工操作 和加工顺序。车间具有连续的生产布局，设备和操作人员总是对每批任务进行 同样的操作，适用于大批量生产的情况。由于此类调度问题统一了工件的加工 路线，因此相比于j o bs h o p 调度问题，其求解难度较小。流水车间的加工路线 图如图2 1 所示。 开始 、， 二珂7 图2 1 流水车间工件加工路线 开放式车间中，同一个工件的各道工序的先后关系是任意的，工件没有 特定的加工路线约束，要获得这类问题的可行调度方法是很容易的，但工序没 有先后顺序约束也使可行调度结果的数量大大增加，要从规模庞大的解空间中 获得最优解仍然比较困难，因为计算量庞大，我们就要寻找出合适的算法来进 行最优解的求解。开放式车间的工件加工路线如图2 2 所示。 1 2 第2 章理论基础及算法 匡至习加亘丑 虹至卜媚至亚 文至亟三 囫虹亘丑 虹亟串名皿垂b 亟立 l 工艺路线3 卜一i - r g ml = 割l 工序ki 卜一七刮l 工序l1 刮完成加工： l 一- - j - - - - - - - - - - - 。l l j l _ j - - j - - - - - - - - - - - - o l 一、- 图2 2 开放式车间工件的加工路线 单件生产的车间中，其车间生产主要是以单件生产为主，所谓的单件生 产，就是对于不同的工件有各自特定的工艺路线，在单件生产的车间中，任何 工件的生产，都很难找到工艺路线完全想同的两个工件。j o bs h o p 调度问题适用 于单件小批量生产，其目标是在满足工件工艺路线要求的前提下，确定每台设 备上不同加工任务的先后加工顺序，使得所有不同工艺的工件能在一个合理的 时间内加工完毕，并能够达到所要求的性能指标。此类调度问题中存在两种序 列：每个工件对应的工序序列和每台设备对应的加工任务序列。在工件加工路 线和设备加工能力双重约束下，此类调度问题成为一种典型的组合优化问题。 2 2 常用车间调度算法的简介 车间作业调度问题的决策内容，包括分配决策、时间决策和路径决策。车 间调度问题可描述为：生产车间有m 台机床，n 种工件，每种工件有多道工序， 每道工序可在多台性能不同的机床上加工，而在生产调度中，要解决的问题， 就是如何去安排这些工件在车间中的生产加工，然后满足我们的某个生产指标， 比如生产交货期、成本等等。在生产加工的过程中，每一台机器在每个时刻只 能加工某个工件的某道工序，这就是在生产加工的过程中的一个约束，称之为 1 3 第2 章理论基础及算法 台用约束。同时，每个工件在上道工序加工完成后才能进入到下一道工序的加 工，这个称之为顺序约束。在进行车间调度的过程中，由于调度的多目标性， 这就需要好的调度算法来控制调度过程。 由于很多领域的组合优化问题都与之有相似之处，因此调度问题受到了不 同学科研究人员的关注并展开深入的研究，随之产生了很多重要的新方法。这 些方法主要有：数学规划法、基于规则的方法、人工智能技术、人工神经网络、 邻域搜索技术、模糊逻辑等方法，使得调度的问题向多元化的发向发展。 1 运筹学的方法【m 】 运筹学主要是通过模型来解决问题的。用一个运筹学模型来代替现实情况 供我们分析研究，可以用数学形式表达，也可以用图表形式表达，也可以是某 种经验积累而成的技巧。模型是一个能达到一定目标( 一个或多个) 行动的一个系 统。因此，运筹学的核心问题，就是建立合适的模型和对模型的分析或求解。 对模型分析得到的结果，还需按照它能否解决实际问题来进行评价，否则就要 考虑改换模型，或者增减计算时用到的资料或数据。我们主要是用到数学规划 的方法来解决生产调度中的问题。 2 基于规则的方法 对生产加工任务进行调度的传统方法是使用调度规贝, u ( d i s p a t c h i n gr u l e s ) ，如 最简单的规则是分派规则，包括s p t ( 选具有最短加工时间的工件进行加工) ， l p t ( 选具有最长加工时间的工件进行加工) ，f r o ( 选具有最少剩余加工时间 的工件进行加工) 等。由于该方法具有简单、易于实现、计算复杂度低等特点， 能够用于动态实时调度系统中，多年来一直受到学者的广泛研究，并不断涌现 出新调度规则。 p a n w a l k a r 和i s k a d d e r 【l l 】总结了1 1 3 条规则，主要分为三类：简单规则、复 合规则、启发式规则；m o n t a z e r im e t a l 1 2 j 等列举了常见的2 0 条规则，并针对一 个实际的车间作业调度，分析了这些规则对系统性能( 如作业的平均等待时间、 设备的平均利用率等) 的影响。但是近十年的研究表明并不存在一个全局最优 的调度规则，它们的有效性依赖于对特殊性能需求的标准及生产条件。 这是一种启发式方法，采用优先规则对生产加工任务进行调度，完全根据 一定的规则或策略来确定生产过程中的每一步操作。虽然不一定能生成最优解， 但能够减小问题的求解空间，在短时间内得到较为满意的结果，是非常适用的 方法，在求解大规模调度问题的时候尤其能够体现出其优越性。 1 4 第2 章理论基础及算法 3 基于d e d s 的解析模型方法 该方法主要应用于f m s 生产线。由于制造系统是一类典型的离散事件系统， 因此，可以用研究离散事件系统的解析模型和方法去探讨生产调度问题，诸如 排队论、极大极小代数模型、p e t r i 网等。调度中的排队论方法是一种随机优化 方法，很难得到比较具体的细节。p e t r i 网作为一种图形建模工具，具有很强的 建模能力，对于描述系统的不确定性和随机性也具有一定的优越性。目前，p e t r i 网模型用于f m s 的调度还存在节点语义、重用性差、不能对高级的调度规则加 以建模等缺点。 4 基于排序的方法 该方法是先有可行性加工顺序，然后才确定每个操作的开工时间，并对这 个顺序进行优化，它虽然属于近似算法，但有可能达到最优的调度方案。 ( 1 ) 启发式图搜索法 对于表述为整数规划的调度问题，最初采用分枝定界法来解决，而后其它 的启发式图搜索法也被应用于解决调度问题。启发式方法的思想是按照调度规 则从尚未调度的工序的子集中选择一个工序进行调度，直到所有的工序都被调 度为止。由于调度规则是基于经验和特定问题，故没有普遍适用的调度规则存 在，某一规则只能运用于一定场合的问题，所求得的解只是可行解。 ( 2 ) 神经网络算法 h o p f i e l d 神经网络模型的提出为求解各种有约束优化问题开辟了一条新