基于遗传算法求解作业车间调度问题-生产运作实践.docx

目录i问题一：基于遗传算法求解作业车间调度问题21 .问题介绍21.1 作业车间调度问题表述2生产运作实践大作业1.2 作业车间调度问题研究的假设条件31.3 车间作业调度问题的数学模型32 .根本遗传算法42.1 遗传算法的根本思路52.2 根本遗传算法参数说明53 .用遗传算法对具体问题的解决63.1 参数编码63.2 初始种群的生成63.3 个体的适应度函数73.4 遗传算子的设计83.5 遗传算法终止条件94 .模型的求解95 .结论总结106 .附录10问题二：邮政运输网络中的邮路规划和邮车调度171 .问题描述172 .模型建立182.1 模型的根本假设182.2 符号说明182.3 模型分析192.4 模型的建立203 .模型的求解203.1 求解思路203.2 求解算法21问题一：基于遗传算法求解作业车间调度问题1 •问题介绍1.1 作业车间调度问题表述作业车间是指利用车间资源完成的某项任务.在实际生产中，这项任务可能是装配一种产品，也可能是完成一批工件的加工，为了研究方便，我们将这项任务限定为加工一批工件在此根底上，可对作业车间调度问题进行一般性的描述:假定有N个工件，要经过M台机器加工,一个工件在一台机器上的加工程序称为一道"工序"，相应的加工时间称为该工序的"加工时间",用事先给定的■•加工路线"表示工件加工时技术上的约束，即工件的加工工艺过程,用"加工顺序"表示各台机器上各个工件加工的先后顺序。

在车间作业调度问题中，每个工件都有独特的加工路线，我们要解决的问题就是如何分配N个零件在M个机器上的加工顺序以使得总的加工时间最短1.2 作业车间调度问题研究的假设条件在研究一般的作业车间调度问题中往往需要明确两类重要假设条件：1 .工艺路径约束:工件的任一工序必须在其前道工序完成后才能开始，并保证同一工件不会同时在两台机器上加工，反映了工件不同工序间的时序关系；2 .资源独占性约束:任一台机器每次只能加工一个工件，且一旦开工就不能中断，反映了加工队列中工件间的时序关系根据上面以及求解方便，我们做出以下具体假设：1 .每一台机器每次只能加工一个工件，每一个工件在机器上的加工被成为一道工序2 .不同工件的加工工序可以不同；3 .所有工件的工序数不大于设备数；4 .每道工序必须在指定的某种设备上加工，所有机器处理的加工类型均不同；5 .在作业优化过程中既没有新的工件参加也没有取消的工件；6 .不考虑工件加工的优先权，即工件之间没有优先约束关系限制的；7 .工序允许等待，即前一个工序未完成，那么后面工序需要等待；8 .工件的加工时间事先给定，且在整个加工过程中保持不变1.3 车间作业调度问题的数学模型建立车间作业调度问题的数学模型，是我们研究该问题的出发点，同时也为其后的研究奠定了根底。

