（机械制造及其自动化专业论文）齿轮加工车间生产调度问题的研究.pdf

摘要 摘要 生产调度是生产决策的一种形式，在制造业中担当着非常重要的角色。在 当前的竞争环境中，有效的排序和调度是提高经济效益的基础和关键，并逐步 成为在市场中生存的必要条件。在6 0 年代，人们就已经用动态规划和整数规划 对调度问题做了大量的研究，然而现实中的调度问题往往与理论研究中的数学 模型有很大区别。在现实生产加工中会出现很多随机事件，现实中的机器环境 也非常复杂。 本篇文章在分析了齿轮加工工艺的基础上，针对齿轮加工车间生产调度问 题进行研究，主要研究工作如下： ( 1 ) 在分析各种齿轮加工工艺和齿轮加工车间布局的的基础上，阐述了齿轮 加工车间生产调度的理论。对齿轮加工中生产调度问题进行建模，并通过改进 的启发式算法对齿轮加工生产调度模型进行求解，以满足实际生产需求。 ( 2 ) 在加入各种实际生产要素的基础上，运用f l e x s i m 仿真优化软件对设计好 的模型进行虚拟仿真，验证其在生产加工中的可行性，并对各种调度方案进行 评价。 ( 3 ) 针对某齿轮厂的齿轮加工，通过和该企业的信息系统的集成，设计并开 发一套符合其生产要求的调度系统。 关键词：齿轮加工车间；生产调度；虚拟仿真；f l e x s i m ；调度系统 a b s t r a c t a b s t r a c t p r o d u c t i o ns c h e d u l i n gi saf o r m o fp r o d u c t i o nd e c i s i o n s ，i ti sp l a y i n ga n i m p o r t a n tr o l e i nm a n u f a c t u r i n g i nt h ec u r r e n tc o m p e t i t i o ne n v i r o n m e n t , t h e e f f e c t i v es o r t i n ga n ds c h e d u l i n gi st h eb a s i sa n dk e yo fi m p r o v e de c o n o m i c p e r f o r m a n c e ，a n dg r a d u a l l yb e c o m en e c e s s a r yf o rs u r v i v a li nt h em a r k e t i nt h e 19 6 0 s ，p e o p l eh a v ed o n eal o to fr e s e a r c hb yu s ea c t i v ep l a n n i n ga n di n t e g e rp l a n n i n g t h er e a l i t y s c h e d u l i n gp r o b l e mi sv e r y d i f f e r e n tw i t hm a t h e m a t i c a lm o d e l so f t h e o r e t i c a lr e s e a r c h al o to fr a n d o mi n c i d e n t sw i l lb ea p p e a ri nc u r r e n tp r o d u c t i o n , t h er e a l i t yo ft h ee n v i r o n m e n ti sa l s ov e r yc o m p l i c a t e d t h i sa r t i c l es t u d i e dt h es c h e d u l i n gi s s u eo nt h eb a s i so fa n a l y z 她t h eg e a r s p r o c e s s i n g ，m a j o rr e s e a r c hw o r kf o l l o w i n g ： ( 1 ) a n a l y z ea l lk i n d so fg e a rw h e e l sp r o c e s s i n gw o r k s h o pl a y o u t sa n de x p o u n d t h et h e o r yo ft h ep r o c e s s i n gw o r k s h o pp r o d u c t i o ns c h e d u l i n g m a k eam o d eo f p r o d u c t i o ns c h e d u l i n g ，a n dt h e nf i n dt h es o l u t i o nb yu s et h ei m p r o v e dh e u r i s t i c a l g o r i t h mt om e e tt h ep r o d u c t i o n n e e d s ( 2 ) o nt h eb a s i so fj o i n e dv a r i o u sp r a c t i c a lf a c t o r s ，v a l i d a t e st h em e t h o d s p r a c t i c a b i l i t ya n dt e s tf e a s i b i l i t yi np r o d u c ep r o c e s s i n gb yu s et h ef l e x s i me m u l a t i o n s o r w a r e a n dt h e nt oe v a l u a t ev a r i o u so p t i o n s ( 3 ) a c c o r d i n g t ot h ew h e e l s g e a rf a c t o r yp r o c e s s i n g , t h r o u g hi n t e g r a t e i n f o r m a t i o ns y s t e m so ft h ee n t e r p r i s e d e s i g na n dd e v e l o pas y s t e mt h a tm e e tt h e r e q u i r e m e n t so fp r o d u c t i o n k e yw o r d s ：g e a rw o r k s h o p ；p r o d u c t i o ns c h e d u l i n g ；v l r t u a lr e a l i t y ；f l e x s i m ； d i s p a t c h i n gs y s t e m 第1 章绪论 第1 章绪论 1 1 课题研究的背景及意义 随着竞争的日趋激烈，生产技术的不断更新，加工的方法越来越多样化， 因此，调度和优化在生产中所起的作用也越来越明显。改革开放以来，特别是 最近几年，生产制造方式发生了显著的改变，在充满竞争的大环境下，为了确 保生产过程的稳定性及高效率，以提高整体的经济效益，一些落后的、简单的、 不能满足生产需求的管理方法正逐步被市场所淘汰。生产管理工程师们要解决 的问题是如何对生产过程进行调度来满足生产计划不断变化下的生产要求，使 生产的柔性发挥到最大限度。 齿轮类零件是机械加工中的主要零件，从2 0 世纪末到现在，齿轮生产正逐 步从大批量连续生产向多品种、小批量生产转型。一个制造型企业的竞争能力 基本上取决于它是否具备在较短的生产周期内，生产出高质量、低成本、多品 种产品的能力。生产调度就是根据企业生产系统的生产目标和环境状态，在尽 可能满足约束条件( 如交货期、工艺要求和路线、资源现状) 的前提下，按照工艺 规程和计划，通过下达生产计划及调度指令对生产系统内的可用资源进行实时 分配，以实现缩短产品制造期、减少在制品数量、降低库存、提高生产资源的 利用率以及提高制造系统生产率等目的。制造企业非常迫切需要高效的调度系 统来制定企业生产计划与调度方案，来增加产能、降低生产成本、降低能耗， 以提高经济效益。 基于上述对研究背景的描述，本文在和江西某传动系统有限公司合作的基 础上，对齿轮生产车间的调度问题进行深入研究，在理论和实际生产上都具有 广泛的实用性和重要的意义1 1 5 】。 1 2 课题的研究现状与发展趋势 1 2 1 车间生产调度研究现状 从2 0 世纪中期，人们已经开始对调度问题进行研究。1 9 5 4 年，j o h n s o n n 提出了优化i 比厄c m 戤和们f c m “问题的有效方法，开创了经典调度理论研究 第1 章绪论 的先河。然而直到2 0 世纪5 0 年代末期，研究的主要内容还只是解决了在某些 特殊的生产情况和规模较小的、简单的流水车间的调度问题【1 1 1 ，研究范围过于 较窄。直到1 9 7 5 年，中国科学院研究员越民义、韩继业在 ：中国科学上发表 了论文n 个零件在m 台机床上的加工顺序问题”，从此拉开了国内调度理论研究 的序幕【1 2 1 。 6 0 年代末到7 0 年代，整数规划、动态规划和分枝定界法等运筹学的经典方 法被研究人员用来解决一些具有代表性的调度问题。g i f f i e r ，g a v e t t 和g e r e 等 人开始尝试用启发式算法对调度问题进行研究并且提出了一些优先分派规则， 至此，调度理论的基本框架初步形成p 1 0 1 。7 0 年代末，一些研究人员开始对优 化算法进行深入研究，研究证实了大多数的调度问题都是n p 完全或者n p 难问 题，无法用多项式的时间算法去表示，因此，启发式算法慢慢被学者们关注和 研究。p a n w a l k a r 在研究了前人的算法成果的基础上，总结归纳了1 1 3 条调度规 则并将其分类，到此，经典调度理论逐渐走向成熟 1 3 1 5 】。随着计算机学、理学 和工程科学等学科的相互渗透，学者们开始使用跨学科的方法对调度理论进行 研究【1 6 j 。从8 0 年代末到9 0 年代初是调度优化理论研究最活跃的时期，这段期 间涌现出大量不同的调度理论的新技术，如约束满足技术、神经网络技术、模 拟退火、禁忌搜索法和遗传算法等【1 7 q 9 】。到了2 0 世纪末，约束传播、粒子群优 化、蚁群算法和d n a 算法等一些新算法出现，使得特殊调度问题或者一般调度 问题的求解更加便利和高则2 眦4 1 。 虽然调度理论的发展已经日趋成熟，但经典调度理论在调度理论中的地位 依旧是不可动摇的。然而实际生产中面临的调度问题要比经典调度问题还要更 加复杂。从上个世纪8 0 年代起，一些研究人员就一直在研究并试图将调度理论 应用到实际生产中去，如何用丰富的调度理论来解决实际的生产调度问题已成 为当时迫切关心的问题。这也促使着越来越多的研究者开始寻求更直接、更有 效的方法来解决这个难题。 1 2 2 课题研究发展趋势 从上世纪5 0 年代起人们就开始了对调度理论的研究，但至今还不能将这些 理论很好的应用于实际生产中，一般的调度方法能够响应生产的动态变化，但 不能保证得到好的调度：一些最优调度方法理论上能够实现最优调度，但由于 需要通过十分复杂的计算才能实现，并且忽略了很多实际因素，也不能很好的 2 第1 章绪论 应用于实际生产中。因此，对调度问题的研究应该朝着以下几个方向发展： ( 1 ) 动态化 实际生产中的资源信息是不断更新和变化的，了解车间状态的动态特性， 研究车间生产的变化规律，寻求能确切反映生产状态变化的调度方法。如在生 产过程中遇到扰动和设备故障时，有效的调度方法能结合生产的实际情况及系 统的状态对原定的加工顺序和生产资源进行修改，使系统能够持续地、稳定地 运行。 ( 2 ) 集成化 在生产加工车间，车间计划与调度之间往往有着不可分割的联系。计划的 内容是生产什么，而调度的内容是怎样生产，探索车间计划与调度的集成对调 度理论在实际生产中的应用有着很好的促进作用。建立一个车间计划调度集成 系统，调度系统把生产状态及时地反馈到计划层，计划层根据生产状态原先的 生产计划进行修改或拟定新的计划，计划层再把更改后的方案输送到调度系统， 调度系统根据变更后的生产计划指导生产。 ( 3 ) 高效智能化 调度理论的研究虽然已经日趋成熟，但寻找新的调度算法仍是调度理论研 究者们研究的热点，寻求更高效的算法，该算法能够快速、高效地找到大型复 杂生产环境下的调度问题的最优或次优解，并能对解进行评估。 总之，随着对调度理论研究的不断完善，调度算法与生产实践的结合必然 越来越得到重视，向着动态化、集成化、高效智能化的方向发展【2 引。 1 3 本课题的研究内容 随着企业间的竞争越来越激烈，如何提高生产效率，增强企业的竞争力成 为现在研究的热点，车间生产调度的研究就是其中之一。在传统的作业车间调 度问题中，大多数研究者只考虑了机器设备资源受制约的作业车间调度问题， 称为单资源约束的作业车间调度问题 2 6 1 。而实际的作业车间调度问题中还存在 着另一类更为普遍的情况，即每一项加工任务需要多类资源来完成，这一类调 度问题被称为多资源约束的作业车间调度问题【2 7 1 。例如，在生产中的制造设备 资源、制造人员资源、模具、夹具资源、检验工具资源、物料资源、刀具资源 等，都属于车间调度中的各种资源。 3 第1 章绪论 本课题拟在吸收借鉴当今国内外先进的调度方法的基础上，结合齿轮生产 特殊加工工艺和车间布局，建立齿轮加工生产调度模型，探索一种适合齿轮生 产加工的算法对齿轮生产进行调度，已达到满足齿轮生产加工的要求。主要工 作内容如下： ( 1 ) 根据齿轮加工工艺和齿轮加工车间设备布局，分析齿轮加工生产调度 的方式，建立齿轮加工车间生产调度模型，并求解。 ( 2 ) 用f l e x s h n 仿真软件对所建立的齿轮3 h i 生产调度模型进行仿真，验 证模型的可行性。 ( 3 ) 对某企业齿轮生产过程进行系统仿真，提出改进方案。 ( 4 ) 根据所建立的模型，开发出一套适合齿轮生产的齿轮加工车间生产调 度系统。 1 4 论文的组织结构 本篇论文共分六章，各章节阐述安排如下： 第一章引言。本章介绍了车间生产调度的背景及国内研究的现状。阐述了 齿轮加工车间生产调度的意义。 第二章齿轮加工车间加工工艺及设备布局分析。本章描述了几种常用的齿 轮加工工艺路线及相应的齿轮加工机床的选择原则，分析其齿轮加工车间设备 布置形式。 第三章齿轮加工车间调度模型设计与求解。通过分析齿轮加工工艺和设备 布局建立不同的齿轮加工车间生产调度模型，并对相应模型设计求解方法。 第四章基于f l e x s h n 的齿轮加工车间生产调度系统仿真。本章介绍了用 f l e x s h n 建立齿轮加工车间系统仿真模型的方法和步骤。重点介绍了运用统计学 方法对齿轮生产过程的数据建模、仿真模型的检验和输出数据的分析方法。 第五章齿轮加工车间生产调度系统的开发。以某齿轮厂的齿轮生产线为 例，设计开发了一套适合该齿轮厂的生产调度系统。 第六章总结展望。对本文研究齿轮加工车间调度方法的重点内容与创新点 作了总结，并对齿轮n t 生产调度的发展方向作了展望。 4 第2 章调度的一般问题研究 第2 章调度的一般问题研究 2 1 生产车间调度问题的描述 车间调度问题( j o b s h o ps c h e d u l i n gp r o b l e m ，j s p ) 是将稀缺资源分配给在 一定时间内的不同任务，它是一个决策过程，其目的是优化一个或多个目标。 齿轮生产车间调度问题属于柔性加工车间调度问题( 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 m ，f j s p ) ，柔性加工车间的加工过程可描述为：设加工零件的数量为n ， 加工机床的数量为m ，每个加工零件包含多道固定顺序的加工工序，每道工序 可以在不同的机器上进行加工，在不同的机器上工序的加工时间也不同。调度 的任务是安排最合适的机床完成每道工序的加工，计划每台机床上各工序的最 佳加工顺序以及开工时间，使生产中需要达到的交货期、库存数量、经济小于 等性能指标达到最优。 组织中的资源和任务会呈现多种形式，车间里的机器、参与生产的工作人 员、被加工的零件等，都可以看作资源。任务则可能是生产过程中的操作、工 作人员的分配、计算机程序的执行等。每个任务可能有某种优先级水平、最早 可能开始时间和工期。目标也可能会呈现出多种形式，一个目标可能是最小化 最后一项任务的完成时间，而另一个目标可能是最小化超过工期才完成的任务 数量。生产系统中的调度必然与其他活动产生交互，这些交互依赖于系统，并 且从一种情况到另一种情况有本质的不同。 2 2 车间调度问题的分类 车间调度问题大致可分为以下几类：【2 ”o 】。 ( 1 ) 按资源约束 单资源约束：指车间的生产只受一种资源的约束，在某些关于调度的文献 中提到，单资源约束指的是车间生产中的加工机器数量不能满足同时加工所有 可加工工序的要求 双资源约束：指车间的生产同时受到两种生产资源的约束。其中主要的约 束资源是加工设备，另一种资源约束有可能是缺乏有经验的工人，或者缺乏某 种类型的刀具，也可能是一些辅助资源的暂时紧缺。 5 第2 章调度的一般问题研究 多资源约束：指在生产加工中有两种以上的资源约束着车间的生产能力。这 些资源可以是加工机器、操作工、物料运送设备及辅助资源，如量具、夹具和 刀具等。 在实际生产过程中仅仅存在单资源约束和双资源约束的情况并不多见，单 资源约束和双资源车间调度可以看成是多资源车间调度的特例，往往多资源约 束的车间调度问题是十分复杂的。 ( 2 ) 按生产结构 流水车间加工：在流水加工车间，所有被加工的工件都具有相同的加工路 径，加工设备在车间中的布局犹如流水线一样，加工工件从第一道工序开始依 次从生产线的一端进入，加工完成后再从另一端流出。 生产车间加工：该生产车间中的加工设备的是没有固定模式的，因此工件 在被加工时的加工路径、加工工序及工件数量也是任意的。生产车间调度是最 一般的车间调度形式。 开放车间加工：在开放车间里各工件加工工序间的加工顺序是任意的。工 件在被加工时可以从任意一道开始，在任意一道工序结束。 ( 3 ) 按加工特点 静态车间：在这种调度模式中，各加工工件从一开始就己经准备就绪。调 度的范围不包括工件在加工过程中遇见的突发状况，如交货期的提前、设备突 然发生故障或有更紧急的工件需要马上被加工等等。 动态车间：在这种调度模式中，调度的内容往往要涵盖工件在加工过程中 发生的各种突发情况。这要求调度能够随时考虑到车间生产能力的变化，在出 现突发情况后，可以立即根据当时车间的生产能力，对将要被加工的工件重新 进行调度，以保证车间的生产能力始终处于一个稳定、高效的状态。 2 3 调度问题的一些预备知识及常用分派规则简介 调度按生产组织形式的不同可分为确定性模型和随机模型。我们现在所研 究的齿轮生产车间调度问题属于确定性模型范畴1 3 1 1 ，在所有考虑的调度问题中， 工作和机器的数量被假设成有限的，工作的数量记做n ，机器的数量记做m ， 下标j 指一项工作，下标i 指一台机器。下面介绍一些常用的数据： 6 第2 章调度的一般问题研究 ( 1 ) 加工时间( p i i ) 。粕表示工作j 在机器i 上的加工时间。 ( 2 ) 完成时间( c “) 。工作j 在机器i 上的操作完成时间记做c i i o ( 3 ) 提交日期( r i ) 。r 。i 表示工作j 的提交日期，也可称为准备日期，指工 作到达系统的时间( 工作j 可以开始加工的最早时间) 。 ( 4 ) 工期( 氐) 。指承诺的发货或完成时间( 承诺将产品交给顾客的日期) 。 ( 5 ) 工作j 的延迟( k ) 。工作j 的延迟l i 定义为l j = q d j 。 ( 6 ) 工作j 的滞后( - r p 。工作j 的滞后t j = m a x ( q 也，o ) 。 ( 7 ) 权重( q ) 。工作j 的权重畔是个优先性因素，表示工作j 相对于系 统内其他工作的重要性。 一个调度问题一般用三元组a i p i 丫来描述 3 2 1 。旺域描述机器环境并包含单一 一项；p 域提供加工特征和约束的细节，可能根本不包含任何一项，也可能有多 个选项；丫域描述最小化的目标，常常包含唯一一项。 在a 域中可规定的机器环境有：单一机器( 1 ) 、并行同速机( p r o ) 、并行异 速机( q m ) 、并行的无关联的机器( r m ) 、流水车间( f r o ) 、柔性流水车间( f f c ) 、 加工车间( j m ) 、柔性加工车间( f j c ) 、开放车间( o m ) 。 p 域中说明的加工约束和特定限制可能包括多个选项：提交日期( 孔) 、顺序 确定的准备时间( ) 、中断( p r m p ) 、优选约束( p r e c ) 、故障( b r k d w n ) 、机 器适用限制( 帆) 、排列( p r m u ) 、阻塞( b l o c k ) 、无等待( n w t ) 、再循环( r e c r c ) 。 丫域中的最小化目标函数有：制造期( c 一) 、最大延迟( k 雌) 、加权完成 时间和( ic ；1 ) 、折扣加权完成时间( 哗( 1 一e - c j ) ) 、加权滞后和( l t j ) 、加 权滞后工作数量( u t ) 。 分派规则【3 3 】是调度方法的基础，人们对分派规则的研究已经活跃了数十年， 这些规则可以按照基于信息的不同可分为局部规则和全局规则。局部规则只利 用要么是工作等待队列要么是工作在排队等待当前机器的信息，全局规则可能 会利用其他机器的信息，比如这项工作下一步要经过机器的加工时间。表3 1 中 给出了常用的一些分派规则的概述，这些规则中的大部分都会在一定的机器环 境中得到最优调度，在其他情况下也会得到合理的启发式解【3 6 1 。 7 第2 章调度的一般问题研究 调度问题中要用到的这些基本分派规则是工作和机器属性的函数，属性是 和工作相关或和机器相关的性质，给定属性影响工作总体优先级的程度有所使 用的基本分派规则和它的比例参数决定。复合分派规则是综合了许多基本分派 规则的一个表达式，每个复合分派规则中的基本规则都有自己的比例参数它们 被用来确定这个基本规则对复合分派规则影响程度的比例，比例参数要么是有 规则的设计者确定的一个变量，要么是一个与时间相关的或者是与需要调度的 特定工作集相关的函数。如果它们和需要调度的特定工作集相关，那么需要进 行一些工作集的统计计算，这样可以尽量准确地定义当前的调度实例。 2 4 流水车间调度问题 2 4 1 流水车间调度问题描述 一般来说，流水车间调度问题 3 7 1 主要包括加工设备的集合( m ) 和加工工件 的集合( n ) 。同一个工件在不同机床上加工的顺序都是相同的。一台机床在同 一时刻只能对一个工件进行加工。各工件在每台设备上的加工次数仅有一次。 工件在加工时对机床的要求是非抢占式的，即在一台机床上如果有某个工件正 8 第2 章调度的一般问题研究 在加工则在对该工件的加工完成之前，此机床不能加工其它的工件。在流水车 间里，工件的加工准备时间与工件的加工顺序之间是无关联的，因此，工件的 加工准备时间可以添加至工件的加工时间中。在流水车间生产中的调度任务主 要是在满足调度目标的条件下安排工件的加工顺序。流水车间又分为一般流水 车间和置换流水车间，一般流水车间中每台机床上工件的加工顺序是不同的， 在置换流水车间中，每台机床上工件的加工顺序是相同的。置换流水车间是一 般流水车间的特殊情况。对于流水车间生产调度中的调度目标主要有完成时间、 交货期、最大延迟等，其中以完成时间为主要调度目标。 2 4 2 流水车间调度问题研究方法概述 对流水车间调度问题的求解主要通过精确方法、改进型启发式算法和构造 型启发式算法等来实现。精确方法主要包括分支定界方法、动态规划方法和整 数规划【3 8 j 等。在求解流水车间调度问题的过程中经常用到分支定界法和整数规 划法，然而，利用这些方法很难在短时间内解决一些复杂的调度问题。为了求 解复杂的流水车间调度问题，一些学者提出了构造型启发式算法，如p a l m e r 启 发式算法、g u p t a 启发式算法、j o h n s o n 启发式算法、c d s 启发式算法、n e h 启 发式算法和r a 启发式算法等【3 8 】。改进型启发式算法大多是一些具有通用启发 式策略的元启发式算法，所谓元启发式算法指的是一类算法概念的集合，它是 一种应用于大范围内不同问题的、具有多种用途的启发式算法，如遗传算法 ( g e n e t i ca l g o r i t h m ，g a ) 、禁忌搜索( t a b us e a r c h ，t s ) 、模拟退火( s i m u l a t e d a n n e a l i n g ，s a ) 、粒子群优化算法( p a r t i c l es w a r mo p t i m i z a t i o n ，p s 0 ) 、蚁群优 化算法( a n tc o l o n yo p t i m i z a t i o n ，a c o ) 、迭代局部搜索算法( i t e r a t e dl o c a l s e a r c h ，i l s ) 和变邻域搜索算法( v a r i a b l en e i g h b o r h o o ds e a r c h ，v n s ) 等1 3 9 】。 元启发式算法是一种只需要略微改动就能求解不同调度问题的算法，它的出现 使得利用启发式算法来求解高质量解的搜索空间变得更加便利。 2 5 作业车间调度问题 2 5 1 作业车间调度问题描述 作业车间调度问题t 4 0 j 指的是在加工时间和加工顺序已知的和确定约束条件 的情况下，在m 台机器上要加工数量为n 的工件，要求确定m 台机器上的最优 9 第2 章调度的一般问题研究 加工顺序，使得制造期、最大延迟或完工时间等性能指标达到最优。在典型的 作业车间调度问题中，通常会作如下假设： 一台机器在任意时刻都只能对一个零件进行加工，且只能被一台机器所 加工，零件在加工中不会发生中断，加工过程中机器不会发生故障； 在零件加工过程中，同一个工件不能在一台机器上加工多次； 在加工过程中，零件必须按照设计好的加工路线以指定的次序在机器上 进行加工； 加工过程中不考虑零件的优先权； 各工序的加工时间已经确定，在整个加工过程中加工时间保持不变； 零件在加工过程中允许等待，当前一个工作还在加工，则安排在此工作 后面的工作需要进行等待。 在作业车间调度排序中，每种加工任务可以按任何一种可行的加工顺序在 一组机器上进行加工。因此，作业车间生产排序的调度实际上具有广泛组合的 最优化问题，其算法排序非常多，因此只能根据需要优化的目标建立数学模型， 然后对排序进行优化。 2 5 2 作业车间调度问题研究方法概述 作业车间调度问题是大多数实际生产中调度问题的简化模型，是当前学者 们研究最广泛的一类调度问题。作业车间调度研究内容主要是求解工件的加工 开始时间、完成时间和加工顺序使得加工性能指标打到最优。传统的启发式算 法局限于解决那些生产规模小、加工方式单一的调度问题。鉴于传统的启发式 算法的局限性，近几年来模拟退火、进化计算、禁忌搜索法、混沌搜索法、变 邻域搜索法、等改进型领域搜索算法在作业车间调度领域应用十分广泛。 针对作业车间调度问题的求解方法有【4 2 】： 基于优先规则的启发式算法，求解速度较快，但优化结果质量一般不理 想； 枚举法，如分支定界法，用这种方法求解需要进行大量的计算，存储量 也非常大，难以解决大型复杂调度问题； 蚁群算法等方法在对加工时间进行优化时效果较差，优化结果受网络参 数影响非常大，甚至还会产生非法调度。 在使用模拟退火法、禁忌搜索法、遗传算法等方法进行优化时可以得到 1 0 第2 章调度的一般问题研究 理想的优化结果，但其性能十分依赖算法参数，且优化需要进行较长的时间； 因此，当前对于作业车间调度问题的优化算法的研究仍是调度问题中一项 重要的研究内容，针对作业车间调度的各种优化算法已经成为有效解决调度问 题的常用方法和国际调度研究的热点。 2 6 开放车间调度问题 2 6 1 开放式车间调度问题描述 开放式车间调度问题【4 3 1 ( o p e n - s h o ps c h e d u l i n gp r o b l e m ，o s p ) 是典型的 n p 难问题，问题描述如下：n 个工件在m 台机器上进行加工，每道工序有确定 的加工时间，每台机器在给定的时间内只能加工一个工件，且每个工件只能由 一台机器进行加工，同一台机器上工件的加工顺序是任意的，每个工件的工序 处理顺序也无限制，在加工过程中供需不允许中断。调度的任务是在满足上述 约束的情况下确定所有机器和工件的顺序组合，使总加工完成时间最小。 2 6 2 开放式车间调度问题研究方法概述 直接求解开放式车间的调度问题时困难的，一般的方法是先得到确定条件 下问题的最优排序，然后应用以下定理建立调度方法。 定理1 ：对应某台机器和n 道工序，总完成时间最小的调度为使 nh - 1 m i n y p 沪 i 暑a j h 2 2 k 2 l 当且仅当加工顺序按加工时间从小到大排列时。 定理2 ：对应第j 台机器和n 项工作，按一定顺序处理，若每个时间段插入 一后面批次处理工作时间厶p k ，此批工作的最小等待总时间是： nh - t m l n p i ，= 洫( p k t + ) i 芒籼h = 2 k - - 1 当且仅当加工顺序按加工时间从小到大排列时。 定理3 ：对于任意工作j l 、j 2 ，对应第一次处理完成时间或规定等待时间 】c 22x l ，工作j l 、j 2 的处理时间为p l 、p 2 ，如果满足0 p l 吼- x l 则最小等待时间 第2 章调度的一般问题研究 为o ，否则最小等待时间为r a i n( p l x 2t - x i ，p z + x 2 一x 1 ) ，p l 与 p z + z ( x 2 一x 1 ) 比较小者先处理。 定理4 ：一直对于任意作业j l 、j 2 ，对应第一次处理完成时间或规定等待的 时间x 2 芝x i ，设第一批作业处理时间为p 1 l 和p 1 2 ，等待时间为p l l ，p 1 2 j ；第二 批作业处理时间为p 2 l ，p 嚣，等待时间为p 2 l 。，p 2 2 ，则增加p 1 2 不能使 m i n ( p l z + p z 2 ) 减少。 定理5 ：任意两台机器的两作业处理时间为p 1 1 p 蛆，p 2 l ，p 托，每个作业 仅能在一台机器上处理一次，对机器按机器等待时间和处理最优排序：如果 对应处理序列为p n ，p 2 l 。一和p 1 2 ，p 托， 则 p 越= r a i ni p l l - p t = l ，j 为最优作业处理等待时间的机器编号：对应处理序列 为p n ，p z l ，邢p 琵，p l z ，时，如果p 1 1 p 1 2 ，则最有作业处理的 机器编号j = l ，若p 托 现1 ，则最优作业处理等待时间的机器编号j _ 2 ，且两者 必有一种情况成立。 可根据定理1 咐来构造优化队列，所得结果为c i 调度目标下的最优调度方 法。总完成时间目标的调度方法如下： ( 1 ) 对每一个作业按每一台机器由定理1 进行排序； ( 2 ) 从队列第一个作业开始，由定理5 对作业i a 按完成最小来确定机器加 工集合 ； ( 3 ) 对a 中的作业按定理1 或定理3 进行排序； ( 4 ) 计算x i l ，由定理1 的方法确定在下一批处理a 集合： ( 5 ) 对a 中的作业按定理2 、3 进行排序； ( 6 ) 重复( 3 ) 、( 4 ) 的工作直到最后一批处理作业排序完成。 2 7 小结 本章首先对生产车间调度问题进行了描述，然后对调度问题中的一些常用 知识和分派规则进行了介绍，最后对不同类别的车间调度问题的研究方法分别 进行了阐述，为后面的齿轮加工车间生产调度模型的建立提供了依据。 1 2 第3 章齿轮生产车间调度模型求解 第3 章齿轮生产车间调度模型求解 针对齿轮厂生产调度问题的研究，我们采取启发式算法和改进的启发式算 法对齿轮加工车间生产调度问题进行建模求解。本章首先分析了齿轮加工车间 生产调度的优化目标和影响这些目标的具体因素，然后根据齿轮加工车间生产 组织形式的不同将齿轮加工车间调度问题分为三种形式柔性流水车间生产调 度、开放车间生产调度和混合布置生产调度，分别建立数学模型，最后对模型 进行求解。 3 1 齿轮加工生产调度影响因素 3 1 1 齿轮的加工工艺 齿轮生产的加工工艺决定了齿轮加工车间的设备类型、数量和布局等因素， 因此根据不同的齿轮的生产加工方法，能够合理地设计齿轮加工调度模型，对 齿轮生产线进行调度。本章列举了几种常见类型齿轮的加工工艺及加工路线实 例，从生产调度的角度分析了齿轮加工设备的选择原则，为以后的齿轮加工车 间生产调度提供决策依据。常见的齿轮类型按其外形分为圆柱齿轮、锥齿轮、 谐波齿轮、非圆齿轮、蜗杆蜗轮，下面介绍这些齿轮的加工工艺【4 5 1 。 ( 1 ) 锻造制坯 目前，传动零件制造业的毛坯锻造工艺中使用最多的仍然是热模锻。最近 几年，楔横轧技术在轴类零件加工领域得到了广泛重视和推广，该技术特别适 合为复杂的阶梯轴类零件制坯，它具有加工精度高、后序加工余量小等优点， 可有效提高生产效率。 ( 2 ) 正火 此道工艺的目的保证后序齿轮在切削加工时具有合适的硬度并且为最终热 处理做准备，这样可以有效抑制热处理变形。齿轮生产中齿轮钢的材料一般为 2 0 c r m n t i ，通常情况下，正火工艺在不同人员、环境和设备的情况下，工件的 冷却速度和冷却均匀性都会有所不同，通常会造成硬度散差大，金相组织不均 匀等问题，会直接影响后面的金属切削加工及最终热处理，使得零件热变形大 1 3 第3 章齿轮生产车间调度模型求解 而无规律，零件质量得不到保证。为此，往往采用等温正火工艺，这样可以有 效改善一般正火的弊端，使得产品质量得到保证。 ( 3 ) 车削加工 随着对精度要求的提高，齿坯都采用数控机床进行加工，实现了在一次装 夹下完成对孔径、端面及外径加工，既保证了内孔与端面的垂直度要求，又保 证了加工完成的齿坯尺寸离散不会太大。提高了齿坯的加工精度，确保了后序 齿轮的加工质量。 ( 4 ) 滚、插齿 现在工厂仍普遍使用普通滚齿机和插齿机来加工齿部，虽然对机器的调整 和维护比较方便，但生产效率较低，若要完成较大的生产任务需要多台机同时 生产。如今，涂层技术的发展，使得滚刀、插刀刃磨后的再涂镀变得非常方便， 涂镀技术的应用使得刀具的使用寿命明显提高，这样可以有效地减少了机床换 刀次数和刀具刃磨时间，从而提高生产效率。 ( 5 ) 剃齿 大批量齿轮生产中常用的一项技术就是径向剃齿技术，径向剃齿技术有加 工时间短，齿形、齿向的加工要求易于实现等优点。这项技术在某些工业发达 国家已经应用成熟，近来在国内也得到逐步的应用，通过该技术加工的零件质 量稳定可靠。 ( 6 ) 热处理 渗碳淬火是加工汽车齿轮中的一个重要工艺，通过渗碳淬火以后的齿轮的 力学性能可以得到很好的保证。对于一些在热处理后不再需要磨齿加工的零件， 使用稳定高效的热处理设备是不可或缺的。该齿轮生产车间使用的是德国劳易 公司进口的连续渗碳淬火生产线，热处理效果十分理想。 ( 7 ) 磨h f d ；0 工 齿轮端面、内孔、外径等部分在经过热处理以后还要进行磨削加工，以减 小形位公差，提高尺寸精度。齿轮零件在加工时一般采用节圆夹具进行定位夹 紧，这样有效保证了齿部与安装基准的加工精度，产品质量从而也得到了保证。 ( 8 ) 修整 在修正环节主要是在齿轮装配前对零件进行毛刺的检查清理，避免在装配 后由于零件之间的不正常摩擦引起的噪声异响。检查清理毛刺主要通过单对啮 合听声音的方法，也可以在综合检查仪上观察啮合偏差来完成。该生产车间生 1 4 第3 章齿轮生产车间调度模型求解 产的变速器中，箱体类零件有离合器壳、差速器壳和变速器壳。离合器壳属于 承重零件，往往采用专用模具铝合金进行压铸而成。工艺流程包括：铣结合面 一加工连接孔_ 粗镗轴承孔一精镗轴承孔及定位销孔一清洗_ 检测。 以下是一些常见齿轮的加工工艺湖。 圆柱齿轮加工工艺 表3 1 圆柱齿轮加工工艺 锥齿轮加工工艺 表3 - 2 弧齿锥齿轮工艺工程 1 5 第3 章齿轮生产车间调度模型求解 蜗轮加工工艺 表3 - 3 蜗轮加工工艺规程 蜗轮加工工艺 表3 - 4 蜗杆加工工艺规程 3 1 2 调度优化目标 调度方案的优劣需要通过一定的目标函数来判断，目标函数也就是常用的 评价指标，j s p 问题中有以下几个常用的评价指标h 7 】： ( 1 ) 制造期( c 一) 。制造期定义为m a x ( c l ，c 2 ，c n ) ，和最后一项离 开系统的工作完成时间相等。最小的制造期通常意味着机器的高利用率。 1 6 第3 章齿轮生产车间调度模型求解 ( 2 ) 最大延迟( l i i i 瓤) 。最大延迟l i i i 甄定义为m a x ( l l ，k ，l n ) ，它用来 度量违反工期的最坏情况。 ( 3 ) 加权完成时间和( zqq ) 。n 项工作完成时间的加权和。 ( 4 ) 加权滞后和( 咄t p 。这是比加权完成时间更一般的成本函数。 3 1 3 齿轮加工车间的生产线类型 生产线就是产品生产过程所经过的路线，即从原料进入生产现场开始，经 过加工、运送、装配、检验等一系列生产活动所构成的路线。狭义的生产线是 按对象原则组织起来的，完成产品工艺过程的一种生产组织形式，即按产品专 业化原则，配备生产某种产品( 零、部件) 所需要的各种设备和各工种的工人， 负责完成某种产品( 零、部件) 的全部制造工作，对相同的劳动对象进行不同 工艺的加工。根据齿轮生产中加工批量的大小可将生产线分为产品工艺导向型 生产线和导向型生产线【4 阳： ( 1 ) 工艺导向性生产线：在多品种小批量的生产车间中，加工设备大都采用 工艺原则进行布置，按加工工艺分为粗加工、半精加工、热处理、精加工等几 个基本环节，每个环节中加工机床的功能都是类似的，这些机床全都集中放置 在一起组成一个生产小组，可以完成对齿轮的一道工序的全部加工。加工工件 根据已制定的工艺流程，经过在不同的生产小组上的加工来完成整个零件的加 工。 ( 2 ) 产品导向型生产线：工艺导向型的生产线一般只适合多品种小批量零件 的生产，而对于大批量齿轮零件的加工，其生产工艺基本是固定的，加工设备 也是基本固定的，在加工车间里集中了为加工某类型齿轮工件所需的所有设备 和有关工种的工人，加工设备一般按工艺路线顺序摆放，连续的流水作业可以 缩小相邻两个工序之间的距离，既缩短了生产时间，同时节省了运输费用，大 大提高了工作效率。图3 1 是齿轮加工车间流水作业示意图。连续的流水作业， 大大降低了加工工件在制品的数量，减少了空间和资金的占用量，从而生产成 本得到很好的控制。流水线生产对工人的技术要求降低，生产计划简单明了， 大大减少了生产管理的负担。 1 7 第3 章齿轮生产车间调度模型求解 图3 1 齿轮生产车间流水作业生产线 3 2 启发式方法概述 从上个世纪末到现在，学者们在不断追寻调度问题的解决方案的过程中发 明了很多实用的算法，其中启发式算法就是为了解决复杂调度问题而发明的一 种新思路和新方法。在这些启发式算法当中比较经典的算法如遗传算法、蚁群 算法、模拟退火算法、粒子群优化算法、禁忌算法等对求解车间调度等调度优 化问题有着很大的帮助。启发式算法的产生使得在n p 难调度问题的研究上有了 更进一步的发展。启发式算法的对调度问题的研究虽然起着很大的推动作用， 但它也不能确保得到最优解。应用启发式算法求解调度问题时，得到的解在保 证较好的稳定性的前提下尽可能的接近最优解，这样的启发式算法就是一个好 的启发式算法。下面介绍一些实用的启发式算法及其在调度问题中的应用。 3 2 1 遗传算法 1 遗传算法概述 遗传算法 3 0 l 是通过模仿生物遗传选择的方式构造的一种优化搜索算法，是 结合数学理论对生物进化过程进行的模拟仿真仿真。遗传算法最早是在美国学 者h o l l a n d 在1 9 7 5 年提出的，又经过几十年的研究，目前已经发展到一个比较 成熟的阶段。遗传算法的基本原理类似“染色体”的适者生存过程，即优秀的“染 色体”有更多的繁殖机会。通过“染色体”群的不停进化，最终结果得到最适应环 1 8 第3 章齿轮生产车间调度模型求解 境的个体，也就是所求问题的最优解或满意解。遗传算法由五个重要因素组成， 这五个重要因素是：编码和解码、适应值函数、初始种群、遗传操作和参数设 置。 2 求解遗传算法的主要步骤 ( 1 ) 先随机产生一个初始种群，这个初始种群是由被称为“染色体”的拥有确 定长度的特征字符串组成的。 ( 2 ) 对建立好的初始种群进行迭代，直到满足所需条件为止。迭代的步骤为： 计算种群中各“染色体”的适应度。 通过复制、交叉和变异操作产生下一代种群。 ( 3 ) 选择迭代过程中产生的最好的染色体，将该染色体解码为所求问题的解。 3 2 2 粒子群优化算法 粒子群优化算法【3 9 】( p a r t i c l es w a r mo p t i m i z a t i o n ，p s o ) 是一种基于群体搜 索的算法，源于对鸟群捕食的行为研究，由e b e r h a r t 博士和k e n n e d y 博士在1 9 9 5 年提出同遗传算法类似，但是并没有遗传算法使用的交叉和变异算子，而是粒 子在解空间追随最优的粒子进行搜索。在p s o 算法中，每个优化问题的解都是 d 维搜索空间的一只鸟，称之为粒子。所有粒子都有一个由适应度函数决定的适 应度和一个速度v i - - ( v i l , v i 2 ，, v i d ) ，决定它们在搜索空间飞行的方向和距离。 p s