（控制理论与控制工程专业论文）基于微粒群优化算法的生产调度系统研究.pdf

摘要 摘要 生产调度问题是生产管理领域内的关键环节，算法研究是生产调度问题的 一个重要研究方向。微粒群算法作为一种新的全局优化搜索算法，以其实现简 单、通用、鲁棒性强等显著特点，被广泛应用于各种优化问题求解。本文以微 粒群算法为工具，重点研究了生产调度问题中的一类经典问题j o bs h o p 问题 的求解，并以实例验证了算法的合理性。 本文首先对生产调度的基本思想、发展状况给出了一般性的描述，综述了 对调度问题的各种求解方法，然后根据微粒群算法的特点和生产调度问题中面 对的难点，指出了微粒群算法求解调度问题的有效性和优越性，并结合目前微 粒群算法在生产调度问题中的研究现状，进一步加以论证。 本文应用微粒群算法求解复杂的生产调度问题，主要在以下几个方面作了 一些研究工作： ( 1 ) 通过大量阅读各种生产调度和微粒群算法的文献，指出了微粒群算法 适合解决生产调度问题。 ( 2 ) 在系统性地分析了微粒群算法的基本原理、算法特性及应用领域的基 础上，为了解决微粒群算法求解j o bs h o p 问题过程中遇到的计算量大的问题， 本文采用了微粒群算法求解j o bs h o p 问题的机器分解方法。机器分解法是在每 次迭代中微粒仅在子图中构造部分解，并与上次迭代中其他机器上的顺序共同 构成本次解，这样提高了微粒群算法求解j o bs h o p 问题的效率。 ( 3 ) 将该算法用于求解车间生产作业调度问题，以最小生产时间跨度为优 化目标，构建了基于微粒群算法的车间生产作业调度问题求解方法，并结合某 机电设备厂的车间作业调度实例，验证了算法在实际项目中的可行性。 最后对论文的研究工作进行了总结，并展望了微粒群算法在相关领域需要 进一步研究的课题和实际应用拓展的前景。 关键词：生产调度，微粒群算法，车间作业调度，机器分解 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 gp r o b l e m i sa l le s s e n t i a l p a r t o ft h e p r o d u c t i o n m a n a g e m e n t t h es t u d yo fa l g o r i t h mi s a l li m p o r t a n ta s p e c to fs o l v i n gs c h e d u l i n g p r o b l e m a so n eo fg l o b a lo p t i m a la l g o r i t h m ，p a r t i c l es w a r m o p t i m i z a t i o na l g o r i t h m ( p s o ) h a s b e e ni n c f e a s i n g l yi m p l e m e n t e di nf i e l do fs c h e d u l i n gd u ei t sc h a r a c t e r i s t i c so fs i m p l ya p p l i c a t i o n ， 西o b a lo p t i m i z a t i o na n di m p l i c i tp a r a l l e l i s m u n d e rt h i sb a c k g r o u n d ，t h i st h e s i s m a k e i n d e p t hs t u d yo nj o bs h o ps c h e d u l i n gp r o b l e m ，w h i c hi so n eo ft h em o s tf a m o u s p r o d u c t i o ns c h e d u l i n gp r o b l e m s ，b yu s i n gp a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h m f i r s t l y , t h et h e s i si n t r o d u c e st h eb a s i ci d e a s a n dd e v e l o p m e n ts t a t u so ft h e s c h e d u l i n gp r o b l e m ，a n dt h e ns u m m a r i z e sv a r i o u sf o r m e r s o l u t i o n st ot h es c h e d u l i n g p r o b l e m s e c o n d l y , o nab a s i so f p s o sc h a r a c t e r i s t i c sa n dl i m i t a t i o n so ft h e s c h e d u l i n gp r o b l e m ，i tp o i n t so u tt h a tp s o i sa ne f f e c t i v ea n dp r e d o m i n a n ta p p r o a c h f i n a l l v a c c o r d i n gt ot h ep r a c t i c a lr e s e a r c ho fp s ob e i n g u s e di ns c h e d u l i n gp r o b l e m ， t h i sp o i n tc a nb ef u r t h e rd e m o n s t r a t e d t h i st h e s i su s ep s ot of i g u r eo u tt h ec o m p l i c a t e ds c h e d u l i n gp r o b l e m t h em a i n r e s e a r c hc o n c e n t r a t e so nt h ef o l l o w i n gs e v e r a la s p e c t s ： ( 1 1a c c o r d i n gt oag r e a td e a lo fd o c u m e n t so ns c h e d u l i n gp r o b l e m a n dp s o ，t h e i s s u et h a tp s ob e i n ga d a p t i v et os o l v es c h e d u l i n gp r o b l e mi si n t r o d u c e d ( o nab a s i so fa n a l y z i n gt h ep s o b a s i ct h e o r y , a l g o r i t h mc h a r a c t e r i s t i c sa n d a p p l i c a t i o nf i e l d s ，t h i st h e s i sp r o p o s e sam a c h i n e b a s e dd e c o m p o s i t i o nm e t h o df o r j o bs h o pp r o b l e mb a s e do np s o t od e c r e a s et h el a r g ec o m p u t a t i o no ft h ep s o w h e n s o l v i n gj s e t h ep a r t i c l ej u s tg i v e st h ep a r t i a ls o l u t i o no no n em a c h i n ee a c ht i m ea n d t h ep a r t i a ls o l u t i o nc o m b i n i n gw i t ht h el a s ts o l u t i o no no t h e rm a c h i n e sc o n s t r u c tt h e s c h e d u l i n gr e s u l tt h i st i m e t h i sm e t h o di m p r o v e st h ee f f i c i e n c yo fp s o t oj s e ( 3 ) w i t ht h eo p t i m i z a t i o nt a r g e to fm i n i m u mm a k e s p a nt i m e ，p s oi s u s e dt o o p t i m i z et h ej o bs h o ps c h e d u l i n gp r o b l e m i nt h a tc a s e ，i te s t a b l i s h e st h e p o s s i b i l i t yo f p s oi m p l e m e n t e di nt h ef i e l do fj o bs h o ps c h e d u l i n gp r o b l e m w h i l ec o m b i n gw i t hs o m e e m p i r i c a le v i d e n e eo fm e c h a n i c a la n de l e c t r i c a le q u i p m e n tc o m p a n y , i th a sb e e np r o v e d t ob e i i a b s t r a c t p r a c t i c a la n da s t r i n g e n c y f i n a l l y , t h ew o r ko ft h i sd i s s e r t a t i o ni ss u m m a r i z e da n d f u r t h e rr e s e a r c ho np a r t i c l es w a r m o p t i m i z a t i o ni sd i s c u s s e d k e yw o r d s ：p r o d u c t i o ns c h e d u l i n g ，p a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h m ( p s o ) ，j o b s h o ps c h e d u l i n g , m a c h i n e - b a s e dd e c o m p o s i t i o nm e t h o d n l 学位论文版权使用授权书 本人完全了解同济大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名： 治弓舷 ，j 沙7 年 l z 月日 ， 同济大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位敝储躲始甍私 7 年妇日 第1 章绪论 第1 章绪论 1 1 生产调度问题的研究背景 随着科学技术与生产力的不断发展，社会发展对于资源的依赖同益严重， 资源紧缺已成为社会发展所面临的一项难题。资源作为社会发展的基础，制约 着宏观与微观经济的各项活动。面对日益紧缺的资源，如何优化资源配置已成 为全社会关注的一个焦点问题。解决资源优化配置的一个有效途径就是调度， 根据对资源的不同需求，应用调度手段使得资源得到优化配置。 早在2 0 世纪初，生产调度问题卜1 作为一类典型的实际调度问题，就受到了 企业工程师和管理顾问的重视。当时只是一些简单的想法，并没有上升到理论 的高度，也没有切实可行的实际应用，比如g a n t t ( 1 9 1 9 ) 解释如何使用可视化的 图表来表示生产情况，c o e s ( 1 9 2 8 ) 描述了一种机械的调度技术，它与现在的“看 板”系统有许多共同特性。当时的企业工程师和管理顾问很清楚要对工厂中的复 杂问题做些什么：他们讨论如何“分派”工作以及能胜任这些工作的“调度员”，调 度员就是负责短期决策和故障预测的企业人员。从上世纪5 0 年代起，调度问题 的研究受到应用数学、运筹学( 最优化理论) 和工程技术等领域科学家的重视， 科学家们利用运筹学中的线性规划、整数规划、目标规划和动态规划等方法， 研究并解决了一系列有代表意义的调度和优化问题。但是，人们普遍把6 0 年代 c o n w a y 、m a x w e l l 和m i l l e r 三人有关调度的研究工作作为调度理论研究的正式 开始，他们三人也被人们称为调度理论的奠基人。此后3 0 多年的调度理论和应 用研究都受到他们的影响，应用到当今软件系统中的一些调度技术和模型仍然 在使用他们三人提出的有关调度理论的基本假设和问题定义。7 0 年代，随着科 学技术的发展，生产规模越来越大，复杂性越来越高，市场竞争也越来越激烈， 因此对企业的管理和对生产过程的监控都提出了更高的要求。在激烈的市场竞 争中，为了保证生产的高效稳定运行，以获得最大的经济效益，原来简单的、 局部的、常规的控制和仅凭经验的管理己经不能满足现代生产的要求了，企业 管理者和控制工程师们面临的问题是：如何根据市场上原料供应和产品需求的 变化进行经营决策和组织生产；如何在生产计划改变的情况下对生产过程进行 控制，以便最大限度地发挥生产的柔性；如何在生产工艺不作大的改变的f j 提 第1 章绪论 下进行管理、决策，使企业产生最大的综合经济效益。 为了解决上述问题，1 9 7 3 年美国约瑟夫哈林顿( j o s e p hh a r r i n g t o n ) 博士提 出了计算机集成制造c i m 卜1 ( c o m p u t e ri n t e r g r a t e dm a n u f a c t u r i n g ) 的概念，c i m 是一种组织、管理与运行企业生产的新哲理，它借助计算机软件、硬件，综合 运用现代管理技术、制造技术、信息技术、自动化技术、系统工程技术，将企 业生产过程中有关人、技术、经营管理三要素及其信息流与物质流有机地集成 并优化运行，以实现产品的高质、低耗，从而使企业赢得市场竞争。 计算机集成制造系统p ( 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 i m 哲理而组成的实际系统。从狭义上讲，c i m s 定义为应用计算机及网 络技术实现生产过程各个环节的集成化的系统。这仅仅是基于纯技术的定义， 没有考虑经济的、社会的和人为因素的影响。从广义上讲，c i m s 是一种在某种 环境下为提高企业总体效益的全局性的哲理和方法，这种理念要求以集成方式 组织企业的全部活动，从设计、制造到销售和服务的各阶段要尽可能利用各种 方法和技术工具( 计算机和自动化技术) ，以及时地提高生产率、降低成本、按 期交货、提高质量，确保生产系统全局和局部的柔性等，后者说明经济的、社 会的和人的因素和技术有着同样的重要性。 生产调度是c i m s 环境下生产的核心内容，因此无论是生产调度理论的研 究，还是应用系统的开发都受到了学术界和企业界的关注。生产调度问题通常 是多约束、多目标、随机不确定优化问题，已被证明属于n p h a r d 问题1 。所 以实际的调度问题往往难以找到精确最优解，因而人们只能设法寻求某种程度 的近似最优解。由于传统的优化方法不能够很好的求解规模较大较复杂的调度 问题，因此，近年来各种不同的人工智能方法逐渐被引入到调度领域中，取得 了很大进展。 1 2 课题的国内外研究现状分析 众多国内外学者应用不同的求解算法对生产调度问题做了大量的研究工 作，并提出了不同的调度理论与优化算法，但由于生产调度问题的复杂性与离 散性，对该问题的求解尚未形成一个完整的理论体系，提出的各优化算法在求 解过程中也会出现早熟、收敛于局部解、收敛时间长等问题。近年来，人们运 用模拟自然界一些自然现象发展起来的一系列仿生型智能优化算法求解生产调 2 第1 章绪论 度问题，而微粒群算法就是其中的一种。 微粒群算法中的微粒速度和位置都是连续变量，因此它能直接应用于连续 优化问题。而对于生产调度这一类组合优化问题，需要做一些调整和改变才能 应用p s o 求解，且有关应用p s o 求解生产调度问题的研究相对较少。武汉理工 大学雷德明等人己申请了“基于粒子群优化的多目标生产调度研究”的国家自然 科学基金，该项目研究多目标粒子群优化算法( m o p s o ) ，将协同进化引入 m o p s o 中，并提出利用粒子群算法处理多目标作业车间调度的两种有效策略。 近年来，有不少学者将微粒群算法应用于调度的各个领域。文献【7 】提出了 用一种不减少次序机制的最小位置值规则改变置换工件位置矢量的问题，用同 样的方法，文献f 8 1 提出了一种分别用最小化目标制造周期和最大化延迟工件加 工求解置换流水作业调度问题。文献f 9 1 提出一种基于混合p s o 的算法求解多目 标柔性j o bs h o p 调度问题。文献1 1 0 1 提出一种自适应馄沌p s o 算法求解在摆脱 调节情况下的短期水力发电系统的调度问题。文献1 1 1 提出一种s p s o a 算法求 解置换流水作业车间调度制造周期最小化问题。文献【1 2 】利用p s o 算法解决不 确定条件下的混合调度问题。文献 1 3 $ t j 用p s o 算法解决资源受限制的工程调 度问题。文献【1 4 1 提出一种基于p s o 和s a 的新算法求解j o bs h o p 调度问题。文 献【1 5 】将微粒群算法应用到柔性车间调度问题。文献【1 6 】提出一种基于自适应变 异的p s o 算法求解车间调度问题。文献1 1 7 提出一种与局部优化和粒子微变异 方法相结合的混合微粒群算法求解混流装配线优化调度的问题。文献【1 8 】提出一 种p s o o s p 算法求解开放式车间调度问题。文献 1 9 1 在p s o 中引入遗传算法中 的“杂交”算子，并采用自适应的惯性权重求解水库长期优化调度问题。文献 2 0 】 提出了一种2 维粒子表示方法，通过对粒子位置向量进行排序生成有效调度， 并采用粒子位置向量多次交换的局部搜索方法求解港口拖轮作业调度问题。文 献 2 1 1 5 i j 用p s o 算法解决同序流水作业排序问题，以实现制造周期和工件总的 流程时间最小化。文献 2 2 1 5 a j 用p s o 算法解决资源受限制的工程调度问题，以 实现工程周期最小化。文献 2 3 1 禾1 j 用p s o 算法建立一个多目标顺序计划模型， 用于钢板的制造。文献1 2 4 1 针对整数规划问题的特点，提出了一种在整数空间中 进行进化计算的p s o 算法，使微粒群的进化限于整数空间。文献【2 5 】提出并研 究了一种应用于机器人路径规划的改进微粒群算法，提出了矢量编码方案，有 效地避免了对地图建模过程的依赖。文献f 2 6 1 针对标准微粒群算法无法合理控制 全局搜索和局部开发之间的关系，容易出现早熟收敛和全局收敛放慢的现象，提 3 第1 章绪论 出了一种基于吸引力排斥力平衡机制的改进微粒群算法。文献【2 7 】提出了一种基 于微粒群算法的纹理合成图像修补方法，对候选区域确定初始微粒，利用p s o 算法搜索得到最优匹配块。 1 3 课题研究的目的与意义 生产调度理论作为调度理论体系中一个重要组成部分，其提出至今已有几 十年的历史，它作为企业生产计划与控制理论的重要组成部分，是保证企业生 产能够顺利运作的基础。提升企业竞争力的一个重要途径是实现对该问题的有 效求解，选择一个优秀的作业调度方法能够有效的优化企业生产资源配置，缩 短产品加工时间，降低产品生产成本，提高企业生产效率，从而全面提升企业 的市场竞争力。生产作业调度问题的研究对于生产企业有着重要的实际应用价 值。 到目前为止人们己经设计了各种算法来力求趋近最优解，比如，神经网络 算法、遗传算法等。但这些算法大多存在搜索效率和搜索效果之间相互矛盾， 相互制约的问题，当遇到机器数量和工件数量较多的调度问题时，上述算法需 要的运行时间较长，实际应用效果不是很理想。随着新的优化算法不断提出， 为车间生产调度问题的求解提供了新的手段。本文正是将近年来提出的微粒群 优化( p a r t i c l es w a r mo p t i m i z e r ，p s o ) 算法用于对车间生产调度问题的求解，提出 了基于微粒群优化的车间生产调度方法，对车间生产调度问题的求解进行了新 的探索。与其它算法相比较，微粒群群优化算法的优势在于简单、容易操作、 收敛速度快、所需领域知识少，同时又有深刻的智能背景，既适合科学研究， 又特别适合工程应用。p s o 是基于群体的优化技术，亦即搜索轨道有多条，显 示出较强的并行性，并且无需梯度信息，只需利用目标的取值信息，具有很强 的通用性。因此，生产调度问题的建模理论与求解算法的研究有着重要的学术 理论意义。 1 4 本文的主要内容与组织结构 本文研究的主要内容是车间生产调度系统。结合微粒群优化算法的思想， 重新定义了算法中的各种操作算子，提出了可以用于求解调度问题的微粒群算 4 第1 章绪论 法，并对算法进行了优化，成功应用于j o bs h o p 调度问题。 本文结构安排如下： 第一章：绪论。阐述生产调度问题的研究背景，国内外研究现状分析及课 题研究的目的与意义。 第二章：生产调度问题综述。描述了生产调度的概念，调度问题的表述及 其发展过程；介绍了生产调度问题的特点及分类；进而介绍了生产调度问题的 一些优化方法。 第三章：微粒群优化算法。描述了微粒群算法的发展背景；系统地阐述了 微粒群算法的基本原理；包括算法描述，算法流程，参数分析；进而对算法进 行优化改进，介绍一种避免陷入局部最优的微粒群算法。本章为后面章节关于 本课题的研究奠定了理论基础。 第四章：基于微粒群算法的车间作业调度问题求解。描述了车间作业调度 问题，并对其建立数学模型；在分析了j o bs h o p 问题的研究内容、约束条件及 优化目标的基础上，设计求解j o bs h o p 问题的微粒群优化算法。并将其应用于 生产车间实例，验证算法的可行性。 第五章：总结与展望，本章对全文的工作进行了回顾和总结，并对进一步 的研究作了展望。 5 第2 章生产调度问题综述 第2 章生产调度问题综述 2 1 调度问题的表述及其发展过程 所谓调度p 1 ，就是为了实现某一目的而对共同使用的资源进行时间上的分 配。从数学规划的角度来说，生产调度问题可表述为在等式或不等式约束下， 对目标函数所进行的优化。现代典型的生产调度问题就是：将作业均衡地安排 到各机床上，并合理地安排作业的加工次序和加工开始时间，在满足约束条件 的同时优化一些性能指标。 调度问题是一类应用范围很广的问题，如进货与送货的车辆调度，采购与 销售的经营策略等。在其他领域如计算机中线程的调度，计算机网络路由器资 源的调度，人力资源的分配问题，飞机航线的分配，飞机起降调度与闸口的分 配等。它们的本质问题都属于合理利用有限资源的调度问题，只是外在形式不 同而已。 调度问题的研究始于2 0 世纪5 0 年代，j o h n s o n 提出了解决n 2 f c 一和 部分特殊的n 3 f 问题的优化算法，代表调度理论研究的开始：2 0 世纪 6 0 - - 7 0 年代建立了调度理论的主体( 经典调度理论) 并重视调度复杂性的研究。随 着7 0 年代后期调度理论研究的深入及各种交叉学科的发展，又涌现出了许多新 的生产调度理论与方法。 2 2 生产调度问题的描述与分类 2 2 1 生产调度问题的描述 生产调度是在满足某些约束( 工艺路线、预定的完成时间、最早开始时间和 资源能力等) 的条件下对加工操作的排序。生产调度问题通常满足以下假设： ( 1 ) 工件数、机器数、工件在各台机器上的加工时间、工件加工的工艺技 术约束和加工路线是已知的。 ( 2 ) 一个工件在同一时刻仅能在一台机器上加工，一台机器同一时间仅能 加工一个工件。 ( 3 ) 所有工件的就绪时间都为o ，即在加工开始时，所有工件都具备加工 6 第2 章生产调度问题综述 条件。 ( 4 ) 加工过程次允许中断，一个工件一旦开始某工序加工，必须持续到该 工序加工完毕，不允许中间插入其它工件。 ( 5 ) 机器的调整时间包含在工件加工时间中，且与工件加工顺序无关。 ( 6 ) 机器是不会损坏的。 以上假设条件允许改变和放松，由此可构成不同类型的调度问题，满足以 上假设条件的生产调度问题称为基本调度问题卜”。 基本调度问题可以描述如下：甩个任务 ，。，j ：，以，要被加工，朋个机器 m ，m ：，m 。 可用，每一个任务要在这些机器或其中的一部分上加工，任务以 在机器鸩上的加工叫做一个操作( d f f ) ，它对应一个加工时间( 弓) ，每一个任务 还有与之相对应的就绪时间( r f ) ，即以可以进入加工的时间，还有交货期( d f f ) ， 即必须完成的期限，每一个任务还需要有一个工艺约束，它要求该任务按照一 定的工序要求在这些机器上加工，所以一个调度就是在一定时间内任务在机器 上的一个分派，调度问题就是寻找一个任务在机器之间的传送序列，它要满足 两个要求： ( 1 ) 符合工艺约束，即调度是可行的。 ( 2 ) 对应于某些执行目标调度是最优的。 生产调度问题主要集中在车间的计划与调度方面，许多学者作了大量研究， 出了不少的研究成果。制造系统的生产调度是针对一项可分解的工作( 如产品制 造) ，探讨在尽可能满足约束条件( 如交货期、工艺路线、资源情况) 的前提下， 通过下达生产指令，安排其组成部分( 操作) 使用哪些资源、其加工时间及加工的 先后顺序，以获得产品制造时间或成本的最优化。在理论研究中，生产调度问 题常被称为排序问题或资源分配问题。 生产调度中涉及的资源包括：原料、设备( 力工、存贮、运输) 、人力、资金、 能源等。资源的详细分配受到产品的生产工艺的限制。 影响调度问题的因素很多，正常情况下有：产品的投产期，交货期( 完成期) ， 生产能力，加工顺序，加工设备和原料的可用性，批量大小，加工路径，成本 限制等，这些都是所谓的约束条件。有些约束条件是必须要满足的，如交货期， 生产能力等，而有些达到一定的满意度即可，如生产成本等。这些约束在进行 调度时可以作为确定性因素考虑。而对于设备故障，原料供应变化，生产任务 变化等非正常情况，都是事先不能预见的，在进行调度时大都作为不确定性因 7 第2 章生产调度问题综述 素考虑。 生产调度的性能指标可以是成本最低、库存费用最少( 减少流动资金占用) 、 生产周期最短、生产切换最少、设备利用率最高、三废最少等。实际生产调度 的性能指标大致可以归结为三类： ( 1 ) 最大能力指标：包括最大生产率、最短的生产周期等，它们都可以归结 为在固定或者无限的产品需求下，最大化生产能力以提高经济效益。在假定存 在连续固定需求的前提下，工厂通过库存满足产品的需求，调度问题的主要目 标为提高生产设备的利用率、缩短产品的生产周期，使工厂生产能力最大，因 此，这类生产调度问题可以称为最大能力调度问题。 ( 2 ) 成本指标：包括最大利润、最小化运行费用、最小投资、最大收益等， 其中收益指产品销售收入，运行费用包括库存成本，生产成本和缺货损失。 ( 3 ) 客户满意度指标：包括最短的延迟，最小提前或者拖后惩罚等。 在传统的调度中，一般以平均流通时间最小、制造周期最短、满足交货期 为调度目标，而在实际生产中，由于提前完成的产品必须保存到交货期， 而拖期产品必须交付违约金，因此，在实际调度中经常考虑提前或者拖后惩罚。 车间调度问题的表示方法可以为三参数表示法p w ( 口卢r ) 。其中a 描述加 工环境中的机器状况；卢则表示加工性质与约束；而y 则表示优化的性能指标。 一般可以按照o f 和y 对车间生产调度问题进行分类。 在三参数表示法( 口) ，) 中，口表示加工环境中的机器状况，o f o f l o f ：，其 中p ，p ，q ，r ，g ，x ，0 ，j ，f 】。 若q o ，p ，q ，母，则每一个工件仅包含一个工序； 若q = 0 ，则每个工件必须在一个规定的机器上加工； 若 p ，q ，尺】- 则表示并行机加工环境。其中q p 表示相同并行机，即所 有机器具有相同的加工速度。q = q 表示均匀并行机，即所有机器加工速度不同， 但与各工件无关。砺= r 表示不相关并行机，即机器的加工速度取决于各个工件； e o ，j ，f 】则表示多工序类型，同时所有机器是专用性的，且各工序间存 在优先顺序。其中o f l = o 表示各工件可以不考虑自身的工艺顺序约束。儡* f 表 示f l o ws h o p 调度类型，一j 表示j o bs h o p 调度类型。 ； 展，殷，尼，反，孱，成】表示工件的加工特性。 屈用来表示加工方式，包括抢占式或非抢占式。抢占式加工工序在加工过 程中可以被打断，再在原机器或别的机器上重新开始；非抢占式工序则在加工 8 第2 章生产调度问题综述 开始后不能被打断。屈一p m t n 表示抢占式。 展表示工件间的加工优先关系，该优先关系可用非循环有向图表示，若该 有向图为任意非循环有向图，则展一p r e c ，若该有向图为树，则应一, t r e e 等。 岛表示工件的加工准备时间。若加工准备时间= 0 ，尼l l ，；。 反表示工序加工时间的限制，仍= p 表示每个工件的加工时间均为p ， p p i 歹表示每个工件的加工时间在( p ，歹) 之内。 屈表示交货期信息，若尾= 4 表示工件有交货期要求。 成表示批量信息，即工件是否成批联合进行加工。成= p b a t c h 表示批量 长度等于该批量中所有工件的加工时间的最大值，成= s b a t c h 表示批量长度等 于该批量中所有工件的加工时间之和。 y 表示加工性能指标。 车间调度常用的性能指标可分为三类： ( 1 ) 基于加工完成时间的指标： 最大完成时间c 蚴( m a k e s p a n ) ：一m a x c ) ，其中c ，表示工件j 在最 后一个机器上的完成时间； 最大流程时间：瓦。一m a x f _ f ，其中曩一c ：f 一，表示工件的开始加 j 工时间： 总流程时间孓e 以及平均流程时间三y 曩等等。 箭n 箭 ( 2 ) 基于交货期的性能指标： 拖后工件数( 完成时间大于交货期的工件个数) ； 最大推迟完成时间l ：一；m a x ( c f d f ) ，其中d ，表示工件j 的交货期； 最大拖后时间瓦“：一m a x i m a x ( o ，c j d r ) ) 。 总拖后时间罗瓦。 胃 ( 3 ) 基于库存的性能指标： 平均尚未完成的工件数冠。； 平均等待加工的工件数矾。 9 第2 章生产调度问题综述 2 2 2 生产调度问题分类 针对生产调度问题，g r a v e s 等人p 叫进行了分类整理，按照不同的分类标准， 可将其分为六种类型，这里主要介绍四种： ( 1 ) 按机器条件分类 单机问题( 口表示为1 ，下同) ，即由一台机器m 加i n 类工件；) 。甜。的一 类最简单的调度问题。这类问题是多机问题的一个特例，此类问题的理论已得 到广泛研究，成果较为丰富。 并行机问题有如下几类：p m 类，即有m 台相同的机器 m ；k 。，工件；k 。 包括一个操作，可以在任一机器或机器集合的子集上进行加工。q m 类与p m 类 差异之处在于各台机器加工同一工件的时间不同，即机器速度不同。r m 类是一 类更为一般的形式，机器的加工时间既取决于机器也取决于工件。 h o ws h o p 问题有如下两类：f m 类，即加工环境中有m 台机器 m ，k 。加 i n 种工件p 。k 湎，每个工件以有相同的加工顺序，但它们在各台机器上的加 工时间不同。f 类，即具有柔性加工路线的h o ws h o p 问题，同一工件的同一 个操作可以选择在多个并行机中的一个进行加工。 j o bs h o p 问题也可分为如下两类：砌类，即加工环境中有m 台机器 m ，) k 渤 加工以种工件弘k ；。，每个工件的加工顺序为预先给定且各不相同，加工时问 也各不相同，每个工件的每个操作仅有一台机器进行加工。f j c 类，即具有柔性 加工路线的j o bs h o p 问题，与j m 类不同之处在于每个工件的每个操作可以有多 个并行机机器进行加工。 ( 2 ) 按目标函数分类 按目标函数的多少可分为单目标问题与多目标问题。单目标问题如求取最 大完工时间问题c m 觚，最大拖期时间问题l 。；，加权完工时间问题m c ，等。 若目标函数有两个以上的，则称之为多目标调度问题。多目标调度问题很难求 得一个解使两个或多个目标函数同时最优，往往求得的是p a r e t o 意义下的最优 解，p a r e t o 最优解即是没有其他的解较p a r e t o 最优解同时使多个目标函数更优。 从求解方法上来看，多目标的问题通常通过加权，即以某个目标函数为主其他 目标函数为辅的方式将多目标问题转化为单目标问题进行求解。文献p 叫叫分别求 解了( c 。，c ) 以及( c m a x9 a r m 瓠) 问题，其求解思路是：首先通过确定两个目标的 权重将多目标问题转换为单目标问题，然后通过启发式算法获得排序。 ( 3 ) 按生产环境的分类 1 0 第2 章生产调度问题综述 按生产环境可将生产调度问题分为动态调度问题与静态调度问题p 。动态 调度问题即将生产过程中的扰动，如机器损坏，工件到期时间的改变，工件的 取消，有紧急工件的到达等考虑到问题中，使得问题假设更贴近实际。对于动 态调度问题往往要进行多次调度，文献p 叫中针对实际系统的运行状况，提出一 种实时的反馈调度策略，根据系统运行过程缓存中的工件数来实施在线调度。 当系统状态发生改变时就进行重调度的策略称为连续调度策略。但这样的调度 策略在线计算量较大，对于一个大的制造系统来说，系统变化较快而频繁，这 样的调度策略有可能使系统处于重调度状态。对于动态问题的另一种调度策略 是周期性调度策略，即每隔一段时间就进行一次重调度。周期性调度的缺点就 是响应突发事件较慢，导致系统性能下降。文献p 叫提出将两者结合的方法，即 周期性与事件驱动的调度策略。定义关键事件如机器故障等。当关键事件发生 时进行重调度，否则进行周期性调度。 而静态调度问题即是不考虑以上的扰动，仅考虑在机器约束与工序约束下， 调度开始时各个工件均到达，机器状态良好，只调度一次便确定各个工件的加 工顺序并且不再改变。求解静态问题则注重如何排序获得相应问题的最优解。 大量的文献设计各种不同的算法来研究静态问题。实际的生产调度类型往往是 j o bs h o p 型，且是动态的r “。 ( 4 ) 按加工过程的随机性分类 按加工过程的随机性可分为确定性调度问题与非确定性调度问题。确定性 调度问题即生产过程的参数，如工件的加工时间，到达时间，到期时间等，是 确定的，给出问题时这些量是具体的数值。而非确定性调度问题p ”1 中的生存过 程参数是随机的，但满足一定的概率分布，只有当工件加工完成后其自身的加 工参数才得以确定。当然其求解的目标函数也与确定性问题不同，非确定性问 题的目标函数往往是某些指标的期望或方差，即概率意义下的性能指标。 2 3 生产调度问题的特点 生产调度问题有以下特点： ( 1 ) 复杂性：车间中工件、机器、缓存和搬运系统之间相互影响、相互作用。 每个工件又要考虑它的加工时间、安装时间和操作顺序等因素，因而相当复杂。 调度问题是在等式或不等式约束下求指标的优化，在计算量上往往是n p 完全问 第2 章生产调度问题综述 题，随着问题规模的增大，其计算量急剧增加，使得一些常规的方法无能为力， 对于这一点己经证明了。即使对于单台机床加工问题，如果有行个工件而每个工 件只考虑加工时间以及与操作序列有关的安装时间，则这个问题就和厅个城市的 t s p 问题等价。对于一般加工系统，问题更复杂。 ( 2 ) 动态随机性：车间调度中有很多随机和不确定因素，如工件到达时间的 不确定性，实际工件的加工时间也有一定的随机性。而且系统中常有突发偶然 事件，如机器出故障、作业交货期的改变等。 ( 3 ) 多约束性：车间调度问题中资源的数量、缓存的容量、工件加工时间以 及工件的操作顺序等都是约束。此外还有一些人为的因素，如要求各机器上的 负荷要平衡等。 ( 4 ) 多目标性：调度的目标很多，而且这些目标之间往往是有冲突的。k i r a n 等人在文献 4 0 1 调度目标分为三类：基于作业交货期的目标、基于作业完成时间 的目标和基于生产成本的目标。 2 4 生产调度问题的优化方法 生产调度问题的研究最初集中在整数规划、仿真和简单的规则等方法上， 这些方法不是调度结果不理想，就是难以解决复杂的问题r “。近年来，在生产 调度领域出现了许多新的优化方法，比如神经网络法、模拟退火法、遗传算法、 微粒群算法等，使得生产调度问题的研究方法走向了多元化。对现有调度问题 的研究方法总结如下： ( 1 ) 数学规划方法 数学规划方法是一种运筹学方法，它将生产调度问题简化为数学规划模型， 采用分支定界、动态规划以及决策分析等方法来解决调度最优化或近似优化问 题，也称为优化调度方法。生产调度中广泛使用的是分支定界法。 分支定界法是一种求解最优调度序列的枚举算法。该算法首先建立对应优 化问题的数据结构即搜索树，并将优化问题的解空间分解为若干个子集；然后 估计各个子集的最优性能值，并去除那些不可能包含最优解的子集所对应的结 点；随后在符合要求的子集中反复执行“划分子集，估算最优，剔除子集”的步骤， 直到找到最优调度序列为止。从本质上说，该算法并不是一个多项式时间算法， 它没有克服问题求解中的计算复杂度问题。例如一个有2 0 台机器与2 0 个工件 1 2 第2 章生产调度问题综述 的j o b s h o p 问题中，该算法不能在有限的时间内求得最优调度序列。但仍可用 于求解小规模的最优调度问题。 文献【4 2 】提出了求解f l o w s h o p 问题的分支定界方法。这种方法基于即时选 取与优化矫正头尾操作的方法，使得求解问题的规模得以扩大。文献【4 3 】给出一 类自适应解j o b s h o p 问题的分支定界方法。所谓自适应是由于此类方法可以根 据问题规模的大小来设置合适的节点，并且在该方法中求解每一节点下界时将 下界收紧，这样减少了计算量。 数学规划方法的优点是任务分配和排序的全局性比较好，所有的选择同时 进行，因此可以保证求解凸和非凸问题的全局优化。但是，数学规划方法是一 种精确求解方法，它需要对调度问题进行统一的建模，任何参数的变化会使得 算法的重用性很差，因此，对于复杂多变的生产调度来说，单一的数学规划模 型不能覆盖所有的因素，存在求解空间大和计算困难等问题。 ( 2 ) 启发式搜索方法 启发式搜索方法最初是作为人工智能中问题求解程序的搜索器而被开发出 来的。启发式搜索方法依靠任务无关信息来简化搜索过程，在很多情况下，问 题求解可视为系统化地构造或查找解答的过程。启发式搜索方法主要有移动瓶 颈法、分派规则等 移动瓶颈方法是一种求解效率较好的启发式方法。a d a m s 等在文献【4 4 】中最 先提出移动瓶颈方法，具体说明了移动瓶颈方法的求解思路与过程，并用其求 解性能指标为c m 。，的j o bs h o p 问题。它是基于机器分解的思想，将j o bs h o p 问 题按机器分解，然后根据某一性能指标作为各台机器的性能参数，性能较差的 作为瓶颈机，优先进行调度。之后在去除已调度瓶颈机的机器集合中选取瓶颈 机进行调度，直到调度完所有的机器。在每次调度完瓶颈机后，要对已调度的 调度序列进行重新优化。文献 4 5 1 通过仿真验证了移动瓶颈算法求解j o bs h o p 的 结果优于分派规则，并且认为移动瓶颈算法求解结果的好坏一定程度上取决于 具体问题中工件的加工路线。 分派规则( d i s p a t c h i n gr u l e ) 是一类最简单的启发式方法，这些规则是人们 在生产中经验的总结，或是探索性的尝试。其具有如下的调度规则： ( i ) s p t ( s h o r t e s t p r o c e s s i n gt i m e ) 规则：此规则是选取当前未加工的工 件中加工时间最短的工件进行加工，并且在下一次加工时仍选取加工时间最短 的工件进行加工，如此反复直到所有工件都被加工。s f r 规则期望待加工工件的 1 3 第2 章生产调度问题综述 等待时间较小。 ( i i ) u y r ( l o n g e s tp r o c e s s i n gt i m e ) 规则：这个规则与最短加工时间规则 相反，在每次选取工件时都选取需要加工时间最长的工件进行加工。 ( ) e d d 规则：选取所有工件中交货期最早的工件进行加工。 ( i v ) f r o 规则：选取具有最少剩余加工时间的工件进行加工。 ( v ) f i f o 规则：对所有进入待加工队列的工件，选取先到的工件进行加 工。 ( v i ) r a n d o m 规则：随机地选