假设有n个工件，要在m台机器上加工，每个工件有Pi道工序，每台机器上总共要加工Lj道工序我们定义以下根本数学符号囿：上所有工件的集合，J=""2，J11］；M:所有机器的集合，M=｛Ml,M2,-Mm］；写：工件J的工序集合，4=｛%,%2，今“｝；P:所有工序的集合，此为"xmax｛几g,?｝矩阵P〔i,j〕表示i工件的第j道工序P(i,∙)=P.,表示i工件的所有工序按优先顺序的排列缺乏max｛几鸟,2｝,那么其空余的位置用O填满G得2 %δδ^oPjjPja，/“""（/?+1）/“：机器顺序阵，此为"XmaX{%鸟,?}矩阵JM(i.D表示i工件的第j道工序的机器号,Jm(，；・)表示i工件的所有工序按优先顺序加工的各机器号的排列注意：如果某工件的工序数缺乏max{[,6,.己},那么其空余的位置用0填满M„ Mp ∙∙∙Λ∕" Λi ∖⅛2 400 0Mp Mp ' Mp Mp0 0片一片TT加工时间阵，此为"XmaX{%6，{}矩阵T(i,j)表示工件i的第j道工序在/"〔i，D上的加工时间同样地，如果某工件的工序数缺乏max{片,6,.鸟}.那么其空余的位置用0填满Oo0Mj：工件排列阵，此为max{R,R,?}X"矩阵。

Mj(i,_/)表示在i机器上排在第j位加工的工件号，Mj(i,∙)表示i机器上依次加工的各工件的排列同上，如果某工件的工序数缺乏max{/6,?},那么其空余的位置用0填满事实上，工件排列阵就是调度的一种表示形式由此，我们可以给出一般性的车间作业调度数学模型的定义：如果对应于一个确定的M；满足/(M)=min{∕(M)/(M)∙f{Mnj)}或f(M''j)=ma×{f(Mij),f(M-),/(M；)}即M；使得目标函数/(%)取值最小(或最大)，且与JM相容，那么称M:为车间作业调度问题在此目标函数下的最优解2 •根本遗传算法遗传算法是一种基于自然群体遗传演化机制的高效探索算法，由美国学者Holland于1975年首先提出来的，通过模拟达尔文的遗传选择和自然淘汰的生物进化过程来求解它将问题域中的可能解看作是群体的一个个体或染色体，并将每一个体编码成符号串形式，对群体反复进行基于遗传学的操作〔遗传，交叉和变异L根据预定的目标适应度函数对每个个体进行评价，依据适者生存，优胜劣汰的进化规那么，不断得到更优的群体，同时以全局并行搜索方式来搜索优化群体中的最优个体，求得满足要求的最优解遗传算法的根本思路1.首先确定问题的求解空间；2 .将求解空间中的每一个点进行编码，并从求解空间中任选N个点组成初始群体；3 .计算当前群体中每个个体的适应度函数值，然后运用选择、交叉、变异算子产生新一代群体；4 .对新一代群体中的每个个体进行评价，假设找到满足问题的最优解那么结束；否那么，转步骤3。

2.1 根本遗传算法参数说明对遗传算法性能有影响的参数主要有:种群数目N、交换概率Pc、变异概率Pm、代沟G、尺度窗口W、和选择策略S等1 .种群数目种群数目N的多少直接影响到遗传算法的优化性能和效率种群选择太小时，不能提供足够多的个体.致使算法性能较差，易产生早熟收敛，甚至不能得到可行解;种群选择过大时，虽然能防止早熟收敛,但是增加了计算量2 .交换概率交换概率PC用于控制交换操作的频率交换概率太大的时，易产生更新过快，从而破坏掉高适应度个体的现象;交换概率太小的时候又容易产生搜索停滞不前的现象3 .变异概率变异概率Pr对于增加种群多样性具有重要意义如果变异概率太大的时，遗传算法易变成随机搜索，如果变异概率太小，那么不能产生新个体，不利于种群的多样性4代沟代沟G用于控制每一代群体被替换的比例，每代有NX(I-G)个父代个体选中进入下一代种群中，该参数和交换、变异概率以及选择策略有很大关系，它并不是一个初始参数.而是评价遗传算法的一个参数5 .尺度窗口该参数用于作出由目标值到适应度函数值的调整6 .选择策略一般来说有两种选择策略，一种为纯选择，种群中每个个体根据其适应度值进行比例选择，即个体被选择的概率与其适应度值成正比。

另一种为保优策略，首先进行纯选择，把目前最优个体直接参加下一代种群中，该策略是为了防止最优解的丧失，但在实际应用中往往采取这两种选择策略结合的方法，并做适当的变型3 •用遗传算法对具体问题的解决遗传算法在解决作业车间调度问题上比经典的启发式算法好,同时遗传算法比传统的搜索技术有更强的优越性，因为它不仅能解决某一特定问题，而且可以适应不同的问题形式3.1 参数编码遗传编码技术是实施遗传算法的核心遗传算法的工作根底是选择适当的方法表示个体和问题的解.对于同一问题可以有不同的编码表示方法由于遗传算法不能直接处理空间解的数据，在解决此车间调度问题上把它们转换成遗传空间的基因按一定结构组成的染色体或个体，也就是通过编码将它们表示成遗传空间的基因型串结构数据我们采用了基于操作的编码来解此车间调度问题.其根本思想是将所有工件的操作进行编码，不同的工件用不同的编码表示，而同一工件的所有操作在染色体中那么用相同的编码表示，其解码原那么是将染色体上的基因按照从左到右的顺序解释为相应工件的操作顺序，具有相同编码的基因按照其在整个染色体中的位置解释为工件相应顺序的操作表3.1加工时间和工艺约束工程工件操作序列123J1332操作时间J2153J3323JlMiM2M3机器J2MiMaMzJ3M2MiM33.2 初始种群的生成在N个工件M台机器的排序问题中，对每个机器的加工存在加工工艺顺约束，这个工艺约束表示为工件的加工顺序矩阵M∕z^" M12∙"M1MM(J,M)=MZlMjj-Mpm(3.2)MM^2…MnM其中第J行表示第J个工件的机器顺序机器号为零表示工件加工结束。

相应的每个加工操作有时间矩阵：Tn T12,∙ TlM fT21 T22∙∙∙ TzmT(JfM)=： ： ： ： (3.3)Tni TMZ… Tnm其中第J行表示第J个工件的机器加工时间,时间为零表示工件不在机器上加工因为群体中的个体都是由工件的符号组成的，而且工件任意排列总能产生可行调度，所以可以采用随机方法产生初始种群3.3 个体的适应度函数在遗传算法中,适应度是描述个体性能的主要指标根据适应度的大小,对个体进行优胜劣汰适应度是驱动遗传算法的动力从生物学角度讲,适应度相当于"生存竞争,适者生存"的生物生存能力,在遗传过程中具有重要意义适应度函数就是目标函数，在用遗传算法解决车间调度问题里，定义个体的适应度函数为在M台机器上排序加工完N个工件所需的时间，根据染色体编码的思想提出的适应度算法如下：STEPl:定义ti(n)为每个工件的可加工时间，初始化向量为零向量STEP2τhrom(i)对应相应工序的加工机器为machiner〔i〕ti(chrom(l))=ti(chroιn(l)1machine(l))STEP3:fori=2tonFork=ltonti(chrom(i))=ti(chrom(i-l))+ma×(ti(chrom(i-k),machine(i-k)+k))其中假设当i-k<=01那么ti(chrom(i-k),machine(i-k))=0,还有要判断ChOrm(i)所对应的工件在以前是否加工过，假设加工过，那么ti(chrom(i))=ti(chorm(i-l))<,STEP4:求出适应度函数F=ti(chorm(n))o3.4 遗传算子的设计1 .选择算子选择操作是对自然界"适者生存"的模拟。

评价值（目标函数）较小的个体有较高的概率生存,即在下一代群体中再次出现我们采用一种常用的选择方法：按比例选择,即假设个体I适应值（目标函数）是f.,那么个体在群体中复制（再生）的子代个数在群体中的比例将为://£/其中,2f，表示指所有个体适应值之和对群体中各个体的适应值做比拟,将适应值小的个体复制,将适应值大的淘汰掉,这是因为在作业调度算法中的适应度函数为在M台机器上加工完N个工件所需的时间,时间越短,更能到达优化的目的2 .交叉算子在用遗传算法解决作业车间调度问题中,在对工序编码的排序问题中,交叉算子不能简单交换两个个体的相应位置的基因段,因为这样得到的后代个体可能不能满足每个工件号重复M次的要求为了满足我们的工序编码的要求,本文采用下面的交叉算子：随机将工件集。