（机械制造及其自动化专业论文）柔性作业车间调度问题的算法研究.pdf

武汉科技大学硕士学位论文 第1 页 摘要 随着制造技术的发展，企业的生产过程发生了明显的变化，其主要表现在生产过程 的复杂化和生产过程的连续性。在竞争激烈的情况下，要保证企业获取利益的最大化， 生产企业必须合理的安排和利用资源、减少工期、降低生产成本。因而作业车间调度问 题越来越受到人们的关注。 近年来，许多智能优化算法被应用到这类问题中。遗传算法由于其搜索范围广、并 行能力强、同时对于问题模型的依赖程度并不高等特点，广泛的用于作业车间调度问题 中。 本文应用遗传算法求解作业车间调度模型，首先论述了作业车间调度的重要性、国 内外研究现状和研究方法。 其次，对传统的作业车间调度问题和柔性作业车间调度问题分别建立数学模型，提 出了目标函数和约束条件。针对作业车间采用基于工序的编码方法，进行优化求解。对 于柔性作业车间，由于工件的加工存在加工路径柔性的问题，工件的工序在加工过程中 可以选择不同的加工机器。针对这种情况，采用二维矩阵编码方法，扩展了传统基于工 序的编码方式，同时在算法的进化过程中引入了一种改变附加算子的方法。 最后，验证了算法的有效性和稳定性。 关键词：车间调度；遗传算法；路径柔性；改变附加算子 第1 i 页 武汉科技大学硕士学位论文 a b s t r a c t w i mt l l e r a p i dd e 、吧l o p m e n to fs c i e n c e 龇1 dt e c l m o l o g ya n de c o n o m i c9 1 0 b a l i z a t i o n ，t 1 1 e p r o d u c t i o ns c a l eo fe n t e r p r i s e sa r ea l s oi n c r e 舔i i 培l y1 a 唱e r ，t h ec o i n p i e x i 锣o f 也ep r o d u c t i o n p r o c e s si si n c r e 懿i i l g l yl l i g h ，w i l i l ef a c i n gi n c r e 硒i 1 1 9 1 yf i e r c em a r k e tc o h l p e t i t i o ne n v i r o n m e n t h lr e c e n td e c a d e s ，也ep r o d u c t i o np r o c e s sh 嬲a l s ou n d e 玛o n es i 鲥f i c 觚tc h a n g e ，m a i m y ：i i lm e c o n t i l l u i t ) ，o ft h ec o m p l e x i t ) ro ft h ep r o d u c t i o np r o c e s sa r l dp r o d u c t i o np r o c e s s e s i n 趾 i 1 1 c r e 嬲i i l g l yc o n l p e t i t i v ec i r c u m s t a n c e s ，t o e n s u r ea c c e s st om a x 证l i z et l l eb e n e f i t so f p r o d u c t i o nm u s tb er e 嬲0 1 1 乏出l ea 舶眦g e m e n t sa 1 1 du s eo fr e s o u r c e s ，r e d u c et l l e ( i u r a t i o na i l d p r o d u c t i o nc o s t s t h l l s ，1 ej o b s h o ps c h e d u l i n gp r o b l e m sa t n 习【c tm o r ea n dm o r ea _ t t e n t i o n t h ej o b - s h o ps c h e 咖i n gp r o b l e mi sas i m p l i f i e dm o d e lo f 1 ea c t u a lp r o d u c t i o ns y s t e m ，2 l sa 1 i i l e a rp r o 掣锄：l l l l i n gp r o b l e m ，m o r ea n dm o r e 缸e l l i g e n to p 血n j z a t i o na l g o r i m m sa r ea p p l i e dt o s u c hp r o b l e m s f o rc x 卸叩l e ：也eg e n e t i ca l g o r i t ，s 曲【u l a t e d 锄e a l i i l ga l g o r i t 量l 】 1 1 ，h e u r i s t i c a l g o r i t h m ，p a n i c l es w a r mo p t i m i z a ：t i o n ，e t c a m o n gt h e s ei n t e l l i g e n to p t i m i z a t i o na l g 耐t 1 1 m ， g e n e t i ca l g o r i 吼，i t ss e a r c hf o ra 诚d em g e o fp a r a l l e lc 印a b i l i 劬w h n et l l ed 印e n d e n c eo f t l l ep r o b l e mm o d e li sn o tm 曲，s og e n e t i ca l g o r i 也mi ns o l v i n gs u c hp r o b l e m s ，h a sam o r e o b v i o u sa d v 锄协g e 也姐t l l eo t h e ra l g o r i m m s i nt h i sp a p e r ，u s i i l gg e n e t i ca l g o r i t h mt os o l v em ej o b - s h o ps c h e d u l i n gp r o b l e m s ，f i r s t l y d i s c u s s e sm ei i l l p o n a n c eo fm ej o bs h o ps c h e d u l i 芏l g ，r e s e a r c hi n e m o d s ，a n dp r o p o s e das p e c i a l c l a s s 丽t l l 廿1 ep r o c e s s i n gp a mo fn e x i b l ej o b s h o ps c h e d u l i n gp r o b l e m s e c o n d l ye s t a b l i s ht h em a t h e m a t i c a lm o d e lr e s p e c t i v e l y f o rm et r a d i t i o n a l j o b s h o p s c h e d u l i n gp r o b l e ma n dn e x i b l ej o b s h o ps c h e d u l i n gp r o b l e m p r o c e s sc o d i n gi su s e df o rt h e j o b s h o pp r o b l e n l s f o rn l e n e x i b l ej o b - s h o pp r o b l e m s ，b a s e do ng e n 舐ca l g o r i t h i l l s ，a s c h e d u l i l l ga p p r o a c hi sp r e s e n t e d ，w t l i c hc a nb eu s e dt os o l v et h ep r o b l e m an e wc l l r o m o s o m e r e p r e s e n t a t i o n 、) v i 也咖一曲n e i l s i o i 试m 砌xi sd e s i g n e d ，w i l i c hc a l le 1 1 l a 玛e 仃a d i t i o n a lc o d i l l g m o d eb 嬲e do no p e m t o r si i le x p r e s s i o no f 也em a c l l i n e s an e w o p e r a t i o ni sd e s i g n e dt oc h a i l g e t 1 1 ee x t r ai i l f o 珈t i o nt 0e x p a n dm es e a r c hm g e d 砸n g l ee v o l u t i o np r o c e s s 弛a l l y ，m ee 氐c t i v e n e s so f 也ea l g o m m i sv e r i f i e d b yc o m p u t i n gr e s u l t s 谢t 1 1as c h e d u l 吨 p r o b l e m ，、) l ，：i l i c hm e e t sm em i i l i m 眦p r o c e s s i n gt i m e k q 啊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 培o r i 也l ；n e x i b l e ? p a 也；c h a i l g ee x 订ai n f o 咖a t i o n ； 武汉科技大学硕士学位论文 第1 页 1 1 引言 第一章绪论 随着科学技术的飞速发展以及经济全球化趋势，生产制造企业的生产规模也日益变 大，生产过程的复杂程度也日益变高，同时面临的市场竞争环境也越来越激烈，因此对 于企业的管理方法以及在生产过程中监控的要求也越来越高【l 】。近年来，由于先进制造 技术的引进，使得产品的制造加工过程有了十分明显的变化，这些变化主要体现在生产 过程复杂程度高和加工过程的连续性强。在竞争日益激烈的情况下，以前仅仅依靠管理 人员个人经验的管理方法，已经无法满足现代企业的需求，更加无法保证企业获取利益 的最大化。 企业管理者现在面临的问题是如何应对生产的过程中各种随机动态因素。例如：在 生产过程中，由于生产计划临时改变，面对这种情况管理者应该如何对生产过程进行控 制；产品在生产工艺过程变化很小的情况如何对生产加工过程进行有效合理的控制，使 得企业获取利益的最大化【2 j 。 作业车间调度类问题国内外已经有6 0 多年的研究历史，在调度研究的不同的历史阶 段，均有许多代表性的论文、著作和算法。我国对于作业车间调度问题的研究虽然起步 比较晚，但是近年来也取得了很多丰硕的成果。由于我国制造水平以及工业化相比于发 达国家还是比较落后的，提高企业的市场竞争力如果仅仅依靠制造水平的提高，在短期 内无法实现，因此完善调度管理体系，使用有效的调度手段和优化方法，是当前制造企 业首要任务。有效的调度方法的应用和合理的优化算法的设计，对于我国制造企业提高 市场竞争力，具有十分积极的作用【3 j 。 1 2 国内外的研究历史和现状 作业车间调度总的来说就是由一个加工集和一个任务集构成。针对这样一个可以使 用的加工集，将任务集上需要完成的加工作业分配到这个加工集上，满足性能的指标集， 对于这样的一个集和称之为作业车间调度。在作业车间调度问题中包括一个作业集，这 个需要加工的作业集中的作业全部由操作集组成，各项操作需要占用资源( 机床) ，同时 操作在加工的过程中存在工艺顺序的约束【4 】。车间调度的任务就是如何合理的安排这些 作业集，将这些作业集合理的分配到各个机床上。同时在加工的过程中，需要考虑加工 过程中的各种约束条件，合理的分配各个工件的加工顺序，针对某些具体的性能指标进 行优化。 作业车间调度类的问题研究开始于二十世纪7 0 年代，j o l m s o n 首先提针对两台机 床的作业车间调度问题【5 】，在文献【5 叙述了这类问题的复杂性。由于复杂程度高，求解 过程繁琐，引起当时学多学者的关注。当然由于实际加工环境不可能完全一样，以及调 第2 页武汉科技大学硕士学位论文 度问题的复杂程度也不一样，学者在对调度问题进行研究的过程中，都是针对当前的加 工环境，从各个不同的方面对问题进行研究，因此也产生了许多不同类型的问题和解决 方法。调度的核心问题是建模和算法的设计，建模主要涉及到问题的数学模型、约束条 件和目标函数，算法设计则包括问题的最优解、复杂性以及算法的有效性和稳定性。 d u d e k p a n w a 】k a r 在1 9 8 0 年提出了一种利用周期性和事件驱动的作业车间调度策 略【6 - 7 】。d e l l a m i c om 和t r u b i a i lm ，在1 9 9 3 年提出了采用禁忌研究方法来求解作业车 间调度问题m j 。 我国针对作业车间调度问题的研究始于2 0 世纪8 0 年代，李宝泽和汪定伟在1 9 8 1 年提出了一个企业生产调度的两级优化模型，将企业的调度问题分解成为两个模型分别 进行研究。熊光楞在1 9 9 4 年使用了一种基于规则的工厂仿真调度系统来模拟现场加工环 境，王朝晖和陈浩勋在1 9 9 7 年对化工过程中的批处理调度问题，采用l a g m g i a l l 松弛 法来优化求，取得了比较好的效果陟1 0 j 。 调度问题由于复杂程度高，计算量大，采用数学规划求解这类问题比较困难。随着 调度类问题的深入研究，各种有效的智能算法和仿真方法开始被广泛的用于车间调度问 题中。 g 0 0 d i l l gw b 在2 0 0 2 年提出了一种采用神经网络方法使得算法在求解的过程中避免 算法陷入局部最优解，而无法获得真实的最优解。在2 0 0 3 年也提出了一种采用模拟 退火算法使得算法在局部最优解的情况下跳出然后求得最优解。j o s ef e m a l l d o 在2 0 0 6 年提出了一种混合遗传算法对作业车间调度模型进行优化，运用遗传算法对问题进行编 码操作，在算法的进化过程中引入启发式算法来弥补遗传算法早熟的缺点。闫立军在 2 0 0 8 年采用将序优化思想融入巢分区算法框架，对算法进行局部优化，减少算法的搜索 时间，来求解这类问题l l 。 随着调度问题的深入研究，一种更加复杂的作业车间调度问题柔性作业车间调度问 题被提了出来，针对这类具有柔性加工路径的车间调度问题，许多智能优化算法被提出 来用于解决这类问题，遗传算法是应用最广泛的一类。同时针对遗传算法的缺点，结合 实际问题的特点，在应用的过程中也提出了许多改进的算法。 b u c k e r 在1 9 9 0 年首次提出了在作业车间中，工件的加工工序可以不局限在固定的 机床上加工，存在多种加工路径的这个问题。h o l s 印p l e 在1 9 9 5 年针对这个问题，采用 遗传代码确定工件在调度过程中的先后顺序，然后采用常规的f b s 搜索方法，对工件的 加工工序按照约束条件进行调度。l o o d 在2 0 0 0 年采用基于仿真的方法进行了研究，采 用p e 仃i 网对这类柔性路径的作业车间调度进行建模。谷峰在2 0 0 6 年提出了一种采用遗 传算法，在编码过程中引入病毒遗传机制来克服算法早熟的缺点，同时引入了一种自适 应遗传算法加强了算法的搜索效率和稳定性。张超勇在2 0 0 7 年针对遗传算法初始化的问 题，提出了一种两级遗传算法，设计一种基于工序编码和基于机器分配编码的两种交叉 算子和变异算子的改进方法，从而使产生的子代更好的继承了父代的特性，优化的结果 更加准确 1 2 j 3 1 。张国辉和高亮在2 0 0 9 年提出了一种改进的遗传算法，在考虑机器加工平 武汉科技大学硕士学位论文第3 页 衡的前提下，设计了一种全局搜索和局部搜索相结合的种群初始化方法，加强算法的搜 索效率，加快算法的收敛次数1 4 1 。 1 3 研究意义和主要内容 1 3 1 研究意义 首先，作业车间调度问题是c 蹦s 系统中的关键因素，这类问题的研究是现代制造 企业自身生存和发展的基础。作业车间调度综合应用了管理技术、制造系统运筹技术和 优化仿真技术，如何合理有效的使用调度方法，已经成为了先进制造技术的关键问题【1 5 】。 其次，作业车间调度类问题的研究对于现代优化技术的发展有着极大的促进作用。 目前，在作业车间调度领域主要的研究方法有：运筹学、启发式方法、仿真方法、智能 算法、神经网络等等。作业车间调度问题一直被认为是具有挑战力的热点问题，所以如 何高效的求解这类问题对于相关学科的发展有着极大的助力。 最后，作业车间调度类问题的研究对于其他领域的问题也有着借鉴的作用。作业车 间调度来源于制造系统中的车间，实际上这类问题只是调度大类中的一个方面，作业车 间调度问题的研究理论同样也可以适用于物流、能源、和社会服务等等各个方面。同时 求解这类问题的智能优化算法也可以应用到其他的领域，诸如计算机、通讯等等。 鉴于以上因素，作业车间调度问题的研究不仅有着重要的现实意义也有着重要的理 论意义。 1 3 2 研究内容 第一章提出了研究的问题，并简要的介绍了国内外对于作业车间调度问题的研究现 状，同时也详细的论述的本文的研究意义。 第二章详细的介绍了遗传算法，这是一种基于达尔文生物进化论而发展出来的一种 智能优化算法，其核心思想就是适者生存。介绍了这种智能算法的数学基础，基本思想 以及算法的三种主要遗传操作。 第三章分别介绍了作业车间调度问题和柔性作业车间调度问题，对这两类问题进行 详细的讲解，分别对这两类问题进行数学建模，列出约束条件，并阐述了这类问题的研 究方法。 第四章是仿真实例，基于遗传算法的作业车间和柔性作业车间调度问题的具体应用 过程。作业车间调度问题采用基于工序的编码方式，并且采用了自适应的选择和变异方 法进行分析验证。柔性作业车间则采用区别于传统车间调度类问题基于工序或者基于机 器编码的方法，采用一种将加工机器和工件工序相融合，扩展机器表达方法，形成一个 二维矩阵的编码方法，并且通过一种改变算子附加信息的方法，来扩大搜索，并通过多 个实例的验证，验证了这种算法的有效性和稳定性。 第五章对总结了本文的研究成果，明确了未来的研究方向。 第4 页武汉科技大学硕士学位论文 第二章遗传算法理论和基础 遗传算法( g e n e t i c 灿g o 僦h m s ，g a ) 的研究始于2 0 世纪6 0 年代末期，主要由美国 m i c l l i g 趾大学的j o h nh 0 1 l a n d 与其同事通过研究形成了一套比较完整的理论和研究方法 1 6 】。这套理论方法主要从自然环境生物的进化过程着手，通过模拟生物的自然进化机制 来构建人工系统的模型。经过了2 0 多年的发展，遗传算法有了长足的进步，在许多领域 使用遗传算法取得了丰硕的成果。同时近年来随着计算机技术的高速发展，由于遗传算 法的应用范围广、计算效率高等特点，遗传算法受到了大量的关注，研究方法也日趋成 熟。 2 1 遗传算法概述 2 0 世纪5 0 年代末和6 0 年代初，就开始有计算机工程学者对于人工进化系统开始进 行研究，其基本的出发点就是进化的思想可以为许多的工程问题服务，成为工程问题的 优化方法。初始的研究方法形成了现今的遗传算法的雏形，绝大多数的研究方法都是遵 循“适者生存”这一基本进化理论。有些科学家在研究过程中采用了种群( p o p u l a t i o n ) 的设计方案，同时自然选择和变异也被加入到这类研究中，还有一些的研究系统在不断 的研究过程中加入了编码设计，对于编码进行抽象处理。 由于在实际应用中并没有一种通用的编码方案，研究人员在算法的进化过程中通常 只能够依赖染色体变异而不是交叉来产生新的基因结构，由于变异几率较低，在早期的 研究过程中这类算法的作用并不明显。j o l l i lh o l l 趾d 和h j b r e m e n n 锄等人在2 0 世纪 6 0 年代中期，针对这类问题提出了一种位串的编码技术。这种编码技术具有一定的通用 性，不仅适用于变异操作同时也适用于交叉的操作，最重要的是这是一种将交叉操作作 为算法中主要操作的一类方法，这种方案保证了算法在进化过程中有新的基因结构产生。 随后，h o l l a n d 等人开始推广这种算法，而且成功的将其运用到各类工程技术问题中， 并将其命名为遗传算法【1 7 】。遗传算法由于其编码技术的通用性、遗传操作过程简单有效、 算法搜索过程中的并行性和适用范围广的特点，成功的应用到各个工程领域中。 近几十年来，遗传算法的应用范围越来越广，无论是用于解决实际问题或者是理论 研究又或者是建模，应用的范围不断的在扩大。同时由于遗传算法本身的可扩展性，现 在提出来的新方法与最初的遗传算法之间也有不小的差距。不同的基因序列表达方法、 不同的交叉方法和不同的初始化方法等，以及为了达到某些目的例如扩大搜索范围会引 入一些特殊算子，当然这些新提出来的算法的基础仍然是以大自然的生物进化论为基础 的。 遗传算法的本质来源于生物进化理论，其自然选择学说由下面三个方面构成： 1 遗传 这是生物的普遍特征，父代把生物信息传递给子代，子代按照这些信息成长、发育， 武汉科技大学硕士学位论文第5 页 所以子代通常与父代具有相同的或者相似的性状特征，因为这个特征的存在，生物才能 稳定的繁衍下去。 2 变异 父代和子代以及子代的不同个体之间不可能完全相同，之间总会有一定的差异性， 这种差异性称之为变异，变异发生的是随机性的，由于变异的存在保证了生物种群的多 样性。 3 适者生存。 生物在生长过程中，适应程度高的子代就容易保留下来，适应程度低的个体就被淘 汰掉，由于自然环境的选择作用，生物的变异朝着一个方向积累着，逐渐的与祖先不同， 这样就会有新个体的产生。由于这个过程是不断积累的，经过好若干代之后才会与祖先 不同，这是一个长期、缓慢的过程。 2 2 遗传算法的基本思想 一般认为，遗传算法主要由以下5 个方面组成： 1 问题解的遗传表示； 2 种群初始化的方法； 3 根据个体的适应度值进行优胜劣汰判定的适应度函数； 4 产生新的子个体成为遗传算子； 5 遗传算法的参数值。 遗传算法是从种群0 0 p u l a t i o r l ) 开始的，问题的可行解一定在种群之中，种群中的个 体都会采用编码技术对其进行编码。从生物学的角度来说每个个体就是一条染色体，通 过编码技术使这些染色体成为了带有特征的实体。染色体实质上就是含有遗传特性的基 因的集合，个体的性状和特征就是通过这些基因自由组合而表现出来的。外部表现就是 通过染色体内部的基因串来实现的，因此在初始阶段需要实现表现型到基因型的映射， 这种映射就是基因编码。当然基因编码比较复杂，一般都采用简化的编码方法，如二进 制编码法。当初代种群产生之后，按照生物进化学说，自然选择和适者生存的准则，逐 代的演化，产生出越来越好的解。在每一代中，个体在适应度函数的作用下都会有一个 适应值，在对遗传算子进行交叉和变异操作之前，会先根据适应值，选出适应度高的个 体，在进行遗传操作产生新的解集种群。在这个过程中，子代由于保留了父代的特性同 时又不同于父代，因而子代相比于父代对于环境的适应能力更强，算法在经过运算达到 收敛之后，产生的末代种群中的最优个体经过解码，就可以作为问题的最优解。 遗传算法就是模拟自然进化方法，首先建立问题的数学模型，通过选择、交叉、变 异等遗传操作，获取最优解。在算法开始计算之前，会产生一定数目的个体( 个代1 ， 个代2 ，) 这些个体称之为父代个体，这个过程就是对种群进行初始化。然后根据 适应度函数计算个体的适应度，产生初始父代。如果产生的父代不满足优化准则，则重 新产生。下一代的产生过程，按照适应度选择父代个体，父代个体通过交叉操作产生下 第6 页武汉科技大学硕士学位论文 一代个体。同时产生的所有子代个体在变异概率的作用下，进行变异操作。这样子代的 适应度在重新进行计算，子代代替父代成为新一代的父代，这一个过程循环执行，直到 算法满足优化准则算法结束。 问题 j r 确定问题解答的染色体 j r 生产初始种群 1r - j 计算种群适应度函数 上 是否收敛问题最优解 j r n 0 选择高适应值进行繁殖 1r 输出最优解 ， 交叉 1r 变异 图2 1 遗传算法流程图 遗传算法过程： b e g i i l t 卜o 初始化p ( t ) 评价p ( t ) w 1 l i l e ( 终止条件不满足) d o b e g i l l 武汉科技大学硕士学位论文 第7 页 重组p ( t ) 以产生c ( t ) 评价c ( t ) 从p ( t ) 和c ( t ) 中选择p ”1 ) t 卜什1 e n d e n d 2 3 遗传算法的操作 2 3 1 编码 遗传算法的关键问题是在确定需要优化问题的目标函数和约束条件之后，如何对需 要求解的问题进行编码操作。 在h o l l 趴d 的工作中主要采用的是二进制的编码方法。由于h a m m i n g 悬崖的存在【1 8 j ， 二进制编码方法在函数优化的过程中有着十分明显的缺陷。一个十分简单的例子 0 1 1 1 1 1 1 1 和1 0 0 0 0 0 0 0 在空间中属于相邻的两个点，但是在基因型的空间中却有着最大 的距离，要翻越这个悬崖所有的个体都需要变位，操作十分繁琐，所以二进制编码方法 局限性太强。目前常用的编码方式大致由：二进制编码、实数编码、整数或字母排列编 码和一般数据结构编码这四种方案。 在函数优化的问题中，实数编码方法最为有效，许多文献已经对这类方法进行了广 泛的验证。 从编码的结构来看，编码方法则可以分成这样两类：一维编码和多维编码。在许多 的实际问题中，采用的是一维编码方法，当然对于一些复杂的问题，采用一维编码无法 完整表达的时候，可以采用多维编码方法，本文后面的章节在解决实际问题中两种方法 都会采用。 在编码的过程中，任何一种编码方法必须具有下面几个方面的特质： 1 不冗余性编码到解码的过程的映射必须是1 对1 的情况； 2 合法性编码的任意排列对应着一个解； 3 完备性任意解都有一个编码与其相对应： 4 l 撇a r c b 趾某个基因的等位基因的含义不依赖于其他基因。 2 3 2 适应度和选择 个体的适应度大小决定了个体基因是否有机会能够遗传到下一代中，个体的适应度 越高，则被选中的几率就越高。计算个体的适应度，必须先确定适应度函数，在作业车 间调度问题中，适应度函数一般就采用目标函数【1 9 。2 0 1 。选择是遗传操作中的主要操作方 法，在近几十年的研究中，提出并验证了许多的选择方法【2 1 1 ，目前常用的方法主要有下 面几类： 第8 页武汉科技大学硕士学位论文 赌轮盘选择； 竞争选择； 排序与比例变换； + 1 选择； 本文在下面的调度研究中采用比例选择的方法来计算个体的生存概率： 号= 石芝- ( m 为种群的大小，z 则是个体f 的适应度) ，采用赌轮盘方法选择新 筒 一代种群。 2 3 3 交叉和变异 交叉是遗传算法中的主要操作之一，交叉的目的就是为了产生新个体( 基因结构) ， 产生的这些新个体会同时保留两个父代的特性。交叉的方法主要有：单点交叉；多点交 叉；均匀交叉；洗牌交叉；缩小代理交叉【2 2 1 。在实际的应用中，主要使用单点交叉以及 多点交叉方法，下面以一个单点交叉实例为例进行说明。 父代1 父代2 1 1 0 0 0 0o 0 0 11 1 0 0 0 00 0 1 1 o 0 0 1 0 10 0 1 1o 0 0 1 0 1o 0 0 1 子代1 子代2 图2 2 单点交叉 如图2 2 所示，在父代1 和父代2 中随机的选择一个交叉点，然后两个父代将标记 位置之后的片段进行互换，这样就形成了新的子代1 和子代2 。 变异从生物进化的角度来说，保持了种群的多样性，使后代朝着更加有利于生存的 方向进化发展。遗传算法中的变异借鉴了这类理论，通过染色体的变异，使得算法避免 过早的收敛，变异保证了算法在进化过程中有新个体的加入。变异的操作过程并不复杂， 按照给定的变异概率，在染色中随机的选择某个位置，改变基因编码，从而达到变异的 目的。下图可以简单的说明一个变异的过程。 图2 3 变异 图2 3 说明在这样一个染色体中，随机的选择了第一个基因“1 ”，然将其变为了“0 ”。 武汉科技大学硕士学位论文第9 页 2 4 遗传算法的特点 传统的优化方法主要有三种：枚举法、启发式算法和搜索算法瞄】。 1 枚举法 将解空间中的所有解，全部枚举出来，然后选出最优的解。采用枚举法在小规模的 模型中可以求解，但是当解空间比较大的时候，问题比较复杂的时候这种方法的求解效 率比较低。 2 启发式算法 针对问题提出一种启发式规则，根据规则求得最优解。采用启发式方法求解效率高， 计算结果也比较准确。采用这种方法需要对研究的问题找出适合其自身的启发式规则， 通用性比较低，不同的问题采用的规则也不一定相同，因而很难将其扩展到其他问题上。 3 搜索算法 在可行解集合中的一个子集合中进行搜索找到最优解。该方法的缺点是，采用这种 方法，不一定能够保证求得问题的最优解或者近似最优解，不过，适当的采用启发式的 规则，在求得解的质量以及求解效率上有一定的保证。 随着制造环境的复杂程度越来越高，制造技术也越来越高，需要寻求一种以有限的 代价来解决问题的通用方法，遗传算法提供了一个有效的途径，它不同于传统的搜索和 优化方法。主要区别在于： ( 1 ) 自组织、自适应性。基于自然法则适者生存的理念，在遗传算法中，适应度值较 高的个体容易被保留下来，适应度值低的个体则容易被淘汰。经过选择、交叉和变异这 些遗传操作，产生的后代相比于父代对于环境的适应程度更高，后代会按照更加适应环 境的方向累积发展【2 4 彩】。遗传算法并不需要详细描述问题的所有特点，也不需要针对问 题的不同的特点采取不同的方法措施，因此相比于其他算法，使用遗传算法对于解决复 杂的非结构化问题具有十分明显的优势。 圆遗传算法的并行陛。遗传算法的本质就是并行操作，其搜索方法并不是单点的搜 索，而是按照并行的方式搜索一个种群中的所有可行解。遗传算法的并行性有两个特点， 内在并行性和内含并行性。前者指其并行方式是所有的种群各自独立的演化计算，在算 法的运行过程中，没有任何通信，在算法结束后才进行比较，选出其中的最优个体。后 者是指遗传算法在搜索过程中是以种群为基础进行的，这样就能够保证算法可以以比较 少的计算次数获得最优的结果。 ( 3 ) 遗传算法对于其他辅助知识的要求不高，只需要建立问题的目标函数和适应度 函数就可以了 2 6 。2 7 1 。 ( 4 ) 遗传算法可以直接使用。 ( 5 ) 遗传算法强调的是概率的转换原则。 ( 6 ) 遗传算法对于给定的问题，可以产生多个潜在的解，最终的最优解可以由算法 的设计者自行确定，例如在多目标的优化问题中，最优解并不是唯一的，其解是一组的 p a r e t o 解【2 8 1 。 第1 0 页 武汉科技大学硕士学位论文 2 5 遗传算法的应用范围 遗传算法本质上是提供了一种求解复杂系统问题的一类框架，对于问题的具体的领 域并没有强制性的要求，正因为这个特点，遗传算法在使用性上面比其他的算法更具有 优势，能够广泛的应用于许多研究领域，下面介绍遗传算法涉及的一些领域： 1 函数优化 这是遗传算法的常用领域，遗传算法适应程度高搜索能力强的特点，特别实在多目 标的函数优化方面，遗传算法具有十分明显的优势，传统的优化方法对于这类问题求解 难度较大，遗传算法则可行。 2 组合优化 组合优化问题中，伴随着问题的复杂程度过高的问题，传统枚举方法对于这类优化 问题，由于搜索范围太大，虽然枚举法在理论上可以求得最优解，但是在实际求解过程 中，由于计算量太大，基本上无法进行优化。遗传算法对于这类问题，依靠其先天搜索 能力强的特点，本质上并行的特点，采用计算机技术，在这类问题上比较容易求得解。 例如背包问题、装箱问题等，遗传算法都成功的运用在这些优化问题上【2 9 。3 0 】。 3 生产调度 这是一类比较复杂的问题，常规的优化算法在求解该类问题过程中，面对复杂的条 件，以及各种变量，计算根本无法展开，遗传算法则通过本身的遗传操作，对于这类问 题的优化也有着十分明显的效果。 4 图像处理、识别 这类问题是计算机图像处理中的一类难题，计算机在对图像进行提取、识别、扫描 的过程中，不可避免的会产生一定的误差，重点是如何减少处理过程中的误差。如何控 制这些误差是优化的重点问题。遗传算法在这个领域中也可以进行一些优化操作。 武汉科技大学硕士学位论文 第1 1 页 第三章车间调度数学模型与研究方法 3 1 作业车间调度问题 据相关资料表明，生产企业在制造的过程之中有9 5 的消耗是发生在非切削的过程 当中。制造企业的生产计划和控制的问题在调度类问题中，是最具有典型代表意义的， 因此越来越多的学者开始研究作业车间调度类问题，他们各自使用不同的方法研究这类 问题，并且也取得了丰硕的成果。如何合理的安排生产计划，合理的进行调度是目前企 业在生产过程中面临的主要问题。作业车间调度作为其中最为关键的一个环节，是提高 企业生产效益以及可靠性的关键问题。 3 1 1 作业车间调度问题的数学描述 作业车间调度一般这样描述：一个需要加工的作业集中有以个工件，加工系统中存 在一个可用的加工机床集，共有册台加工机床。这个作业集需要在这个加工集上进行加 工制造。作业集中的每个工件加工完成一共需要七道加工工序，每一道工序均可以在加 工机床集上的若干台机床上进行加工。加工机床集中的每台加工机器在同一时刻，只能 加工作业集中某一个工件的某一道工序，不能同时加工两道工序，同时该道工序必须遵 循该工件的前道工序已经加工完成后才能进行加工的原则。 一个3 工件、3 机床的作业车间调度问题如下表3 1 所示： 表3 1j s p 调度 j s p 问题的数学模型： 作业车间调度类问题主要是以最大完工时间最小化为目标函数( m a k e s p a l l ) ，求得 所有可行解的工件加工完工时间，在这样一个解空间中，求得其中最小的加工完工时间， 这个最小值就是最优解，作业车间调度的数学模型如下： 作业车间调度的数学模型： ，2 ：工件数肌：机床数 第1 2 页武汉科技大学硕士学位论文 f ：工件序号七：机器序号 ：工件的工序号 乃：工件f 的第道工序的加工时间 s 毋：工件f 的第j 道工序在机器七上的完工时间 f l 工件f 的第，道工序在机器后上加工 = io 其他 = l 工件f 的第，_ 道工序以及工件e 的第g 道工序都在机 器k 上加工在机器址加工工件i 优先e 0 其他 目标函数如下所示： m i nc 一= m i n m a ) 【 m a ) 【。砖) ) 公式( 3 1 ) 约束条件： e 独- e i ( 一1 ) g 乃 公式( 3 2 ) f ，z ， e 业- 毛k 公式( 3 3 ) p ，f 玎， 公式3 1 为目标函数，求得最大完工时间的最小。公式3 2 是指工件在加工的过程中， 有加工先后顺序的约束，同一工件前后相邻之间的工序之间，工件f 的第- 道工序必须在 _ 一1 道工序完工后才可以开始加工。公式3 3 是指对于机器的约束，工件的加工过程中 同时存在对于机器资源的约束，在任何一个确定的时刻，机器七上加工的工件是唯一确 定的不存在多个工件以及多道工序的问题。 3 1 2 作业车间调度问题的特点 作业车间调度问题存在分配、时间以及路径这三种决策问题。分配决策问题是指工 件的加工先后顺序，时间决策则是指各个工件的各道工序在机床上的加工时间【3 1 】，路径 问题则是工件在加工过程中，针对工件的各道工序如何分配相应的加工机床的决策。 作业车间调度类问题的特点是多个工件在有限的加工集机器上进行加工，如何合理 武汉科技大学硕士学位论文 第1 3 页 的按照工件的工艺顺序分配加工工件和加工机器。合理有效的分配不仅能够使工件的加 工时间达到最优化，还可以提高生产效益减少加工成本。在实际生产过程中车间调度类 问题还具有下面四个特点： 1 复杂性 车间调度类问题是在等式或者不等式这类约束条件下，求得某项指标的优化，常规 的优化方法求解该类问题的时候理论上可以求得最优解，但实际上由于计算量过大，难 于求得期望的最优解或者近似最优解。 2 动态性 在调度过程中存在着各种动态随机因子。这些动态因子会引发各种突发事件，这样 就增加了车间调度类问题的复杂性，使得问题求解更加复杂，例如生产计划的改变、交 货期的延误加工机器损坏、库存容量不足或者交货期延迟等等问题，如何及时对这类突 发事件做出反应是调度过程中的一个难题。 3 多约束 车间调度中同时存在约束条件多的情况，例如在加工工件的过程中，同一个工件， 必须在该工件的前一道工序完成之后才能够开始加工后面的一道工序。同时正在加工的 加工机床在同一时刻只能够加工某个工件的某一道工序，不存在能够同时加工多个工件 工序的情况。 4 多目标 实际的车间调度过程中，优化的性能指标不一定是单个目标，有可能是多个目标的 集合，这些优化的性能指标之间有可能存在交叉类的问题。车间调度类问题的目标主要 可以分为这三类：基于交货期的目标、基于工件加工完工时间的目标和基于生产制造成 本最优的目标 3 2 1 。 3 2 柔性作业车间调度 3 2 1 柔性作业车间调度 在传统的作业车间调度问题中，作业集中的待加工工件的每一道工序都在确定的机 器上进行加工。 柔性作业车间调度( f l e x i b l ej 0 b s h o ps c h e d m i i l gp r o b l e m s ) 是指一类特殊的作业车 间调度问题，在这一类问题中加工工件不存在机器的约束。在作业车间调度问题中，待 加工工件的每一道工序已经预先指定了加工机器，工件可以按照指定机器进行加工。而 在柔性作业车间调度中，由于存在加工路径柔性的问题( 机器可选) ，工件的某一道工序 可能由一台或一台以上的机器均可加工。与传统的作业车间问题相比，柔性作业车间调 度问题因为柔性路径的存在，工件在加工的过程中有多台加工机器可选，因此这类调度 问题更加复杂，算法的设计过程也更加的麻烦。 第1 4 页 武汉科技大学硕士学位论文 表3 2 完全柔性车间调度 根据机器的占用情况，在柔性作业车间中，又可以分为完全路径柔性作业车间调度 和部分路径柔性作业车间调度。作业集中的工件的每道工序可以选择所有的加工机器完 成的加工称之为完全柔性作业车间调度；工件的每道工序只能选择部分加工机器进行加 工的称之为部分路径柔性作业车间调度【3 3 。3 4 1 。表3 1 表示一个完全的路径柔性作业车间， 表3 2 表示一个部分路径柔性作业车间。 表3 3 部分柔性车间调度 工件和工序m lm 2m 3m 4m 5 m 6 4 所有的机器栏下面都有数字的，表示一个工件的某道工序在所有的机床上均可以进 行加工。“ 表示该机器不能够加工这道工件的某个工序，如第一行就是指，工件1 的 - - 5 2 4 - 4 5 k 4 5 - - - - 5 2 5 8 - - 6 4 3 3 - - 9 5 - i 2 3 l 2 3 1 2 l 2 3 饥阢研晚晚晚西西饥m m 如 如 几 武汉科技大学硕士学位论文 第1 5 页 第1 道工序不能使用机床3 ，4 ，5 进行加工。 j i 表示l 号需要加工的工件，这个工件有3 道加工工序，从表2 1 这个完全路径柔 性车间调度来看，该道工序的所有工序均可以在全部的6 台机床上进行加工，加工时间 分别为：1 ，4 ，6 ，2 ，3 ，4 。表2 2 这个部分柔性作业车间调度，j l 的第一道工序只能够在1 ，2 ，6 这三台机床上进行加工，加工时间分别为6 ，4 ，4 。在实际的加工系统中，并不可能所有 的机器均可以加工任意工件的所有工序，所以相比于完全柔性车间调度，部分柔性车间 调度更加符合实际的加工系统。 3 2 2 柔性作业车间调度数学描述 柔性作业车间调度主要是指在一个生产系统中，有一个需要加工完成的作业集，在这 个加工集合中有n 个需要加工的零件，集合可以表示为，= p 。，j 2 ，j 行) 。同时有一个加 工机床集合，这个集合中共有m 台可用的加工机床，集合可以表示为m = ( m 。，m 2 ，m 矾) ， 每一个需要加工的零件都需要经过若干个加工工序才可以完成。 d 壮可以这样定义，作业集中的门件的第，道工序需要在机床集中的机器七上进行 加工，同时由于工件的工序存在多种加工路径的情况，这道工序可以选择一台或以上的加 工机器加工，并且这道工序在不同的加工机床上所花费的加工时间也不一样。 f ：工件的序号；f = 1 ，2 ，3 刀 后：机器的序号；七= 1 ，2 ，3 肌 歹：加工工序号 ：工件f 的加工工序数 ：机床后上加工f 的第道工序所花时间； ：工件f 的第，道工序起始时间； ：工f 的道工序结束时间； 瓦：工件f 的，道工序加工时间； 月：一个无穷大的正整数； c 。：每个加工工件所有工序完成后的时间； c n 。：最大完工时间； 第1 6 页武汉科技大学硕士学位论文 f 1 工件f 的第j 道工序在机器址加工 x 驰= io 其他 f 1d 先于d c f 在机床k 上加工 y 舭21 lo 其他 约束条件： sq 七x l j l cx t 壮冬eq f = 1 ，2 ，玎 七= 1 ，2 ，朋1 j f 办 q _ ，j f u + 1 ) f = 1 ，2 ，刀 1 j 乃 ， c i c 眦 f = 1 ，2 ，z 1 _ ，办 ， s + e 独s 矿+ r ( 1 一y