基于遗传算法的柔性车间作业调度 - 毕业设计(论文)文献综述.doc

文献综述摘要：有效的调度方法与优化技术的研究和应用，对于制造企业提高生产效率、降低生产成本等方面起着重要作用，因而越来越受到学者们的关注。车间作业调度问题(JobShop Scheduling Problem，JSP)是许多实际生产调度问题的简化模型，一种合理调度方案实质就是在满足约束的前提下实现所有工件的所有操作在不同机器上的排序及时问分配，最后在合理的调度方案中选取一个“最优”调度。由于存在许多约束，所以JSP是一个典型的NPhard问题。通过对一些算法特点的比较和对系统总体设计方案特点的分析，得出遗传算法是一种高效率的随机搜索与优化的方法，具有搜索面广、算法速度快等优点。关键词：车间作业调度；多目标优化；遗传算法1车间调度11 课题的提出及意义2l世纪企业的制造模下如何进行组织管理，包括如何组织动态联盟、如何重构车间和单元、如何安排生产计划、如何进行调度都是我们面临的主要问题。其中车间作业调度与控制技术是实现生产高效率、高柔性和高可靠性的关键，有关资料表明，制造过程中95之间的消耗是在非切削过程中。因此，有效的调度方法与优化技术的研究和应用，已成为先进制造技术(AMT-Advanced Manufacturing Technology)实践的基础和关键1。12 车间调度问题的描述车间调度主要是针对一项可分解的工作(如产品制造)，探讨在尽可能满足约束条件(如交货期、工艺路线、资源情况)的前提下，通过下达生产指令，安排其组成部分(操作)使用哪些资源、其加工时间及加工的先后顺序，以获得产品制造时间或成本的最优化值。在理论研究中，车间作业调度问题常被称为排序问题或资源分配问题或组合优化问题。13 车间调度问题的分类对于车间调度问题，Graves等人进行了分类整理2，按照不同的分类标准，可分为以下四种类型：1) 根据加工系统的复杂程度，可分为单机、多台并行机、Flow Shop和Job Shop。2) 根据优化准则，可以分为基于调度费用和调度性能两大类。3) 根据生产环境的特点，可将调度问题分为确定性调度问题和随机性调度问题。4) 根据作业的加工特点，可将调度问题分为静态调度和动态调度。14 柔性车间作业调度问题生产系统中，Job Shop问题研究对象是由m台机器M1，Mm)加工n种工件Jl，Jn。其中，称所加工的工件为任务，工件在机器上的加工为操作，工件基于加工工艺所决定的限制在某些机器M上的加工顺序为约束条件。并且，设Oij为第i个工件在第j个机器的操作，同时设每个操作Oij所需要的作业时间是固定的。对于生产线调度问题即加工排序问题，要对每台机器Mi，来确定n个工件Ji(i=l，n)的一个加工顺序，在与工艺约束条件相容的前提下，使所指定的某个性能指标达到最优3。对于m台机器(Machine)(M1，M2，Mm)，n个工件(Job)(J1，J2，Jn)的加工过程，调度通常用Gantt图表示。Gantt图是在1917年由Henry Laurence Gantt开发的。它基本上是一种线条图，横轴表示时间，纵轴表示要安排的活动，线条表示在整个期间计划的和实际的活动完成情况。Gantt图直观地表明任务计划在什么时候进行，以及实际进展与计划要求的对比。Gantt图使车间的计划安排情况一目了然，成为管理人员了解全局，安排车间进度的有效工具。表1.1 一个33的JSP问题Job(机器，时间)J1（3,1）（1,2）（2,2）J2（3,1）（2,4）（1,1）J3（2,2）（3,3）（1,1）以一个3个工件3个机器的JSP为例说明，表2.1中每个括弧中第一个数据表示工件在哪台机器上加工，第二个数据表示加工时间。以Gantt图表示的该实例的一个可行调度，如图1.1所示。图1.1 表1.1中JSP的Gantt图2. 遗传算法2.1遗传算法的概念简单来说，遗传算法(GA)是基于自然界中“适者生存”的法则所提出的一种高度并行、随机和自适应优化的搜索算法。它将问题的求解表示成“染色体(chromosome)”的适者生存的过程。通过染色体群的一代代进化，包括复制(reproduction)、交叉(crossover)和变异(mutation)等操作，最终收敛到“最适应环境”的个体(individual),从而求得问题的最优解或满意解4。2.2遗传算法特点遗传算法是一类可用于复杂系统优化的具有鲁棒性的搜索算法，与传统的优化算法相比，主要有以下特点5：1) 遗传算法以决策变量的编码作为运算对象。2) 遗传算法直接以适应度作为搜索信息，无需导数等其它辅助信息。3) 遗传算法使用多个点的搜索信息，具有隐含并行性。4) 遗传算法使用概率搜索技术，而非确定性规则。2.3遗传算法设计过程遗传算法的基本步骤是：1) 确定问题的编码方案。2) 确定适应度函数。3) 算法参数的选取。4) 遗传算子的设计。5) 确定算法的终止条件。遗传算法具体设计实施过程如图21所示。2.4 相关参数与操作的具体设计2.4.1编码和解码 目前，遗传算法的编码有多种方法，但基于工件加工工序编码方法简单直接且易于交叉和变异操作。作业车间调度问题的解包含工序的顺序和机器的选择，因此编码和解码也要反映这两方面内容6。可用基于工序和机器的两层编码方案来实现问题，其中opij表示第i个零件的第 j道工序，第一层编码为各工序的优先权随机数(在(1，K)中产生，其中K表示总的工序个数)，第二层编码是各工序所选择的加工机器，从可供选的机器中随机选出7。图2.1 遗传算法的基本步骤流程图2.4.2初始种群产生、适应度定义和选择操作遗传算法需要表示起始搜索点的初始群体数据。由每一个工件选择的工艺计划构成的集合构成初始群体，算法随机产生一组初始个体作为初始群体。在遗传算法中以个体适应度的大小来确定该个体被遗传到下一代群体中的概率。以全部零件在系统中的平均流通时间最短为目标函数。为便于概率选择，令适应度为： (2-1)其中，N 为机床台数，Fij为机床流通时间。而选择操作则建立在对个体适应度进行评价的基础之上，采用适应度比例选择法来计算个体生存概率Ps (其中M表示群体大小)，并计算群体的平均适应度Favg和最大适应度Fmax，即： (2-2)2.4.3 交叉操作与变异操作交叉操作可以将父代的良好基因通过信息互换产生更好的子代。从父代1中随机挑选一个子系列拷贝到子代相应位置。对于第一层编码为避免产生不合法染色体，可以从父代2中移走在子代中已有的随机数，将剩余随机数依次放入子代中。而对于第二层编码则可以将父代2基因(除子代中已有子系列外)直接拷贝到子代相应位置8。变异操作对第一层编码进行变异操作，采用倒置变异方法，对第二层编码采用约束倒置变异方法。另外，采用固定概率的交叉和变异概率不能准确反映群的进化进程。自适应的交叉概率Pc和变异概率Pm由种群进化状况来确定，随着群体的适应度自动改变。当种群各个个体适应度趋于一致或趋于局部最优时，使Pc和Pm增加以跳出局部最优；而当群体适应度比较分散时，使Pc和减Pm小以利于优良个体的生存。同时，对于适应度高于群体平均适应值的个体，选择较小Pc和Pm，使得优良个体得到保护；而适应度低于群体平均适应值的个体选择较大Pc和Pm，增加新个体产生的速度9。交叉和变异概率的自适应算式分别为： (3) (4)其中，Pc为交叉概率； Pm为变异概率；Fmax为种群个体中的最大适应度；Favg为种群个体的平均适应度；F为交叉或变异个体的适应度；c1，c2，m1，m2为0，1之间的常数。3. 总结车间生产调度是制造系统的基础，生产调度优化是先进制造技术和现代管理技术的核心技术。在解决这个问题时传统算法均不再使用，学者们引进了遗传算法来解决车间调度问题，然而遗传算法也存在了一系列的问题，学者们又针对遗传算法的不足进行了改进，寻找出了许多不同的改进型算法，在解决车间调度问题上取得重大突破。参考文献1 王凌. 车间调度及其遗传算法 M 北京 ： 清华大学出版社 ， 2 0 0 3 1 83 6 2 段培勇遗传算法在车间优化调度中的应用研究D合肥：合肥工业大学,20073 王书锋车间作业调度(JSSP)技术问题简明综述J系统工程理论与实践,2003，23(1)：49554 KAAN E,YUSUF AHigh speed CNC system designpartl：jerk limited trajectory generation and quintic splineInterpolationJInternational Journal of Machine Tools Manufacture,2001，41：132313455 Gavett,JX three Heuristic Rules for Sequencing Jobs to a Single Production FacilityD. Mgmt.Sci.,Vol. 11, 1965: B 166-B 1766 余琦玮， 赵亮， 潘双夏.基于遗传算法的柔性作业车间调度优化.组合机床与自动化加工技术， 2004，7 王小明， 曹立明 遗传算法 M 西安 ： 西安交通大 学出版社， 2 0 0 2 6 5 6 8 8 Davis LHandbook of Ge