遗传算法在生产调度方面的应用

遗传算法在生产调度方面的应用合肥工业大学吴磊（20080313）陈超峰（20080321）方振中（20080322）周超（20080332）王伦良（20080340）摘要：生产调度问题是企业生产甚至国际合作的关键问题，但生产调度问题难以精确求解。遗传算法可以很好的解决这一问题，在生产调度、生产规划、任务分配等方面发挥着极其重要的作用。关键词：生产调度生产调度方式遗传算法1.遗传算法遗传算法是模拟生物在自然环境中的进化过程而形成的一种自适应全局优化概率的搜索算法。它使用群体搜索技术，通过对当前群体施加选择交叉变异等一系列遗传操作，从而产生新一代的群体，并按优胜劣汰的机制逐步使群体进化到包含或接近最优解的状态。1.1遗传算法的基本运算过程选择：从当前种群中选出优良的个体作为父代个体。对各染色体vk计算适合度eval（vk）；k=1,2,3，…，m对各染色体vk，计算选择概率：P=eval（vk）/∑eval(vk)交叉：对群体中的个体进行两两随即配对对每一对相互配对的个体，随机设置某一基因之后的位置为交叉点对每一对相互配对的个体，依设定的交叉概率在其交叉点处相互交换两个个体的染色体，从而产生出两个新的个体。变异：遗传算法中的所谓变异运算，是将个体染色体编码串中的某些位置上的基因值用其他等位基因替换，从而形成一个新的个体。2.生产调度生产调度就是组织执行生产进度计划的工作，是实现生产进度计划的主要手段。生产调度以生产进度计划为依据，生产进度计划要通过生产调度来实现。在生产调度的事业上，生产调度有管理和工作之分，也就是生产调度管理和生产调度工作，是两个互为联系有有区别的概念。生产调度的作用是职能作用，生产调度工作的作用是职责作用。具体来说，生产调度管理，是指生产调度的计划、实施、检查、总结的期量循环活动的管理，是指生产调度的计划理论、方法、法规等方面的管理。生产调度工作，则有狭义和广义之分，从狭义上说，生产调度工作是指生产调度的业务工作，也就是生产经营管理方面的技术性工作，其内容是生产调度对生产经营动态的了解、掌握、预防、处理，对关键岗位如主机岗位实行控制，对跨车间和跨部门的电、水、风，产、供、销、运等进行协调平衡，对产量、质量、安全、效益等重点环节实行衔接一致的保证；从广义上说，生产调度部门的行政管理方面的具体事项，如业务上，科技上的研讨活动，在岗人员道德和专业知识的教育，业务能量的具体发挥等，可见广义的生产调度工作，其具体活动事项要比生产调度管理大得多，将生产调度管理等同生产调度工作是不准确的。可以概括的说，生产调度工作是生产调度管理的具体表现，生产调度工作的完成是生产调度管理在实际上完成的具体表现。生产调度的重要意义在于：现代工业企业，生产环节多，协作关系复杂，生产连续性强，情况变化快，某一局部发生故障，或某一措施没有按期实现，往往会波及整个生产系统的运行。因此，加强生产调度工作，对于及时了解、掌握生产进度，研究分析影响生产的各种因素，根据不同情况采取相应对策，使差距缩小或恢复正常是非常重要的。3.遗传算法在生产调度中的应用生产调度主要包括生产环节的调度、资源配置的调度、协作关系的调度。应用遗传算法对生产进行调度要建立在生产资料的统计数据基础上。生产调度工作必须以生产进度计划为依据，这是生产调度工作的基本原则。生产调度工作的灵活性必须服从计划的原则性，要围绕完成计划任务来开展调度业务。同时，调度人员还应不断地总结经验，协助计划人员提高生产进度计划的编制质量。所以说，生产调度是对生产计划的执行手段，而生产计划又以生产调度的执行结果为依据，二者是相互紧密联系，相辅相成的。3.1遗传算法在生产环节的调度中的应用生产环节即产品生产过程中各个工序和相互间写作关系的综合。生产过程中不可避免的存在零部件的存放、储运等一系列的准备工作。如何合理的分配各个环节的工作是提高生产效率的前提。在工厂各事业部的布局问题上。已知个事业部的吞吐量、进出货频率、单位距离货物的运输时间和事业部之间的距离参数。组成的矩阵分别如下：建模时假设：各事业部在一定的时间内吞吐量一定，事业部的方位一定都为纵向排列。则备料时间最短的事业部布局可以描述如下：Min∑∑∑fijcijdij（Aj-Ai）约束条件为事业部之间不会出现布局重叠。单行事业部的布局可以看做是机器的排序问题。则可表达为：{a1a2a3…an}评估：染色体vk给定如下：Vk=[a1ka2ka3k…ank]计算：事业部吞吐量1A12A23A3……nAn123…n1B11B12B13B1n2B21B22B23B2n3B31B32B33B3n…nBn1Bn2Bn3Bnn123…n1C11C12C13C1n2C21C22C23C2n3C31C32C33C3n…nCn1Cn2Cn3Cnn123…n1D11D12D13D1n2D21D22D23D2n3D31D32D33D3n…nDn1Dn2Dn3Dnn∑∑∑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技术北京：机械工业出版社20042.梅中义丛培勇飞机复合材料车间生产计划调度管理系统研究200806-0216-03