（计算机应用技术专业论文）基于动态关键路径的复杂产品制造调度研究.pdf

哈尔滨理r 丁大学工学硕士学位论文 基于动态关键路径的复杂产品制造调度研究 摘要 当前生产调度问题的研究主要是解决工件间无约束的简单产品的车间调度 问题，没有考虑工件间存在约束关系的复杂产品的情况。事实上，在许多调度 中是存在着工件之间的工艺约束的。因此在进行生产调度计划时，如果忽略了 工件间的约束关系，所得到的生产计划将是不可行的。因此，本文研究的复杂 产品调度具有重要的理论和实际意义。 针对已有的关于复杂产品拟关键路径调度算法，没有考虑产品关键路径长 度随调度变化影响调度效果的问题，本文提出了一种基于动态关键路径的调度 算法。对于复杂单产品问题，首先根据产品的加工流程为产品建立一个加工工 艺树，其中树的叶子节点代表最先加工的工序，根节点代表最后一道工序，边 代表工序加工次序的偏序关系。在调度过程中，算法根据加工工艺树动态生成 备选的工序集合，结合调度策略从备选集中选择工序，并应用最佳适应调度法 调度工序，直到备选集合为空，即所有工序加工完毕。 在单产品研究的基础上，提出了一种解决复杂多产品调度问题的方法，将 多个产品转化成一个虚拟的产品，构造一个产品的虚拟加工工艺树，然后利用 处理单产品的方法来解决多产品问题。 对于具有相同设备的调度问题，由于相同设备的存在，扩大了设备选择范 围，增加了问题解决的难度。针对这种复杂的组合优化问题，结合动态关键路 径和复杂多产品调度算法，提出了设备选择策略，将调度工序的选择与工序所 用设备的选择分开进行处理，实现具有相同设备的复杂多产品调度优化。 最后，用v i s u a lc + + 6 0 开发了算法的生产调度仿真软件。 关键词复杂产品：调度；虚拟加工工艺树；动态关键路径；备选工序集 哈尔滨理工大学工学硕上学位论文 r e s e a r c ho nc o m p l e xp r o d u c tm a n u f a c t u r es c h e d u l i n g b a s e do nd y n a m i cc r i t i c a lp a t h a b s t r a c t m o s to ft h ec u r r e n tr e s e a r c ho np r o d u c t i o ns c h e d u l i n gp r o b l e mc a l lo n l ys o l v e t h es i m p l ep r o d u c ts c h e d u l i n gp r o b l e m 埘t hn o n r e s t r a i n ta m o n gj o b s ，a n dw i t h o u t c o n s i d e r i n g t h e c o m p l e xp r o d u c ts c h e d u l i n gp r o b l e m w h i c hh a sc o n s t r a i n t r e l a t i o n s h i pa m o n gj o b s b u ti nf a c t , t h e r ee x i s tc o n s t r a i n tr e l a t i o n s h i pa m o n gj o b si n m a n ys c h e d u l i n g s oi fw ed o n tc o n s i d e rt h ec o n s t r a i n tr e l a t i o n s h i pa m o n gj o b s d u r i n gm a k i n gt h ep r o d u c t i o ns c h e d u l i n gp l a n ，t h ep l a ni sn o tf e a s i b l e s ot h e s c h e d u l i n gp r o b l e mo fc o m p l e xp r o d u c t s t u d i e di n t h i sp a p e rh a s i m p o r t a n t t h e o r e t i c a la n dp r a c t i c a ls i g n i f i c a n c e i nv i e wo fa l l i e dc r i t i c a lp a t hm e t h o do fc o m p l e xp r o d u c ts c h e d u l i n ga l g o r i t h m h a v eb e e np r o p o s e d ，w i t h o u tc o n s i d e r i n gt h ep r o b l e mo ft h ec r i t i c a lp a t hl e n g t ho f t h ep r o d u c tt a k ec h a n g e 、i t l ls c h e d u l i n gi m p a c t st h ee f f e c to ft h es c h e d u l i n g ，a s c h e d u l i n ga l g o r i t h mb a s e do nd y n a m i cc r i t i c a lp a t hi sp r e s e n t e d f o rt h es c h e d u l i n g p r o b l e mo fc o m p l e xs i n g l ep r o d u c t ，a c c o r d i n gt ot h ep r o c e s s i n gf l o wo f t h ep r o d u c t b u i l d sa p r o c e s s i n go p e r a t i o n t r e ef o r t h ep r o d u c t t h el e a fn o d e so ft h et r e e d e l e g a t e st h eo p e r a t i o nf i r s ts c h e d u l e d ，t h er o o tn o d ed e l e g a t e st h el a s to n e ，a n dt h e l i n e sd e l e g a t et h eo r d e ro fo p e r a t i o np a r t i a lr e l a t i o n s d u r i n gt h es c h e d u l i n ga n o p e r a t i o nc o l l e c t i o ni sd y n a m i c a l l yg e n e r a t e da c c o r d i n gt ot h ep r o c e s s i n go p e r a t i o n t r e e t h e no p e r a t i o na r es e l e c t e df r o mt h es t a n d b yo p e r a t i o ns e tw i t hd y n a m i c c r i t i c a lp a t hs t r a t e g ya n ds h o r t - t i m es t r a t e g y , a n ds c h e d u l e di tw i t hb e s tf i ts c h e d u l i n g m e t h o du n t i lt h es e ti se m p t y , t h a tm e a n sa l lo p e r a t i o n sh a v eb e e np r o c e s s e d a f t e rt h er e s e a r c ho ft h es i n g l e p r o d u c t ，ac o m p l e xm u l t i p r o d u c ts c h e d u l i n g p r o b l e ma l g o r i t h mi sp u tf o r w a r d t h ea l g o r i t h mt r a n s f o r m sm u l t i p r o d u c t i n t oa v i r t u a lp r o d u c t ，a n dc o n s t r u c t sav i r t u a lp r o c e s s i n go p e r a t i o nt r e e t h e ns o l v et h e m u l t i - p r o d u c ts c h e d u l i n gp r o b l e mb yu s i n gs i n g l e - p r o d u c tw a y - 哈尔滨理工大学工学硕士学位论文 s i n c et h ee x i s t e n c eo ft h es a m e - f u n c t i o ne q u i p m e n t ，w h i c he x p a n d st h ec h o i c e o ft h ee q u i p m e n t , a n di n c r e a s e st h ed i f f i c u l t yo ft h es o l v i n gt h ep r o b l e m i nv i e wo f t h i sc o m p l e xc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m ，a ne q u i p m e n ts e l e c t i o ns t r a t e g yi s p u tf o r w a r d t h es e l e c t i o no fs c h e d u l i n go p e r a t i o na n dt h ee q u i p m e n tu s e db y o p e r a t i o nw i l lb es e p a r a t e dt ot r e a tc o m b i n e dw i t hd y n a m i cc r i t i c a lp a t ha n dc o m p l e x m u l t i p r o d u c ts c h e d u l i n ga l g o r i t h m ，w h i c ha c h i e v e st h es c h e d u l i n go p t i m i z a t i o no f c o m p l e xm u l t i p r o d u c tw i t ht h es a m e f u n c t i o ne q u i p m e n t f i n a l l y , as c h e d u l i n ge m u l a t o rs o f t w a r ei sd e v e l o p e du s i n gv i s u a lc + + 6 0 k e y w o r d sc o m p l e xp r o d u c t ，s c h e d u l i n g ，v i r t u a lp r o c e s s i n go p e r a t i o nt r e e ，d y n a m i c c r i t i c a lp a t h ，s t a n d b yo p e r a t i o ns e t i l l - 哈尔滨理工大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文基于动态关键路径的复杂产 品制造调度研究，是本人在导师指导下，在哈尔滨理工大学攻读硕士学位期 间独立进行研究工作所取得的成果。据本人所知，论文中除已注明部分外不包 含他人已发表或撰写过的研究成果。对本文研究工作做出贡献的个人和集体， 均已在文中以明确方式注明。本声明的法律结果将完全由本人承担。 作者签名：l 刽噢 日期： 2 0 0 9 年3 月2 d 日 哈尔滨理工大学硕士学位论文使用授权书 基于动态关键路径的复杂产品制造调度研究系本人在哈尔滨理工大学 攻读硕士学位期间在导师指导下完成的硕士学位论文。本论文的研究成果归哈 尔滨理工大学所有，本论文的研究内容不得以其它单位的名义发表。本人完全 了解哈尔滨理工大学关于保存、使用学位论文的规定，同意学校保留并向有关 部门提交论文和电子版本，允许论文被查阅和借阅。本人授权哈尔滨理工大学 可以采用影印、缩印或其他复制手段保存论文，可以公布论文的全部或部分内 容。 本学位论文属于 保密口，在年解密后适用授权书。 不保密团。 ( 请在以上相应方框内打4 ) 作者签名：f 割隽 日期： 2 0 0 9 年弓月z p 日 剔噬轹舡叫弓 醐：2 0 0 9g jf l 伽日 哈尔滨理t 大学工学硕士学位论文 第1 章绪论 1 1 课题研究的目的和意义 调度( s c h e d u l i n g ) 问题最初产生于机器的制造安排，但后来被广泛应用 于计算机系统、运输调度、生产管理领域。从普通的生产部门的计划安排、人 员调度，学校课程表的制定，到宇宙飞船的复杂庞大的飞行计划，都要用到调 度的理论和算法。有关资料表明，制造过程9 5 的时间消耗在非切削过程中， 因此制造过程的调度技术，将在很大程度上影响制造的成本和效率。而在以往 的生产管理中，企业仅仅是依靠个人的经验来完成，在规模很小的时候可以起 到一定的作用。不过随着生产规模的急剧扩大，各种情况的突然发生，使得这 种模式对这些情况的处理存在着很大的局限性，距离现代企业生产管理的标准 有很大的差距，而这将导致企业在生产全球竞争的环境下处于十分不利的被动 地位。虽然不少企业在企业管理上引入学习了e r p 管理软件，可是在具体的 生产中却没有相应的技术。因此有效的合理的调度方法与优化技术的研究，对 于先进制造企业的现代化具有重要的意义。 加工和装配是产品制造过程中最主要的蕊个任务，这两个任务调度安排的 效果对产品生产有着很大的影响。加工和装配任务调度算法的研究是当前调度 理论中所研究的重要问题之一，对它们的研究不仅可以促使调度问题研究的发 展，更可使企业在相同的技术条件下，制定出产品加工和装配计划的更为合理 的安排，从而减少人们的繁杂劳动，合理优化地组织生产，缩短生产周期，降 低成本，提高生产效率，提高产品竞争力，获得更多的利润，为企业带来更好 的经济效益。 目前对加工和装配调度理论算法的研究主要作为两个部分分开来研究：一 类是加工调度优化研究，另一类是装配调度优化研究。加工调度优化主要解决 的产品加工问题，即每个工件由一串工序加工而成，且工件间无约束的纯加工 问题，属于简单产品加工调度优化问题，也就是所谓的车间调度问题；装配调 度优化研究解决的是产品的装配问题，即工件间的具有约束的装配问题，属于 装配调度问题。但是在很多行业的制造生产中，产品的加工和装配是并不是完 全独立分开的：有的产品加工完毕之后需要继续装配：有的产品装配之后需要 继续加工。因此若将加工与装配分开来进行研究具有一定的局限性，需要将其 哈尔滨理工大学工学硕士学位论文 结合起来研究，即研究同时存在着加工与装配的复杂产品的调度问题。复杂产 品制造的特点是工件加工、工件与工件装配以及装配以后成为新工件再加工， 形成工件间有约束的加工、装配，直到产品制造完成。 随着生产制造的进一步发展和进步，制造过程逐步由无约束的简单产品的 制造转变为工件间有约束加工、装配，复杂产品制造。此时如果还是分别考虑 加工调度与装配调度，那么这种割裂产品制造过程中的联系的算法必然会破坏 可能存在的并行关系，即本可以优化为并行进行的工序不能并行进行，从而延 长了制造的时间，降低了生产的效率。因此积极地进行工件间存在约束关系的 复杂产品调度优化研究，进行复杂产品加工和装配的优化调度研究不仅有理论 意义，还具有广泛的应用领域和实用价值。 1 2 国内外研究现状及分析 近年来，车间作业调度问题的研究向更实用的方向发展，主要表现在以下 面几个方面： 1 多目标调度实际调度问题往往属于多目标优化问题，不同的部门之间 希望调度能够带来的目标各不相同：有的希望缩短生产周期，有的希望最大的 生产利润，有的希望节省原料，而这些目标往往相互冲突的。所以研究如何获 得多种目标在调度中日益变得重要。基于直接根据问题的性质和结构求出部分 以至全部非劣解这种思想，m u r r a 等提出了多目标的遗传算法。鞠全勇，朱 剑英提出了批量生产优化调度策略，建立多目标优化调度模型，结合多种群粒 子群搜索与遗传算法的优点提出具有倾向性粒子群搜索的多种群混合算法昭1 ， 提高了搜索效率和搜索质量。 2 动态调度由于生产会受到各种因素的影响，因此实际的生产调度过程 是一个动态过程，调度算法必须对的情况的发生作出动态响应改变。考虑到周 期再调度策略不能及时响应突发事件，而事件驱动再调度策略对未来事件缺乏 预见性，c h u r c h 和u z s o y 提出了周期和事件驱动的混合策略，即当有突发事件 发生时立即进行调度，其它时间每隔一个固定周期进行再调度。谢志强提出了 基于优先级结合几种调度策略的动态调度方法啼1 ，可以获得比较好的解。 3 多资源调度车间的生产能力不但要受到机床的制约，而且会受到工人 和辅助加工设备的制约。t r e l e v e n 和e l v e r s 研究了受工人和机床限制的调度问 题，分析了工人与设备机床之间的比例问题。他们认为当工人与机床设备的比 率在5 0 7 5 之间时，生产调度效率最高。陈希等提出了将遗传算法与启发 哈尔滨理工大学工学硕士学位论文 式调度规则相结合，提出了工艺路线可变的双资源双目标车间调度优化h 1 。 4 人机交互调度为了考虑实际调度中存在的各种复杂因素及调度的多目 标性，以取得好的调度结果，往往需要好的人机交互策略与手段去利用和启发 调度决策者的经验知识。张晴提出了人机交互的j o b s h o p 车间动态调度方 法，指出对于离散事件的j o b s h o p 调度，采用人机交互与仿真相结合的方 法，描述了调度过程中人的行为模型，建立了一种人机交互的车间调度系统框 架结构，并探讨了适用于该框架结构的动态调度机制啼1 。 5 模糊调度受多种因素的影响，零件的加工时间和交货期并不是非常准 确的数值，这些不确定性可以用模糊数表达。m u r a t a 等研究了具有模糊交货期 的流水车间调度问题。耿兆强，邹益仁在遗传算法适应度评估中，引入了模糊 数和相应的模糊算子及模糊数比较方法从而有效地解决了作业车间模糊调度问 题。 1 3 课题来源及本文主要内容 1 3 1 课题来源 黑龙江省自然科学基金( n o f 2 0 0 6 0 8 ) ；黑龙江省教育厅重大科技项目 ( n o 1 0 5 1 l z 0 0 0 8 ) ：哈尔滨市科技攻关项目( n o 2 0 0 5 a a i c g 0 6 1 1 1 ) ；黑龙江 省教育厅海外学人重点科研资助项目( n o 1 1 5 2 h q 0 8 ) 。 1 3 2 本文研究的主要内容 对于调度问题，已经有很多算法被开发出来。本课题研究的目的是对现有 的用于求解调度问题的方法所存在问题进行分析，提出了一种新的复杂产品调 度算法。该算法根据调度过程中全局变化的动态性，并结合工序和设备资源的 特点对不同类型的工序采用不同的优化策略。 本文主要研究以下几项内容： 1 复杂单产品调度问题通过对复杂单产品调度问题进行建模，针对复杂 单产品调度问题制定调度策略，对产品工序进行调度。 2 复杂多产品调度问题通过对多产品进行建模，将多个产品对应的加工 树构造成为一棵虚拟加工树，从而简化复杂多产品调度问题。 3 具有相同设备的复杂多产品调度问题在多产品调度的基础上根据相同 哈尔滨理t 大学工学硕十学位论文 设备的特点，提出一个相同设备选择策略进行设备的选择，从而简化具有相同 设备的多产品调度问题。 1 4 论文结构 第1 章介绍了本课题研究的目的和意义，国内外研究现状，课题来源及论 文主要研究内容。 第2 章介绍了车间作业调度问题的含义、特点及分类，然后给出了现有的 求解车间作业调度问题的方法，最后阐述了车间作业调度存在的问题及其发展 趋势。 第3 章对复杂单产品调度问题进行了分析，并且提出了两种调度策略结合 最佳适应调度法来调度工序。因为单产品调度问题具有一般调度问题的性质， 所以这两种调度策略可以作为研究更一般的调度问题的基础。 第4 章在前一章的基础上提出了一种通过将多个产品虚拟成一个单产品的 调度问题算法，并通过实例进行比较。 第5 章在前两章研究的基础上提出了一个完整的算法来解决具有相同设备 的调度问题并通过实例进行比较。 第6 章介绍了算法的仿真试验软件的设计结构，以及软件的使用方法。 最后对本文进行了总结，并对进一步的研究做出了展望。 哈尔滨理工大学工学硕 二学位论文 第2 章调度问题概述 2 1 调度问题的含义 1 9 5 4 年，j o h n s o n 研究了两台机床的流水车间调度问题。这标志着调度理 论研究的开始。一般的说，调度问题就是如何将有限的机器资源分配给在一定 时间内的不同生产任务从而来达到某种优化，在时间、空间上合理配置系统的 有限资源，以满足特定目标。调度是一个决策过程，在制造和生产系统中扮演 着重要的角色。典型的调度问题包括工件的加工与工件的装配。工件的加工和 装配包含一个工序的集合，每道工序需要占用加工设备或者装配设备等资源， 并且这些工序之间存在着前后约束顺序，按照一定的工艺流程路线进行加工。 调度研究的目的就是在满足一定的约束条件下，为工件合理的分配设备，科学 的安排加工时间，使某些目标达到最优。 2 2 调度问题一般性描述 2 2 1 调度问题的分类 调度问题是一类重要的组合最优化问题，调度问题的分类方法很多，主要 从以下几个方面来分类： 1 根据加工系统的复杂度可分为单机、多台并行机、f l o w - s h o p 和j o b s h o p 。单机调度问题是最简单的调度问题，所有的操作任务都在单台机器上完 成；多台并行机的调度问题更复杂，因而优化问题更突出：f l o w s h o p 型问题 的加工操作和加工顺序相同；j o b s h o p 是最一般最复杂的调度类型，他不限制 作业的操作的加工设备，因此可以有不同的加工顺序。 2 根据性能指标分为基于调度费用和调度性能的指标两大类。对于调度 问题来说，不同的调度算法希望达到的效果并不完全相同：有的出于各种费用 支出的优化，减少开支；有的则是希望调度的性能提高，缩短生产所需的周转 时间。 3 根据生产环境的特点可将调度问题分为确定性调度和随机性调度问 题。对于某些生产来说，其调度问题的各种因素流程是调度之前完全确定的， 哈尔滨理工大学工学硕士学位论文 不会发生改变。而对于某些生产来说，其调度过程存在这各种不稳定的随机的 因素，调度需要实时进行改变。 4 根据作业的加工特点可将调度问题分为静态调度和动态调度。静态调 度是指所有待安排加工的工作均处于待加工状态，因而进行一次调度后、各作 业的加工被确定、在以后的加工过程中就不再改变；动态调度是指作业依次进 入待加工状态、各种作业不断进入系统接受加工、同时完成加工的作业又不断 离开，还要考虑作业环境中不断出现的动态扰动、如作业的加工超时、设备的 损坏等。因此动态调度要根据系统中作业、设备等的状况，不断地进行调度。 2 2 2 调度问题的特点 实际调度问题主要有一下几个特点： 1 计算的复杂性调度中工件、机器、操作人员和搬运系统之间相互影 响、相互制约。每个工件又要考虑它的加工时间、安装时间和操作顺序等因 素，因而加工环境相当复杂。调度问题已经被证明具有n p h a r d 的特性，是一 个十分复杂的组合优化问题，他随着调度规模的增大，问题可行解的数量呈指 数级增加，因而求解非常困难。因此对于那些一般的常规调度算法要求解出一 个最优解是比较困难甚至无能为力的。 2 动态随机性实际的加工环境是不断变化着的，存在这很多不确定和随 机的因素，如机器设备的损坏，原料送达时间的延迟，订单的取消等等。因 此，调度过程是一个动态的随机的过程。 3 多约束性一般情况下，调度过场不仅受着工艺路线的约束，同时，他 还受到各种资源设备的约束，如加工机床、装配设备、运输设备等。 4 多目标性实际的车间调度问题性能指标有很多，例如生产周期、加工 费用、平均流通时间、平均延误率、设备利用率、换线成本等，而且这些目标 之间往往有可能会发生冲突。因为这种多目标的存在，使得调度的复杂性急剧 扩大。因此还没有出现一个通用的实用调度系统出现。 5 离散性车间生产系统是一个典型的离散系统，工件的加工发生在不同 的时间和资源上，并且任务的到达、订单的更改、设备的添加和故障等都是离 散事件。这样，就可以用数学规划、离散系统建模与仿真的方式，通过排序理 论研究车间调度问题。 哈尔滨理工大学工学硕上学位论文 2 2 3 调度指标 调度指标是评价调度算法优秀与否的标准。在实际生产调度中的调度评价 指标有以下几种： 1 性能指标 包括：生产周期、平均流动时间、机床利用率、工人利用率等，其实质是 最大化生产能力以提高经济效益。 2 成本指标 包括：加工成本( 包括工人工资、原料成本、场地费用等) 、换线成本、 延期违约罚款和废品率等。 3 客户满意度指标 包括：货物延期时间、提前的时间和延期工件的数量等。生产的实质是满 足客户的需要，客户的满意是企业追求的目标，所以在实际的调度中，追求平 均流通时间最小、制造周期最短、满足交货期作为调度目标。 2 3 研究方法 自5 0 年代初期开始，各领域的学者就投身调度问题的研究。1 9 5 4 年， j o h n s o n 对两台机床的f l o ws h o p 型调度问题进行研究，提出了解决n 2 c m 瓤和 部分特殊的n 3 f c m 戤问题的有效的优化算法，标志着调度理论研究的开始。 自此以后，学术界对调度问题的更广泛和更进一步的探讨研究，取得了大量的 丰硕的成果。但同时，人们发现，由于对这些调度理论对现实情况设定了很多 假设，很难用于生产实践中。在6 0 年代中期，人们发现证明了调度都是n p 难问题，对于这类问题，并不存在有效的多项式求解方法，因此开始寻找有效 的近似方法来解决它们1 。于是，大量的近似优化方法被提出来，如基于优先 规则的方法、基于瓶颈的启发式方法、遗传算法、模拟退火算法、禁忌搜索算 法、阀值接受算法、人工神经网络、专家系统、蚁群系统等等陋1 引。 1 运筹学方法运筹学方法是将生产调度问题简化为数学规划模型，采用 基于枚举思想的分枝定界法或动态规划算法进行解决调度最优化或近优化问 题，属于精确方法n 制。有关不同的分枝定界法，其不同点主要在于分析规则、 定界机制和上界的产生这三方面存在差异刮。这类方法虽然从理论上能求得 最优解，但由于其计算复杂性的原因、因而不能获得真正的实用。 2 数学方法数学规划法在车间调度中被广泛的采用。从数学规划的角 哈尔滨理工大学工学硕士学位论文 度，车间调度问题可以归结为在等式约束或者不等式约束下，对一个或者多个 目标函数进行优化。数学规划方法将车间调度问题简化为数学规划模型，采用 整数规划、动态规划以及决策分析等方法来解决调度最优化或近似最优化问 题。车间调度中广泛使用混合整数线性规划和混合整数非线性规划方法n 卜埔，。 但是，数学规划方法是一种精确求解方法，它需要对调度问题进行统一的建 模，任何参数的变化会使得算法的重用性很差。 3 分派规则法最早的分派规则由j a c k s o n 和s m i t h 等提出，j s s p 的分配 规则有s p t ( 最短加工时间) 、l p t ( 最长加工时间) 、m w r ( 剩余总加工时 间最长) 、l w r ( 剩余总加工时间最小) 、m o r ( 剩余工序数最多) 、l o r ( 剩 余工序数最小) 、e d d ( 最早交货期) 和f c f s ( 选择同一机器上工件队列中的 第一道工序) 等n 蚴1 。p a n - w a l k a r 等通过性能指标对1 1 3 个分派规则归类总 结，w u 把调度规则分为三大类，即同作业信息相关的优先级规则、优先级规 则的组合和切换以及加权规则。优先分派规则的近似优化方法，关键在于如何 针对给定问题的性能，选择最好的规则幢。从各规则的优化效果看，s p t 能够 减小所有作业的平均流程时间，e d d 用于优化最大延期相关的目标。对规则 之间的切换及由此产生的问题( 如出错修复) 是近期活跃的研究领域。 4 演化规划演化规划是本世纪6 0 年代提出的。主要用于数据诊断、模 式识别和分类以及控制系统的设计之中，并取得了良好的效果。后来，借助于 演化策略方法对演化规划进行了发展，并用到数值优化和神经网络训练等问题 之中。 5 基于离散事件动态系统的解析模型方法离散事件动态系统是指由离散 事件按照一定的运行规则，相互作用而导致系统状态演化的一类动态系统。离 散事件驱动状态的演化，而状态演化又导致新的事件的出现。这种离散事件的 错综复杂的相互作用，构成了系统的动态特性，此类动态特性难以用传统的微 分方程或差分方程来描述。在制造系统中存在着大量的离散事件过程，它们无 法由物理和其它自然科学的定律描述，而是服从于人为的一些复杂规则，这些 离散事件的相互作用构成了系统的演化过程。 6 启发式图搜索法对于表述为整数规划的调度问题，最初采用分枝定界 法来解决，而后其他的启发式图搜索法也被应用于解决调度问题：b a l a s 将调 度排序问题用一个d i s j u n c t i v e 图来表示，首先构造一个可行解，采用基于枚举 的搜索方法不断提高解的次优性；采用束搜索法( b e a ms e a r c h ) 来识别瓶颈机 器，进行调度；为了解决搜索空间太大的问题，通过对分枝定界法和束搜索法 进行系统的分析，提出了一种过滤束搜索法( f i l t e rb e a ms e a r c h ) ，用来解决单 哈尔滨理工大学工学硕一l 学位论文 台机器提前延期问题和加权延期的f l o w s h o p 问题：研究了基于a 宰的优先 树搜索法的优化作业排序问题幢引：针对基于树搜索的优先a 牛算法需要大量内 存的问题，提出了一个图搜索法，并对两种方法作了比较；为解决j o b s h o p 调度问题对a 幸算法作了两点改进：1 ) 在搜索过程中只展开有限节点；2 ) 采用加权的评价函数。对于图搜索算法，如何提高搜索效率并减少内存使用以 解决规模较大的问题，还需要进一步探索。 7 神经网络方法h o p f i e l d 神经网络模型的提出为求解各种有约束优化问 题开辟了一条新途径幢3 刊，用h o p f i e l d 网络解决t s p 问题就是其在组合优化问 题中的最成功的应用之一。它的主要思路是：通过一个l y a p l m o v 能量函数构 造网络的极值，当网络迭代收敛时，能量函数达到极小，使与能量函数对应的 目标函数得到优化。已实现用一种随机h o p f i e l d 网络解决j o b s h o p 调度问 题；为了解决大规模问题，又提出一种改进的h o p f i e l d 网络的整数线性规划神 经网络方法来解决j o b s h o p 调度问题，提出了一种用于解决j o b s h o p 调度问 题的神经网络方法。 8 人工智能的调度方法人工智能的方法包括：基于专家系统的、基于智 能搜索算法的和基于m u l t i a g e n t 的方法。它利用模型和知识库，通过模拟、推 理等手段产生一个更符合实际的调度决策，以弥补人类调度专家的不足，具有 一定的智能性。这种方法的缺点是：在解决问题域范围的大小方面受到限制， 而且，收集人类的知识和经验以及认知过程的建模是很困难的1 。 9 邻域搜索算法( l o c a ls e a r c hm e t h o d ) 邻域搜索算法的原理是以优化问 题的一个初始可行解作为当前解，通过预先设置解的邻域结构，在当前解的邻 域内搜索比当前解更好的邻域解，并以此作为新的当前解，重复上述移动，直 到搜索到全局最优解也h 。 邻域搜索算法一般包括模拟退火算法、禁忌搜索算法、遗传算法、阀值接 受算法等等。 模拟退火：模拟退火是基于m e n t ec a r l o 迭代求解的一种全局概率型搜索 算法，是一种串行优化算法乜引。其收敛性要求初温应足够高，使解空间各状态 能以几乎相同的概率出现。v a nl a a r h o o v e n 等提出对于j s s p 问题，邻域函数 的重要标志是相邻关键操作工序处理顺序的改变，且必须服从在同一机器上处 理的工序条件。k o l o n k o 证明标准的j s s p 的邻域具有非对称性，且由于模拟 退火的弱收敛性，张朝勇等提出了在它的基础上结合g a 的混合启发式啪1 。 禁忌搜索法：禁忌搜索法是模拟智能过程的一种具有记忆功能的全局逐步 优化算法，对变动的排序在其可行解的所有空间中进行搜寻m 1 。通过设置禁忌 哈尔滨理工大学丁学硕士学位论文 表，避免陷入局部最优或重复过去的搜索，利用中、长期的存储机制进行强化 和多样化搜索，对j s s p 问题l a g u n a 等提出三个基于简单移动的禁忌搜索法排 序策略。文献提出了一种遗传禁忌混合算法求解j o b s h o p 调度问题，应用遗 传算法探索j o b s h o p 调度问题的整个解空间，禁忌搜索算法充当遗传算法中 的变异算子，完成对某个解领域进行寻优以提高算法整体寻优性能。 遗传算法：遗传算法是h o l l a n d 基于自然遗传进化的绝对模型提出的并行 搜索机制，遗传算法的5 个要素是编码、适应值函数、初始种群、遗传算子和 参数设置m 1 。由于对j s s p 问题要考虑工序的前后约束和非堵塞约束，使得染 色体的编码表示非常重要。如果编码不当，会在遗传算子操作时产生不可行 解，失去了交叉或变异算子的有效性。c h e n g 等把编码表示分为两类共9 种， 分别是直接的方法( 基于工序、基于工件、基于工件对关系、基于完成时间和 基于随机键表示法) 和间接的方法( 基于优先规则、基于优先表、基于非连接 图和基于机器的表示法) 。d a v i s 首先基于优先表的间接编码表示求解j s s p ， f a l k e n a u e r 等则利用把工序编码为字符串的方法。王凌等对近年来基于遗传算 法的j o b s h o p 研究进行了较全面综述，并讨论了进一步研究的若干方向。 变邻域搜索法：变邻域方法是由h a n s e n 等人于2 0 0 1 年提出的一种超启发 式算法m 1 ，它区别于传统方法的单一邻域结构，首先定义一系列邻域结构，并 在搜索过程中系统性地不断改变邻域搜索范围，直到有新的更好的解产生。变 邻域搜索法的具体步骤见文献3 3 。 1 0 人工蚁群算法人工蚁群算法* 矧具有很强的发现较好解的能力，通过 模拟自然界中蚁群觅食行为和觅食策略来求解组合优化问题。由于算法本身采 用了正反馈原理，加快了进化过程，且不易陷入局部最优解；人工蚁群算法具 有很强的并行性，个体之间不断进行信息交流和传递，有利于发现较好解，单 个个体容易收敛于局部最优，多个个体通过合作，可以很快收敛于解空间的某 一子集，有利于对解空间的进一步探索，从而发现较好解3 引。其存在的问题 是该算法本身很复杂，一般需要较长的搜索时间；容易出现停滞现象，即搜索 进行到一定程度后，所有个体所发现的解完全一致，不能对解空间进一步进行 搜索，不利于发现更好的解。 1 1 系统仿真的方法基于仿真的方法不单纯追求系统的数学模型，侧重 对系统中运行的逻辑关系的描述，能够对生产调度方案进行比较评价，分析系 统的动态性能，并选择系统的动态结构参数。由于制造系统的复杂性，很难用 一个精确的解析模型来进行描述和分析。而通过运行仿真模型来收集数据，则 能对实际系统进行性能、状态等方面的分析，从而，能对系统采用合适的控制 哈尔滨理- t 大学工学硕上学位论文 调度方法。但仿真方法的生产调度费用比较高，对仿真模型、编程人员的技 术、试验数据等依赖性较高，且又由于其仿真实验性的特性，很难产生出理论 性的成果。 1 2 数据挖掘技术数据挖掘技术是一种从大量数据中自动或者半自动地 发现知识的方法。用以辅助人们进行科学有效的决策，已成功应用于金融、销 售数据库、搜索引擎等领域。不过目前国内外在这方面的研究却刚刚开始起 步。2 0 0 2 年，华中科技大学的研究人员首次将数据挖掘技术应用于流程工业 生产调度中，并在论文中分析了生产调度与数据挖掘两者相结合的可行性啪1 。 2 4 j o b s h o p 调度问题中的基本概念 调度问题的主要概念有以下几种： 1 生产周期( m a k e s p a n ) 生产周期是调度开始时间与终止时间之间的间 隔。一个调度的生产周期就是该调度中所有作业的最大完成时间，即 m a k e s p a n = m a x ( 另) ，i - 1 ，2 ，m ，c i 为作业f 的完成时间，生产周期代表资源利用 率。较短生产周期意味着较高资源利用率，常作为作业调度优化目标。 2 关键路径( c r i t i c a lp a t h ) 关键路径就是最重要的路径，其对全部工程 完工所需时间影响最大。 3 甘特图( g a n t tc h a r t ) 甘特图利用长条图来显示所有任务，将任务画在 表上，并显示开始日期与完成日期以及持续时间。 2 5 调度问题中的主要模型 2 5 1 代数建模方法 用纯代数的形式来描述调度对象可称之为调度对象的代数建模，常用很多 等式和不等式来表示，此时对应的调度问题就可以描述成一个数学优化问题。 代数建模方法是最为传统的一类建模方法，这类建模方法数学含义非常明确， 适合用经典的数学规划方法来求解对应的调度问题，而且由于这种建模方法比 较常用，当前的很多智能调度算法也是在这种模型上提出的。当前针对调度对 象的几类经典代数建模方法包括混合整数约束，极大极小代数阳训等。 哈尔滨理工大学工学硕上学位论文 2 5 2 图论模型 图论建模方法是对系统的一种形象化建模方法，图论概念的涵盖范围非常 广泛，只要有结点和边的概念都可归结到图论的框架中。最早的调度对象图论 模型当属于b a l a s 于1 9 6 9 年提出的析取图模型1 ，这是最简单的一种图论模 型，在这种模型中，每种调度实现都可以看作是该图中的一条路径，因此极小 化最后一个任务完成时间的调度目标可以看成是提取其中的某个完备子图使得 其中的最大路径极小化。其它几种比较经典的调度对象图论模型包括结点着色 模型n 、排队论网络模型2 1 、p e t r i 网模型等。 2 6 调度研究存在的问题以及发展趋势 调度问题是n p h a r d 问题，虽然对他的研究已经有几十年的历史，但是至 今尚未现成一套完整的理论与方法体系，理论研究与实用化严重脱节。些调 度算法在理论上能够提供一个近似最优解，但由于没有考虑到现实中的因素， 不能快速响应生产的变化，而且其计算量十分巨大，离其实际应用有较大的差 距。因此，调度问题的研究应该朝以下几个方向发展： 1 实用化现在大部分调度算法的研究仅仅只注重调度算法理论本身，而 能将调度理论大规模的与实际生产问题相结合，给企业带来巨大效益的研究应 用成果鲜有出现。因此，如何加强理论与实际的相结合，实用化调度算法，给 企业提高效率、带来效益是调度研究的进一步研究重点。 2 动态化在生产实际中，经常有机器故障、工件的延迟到达、紧急订单 的插入等情况的发生，这就需要调度系统能对这些情况做相应的调整。在遇到 这种扰动后，调度算法应该能根据当前的调度状态合理的修改调度顺序，合理 安排调度，并且修改后的调度不应该改变已安排的调度，从而最大程度的优化 调度，保持调度系统高效、稳定的运行。 3 计算机化由于调度算法的复杂性，使得一般的方法难以仿真试验。而 计算机拥有强大的计算能力，因此可以利用其高效快速的搭建试验平台，对算 法进行模拟实现，得出仿真结果。 4 复杂化随着生产的发展，社会的进步，对产品制造的要求日益变得复 杂，这就使得存在约束关系的复杂产品调度研究成为一个重要内容。 总之，随着调度问题的进一步深入研究，其必然朝着实用化、动态化、计 算机化、复杂化、高效化方向发展。 哈尔滨理工大学工学硕上学位论文 2 7 本章小结 本章介绍了车间作业调度问题的含义、特点及其分类，然后详细的介绍了 现有的求解车间作业调度问题的研究方法，研究模型。最后阐述了车间作业调 度研究存在的一些问题及其发展的可能趋势。 哈尔滨理 i 大学t 学硕士学位论文 3 1 引言 第3 章复杂单产品调度研究 在实际生产中，产品是由一组存在约束关系的工件按照树状工艺图装配而 成，而工件是由一串前后约束的工序组成。所以，产品加工、装配完全工艺图 是树状结构的。为了简化调度分析，将加工、装配设备定义为设备统一调度， 并统一定义加工、装配为加工。本章所研究的问题是在满足三个约束条件的前 提下使得加工完所有的产品所用的时间尽可能的少。这三个约束条件是：( 1 ) 对于每道工序来说。必须等待其所有的前继工序加工完毕后才能处理此道工 序；( 2 ) 对于每台机器来说，任意时刻只能加工一道工序，且必须满足加工完 一道工序后才能加工另一道工序；( 3 ) 不存在相同设备。本章首先对单个产品 的加工环节进行分析，在尽量做到并行加工的基础上提出了两种调度策略。在 调度过程中根据虚拟加工树的加工流程动态地构造一个可供调度的工序集，同 时应用所提出的两种调度策略调度工序集中的工序。最后给出了完整的算法， 实例对比验证该