搜索
遗传算法在生产调度方面的应用摘要：生产调度问题是企业生产甚至国际合作的关键问题，但生产调度问题难以精确求解。遗传算法可以很好的解决这一问题，在生产调度、生产规划、任务分配等方面发挥着极其重要的作用。关键词：生产调度生产调度方式遗传算法研究背景：生产调度任务分配问题是任务分配问题的一种，它主要是指怎样分配有限的工人和工具来生产调度，以达到生产调度时间最短，效率最高的问题。通过一定的优化算法，合理的安排生产调度的人员与设备，可以达到缩短劳动时间提高效率的目的，从而提高经济效益。生活中类似的任务分配问题还有交通运输，生产线工人任务分配，工业生产设备调度等问题，涉及到工业生产、计算机、交通运输、通信、农业生产、物流及服务行业等国民生产重要部门。能不能解决好这类问题，能不能找到最优的优化算法将关系到我们的国民经济发展和个人的切身利益。生产调度任务分配问题模型与算法研究这一课题来自于实际应用。生产调度是我们生活中的一项重要的生产生活活动。在一般的情况下，生产调度的数量与生产调度工人以及相应生产调度设备的数量是不一致的，调度的种类也是不同的，怎样利用有限的资源在最短的时间内完成生产调度就是本课题所要解决的问题。例如,生产调度车间的生产，而生产调度的数量是有限的，不能同时对这些间车进行生产调度，为了保证生产调度任务在最短的时间内完成，就要设计出最优的算法来计算并安排调度的分配，从而提高效率。解决了生产调度任务分配的优化问题，就可以明显提高交通运输、工业生产等领域的效率，对于企业经济效益的提高和国家经济的发展具有现实意义。其次，通过研究生产调度任务分配问题的优化算法，研究者会进一步得到有关任务分配问题的相关优化算法，而任务分配问题在生产生活中非常的普遍，这对于全面提高社会生产效率有积极的影响。再次，对具体问题的研究也能促进智能优化算法的发展，促进优化理论的发展。这对于科学是具有积极意义的，同时得到发展的理论又可以被用于分配问题以外的实际生产中，使得整个社会的生产效率得到巨大的提高。总之，研究生产调度任务分配优化算法，不仅仅对这项单独的问题有积极的作用，同时对于优化理论的发展和社会生产效率的提高都具有一定的积极意义。1遗传算法的概述遗传算法是模拟生物在自然环境中的进化过程而形成的一种自适应全局优化概率的搜索算法。它使用群体搜索技术，通过对当前群体施加选择交叉变异等一系列遗传操作，从而产生新一代的群体，并按优胜劣汰的机制逐步使群体进化到包含或接近最优解的状态。1.1遗传算法的基本运算过程遗传算法（GeneticAlgorithm）作为一种优化算法特别适合于对象模型难于建立、搜索空间非常庞大的复杂问题的优化求解。它和模糊控制技术一样，虽然在理论上还没有完善，但是在实践中已经得到了广泛的应用。遗传算法的基本思想是：模仿生物系统“适者生成的原理，通过选择、复制、交叉、变异等简单操作的多次重复来达到去劣存优的目的，从而获得问题的优化结果。遗传算法的实现由两个部分组成，一是编码与解码，二是遗传操作。其中遗传操作又包括选择、复制、交叉、变异等步骤。本算法根据实际情况采取了1-6整数编码。数字1，2，3，4，5，6分别代表6件待加工产品。遗传算法基本流程:通过编码，解码程序随机产生N个（有一定数量,如50或100）个体构成初始种群从初始中群中选取2个具有最优染色体（最有排序方案）的个体作为临时个体（父代）；如果此2个体中有一个个体通过解码操作能够实现最优排序（即使总时间为75周期），那么结束此算法，得到最优解；对2个临时个体以一定方式(循环交叉)执行染色体交叉变换和变异选择（小概率,互换操作），产生2个新的个体；对父代和子代共4个个体进行选择，从中选出最佳的2个个体，做为下一代的父代；重复执行第二步(b)操作；如果执行完M步后仍然未得出答案75，那么将目前的最优解作为本算法的最优解答案。首先，编码和解码（同上）其次，交叉变换(crossover)对2个父代临时个体进行染色体交叉变换，采用循环交叉方法（CyclecrossoverCX），如父代染色体为：X：[926473581]和Y：[345816729]，如果随机选到第二位开始交叉，那么X的2对应Y的4，X的4对应Y的8，X的8对应Y的2，这样就确定了以上为不变的染色体，其余位置的染色体互换位置，最后得到X:[325416789],Y:[946873521],实现交叉变换。然后，变异选择（mutation）采用互换操作（SWAP），，即随机交换染色体中两不同基因的位置。如上面的染色体为：X:[325416789]。随机产生变换位置号，如产生随机数3和5，那么交换数字后得到染色体：[321456789]，变异概率取0.1最后，选择操作（selection）对父代2个体f1,f2和子代2个体f3,f4进行选择，通过编码操作确定具有最优解的2个个体，成为新一代f1和f2。如此，通过多次编码和解码随机产生一定数量的个体，选取2个最佳个体进行交叉变换操作，产生2个新个体，然后对4个个体进行选择，产生下一代，如果某时刻通过解码操作得出最优解（所有解的下限，这里是75周期），那么算法结束，否则循环进行，直至预先给定的循环次数达到为止，以最后得到的最优解作为最终最优解。选择：从当前种群中选出优良的个体作为父代个体。对各染色体vk计算适合度eval（vk）；k=1,2,3，…，m对各染色体vk，计算选择概率：P=eval（vk）/∑eval(vk)交叉：对群体中的个体进行两两随即配对对每一对相互配对的个体，随机设置某一基因之后的位置为交叉点对每一对相互配对的个体，依设定的交叉概率在其交叉点处相互交换两个个体的染色体，从而产生出两个新的个体。变异：遗传算法中的所谓变异运算，是将个体染色体编码串中的某些位置上的基因值用其他等位基因替换，从而形成一个新的个体。2生产调度的概述生产调度就是组织执行生产进度计划的工作，是实现生产进度计划的主要手段。生产调度以生产进度计划为依据，生产进度计划要通过生产调度来实现。在生产调度的事业上，生产调度有管理和工作之分，也就是生产调度管理和生产调度工作，是两个互为联系有有区别的概念。生产调度的作用是职能作用，生产调度工作的作用是职责作用。具体来说，生产调度管理，是指生产调度的计划、实施、检查、总结的期量循环活动的管理，是指生产调度的计划理论、方法、法规等方面的管理。生产调度工作，则有狭义和广义之分，从狭义上说，生产调度工作是指生产调度的业务工作，也就是生产经营管理方面的技术性工作，其内容是生产调度对生产经营动态的了解、掌握、预防、处理，对关键岗位如主机岗位实行控制，对跨车间和跨部门的电、水、风，产、供、销、运等进行协调平衡，对产量、质量、安全、效益等重点环节实行衔接一致的保证；从广义上说，生产调度部门的行政管理方面的具体事项，如业务上，科技上的研讨活动，在岗人员道德和专业知识的教育，业务能量的具体发挥等，可见广义的生产调度工作，其具体活动事项要比生产调度管理大得多，将生产调度管理等同生产调度工作是不准确的。可以概括的说，生产调度工作是生产调度管理的具体表现，生产调度工作的完成是生产调度管理在实际上完成的具体表现。生产调度的重要意义在于：现代工业企业，生产环节多，协作关系复杂，生产连续性强，情况变化快，某一局部发生故障，或某一措施没有按期实现，往往会波及整个生产系统的运行。因此，加强生产调度工作，对于及时了解、掌握生产进度，研究分析影响生产的各种因素，根据不同情况采取相应对策，使差距缩小或恢复正常是非常重要的。3.遗传算法在生产调度中的应用生产调度主要包括生产环节的调度、资源配置的调度、协作关系的调度。应用遗传算法对生产进行调度要建立在生产资料的统计数据基础上。生产调度工作必须以生产进度计划为依据，这是生产调度工作的基本原则。生产调度工作的灵活性必须服从计划的原则性，要围绕完成计划任务来开展调度业务。同时，调度人员还应不断地总结经验，协助计划人员提高生产进度计划的编制质量。所以说，生产调度是对生产计划的执行手段，而生产计划又以生产调度的执行结果为依据，二者是相互紧密联系，相辅相成的。3.1遗传算法在生产环节的调度中的应用生产环节即产品生产过程中各个工序和相互间写作关系的综合。生产过程中不可避免的存在零部件的存放、储运等一系列的准备工作。如何合理的分配各个环节的工作是提高生产效率的前提。在工厂各事业部的布局问题上。已知个事业部的吞吐量、进出货频率、单位距离货物的运输时间和事业部之间的距离参数。组成的矩阵分别如下：建模时假设：各事业部在一定的时间内吞吐量一定，事业部的方位一定都为纵向排列。则备料时间最短的事业部布局可以描述如下：Min∑∑∑fijcijdij（Aj-Ai）约束条件为事业部之间不会出现布局重叠。单行事业部的布局可以看做是机器的排序问题。则可表达为：{a1a2a3…an}事业部吞吐量1A12A23A3……nAn123…n1B11B12B13B1n2B21B22B23B2n3B31B32B33B3n…nBn1Bn2Bn3Bnn123…n1C11C12C13C1n2C21C22C23C2n3C31C32C33C3n…nCn1Cn2Cn3Cnn123…n1D11D12D13D1n2D21D22D23D2n3D31D32D33D3n…nDn1Dn2Dn3Dnn评估：染色体vk给定如下：Vk=[a1ka2ka3k…ank]计算：∑∑∑fijcijdij（aik-ajk）由于布局设计问题是最小化问题，必须将每个染色体的目标函数值转换成适应度，以使适宜的染色体有较大的适应度。转换由以下评估函数完成：eval（vk）=1/fk然后确定种群大小M最大进化代数N交叉率X变异率Y。遗传算法计算后获得最好染色体从而得到个事业部的布局顺序。3.2遗传算法在资源配置的调度中的应用资源配置的主要内容有原材料的数量、工人的工作时间、设备的运转时间等。准确地调查上述数据后间建立种群大小、最大进化代数、交叉率、变异率。依照上述方法计算得最好的染色体，从而确定合理的资源配置。3.3遗传算法在协作关系的调度中的应用协作关系主要指在企业与企业间、地域与地域间的交流与合作。在城市规划等方面有重大的意义。良好的协作关系调度不仅可以方便企业的协作，还有助于带动地区经济的发展，发展集成化的大生产。根据经验和调查，作出合理假设，计算最好的染色体。4飞机复合材料车间生产计划调度管理系统下面以飞机符合材料车间的生产计划调度为例具体说明。在制造企业中,这通常通过可利用的设备数来表示,可以通过公式(1)来计算每月所需的设备小时数。R=∑DiRi+∑（Di/Qi）Si式中:R—每月所需的全部设备小时数;Di—每月所需的产品i的数量;Pi—产品i所需的加工时间;Qi—产品i每批的加工数量;Si—产品i标准的作业交换时间;n—产品的种类数。得到了每月所需的设备小时数后,需要计算每台设备可提供的工时数,这需要考虑到设备的实际利用率。H=N(1-C)(2)式中:H—某设备一年可提供的实际工作时数;N—某设备一年的理论工作时数;C—缓冲量。计算：fk=M∑∑(RH)CijM为每台设备时均出产品量，Cij为各台设备的投入工人数。基于遗传算法而设计出了生产调度的系统图。5总结面向车间的生产计划调度管理体现了企业计划层与生产执行层之间的信息集成思想，达到了物流和信息流的统一。它的实施从根本上改变企业传统的手工操作流程和纸质信息传递方式,促进企业内部及企业间的组织变革和流程改进,大大提高企业的工作效率,并最终为企业的全面业务流程重组打下基础。与此同时,对生产信息的实时监控和反馈,填补了以往企业级计划层与生产执行层之间的信息鸿沟,实现了企业生产计划与车间生产调度的整体优化,从而最终能够达到缩短生产周期,加快资金周转,降低成本,提高质量和服务水平,追求最佳经济效益的目标。同企业其它信息系统的良好集成,将确保其作为企业整体信息框架的一部分提供给企业决策层良好的信息支持。参考文献：[1]宁汝新CAD/CAM技术北京：机械工业出版社2004.22—24[2]梅中