（机械制造及其自动化专业论文）基于遗传算法的fms调度问题研究.pdf

摘要 论文题目：基于遗传算法的f m s 调度问题研究 学科专业：机械制造及其自动化 研究生：王海霞 指导教师：李德信副教授 摘要 签名i i ! 鱼墨 签名：d 翱毫。i f m s 控制系统的高效性和柔性主要取决于其调度的水平，良好的调度能预先解决生产 中的干扰，缩短产品的生产周期，保证准时交货。因此，寻求有效的调度方法和优化技术 实现最合理的f m s 调度是一个值得研究的课题。 本文针对f m s 调度问题的调度方法及优化算法进行了研究，主要研究工作如下： 针对f m s 调度问题的编码方法及其实现进行了研究，根据实际情况以及在对以往编码 方法分析的基础上，给出了基于工序的编码方法，该编码方法操作简单、容易理解，且能 够很好地反映调度问题的实质；针对该编码方法的初始种群的生成方法进行了研究，给出 了染色体的随机生成方法和交换工序与其前驱工序位置的方法对非法个体进行修正的策 略，并对修正后的个体进行调度加工过程仿真，验证了编码方法、初始化群体的生成方法 和修j 下策略的可行性。 在基于工序编码方法实现的基础上，运用自适应遗传算法对静态调度优化问题进行了 研究，分析并给出了目标函数及其评定方法、三个遗传算子的设计和与之相适应的自适应 遗传算法，并以实例验证了该算法的可行性和有效性。 对三种常见的动态事件( 急件到来、设备故障、订单取消) 的重调度控制方法进行了 研究，并在静态调度问题研究的基础上，运用自适应遗传算法对动态调度问题进行了研究， 获得了动态调度的控制策略和重调度方法。此控制策略和重调度方法可以较好地解决由于 动态事件的出现而导致的静态调度方案不再适用的问题，从而保证了f m s 系统在有扰动时 也能持续地运行。 关键词：刚s 调度；自适应遗传算法；工序编码 a b s t r a c t t i t l e ：t h es t u d yo ff m ss c h e d u l l n gp r o b l e mb a s e do n g e n e t i ca l g o r i t h m m a j o r ：m a n u f a c t u r i n ga n da u t o m a t i o n n a m e ：h a i x i aw a n g s g n a t u r e ：趁堑业鱼乒 s u p e r v i s o r ：a s s o c i a t ep r o f d e x i nl is i g n a t u r e ： a b s t r a c t 眦。l f m sc o n t r o ls y s t e mm a i n l yd e p e n d so nt h ee f f i c i e n ta n df l e x i b l es c h e d u l i n g af i n e s c h e d u l i n gc a nb eag o o ds o l u t i o no f p r e - p r o d u c t i o nd i s r u p t i o n s ，a n dc a ns h o r t e nt h ep r o d u c t i o n c y c l et on l s r i ot i m e l yd e l i v e r y s oi ti saw o r t h ys t u d yt of m da l le f f e c t i v es c h e d u l i n ga n d o p t i m i z a t i o nt e c h n o l o g yt oa c h i e v et h em o s tr e a s o n a b l es c h e d u l i n go ff m s s p e c i f i c a l l y , t h e m a i nr e s e a r c hw o r kt h i sd i s s e r t a d o nc o r l c e r u si sa sf o l l o w s ： i nt h i sp a p e r , am e t h o db a s e do ne n c o d i n gp r o c e s si ss t u d i e d ，w h i c ha n a l y z e dt h ea c t u a l c o n d i t i o ni np r o d u c t i o na n dp r e v i o u sc o d i n gm e t h o d s t h ee n c o d i n gm e t h o di ss i m p l e ，e a s yt o u n d e r s t a n da n dc a nb e t t e rr e f l e c tt h ep r o b l e mo f s c h e d u l i n g a c c o r d i n gt ot h em e t h o d ，am e t h o d t h a tg e n e r a t i n gi n i t i a lc h r o m o s o m e sr a n d o m l ya n dap l a nt h a te x c h a n g i n gt h ep o s i t i o nb e t w e e n o n ep r o c e s sa n da n o t h e rt oc o r r e c ti l l e g a lc h r o m o s o m ea r cp r e s e n t e d , a n dt h e n , t h el e g a l i n d i v i d u a li su s e di np r a c t i c a lp r o c e s st oc o n f i r mi t sf e a s i b i l i t y b a s e do nt h em e t h o do f c o d i n gp r o c e s s e sa n dt h eu s eo f a d a p t i v eg e n e t i ca l g o r i t h m ，t h e s t a t i c s c h e d u l i n gp r o b l e mi ss t u d i e d a tt h es a m et i m e ，t h em e t h o do f e v a l u a t i n gt h eo b j e c t i v e f u n c t i o n ，t h ed e s i g nm e t h o d so f t h r e eg e n e t i co p e r a t i o n sa n da na d a p t i v eg e n e t i ca l g o r i t h ma r e p u tf o r w a r d ，a n dt w oe x a m p l e sa r ep r o v i d e dt od e m o n s t r a t et h ef e a s i b i l i t ya n de f f e c t i v e n e s so f t h ea l g o r i t h m t h e r e - s c h e d u l i n gc o n t r o lm e t h o do f t h r e e d y n a m i ce v e n t s ( t h ea r r i v a lo f n e w p a r t s ， m e c h a n i c a lf a i l u r e s ，c a n c e l e do r d e r s ) a r cs t u d i e d ，a n db a s e do nt h es t a t i cs c h e d u l i n gp r o b l e m ， t h ea d a p t i v e g e n e t i ca l g o r i t h m i su s e df o rt h es t u d yo f d y n a m i c s c h e d u l i n g i nt h i sp a r t ， d y n a m i cs c h e d u l i n ga n dc o n t r o ls t r a t e g y a r e p u tf o r w a r d a p p l i c a t i o no f t h ec o n t r o l s t r a t e g i e sa n dr e s c h e d u l i n gm e t h o d s c a l ls o l v et h ep r o b l e mt h a tt h ea p p e a ro f d y n a m i ce v e n t s l e d t os t a t i c s c h e d u l i n gp r o g r a mi sn o ta p p l y ，s oe n s u r i n gt h ef m ss y s t e mc a nc o n t i n u et o o p t i m i z et h eo p e r a t i o ni nt h ec a s eo f ad i s t u r b a n c eh a p p e n i n g k e yw o r d s ：f m ss c h e d u l i n g ；a d a p t i v eg e n e t i ca l g o r i t h m ；e n c o d i n gp r o c e s s 2 独创性声明 秉承祖国优良道德传统和学校的严谨学风郑重申明：本人所呈交的学位论文是我个 人在导师指导下进行的研究工作及取得的成果。尽我所知，除特别加以标注和致谢的地 方外，论文中不包含其他人的研究成果。与我一同工作的同志对本文所论述的工作和成 果的任何贡献均已在论文中作了明确的说明并已致谢。 本论文及其相关资料若有不实之处，由本人承担一切相关责任 论文作者签名：二蔓姊7 年 多月z p 日 学位论文使用授权声明 1 ，i j 本人生! 鱼粕。在导师的指导下创作完成毕业论文。本人已通过论文的答辩，并 已经在西安理工大学申请博士硕士学位。本人作为学位论文著作权拥有者，同意授权 西安理工大学拥有学位论文的部分使用权，即：1 ) 已获学位的研究生按学校规定提交 印刷版和电子版学位论文，学校可以采用影印、缩印或其他复制手段保存研究生上交的 学位论文，可以将学位论文的全部或部分内容编入有关数据库进行检索；2 ) 为教学和 科研目的，学校可以将公开的学位论文或解密后的学位论文作为资料在图书馆、资料室 等场所或在校园网上供校内师生阅读、浏览。 本人学位论文全部或部分内容的公布( 包括刊登) 授权西安理工大学研究生部办 理。 ( 保密的学位论文在解密后，适用本授权说明) 粼：避凿硒日 第一章绪论 1 绪论 柔性制造系统( f l e x i b l em a n u f a c t u r i n gs y s t e m f m s ) 是一项高水平、高自动化、高效 率的制造系统，对于多品种、小批量生产具有很高的柔性和适应性。极大地满足了市场的 需求，而这种优良的特性在f m s 内部主要取决于调度技术的水平。调度闯题主要解决工 件在加工设备之间的合理安排和资源分配的问题，它的处理方法是整个系统是否具有高柔 性和高适应性的关键所在，所以对于调度问题的研究是非常有必要的。近年来，由于柔性 系统所带来的巨大的市场效益，人们投入了大量的人力，财力和时间致力于柔性系统调度 问题的研究，若取得了很大的进展。 1 1 调度问题的研究意义 为了适应市场竞争，满足客户多品种、小批量和高质量产品豹需要，柔性制造系统 ( f m s ) 从传统加工系统中应运而生。它克服了传统刚性系统的局限性，实现了高度柔 性、高度产品自动化加工，显示了极强的适应能力。因为柔性制造系统对市场具有强大的 适应能力和带柬的经济效益越束越受到厂家的青睐，极大地满足了市场多品种、中小批量 产品的需求，同时由于其巨大的灵活性而具有广阔的前景。 调度控制系统是f m s 的核心和大脑，负责整个系统的协调、优化、高效率的运行。 控制系统的商效性和柔性在很大程度上取决于f m s 调度的水平。调度技术是决定整个柔 性制造系统能否取得预期经济效益的关键技术之一。f m s 的调度指的是针对一项可分解 的工作，探讨在尽可能满足约束条件的前提下，通过下达生产指令，安排其组成部分使用 哪些资源、其加工时间及加工的先后顺序，以获得产品制造时间或成本的最优化“2 1 由 于良好的f m s 生产调度能够预先解决生产中的干扰，能蟛缩短产品在车间的流动时叫， 减少在制品库存，保证准时交货。所以从这个意义上说，如何实现最合理的f m s 调度， 是控制系统应具备的重要功能，有效实用的调度方法和优化技术的研究与应用已成为先进 制造的基础，也是提高企业生产效益的关键。作业调度与控制是管理自动化的核心技术， 调度是其中重要的一环，它在工厂经营管理、产品制造这两个层次上都占有极其重要的地 位和作用，它主要解决工件在机器上的合理安排和资源分配问题。因此，对f m s 调度问题 进行研究具有重要意义，是实现车间作业调度的合理化、自动化和集成化的重要环节，同 时。由于产品市场竞争日趋严峻，而管理水平又制约着企业的发展，所以调度技术的重要 性便日趋明显起来。随着现代生产技术与市场的快速发展。社会对生产调度的快速响应能 力和精确性提出了更高的要求。因此，对调度问题的研究既有理论价值，更有实际意义a 1 2 调度问题的发展 2 0 世纪5 0 年代调度问题受到了应用数学、运筹学、工程技术等多个领域学者的关注， 并运用运筹学中的线性规划、动态规划及决策分析等方法，研究和解决了一系列具有代表 意义的调度和优化问题。 西安理工大学硕士学位论文 2 0 世纪7 0 年代建立了调度理论的主体一经典调度理论，开始了复杂性调度问题的 研究，提出了用于研究算法有效性和问题难度的计算复杂度理论，此时许多调度问题被证 实是n p h a r d 问题3 “5 1 。7 0 年代后期经典调度理论取得了很大的进展，并且作为- 1 7 应 用数学学科已基本成熟，然而实际问题和经典调度问题( 如：j o b s h o p 问题) 还有很大 的距离，因为调度问题是制造系统中最基本、最主要、最复杂的问题之一，实际生产中没 有确定的规律可遵循，所以求解起来有很大的难度 6 1 0 因此，有关调度理论很多没有在 实际中得到足够的应用。因而仅依靠经典调度理论中基于解析优化技术和方法来求解实际 调度问题不可避免地遇到了很大困难”1 。 2 0 世纪8 0 年代初随着调度理论研究的深入和各种交叉学科的发展，这阶段各个领 域的学者一直努力于解决实际调度问题，这使得调度理论开始转向了应用研究阶段。同时， f m s 也有了一定的发展，调度开始涉及到车间内的各个生产对象，安排并协调整个车间 内的生产活动成为调度的主要任务，调度经历了从理论性研究到实际应用的发展过程。在 这样的发展背景下，出现了许多新的调度理论与方法硌 9 1 。近年来，随着计算机应用技术 的快速发展，人工智能、人工神经网络、基因遗传算法等被广泛用于解决生产车间调度问 题的研究9 o 川1 ，并取得了丰硕的成果和理论成就。 我国从8 0 年代后期才开始进入这方面的研究，目前已取得了不小的成果。随着f m s 和c i m s 技术的发展，多品种、小批量零件调度问题越来越显示出它的优越性，而其关键 是在于计算机科学和人工智能技术的飞速发展，这使得以往难以解决的实际调度问题有了 很大的突破。 纵观各种文献与研究成果 1 0 - 7 9 1 可以看出计算智能已成为人工智能研究的一个主要 方向。所以智能调度方法已成为解决实际调度问题最有效的途径和最有前途的调度方法之 一1 7 1 。与其他寻优算法相比，遗传算法的随机搜索机制具有良好的鲁棒性，所以近年来 在解决实际调度问题中得到了广泛应用1 1 2 1 。 1 3 调度问题的描述 生产调度问题是一类典型的实际调度问题，它很早就受到了生产管理者们的关注，但 那时还没有进入到理论研究的阶段，只是一些简单的思想，也没有被广泛的应用到实际中。 那时人们主要关注的问题是如何分配工作以及哪些操作者能够胜任这样的工作。起初人们 主要从应用数学的角度来研究调度问题，调度问题通常被定义为：“对一种资源进行分配 来执行一种任务”，也就是对零件进行“排序( s e q u e n c i n g ) ”的问题订1 。如g a m t n ”提出 了使用可视化的图标来表示生产的进度状况，c o e sn 4 1 阐述了一种机械的调度技术。而在 后来的生产中，针对先进制造系统，调度问题被更为具体地定义为：“生产调度是针对一 项可分解的生产任务，探讨在尽可能满足约束条件的前提下，通过下达生产指令，安排其组 成部分使用哪些资源、其加工时间以及加工顺序，以获得生产任务执行时间或成本的最优 化”1 6 1 。所以车间调度就是在一定条件下，对一个可用的加工设备集，在时间上进行加工 任务分配，以满足某个给定的性能指标。 2 第一章绪论 根据加工任务，可将调度分为静态调度移动态调度。静态溺度是指所有待安排加工的 工件均处于待加工状念，因而进行一次调度后，各作业的加工被确定，在以后的加工过程 中就不再改变；动态调度是指作业依次进入待加工状态，各种作业不断进入系统接受加工， 同时完成加工的作业又不断离开，还要考虑作业环境中不断出现的不可预测的动态扰动， 如作业加工超时、设备损坏等。实际生产调度问题往往是由j o b s h o p 和f l o w - s h o p 等基本 调度类型组合而成，丽其体现的特征是随机性的、动态的。 f m s 调度是从传统车间发展而来的，与传统作业调度没有本质区别，也是对其作业 计划中规定的各项任务按不同时间的系统状态分配给机床进行加工。但与传统调度不同的 是，必须考虑输送设备和在线存储问蘧，以及对于可能出现的计划变更并对此变更做出迅 速地调整都比传统生产的调度要求明显要高得多。 f m s 调度问题是非常复杂的问题，它般是一个多约束、多目标、随机不确定的优 化问题。在理论上，求解过程的计算量是随着问题的舰模呈指数增长，己被证明是n f 完 全问题( n o n - p o l y n o m i a lc o m p l e t ep r o b l e m s ) 孓”1 。所以对于十几台机器，多种类的零件， 即使拥有很先进的计算机技术都很难在有限的时俩内求盘问题的最优解或者近似最优解， 因此只能针对较小规模的柔性系统进行求解”。 本文在f m s 环境下，在考虑机床一种资源的情况下主要针对单件、小批量生产车 间如何安排零件在机床上的加工顺序的调度问题进行研究，同时考虑实际生产中的约束条 件和优化目标的限制，使得柔性系统能够高效、优化地运行，以确保生产的最大利润。 1 4 调度问题的优化方法 调度问题的研究方法，最初是集中在整数规划、仿真和简单的规则上，这些方法一般 都存在一定的局限性，不是调度结果不理息就是难以鼹决复杂秘题“1 。随着各种新的辊 关学科与优化技术的建立与发展，在调度领域出现了许多新的优化方法，比如神经网络、 模拟退火算法，遗传算法、禁忌搜索法等，使得调度问题的研究方法向多元化方向发展。 总结起来，现有调度问题的研究方法大体上可以分为以下几种类别： ( 1 ) 数学规划方法：即运筹学( o r ) 方法，将生产调度问题简化为数学规划模型， 采用基于枚举思想的分枝定界法解决调度最优化或近似优化问题，属于糖确方法。典型应 用有：c o x h e a d 用几个经典的m i l p ( 混合整数线形规划) 模型对炼油厂的调度优化进行建 模：s c h u s t e r 和a l l e n 建立了一个线性规划模型来分配食品加工厂里的稀有资源2 2 1 ： a d e l m a n 等人采用整数规翔技术来分配龟缆生产厂里的光纤；r o s l o f 等入泓开发了一 种基于m i l p 的算法来求解生产调度和重调度问题，并且在造纸厂和制药厂进行了应用等 等。这类方法虽然从理论上能求得最优解，但由于其计算复杂的原因而难以真正实用。对 于复杂调度问题，这种纯数学方法由于存在模型提取困难、运算量大、算法难以实现的弱 点，仅适合较小规模的调度问题1 2 5 1 ( 2 ) 基于启发式规则的调度方法：从实用角度来看，窟发式算法国其易子实现、计算 复杂度低等原因，在实际中得到了比较广泛的应用，并且不断涌现出许多新的调度规则， 西安理工大学硕士学位论文 可将其分为三类：简单规则、复杂规则、启发式规则。虽然启发式规则常被用于实际当中， 但它们一般不具有全局优化的特点1 2 6 1 。 ( 3 ) 基于人工智能( a 1 ) 的方法：a i 方法是通过提高调度方法的智能而解决各类生产调 度问题方法的总称。单一的数学方法和工具不足以解决实际的调度问题，a i 和专家系统 ( e s ) 的出现对解决调度的实时性和智能性提供了新的辅助手段1 3 0 j 。 ( 4 ) 基于仿真的方法：由于制造系统的复杂性，以致于很难用精确的解析模型对其进 行描述分析。但仿真却能提供理想模型，且可以定量地进行评估，从而对实际系统采用合 适的调度方法1 2 7 1 。仿真方法用于调度的优点有实验时间短，不受时空限制；可以测 试不同调度决策的性能，从而选择较优的调度决策；能够用分析方法解决问题并寻求可 行解。其不足之处是由于仿真具有实验的特点，很难从特定的实验中提炼出一般的规律 性；生产调度成本高：仿真结果的价值和可信度严重依赖仿真模型、仿真方法及仿真 实验输入数据；仿真的准确性受程序员判断能力和技能的限制。 ( 5 ) 计算智能方法：近年来，一些高级局域搜索法由于具有普遍适用性和较低的经验 复杂性等优点，得到了广泛的重视和应用。主要有以下几种方法： 遗传算法( g a ) ：g o l d b e r g 首次将g a 应用到实际工程系统的优化当中。由于g a 原理 和操作简单，通用性强，不受限制条件的约束，且具有隐含并行性和全局空问搜索能力， 尤其适用于处理传统搜索方法难以解决的复杂的非线性问题。在机器学习、模式识别、控 制工程等领域，尤其在生产调度领域都得到了广泛地应用。 使用遗传算法求解生产调度问题的主要工作有：生产问题到遗传编码的转换、字符串 操作符的选择和限制搜索空间的约束描述等。典型研究和应用有：s t a r k w e a t h e r 等人口 在一个啤酒厂中应用遗传算法解决了多目标j o b s h o p 调度问题，这些目标包括工厂中平 均存货时间的最小化和客户订单平均等待时间的最小化等；刘民等人3 4 用遗传算法解决 并行多机调度问题；张纪会等人口 用遗传算法进行生产动态调度知识获取，并用实例说 明了其可行性；a m a n e i o 等人3 6 1 用遗传算法来解决流程工业中能量和生产的调度优化问 题等等。如何利用g a 高效求解调度问题，一直被认为是一个具有挑战意义的难题并成为 研究的热点，近年来涌现出大量论文并取得较大进展1 3 1 1 。 然而遗传算法对于大规模的组合优化问题，搜索空间大，搜索时间较长，往往会出现 早收敛的现象；对初始种群很敏感，初始种群选择不好会影响解的质量和算法效率。目前， 人们主要从两方面入手：一是对遗传算法本身进行改进；一是与其他算法结合，取长补短。 神经网络删) 优化法：用于车间调度，主要有三类方式：利用其并行计算能力，求 解优化调度，以克服调度的n p 难题。利用其学习能力，从优化轨迹中提取调度知识。 用n n 来描述调度约束或调度策略，以实现对生产过程的可行或次优调度。 ( 6 ) 组合调度方法：由于各种调度算法都不同程度地存在不足之处，所以学者们开始 关注各种近似算法的组合研究，以弥补各自的缺点，发挥各自的优势，达到高度优化的目 标。目前，各种算法的组合应用己成为解决优化调度问题很有前途的方法”1 。 4 第一聿绪论 根据以上优化方法的分析比较，出于遗传算法是基于生物遗传和进化理论的自适应随 机搜索方法，它通过保持一个潜在解的种群进行多方向搜索，采用概率转移来选择部分个 体，创造新后代。遗传算法对优化问题没有太多的数学假设，遗传算法目前在生产调度、 设备御置、成组技术等领域都有成功的应用。遗传算法的优越性主要表现在搜索过程中不 易陷入局部最优，即使在所定义的适应度函数不连续的情况下，也能以极大的概率找到最 优解。所以本文确定采用遗传算法对f m s 调度问题进行全局寻优，获得最佳韵调度方案。 使得f m s 能够优化地运行。 1 5 调度研究存在的问题和发展趋势 调度问题多数属于n p h a r d 问题，虽然对它的研究已有多年的历史，但至今尚未形成 一套系统的方法和理论，理论研究与实际应用之间还存在着很大差距。实际应用中的调度 方法虽然能够响应系统的动态变化，僵不能保证得到最好的调度。尽管一些理论上的优化 方法能提供近似最优调度，但由于其计算的复杂性以及忽略了许多实际因素，与实际应用 还有较大的距离。 由于大多调度问题属于组合优化问题，因此寻找具有多项式复杂性的最优算法几乎是 很难的。各种近似启发式方法，如基于规则的算法等，尽管能在合理的时间内产生较满 意的调度，也广泛应用于实际，但其往往对所得的调度解的次优性不能进行评估。各种基 于统计优化的方法，如模拟退火法、遗传算法等，提供了一种解决调度优化问题的新途径， 但与其他优化算法类似，其也存在着一定程度的局限性，一般收敛到最优解很慢，且对于 判断解的最优性也很困难。 目前对生产调度的研究多数集中在解决静态和单目标问题上，但是实际生产中调度 问题的特点是多目标、全局性和动念随机性。目前，研究人员开始研究如何从控制筑略上 去考虑车i b j 调度问题，从而形成了各种控制策略指导车f 日j 调度的研究。调度控制策略就是 在系统全局的观点，如何控制调度环节使系统在全局上满足任务的要求，常见的控制策略 有并行或分布策略、分解与分组策略、人机交互策略、动态重调度策略等等。动态重调度 的控制策略就是在系统出现扰动的时候，系统启动重调度控制机制，重新安排任务组织生 产，使系统能够在不影响生产的情况下继续生产，保持生产过程的连续性。实践证明，把 调度优化算法和调度控制策略结合起来实现有效的生产控制是一种实用有效的方法。 根据上述存在的问题，对调度问题的研究主要有以下几种发展趋势： ( 1 ) 调度算法和调度系统的深入研究和开发：目前对调度算法和调度系统的研究己取 得很大进展，但由于调度问题的n p 性质而不可能在短期内取得突破性进展，这就要求人 们进一步拓宽研究范围和思路，在原来调度算法的基础上继续寻找可行的能够获得最优解 而且求解速度快的调度算法。基于人工智能、计算智能和实时智能的调度算法将会是未来 调度算法的主流。 ( 2 ) 调度专家的作用问题研究：调度专家具有丰富的经验，纯粹韵自动调度是不现实 且很赃实现的。因此，具有最终决策职责的调度专家的重要作用在任何时候都不能忽略。 西安理工大学硕士学位论文 所以研究调度专家的作用以及如何与调度系统的协调等问题也是一个重要的研究方向。 ( 3 ) 多种调度方法的结合研究：目前许多新的算法应用于调度领域，但由于需要特定 的应用环境，所以就出现了调度理论和实践的不一致性。文献1 3 4 1 就对调度算法的集成 问题进行了比较深入地研究。因此，集成各种调度算法求解生产调度问题充分发挥各种调 度算法自身的优势，是今后研究和解决实际调度问题的重要方向之一。 ( 4 ) 与其他系统的集成研究：目前制造业特别是流程工业中生产调度和过程优化控制 相互脱节，在过程控制和管理信息系统之间存在着“信息鸿沟” 3 7 1 割裂了流程企业经营 管理与生产控制。因此，只有将调度和控制综合考虑，实现信息与功能的集成才能形成一 个适应生产环境不确定性和市场需求多变性的全局优化的高质量、高柔性、高效益的智能 生产系统。所以调度系统应能与现有企业的信息基础结构进行通信与交换，并作为信息基 础结构的一部分，这也是生产调度理论和方法的研究方向之一。 总之，对车间调度领域这一具有n p ，h a r d 特性问题的研究，随着应用数学理论的进一 步发展，必然朝着集成化、柔性化、多目标化、动态实用化、高度次优化方向发展。 1 6 本文的研究内容及目的 本文主要针对f m s 调度问题的调度方法进行研究，并运用自适应遗传算法对调度问 题进行优化，寻求最佳调度方案。本文共分六章： 第一章首先概述了柔性制造系统的基本理论；然后进一步介绍了f m s 调度问题的研 究现状，包括调度问题的相关概念，研究方法，存在的问题及发展趋势；最后给出课题的 主要工作及内容。 第二章首先阐述了遗传算法的基本思想；然后对遗传算法特点进行了分析以及对基 于实数的遗传编码进行了研究，说明在实际调度问题中采用实数编码的意义；其次对遗传 参数的选择以及三个基本操作方法进行分析，给出了本文中参数的选择范围以及三个基本 操作的的遗传方法。 第三章根据对以往调度问题中编码方法的分析和对f m s 实际调度问题的分析，研 究了基于实数编码方法的实现，并给出了本文采用的编码方法及策略；然后给出了根据此 编码方法生成合理和可行的初始种群的策略；最后以实例验证了此编码策略的可行性。 第四章在基于工序编码方法产生合理的和可行的初始群体的研究基础上，以及在对 静态调度问题研究的基础上，为了获得工件在机床上更好的入线顺序，在仅考虑机床一种 调度因素的前提下，采用基于线性顺序的交叉算予以及交换基因的变异算子的自适应遗传 算法对工件的调度排序问题进行优化，以获得最佳调度方案；最后以两个实例来验证了此 算法的有效性和可行性。 第五章首先对动态调度问题进行了描述，包括动态调度类型、动态事件类型和动态 策略；然后在此基础上给出对动态扰动采用事件驱动的调度策略来处理急件到来、设备故 障、订单取消等动态问题：最后以实例验证了算法的可行性和有效性。 第六章结论与展望 6 第二章遗传算法理论 2 遗传算法理论 遗传算法( g e n e t i ca a l g o r i t h m sg a ) 是基于自然选择原理、自然遗传机制和自身适 应搜索的算法，是当代人工智能科学的一个重要分支，在解决许多传统数学难题以及常规 条件下明显失效的复杂问题时，它能够提供一个行之有效的新途径，为人工智能计算理论 的研究带来了新的发展前景，成为信息科学领域中- f q 新兴学科。在二十世纪6 0 年代， 遗传算法就由密歇根( m i c h i g a n ) 大学h o l l s t i e n 、b a g l e y h 和r o s e n b e r g 等人在其博士论 文中首先加以研究；1 9 7 5 年，由美国j h o u a n d 教授在其著作“a d a p t a t i o ni nn a t u r a la n d a r t i f i c i a ls y s t e m ，中系统进行了阐述，给出了它的基本定理和大量理论证明3 8 3 9 1 。 2 1 遗传算法的基本思想 遗传算法是从携带问题可能存在潜在解集的一个种群开始，而一个种群则由合成基因 编码的一些个体组成，实际上，每个个体是带有染色体特征的实体。染色体作为遗传的主 要载体，即多个基因的集合，其内部表现的是某种基因的组合，并决定了个体特征的外部 表现。因此，在一开始就需要把求解问题的状态空间映射为遗传空间。首先把每个可能的 解编码为向量，把向量中的每个元索称为基因，然后把所有的染色体组成群体，按给定的 目标函数对每个个体进行评价，根据目标函数值给出适应度值的大小来挑选个体，并模拟 自然遗传学原理进行组合交叉和变异，产生出能够代表新解集的种群。这个过程将导致种 群像自然进化一样的后生代种群比前代更加适应环境，末代种群的最优个体经过解码可以 作为问题的近似最优解4 0 “4 3 。 遗传算法的计算过程是一个不断优化的过程，其算法的主要操作步骤包括： ( 1 ) 编码：根据问题的实质，将问题的解用染色体编码来表示，从而将问题的状态空 间与g a 的编码空f n j n 对应。由于g a 的优化过程不是直接作用于问题参数本身，而足在 一定编码机制对应的空日j 上进行的，因此编码的选择是影响算法性能与效率的重要因素。 ( 2 ) 产生初始种群p ( t ) ：在对问题空间的变量进行编码后，随机产生一定数目的初始 染色体，这些随机产生的染色体组成一个种群。种群中染色体的数目称为初始种群的大小 或规模。 ( 3 ) 计算个体适应度：适应度即染色体对环境的适应程度，不同的问题，适应度函数 的定义方式也不同。根据问题求解相应的适应度函数值，以此来评价每个染色体的优劣， 用来作为后续遗传操作的依据。 ( 4 ) 选择操作：从当前种群中选出优良的染色体，使它有机会保留以继续繁殖后代。 判断染色体优良与否的准则是各自的适应度，染色体的适应度值越高，其被选择的机会就 越多。通过选择操作，产生了一个新种群。 ( 5 ) 交叉操作：对选择到的新个体，按某一选择机制选取两个染色体作为父染色体， 根据二者的特征进行交叉操作产生新的子个体。 ( 6 ) 变异操作：以较低的概率，在染色体上自发地产生随机的变化。变异操作的目的 西安理工大学硕士学位论文 是挖掘种群中个体的多样性，克服有可能陷入局优解的弊病。 ( 7 ) 通过上述( 4 ) 、( 5 ) 、( 6 ) 步骤的运算产生新的种群后代p ( i + 1 ) ，并判断是否满足优 化准则，如果是的话结束进化，否则把新的种群p ( t + 1 ) 作为初始种群重复进行选择、交叉 和变异操作。 ( 8 ) 经过给定次数的迭代处理或满足目标条件后，把最好的染色体作为优化问题的最 优解。 遗传算法流程图如图2 1 所示。 图2 - i 遗传算法沉程图 f i g2 - 1g e n e t i ca l g o r i t h mf l o w c h a r t 2 2 遗传算法的特点 与其他寻优算法相比，遗传算法具有优良的鲁棒性。遗传算法吸收了自然界生物系统 “适者生存”原理，从而获得了良好的鲁棒性，能够在复杂空间自动进行寻优搜索m 划。 其主要特点可归纳如下： ( 1 ) 采用编码技术：对优化问题，遗传算法不是直接处理决策变量本身的实际值，而 8 第二章遗传算法理论 是对它进行编码作为进化的载体。利用简单的编码技术和繁殖杌箭柬表现复杂的现象，适 于解决复杂的问题，尤其是求解规模复杂的优化问题。 ( 2 ) 从全局中寻优：多数传统的优化方法是单点搜索法，遗传算法是在搜索空间能够 同时处理多个个体的方法，即在搜索空间可以同时对多个解进行评价，从而提高了搜索效 率，更好地防止了算法陷入局部最优解的困境，并能够搜索到全局最优解。 ( 3 ) 对目标函数限制小：遗传算法不要求目标函数连续和可微，对目标函数几乎没有 多少限制，通过计算其适应度值的引导来进行代和代之间的启发式随机搜索，不受搜索空 问限制性假设的约束，不需要任何附属的条件，搜索效率优于传统方法。 ( 4 ) 自适应的搜索技术：多数传统方法通常使用确定性地搜索方法，即从一个搜索点 到另一个搜索点有确定地转移方法和关系，这种确定性往往使得搜索难以获得最优。而遗 传算法是属于自适应的搜索算法，采用的是基于概率的驱动原则丙非确定性规则来对空间 进行搜索。尽管这种概率机制也会产生一些适应度不好的个体，但随着进化过程的推进， 新的群体不断地产生许多优秀的个体，使整个进化过程向最优解靠近。 ( 5 ) 采用并行计算：遗传算法具有隐含并行性，可以同时对许多点并行操作，这样就 能通过大觑模并行计算来提高系统处理和求解寻优的速度与效率。 总之，由于遗传算法引入了自然生物系统“适者生存”的进化规则，与各种寻优算法相 比较，具有很好的鲁棒性，能够适应于复杂问题的求解并能够自动寻优搜索。同时又因为 其算法简单且功能强，对搜索空间一般不需要限制性的假设。所以本文将采用基于工序的 编码方法对调度闯题的解变量进行编码，用自适应交叉、变异遗传算法进行全局寻化，获 得最佳调度方案，使得调度系统能够持续、优化地进行。 2 3 遗传算法的编码 遗传算法不直接处理问题的空间参数，而是把问题转换成遗传算法空问的由一定结构 组成的染色体或个体，这一转换操作称为编码1 。遗传算法交替地在编码空间和解空间 中工作，它在编码空间对染色体进行遗传运算，而在解空间进行评估和选择运算。 如何将问题的解空问转换为编码空间的染色体的表达是遗传算法的关键，也是进行遗 传运算遇到的首要闯题。h o l l a n d 的二进制串编码方法已成为解决参数优化问题的标准编 码方式，但它很难被直接应用到与调度问题密切相关的排序优化中。直接采用十进制编码 是连续参数优化问题直接的自然描述，不存在编码和解码的过程。在实数编码情况下，将 个实数矢量在编码空间对应为一个染色体，一个实数问题空间对应为一个基因，一个实 数对应为一个等位基因。使用实数编码具有以下优点： ( 1 ) 采用实数编码的基因消除了因编码精度不够使得搜索空间中具有较优的可能解不 能够表现出来的隐患。如果对连续参数进行二进制编码，当个体编码较短时，就可能没有 足够的精度将那些好的基因组块充分地表示出来；在个体编码串较长时，虽然能提高精度， 但会使算法的援索空间急剧增大，甚至使算法无法进行下去，而造成算法的性能降低，并 且给存储和运算也带来了很大的负担。 9 西安理工大学硕士学位论文 ( 2 ) 遗传算法用实数编码表示基因，具备了利用连续变量函数具有的渐变性的能力。 渐变性表示变量小的变化所引起的对应函数值的变化也是t i e d , 的，实际中所考虑的问题多 数都为连续函数，都具有这种渐变性。遗传算法这一特征证明对某些优化问题是至关重要 的。 ( 3 ) 用实数编码可消除“h a m m i n g 悬崖”：在采用简单二进制编码时，如编码长度为3 的整数3 和4 所代表的实数在直线上是相邻的，但其在二进制编码0 1 1 和1 0 0 在h a m m i n g 距离来看是最远的。 根据以上优点，本文将采用实数编码方法对f m s 调度问题变量进行编码，即染色体 的每一位基因代表零件的一道工序，染色体的全长为调度任务中所有工件的工序数之和， 调度系统将依据染色体工序的先后顺序来进行调度，也就是说染色体代表实际操作中工件 在机床上加工的先后顺序。本文将在第三章中对实数编码实现方法进行详细研究。 2 4 遗传算法的基本操作 选择、交叉和变异算子是遗传算法“优胜劣汰”思想的主要体现，也是构成算法具备很 强的全局搜索能力的核心，利用遗传操作算子能够产生新一代种群，实现种群向更优方向 进化。 ( 1 ) 选择算子 选择算子又称繁殖或者再生，是对群体中的个体按照优胜劣汰的方式选取，并遗传到 下一代的操作，它是建立在群体中个体的适应度评价基础上，并选择适应值高的个体进行 复制。通过选择机制可以避免优秀基因的流失，能够提高全局收敛性和算法的效率。 比例选择法：比例选择法是基本的选择方法，也叫轮盘赌选择法。它的基本思想 是：个体被选中的概率与其适应度大小成正比。设群体大小为m ，个体i 的适应度 为f i ，选择概率p i 为： 冒 p j = 1 i l( i = 1 ，2 ，m ) 0 1 ) f ； j = t 1 0 式中p i 体现了个体i 在整个群体的个体适应度总和中所占的比例，个体适应度值越 大，其被选中的概率就越大。但是，采用比例选择法会因为随机数的产生而有可能使 适应度高的个体没有被选中的，而适应度低的个体反而被选中。 期望值法：期望值方法的基本思想是根据每个个体在下一代群体中的生存期望概 率值来进行随机选择运算。个体在下一代群体中生存的期望数目n i 为： ，：善：半生( i = 1 ，2 ，m ) ( 3 2 ) 屯”s f ， 最佳个体保存法：此方法的思想是把群体中最优的个体挑选出来，直接复制到下 一代种群中去，故这种方法又称为精英保护法。最优保存策略成功地改善了遗传算 第二章遗传算法理论 法的局部收敛特性，能够防止优秀个体由于复制、交叉和变异中偶然因素而被破坏， 也是一种增强算法稳定性和收敛性的有效方法。但是，应用最优保存法时，应避免 使进化计算陷入局部极值，以至于丧失了全局寻优的机会。 以上几种选择方法均以适应度为基础进行选择，这就可能在进化过程中导致遗传算法 的早期收敛的问题，可采用适应度函数尺度变换的方法来解决，此外还可采用部分个体的 替换选择法、自适应变异撅率选择法等选择方法来提高遗传算法性能。 比例选择法是最基础的选择方法，且易于实现，但是因为这种方法有可能使适应度高 的个体没有被选中，而适应度低的个体反而被选中。所以本文将采用比例选择法与最佳个 体保存法相结合的选择方法，既避免了最优个体被漏选又能保证算法在全局中寻优。 ( 2 ) 交叉算子 交叉操作是遗传算法在种群中产生新个体的主要方法，它是模拟生物进化过程的繁殖 现象，通过两个染色体的交换组合而产生新的优良品种。交叉操作具体分为两步： 第一步将已复制的放在匹配池中的个体随机两两匹配，称为双亲的染色体； 第二步对双亲染色体进行交叉繁殖，确定交叉点的位置和进行部分基因交换策略。 交叉是决定g a 收敛性的核心绦作，是最主要的遗传运算，它同时对两个染色体操作，组 合二者的特性产生新的后代。 常见的交叉操作有一点交叉、多点交叉： 一点交叉：一点交叉是由h o l l a n d 提出的最基础的交叉方式。首先随机确定一个 交叉位置，然后对换交叉点后的子串。例如：父串为( 1 0 1 1 桕0 i ) 和( o o t o i l l o ) ，若擎点 交叉位置为4 ，则后l 弋个体为( 1 0 lt l t l _ o ) 和( o o l o l 0 0 1 ) 。点交叉操作的信息量较小， 交叉点位置的选择可能带来较大的偏差。 多点交叉：为了增加交叉的信息量，遗传算法发展了多点交义的概念。首先随机 确定多个交叉位置，然后对换相应的子串。例如：两点交叉，交叉位置为2 和5 ， 父代个体同上。则后代个体为( 1 0