遗传算法在作业车间调度问题中的应用——先进制造管理作业

第1页先进制造管理报告遗传算法在作业车间调度问题中的应用专业：管理科学与工程时间：2015年1月第2页遗传算法在作业车间调度问题中的应用1作业车间调度问题所谓生产调度，即对生产过程进行作业计划，作为一个关键模块，是整个先进生产制造系统实现管理技术、运筹方法、优化技术、自动化与计算机技术发展的核心，有效的调度方法和优化技术的研究与应用，是实现先进制造和提高生产效益的基础和关键。作业车间调度（job-shop）问题可以表述为：设有N个工件在M台机器上加工，根据工件加工工艺的要求，每个工件使用机器的顺序及其每道工序所花时间已给定，调度问题的目标就是如何选择加工顺序使得总的加工时间最短最优。前提假设：1.每一台机器每次只能加工一个工件，每一个工件在机器上的加工被成为一道工序。2.不同工件的加工工序可以不同；3.所有工件的工序数不大于设备数；4.每道工序必须在指定的某种设备上加工；5.任何作业没有抢先加工的优先权；6.在作业优化过程中既没有新的工件加入也没有取消的工件；车间作业是指利用车间资源(如机床、刀具、夹具等)完成的某项任务。在实际生产中，这项任务可能是装配一种产品，也可能是完成一批工件的加工。而在本文中，为了研究方便，我们将这项任务限定为加工一批工件。在此基础上，可对车间作业调度问题进行一般性的描述:假定有多个工件，要经过多台机器加工。一个工件在一台机器上的加工程序称为一道“工序”，相应的加工时间称为该工序的“加工时间”。用事先给定的“加工路线”表示工件加工时技术上的约束，即工件的加工工艺过程。用“加工顺序”表示各台机器上各个工件加工的先后顺序。车间作业调度问题中，每个工件都有独特的加工路线。它所要解决的问题就是确定每台机器上不同工件的加工顺序，以及每个工件的所有工序的起始加工时间，以最优化某个性能指标。然而，车间调度是一个NP-Hard问题，运用穷举法又会大大增加计算量，所以考虑利用遗传算法求解。第3页1.1车间作业调度问题研究的假设条件在研究一般的车间作业调度问题中往往需要明确两类重要假设条件:1.工艺路径约束:工件的任一工序必须在其前道工序完成后才能开始，并保证同一工件不会同时在两台机器上加工，反映了工件不同工序间的时序关系;2.资源(机器)独占性约束:任一台机器每次只能加工一个工件，且一旦开工就不能中断，反映了加工队列中工件间的时序关系。此外，还有一些辅助假设条件，如下:1.各工件经过其准备时间后可开始加工;2.不考虑工件加工的优先权，即工件之间没有优先约束关系限制的;3.工序允许等待，即前一个工序未完成，则后面工序需要等待;4.所有机器处理的加工类型均不同;5.工件的加工时间事先给定，且在整个加工过程中保持不变;6.缓冲区容量为无穷大。1.2车间作业调度问题的数学模型设有n个工件，要在m台机器上加工，每个工件有Pi道工序，每台机器上总共要加工Lj道工序。定义如下：J:所有工件的集合，12{,,}nJJJJ；M:所有机器的集合，12{,,}mMMMM；ijP：工件Ji的工序集合，12{,,}iiiiijjjjpPPPP；P:所有工序的集合，此为12max{,,}nnPPP矩阵。P（i，j）表示i工件的第j道工序。(,)ijPiP，表示i工件的所有工序按优先顺序的排列。不足12max{,,}nPPP则置零。111111111212(1)1100000innnniiiPPPjjjPjjjpjPPPPPPPPPPPP（1.1）MJ:机器顺序阵，此为12max{,,}nnPPP矩阵。MJ（i，j）表示i工件的第j道工第4页序的机器号，(,)MJi表示i工件的所有工序按优先顺序加工的各机器号的排列。若某工件的工序数不足12max{,,}nPPP则置零。11121111121(1)11100000ijPjjjpjjnjPnnniiiPPPPPPMPPPPPPPMMMJMMMM（1.2）T:加工时间阵，此为12max{,,}nnPPP矩阵。T(i,j)表示工件i的第j道工序在MJ（i，j）上的加工时间。同样地，如果某工件的工序数不足12max{,,}nPPP则置零。11121111121(1)11100000ijPjjjpjjnjPnnniiiPPPPPPPPPPPPPTTTTTTTT（1.3）jM：工件排列阵，此为12max{,,}nPPPn矩阵。(,)jMij表示在i机器上排在第j位加工的工件号，(,)jMi表示i机器上依次加工的各工件的排列。同上，如果某工件的工序数不足12max{,,}nPPP则置零。事实上，工件排列阵就是调度的一种表示形式。由此，我们可以给出一般性的车间作业调度数学模型的定义:如果对应于一个确定的jM，满足*12()min{(),(),()}njjjjfMfMfMfM或*12()max{(),(),()}njjjjfMfMfMfM。即jM使得目标函数()jfM取值最小(或最大)，且与MJ相容，则称jM为车间作业调度问题在此目标函数下的最优解。生产调度问题存在多种优化目标或者综合优化目标，调度问题的优化目标通常从两个方面来考虑:生产成本和生产时间。调度问题从生产成本方面来考虑，其优化目标有:库存最少、在制品最少、设备利用率最高等;从生产时间方面来考虑，其优化目标有:最大程度满足交货期、最小完成时间、最小流动时间和最小等待时间等。第5页2遗传算法遗传算法(GeneticAlgorithm,GA)是一种基于自然群体遗传演化机制的高效探索算法，它是美国学者Holland于1975年首先提出来的。它摒弃了传统的搜索方式，模拟达尔文的遗传选择和自然淘汰的生物进化过程。它将问题域中的可能解看作是群体的一个个体或染色体，并将每一个体编码成符号串形式，对群体反复进行基于遗传学的操作（遗传，交叉和变异），根据预定的目标适应度函数对每个个体进行评价，依据适者生存，优胜劣汰的进化规则，不断得到更优的群体，同时以全局并行搜索方式来搜索优化群体中的最优个体，求得满足要求的最优解。2.1遗传算法的基本思路1.首先确定问题的求解空间；2.其次将求解空间中的每一个点进行编码，并从求解空间中任选N个点组成初始群体；3.计算当前群体中每个个体的适应度函数值。运用选择、交叉、变异算子产生新一代群体；4.对新一代群体中的个体进行评价，若找到满足问题的最优解，结束；否则，转步骤3。2.2遗传算法的模式定理1.选择操作对模式的影响选择操作是遗传算法中体现“适者生存”的关键一环，它能控制高适应度的模式成指数级增长。最常用的选择方式是“轮盘赌”法。其传统实现建立在逐项比较的基础上，算法复杂度为O（n＾2）。通过把各码链适应值转换为一组具有线性序的区间，从而可利用二分查找法实现“轮盘赌”选择操作的递归算法，使时间复杂度下降到O（nlog2n）。2.交换操作对模式的影响交换操作是有规则的信息交换，它能创建新的模式结构，但又最低限度地破坏选择操作过程所选择的高适应度的模式。假设交换操作是采用的单点随机杂交方式，随机选取杂交的起始位置，交叉概率为Pc，两个具有相同模式H的个体发生交换，即杂交操作，不会改变模式H。但是如果其中一方个体不具有模式H，则有可能会引起另一个个第6页体模式的改变。其中一方不具有模式H的概率为1-p(H,t)，当两个个体发生交换时，如果引起模式H的改变，只可能将交换的起始位置选择在第一个模式位到最后一个模式位之间的任何一个位置上，此时，使模式H生存的概率Ps，为:()11scHPPl(2.1)在交换过程中，可能使两个都不具备模式H的个体经交换后产生模式H，故生存概率（()11cHPl）只是一个下界，则有：()11scHPPl(2.2)综合考虑选择操作，模式H在下一代中的数量可以用下式来综合估计:_()()(,1)(,)(1)1cfHHmHtmHtplf(2.3)从上式可以看出，模式的平均适应度高于群体平均适应度，并且具有短定义距的模式，将在下一代中成指数级的增长。3.变异操作对模式的影响通过变异操作对个体串中单个位置进行代码替换，替换的概率为变异概率Pm，则该位置不发生变异的概率为1-Pm。要使一个模式H在变异操作过程中不被破坏，就要保证模式H中确定位必须保证不变，因此，模式H保持不变的概率为:()(1)1()OHsmmppPoH(2.4)上式中O(H)为该模式的阶数。综合上面所述，考虑到选择操作、交换操作和变异操作对模式的影响，则第t代种群P(t)经过遗传操作后下一代种群P(t+1)具有模式H的个体总数为:_()()(,1)(,)(1)(1())1cmfHHmHtmHtPPoHlf(2.5)该式表示了下述的模式定理。模式定理:在遗传算子选择、交换、变异的作用下，具有低阶、短定义距以及平均适应度高于群体平均适应度的模式，在子代中将得以指数级增长。模式定理保证了较优的模式(遗传算法的较优解)的数目呈指数增长，为解释遗传算法机理提供了数学基础。第7页由模式定理可知，具有低阶、短定义距以及平均适应度高于群体平均适应度的模式在后代中呈指数级增长。这些模式在遗传中很重要，称为基因块。基因块假设:遗传算法通过短定义距、低阶以及高平均适应度的模式(基因块)，在遗传操作下相互结合，最终接近全局最优解。模式定理保证了较优模式的样本数呈指数增长，从而使遗传算法找到全局最优解的可能性存在;而基因块假设则指出了在遗传算子的作用下，算法具有生成全局最优解的能力，即能生成高阶、长定义距、高平均适应度的模式，最终生成全局最优解。2.3基本遗传算法参数说明对遗传算法性能有影响的参数主要有:种群数目N、交换概率Pc、变异概率Pm、代沟G、尺度窗口W、和选择策略S等。1.种群数目(populationsize)种群数目的多少直接影响到遗传算法的优化性能和效率，种群选择太小时，不能提供足够多的个体，致使算法性能较差，易产生早熟收敛，甚至不能得到可行解。种群选择过大时，虽然能避免早熟收敛，但是增加了计算量。2.交换概率(crossoverrate)交换概率Pc用于控制交换操作的频率。交换概率太大的时，易产生更新过快，从而破坏掉高适应度个体的现象。交换概率太小的时候又容易产生搜索停滞不前的现象。3.变异概率(mutationrate)变异概率Pm。增加种群多样性具有重要意义。通常选取一个较低的变异概率。如果变异概率太大的时，遗传算法易变成随机搜索，如果变异概率太小，则不能产生新个体，不利于种群的多样性。4.代沟(generationgap)代沟G用于控制每一代群体被替换的比例，每代有N×(1-G)个父代个体选中进入下一代种群中，该参数和交换、变异概率以及选择策略有很大关系，它并不是一个初始参数，而是评价遗传算法的一个参数。5.尺度窗口(scalingwindow)该参数用于作出由目标值到适应度函数值的调整。6.选择策略(selectionstrategy)第8页一般来说有两种选择策略，一种为纯选择，种群中每个个体根据其适应度值进行比例选择，即个体被选择的概率与其适应度值成正比。另一种为保优策略，首先进行纯选择，把目前最优个体直接加入下一代种群中，该策略是为了防止最优解的丢失，但在实际应用中往往采取这两种选择策略结合的方法，并做适当的变型。第9页3用遗传算法对具体问题的解决与探讨遗传算法在解决作业车间调度问题上比经典的启发式算法好，同时遗传算法比传统的搜索技术有更强的优越性，因为它不仅能解决某一特定问题，而且可以适应不同的问题形式。3.1研究过程中的几个关键问题3.1.1参数编码遗传编码技术是实施遗传算法的核心。遗传算法的工作基础是选择适当的方法表示个体和问题的解(作为进化的个体)。对于同一问题可以有不同的编码表示方法。由于遗传算法不能直接处理空间解的数据，在解决此车间调度问题上把它们转换成遗传空间的基因按一定结构组成的染色体或个体，也就是通过编码将它