（系统工程专业论文）离散制造业生产调度问题的研究.pdf

华中科技大学硕士学位论文 摘要 本文研究了离散制造业的生产调度问题的特性，并对这类问题的解决进行了探讨。 其目的在于从理论和实践上寻找解决离散制造业的生产调度问题的有效途径，为有关技 术的进步完善与发展以及先进调度系统的研究和开发提供一定的理论和实践基础。 本文的研究问题及所得到的主要结果可归纳如下： 、分别对不同类型的调度问题进行了描述，并且针对一些典型的情况建立了数学规 划模型，分析了问题的解决方案，方案的实施以及其复杂度，重点讲述了最一般的调度问 题单件车间( j o b s h o p ) 调度，分析和归纳了它的主要研究方法和各种方法的优缺点。 二、对长丰汽车集团公司机械部的生产调度问题进行了研究，分析了现行生产系统 的不足，建立了系统的简化模型，明确了所研究阔题的类型，对计算机调度系统进行了 功能规划，并指出了系统实现的难点和重点，提出了要解决问题的具体内容。 三、在对实际问题的分析基础上提出用遗传算法来解决生产调度问题，设计了一个 标准遗传算法，该算法采用了合理的编码方案，并提出了一种特殊的交叉算子，论文在 理论上证明了，该算法能够有效避免非法个体的产生，完成对搜索空间的全局搜索和局 部搜索，从而使得算法能够以良好的搜索性能完成问题的寻优过程。为了进一步验证算 法的有效性，编制了一个仿真程序对随机产生的调度问题进行了仿真，由收敛曲线可以 知道该算法能够寻找到较优解。 四、标准遗传算法在仿真中暴露了收敛速度过慢的缺点，为了加速算法收敛，论文 对标准遗传算法( c g a ) 进行了改进，在算法中引入了启发式规则和惩罚函数，对遗传 算法的搜索过程进行模式引导，缩小了算法的搜索空间，提高了算法效率，利用保优操 作保证算法能够全局收敛到最优解，最后对这种改进的算法进行了定性分析，说明了这 个改进算法设计思想的先进性和实用性。 五、具体设计了长丰汽车集团公司机械部计算机调度系统，针对实际中出现的各种 现实问题采取了相应的算法对策。该系统投入了使用，从调度实施结果可以看出，该系 统能够满足实际生产需要，取得了较好的效果。 总之，本文以实际课题为研究背景，对调度问题进行了深入的探讨，创造性地设计 了两个遗传算法来解决单件车间调度，完成了实际课题调度的系统分析和软件设计。 一 一一 一 关键词t 离散制造、生产调度。、j o b s h o p 调度、遗传算法启发式规财 染色体编码遗传算子、 华中科技大学硕士学位论文 a b s t r a c t i nt h i st h e s i s t 1 1 ep r o p e r t i e so fp r o d u c t i o ns c h e d u l i n gi nd i s c r e t em a n u f a c t u r es y s t e ma r e i n v e s t i g a t e d a sw e l la st h es o l v i n gm e t h o d s o ft h i sk i n do fp r o b l e m t h em a i np u r p o s ei st o f i n de f f i c i e n t a p p r o a c h e s o ft a c k l i n gt h es c h e d u l i n gp r o b l e m s i nd i s c r e t em a n u f a c t u r e s v s t a m a n dt o p r o v i d e t h e o r e t i ca n dt e c h n i c a l f o u n d a t i o n sf o r f u r t h e r i n g t h er e l a t e d t e c t m o l o g i e sa n d f o rd e v e l o p i n gt h ea d v a n c e dp r o d u c t i o ns c h e d u l i n gs y s t e m s t h em a i np r o b l e m ss t u d i e da n dt h er e s u l t so b t a i n e di nt h i st h e s i sc a nb es u m m e du pa s f o l l o w s 1 ) i t d e s c r i b e st h ed i 丘i r e n tk i n d so fs c h e d u l i n gp r o b l e m sb yf o r m u l a t i n gt h e ma s m a t h e m a t i c a lp r o g r a m m i n gm o d e l s ，a n da n a l y s e st h es o l v i n gm e t h o d sa n dt h ec o m p l e x i t yo f e a c hk i n dj o b s h o pp r o d u c t i o ns c h e d u l i n gi sag e n e r a ls c h e d u l i n gp r o b l e m t 1 1 em a i nr e s e a r c h t e c h n i q u e so f j o b s h o ps c h e d u l i n ga sw e l la st h e i ra d v a n t a g e sa n dd i s a d v a n t a g e sa r es t r e s s e d p r i n c i p a l l y 2 ) b ys t u d y i n g t h es y s t e md e m a n d so fa t y p i c a ld i s c r e t em a n u f a c t u r ew o r k s h o p ，t h ep a p e r s u m m a r i z e st h es h o r t a g e so ft h ee x i s t i n gs c h e d u l i n gs y s t e m ，s e t su pt h ep r o g r a m m i n gm o d e l a n dc a t e g o r i z e st h ep r o b l e m 3 ) b a s e du p o nt h ea n a l y s i so f t h ep r a c t i c a lp r o j c o t , t h eg e n e t i ca l g o r i t h m sa r ed e s i g n e dt o t a c k l et h ej o b s h o pp r o b l e m t h es c h e m eo fc h r o m o s o m ec o d i n ga n dg e n e t i co p e r a t o r sa r e d e s c r i b e di nd e t a i l o t h e r w i s et h ep a p e rp r o v e st h ea l g o r i t h m sw i t hau s e f u lc h r o m o s o m ec o d e s c h e m ea n das p e e i a lc r o s s o v e r o p e r a t o r c a r lp r o m i s et h ev a l i d i t yo f t h ed e s c e n d a n t i no r d e r t o v e r i f yt h ep r a c t i c a b i l i t yo ft h em e t h o d ，as i m u l a t o ro ft h e s t o c h a s t i cs c h e d u l i n gp r o b l e m s o l v i n gi sd e v e l o p e d t h es i m u l a t i o nr e s u l t s i n d i c a t et h a tt h eg e n e t i ca l g o r i t h m sc a r lf i n da s a t i s f a c t o r ys o l u t i o n 4 ) m e a n w h i l e ，t h e s i m u l a t i o na l s or e v e a l st h e d i s a d v a n t a g e s o fc g a ，s u c ha sl o w s e a r c h i n ge f f i c i e n c ya n dn o n - g l o b a lc o n v e r g e n c e t oo v e r c o m e t h e m t h ec g ai si m p r o v e di n t h et h e s i s t h eh e u r i s t i cr u l e sa n dp e n a l t yf u n c t i o n sd e s i g n e da c c o r d i n gt ot h es p e c i a l t i e so f t h e d i f f e r e n tp r a c t i c a lp r o b l e m sc a nr e d u c et h es e a r c h i n ga r e aa n de n h a n c et h ee f f i c i e n c y t h e o p e r a t i o nh o l d i n g t h eb e s tr e s u l tw i l le n s u r et h eg l o b a lc o n v e r g e n c e 5 ) t h ep r a c t i c a lj o b s h o ps c h e d u l i n gs y s t e mi sd e s i g n e da n di m p l e m e n t e d i nt h e r e a l - l i f e a p p l i c a t i o n ，i ta c h i e v e dq u i t es a t i s f a c t o r y r e s u l t s s u m m i n gu p ，t a k i n gt h es c h e d u l i n gs y s t e mo fc h a n g f e n gc o a sb a c k g r o u n d ，t h et h e s i s a n a l y s e sk i n d so fs c h e d u l i n gp r o b l e m s t w og e n e t i ca l g o r i t h m sa r ep u tf o r w a r dt o s o l v et h e i o b s h o pp r o b l e m o t h e r w i s et h ep a p e rh a sa c c o m p l i s h e d t h es o f t w a r ei m p l e m e n t a t i o no ft h e p r a c t i c a ls c h e d u l i n gs y s t e m k e y w o r d s ：d i s c r e t em a n u f a c t u r ep r o d u c t i o ns c h e d u l i n gj o b - s h o ps c h e d u l i n g g e n e t i ca l g o r i t h m s h e u r i s t i cr u l e sc h r o m o s o m ec o d e g e n e t i co p e r a t o r s 华中科技大学硕士学位论文 1 1 引言 1 绪论 科学技术的日新月异在急剧地改变着现代制造业的产品结构和生产过程，传统的相 对稳定的市场变成动态多变的市场；传统的管理、劳动方式、组织结构和决策准则经历 着新的变革：生产能力在世界范围内迅速提高和扩展，制造业竞争的焦点也发生了历史 性的转移。世界经济进入新的发展期，面对激烈竞争，近2 0 年来，特别是近1 0 年来， 人们将制造技术与飞速发展着的信息技术、自动化技术、现代管理技术与系统技术有机 融合，逐渐形成了新一代“先进制造技术”( a d v a n c e dm a n u f a c t u r i n gt e c h n o l o g y ) 。 | 】1 2 ) 3 c i m s 就是这种先进技术的重要组成部分。 1 2c i m s 的介绍 1 2 1 c l m s 的概念 c i m s 是英文c o m p u t e ri n t e g r a t e dm a n u f a c t u r i n gs y s t e m 的缩写，译作计算机集成制 造系统，计算机集成制造( c n “) 的概念最早是由美国约瑟夫哈林顿博士在1 9 7 3 年提出 的l 刀，c i m s 就是按c i m 的理念建成的系统，将企业作为一个统一的整体从系统的观点 即全局的观点广泛采用计算机高新技术，加速信息的采集、传递和加工处理，提高工作 效率和质量，从而提高制造业的总体水平。i l j c i m s 是自动化程度不同的多个子系统的集成。随着科学的发展和技术的进步，制 造业中的计算机应用水平在迅速提高，出现了多种程度不同的自动化系统。如管理信息 系统( m i s ) 、制造资源计划( m r pi d 系统、计算机辅助设计( c a d ) 系统、计算机辅助工艺 设计( c a v p ) 系统、计算机辅助制造( c a m ) 系统、柔性制造系统( r m s ) ，以及数控机床( n c ， c n c ) 、机器人等1 2 1 1 4 1 1 6 1 。c i m s 正是在这些自动化系统的基础上发展起来的，它根据企 业的需求和经济实力，把各种自动化系统通过计算机实现信息集成和功能集成，综合考 虑企业中人、技术和管理的作用，实现企业生产经营全过程中的信息流和物流的集成， 并在产品质量、生产成本、生产周期等方面达到总体优化。1 2 l 由此给出一个比较通用的c i m s 的定义：c i m s 是一种在某种环境下为提高企业总 华中科技大学硕士学位论文 体效益的全局性的观念和方法，这种观念方法要求以集成方式组织企业全部活动，包括 从设计、制造到销售和售后服务，要利用各种方法和技术工具( 计算机和自动化技术) ， 其目的在于及时地提高生产率、降低成本、按期交货、提高质量，确保生产系统全局和 局部的柔性等j 。 作为完成企业的生产经营目标的一种技术手段，c i m s 的基本任务是以计算机集成 的方式支持企业完成上述生产经营活动。通常c 1 m s 系统可分为四个分系统，即生产经 营管理分系统、工程设计分系统、车间自动化分系统以及计算机支撑环境分系统。1 2 l 【5 1 本文的研究重点车间生产的调度问题就是车间自动化分系统的一个主要模块。 1 22 离散制造业与连续制造业 对于制造系统的分类标准有多种，w i l d 从运作特点上依据产品的数量和种类的重复 程度将制造系统分为四类：连续过程制造和离散制造，其中离散制造可以继续划分为大 批量生产，批量生产和单件小批量生产。【2 】从c i m 的提出至今，c i m 的概念已从典型 的离散机械制造业扩展到化工、冶金等连续或半连续制造业。针对不同模式的制造企业， c i m s 的构成是有所不同的，下面从c i m s 的构成上介绍离散制造业和连续制造业的各 自的特点。 1 ) 离散制造业【2 】 在经营管理方面，由于离散制造业产品结构复杂，制造工艺复杂，工序多，生产周 期长，生产过程所需机器设备和工艺装备等种类繁多，结构与性能差异较大，因此企业 的生产经营管理工作复杂，要求很高的成套性和严格的交货期。为了满足这些特殊要求， c i m s 中的生产经营管理分系统比较关键和复杂，针对于此已经研究出了很多方法，如 物料需求计划( m r p ) 、制造资源计划( m r p n ) 、网络计划法( p e r t ) 等。 在工程设计方面，离散制造业由于产品结构复杂，工艺复杂，因此工程设计任务很 重，不仅新产品开发，即使在正常生产过程中也经常有大量的变形设计任务，这些设计 需要进行复杂的结构设计、工程分析、精密的绘图、数控编程和仿真等，因此工程设计 分系统对离散制造业c i m s 是不可缺少的、最重要的分系统之一。 离散制造业和连续制造业最大的区别在于它们的生产组织方式和生产特点。离散型 生产通常可以分为工程项目型、车间任务型、重复制造型等。工程项目型的特点是一个 企业组织的大部分能力和资源用于某个单项工程，对每个单项工程要分别进行计划编制 和生产管理。车间任务型生产的特点是，将功能类似的设备按空间和行政管理建成一些 生产组织。对于车间任务型生产的组织方式，其设备的使用是灵活的，加工工艺路线也 华中科技大学硕士学位论文 可以是灵活的。在车间任务型生产中，作业计划的调度和控制是生产的关键。重复制造 指的是大批量的流水生产，其特点是：( 1 ) 对一个特定产品的生产、所需的加工能力和工 艺装备是专门设定的；( 2 ) 力n m m 艺路线是固定的。被加工的零部件以流水的方式通过工 作中心或设备。各个工作中心( 或设备) 之间的平衡比车间任务生产是更重要，因为它将 确保流水生产的顺利进行。离散制造业的车间生产管理是非常复杂和重要的，其中的生 产计划和生产调度是个研究热点和难点，涌现了许多实用的算法。本文将以一个实际 课题为背景对车间生产调度算法重点论述。 2 ) 连续制造业【2 j l ” 连续制造业的产品物理结构相对简单，工艺过程比较固定，因此其c i m s 的经营管 理分系统相对比较简单，但连续制造业由于生产周期短，生产的节奏性要求高，因此一 般在管理上集中程度较高。 在工程设计方面，对连续制造业，正常的生产过程中，产品及其生产工艺是固定的， 虽多在技术性能，工艺参数有些变化，这些变化也是在技术标准规定的范围之内，因此 基本上不需要工程设计功能。连续制造业的c i m s 中，可以不包括工艺设计分系统，不 包括产品设计功能，其工艺管理功能以及连续制造业特有的产品配方、产品混合、物料 平衡等可纳入经营管理分系统中。 生产方面，连续制造业往往是化学的甚至生化过程为主，它要求复杂的自动控制装 置，为了保证生产的稳定性，实现稳产高产，不仅对生产设备的可靠性要求很高，对辅 助设备，如生产蒸汽、压缩空气、水、电等的设备也要求高可靠性，因此对于连续制造 业的c i m s 的车间自动化分系统中通常也纳入了辅助车间。 由于离散制造和连续制造的本身特点的差异，各自c i m s 也各有偏重。早期的c i m s 研究主要是针对离散工业的，相应的生产体现为决策支持、计划调度、虚拟制造、数字 机床、质量管理等，核心技术难题在于计划调度和虚拟制造等。随着c i m s 研究的进一 步发展，人们将c i m s 系统集成的思想应用到了流程工业即连续制造业中，也获得了良 好设计效果，而由于流程工业区别与离散工业的特征，使得流程工业c i m s 技术主要体 现在决策分析、计划调度、生产监控、质量管理、安全控制等。其中核心技术难题在于 生产监控和质量管理等。由于这些差剐，也有学者提出将流程工业c i m s 单独命名为 c i p s ( e o m p u t e ri n t e g r a t e dp r o c e s ss y s t e m ) 。【3 j 关于c i m s 和c i p s 技术对比见表l - 2 - 1 。 华中科技大学硕士学位论文 表l 一2 1c i m s 技术与c i p s 技术实施难点对比【4 j l项目c i m s c i p s l设计技术虚拟制造实验室管理系统和虚拟实验室 |生产技术数字加工先进控制系统 f质量管理基于采样破坏性的质量管理基于生产过程实时质量控制 l计划调度多维复杂空间的优化问题复杂空间的优化问题 1 3 生产调度问题在c i m s 中的意义 1 3 1 生产调度的概念 调度问题是一类应用广泛的运筹学问题。一般说来，对于调度决策的要求，是希望 在满足一定的技术与资源约束的前提下对一系列活动进行排序，并确定适当的执行时间 段，以保证各类活动得以经济合理的安排执行。依据应用背景的不同，被安排的活动可 以是机器上的加工工序、交通中的运输工具、学校中的课程、医院中的病床或手术，也 可以是c p u 中处理的进程等。 i o l 】生产调度问题就其本质来说，是一个涉及任务、时 间和资源( 如机床、材料、操作工人等) 的三维空间问题【1 2 】，其主要i f l 的在于确定制造过 程中何时、何地、由哪个任务占用什么样的资源，以此保证由技术工艺和资源容量等所 决定的一系列约束关系在调度计划执行过程中得到满足，并使企业经营目标或用户订单 要求所决定的、与调度计划执行过程及执行结果有关的一系列评价指标得以满足或优 化。 1 3 2 生产调度的作用和意义 在c i m s 系统中，生产调度是其中的一个复杂而且重要的部分，也是实现企业c i m s 的关键部分。它在c i m s 中的位置处于整个体系结构的中间，发挥两方面的作用：一方 面接受企业决策层的综合生产计划( 含生产、能源、库存、运输、设备等综合信息) ，经 静态计划分解，向下面的设备控制层发布调度命令，即各种生产设备和原材料用量的设 定值；另一方面，接受设备控制层上报的实时状态信息，依次进行动态调度来改变部分 设定值，并把计划执行情况上报企业决策层。现代化生产管理中，各企业的生产管理方 式不尽相同。 1 3 1 生产调度直接影响生产成本和资源的合理利用，决定着生产过程的顺利进行，生产 一 - _ 4 华中科技大学硕士学位论文 资源的合理配置和优化。因此，调度决策水平的提高已经成为现代制造企业中决定生产 经营过程能否稳定高效地运转的决定性因素之。在过去的几十年里，随着产品制造业 市场竞争性的加剧，不断地激励着人们寻找新的生产调度策略和优化算法，以提高资源 的璺产率及操作管理的相对水平，生产出更具有竞争性的产品。车间的调度优化工作， 因其在提高生产效率、降低生产成本等方面所起的重要作用，正越来越受到学者们的关 注。1 1 4 1 4 全文安排 本文的研究对象是离散制造业中的生产调度问题，对实际生产调度问题的解决进行 了探讨和研究。全文安排如下： 第一章阐述了研究课题的意义，讲述了制造业的发展趋势，c i m s 的概念和构成， 以及调度问题的研究内容和它在c i m s 中的重要研究地位。 第二：章将生产调度问题分成单机调度，并行机调度，f l o w s h o p 调度和j o b s h o p 调 度四种类型，并从建立数学规划模型的角度描述了各种类型的典型生产，讨论了各个模 型的解决方法和复杂度。 第三章给出了实际研究的问题长丰汽车集团机械部生产调度系统问题的定义， 并对该系统进行了详细的系统分析，讨论了现行系统中存在的问题，明确了系统开发的 重点和难点。 第四章采用遗传算法来解决生产调度问题，设计了一种实用的编码方案，交叉算子 则采用无性繁殖，该算法既简单又能够保证产生的新个体仍在可行解范围之内。并对随 机产生的调度问题进行了仿真，验证了算法的有效性。 第五章对标准遗传算法( c g a ) 做了改进。根据待解决实际问题的特点，在算法中引 入了启发式规则和惩罚函数。缩小了算法的搜索空间提高了算法效率，利用保优操作保 证算法能够全局收敛到最优解。最后对这种改进的算法进行了定性分析，证明了该算法 设计思想的先进性和实用性。 第六章介绍了长丰集团公司机械部生产管理系统的设计与开发细节，针对实际中出 现的各种现实问题的特点采取了相应的解决对策，并在软件实现上作了讨论。该系统现 已投入试运行，各项性能均超过原有的手工生产调度系统。 第七章进行全文总结。总结了本论文的研究内容，研究成果及研究意义。 华中科技大学硕士学位论文 2 i 问题的一般描述 2 生产调度问题的描述 总的说来，生产调度就是对一个可用的加工机床集在时间上进行加工任务集分配， 以满足个性能指标集。从数学规划的角度来看，车间调度问题可表达为在等式或不等 式约束下，对目标函数的优化。典型的车间调度问题包括一个要完成的作业集，每个作 业 | j 一个操作集所组成，各操作的加工需要占用机床或其它资源，并且必须按一些可行 的工艺次序进行加工；每台机床可加工工件的若干操作，并且在不同的机床上能加工的 操作集可以不同。调度的目标是将作业合理地安排到各机床，并合理安排作业的加工次 序和加工开始时间，使约束条件被满足，同时优化一些性能指标。一般说来，车间调 度包括作业排序和作业加工机床安排，相同的作业排序方案可以得到不同的调度方案， 但是在般实际生产情况下调度都是依据作业排序按照最早可能开( 完) 工时间来安排作 业生产的，所以实际上加工顺序确定之后，作业计划也就确定了。【l o 】因此在解决调度问 题中，作业排序是一个最关键的步骤。 根据加工系统的复杂度，调度问题可分为单台机床下的生产调度、多台并行机床的 生产调度、f l o w - s h o p 和j o b - s h o p 的生产调度；下面对这几类问题分别进行分析。为了 简明标识不同的调度问题，本文采用c o n w a y 等人提出的方法使用四个参数1 1 5 】：n n g a b ， 其q ， n 工件数： m 机器数； a 车间类型； b 目标函数。 为了方便表达，使用了如下的符号记法： 3 = ，以 ：全部工件的集合； m = m ，m 。 ：全部机器的集合： o h k j ( h = l ，日可，七= 】，啪：工件被指定在m k 机床上加工的第 工序，h 口为 被安排在m 。上加工的工序数； p 。h 0 ：对应于。埘的加工工作量( 有时也可以视作为加工时间) ； 6 华中科技大学硕士学位论文 d ：l ，工件的交货期； c ：j 工件的完工时间： 7 1 ：j 工件的延迟时间； s ：一个调度方案； ( s ) ：调度s 的目标函数值。 2 2 单台机床的生产调度 虽然单台机床的生产调度是一类最简单的调度问题，但这类调度也是实际生产中使 用最多的一类调度问题。比如，一个工人负责几台机器的维修，多列火车要依次通过一 个单轨轨道，几艘轮船等待停靠一个码头，一个工厂轮番生产几种不同的产品，对于有 多台机床的工厂或车间，往往有一台关键机床，它的作用的发挥，直接影响到全厂的生 产，这使得整个工厂或车间生产安排的焦点就在这台关键的机床上，这样的情景也可以 按照单台机床的问题来考虑。同时有很多复杂问题的调度可以通过模型简化，分解成单 机调度模型的组合，本文在解决实际课题中也用到了这种简化方法，因此对单机调度的 研究是很有理论和实际价值的。下面以有优先顺序约束的n l l 。为例对这类问题加以 讨论。1 1 0 】 n 个工件被安排在一台机床上加工，由于各个工件的重要程度不一样，或者工件的 加工在逻辑上有先后顺序，这些构成了工件的优先顺序约束。调度目标是使最大延迟时 间l 。最短。定义决策变量：x ；= 1 表示安排第k 个加工的是i ，工件，否则x ：= 0 。本 问题的一般数学规划表达为： m i n i m i z ek 。 ( 2 2 - 1 ) 满足：x j = l ( 七= l ，玎)( 2 2 2 ) x ；= l ( ，= l ，n ) k - i k li e x ：x ：( 七= 1 ，”) ，如果j ，必须在j ，开工之前完成加工 hh e p ，x ：一e , t ，x ；l 。 i = lj - t 一l ( 2 2 3 ) ( 2 2 - 4 ) ( 2 2 5 ) 华中科技大学硕士学位论文 x ： o ，l ( - ，k = l ，”) ( 2 2 - 6 ) x ? = 0 ( j = 1 ，”)( 2 2 7 ) 式( 2 2 1 ) 为优化目标：最小化最大延迟时间：式( 2 2 2 ) 表示同一时间只能加工一个 工件；式( 2 2 3 ) 表示一个工件的加工不能被抢占的；式( 2 2 - 4 ) 表示工件之间加工优先顺 序：式( 2 2 5 ) 是求每个工件的延迟时间。对于调度目标是最大延迟时间最短的单台机床 的作业调度问题，有定理证明最早交货期法则e d d ( e a r l i e s t d u e d a t e ) 可提供最优解。所 谓e d d 法则就是按照r 1 个工件的交货期从早到晚排列，构成一个交货期的非减顺序， 并以此顺序安排生产。 2 3 多台并行机床的生产调度 在实际生产中，常常有数台相同的机器对工件进行加工。每台机器完成同一工序， 每个工件只需在其中一台机器上加工。在实际工作中，也有这种问题。譬如有若干份文 稿需要安排给数个打字员打印，应该如何安排，使这些文稿在最短时间内完成? 我们称 这种问题为并行机床的调度问题。u o l 设有m 台平行机床，n 个不同的工件，n m ，每个工件只需经一道工序加- 3 2 ，m 台机床中的任何一台都可以承担所有工件的加工任务。机床i 对工件，的加工速度记作 s 。，那么如果仅由机床i 来加工工件需要时间为p ，s 1 1 个工件同时到达车间，加工 中不允许中断，一个工件只允许被安排在一个机床上加工。下面对这类问题中的几个典 型问题加以研究。 2 3 1 使最长流程时间f 眦最短( n l m p l f 。) 定义决策变量：x ：= l 表示第七个加工的是j ，工件且被安排在机床i ，否则x ：= o 。 本问题的一般数学规划表达为： m i n i m i z e y m 。( 2 3 一1 ) 满足：x ：= 1 ( = 1 ，h ) ， ( 2 3 2 ) x ；s 1 ( 七= l ，n ；i = l ，m ) ， ( 2 3 3 ) = 1 月n ( 日 s o ) x ；冬r 。( f - l ，珊) ，( 2 3 4 ) r - i - i 一一 8 华中科技大学硕士学位论文 x ： o ，1 ( ，k = l ，n ；i = 1 ，) ( 2 3 - 5 ) 式( 2 3 1 ) 为优化目标：最小化最长流程时间：式( 2 3 2 ) 表示一个工件的加工不能被 抢 i 的；式( 2 3 。3 ) 表示一台机床同一时间只能加工一个工件：从式( 2 3 - 4 ) 可以看出。 为最长流程时间，那么它不可能小于任何一台机床的总加工时间。当埘2 时，这类问 题已经被证明是一类n p 难题【1 7 】，对大规模的实际问题只能试图求解近优解或满意解。 2 3 2 使总加工时间最短( n m p y “c ，) 定义决策变量：工；= 1 表示第k 个加工的是，工件且被安排在机床f ，否则x ：= 0 。 本问题的一般数学规划表达为： 月m m i n i m 拓e e m 厂_ m 。， m l 。假设所有工件的到达时间为0 。要求确定这n 个工件在每台机器上的加工顺序， 使得预定的目标函数值最小，这类问题就称作是流水车间的生产调度问题。 2 41 模型分析m “删 设定：s 可行解集，有s = 1 ，2 ，n ；j 。可行解集s 中的第k 个工件： c ( d 。，i ) t - 件以在机床i 上的完工时间，那么： 1 0 x 肿( ，p = l ，n ；j ，q = l ，o p t t i 丑x ) ( 2 5 3 ) x 口+ p c 。 ( f ，p = l ，n ；j ，q = l ，o p 。) ，( 2 ，5 4 ) 华中科技大学硕士学位论文 x ( = ，”；，= 1 ，。) ，(。s)u 0i i o p 2 5 式( 2 5 1 ) 为优化目标：最小化最长流程时间；式( 2 5 2 ) 表示同一工件的工序之间的 加 先后顺序：式( 2 5 3 ) 表示表示一台机床同一时间只能加工一个工件。这类问题也是 一类n p 难题。 2 5 2 解决j o b s h o p 调度问题的主要方法 由于i o b - h o p 调度问题的本身复杂性以及实际生产的随机情况和运算规模，使得它 的研究非常具有挑战性。近年来，随着各种新的相关学科与优化技术的建立与发展，在 调度领域也出现了许多新的优化方法，比如神经网络、模拟退火法、遗传算法、禁忌搜 索法等，使得 o b s h o p 调度问题的研究方法趋于多元化。f 1 4 j 1 ) 确定性最优化方法。这类方法主要是通过对车间调度问题建立一个整数规划模 型，采用基于枚举思想的分枝定界法或动态规划算法进行求解。这类方法虽然从理论上 能求得最优解，但由于其计算复杂性的原因，不能获得真正的实用。 2 ) 基于启发式规则的调度方法。调度规则因其易于实现、计算复杂度低、能够用于 动态实时调度系统中等原因，许多年来一直受到学者们的广泛研究，并不断涌现出许多 新调度规则。将其分为三类：简单规则、复合规则、启发式规则。虽然启发式规则常被 用于实际当中，能够得到问题的可行解甚至满意解，但它们不具有全局优化的特点。 3 ) 基于知识的调度方法。近年来受实际需要的推动，基于知识的智能调度系统和方 法的研究取得了很大的进展。基于知识的调度方法是用专家系统自动产生调度或辅助人 去调度。它是将传统的调度方法与基于知识的调度评价相结合的方法。 4 ) 仿真调度方法。由于制造系统的复杂性，很难用一个精确的解析模型来进行描述 分析。而通过对仿真模型的运行收集数据，就能对实际系统进行性能、状态方面的分析， 从而能对系统采用合适的控制调度方法。 5 ) 基于d e d s 的解析模型方法。由于制造系统是一类典型的离散事件系统，因此可 以用研究离散事件系统解析模型和方法去探讨车间调度问题，诸如排队论、极大极小代 数模型、p e 雠网等。 6 ) 启发式图搜索法。对于表述为整数规划的调度问题，最初采用了分枝定界法，而 后其他的启发式图搜索法也被应用于解决调度问题。 7 ) 模拟退火法。模拟退火算法( s a ) 将组合优化问题与统计力学中的热平衡问题类 比，通过模拟退火过程，可找到全局( 或近似) 最优解。模拟退火法的改进算法有加温 退火法、有记忆的模拟退火法等。由于模拟退火法能以一定的概率接受差的能量值，因 华中科技大学硕士学位论文 而肓可能跳出局部极小，但它的收敛速度较幔，很难用于实时动态调度环境a 8 1 禁忌搜索法。对于复杂m i l l 合优化问题，禁忌搜索也是一种通过领域搜索以获取 最优解的方法。 9 ) 神经网络优化。h o p f i e l d 神经网络模型的提出为求解各种有约束优化问题开辟了 一条新途径。 1 0 ) 遗传算法。遗传算法是一种新的隐含并行优化搜索方法。遗传算法的最大优点 是通过群体间的相互作用，保持已经搜索到的信息，这是基于单次搜索过程的优化方法 所无法比拟的。但是，遗传算法也存在着计算速度较慢的问题。 1 1 ) 拉氏松弛法。拉氏松弛法由于其在可行的时间里能对复杂的规划问题提供好的 次优解，并能对解的次优性进行定量评估，近年来已成为解决复杂车间调度问题的一种 重要方法。 对生产调度问题的研究，在八十年代前多基于组合优化、整数规划、动态规划等数 学规划方法，后来扩展到排队论、控制理论等分析方法。但由于实际生产系统的维数多、 参数随机波动等复杂因素，分析方法对实际问题采取了不同程度的简化和假设，其结果 常常和实际值差别很大，有时只有指导价值，很难得到令人满意的实用结果。因而在实 际中仿真方法以及综合实际生产经验和理论分析的“实用性”启发式搜索方法得到了重 视，并和模糊逻辑、人工智能方法( 专家系统、自学习) 结合，在实际生产中已经有了良 好的应用。 2 6 本章小结 本章将离散制造业的生产调度分成四种类型即单机调度、并行机调度、f l o w s h o p 调度、j o b s h o p 调度，分别进行数学规划建模，探讨了各类问题的解决方法和复杂程度， 其中j o b s h o p 调度是一类最一般也最复杂的调度问题，因此，本章比较详细地介绍了此 类调度的研究方法，简单分析了各种方法的优越性和局限性，为后面章节研究调度方案 的选择提供了一个理论和研究基础。 华中科技大学硕士学位论文 = ：= = = = = = = = = = = = = = = = ；= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = ；= = = = = = = = = 一 3 长丰公司生产调度系统的研究 3 1 系统背景介绍 3 1 1 长丰集团公司计算机集成信息系统 长丰f 集团) 有限责任公司是以生产越野汽车为主的企业，辅之以生产汽车配件，包 括汽车沙发座椅、汽车冲压件、汽车橡塑件及汽车线束和动力转向器、汽车电器产品； 并承担生产公安、防洪、囚车等专用车，汽车修理及军械修理任务。长丰( 集团) 有限责 任公司经过5 0 多年的建设，为国家作出了重大贡献，为今后的发展打下了较好的基础。 但是，面对新的形势，特别是国际、国内市场竞争的严峻形势，公司急迫要解决在经营 和管理各方面存在着的许多与市场经济不适应的薄弱环节和瓶颈问题，期待通过运用先 进的管理思想，移植现代企业制度，建立新的管理信息系统，使问题得到解决，制度得 到不断的完善。基于此。公司委托华中科技大学设计开发出计算机集成信息系统。 该系统的总体设计思想是：着眼于供应链上的物料的增值过程，加快物料流、资金 流、作业流和信息流在供应链上的流动：集成供应链上所有流程的信息，实现信息资源 共享，为各级管理人员处理好各生产环节的供需矛盾，提供可靠的决策依据，系统设计 的主要功能要求有： 长丰集团公司管理系统 长丰汽车公司管理系统 生 产 计 划 子 系 统 生 产 管 理 子 系 统 供 应 管 理 子 系 统 销 售 管 理 子 系 统 人 力 资 源 管 理 子 系 统 财 务 管 理 子 系 统 生 产 技 术 管 理 子 系 统 质 量 管 理 子 系 统 图3 一l 一1 长丰集团汽车公司计算机集成信息系统 集 团 公 司 直 属 部 门 子 系 统 决 策 支 持 子 系 统 华中科技大学硕士学位论文 各二f 系统的主功能模块的逻辑结构图如下 预测需求定单 图3 - 1 - 2 系统功能模块逻辑结构图 库存信息 从逻辑结构图可以看出车间作业计划是整个系统的底层，直接影响着生产成本和资 源的合理利用，决定生产过程的顺利进行，因此优化和合理化组织车间的生产计划，实 现各车间主要生产环节的物流、信息流的一致，使在线生产的状态可控、可操作、容易 实现供需流的均衡管理，对降低生产成本，提高工作效率和企业管理水平有着重要作用。 在该系统中，我们将车间作业计划的安排在生产管理子系统中实现。 3 1 2 生产管理子系统 c i m s 中生产管理子系统是一个比较独立也是很关键的模块。生产管理子系统的主 要功能是实时收集在线生产信息和质量检测信息，实行在线生产管理和实时进行质量监 测分析，能进行各种报表的分析和统计，综合信息的查询以及生产成本分析。该子系统 的数据走向及关系如下图： 华中科技大学硕士学位论文 一= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 图3 - l - 3 生产管理子系统生产示意图 其中组焊、涂装、总装车间均采用流水车间( f l o w - s h o p ) 的生产方式，其调度问题如 第二：章所述相对比较简单，机械部为车间片件( j o b s h o p ) 的生产方式，这是一类最一般最 复杂的调度问题。如图所示每个车间的生产都受着上一环节车间的生产制约，因此机械 部的生产调度在生产管理子系统中最为重要，它的生产效率将影响和制约整个厂的生 产。因此机械部调度模块是该系统的重点和难点，也是本课题的主要研究对象。 3 2 机械部生产调度系统分析 3 2 1 机械部生产描述 机械部负责公司车身片件的生产，将板材裁剪后，进行冲压处理，制成各种片件， 其生成的片件送往焊装车间进行焊接。目前设备生产能力( 按2 班生产) 大约为1 3 0 0 - 1 4 0 0 套车身。车身一般由4 6 7 种片件构成。机械部有3 条冲压线，一条下料线。下料线将板 材翦成各种片件需要的尺寸。冲压线有a 、b 、d 3 条线。d 线冲压小件，交由外协生产， 本系统未予考虑。在a 线生产的片件有7 3 种，b 线有5 7 种。a 线上有5 台冲压机床， a i ，a 2 ，a 3 ，a