（机械制造及其自动化专业论文）jobshop调度优化方法及其应用研究.pdf

独创性申明 秉承祖国优良道德传统和学校的严谨学风郑重申明：本人所呈交的学 位论文是我个人在导师指导下进行的研究工作及取得的成果。尽我所知 除特别加以标注和致谢的地方外，论文中不包含其他人的研究成果。与我 一同工作的同志对本文所论述的工作的任何贡献均已在论文中作r 明确的 说明并已致谢。 本沦文及其相荧资料若有不实之处由本人承担一切相关责任 论文作者签名：看芭疆图d 嬖f 上月j 子h 保护知识产权申明 本人完全了解西安理工大学有关保护知识产权的规定即：研究生在 校攻读学位期间所取得的所有研究成果的知识产权属西安理工大学所有。 本人保证：发表或使用与本论文相关的成果时署名单位仍然为i 酐安理工大 学，无论何时何地，未经学校许可。决不转移或扩散与之相关的任何技术 或成果。学校有权保留本人所提交论文的原件或复印件。允许论文被查阅 或借阅；学校可以公布本论文的全部或部分内容，可以采用影印、缩印或 其他手段复制保存本论文。 ( 加密学位论文解密之前后以上申明同样适用) 论文作者签名： 导师签名：么奎釜玎年；月己z 日 中丈摘要 论文题e l ： j o b s h o p 调度优化方法及其应用研究 学科： 作者： 导师： 导师： 担越剑造厦甚自塾丝答辩日 迦签名：盆望同 奎宣 职称： 数握 签名： 奎塑妲 职称：副塾援签名： 摘要 j o bs h o p 调度问题( j o b s h o ps c h e d u l i n gp r o b l e m ，j s s p ) 是一类具有时间 约束、次序约束和资源约束的组合优化问题。在理论上已经证明，j s s p 是一个n p 难题。而解决这一问题的关键在丁性能良好的优化调度方法的研究和应朋。 本文分析了现存的遗传算法的优缺点，并根据具有各选： 艺的调度过程的特 点，提出了基于】：序优先权和机器约束的两层编码方案，并实现了遗传优化算法， 最后对进化代数对调度性能的影响作了分析。 根据不同的规则对调度结果的影响，设计了单规则调度和多规则组合调度启发 式算法，对相同工艺约束的零件进行了分析进行了大量的实验分析，结果表明，采 用不同的规则组合可以获得良好的调度结果，避免了单规则调度过程的随机性。 对蚂蚁算法在生产调度方面的应用进行了探讨，分析了蚂蚁算法的优越性以及 和j o b s h o p 车间的生产调度问题结合点，设计了生产调度问题的蚂蚁求解方法， 并进行了实例验证。 结合企业生产过程，设计了生产计划与调度部分的数据库。以j s p ( j a v as e r v e r p a g e s ) 语言开发实现了生产调度仿真平台，系统运行结果表明本文所提出的优化调 度算法是可行的和有效的。 关键词： j o b s h o p 调度；遗传算法；启发式算法；蚂蚁算法i 本研究得到陕西省自然科学基金项目“敏捷制造系统控制技术研究( 2 0 0 4 e r 0 2 ) ”的 资助 l 英文摘要 titie ：t h er e s e a r c ho no p t i m a lm e t h o d sa n da p p l i c a t l 0 n s o fj o b s h o ps c h e d u l i n g p r o b l e m s p e c ia a u t h o r s u p e r v s u p e r v t y ：m a n u f a c t u r i n ga n da u t o m a t i o n d a t e ：y uj i a n g u o is o t ：l iy a n s ig n a t u r e ： p o s t ：p r o f e 4 s o r ：l is h u j u a np o s t ：a p r o 戴批，e 船 f e s s o rs ig n a t u 幽曲 a b s t r a c t j o b s h o ps c h e d u i n gp r o b l e m ( w h i c hj s s pi ss h o r tf o r ) i sac o m b i n a t o r i a l o p t i m u mp r o b l e mt h a ti sc o n s t r a i n e dw i t ht i m e 、s e q u e n c ea n dr e s o u r c e i t h a sb e e np r o v e ni nt h e o r yt h a tt h ej s s pi sac l a s s i c a ln p h a r dp r o b l e m s o t h ek e yo fs o l v i n gt h i sp r o b l e mi st h er e s e a r c ha n dt h ea p p li c a t i o no f e x c e l l e n to p t i m a ls c h e d u l i n g a l g o r i t h m s i nt h i s p a p e r ，a d v a n t a g e sa n dd i s a d v a n t a g e s o fe x i s t i n gg e n e t i c a l g o r i t h ma r ea n a l y z e d ，o nt h eb a s i so f t h ec h a r a c t e r i s t i c t h a t t h e s c h e d u l i n gp r o c e s sp o s s e s s e sa l t e r n a t i v ep r o c e s sp l a n n i n g ，t w o l a y e r s c o d i n gs c h e m eb a s e do nw o r k i n gp r o c e d u r ep r i o r i t ya n dm a c h i n ec o n s t r a i n t i sp r o p o s e d ，a n dt h eg e n e t i co p t i m i z a t i o na l g o r i t h mi sa c h i e v e d f i n a l l y ， t h ei n f l u e n c eo fg e n e t i cg e n e r a t i o n so ns c h e d u l i n gd e r f o r m a n c e s is a n a l y z e d a c c o r d i n gt ot h ee f f e c to fv a r yr u l e so ns c h e d u l i n gr e s u l t s ，t h e h e u r i s t i ca l g o r i t h misd e s i g n e d ，w h i c ha d o p t st h ec o m b i n a t i o ns c h e d u l i n g o fs i n g l er u l ea n dm u l t i r u l e s p a r t sw i t hs a m ep r o c e s s e sc o n s t r a i n ta r e a n a l y z e du s i n gal o te x p e r i m e n t s ，a n dr e s u l t si n d i c a t et h a tp e r f e c t s c h e d u l i n g r e s u l t sc a n b ea c h i e v e dw i t hv a r y r n l e s c o m b i n a t i o n ， c o n s e q u e n t l y a v o i d i n gt h er a n d o m i c i t yi nt h ep r o c e s s o f s i n g l e r u l e s e h e d u li n g t h ea p p l i c a t i o no fa n ta l g o r i t h mi np r o d u c t i o ns c h e d u l i n gisd is c us s e d t h ea d v a n t a g ea n dt h ec o m b i n a t i o np o i n to fa n ta g o r i t h mo n 1 0 bs h o p 西安理工大学硕士学位论文 p r o d u c t i o ns c h e d u l i n ga r ea n a l y z e d ，a n to p t i m a la l g o r i t h mf o rj o b s h o p s c h e d u l i n gi sd e s i g n e d ，f i n a l l yt h ec a s ev a l i d a t i o ni sp r o c e s s e d l i n k i n g t h ee n t e r p r js e 8 p r o d u c t i o n ，t h e d a t a b a s eo np r o d u c t i o n p l a n n i n ga n ds c h e d u l i n gisa n a l y z e da n dc r e a t e d f h ep r o d u c t i o ns y s t e mi s c o m p i c a t e db a s e do nj a v as e r v e rp a g e s1 a n g u a g ea n dt h er u no ft h iss y s t e m s h o w st h ef e a s i b i l i t ya n dv a l i d i t yo ft h e s es c h e d u l i n ga l g o r i t h m s k e yw o r d s ：j 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 ：h e u r i s t i cp r o c e s s i n g a l g o r i t h m ；a n ta l g o r i t h m t h i sd i s s e r t a t i o niss u p p o r t e db ys h a a n x ip r o v i n c en a t u r es c i e n c ef u n d p r o g r a m “c o n t r o lt e c h n o l o g yo fa g i l en a n u f a c t u r i n gs y s t e m ( 2 0 0 4 e 2 0 2 ) ” i l l 第一章绪论 绪论 1 1 选题背景及其意义 2 l 世纪的制造企业面临着日益激烈的国际竞争，要想赢得市场，赢得 用户就必须全面提高企业的交货期( t i m e ，t ) 、质量( q u a l i t y ，q ) 、成本 ( c o s t ，c ) 、服务( s e r v i c e ，s ) 、环境清洁( e n v i r o n m e n t ，e ) 。许多企业 通过实施m r p i i e r p 来加强管理。然而上层生产计划管理受市场影响越来 越大，明显感到计划跟不上变化。制造企业面对客户对交货期的苛刻要求， 面对更多产品的改型，订单的不断调整。企业决策者逐渐认识到，企业计 划的制订要依赖于市场和实际的作业执行状态，而不能完全以物料和库存 回报来控制生产。 车间生产调度是制造系统的基础，生产调度的优化是先进制造技术 和现代管理技术的核心技术。近2 0 年来，国际生产工程学会( c i r p ) 曾 总结了4 0 种先进的制造模式，无论那一种模式都是以优化的生产调度为 基础的。有关资料表明，制造过程9 5 的时间消耗在非切削过程中，因 此制造过程中的调度技术，将在很大程度上影响制造的成本和效益。有 效的调度方法与优化技术的研究，己成为先进制造技术( a m t ) 实践的基础 和关键。 总的浇来，制造系统的生产调度是针对一项可分解的工作( 如产品 制造) ，探讨在在尽可能满足约束条件( 如交货期、工艺路线、资源情况) 的前提下，通过下达生产指令，安排其组成部分( 操作) 使用哪些资源、 其加工时间及加工的先后顺序，以获得产品制造时间或成本的最优化。 1 2 车间调度问题的研究现状 1 2 1 车间调度问题的分类及特点 根据研究对象的复杂性，g r a v e s r “j 把车间调度问题分为四类：单机 调度问题、并行机床调度问题、流水车间调度问题和作业车间调度问题。 西安理工大学硕士学位论文 作业车间调度问题( j o bs h o ps c h e d u l i n gp r o b l e m ) 是最复杂的调度问题，生 产车间的大多数调度是作业调度。目前大多数研究集中在作业调度上。 车间调度问题具有以下几个特点”1 ： ( 1 ) 复杂性：由于生产车间中工件、机器、缓存及搬运系统之间相互 影响、相互作用、每个作业又要考虑它的加工时间、操作顺序、交货期 等，因而相当复杂。 ( 2 ) 动态随机性：在实际的生产调度系统中存在很多随机的和不确定 的因素，比如作业到达时间的不确定性、设备的损坏修复、作业交货期 的改变、紧急定单等。 ( 3 ) 多目标性：实际的计划调度往往是多目标的，并且这些目标间可 能发生冲突。生产调度的性能指标可以是成本最低、库存费最少、生产 周期最短、生产切换最少、设备利用率最高、摄短的延迟，最小的提前 或者拖期惩罚、三废最少等。这种多目标性导致调度的复杂性和计算量急 刷增加。 ( 4 ) 多约束性：生产车间中资源的数量、缓存的数量、工件的加工时 间和加工顺序都是约束。此外还有一些人为的约束，如要求各机器上的 负荷平衡等等。 1 2 2 车间调度问题的研究方法 在对调度问题进行研究的方法上，最初是集中在整数规划、仿真和 简单的规则上。随着各种新的相关学科与优化技术的发展，在调度领域 出现了许多新的优化方法，比如神经网络、模拟退火法、遗传算法、禁 忌搜索法等，使得调度问题的研究向多元化方向发展”1 ”，简述如下： ( 1 ) 运筹学方法 运筹学方法是将生产调度问题简化为数学规划模型，采用基于枚举思 想的分枝定界法或动态规划算法解决调度最优化或近优化问题，属于精 确方法。由于其计算复杂性的原因、只能实用于小规模的调度问题。 ( 2 ) 基于规则的方法 2 第一章绪论 对生产加工任务进行调度的传统方法是使用调度规则。该方法具有简 单、易于实现、计算复杂度低等特点，能够用于动态实时调度系统中。 但是近十年的研究表明并不存在一个全局最优的调度规则，它们的有效 性依赖于对特殊性能需求的标准及生产条件。 ( 3 ) 系统仿真的方法 基于仿真的方法不单纯追求系统的数学模型，侧重对系统中运行的逻 辑关系的描述，能够对生产调度方案进行比较评价。由于制造系统的复 杂性，很难用一个精确的解析模型来进行描述和分析。 ( 4 ) 基于d e d s 的解析模型方法 由于制造系统是一类典型的离散事件系统，因此，可以用研究离散事 件系统的解析模型和方法去探讨车间调度问题，诸如排队论、极大极小 代数模型、p e t r i 网等。调度中的排队论方法是一种随机优化方法，很难 得到比较具体的细节。p e t r i 网作为一种图形建模工具，具有很强的建模 能力，对于描述系统的不确定性和随机性也具有一定的优越性。目前， p e t r i 网模型用于f m s 的调度还存在节点语义、重用性差、不能对高级的 调度规则加以建模等缺点。 ( 5 ) 基于排序的方法 该方法是先有可行性加工顺序，然后才确定每个操作的开工时间， 并对这个顺序进行优化，它虽然属于近似算法，但有可能达到最优的调 度方案。主要有下面几种： 1 ) 启发式图搜索法 对于表述为整数规划的调度问题，首先构造一个可行解，采用基于 隐枚举的搜索方法不断提高解的次优性；采用束搜索法( b e a ms e a r c h ) 来识 别瓶颈机器，进行调度。 2 ) 模拟退火法 模拟退火算法( s a ) 通过模拟退火过程，可找到全局( 或近似) 最优解。 其基本思想为：把每种组合状态s i 看成某一物质系统的微观状态，而将 西安理工大学硕士学位论文 其对应的目标函数c ( s i ) 看成该物质系统在状态s i 下的内能；用控制参数 t 类比温度，让t 从一个足够高的值慢慢下降，对每个t ，用抽样法在计 算机上模拟该体系在此t 下的热平衡态，即对当前状态s i 作随机扰动以 产生一个新状态s ，如果c ( s ) 2 ) 台机器上完成加工。已知： ( 1 ) 工件集p = ( p ，p ：，p 。) ，p i 为第i 个工件，i = l ，2 ，n ； ( 2 ) 机器集m = m 。，m 。，m 。 ，m j 为第j 号机器，j = l ，2 ，m ： ( 3 ) 工序序列集o p = o p ，o p ：，o p 。) ，o p = o p o p i ：! ，o p 。) 为 工件p i 的工序序列。o p ，。为第i 个工件在第k 道工序使用的机器号。o p f 0 表示工件p i 在第k 道工序不加工，k = l ，2 ，m ： 而且问题满足下列条件： ( 1 ) 一个工件不能同时在几台不同的机器上加工。 ( 2 ) 工件在加工过程中，当上一道工序完工后，才能送下道工序加工。 ( 3 ) 一般不允许中断。当一个工件一旦开始加工，必须一直进行到完工， 不得中途停止插入其它工件。 ( 4 ) 工件数、机器数和加工时间己知，加工时间与加工顺序无关。 要求安排其各零件的加工工序使用哪些资源、其加工时间及加工的先 后顺序，以获得产品制造时间、成本或其它性能的最优化。 西安理工大学硕士学位论文 2 3 2 遗传编码 基于遗传算法的车间调度研究最重要的工作之一就是如何进行遗传 算法编码，由于车问调度问题具有离散、动态、多机、多变量耦合等多 种属性，所以作业车间调度遗传算法编码具有一定的难度，一直成为g a 直接应用于作业车间调度问题的瓶颈口。在过去的一些年中，人们提出 的主要编码方法如下”2 一“”： ( 1 ) 基于完成时间的表达法 这是一种最直观的方法，它是由y a m a d a 和n a k a n o 提出了一种基于 完成时间的表达法，一个染色体被编码为一个工序完成时间的有序列表， 如下面所示染色体： 【c l u ，c 1 2 2 ，c 1 3 3 ，c z u ，c 2 2 3 ，c 2 3 2 ，c 3 1 2 ，c 3 2 1 ，c 3 3 3 】 其中c 表示工件j 在机器r 加工的第i 道工序的完成时间。很容易看 出这种表达法不适用于大多数的遗传算子，并且需要设计较复杂的遗传 算子，以保证约束条件得以满足。 ( 2 ) 基于工序的表达法 这种表达法将调度编码为工序的序列，每个基因代表一道工序。它 有两种可能的方式来命名每道工序，一种自然的方式是自然数来命名工 序，像t s p 的顺序表达法，但由于j o b s h o p 问题受加工路线的约束，不 是所有的自然数组合都可以定义可行的调度。g e n ，t s u j i m u r a 和k u b o t 提出另一种方式：给所有同一工件的工序指定相同的符号，然后根据他 们在给定染色体中出现的顺序加以解释。对于n 个工件m 台机器问题， 一个染色体包括nxm 个基因，每个工件出现在染色体中m 次，每个基 因不表明一个工件的具体的工序，而是指有上下依赖关系的工序。很容 易看出染色体的任意排列总能产生可行调度。 这里我们用表2 - i 所示的3 台机器、3 个工件调度问题来说明基于工 序的表达法。 1 4 第二章j o b - s h o p 调度问题的遗传优化算法 表2 - 13 台机器、3 个t 件的作业车间调度问题 工件加工路线和加工时间 m l ( 3 )m 2 ( 3 )m 3 ( 2 ) m o )m 3 ( 5 )m 2 ( 3 ) m 2 ( 3 )m l ( 2 )m 3 ( 3 ) 假设给定染色体为 32 21 1 2 3 1 3 ，其中1 表示工件j 1 ，2 表示工件j 2 ，3 表示工件j 3 ，因为每个工件有3 道工序，所以每个工件 在一个染色体中刚好出现3 次，染色体和工件的对应关系如图2 一】所示。 在以上给定的染色体中出现三个2 表示工件j 2 的三道工序，第一个2 对 应工件j 2 第一道工序在机器1 上加工，第二个2 对应工件j 2 的第二道 工序在机器3 上加工，第三个2 对应工件j 2 的第三道工序在机器2 上加 工。我们可以看到工件入的所有工序都用相同的符号2 来命名，并且根 据它出现在染色体中的顺序得到解释，根据对应关系，我们可以得到相 应的机器列表为 m 2m 1 【1 1 3m 1 m 2m 2m l m 3m 3 ，如图21 所示。从图 中可以看到，机器1 上工件的加工顺序为j 2 ，j 1 ，j 3 ，机器2 上工件的 加工顺序为j 3 ，j 1 ，j 2 ，机器3 上工件的加工顺序为j 2 ，j l ，j 3 ，由此 可以得到一个可行调度。 染色体 3 22l123l 3 工件 j 3j 2 j 2 j 1 j 1j 2j 3 j 1j 3 机器e m 2m l m 3m lm 2m 2m lm 3 m 3 图21t 件工序一个可行调度 ( 3 ) 基于工件的表达法 h o l s a p p l e ，j a c o bp a k a 和z a v e r i 提出了这种方法，它由包含n 个 工件的列表组成，每个调度根据工件的顺序来构造。对于一个给定的工 件顺序，列表中第个工件的所有工序将首先被调度，然后考虑列表中 第二个工件的工序，依次进行，直到工件的所有工序排完。加工中的第 一道工序要求的加工时间应为相应机器最可能得到的加工时间。 我们同样以表3 一l 的问题来说明。假设给定染色体为 231 ，则工 件的调度顺序为j 2 ，j 3 ，j 1 。首先加工的第一个工件为j 2 ，该工件工序的 加工设备为 m 1m 3m 2 ，每台机器对应的加工时间为 153 。首先对 j 2 依据 m 1m 3m 2 的顺序进行调度，然后对j 3 依据 m 2m 1m 3 的顺j 进 西壬理工大学硕士学位论天 行调度，最后j l 依据 m 1m 2m 3 的顺序进行调度。最后得到调度结果。 ( 4 ) 基于优先表的表达法 这种表达法首先由d a v i s 提出。对于n 个工件m 台机器的调度问题， 一个染色体由m 个子染色体组成，每个子染色体对应于一台机器，由一 串长度为n 的符号表示，每个符号代表一道在相关机器上处理的工序， 子染色体不能描述机器上工序的先后顺序，因为它们表示的是优先列表： 每台机器有其自身的优先列表。实际的调度由染色体通过模拟发现机器 前等待排队的状态得到，如果有必要用优先列表来确定调度，即选择首 先出现在优先列表中的工序。 同样以表3 一l 给出的实例来说明如何调度，给定染色体为 23l l 32213 。第一个子染色体 231 是机器m l 的优先列表，子染 色体 132 是机器m 2 的优先列表，子染色体 213 是机器m 3 的优先 列表，从这些优先列表可知第一道优先的工序是机器m l 上加工工件j 2 ， 机器m 2 上加工工件j 1 ，机器j i 】3 上加工工件j 2 ，根据给定的工序先后约 束，只有机器m l 上加工j 2 工件才是可行的调度，因此首先对机器m l 调 度。剩下的工序调度方法与此类似。 ( 5 ) 基于优先规则的表达法 d o r n d o r f 和p e s c h 提出了一种基于优先规则的遗传算法，其中染色 体编码为一个工件分配规则的序列。基于分配规则序列，用优先分配启 发式构造调度，遗传算法用于进化染色体以方便产生一个好的分配规则。 由于该方法便于实现，且时间复杂性较小，优先分配规则可能是实际求 解调度问题最多的启发式方法。g i f e r 和t h o m p s o n 的算法被认为是所有 基于优先分配规则启发式算法的基础。 对于n 个工件、m 台机器的调度问题，染色体是一个nxm 的串 ( p l ，p 2 ，p n m ) ，其中p i 表示预先的设定的优先分配规则集合的一个 规则，处于第i 个位置的元素表示，在g i f t l e r 和t h o m p s o n 算法的第i 步迭代中的冲突应该由优先规则p i 来重新处理。令 第二章j o b - s h o p 调度问题的遗传优化算法 p s 。，一包含t 步己调度工序的部分调度 s t ，一对应于p s t 在迭代t 时可调度工序的集合 。t ，一工序i s t ，能够开始的最早时间 由t ，一工序i s t ，能够完成的最早时间 c t ，一迭代t 时刻冲突工序集合。 从染色体( p 1 ，p 2 ，p n m ) 得到一个调度的步骤为： 步骤1 ：令t = l ，p s t 为空，s t 包含所有加工前工序的工序。 步骤2 ：确定中t * = m i n 。： 巾t ) 和能够实现巾 的机器m ，如果 存在多个这样的机器，则通过随机选择来断开链。 步骤3 ：形成一个包含需求机器m 术，且满足ot m ，停止，否则返回步骤2 。 ( 7 ) 随机键表达法 该法首先由b e a n 提出。随机键表达法用随机数编码成一个解。对 于n 个工件，1 7 1 台机器的调度问题，每个基因( 一个随机键) 包含两个部分： 集合f 1 ，2 ，m ) 中的整数和由( 0 ，1 ) 间随机产生的分数，整数部分用来 分配给机器，分数部分用来为每台机器上的工件排序。考虑表3 一l 给出 的实例，假设染色体为： 1 3 4 1 0 91 8 82 6 62 9 12 0 13 2 33 2 1 3 4 4 机器1 按增加的顺序调度，得到工序的顺序为2 1 3 。令d i m 表达机器 m 上的工件i ，则染色体转化为一个有序的唯一列表为： 【0 2 1 0 1 10 3 1 0 3 20 1 2 0 2 20 2 3 0 1 30 3 3 】 容易看出上面给出的工件顺序可能违背工序先后约束，针对这种编 码，可以用一种处理该约束的伪代码。 总的看来，以上各种编码各有自己的特点，但对于解决j o b s h o p 调 度问题，特别是具有备选工艺的调度问题编码实现起来比较困难。为此 将在后面提出基于工序和机器的两层编码方案。 2 4 遗传调度算例 2 4 1 调度问题 这是一个有6 个零件，共3 5 道工序，6 台机床的调度问题。零件 1 8 第二章j o b - s h o p 调度问题的遗传优化算法 的工艺路线约束如图2 4 所示。调度所用的工艺计划的有关数据如袁2 2 所示。 n 舔 。 固固固 回吨 位h 围吨 回 盯 么一一展 v 嗍 咖 圆徊 囡吨 囫吨 酗 图2 - 4零件的工艺约束 2 4 2 调度原始数据 表2 2 是零件工艺计划中每道工序所用的加工设备和工时定额。加 工设备用数字表示，工时定额为时间单位( 本文取分钟为时间单位) 。资 源仅考虑机床，其它资源不受限制，( 考虑其它资源时方法相同) 。没有 考虑机床故障，每一零件有一确定的交货期。 表22 零件加工设备和工时定额数据 零件名称工序编号加工设各和工时定额m ( t ) lm l ( 3 ) ，y 4 ( 6 ) m 5 ( 8 ) 2m 2 ( 4 ) m 6 ( 6 ) 3 m 5 ( 3 ) ，m 3 ( 5 ) ，m l ( 7 ) 零件1 4m 6 ( 5 ) ，m 2 ( 6 ) 5 m 4 ( 6 ) ，m 1 ( 7 ) 6m 3 ( 3 ) m 5 ( 4 ) 7 m 2 ( 5 ) m 3 ( 7 ) 8m 5 ( 6 ) ，m i ( 7 ) m 2 ( 9 ) 零件29m 4 ( 4 ) ，m 2 ( 7 ) 1 0m 5 ( 7 ) m 3 ( 9 ) 1 1 m 3 ( 3 ) ，m 6 ( 5 ) 1 2m 1 ( 5 ) ，m 4 ( 6 ) m 3 ( 7 ) 1 3m 3 ( 5 ) m 5 ( 7 ) 1 4 m 6 ( 4 ) ，m 2 ( 5 ) 西安理工大学硕士学位论文 零件3 1 5m 5 ( 4 ) ，m 3 ( 5 ) 1 6m 4 ( 3 ) ，m l ( 5 ) m 4 ( 6 ) 1 7 m 2 ( 7 ) m 5 ( 9 ) 1 8m 6 ( 2 ) ，m 2 ( 5 ) 1 9h l ( 6 ) ，m 4 ( 7 ) 2 0 m 3 ( 7 ) ，m 5 ( 8 ) ，m 6 ( 1 0 ) 零件42 lm 2 ( 5 ) ，m 6 ( 8 ) 2 2 m 4 ( 4 ) ，m l ( 7 ) 2 3 m 6 ( 6 ) ，m 2 ( 7 ) 2 4 m 5 ( 4 ) ，m 3 ( 5 ) 2 5m 6 ( 6 ) ，m 2 ( 7 ) 2 6 m 4 ( 5 ) ，m 1 ( 7 ) m 3 ( 8 ) 零件52 7m l ( 4 ) m 4 ( 7 ) 2 8m 2 ( 5 ) m 6 ( 7 ) 2 9m 4 ( 3 ) ，m l ( 5 ) 3 0 m 3 ( 6 ) ，m 5 ( 9 ) 3 1， m 5 ( 4 ) ，m 3 ( 7 ) 3 2m 6 ( 6 ) ，m 2 ( 7 ) m 4 ( 9 ) 零件63 3m 3 ( 3 ) ，m 5 ( 7 ) 3 4m l ( 3 ) ，m 4 ( 4 ) 3 5m 2 ( 6 ) ，m 3 ( 7 ) 2 4 3 遗传优化算法 ( 1 ) 编码和解码 通过上面对编码方法的分析可知基于工件加工工序的编码方法简 单直接且易于交叉和变异操作，构造的交叉和变异操作既保证了工件的 加工工序约束，又具有很高的效率，但常用于机器事先确定的作业调度 问题。对于有备选工艺的柔性作业车间调度问题，问题的解包含两方面 的内容：工序的顺序和机器的选择。因此编码也要反映这两方面的内容。 为此提出基于工序和机器的两层编码方案来实现表2 - 1 和表2 - 2 所描述 的问题，如表2 3 所示( 其中o p 。，表示第i 个零件的第j 道工序，表中 仅列出零件部分工序) 。第一层编码为各工序的优先权随机数( 在 1 ，k 中产生，其中k 表示总的工序个数) ，第二层编码是各工序所选择的加 工机器，从可供选的机器中随机选出。 第二章j o b - s h o p 调度问题的遗传优化算法 表2 3 基丁t 序和机器的两层编码表 【零件工序 o p t lo p l 2o p l 3o p 2 1o p 2 2o p 2 3o p 3 l0 p 3 20 p 3 3 l 第一层编码915386 7 42 l 第二层编码 m 1m 2 m 5m 3 m 2m 5 m 3m 6 m 5 对于上述编码方案的解码主要是排定所有工序的加工顺序。在这里采 用结合编码中各工序的优先权随机数对工序约束( 图2 4 ) 进行拓扑排序 的方法。步骤如下： 第一步：选取没有前驱( 入度为零) 的工序，结合图2 - 4 和表2 3 中 的数据知相应满足条件的工序为：o p ，o p l 2o p 。o p ，。 第二步：比较选出工序的优先权，选出优先权最高的工序，同时从 工序约束图中去掉该工序节点。根据表2 3 知o p 。的优先权最高，故首 先选出o p ，从工序约束图中删除op 1 【节点。 第三步：若入度为零的顶点输出完毕，则结束，否则重复第一步和 第二步。 按照此方法，可以得到表2 3 中染色体的工序顺序为： o p i l o p 3 l 一0 p 3 2 0 p 2 l 一0 p 2 2 0 p 船一0 p 3 3 一o p l2 一o p l3 然后根据各工序选择的机器就可得到每台机器上加工的工序及顺序， 即调度问题的一个解。因为在拓扑排序过程中已经考虑了各工件工序的 先后约束，所以得到的调度一定是可行的。调度结果如表2 4 所示： 表2 - 4 机器 部分加工工序及顺序 机器编号加工工序及顺序 m l o p l l m 2 o p 2 r o p l 2 m 3 0 p 3 1 _ 0 p 2 i m 5 o p 2 3 p ) r o p l 3 m 6 o p 3 2 遗传算法的编码及解码流程如图2 5 和图2 - 6 所示： ( 2 ) 初始种群产生 由每一个工件选择的工艺计划构成的集合就构成了初始群体。 西安理工大学硕士学位论文 开始 查寻零件总工序数 o p 机器数日k 和 工序加t 机器m 选出入度为 自工序，将其自 口到集合r ( 0 从集合ri 0 ) b 出优先权最大 出，删除该工 图2 - 5 编码流程图 图2 - 6 解码流程图 ( 3 ) 适应度定义和选择操作 在遗传算法中，以个体适应度的大小来确定该个体被遗传到下一代 群体中的概率。个体的适应度越大，该个体被遗传到下一代的概率也越 大。计算个体适应度首先要得到个体的目标函数值。以全部零件在系统 中的平均流通时间最短为目标函数。为了便于概率选择，令适应度为： l ； 1 争葚， ( n 一机床台数，f ，m 床流通时间) ( 2 - 6 ) 选择操作建立在对个体的适应度进行评价的基础之上，采用适应度 比例选择法来计算个体生存概率。 ， p 。( f ) = ( 其中m 表示群体大小) ( 2 7 ) ( 4 ) 交叉操作 第二章j o b - s h o p 调度问题的遗传优化算法 交叉操作可以将父代的良好基因通过信息互换，而产生更好的子代。 交叉方法如图2 7 所示： 于代工序 o p , 1 o p 【oo d i3o p io p ”o p 2 s o p 3 1 o d3 2o d 33 第一层编码 72t 娃 ； ： ! i 、3 ， 。nj ： 9l4 第二层编码 摊r ? m 2 i 瓶戤一 m 0m 3 粕溉m 6 m 5 j l 父代2 工序o p t lo p i 2 o p l 3o p 2 1o p 2 z o d z 。o d 3 l0 d 2 o p t 3 l 第一层编码729 s 鞲瓣；罐瓣瓣_ 氍 1 ：1 1ll j0。#4 8 l 第二层编码 娘e 4 ，。2 m 4 l 酝露溅懑麟蓑 m 5 m 5 图2 - 7 交叉操作方_ i 击不葸图 从父代i 中随机挑选一个子系列拷贝到子代相应的位置。对于第一层 编码为避免产生不合法的染色体，可以从父代2 中移走在子代中已有的 随机数，将剩余的随机数依次放入子代中。而对于第二层编码则可以将 父代2 的基因( 除子代中已有的子系列外) 直接拷贝到子代相应的位置。 ( 5 ) 变异操作 变异操作相对而言比较简单，对第一层编码进行变异操作，采用倒置 变异的方法。对第二层编码操作，采用约束倒置变异的方法。如对父代 1 变异过程如下： 表2 - 5 变异前父代l 编码图 父代1 工序lo p ，o p 。 o d l3 0 m l0 p 2 20 d 2 3o p 。，o p o p 。a 第一层编码l9 l 黔 ；| | ； 38 6 7dl 第二二层编码lm l m 2瞒j ：m 3m 2m 5 “口i rl 将表2 - 5 的第一层编码随机数5 和7 采用倒置变异的方法得到新的个体 如表2 - 6 。 表2 - 6 变异后父代1 的编码 如果需要同时对第二层编码变异的话，先要判断第二层机器编码足 甭可以互换，即判断对应的机器是否都可以加工需要变异的工序。如果 2 3 西安理工大学硕士学位论文 可以的话，则同上将两机器进行倒置变异即可。 例外，交叉和变异的概率选择常采用固定概率，不能准确的反映种 群的进化进程。自适应的交叉概率p c 和变异概率伟根据种群的进化状态 来确定，随群体的适应度自动改变，当种群的各个个体的适应度趋于一 致或趋于局部最优时，使p c 和岛增加，以跳出局部最优；而当群体适应 度比较分散时，使卫和体减小，以利于优良个体的生存。同时，对于适 应度高于群体平均适应值的个体，选择较小的卫和凸，使得优良个体得 到保护；而适应度低于群体平均适应值的个体，选择较大的且和体，增 加新个体产生的速度。交叉和变异的自适应算式为： 胪c 。等净，。f ； 陋。， i c 2 ，f 二，一只镕2 f p ，；m i 瓦- f m a x - - f ，k f c 氏，一 ( 2 9 ) i m 2 ，f 眦；一f 乏，：。一，4 其中，p 。为交叉概率；p 。为变异概率；f m a x 为种群个体中的最大适 应度；f a ，。为种群个体的平均适应度；，为交叉或变异个体的适应度；c l 、 c 2 、m 1 、肌2 为 0 ，1 之间的常数。 ( 6 ) 算法流程框图 自适应遗传算法流程如图2 8 所示。 ( 7 ) 遗传调度结果 遗传算法中的参数设定为：群体大小m = 1 0 0 ，终止代数t = 5 0 0 ，交叉 概率和变异概率根据进化过程确定。采用j a v a 语言，数据库为 s o l s e r v e r 2 0 0 0 ，电脑的c p u 为6 5 4 m h z ，内存1 2 8 m ，得到的优化调度结 果如图2 - 9 所示。调度结果指标为最大流通时间为3 7 分钟，平均流通时 间为3 2 8 3 分钟，机床相对利用率为8 2 8 。 2 4 第二章j o b s h o p 调度问题的遗传优化算法 圃 图2 - 8 自适应遗传算法流程图 黛太流通时简c3 7 0 分钟平均流疆时阃c3 2 8 3 分钟机床利用弗8 2 8 幽2 - 9 遗传算法训度i 特幽 西安理工大学硕士学位论文 2 4 4 结果分析 对于遗传算法的性能及其对调度结果的影响，可以从以下几个方面进 行探讨1 3 3 1 ： ( 1 ) 在线性能：由第一代到当前代的平均值表示。设t ( s ) 为环境e 下策 略s 的在线性能，c ( f ) 为时刻t 或第t 代中相应于环境e 的目标函数或平 均适应度函数，则 x e( s ) = f 1 章川) ( 2 1 0 ) 在线性能表示了算法从开始运行一直到当前为止的时间段内性能值 的平均值，反映了算法的动态性能。 ( 2 ) 离线性能：是最佳性能的累计平均。设x 。+ ( s ) 为环境e 下策略s 的 离线性能，则有 x 。$ ( s ) 2 争乏p ( f ) ( 2 _ 1 1 ) 其中，丘。o ) = 6 阳f ( 丘( 1 l 丘( 2 ) o ) ) 离线性能表示了算法运行过程中各进化世代的最佳性能值的累计平 均，它反映了算法的收敛性能。 ( 3 ) 最大流通时间( f 一) f 。= m a x ( f ，) j = l ，2 ，n ，n 为机床台数 ( 2 1 2 ) ( 4 ) 平均流通时间( f ) ，n( 2 1 3 ) n 专著l 其中f ，为机床的流通时间，n 为机床台数 ( 5 ) 机床相对平均利用率( u t 。) “：。专“， ( 2 1 4 ) 其中“，2 i 1 盔c 第二章j o b - s h o p 调度问题的遗传优化算法 t ；为工序i 的加工时间，m ( ) 为在j 上加工的工序集 ( 6 ) 调度计算所用时间( t ，单位为分钟) t - t 。一t 。其中t 。表示调度计算开始时间，t 。调度计算结束时涮 表27 进化代数t 对调度结果的影响 t凰( s )* ( s )r 。： f u mt l4 1 0 04 1 0 04 80 04 1 0 06 65 8 0 2 5 53 9 ，5 93 9 5 94 2 0 03 8 1 77 1 3 2 o4 2 1 03 9 3 93 9 1 l4 6 0 03 9 0 06 9 9 2 0 6 0 1 53 8 6 43 8 4 34 3 o o3 6 3 77 46 3 0 7 5 2 0 3 8 0 4 3 7 8 8 4 1 0 0 3 5 6 7 7 59 0 09 1 2 53 7 5 43 7 4 0 3 9 0 0 3 5 0 07 73 0 1 0 7 3 03 7 2 7 3 7 0 5 4 1 0 03 5 6 77 5 9 0 l2 1 3 53 7 2 l3 6 8 04 0 0 03 6 8 37 4 0 3 l3 8 4 03 6 9 73 6 6 03 9 o o3 5 0 07 73 0 15 0 4 53 6 7 73 6 4 4 3 9 0 0 3 5 o o7 73 0 16 6 5 03 6 7 23 6 3 l 4 1 0 03 6 1 77 5 0 8 18 3 5 53 6 4 83 6 1 03 8 0 03 3 8 38 04 2 l9 9 6 03 6 3 63 5 9 33 9 0 03 5 0 07 7 3 0 213 6 53 61 13 5 7 13 7 0 03 2 8 38 2 8 0 23 0 7 03 6 0 l3 5 5