[硕士论文精品]基于改进遗传算法的混合车间调度问题研究

硕J学位论文摘要并行工程CONCURRENTENGINEERING，CE、敏捷制造AGILEMANUFACTUREING，AM、虚拟制造VIRTUAIMANUFACTURING，VM，网络化制造NETMANUFACTURING，NM等作为现代化企业主导的先进制造模式，其目的是要以最低的成本制造出顾客满意的产品。在这些制造模式下如何运用有限的资源，降低产品的生产成本，缩短产品的制造周期，保证按时交货，提高企业信誉，赢得更多客户，合理的调度方法与优化技术成为制约以上目标实现的关键因素，因而车间调度问题也越来越受到学者们的关注。遗传算法GENETICALGOIRTHM，GA是一类借鉴生物界自然选择和自然遗传机制的随机搜索算法，因其对优化模型的依耐性不强、求解问题的简单性和鲁棒性等特点被广泛应用于制造业的各个领域。本文在对遗传算法进行改进的基础上，围绕混合车间的调度问题进行了研究。本文主要作了如下工作文章回顾和总结了车间生产调度问题发展的概况，以遗传算法为线索，以制造系统调度问题及其相关问题为背景，阐述了遗传算法调度问题及其相关问题的数学模型首先针对JIT作业车间多种工艺路线的工件调度问题，考虑到生产过程中受许多因素的影响，采用多目标分层协调策略，建立了柔性多目标函数模型，在混合遗传算法与拉格朗日松弛算法结合的基础上，提出一种混合改进算法，利用遗传算法更新拉格朗日乘子得到问题的最优解，仿真实例验证了该模型与求解方法是现实可行的；其次针对具有多种工艺路线的混合柔性流水车间最小完工时间问题，结合生产工艺计划与车间调度系统的集成原理，建立了目标模型，通过将简单遗传算法加以改进，对算法进行研究，把改进后的遗传算法SGA和模拟退火算法SA有机结合，优化了算法的融合机制和互补结构，形成了较为高效的混合优化算法，使问题得到求解，给出具体算例，验证算法的有效性和先进性。另外结合面向对象的方法，基于组件和线程技术，设计了一个应用于实际生产的优化调度系统模块，介绍了调度系统基于多层次BS结构的系统结构，并对系统的业务逻辑作了详细阐述，说明了生产调度管理系统的数据库开发过程本文最后对下一步基于改进遗传算法的混合车间生产调度问题将要进行的工作进行了展望。关键词柔性车间调度JIT遗传算法模拟退火ABSTRACTCONCURRENTENGINEERING，AGILENETWORKBASEDMANUFACTURINGASAMANUFACTURING，VIRTUALMANUFACTURING，MODERNBUSINESSSUCHASADVANCEDMANUFACTURINGMODEL，THEAIMISTOPRODUCETHE10WESTCOSTPRODUCTOFCUSTOMERSATLSTACTLONINTHESEMANUFACTURINGMODELOFHOWTOUSEOURLIM“EDRESOURCES10WERPRODUCTIONCOSTS，REDUCETHEMANUFACTURINGCYCLETOENSUREONTIMEDELIVERY，IMPROVECREDIBILITY，WINMORECUSTOMERS，AREASONABLEMETHODOFSCHEDULINGCONSTRAINTSANDOPTIMIZATIONTECHNOLOGYTOACHIEVETHESEOBIECTIVESKEYFACTORS，WHICHSHOPSCHEDULINGPROBLEMSAREMOREANDMOREATTENTIONBVSCHOLARSGENETICALGORITHMGENETICALGOIRTHM，GAISAKINDOFLEARNFROMBIOLOGICALNATURALSELECTIONANDNATURALGENETICMECHANISMSOFRANDOMSEARCHALGORITHM，WHICHACCORDINGTOTHEOPTIMIZATIONMODELOFPATIENCEISNOTSTRONG，TOSOLVETHEPROBLEMOFSIMPLICITYANDROBUSTNESSOFTHECHARACTERISTICSOFWIDELVUSEDINALLAREASO士MANU士ACTURLNGINTHISPAPER，GENETICALGORITHMONTHEBASISOFLMPROVEMENTSAROUNDTHEISSUEOFMIXEDSHOPSCHEDULINGISSTUDIEDINTHISPAPER，THEFOLLOWINGWORKTHEARTICLEREVIEWSANDSUMMARIZESTHEWORKSHOPPRODUCTIONOFANOVERVIEWOFTHEDEVELOPMENTOFSCHEDULINGPROBLEMS。FORCLUESTOTHEGENETICALGORITHMTOSCHEDULINGPROBLEMOFMANUFACTURINGSYSTEMSANDRELATEDISSUESASTHEBACKGROUNDONTHESCHEDULINGPROBLEMOFTHEGENETICALGORITHMANDITSMATHRELATEDISSUESMODEL；NRSTOFALL，FBRAVARIETYOFJOBSHOPJITPROCESSWORKPIECELINESCHEDULINGPROBLEM，TAKINGINTOACCOUNTTHEPRODUCTIONPROCESSISAFFECTEDBYMANYFACTORS，THECOORDINATIONOFAMULTITIEREDSTRATEGYOBJECTIYES，THEESTABIISHMENTOFAFLEXIBLEMULTIOBIECTIVEFUNCTIONMODELTHEHYBRIDGENETICALGORITHMWITHTHERUGBYLONGDAYOFRELAXATIONALGORITHMSBASEDONAHYBRIDALGORITHMUSINGGENETICALGORITHMTOUPDATELAGRANGEMULTIPLIERSOFTHEOPTIMALSOLUTIONHASBEENTHEPROBLEM，TOVERIFYTHESIMULATIONMODELANDMETHODWASFEASIBLEANDPRACTICAL；FOLLOWEDBYTARGETEDAMIXTUREOFAVARIETYOFF。LEXIBLEPROCESSROUTESTHESMALLESTCOMPLETIONTIMENOWSHOPPROBLEM，COMBINEDWITHTHEPRODUCTIONPROCESSPLANNINGANDSHOPSCHEDULINGSYSTEM，THEPRINCIPIEOFINTEGRATION，THEESTABLISHMENTOFTHETA唱ETMODEL，BYASIMPLEGENETICALGORITHMTOLMPROVETHEALGORITHMTOSTUDYTHEIMPROVEDGENETICALGORITHMSGAANDSLMULATEDANNEALINGALGORITHMSACOMBINATIONOFALGORITHMSTOOPTIMIZETHEINTEGRATLONO士COMPLEMENTARYMECHANISMSANDSTRUCTURES，THEFORMATION0FAMOREEFFICIENTHYBRIDOPTIMIZATIONALGORITHMFORSOLVINGTHEPROBLEM，SPECINCEXAMPLESAREGIVENTOVERIFLYTHEEFFECTIVENESSOFALGORITHMSANDADVANCEDSEXUALANOTHERMETHODOFCOMBININGOBJECTORIENTED，TECHNOLOGYBASEDCOMPONENTSANDTHREADS，ANAPPLICATIONDESIGNEDTOOPTIMIZETHEACTUALPRODUCTIONSCHEDULINGSYSTEMMODULES，INTRODUCEDTHEMULTILEVELSCHEDULINGSYSTEMISBASEDONBSSTRUCTUREOFTHESYSTEMSTRUCTURE，THEBUSINESSLOGICOFTHESYSTEMMADEADETAILEDDESCRIPTIONOFTHEPRODUCTIONSCHEDULINGMANAGEMENTSYSTEMOFTHEDATABASEDEVELOPMENTPROCESS；THEENDOFTHISARTICLETHENEXTSTEPTOIMPROVETHEGENETICALGORITHMBASEDONAMIXTUREOFWORKSHOPPRODUCTIONSCHEDU“NGWORKTOBECARRIEDOUTINFLLTUREKEYWORDSFLEXIBLE；JOBSHOPSCHEDULING；JIT；GENETICALGORITHM；SIMUIATEDANNEALINGIII兰州理工大学学位论文原创性声明和使用授权说明原创性声明本人郑重声明所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名、黑飞淞日期Y卞G月C1日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，即学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权兰州理工大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同时授权中国科学技术信息研究所将本学位论文收录到中国学位论文全文数据库，并通过网络向社会公众提供信息服务。作者签名R龟南导师签名晰乏一L日期MO、年月弋日日跏尹二月夕日硕学位论文第1章绪论与综述11课题研究的背景、意义随着科学技术日新月异的变化，尤其是以电子技术、信息技术、自动化技术、计算机与网络技术、人工智能技术和新材料技术的迅速发展，市场全球化进程正在形成，市场响应的快速化、产品的客户化等要求促使制造业必须采用先进的制造模式来组织生产。在这种时代背景下，快速响应、瞬息万变的市场需求成为制造系统赢得市场竞争的焦点，因此产生了许多先进的制造系统模式，如并行工程CONCURRENTENGINEERING，CE、敏捷制造AGILEMANUFACTURING，AM、虚拟制造VIRTUAIMANUFACTURING，VM等。先进制造模式ADVANCEDMANUFACTURINGMODE，AMM是指在生产制造过程中，依据不同的制造环境，通过有效的组织各种制造要素形成的，可以在特定环境中达到良好制造效果的先进生产方法。这些先进的生产模式能否被成功运用在生产实际中，关键是有没有合理的调度方法与优化技术的支撑。车间生产调度问题也就越来越成为制造业中研究的焦点。什么是车间调度呢车问调度主要是针对一项可分解的工作如产品制造，探讨在尽可能满足约束条件如交货期、工艺路线、资源情况的前提下，通过下达生产指令，安排其组成部分操作使用哪些资源、其加工时间及加工的先后顺序，以获得产品制造时间或成本的最优化。有关资料表明，制造过程中95的时间消耗在非切削过程中心1，合理的建模、有效的调度方法与优化技术可以更好地解决工件在机器上的调度和资源分配，实现车间调度的合理化、自动化、集成化可以实现对生产过程中的物流和信息流的综合管理，使前后工序紧密衔接，保持物流的一贯性可以提高设备的生产效率，减少工序等待时间，降低物料的消耗，减少库存，缩短交货期，降低成本，提高产品竞争力。因此，在制造业中，车间调度已经成为实现先进制造系统运筹学技术、管理技术与组合优化技术发展的核心N】。车间调度也是企业日常生产活动中必不可少的重要组成部分，随着企业生产模式的改变，生产调度问题也在不断发生变化。为了适应这种变化，制造企业的生产经营模式也发生了新的改变1产品开发周期显著缩短，上市时间更快，这是21世纪市场环境和用户消费观所要求的，也是赢得竞争的关键所在。例如，美国制造业的策略从20世纪50年代的“规模效益第一”，经过70年代和80年代的“价格竞争第一和。质量竞争第一”发展到90年代的“市场速度第一。可见时间的因素被提到了首要位置。2具备赢得竞争，提高市场占有率的四种基本能力时间竞争能力，产品上市快、生产周期短、交货及时；质量竞争能力。产品不仅可靠性高，而且使用户在各方面都满意；琏丁改进遗传算法的混合车问生产调度问题研究价格竞争能力。产品生产成本低，销售价格适中创新竞争能力。产品有特色、生产有柔性、竞争有策略。3柔性更加提高，以响应“瞬息万变、无法预测”的市场。企业不仅要具备技术上的柔性还要具备管理上的柔性，以及人员和组织上的柔性。4全生命周期内的质量保证。产品质量的完整概念是顾客的满意度。对产品质量更全面的理解是用户占有使用产品的一种综合主观反映，包括可用、实用、耐用、好用。5企业的组织形式将是跨地区跨国家的虚拟公司或动态联盟。6生产过程更加精良。产品开发生产、销售、维护过程更加简化，生产工序更加简单，从而降低成本、提高劳动生产率、缩短上市时间。7人员的素质更加提高。21世纪制造业要求全体职工具有更高的技术管理和协作素质。8智能化程度更高。在产品设计和制造过程中广泛应用人工智能技术，各种设备的智能化程度大大提高。在上述这些变化下，车间调度问题的研究更加成为当今科学研究的热点。由于大多数车间调度问题属于一类NP困难组合问题，因此寻找具有多项式复杂性的最优算法几乎是不可能的哺1。各种近似启发式方法、诸如基于规则的算法等，由于能在合理的时间内产生比较满意的调度，因此广泛应用于实际调度中，但其往往对所得的调度解的次优性不能进行评估。因此在这方面有必要探索更好的近似最优调度算法。各种基于统计优化的方法、诸如遗传算法、模拟退火法等拍，提供了一种解决调度优化问题的新途径，这方面也需要做进一步的研究。过去的几十年里，基于对实际问题及理论上的考虑，调度问题激励着人们不断寻找新的算法来提高制造业的市场竞争性。好的生产调度技术能提高资源的利用率和操作管理水平，生产出具有竞争力的产品。车间的调度优化工作，因其在提高生产效率，降低生产成本等方面所起的重要作用，正越来越受到学者们的关注，也是本课题的研究意义所在。12车间调度问题国内外研究现状121车间调度问题的分类、特点及有关符号的含义在了解后面的内容之前，有必要对车间调度问题的分类、特点及有关符号的含义进行了解，以方便对后续内容的理解。对于车间调度问题，GRAVES等人对其进行了分类整理“1。按照不同的分类标准，可分为以下6种类型开环车间OPENSHOP和闭环车间CLOSESHOP。单台处理机SINGLEPROCESSOR，多台并行机MULTIPARALLELPROCESSORS，FLOWSHOP和JOBSHOP。基于调度费用和调度性能的指标。确定性调度DETERMINISTICSCHEDULING，随机性调度STOCHASTICSCHEDULING。静态调度STATICSCHEDULING，动态实时调度DYNAMICSCHEDULING有序加工，无序加工。现代车间调度类型往往是JOBSHOP型FLOW2硕学位论文SHOP型，因此，后面的内容主要围绕这两种类型的调度问题展开。其具有以下特点建模复杂性。计算复杂性。动态随机性。多约束性。多目标性。处理机、任务或作业和目标函数三要素组成了调度问题。处理机的数量、类型和环境有近十种情况，任务或作业和资源的约束条件更是错综复杂，再加上度量不同指标的目标函数，形成了种类繁多的调度问题。为了描述方便，用GRAHAM等人陋1首先使用的三元组来描述调度问题的种类，这样大大简化了调度问题的表示。三元组记号由三个域组成AIPLY。它们具有下面的含义。口域表示处理机的数量、类型和环境，它可以为1单处理机。聊个同速机。绒脚个恒速机。JIC。删个变速机。朋个处理机，流水作业。D矗历个处理机，开放作业。以M个处理机，异顺序作业。腰J类处理机，柔性流水作业。P域表示任务或作业的性质、加工要求和限制，资源的种类、数量和对加工的影响等约束条件。它同时可以包含多项，可能的项主要有，；任务有不同的到达时间。表示在弓和瓦之间的切换时间SETUPTIME。脚加工时可中断。胛C，C加F船，INTRPP，D甜舭P表示任务的相关性，分别表示一般优先约束、链、入树和出树。鸩处理机资格限制。当处理机环境是平行机时，鸩可能出现在卢域中。当哆出现在卢域中时，不是所有的处理机都能加工任务乃，鸠表示能加工任务丁，的处理机集合。如果P域中不出现M，R可以在任意处理机上加工。6，捌伽，L机器故障表示机器不能连续被使用。在确定性调度中，机器的不可用时间是固定的。对于同速机，可用的机器数在任何时刻都是时间的函数。胛“这个约束只能出现在流水作业中。当P删甜出现时，作业按先进先出的原则进行所有作业的每一道加工顺序性同。6，D础阻塞现象只能出现在流水作业中。如果在两个相邻的机器之间有一个容量有限的缓冲区，当缓冲区被占满时，上流的机器就不能释放加工完的作基】改进遗传算法的混合下问生严测发问题研究业，即被加工完的作业阻塞在上流机器上。这就是零缓冲区。删，不等待限制只能出现在流水作业中。陀伽循环指可以出现在异序作业环境，它表示作业可以多于一次的访问同一处理机。，域表示要优化的目标函数，它可以是CM。时间表长，表示最后一个被加工完任务的完工时间。K瓤最大延误时间。Q，Q总完工时间，加权总完工时间。Q，一Q总误工，加权总误工。Q，_Q误工任务数，加权误工任务数。122调度问题国内外研究现状19世纪末20世纪初，内燃机的广泛应用引发了制造业的变革，制造业进入了以兵器工业和汽车制造业为代表的大批量生产时代，出现了流水生产线，20世纪20至40年代制造业出现了机群式生产模式阳1，但在当时，生产调度主要依靠经验进行，没有自成体系的理论支撑。自20世纪50年代初期，应用数学、运筹学、工程技术等领域的学者才开始对制造过程中的调度问题进行大量研究。在研究的初期阶段，调度问题是作为一个纯粹的数学问题加以研究，50年代早期，针对FSSP流水车间调度问题，SMJOHNSON【L们提出了解决N2FCMAXN个工件2台机器的FLOWSHOP型调度的最小流程周期问题和部分特殊的N3FCMAX问题有效的JOHNSON规则，虽然只是针对流水作业的求解方法，但它对以后的研究有很大的影响此后相继有利用多项式时间算法求解2谳MAX，J2LJS2ICMAX和J2ITI1ICMAX等特殊的JSSP作业车间调度问题，这些研究奠定了经典调度理论的基础，标志着调度理论研究的开始。最早的调度问题是单机问题，同时也是最简单的调度问题。首先单机调度问题比较容易求出解决方案，这些方法对于研究比较复杂的调度问题具有指导作用，可以为处理复杂调度问题提供近似算法；1955年，JACKSONJR针对生产线上单机调度问题的最小延缓时间做了深入的研究，提出了分派规则N1J。1956年，SMITHWE对基于多最优的单阶段生产调度问题进行了研究N引。1973年LAWLEREL研究了具有优先约束的单机最优调度，讨论了加权总完工时间最小的优先调度规则N引。1974年，BAKER对单机作业情况下工期和最早开工时间最小延迟调度问题进行了详细论述N劓。1975年，MCMAHON等讨论了具有准备时间和完工日期最短的调度问题N51，1976年，LAGEWEGBJ等人研究了单机情4形J学位论文况下的最短延迟调度问题N引。随后这类问题一直被作为研究的重点，1977年，LENSTRAJK等人，1978年LAWLEREL，1991年，BURBRIGEJL，1993年，BLAZEWICZ等人，1998年，罗成新，赵玉芳等又从不同角度研究讨论了单机调度问题“。平行机调度问题是调度中重要的一类问题，其中包括不可中断时间表长问题，可中断时间表长问题及总完工时间问题。L961，HUTC，1966，GRAHAMEG从不同方面对不可中断时间表长问题进行了深入的理论研究引。1997年，赵传立等人研究讨论了处理机具有不同开始加工时间的可中断调度问题，此外还有许多学者在这方面做了大量研究，这里不一一列举。车间作业调度问题包括同顺序作业调度问题、自由作业调度问题和异顺序作业调度问题。这类也是研究中涉及最多的问题之一，另外，流水问题也是一类特殊的作业车间调度问题。1965年，针对JSSP问题，LOMNUCKIN训提出了分支定界法，其主要思路是首先求解整数规划的伴随规划，如果求得的最优解不符合整数条件，则增加型的约束缩小可行域；将原整数规划问题分支，分为两个子规划再解子规划的伴随规划，通过求解一系列子规划的伴随规划及不断的定界。最后得到原整数规划问题的最优解。1968年，GOLOMB心们等人又提出了回朔法用来求解JSSP问题，它的思路是不断切割原问题规划的可行域，使它在不断缩小的过程中将原问题的整数最优解逐渐暴露且趋于可行域极点的位置。随后几年，车间调度理论主要围绕着整数规划、动态规划、分枝定界等这些方法进行，研究并解决了一系列有代表性的调度问题。由于调度问题本身的复杂性，后来人们逐渐着手寻找更有效的求解方法，到60年代后期，对于复杂的调度问题，人们开始研究用启发式方法加以解决，至此调度理论的主体结构基本建立起来。从70年代开始，随着复杂性理论COMPLEXITYTHEORY及NP一完全问题NPCOMPLETE研究的兴起，人们开始注意并重视调度问题的复杂性研究，证明了许多调度问题是NP难的NPHARD，即使简单的JOBSHOP和FLOWSHOP问题也是NP难的，不存在有效的多项式求解方法，因此只好寻找有效的启发式方法来解决它们，针对不同的问题，人们提出了大量的启发式算法心223H2钉。到70年代后期，对调度问题的研究深入，已作为一门应用数学分支，经典调度理论己逐渐成熟心5】【2引。主要侧重计算复杂性方面的研究，LENSTRA等心证明了3名允CMAX，J2IJ53CMAX和J3LJS2ICMAX三种情况都是NP难问题BALAS心引最早提出JSSP问题的BB算法，此后CARLIER等他引基于JACKSON们的剩余总加工时间最长MWR规则提出预占先调度JPS用来求解JSSP问题，并且取得了较好的结果“针对传统JSSP问题，以运筹学方法研究为解决问题的重点，即研究如何在M台处理机床上安排N个JOB的处理顺序和处理时间，以使某个目标函数调度长度，拖期惩罚极小化。调度长度极小的调度问题可用混合整数线性规划来求解，但由于约束和整数变量随着问题规模的增加而变得很多，所以只适合较小规模的调度问题。动态规划法隐含枚举整个空间的搜索方法，它把问题分解成若干步，然后在每步上搜索最优解它是求解小规模问题的有效算法但它基于改进遗传算法的混合车问牛产调度问题研究对组合的需要随问题的规模指数增长，以至求解大规模问题成为不可能1。1998年，吴少岩，纪树新等在文献口2331中提出了不同的分支定界法，使得分支定界法成为求解许多调度问题很有希望的方法，因为它常常可为部分路径计算很强的下界，所以它成了求解大型组合问题为数不多的方法之一。基于运筹学方法的研究，这方面的详细论述我们可以参考文献制。值得注意的是，在用OR方法研究调度问题时，一般都是寻求调度特例的多项式时间的最优算法，近似算法或启发式算法。上面的分支定界法在下界精确的情况下是一种精确最优解。反之，当下界不十分精确时，它就是一种近似解。二十世纪八十年代初，调度研究转向应用研究阶段副凹6I。以FOXMS发表的文章为标志，开始了人工智能方法AI在JSSP调度问题中的研究应用71。AI方法是通过提高调度方法的智能而解决各类生产调度问题方法的总称。它主要利用启发式规则来引导搜索并提供有效的搜索程序去寻找复杂问题的较优解，主要包括以下各方面的内容一个是启发式搜索规则，研究的内容主要有宽度优先，深度优先，BEAM搜，A撑算法等。宽度优先，深度优先都是穷举搜索算法，从原理上讲，利用它们都能找到可行解，但却都不适合用于制造系统。因为可行解的空间非常庞大，超过了搜索时间与储存空间的限制。在AI中，较著名的搜索方法就是A拌算法。它将分支定界法与动态规划法相结合，常用于图的路径搜索中。NILSSON证明了A撑算法一定可以找到最优解8I。第二个是基于规则与基于知识的方法，单一的数学方法和工具不足以解决实际的调度问题，AI和专家系统的出现对解决调度问题的实时性和智能型提供了新的辅助手段。调度问题适合用AI和专家系统来解决是因为它本质上是启发式的，即需要用经验规则来获取可接受的解。它们用于调度可以克服数学规划与仿真方法的不足，能根据系统当前的状态和给定的优化目标，对知识库进行有效的启发式搜索和并行模糊推理，避开了繁琐的计算选择最优的调度策略，为在线决策提供支持。但也存在一定的不足，对新的调度环境适应性差，开发周期长，成本高，同时由于AI技术本身发展的限制，完全由计算机实现的系统大多是不良的。在80年代后期，YUEHWERNY等学者先后开展了基于调度系统处于不同的状态，采用不同的调度规则策略的动态调度方法的研究2I，其共同特点是在支持某些活动发生的资源条件具备时砰为决策点，根据系统当时所处的属性状态，决定采取何种规则策略，确定或选择活动发生的顺序和时间，即所谓的状态指导的智能调度方法。另外，为克服数学表示和软件方法的局限性，11988年，DAVIS等N61提出基于数学规划的分解策略，将调度问题分解为多个子问题，分别考虑各子问题及其限制，提高了计算能力数学分析模型通常用数学关系式表达所研究系统变量之间的相互关系。大多数分析模型是描述性的，即在一组条件下预测某一方案的各种结果数值。有一类预测模型需要分辨出最优结果，即需求出最优解，在车间优化调度中，要从多个调度方案中寻求满足约束条件和目标的最佳6硕I学位论文调度方案，这个寻求最优解的过程常称为优化模型。数学优化模型逻辑性强，能清楚地表示出复杂系统中的各种输入输出变量以及较好地反映出多个变量之间的关系，并能实现系统的优化，且建模方便，是车问调度问题中应用较多的一种建模方法。日本学者TADAOMURATA于1989年首次对PETRI网的基本性质和应用做了详细的介绍，并将其用于对调度问题进行建模。基本PETRI网模型具有直观易理解的优点，但其在描述复杂系统时节点数目过多，因而只适用于简单系统的建模。有关扩展PETRI网在调度问题中的研究见MURATA文献N引，这里详细介绍了几种典型的扩展PETRI网的研究情况。主要有以下几种模型的应用研究现状。EPN模型，它通过增加决策节点，使PETRI网具有描述诸如FMS调度决策过程的能力。这种模型由于节点数目过多，只能用于简单系统的建模。MURATA对此做了详细的论述。1991年WANGWX等人对扩展PETRI网在制造系统中的应用做了详细论述比01，由于CPN是PETRI网的压缩形式，同基本PETRI网相比它具有较少的节点数目，所以比较适合复杂系统的建模，但其分析方法比较复杂。VENKATESH等人将TPN模型应用到FMS的局域网建模，控制和仿真当中口，它不仅能够描述系统中事件和状态演化中的逻辑关系，而且通过设置时间与变迁或库所的联系来分析PETRI网演化过程。姜思杰将PTPN模型应用于GA遗传算法和TS禁忌搜索算法混合算法的建模当中口，虽然它比EPN模型结构简单，但它没有决策节点。JENSEN将PTPN和CPN结合起来提出了HLPN。严洪森在HLPN和EPN的基础上提出了EHLEPN模型心纠，该网结构简单，节点少，很适合于FMS的建模，仿真与控制。随着面向对象OO技术的发展与应用，人们开始研究如何将PETRI网与OO技术结合起来，1996年，WANGLC通过将制造系统分为四个阶段，提出了一个集成的OOPO机制，增强了PETRI网的设计描述能力和功能实现能力，降低其建模和分析的系统依赖性与难度乜副。随后他又对OOPO机制在单元控制建模中的发展和应用做了系统研究乜引。随着研究的深入，启发式算法因其易于实现，计算复杂度低等原因，在实际中得到了广泛的应用心纠。，并且多年来一直受到学者们的广泛关注，不断涌现出许多新的调度规则。例如，PANWALKARSA对1L3种启发式调度规则作了详细地总结，将其划分为简单规则，复合规则，启发式规则三类心”。纪树新等在文心引中举了常见的20条规则，并针对一个实际的制造系统，分析了这些规则对系统性能如作业的平均等待时间、机床的平均利用率、作业总加工时间等的影响。随着计算机运算速度的飞速提高，人们希望寻找新的近似调度方法，它以合理的额外计算时间代价，换得比单纯启发式规则所得到的调度更好的调度，如文29中提出的移动瓶颈方法。虽然启发式规则常被用于实际当中，但它们一般不具有全局优化的特点心引。这一阶段硕果累累，解决了一系列长期困惑人们的难题，为车间调度问题的研究打下了坚实的基础。随着调度理论研究的更加深入以及各种交叉学科的发展，不断涌现出了许多新的求解问题的方法。1991年，GERSHWIN等人从控制理论的角度出发，全面阐述了控制理论的方法在制造系统的应用情况心“。控制理论方法比较适合定7基R改进遗传算法的混合车问生产调度问题研究量地定义基本问题，但它只适合对小规模系统进行求解。1993年，邓子琼，李小宁对控制理论方法进行了深入地探讨N引，主要集中在扰动分析法和极大代数法上面。扰动分析法兼容了仿真法与理论分析的长处，同时也避免了单纯用仿真法的大量计算和理论分析研究复杂问题所遇到的困难，主要用于研究制造系统的性能指标生产率等对参数变化的敏感性，并以此为基础对系统的运行进行优化，但是它对多参数的扰动很难用表或状态方程表示仿真运行过程，扰动较大，近似度较差。极大代数法用与解决线性系统相类似的方法对DEDS离散事件动态系统进行建模。它根据系统的运行关系建立起一系列事件发生时间的关系方程。但此方法必须在工件加工顺序事先确定的条件下，才能进行建模分析，因而只适合制造系统的性能分析，而不适合调度。1993邓子琼等人利用仿真语言对此又进行了研究分析，并取得一定的进展，但是此方法主要缺点是代价很高N81。1998年，姜思杰在基于GA和TS的最小平衡算法及其在FMS中的应用一文中运用数学规划的方法对排队网络用于FMS做了初步的分析心。但排队网络只能分析系统的生产率，平均时间等，很难将车间其它资源考虑进去，并且很难处理系统出现异常时的情况。此外还有对线性规划法理论的再研究，LENONID，NISONVASERSTEIN等人对此方法的建模重新进行了详细地论述【26】O大量启发式算法的出现解决了过去无法解决的许多实际问题。随着各种新的相关学科与优化技术的建立与发展，在车间调度领域也出现了许多新的优化方法，以遗传算法GENETICALGORITHM禁忌搜索TABUSEARCH、模拟退火SIMULATEDANNEALING、人工神经网络ARTIFICIALNEURALNETWORK、多智能体MULTIAGENT为代表的智能优化算法在理论上取得了很大进展，并应用到车间调度问题中，取得了理想的效果。一般的车间调度问题都是对于具体生产环境中复杂的、动态的、多目标的调度问题的一种抽象和简化，因而一个调度算法可以通过其如何表述这些复杂性进行分类。文26中为了帮助区别不同的生产调度策略，给出了典型生产调度环境的5个特征1边界条件。2分批大小和调整费用。3加工路径。4随机事件和扰动。5性能指标和多目标。车间调度问题的研究方法最初是集中在整数规划、仿真和简单的规则上，这些方法不是调度结果不理想就是难以解决复杂的问题。MURATA对基于离散事件动态系统DEDS的解析模型这一方法进行了较早的研究，它主要有QN，极大代数法，动态规划法，但它们都适合制造系统的性能分析N引。另外HUGH等人利用普通随机PETRI网对FMS调度与控制决策支持系统进行了研究。1991年，JIANGCQ，SIN曲MG用带有限缓存的排队网络来描述带有有限存储容量的制造系统拍31由于制造系统的复杂性，以至于很难用精确的解析模型对其进行描述分析。但是仿真却能提供这种理想模型，且可以定量地进行评估，从而对实际系统采用合适的方法。这一方面，美国，德国的研究现在处于领先地位，1993年，DOUBLGERIZ，DALESSANDROG在文口518硕IJ学位论义中提出了基于纯仿真模型的车间调度方法，即在个较短的时间段内用仿真来评价一个分派规则集，选取最小代价的规则，以适应系统状态的变化。近年来，我国也开始了此方面的工作，详见文献心。1994年HIRABAYASHIN等人在ADECOMPOSITIONSCHEDULINGMETHODFOROPERATINGFLEXIBLEMANUFACTURINGSYSTEMS一文中对调度问题的分解策略进行了论述，1994年，刘瑞华等针对FMS中一类特殊的DEDS一一FORKJOIN排队网络，利用了极大代数方法对其进行建模，并进行了系统的稳定性分析口引。由于PETRI网并发，动态，直观等优点，所以它与其他方法结合在调度问题里得到广泛的应用。但节点单一，重用性差，建模困难等缺点限制了它的发展。1997年，KHALID等人用多智能体结构的分布式决策方法对FMS进行了动态调度，结果表明此方法的准确性。1997年黄必清等人发表的一篇名为用成组技术分解调度问题也对此作了详细地论述。1999年，廖强，周凯针对一个大的半导体车间提出了一种基于交货期及缓存优先级的分布式调度算法哺引。目前，神经网络NN用于车间调度主要有以下三类一是利用其并行计算能力，求解优化调度，以克服调度的NP困难问题；二是利用其学习能力，从优化轨迹中提取调度知识；三是用其来描述调度约束或调度策略，以实现对生产过程的可行获次优调度。如用HOPNELD网络解决TSP就是最成功的范例，但利用其解决TSP并不是每次都能收敛到最小，时常被冻结在无意义的旅行路线上。1995年，王伟对此在其人工神经网络原理一书中作了一定论述口引。1999年ROVITHAKIS提出了神经网络用于FMS系统口“。2000年，YANGSX等采用了满足约束条件的神经网络和启发式算法求解通用车间调度问题口引。2001年，王万良，吴启迪在文口钉介绍了一种随机HOP行ELD网络来解决JOBSHOP调度问题的方法。FOOYS，TAKEFUJIY为了解决大规模问题，又提出一种改进的TANK和HOP6ELD网络的整数线性规划神经网络ILPNN来解决JOBSHOP调度问题N01。张长水等在文1中也提出了一种用于解决JOBSHOP调度问题的神经网络方法。客观现象具有确定性与不确定性两个基本方面，经典数学表述的现象是确定性的不确定性一方面表现为随机性，另一方面表现为模糊性。正是利用这个特点，许多学者将其引入了调度领域。BGRABO等人将不同的调度规则对其加工系统性能的影响描述成模糊数学形式，由此而引发了对这一理论方法的研究热潮，1995年，DIDIERDUBOIS等人N引，1999年熊红云等分别用基于模糊约束宽展和模糊加工时间参数代替清晰参数的表述法对FLOWSHOP进行调度H副，最后用仿真算例验证了其有效性。但是这种方法同样具有开发周期长，需要丰富的调度经验和知识的缺点。拉氏松弛法由于其在可行的时间里能对复杂的规划问题提供好的次优解，并能对解的次优性进行定量评估，近年来己成为解决复杂车间调度问题的一种重要方法。1990年，HOITOMTFJ用拉氏松弛法解决了单机调度和多台并行机调度问题价N利。9O年代初，HOITOMTD通过引入更多的拉氏乘子松弛9基改进遗传算法的混合车问生产调度问题研究了操作之间的顺序约束，将这种方法用于一般的JOBSHOP调度问题H引。CHENHX，CHENGBC提出用动态规划算法解决作业级子问题的方法，较好地解决将子问题分解到操作级可能出现解振荡的问题H引。此外，一些高级局域搜索法由于具有普遍适用性和较低的经验复杂性等优点而得到了广泛的重视和应用，它们有遗传算法GENETICALGORITHM，GA、禁忌搜索法、模拟退火算法SA。遗传算法的思想源于生物遗传学和适者生存的自然规律，是由美国MICHIGAN大学的HOLAND教授和他的学生发展建立的。HOLAND的两篇文献和DEJONG的博士论文奠定了GA的理论基础。1983年，GOLDBERG在其博士论文中，首次将遗传算法应用到实际的工程系统的优化当中，从而为遗传算法的应用研究和理论研究的更加深入和丰富提供了广阔的前景。由于遗传算法在理论上和经验上被证实能提供在复杂空间中的鲁棒搜索，因而被广泛应用于机器学习，控制，优化等领域。遗传算法不同于前面叙述的梯度法，即它不倾向于局部最优解另外，它也不同于随机算法，因为她能够引导搜索过程向有希望的区域进行。一般来说，遗传算法是由复制，交叉，和变异三个遗传算子组成。但是遗传算法的最大优点是通过群体间的相互作用，保持已经搜索到的信息，这是基于单次搜索过程的优化方法所无法比拟的。但是，对于某些问题遗传算法也存在着计算速度较慢的问题。这时通常将遗传算法和其他优化算法结合使用，有利于改善搜索效率禁忌搜索法TABUSEARCH，TS对于复杂的组合优化问题，通过领域搜索以获取最优解的方法，80年代，GLOVER在文”中叙述了它的基本原理，BARNESANDNOWICKI对TS作了改进。90年代初，TAILARDE提出了解决NOWSHOP调度问题的禁忌搜索算法引，1995年张长水，沈刚为了更有效地搜索解空间，引入了插入移动和移动相结合的机制提高了搜索效率，用来求解JOBSHOP问题91。模拟退火算法SA将组合优化问题与统计力学中的热平衡问题类比，通过模拟退火过程，可找到全局或近似最优解。模拟退火法的改进算法有加温退火法、有记忆的模拟退火法等。1982年KIRKPATRICK等人将金属热加工中的退火工艺的思想首次运用于组合优化问题邻域提出了一种新的搜索技术。1994年，田澎在文章中对FLOWSHOP问题构造了一类模拟退火法拍0J。1995年，HISAOL，SHINTAM提出一种改进的模拟退火法，用来解决具有最小MAKESPAN指标的FLOWSHOP排序问题，并与禁忌搜索法等进行了比较啼。模拟退火法也可与其他方法相结合进行求解，MITTENTHALJ，MADABHUSHIR，ARI仃R先用贪心法搜索，将得到的作业序列作为初始解，再用模拟退火法求解单机调度问题哺别。由于模拟退火法能以一定的概率接受差的能量值，因而有可能跳出局部极小，但它的收敛速度较慢，很难用于实时动态调度环境。由于各种调度算法都不同程度存在这样或那样的缺点，除了传统组合的启发式规则外，近年来，许多人开始把各种近似算法的组合应用研究作为研究的热点，以弥补各自的缺点。LIUHUAIIE等人将启发式规则与仿真方法结合用于调度问题，然后将仿真结果训练ANN，通过ANN选择最优调度规则31。实际的车间调度往往是多目标的，而且这些目标间可能相互冲突。鉴于现有的调度LO硕一L学位论文方法实用性较差的缺点，考虑实际车间环境而构造的调度方法为解决问题提供了新的思路。胡华平，王伟提出了种基于剩余可靠度最大FMS调度算法饰引，并且在解决特定问题中表现出不可替代的作用。EBALAS，AVAZACOPOULOS提出了局部域搜索结合移动瓶颈过程的算法哺51，FPEZZELAEMERELLI提出了禁忌搜索结合移动瓶颈过程的算法引，这些方法在特定的环境下都取得了很好的效果。作为敏捷制造的关键技术之一，异地生产调度已经成为近期研究的热点。重庆大学的刘飞等人提出了一种基于动态联盟的异地生产计划调度方法，国家863CIMS将此列入重点研究领域哺叫。最近，黄文奇等人首先提出拟物拟人的方法求解组合优化问题7“，后来又提出一种基于拟物策略求解JSSP的快速算法随引，并且证明了其效率优于启发式算法。另为，蚁群算法等作为此类方法也得到研究者的广泛关注。不过拟物拟人的方法是一个新的思路，尚未得到人们的广泛认同。随着调度技术与计算机技术的紧密结合，将成熟的调度理论与车间生产调度实际相结合，设计符合本国生产实际的调度系统，已经开始在实际问题中发展。这方面的，哈尔滨工业大学，南京航空航天大学，西安交通大学等国内著名高等院校不少专家学者对此进行了大量的研究工作，利用现有的方法模型，为国内许多大型企业设计了许多符合生产实际需要的调度系统，并获得多项应用成果，取得了可观的经济效益。尽管成绩喜人，但仍旧存在大量问题不能解决，还需要我们去做大量的工作，来不断完善这些已有的成果。123车间调度问题发展趋势虽然对车间调度领域的研究已有半个多世纪的历史，但大多数研究忽略了许多重要因素，建模时对真实的环境进行了大量的简化，离生产实际的应用尚有很大的差距。针对上述存在的问题以及车间调度系统的日益复杂性，目前车间调度问题的研究形成了下列一些研究趋势。1过去的研究大多是使用单纯的禁忌搜索法，存在算法的局限性，多种方法的混合使用能避免单纯使用一种方法的不足与缺陷，现在越来越多的方法更多的探求其它智能方法求解多目标问题。2目前的研究大多是应用多目标优化算法求解某类问题，很少从理论上分析多目标优化算法的性能，越来越多的方法集中在如何验证算法的收敛性和解的多样性。3多目标调度原型系统的研究太少，有很多问题值得进一步探讨，而且与企业其它控制系统和信息系统之间存在信息鸿沟，开发实用的多目标原型系统，探讨集成环境下原型系统与企业其它信息系统之间的信息集成问题，越来越成为生产调度问题研究中的焦点。基于改进遗传算法的混含车间生产调度问题研究13本文的主要工作本文针对JIT作业车间多目标优化问题以及混合流水车间最小完工时间的调度问题，在查阅大量中外文献后，通过比较，选择目前在求解调度问题占有一定优势的遗传算法，通过对普通遗传算法算法的改进，从而使得选定的以上两类车间生产调度问题得以解决，最后结合面向对象的方法实现对车间调度系统的软件设计。本论文主要作了如下工作1针对柔性多目标儿T作业车间的加工设备分散化特点，运用层次分析方法建立目标模型，通过将遗传算法加以改进提出一种集成算子遗传算法，采用了两两竞赛的方法选择算子、聚集度、违约度来处理多目标约束优化对问题进行求解。最后给出了一个具体算例，验证算法的有效性和先进性。2针对柔性儿T混合流水车间复杂化的特点，运用生产工艺计划与车间调度系统的集成原理，提出将CAPP模块与基于周期和事件驱动的滚动窗口调度有机地相结合，从而实现工序分段设计的CAPP系统和基于周期和事件驱动的滚动窗口再调度策略的生产调度系统的集成，建立目标模型，通过将遗传算法加以改进，提出一种混合结构的遗传算法，在建立集成模型的基础上，对算法进行研究，把简单遗传算法SGA和模拟退火算法SA有机结合，使算法优化机制融合和优化结构互补，形成高效的混合遗传算法，从而使问题得到求解。最后给出了一个具体算例，验证算法的有效性和先进性。3通