（机械制造及其自动化专业论文）混合批量生产的车间调度模型研究.pdf

摘要 手葡姜 本论文主要涉及的内容是混合批量生产企业的车间计划调度的算法研究。 在当今激烈的市场竞争环境中，为了生存和发展，小批量多品种的生产成为 企业的主要生产模式，这种生产方式同时具有批量和单件生产的混合生产特性。 企业为了在竞争中求生存，必须采用先进的、科学的方法和手段组织生产，努力 提高生产效率。而传统的、严格将生产类型按照单件生产或批量生产区分后组织 生产的方式已不能满足混合生产的需要，将两种生产方式进行有机的结合来组织 生产成为目前现代化企业生产调度过程中面临的新问题。 本文介绍了车间调度的概念及其发展过程、研究现状和发展趋势；对车间调 度的各种研究方法进行了简要的介绍和比较；概述了遗传算法的基本原理和步 骤，介绍了遗传算法常用的一些算子，分析了遗传算法的特点，对遗传算法在车 间调度方面的应用进行总结，并对其在车间调度方面应用的一些算子进行了讨 论。 本文研究了多种批量混合型生产方式的特点及存在的调度问题，建立了基于 混合批量的加工计划的生产调度集成框架图和数学模型。给出了基于遗传算法和 启发式规则相结合的有辅助加工时间批量混合生产类型的计划调度算法。通过与 国内外学者所提出的算法进行比较，证明了该算法的正确性和优越性，同时，对 在本文中所采用的遗传算法的相关算子进行了阐述。在理论上，该算法可以获得 全局最优解。最后通过三个不同的调度策略，证明该算法能够取得较佳的调度性 能。 关键词：混合批量生产；遗传算法；启发式算法；批量调度 广东t 业大学t 学硕上学位论文 a bs t r a c t t h i sa r t i c l em o s t l yr e f e r st ot h eh y b r i dp r o d u c t i o ns t y l e w i t ht h eg r o w i n gc o m p e t i t i o no ft h ew o r l dm a r k e t ，m o r ea n dm o r ee n t e r p r i s e s a d o p tv a r i e t i e sa n ds m a l l - b a t c hp r o d u c t i o nm o d e a st h em a i n l yp r o d u c t i o ns t y l e t h e p r o d u c t so ft h i sp r o d u c t i o ns t y l ea r ea l w a y sm u l t i p l ew i t hs m a l lb a t c h a n dh a st h e c h a r a c t e ro fc o n t i n u o u sa n dd i s c r e t i o n a tt h es a m et i m e ，t os u r v i v a la m o n gt h e c o m p e t i t i o n ，e n t e r p r i s e sm u s ti m p r o v ep r o d u c t i v i t y t h e ym u s ta d o p t t h eb a t c h p r o d u c t i o n s t y l e a sw e l l s ot h es i n g l e p r o d u c t i o ns t y l e c a nn o tm e e tt h e d e v e l o p m e n to ft h ec u r r e n te n t e r p r i s e s w en e e dt o c o m b i n et h et w op r o d u c t i o n s t y l e s t h i sa r t i c l ei n t r o d u c e dt h ec o n c e p t i o n ，d e v e l o p m e n ta n dt h em a i nr e s e a r c h e si n c u r r e n ta n di nt h ef u t u r ej o bo fs h o ps c h e d u l i n g s o m er e s e a r c hm e t h o d so nt h ej o b s c h e d u l i n ga r ei n t r o d u c e da n dc o m p a r e d b a s i cf o u n d a t i o n ，p r o c e s sa n do p e r a t i o n s o fg e n e t i ca l g o r i t h ma r es t a t e db r i e f l y a n dt h ec h a r a c t e r i s t i c sa n dt h et h e o r e t i ca r e d i s c u s s e d t h ec h a r a c t e r i s t i c so fh y b r i dp r o d u c t i o ns t y l ea r es t u d i e da n di t s s c h e d u l i n gi n t e g r a t i o nd i a g r a mi se s t a b l i s h e d an e ws c h e d u l i n ga l g o r i t h mb a s e do n g e n e t i ca l g o r i t h ma n dh e u r i s t i cr u l ei sp r o p o s e d 。 c o m p a r e dw i t h a n o t h e r s c h e d u l i n ga l g o r i t h m sp r o p o s e db ys o m eo t h e rp e o p l e ，i ti sp r o v e dt h a t t h i s s c h e d u l i n ga l g o r i t h mi sc o r r e c ta n de x c e l l e n t a n dd i s c u s s e dt h ea r i t h m e t i co p e r a t o r s o ft h eg ap r o p o s e di n t h i sa r t i c l e t h e o r e t i c a l l y ，t h eb e s to v e r a l ls i t u a t i o nc a nb e a c h i e v e d f i n a l l y ，a ne x a m p l eo fs c h e d u l i n g i s g i v e n b yt h e r e s u l to ft h r e e s c h e d u l i n gs t r a t e g i e s ，i ti ss h o w e dt h a tt h i sa l g o r i t h mc a na c q u i r eg o o dp e r f o r m a n c e o fs c h e d u l i n g k e yw o r d s ：h y b r i dp r o d u c t i o ns t y l e ，g e n e t i ca l g o r i t h m ，h e u r i s t i cr u l e ，b a t c h s c h e d u l i n g 独创性声明 独创性声明 秉承学校严谨的学风与优良的科学道德，本人声明所呈交的论文是我个人在 导师的指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以 标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，不包 含本人或其他用途使用过的成果。与我一同工作的同志对本研究所做的任何贡献 在论文中都做了明确的说明，并表示了谢意。 本学位论文成果是本人在广东工业大学读书期间在导师的指导下取得的，论 文成果归广东工业大学所有。 申请学位论文与资料若有不实之处，本人承担一切相关责任，特此声明。 指删币签字驰彳 论之瓣纛狲。2 0 0 考年岁月2 6 日 、 第一章绪论 1 1 研究背景及意义 第一章绪论 企业的生产目标、生产组织结构、生产方式和方法，都必须适应生产的环境 和市场需求的变化。在当今以多样化为特征的市场需求条件下，生产组织方式和 方法显得更为重要，并且日益复杂化。 在我国多数制造企业中，存在设备利用率低、交货期长、生产准备周期长、 费用高、自动化水平和柔性水平低、质量不稳定，资金周期慢等问题。企业要在 激烈的市场竞争中求生存、谋发展，除了转变现有的经营机制外，最重要的是运 用先进的制造技术与管理方法，以提高企业响应市场的快速应变能力，这就要求 企业具有快速的产品开发能力，尽可能短的产品生产周期，较高的产品质量，较 高的设备利用率。而车间管理调度系统的目标就是合理的安排车间生产作业计 划，充分利用现有的各种资源，消除生产瓶颈，实现均衡生产，保证按时交货， 提高设备的利用率，提高零部件加工质量，缩短生产周期，减少在制品，减少或 消除加班，降低零件加工成本，准确迅速地为上级部门提供可靠的各种统计数据。 因此，车间调度系统运行效率的高低，以及其本身的合理性、实用性，对于一个 企业能否获得较高的经济效益，起着非常重要的作用。现在，车间调度管理成为 组织现代化企业生产的科学哲理和工厂自动化的重要组成部分，在整个现代化企 业中，起着越来越重要的作用。 当前企业的生产方式已由传统的大批量生产逐渐转变为多品种中小批量的 生产方式，但是在本实验室自主开发的车间作业计划m e s 系统的实施过程中，发 现不少企业在多品种小批量生产的过程中，往往会有大批量生产的订单的加入， 形成各种不同批量混合作业的情况。针对此种生产类型，当前多数的车间作业计 划系统都未能很好地解决。如何解决在各种不同批量混合作业下批量划分问题， 成为本文所研究的重点。 目前，车间作业调度的工作大多是依靠传统的数学模型或是调度人员的经验 来完成的。对于一些混合批量调度的情况则难以满意的解决。因此，研究车间调 度算法，开发一个运行高效、使用简单、便于人机交互的调度系统，对于促进车 广东工业大学硕士学位论文 间生产管理的发展和企业生产资源的合理配置、提高企业在市场中的竞争力具有 重要的意义。 1 2 国内外研究现状 1 2 1 现代制造业的现状及其发展趋势 制造业是国民经济最重要的支柱产业。所有原材料转化为物质产品的行业都 可以称之为制造业。在工业化国家，约有四分之一的人口从事制造业，约7 0 8 0 的物质材料来自制造业。13 随着现代信息技术、现代制造技术和全球化的发 展，制造业的发展技术、发展模式发生了较大的变化，出现了所谓现代制造业。 其中生产自动化技术经历了以下四个发展阶段：( 见表卜1 ) 。 阶段特征举例年代 机械化机器代替人力车床 1 7 7 5 点自动化对机器的自动控制n c c n c 1 9 6 0 替代了人为控制 自动化孤岛在部分生产过程管 m r p - i i 1 9 7 0 理的局部环境中， f m s 点自动化的综合应c a d c a m 用 计算机一体以计算机综合应用自动化和自动的工 1 9 9 0 化生产为基础的自动化和厂 对生产系统的全部 作业进行管理的决 策支持系统 表1 1现代生产自动化技术的发展阶段 t a b l e 1 1d e v e l o p m e n to fm o d e r na u t o m a t i ct e c h n i c a l 制造业信息技术是将原材料有效的转变成产品的技术，是制造业赖以生存和 发展的技术基础，它表现在c a d 、c a m 、c a p p 、p d m 、e r p 、m i s 、v p d 等技术的发 展。比。h 1 在现代制造业中，计算机可以对生产过程进行智能化控制。 计算机 通过各种仪器、设备适时收集生产过程的数据，然后按照一定的数学模型进行分 2 第一章绪论 析判断，并根据预设的最佳标准自动调节设备，对生产过程加以调整，实现最佳 加工状态。 现代制造业的最大的特点是制造业的信息化。制造业信息化是将信息技术、 自动化技术、现代管理技术与制造技术相结合，带动产品设计方法和工具的创新、 企业管理模式的创新、企业间协作关系创新的过程。制造执行系统m e s ( m a n u f a c t u r i n ge x e c u t i o ns y s t e m ) ，是一个工厂层的信息系统，介于企业领导 层的计划系统与生产过程的直接工业控制系统之间。它以当前视角向操作人员 管理人员提供生产过程的全部资源( 人员、设备、材料、工具和客户要求) 的数据 和信息。m e s 在工厂综合自动化系统中起着中间层的作用。在e r p 系统产生的长 期计划的指导下，m e s 根据底层控制系统采集的与生产有关的实时数据，对短期 生产作业的计划调度、监控、资源配置和生产过程进行优化。功能模块包括工序 详细调度、资源分配和状态管理、生产单元分配、过程管理、人力资源管理、维 护管理、质量管理、文档控制、产品跟踪和产品清单管理、性能分析和数据采集 等模块。在m e s 下层，是底层生产控制系统，包括d c s 、p l c 、n c c n c 或这几种 类型的组合。【) j 【o j 如图1 - 2 所示为制造执行系统的三层模型。 制造资源计划 e r p 么、 ，7 制造执行系统 m e s 8 酋 现场控制系统 d c s p l c 图卜2 制造执行系统的模型 f i g 1 1t h em o d e lo fm a n u f a c t u r i n ge x e c u t i o ns y s t e m 现代制造业具有以下几个特点： 1 制造技术的实用性 计划层 执行层 控制层 介u介u介u 广东工业大学硕十学位论文 现代制造技术最重要的特点在于，它首先是一项面向工业应用，具有很实用 性的新技术。从现代制造技术的发展过程，从其应用于制造全过程的特别是达到 的目标与效果，无不反映这是一项应用于制造业，对制造业、对民经济的发展可 以起重大作用的实用技术。 2 先进制造技术应用的广泛性 现代制造技术相对传统制造技术在应用范围上的一个很大不同点在于，传统 制造技术通常只是指各种将原材料变成成品的加工工艺，而现代制造技术虽然仍 大量应用于加工和装配过程，但由于其组成中包括了设计技术、自动化技术、系 统管理技术，因而则将其综合应用于制造的全过程，覆盖了产品设计生产准备、 加工与装配、销售使用、维修服务甚至回收再生的整个过程。 3 制造技术的动态特征 由于现代制造技术本身是在针对一定的应用目标，不断地吸收各种高新术逐 渐形成、不断发展的新技术，因而其内涵不是绝对的和一成不变的。 4 制造技术的集成性 传统制造技术的学科、专业单一独立，相互间的界限分明。现代制造技术由 于专业和学科间的不断渗透、交叉、融合，界线逐渐淡化甚至消失，技术趋于系 统化、集成化、己发展成为集机械、电子、信息、材料和管理技术为一体的新型 交叉学科。 5 制造技术的系统性 传统制造技术一般只能驾驭生产过程中的物质流和能量流。随着微电子、信 息技术的引入，使现代制造技术还能驾驭信息生成、采集、传递、反馈、整个的 信息流动过程。现代制造技术是可以驾驭生产过程的物质流、能量流和信息流的 系统工程。 1 2 2 混合批量调度研究现状 在批量调度问题的研究中，依据分批原则，将每一种工件分成若干小批量， 每一小批工件称为子批。子批的数量、大小和加工顺序是决定批量调度性能最为 关键的三要素。 在英文术语中，l o ts p l i t t i n g ( l p ) ，l o ts t r e a m i n g ( l s ) 表示批量分批调度， 4 第一章绪论 其含义相同。 在过去的几十年里，有许多学者对车间调度问题中的单车间调度、流水车间 调度以及单件多品种车间调度进行了广泛的研究，然而真正涉及到生产车间批量 调度的文献很少。尤其是生产车间中的多品种、小批量工件的分批调度研究。其 原因主要在于车间调度的复杂性。到目前为止，十种工件、十个机器( 1o 1 0 ) 的车间调度优化问题还没有得到解决，更为复杂的批量调度问题，在实际计算中 是很难得到最优解。由于批量调度在实际生产中的重要性和现代计算机技术的飞 速发展，近几年来，有一些学者开始研究批量生产调度优化问题。 1 流水车间批量调度 流水车间调度要比生产车间调度模型简单，因此，对于流水车间批量调度问 题的研究，取得了一定的成果。k r o p p 和s m u n tl j 副采用数学规划法研究了流水 车间调度问题的分批运输问题，重点研究了运输批量的大小对生产周期的影响。 c e t i n k a y a l j 4 j 在完全考虑工件的安装、加工和拆卸的情况下，研究了流水车间 批量调度问题。虽然他们在理论上得到了最优解，但是不能用来解决生产车间调 度问题。 2 生产车间批量调度 生产车间分批调度生产方式已广泛应用在实际生产中，然而国内外只有很少 人对此类问题作了深入的研究。由于大部分学者在其研究中没有把调整工具、更 换模具等辅助加工时间与工序加工时间区别开来，不能得到最优调度，并且他们 建立的模型简单，与实际生产差别较大。j e o n g l 3 5 1 采用启发式方法研究了单工艺 路线生产车间动态批量分批调度，区分了生产辅助时间与加工时间，先把一批工 件作为整体调度，然后按照分批原则进行调整，在一定程度上改进了调度性能。 潘全科1 3 6 j 采用遗传算法，假定了最小加工批量，研究了生产车间多工艺路线的 批量调度问题，以优化生产周期为目标，提出了一种基于工序优先级的调度算法。 由于文献 3 5 和 3 6 的分批原则是人为规定的，缺少理论依据，因此很难得到全 局最优解。 c a n d id o 和k h a t o r l n l 【j ，j 注意到把一批工件分多次运输能缩短生产周期，但 他们没有考虑到一道工序可在多个机床上加工的情况，并且没有分析运输批量对 生产周期的影响。台湾学者c h i n y a o l o we ta li j 驯研究了生产车间批量调度分批 调度的优点。他们对等量分批和不等量分批进行了对比研究，认为对批量调度进 广东工业大学硕士学位论文 行合理的等量分批可以缩短生产周期、降低生产成本。但他没有解决应该如何分 批的问题。 1 2 3 车间作业计划国内外研究现状 车间作业计划按工件工艺路线的特征，可分为单件车间( j o b s h o p ) 作业计 划和流水车间( f l o w - s h o p ) 作业计划。工件的加工路线不同为单件车间作业计 划的基本特征；而所有工件的加工路线相同为流水车间作业计划的基本特征。本 文所研究的基本类型为车间作业计划批量混合中的各种批量工件的分批问题，具 体研究的模型为非标准的j s s 问题，它与典型的、标准的j s s 问题主要区别在于， 标准j s s 中每道工序排序前均指定机器，而非标准j s s 中每道工序在排序前并不 指定机器，只指定所属的工作单元，具体的加工机器将在运算中智能地选择。1 【8 】【9 】 g o d a m m e r f a ，j a c k e kb 对j s p 调度方法、复杂性分析和数学规划模型进 行了综述。 2 6 】【2 7 】由于调度问题的复杂性，导致不同的研究者从不同的角度究某 一方面的问题，产生了许多的车间调度问题的类型和方法，并随着对各类调度问 研究的深入及各种交叉学科的发展，涌现出了许多新的车间调度理论和方法。经 过5 0 年的发展，车间调度问题的研究方法经历了从简单到复杂、从单一到多的 过程。总结起来、现有调度问题的求解方法大体上可以分为以下几种类别： ( 1 ) 基于运筹学( o r ) 方法 运筹学方法是将生产调度问题简化为数学规划模型，采用基于枚举思想的分 枝定界法或动态规划算法解决调度最优化或近优化问题，属于精确方法。i l o l ( 2 ) 基于启发式规则的方法 对生产加工任务进行调度的传统的方法是使用调度规则( d is p a t c h i n g r u le s ) ，已经有许多调度规则被应用，因其调度规则简单、易于实现、计算复杂 度低等原因，能够用于动态实时调度系统中。 1 1 】【1 2 1 调度规则可以分为三类：简 单规则、复合规则、启发式规则。虽然启发式规则常被用于实际当中，但它们一 般不具有全局优化的特点。i l j j ( 3 ) 控制理论方法 6 第一章绪论 g e r s h w i n 等人从控制理论的角度出发，较全面地阐述了控制理论方法在制 造系统的应用情况。控制论方法比较适合定量地定义基本问题，但还没有形成一 套有效的调度模型表达和分析设计的技术。此理论方法的缺点是：模型描述能力 有限，建模时必须对真实环境进行大量的简化，求得最优解的时间随着问题规模 的增大而呈指数规律增长。l j4 j 因此此理论方法也只适合对小规模的系统求解。 ( 4 ) 基于人工智能( a i ) 的方法 a i 方法是通过提高调度方法的智能而解决各类生产调度问题方法的总称。 它主要利用启发式规则来引导搜索并提供有效的搜索程序去寻求复杂问题的较 优解，主要包括启发式搜索规则和基于知识的方法。【1 5 】【1 6 】 ( 5 ) 系统仿真的方法 由于制造系统的复杂性，一般的方法很难用精确的解析模型对其进行描述分 析。但是，仿真的方法却能提供这种理想模型，且可以定量地进行评估，从而对 实际系统采用合适的调度方法。基于仿真的方法不单纯追求系统的数学模型，侧 重对系统中运行的逻辑关系进行描述，能够对生产调度方案进行比较评价，分析 系统的动态性能，并选择系统的动态结构参数。07 】f 1 8 】计算机仿真是当前仿真 研究的重要领域，美、德、日等国的研究具有一定的代表性。 ( 6 ) 基于d e d s 的解析模型方法 对于车间类型的d e d s ，同样可用其解析模型与方法来解决车间调度问题，如 极大代数法、动态规划法等，但它们都只适合于制造系统的性能分析。p e t r i 网 具有并发、动态、直观等优点，还能够准确快速地反映制造系统实时调度的离散 性与随机性，所以它与其它方法相结合在调度问题中得到了广泛的应用。t i l l ( 7 ) 神经网络( n n ) 优化法 n n 用于车间调度主要有三类方式：利用其并行计算能力，求解优化调度， 以克服调度的n p 困难问题。利用其学习能力，从优化轨迹中提取调度知识。 利用n n 来描述调度约束或调度策略，以实现对生产过程的可行或次优调度。 1 2 0 ( 8 ) 基于模糊数学理论的方法 客观现象具有确定性与不确定性两个基本方面，经典数学表达的是现象的确 定性：不确定性一方面表现为随机性，另一方面表现为模糊性。正是利用此特点， 许多学者把它引入了调度领域。但与专家系统相似，这种方法同样存在开发周期 7 广东工业大学硕十学位论文 长、需要丰富的调度经验和知识等缺点。l i , l j ( 9 ) 组合调度方法 由于各种调度算法都不同程度地存在着这样或那样的优缺点，除了传统组合 的启发式规则外，近来人们开始把各种近似算法的组合应用研究作为热点，以弥 补各自的缺点，发挥各自的优势，达到高度次优化的目标。目前，各种算法的组 合应用已成为解决优化调度问题很有前途的方法。现代高性能计算机的飞速发展 为智能软件计算方法的实现创造了前所未有的条件。软计算方法的主要应用对象 是优化问题中的n p 难题。不同的软计算方法在寻优中显示出不同的优势。由于 遗传算法求解复杂优化问题的巨大潜力及其在工程领域的成功应用，此算法受到 广泛的关注。尤其在生产调度领域，被认为是一种很有前途的智能优化方法。纠 f 2 3 1 1 3 研究内容与论文组织结构 1 本课题的研究主要针对批量混合车间的作业计划算法研究，主要包括如 下内容： ( 1 ) 研究了不同生产方式的特点； ( 2 ) 总结了当前生产调度算法，研究各种生产方式下的生产作业计划的功能 模型和系统机制； ( 3 ) 研究基于遗传算法和启发式规则相结合的算法模型，并用此算法来解决 混合批量生产方式的作业计划问题； ( 4 ) 本实验室原有的作业计划平台上进行新模块的开发。 2 论文结构 本文论文结构如下： 第一章介绍了当前制造业的特点及其发展趋势，对各种生产方式进行了总 结，指出当前制造业生产方式的复杂性和混合型；对车间调度的求解方法进行了 简单的介绍和比较，同时，对本课题的研究意义和研究内容作了阐述。 第二章研究了遗传算法，在介绍遗传算法起源和发展应用现状之后，给出 了遗传算法的详细设计步骤，同时对于遗传算法在车间调度方面的应用进行了研 究和总结。 8 第一章绪论 第三章通过遗传算法和启发式算法相结合，建立了基于此混合算法的数学 模型，用以求解混合批量生产车间的调度问题，主要解决混合批量生产方式作业 的分批问题，最后对算法进行可行性和有效性的分析。 第四章利用混合算法实现软件开发，为生产提供指导和参考，同时验证所 研究的算法的实用性。 全文总结及展望：分析论文中获得的主要成果，并探讨其中不足之处和进一 步研究的方向。 9 广东工业大学硕十学位论文 第二章遗传算法及其在车间作业计划中的应用研究 2 1 遗传算法概述 2 1 1 遗传算法的基本概念及其特点 遗传算法是一种模仿生物进化过程的随机方法。因而掌握几个生物学的基本 概念和术语，非常重要。【2 4 】【2 5 】 ( 1 ) 染色体( c h r o m o s o m e ) 它是遗传物质的主要载体，由多个遗传因子( 即 基因) 组成；在算法中为解的编码( 字符串，向量等) 。 ( 2 ) 基因( g e n e ) 是控制生物性状的遗传物质的功能单位和结构单位，在 算法中为解中每一分量的特征( 如各分量的值) 。 ( 3 ) 基因座( l o c u s ) 遗传基因在染色体中所占据的位置，同一基因座可能有 的全部基因称为等位基因( a 1 l e l e ) 。 ( 4 ) 个体( i n d i v id u a l ) 指染色体带有特征的实体，在算法中为解。 ( 5 ) 种群( p o p u l a tio n ) 染色体带有特征的个体的集合。该集合内个体数称 为群体的大小；在算法中为选定的一组解( 其中解的个数为群体的规模) 。 ( 6 ) 适应度( f i t n e s s ) 表示某一个体对于环境的适应程度；在算法中为适应 函数值。又称为适配度。 ( 7 ) 选择( s e le c ti o n ) 以一定的概率从种群中选择若干个体的操作。 ( 8 ) 交叉( c r o s s o v e r ) 有性生殖生物在繁殖下一代时两个同源染色体之间通 过交叉而重组，即在两个染色体的某一相同位置处d n a 被切断，其前后两串分别 交叉组合形成两个新的染色体。在算法中为通过交配原则产生一组新解的过程。 ( 9 ) 变异( m u t a t io i l ) 在细胞进行复制时可能以很小的概率产生某些复制差 错，从而使d n a 发生某种变异，产生新的染色体，这些新的染色体表现出新的性 状。 遗传算法是一类可用于复杂系统优化计算的鲁棒搜索算法，与其它的一些优 化算法相比，它主要有以下特点： 1 遗传算法是进行群体的搜索，即同时搜索解空间的许多点。 2 遗传算法使用适应度函数这一信息来进行搜索，而不需要其它辅助信息。 1 0 第二章遗传算法和及其在车间作业计划中的应用研究 3 遗传算法是对问题参数的编码组进行计算，而不是直接对参数本身。 4 遗传算法是一种随机搜索方法。遗传算法使用的选择、交叉、变异等算子 都是随机操作，而不是确定规则。 5 自组织、自适应和自学习性( 智能性) 。 6 隐含并行性。隐含并行性是遗传算法优于传统的算法的关键所在。 2 1 2 遗传算法的基本操作 1 、编码：将拟解决问题的解表示成遗传空间的基因型串数据结构，其目的 主要是使优化问题解的表现形式适合于遗传算法中的遗传运算。针对函数优化的 编码技术主要有二进制编码、十进制编码、实数编码等。 2 、初始群体的生成：随机生成初始的种群，并以此为基础，进行迭代运算。 3 、确定适应度函数：根据优化问题的目标函数来确定适应度函数，其主要 作用是用来表明迭代运算产生的种群的优劣程度。当适应度函数确定以后，计算 群体中各个个体的适应度。自然律是以适应度函数值的大小决定的概率分布来确 定哪些染色体适应生存。生存下来的染色体组成种群，形成一个可以繁殖下一代 的群体。 4 、交叉：交叉操作是遗传算法中最主要的遗传操作。父代的遗传基因经过 父代染色体之间的交叉并到达下一代个体的。子代的产生是一个生殖产生了一个 新解。 5 、变异：新解产生过程中可能发生基因变异，变异使某些解的编码发生变 化，使解空间具有更大的遍历性，变异运算后得到下一代群体。 6 、终止条件判断：在所有新一代群体中，是否存在满足条件的最优个体存 在，则停止迭代运算，输出最优解，否则继续迭代运算。 广东工业大学硕士学位论文 i 最优个体 f 得出结果 图3 1 遗传算法的基本流程 f i g 2 一ib a s i cp r o c e s so fg e n e t i ca l g o r i t h m 2 1 3 适应度函数和遗传算子 1 、适应度函数 遗传算法遵循自然界优胜劣汰的原则，在进行搜索中基本上不用外部信息， 适应度函数用于对个体进行评价，同时也是优化过程发展的依据。仅以适应度函 数为依据，利用种群中每个个体的适应度值来进行搜索。在具体应用中，适应度 函数的设计要结合求解问题本身的要求而定。 适应度函数在设计时主要应考虑以下条件： ( 1 ) 、单值、连续、非负、最大化这个条件是很容易理解和实现的； ( 2 ) 、合理、一致性适应度值反映对应解的优劣程度，这个条件的衡量往往 比较困难； ( 3 ) 、计算量小适应度函数设计应尽可能简单，这样可以减少计算时间； ( 4 ) 、通用性强的适应度函数应尽可能通用，最好无需使用者改变适应度函 数中的参数。 几种常见的适应度函数如下： 1 2 习| 塑 第二章遗传算法和及其在车间作业计划中的应用研究 ( 1 ) 直接将目标函数转化成适应度函数 若目标函数为最大化问题，则厂( z ) = g ( x ) 若是最小化问题，则f ( x ) = - g ( x ) 。 这种适应度函数简单直观，但存在两个问题，其一是可能不满足常用的轮盘赌选 择中概率非负的要求；其二是某些待求解的函数在函数值分布上相差很大，由此 得到的平均适应度可能不利于体现种群的平均性能，影响算法的性能。 ( 2 ) 界限构造法 对于某些求解极小解和利率问题时，我们必须将目标函数转化为求解最大值 的形式，从而保证适应度函数的非负。常用的解决方法如下： f ( x ，= c 傩喈 巍嚣 1 ， 此时的c 一可以是一个和群体无关的极大值，也可以是g ( x ) 进化过程中的最 大值或者当前群体g ( x ) 中的最大值。 另一种方法是取目标函数的倒数，即： f ( x ) = 去 ( 2 2 ) g u j 为了保证其的非负性，可采用如下方法解决： f ( x ，= 恬q鬓箍麓汕 3 ， 式中，系数c 曲可以是合适的输入值，或是当前一代或者前几代中费用函数 的最小值，也可以是群体方差的函数。 2 、遗传算子 遗传算法中的遗传算子一般有变异、交叉、选择。 ( 1 )选择算子 1 ) 适应度比例方法 目前遗传算法中最为基本也是最常用的选择方法。它也叫赌轮或蒙特卡罗选 择。在该方法中各个个体的选择概率和其适应度值成比例。 设群体大小为n ，其中个体i 的适应度为z ，则个体i 被选中的概率为 只：l ( 2 4 ) 厂， 广东丁业大学硕士学位论文 2 ) 最佳个体保护法 该方法的主要思想是使得群体中适应度最高的个体不经过遗传操作而直接 进入到下一代种群中去。群体中，为达到这一目的，可以使用精英保护方法来进 行选择操作。采用此选择方法的优点是，进化过程中某一代的最优解可不被交叉 和变异操作破坏。但是，这也会导致局部最优个体的遗传基因会急剧增加而使进 化有可能陷于局部最优解，也就是说，该方法的全局搜索能力较差。因此，此方 法一般都与其它选择方法结合使用。 3 ) 排名选择法 所谓排名选择方法是在计算每个个体的适应度后，根据适应度大小顺序对种 群中个体排序，然后把事先设计好的概率按序分配给个体，作为各自的选择概率。 依据选择概率的不同，可分为线性排名选择和非线性排名选择。这种选择方法的 主要着眼点是个体适应度之间的大小关系，并不考虑个体适应度之间的差异程 度。此种方法的不足之处在于选择概率和序号的关系需事先确定。此外，它和适 应度比例方法一样都是一种基于概率的选择，所以仍有统计误差。 4 ) 联赛选择方法 这也是一种基于个体适应度之间大小关系的选择方法。其操作思想是每次从 群体中任意选择一定数目的个体( 称为联赛规模) ，其中适应度最高的个体保存到 下一代。这一过程反复执行，直到保存到下一代的个体数达到预先设定的数目为 止。通常，联赛规模取2 。 5 ) 期望值方法 基本思想是，首先计算每个个体在下一代生存的期望数目： 肚老轰 5 ， 若某个体被选中并要参与配对和交叉，则它在下一代中的生存的期望数目减 去0 5 ；若不参与配对和交叉，则该个体的生存期望数目减去1 ；若一个个体的 期望值小于0 ，则该个体不参与选择。 ( 2 ) 交叉算子 1 ) 单点交叉 在个体串中随机设定一个交叉点，实行交叉时，该点前或后的两个个体的部 分结构进行互换，并生成两个新的个体。 1 4 第二章遗传算法和及其在车间作业计划中的应用研究 2 ) 两点交叉 两点交叉的操作与单点交叉类似，只是设置了两个交叉点( 依然是随机设 定) 。两个交叉点之间的码串相互交换。 3 ) 多点交叉 将单点交叉与二点交叉的概念加以推广，可得到多点交叉的概念。多点交叉 是指在个体编码串中随机设置多个交叉点，然后进行基因交换。多点交叉又称广 义交叉，其操作过程与二点交叉相类似。一般来讲，多点交叉较少使用，因为不 能有效地保存重要的模式，影响了遗传算法性能。 4 ) 一致交叉 所谓一致交叉是指通过设定屏蔽字来决定新个体的基因继承两个旧个体中 的哪个个体的对应基因。一致交叉的操作过程表示如下：当屏蔽字中的位为0 时，新个体a 继承旧个体a 中对应的基因，当屏蔽字为1 时，新个体a 继承旧个 体b 中对应的基因，由此生成一个完整的新个体a 。反之，可生成一个新个体 b 。 当前改进的交叉算子的研究现状如下： 1 ) g o l d b e r g 提出了部分映射交叉( p m x ) 。 2 8 】 2 ) s t a r k w e a t h e r 等提出了增强边缘重组算子。【2 9 1 3 ) d a v is 提出了序号交叉算子( o r d e rc r o s s o v e r ) 和均匀排序交叉算子 ( u n if o r mo r d e r - b a s e dc r o s s o v e r ) 。 3 3 】 4 ) s m i t h 提出了循环交叉算子( c y c l ec r o s s o v e r ) 。 3 0 】 5 ) d ej o n g 提出了单点交叉算子( o n e - p o in tc r o s s o v e r ) 和多点交叉算子 4 7 1 。 3 2 】 6 ) s y s w e r d a 提出了双点交叉算子( t w o p o in tc r o s s o v e r ) 。 3 1 】 ( 3 ) 变异算子 变异算子的基本内容是对群体中的个体串的某些基因座上的基因值作变动， 交叉之后子代经历的变异，实际上是子代基因按小概率扰动产生的变化，依据个 体编码表示方法的不同，可以有以下的算法 1 ) 基本变异算子 基本变异算子是指对群体中的个体码串随机挑选一个或多个基因并对这些 基因座的基因值做变动( 依变异概率作变动) ， o ，1 ) 二值码串中基因变异操作如 1 5 广东工业大学硕士学位论文 f ： 变异前：10 0 11 11变异后：1 10 10 1 1 2 ) 逆转变异算子 在个体码串中随机挑选二个逆转点，然后将两个逆转点的基因值逆向排序如 下所示： 变异前：10 0 111 1变异后：10 11 0 11 2 1 4 遗传算法基本参数的设置 遗传算法中需要选择的参数主要有串长l ，群体大小n ，交换概率只，变异 概率只等，这些参数对g a 性能影响很大。 串长决定于求解问题的精度。g o ld b e r gd e 提出了变长度串的概念，并显 示了良好性能。m6 j 为了选择合适的n 、p c 、己许多学者进行了研究，通常认为： 若种群过小，算法就可能收敛于局部最优解，而不能收敛到最优结果或最优结果 附近。这主要是因为种群规模过小，导致种群内个体多样性减小，从而可能丢失 一些有意义的搜索点或最优点。然而种群过大，每次迭代所需要的计算量就会很 大，这又可能导致一个无法接受的慢收敛率。一般，当种群规模增大时，将有利 于改善种群的多样性，从而可能有利于使算法收敛到最优解或最优解附近。 s c h a f f e rj d 建议的最优参数范围是：n = 2 0 3 0 ，p c = o 7 5 o 9 5 ，己= 0 0 0 5 o 0 1 。但在某些情况下，当种群达到一定规模时，再增大种群规模，对搜索结果 的改善并无多大帮助，甚至有可能变差，目前常用的参数范围是：n = 2 0 “2 0 0 ， = 0 5 1 0 ，巴= 0 0 0 5 。 2 2 车间作业调度遗传算法设计 遗传算法是一种通用的随机优化算法，而车间调度问题则是一类特殊的组合 优化难题。要使g a 能够较好地解决车间调度问题，一方面可对问题进行处理使 其适应g a 的优化，另一方面可对g a 进行处理使其适应车间调度问题的求解，更 有效的方法是对g a 和车间调度问题同时作处理使其相互适应。 1 6 第二章遗传算法和及其在车间作业计划中的应用研究 2 2 1 车间作业计划的编码方式 编码问题是设计遗传算法的首要和关键问题。由于遗传算法不是针对优化问 题的参数而是针对其编码进行操作，因此第一步是将车间作业调度系统中的调度 方案进行编码。遗传算法的编码技术必须考虑“染色体的合法性、可行性、有 效性以及对问题解空间表征的完全性。一个良好的编码方案应该是编码空间到可 行解空间的一一映射。鉴于车间调度问题的组合特性以及工艺约束性，染色体的 l a m a r k ia r l 特性。解码的复杂性、编码的空间特性和存储量的需求是设计遗传算 法编码通常要考虑的问题。 车间调度的遗传算法编码可归纳为直接编码和间接编码两种。 ( 1 ) 直接编码。将各调度作为状态，通过状态演化达到寻优目的，主要包 括基于操作的编码、基于工件的编码、基于工作对关系的编码、基于完成时间的 编码、随机键编码等。 ( 2 ) 间接编码。将一组工件的分配处理规则作为状态，算法优化的结果是 一组最佳的分配规则序列，再由分配规则序列构造调度，主要包括基于优先权规 则的编码、基于先后表的编码、基于析取图的编码和基于机器的编码等。 目前，调度问题中遗传算法的编码方式在应用中主要有以下几种： ( 1 ) 基于完成时间的表达法。这是一种最直观的方法，一个染色体被编码 为一个工序完成时间列表，如染色体 嵋1 l ，2 2 ，3 3 ，w 2 1 1 ，w e 2 3 ，w 2 3 2 ，w 3 1 2 ，w 3 2 l ，w 3 3 3 其中 w 洳表示作业j 在机器r 加工的第i 道工序的完成时间，很容易看出这种表达法 需要设计较复杂遗传算子，以保证约束条件的以满足。 ( 2 ) 基于工序的表达法。将作业的调度编码为工序的序列，每个基因代表 作业的一道工序，它有两种可能的方式来命名作业的每道工序，一种自然的方式 是自然数来命名每道工序，就像t s p 的顺序表达法那样，但由于作业车间调度问 题受加工路线的约束，不是所有的自然数组合都可以定义可行的调度。 ( 3 ) 基于作业的表达法。它由包含1 3 个作业的列表组成，每个调度根据作 业的顺序来构造。对于一个给定的作业顺序，列表中第一个作业的所有工序将首 先被调度，然后考虑列表中第二个作业的工序，依次进行，直到作业的所有工序 排完。加工中的第一道工序要求的加工时间应为相应机器最可能得到的加工时 间。 1 7 广东工业大学硕士学位论文 ( 4 ) 基于优先表的表达法。对于n 个作业m 台机器的调度问题，一个染色 体由m 个子染色体组成，每个子染色体对应于一台机器，由一串长度为n 的符号 表示，每个符号代表在相关机器上处理的工序，子染色体不能描述机器上工序的 先后顺序，因为它们表示的是优先列表，每台机器有其自身的优先列表。实际的 调度由染色体通过模拟发现机器前等待排队的状态得到，如果有必要用优先列表 来确定调度。 ( 5 ) 基于优先规则的表达法。此方法中染色体编码为一个作业分配规则的 序列。基于分配规则序列，用优先分配启发式构造调度，遗传算法用于进化染色 体以方便产生一个好的分配规则。由于该方法便于实现，且时间复杂性较小，优 先分配规则可能是实际求解调度问题最多的启发式方法。 ( 6 ) 基于机器的表达法。染色体变为机器的序列编码，根据序列用瓶颈移 动启发式构造调度。该算法把机器逐一排列，每次在没有被调度的机器中识别一 个瓶颈机器。当调度一个新的机器时，以前的调度需要重新局部优化。瓶颈识别 过程和重新局部优化是基于反复求解一个特定的单机调度而进行的，该问题是原 问题的松弛问题，该方法主要贡献在于用松弛来决定机器的排列顺序。 2 2 2 交叉操作 交叉操作用于组合出新的个体，在解空间中进行有效搜索，同时降低