多目标柔性作业车间调度问题研究

多目标柔性作业车间调度问题研究多目标柔性作业车间调度问题综合考虑了实际生产中的多个性能指标*比如交货期、单个机器最人负荷、拖延时间、机器总负荷等，比対单一目标进行优化更能满足实际生产的需要。多目标柔性作业车间调度问题研究应用于实际生产，提高了企业生产的灵活性，抓快了对市场变化的响应速度,捉高了七产能丿J,缩短了供筋时I讥主产屮不同的牛产任务无石改装机器*仅在牛产调度屮做一兆变动即可进行牛产;在牛一产中某台机器岀现故障后，可以通过生产调度快速的找到其他设备替代，生产不受单台机器的影响：可以对复杂零件的各种要求进行综合加工，无需按照传统的单一匚序的加T-方达；讨以减少单台机器负荷率过低的问题,提高了机器的使川率,从而人人降低了企业的牛产成本」早在1772年Franklin^1就对多目标矛盾提出过探究，也是第一个提出怎样对多r［标进行优化.Zfu乂在19箝年法国经济学家Paretop71±政治经济学的去面丄也同样提出过多目标优化问题的探究。现在多目标优化已经成为数学上的一个分支进行系统的研究,在理论上取得了报多伟人的成果’在很多领域都冇应-川。一般多目标问题可以描述为有£个目标函数，同时决策变量工必须满足*个约束条件，具体可以表述为：约束条杵分为两类，不等式约束和等式约束：輕=P/=L2n设有占个忧化目标，目标函数表示为：卩⑴二(川门/⑴—.<(-0H.J)r［标函数屮仃的子II标是求极人值,仃的口标函数是求极小111,但是f(X)的极小值丿厂广(X)极大值在—心取绘优值*所以可以转化为同-啖形式的口标函数°与多目标忧化的主要几个相关定义【徊有：可行解集若工满足H标函数的约束条杵,则称工为H标函数的I叮it解,所仃听亍解的集合为可行解集X,其屮Pareto最优解集在可行解集屮，对于给定的两个可行解T比*有效，则可厅解T为Pareto最优解，目标函数有多个可行解，Pareto最优解也有多个解，组成的集合为Pareto最优解集，汜为｛"｝。Pareto前沿Pareto最优解集XT屮的解对应的目标函数值组成的集合比」，称为Pareto前沿。3.2生产调度问题数学建模实际的制造生产过程需要同时考虑多个性能指标，生产调度问题通常需要考虑加工成本、交货期、设备负荷最等多个性能指标。不同丁•单目标作业车间调度，多目标车间凋度和不同的目标范吊I内的不同取值和駅纲存在冲突，一个目标性能的改善可能恶化其他目标性能。3.2.1柔性作业车间调度问题的基本描述柔性作业车间有路径和排序两个子问题㈤】，为工序选择机器路径，对每台机器加工的工序进行排序，在生产制造过程屮柔性作业车间调度问题一般可描述如卜：有/个工件｛外▲，•••&｝,可用丁•工件加工的机器有〃台仏02，••〃"｝,每个工件有〃道工序，工件有多条工艺路线可以选择，每道工序可以在一台或者多台机器上加工，每台机器是不相同的，所以工序的加工时间随加工时选择的机器的不同而不同。生产调度的目标是为每个工件选择合适的加工工艺路线，工件的每道工序选择最合适的机器，确定每个工件的每道工序的最佳加工顺序，从而使生产过程屮的某些性能指标达到最优。目前，生产调度屮应用最广的一个调度性能评价指标是最人完工时间（人席）最小。此外，在加工制造过程受许多约束条件的限制，需要满足卜•面的假设条件。（1）某一IN刻在冋一台机器上只能加工一个工件的一道工序；（2）某一时刻同一个工件的相同工序只能在一台机器上加工；（3）工件的每道工序的加工都是连续的，加工过程不能被中断；（4）工件与工件Z间没有先后关系；（5）所有工件的优先级相同；（6）每个工件的每道工序都有可能在零时刻被加工；（7）所有工件加工完都是合格品，不存在次品。3.2.2多目标柔性作业车间调度问题描述和模型柔性作业车间调度问题是一种组合的优化问题，为了适应市场的多变性，需要有柔性的调度系统，生产过程屮为工件的每道工序选定加工机器，并对指定机器上加工的工序排序，多目标柔性作业车|iU调度问题是指同时优化生产过程屮的多个评价指标。文章对工件的完工时间最小、机器负荷最小以及总的机器负荷最小为优化目标对问题进行研究。多目标柔性作业车间调度问题在很多关多目标调度的文献里都何描述，一般可以描述如卜•：有〃个工序加工路线不同的工件，可以选择在加台机器上加工,机器的加工功能不同，相同的工序可以在同一台机器上加工，有的机器具有多种功能，可以加工两道或者多道工序，工序可以选择加工的机器也是柔性的，相同工件的工序可以选择加工的机器有多台，一台机器在任意相同的时间里只能有一个工件在上面加工，一个工件在任意相同的时间里只能选择一台机器加工。对丁•多目标柔性作业问题需要从两个角度來分析问题：（1）给每道工序选择最合适的加工机器，就是考虑机器如何达到最优分配；（2）给每台机器上的加工工序选择最优加工时间，同时将目标函数的多个性能函数考虑进去。在加工过程受到一约束条件的制约。定义文章涉及的符号以及变最的含义：〃:需要加工的工件数量；加：工件的加丁机器总数量；讥:机器序号,「，"1，2,3,…,”；j，k:工序序号,丿1,2,3,...,〃；4:工件,所包含的工序数；Qijk:在机器&上加工待加工工件：的第丿道工序需要加工的时间；%:在机器'上加工待加工工件°的第丿道工序起始加工时fHj：Eijk:在机器k上加工待加工工件'的第丿道工序完工时间；BPk:所有工件在机器2上的完工时间；%：工件'在工序丿上的结束加工时间；人曲：工件总完工时间；第丿个工件的完工时间；1,工件，的第丿道工序和工件e的第g道工序RljeKk=在同一机器R上执行，若工序/先于工序g[o,其他3.3建立多目标柔性作业车间调度的模型0工件i未被安排在第w个位置加工X.•=*”1「件i被安排在第W个位置加丁y_JO工件味在工序j上的第k台机器上加工ijk=}1工件i在工序j上的第k台机器上加工_]0工件i未在工序j上的第k台机器上第1顺位加工乙闵科]工件：在工序j上的第k台机器上第1顺位加工多目标柔性作业车间调度评价指标一般有交货期和机器使用率。论文同时优化生产过程屮较常用的三个评价指标：最人完工时间、最人机器总负荷和单台机器最人负荷。（1）最人完工时间最小人际，最人完工时间是指所有工件都加丁完所需要的时间，直接关系到产品能否在交货期内按时交货，最人完工时间越小说明调度方案越优。/=min（max（d,））（3.2）\<j<n（2）单台机器最人负荷最小BPk,生产过程中选择的调度方案不同，每台机器的负荷就不同，在选取调度方案屮要尽駅满足机器负荷的均衡。nkjfi=min（max工工Oijk切）（3.3）7=11=1（3）最人机器总负荷聂小代”，同一工件的相同工序选择的机器不同，加工时间不同，在满足产品交货期，即最人完工时间最小，机器使用均衡的条件卜•，同IM也需要优化机器的总负荷。(3.4)fi=min(max工工工Qiikxijk)(3.4)/=!j-\h=\优化目标函数时也有一定约束条件：（1）每个排序位置只能分配一个工件;n工X=1w=1,2,ni=liw每个工件只能有一个排序位置；=1i=l,2,...,nW=1⑶任意一个工件在任何一个阶段只能由一台机器加工;N,YZjk=11―1,2,...,n；j—1,2,...,itik=l⑷加工阶段至少为1：m>l(5)至少有一个阶段的机器数目人于1台；m工7Vj>m,N->1j=1,2,...,mj=>⑹工件在某台机器上的加工顺序唯一；k=l1=1(7)工件d在阶段,/+1±的开始加工时间不应早丁•在阶段j上的结束加工时间；C.<Si=1,2,...,n；j=1,2,...,m；r=j4-13.4基于”SGA-II算法的多目标柔性作业车间调度3.4.1NSGA-II算法非劣前沿分级遗传算法"5(NondominatedSortingGeneticAlgorithmNSGA)是基J：Goldberg的非支配排序的思想设计的，通过共享非支配解的虚拟适应度，从而维持了种群在进化过程的多样性。但是NSGA算法的计算要求多，复杂程度高，并且在计算前还必须对参数共享。2002年Deb刖等改进了NSGA算法的不足，提出了NSGA-II算法，该算法被很多学者引用，是目前最优秀的多目标算法Z—。与NSGA相比，NSGA・II具有卜•面的优势：①为了降低算法计算过程屮的复杂度，使用了一种新的排序方法，基J'-分级的快速非支配解的排序；②采用的拥挤距离比较算子可以快速的标定非支配，排序后的非支配解的同级屮不同元素的适应度值，并使Pareto-前端个体可以均匀的分布；③引入了精英保留机制，父代与其繁殖产生的后代通过共同竞争,选择出优良个体來繁殖卜•一代，维持了种群的优良性。3.4.2NSGA-II算法基本流程NSGA-II算法的基本操作流程为：首先初始化种群，随机产生一个规模为N的种群，Pareto排序选择非支配解集Z,通过种群的遗传进化产生种群第一代子代；然后将产生的后代与父代种群组成新的种群，标定快速非支配排序后同级中的适应度值，采用拥挤距离比较算子选取遗传进化中优良的父代个体;最后通过遗传进化产生新的子代种群，反复循环，直到得到满足要求的解。算法流程图陀】如图3-1所不:初始种群N,遗传进化第一代rPareto排序组成的非支配集z—▼i=l111►口召放入#代种群|厂子代与父代结〒合成的新的种群Rt,种群规〔厂子代与父代结〒合成的新的种群Rt,种群规〔I模为2NI＜肿.群Pt+i个圾＞「x7尸Zi+1+.•ZiJ＞1等于N*"遗传操作（交叉，变异）新的后代种群Qt+i进储弋数Gen=Gcn+l遗传操作（交叉，变异）新的后代种群Qt+i进储弋数Gen=Gcn+l图图3-1NSGA-II算法的基本流程图3.4.3算法的设计（1）建立初始种群初始种群的建立是遗传进化中的一个关键步骤，如果初始种群的平均适用度值偏低，初始种群的进化速度会降低，为了收敛得到最优解迭代过程需要很长时间，共至无法收敛到最优解；如果选择较高的平均适应度值,算法可以在较短的时间内收敛到问题的最优解，有效的提高了进化的速度。因此，初始种群对算法求解的速度和质最有很人的影响。本文为了建立较好的初始种群，采用的随机初始化方法随机选择规模为N的初始种群。编码解码设计编码即通过对问题的染色体编码，将具体的调度方案用一定的代码表示，车iiu调度问题常见的编码依据方式有:基j'-待工件的编码，基r工件待加工工序的编码，基丁•工序先后表的编码，基丁•工件z间対应关系的编码，基丁•工件加工优先规则的编码，基r析取图的编码，基丁•工件完工时间的编码，基丁•机器及随机键编码,基『•生产中优先调度权值的编码等。结合柔性车间作业调度问题的特点,米用基J-待加工工序的编码方式，并用阴层编码［43］的方式，先确定各道工序的优先权，由于不同工件的工序Z间没有约束，而同一个工件每次只能加工一道工序,有前后约束，第一层编码为工序的随机数，第二层编码为各工序确定加工机器。柔性作业车间调度问题解码是为所有工序选择一台合适的机器，先把工件排序串转化为有序的工序表，然后依次为有序工序表屮的所有工序安排加工开始时间，工序表中的所有工序都安排完解码停止。设计适应度函数遗传进化过程屮适应度值(①)是评价个体优劣程度的标准，适应度值越人的个体繁殖后代的能力就越强，父代的优良特性更能得以遗传。本文建立的多目标柔性车间作业调度模型的目标函数为适应度函数，即以最人完工时间最小，最人负荷机器最小和总机器负荷最小为目标，调度方案中的工序排序受到机器负荷约束的同时受到工件的约束，调度目标是求人、厶和人三个目标函数的最小值。遗传算子的设计遗传算子的设计是遗传算法屮较为关键的一步，每个染色体对应一个问题的解决方案，执行复制、交叉、变异算子的操作。A复制从种群中选择优良的个体进行进化繁殖，比较种群的个体的适应度，选择适应度高的个体直接复制到卜•一代。一般情况卜•，个体的适应度值越人，被选择直接将染色体复制到卜•一代的机会也就越人，其中选择概率P为:c=4/£厲k=\

其中〃是种群规模数，①是第，个染色体的适应度值，这样适应度值低r平均值的个体在选择过程中被淘汰了，选取适应度高的个体组成一个新的群体。B交叉按照给定的交叉概率（'）随机选择两个编码的染色体交叉操作，产生新的基因组合。所有染色体重复如卜•的迭代过程：在区间［°」］内取随机数厂；若厂则选择交叉的染色体数最为"X'。交叉是将父母的基因在染色体相互交换后随机遗传给卜•一代，在基丁•二序编码的交叉屮，本文采用两点交叉法，随机选择两个交叉点，将两点Z间的基因对换，产生新子代。这个过程与自然界的交配过程类似，父代如果将优良基因传给了后代，就能得到更优的一代。两点交义的选择点（串屮的第3个和第6个点基因对换）100111101011001010011110101100101011101010010110图3-2交叉算子（两点交叉）C变异以较小的概率改变染色体屮的基因位，进化产生新的个体，保证了群体的多样性，确定变异概產为化。本文采用基本位变异算子作变异运算，遗传操作屮二进制编码符号串屮基因位屮的0变为1,或者1变异为0。（5）染色体的选择机制用赌轮法确定种群个体数，用精英保留策略保留迭代过程中的精英个体。子代通过精英策略产生的种群与父代的精英种群组合成新的种群°，人小为2N，月非支配排序的方法対新产生的种群°进行排序，得到非支配解集川，计算非支配解集的拥挤度，经过支配排序后得到优良的个体，然后进行遗传操作（选择、交叉、变异）选择新的子代种群°呵，循环迭代。A非劣前沿分层非劣解指该解的各个目标函数值都是最优的解,即Pareto解，Pareto解指在求解多目标问题时，rl3F目标函数Z间是相互冲突的，某个可能是其中一个目标的最优解，但是在其他目标上较差，任何目标函数的改进都可能导致其他目标函数的解的削弱,Pareto解又称非支配解。如下图，点A,B,C是非支配解,APareto支配解点X,CPareto支配解点Y。▲flXkf2图3-3Pareto支配解示意图在解空间里Pareto最优解是冲突最小的解，染色体群初始化后根据适应度值的人小进行非劣前沿等级分层，具体操作如卜•：将染色体群。内的所有染色体个体°实行卜•面操作：I.初始化一个存放相对染色体°所有非劣染色体的集合；II•初始化一个表示相对染色体。所有非劣染色体的变帚N=°：III•对比染色体°与。，若°相对。非劣，则将。添加到集合纭内，即岛=氏丫｛0」；反乙则增加支配解S即+IV.如没有染色体相对°非劣，则将染色体°」归到第一级的非劣前沿层，记°”认i,同时将Q放到第一级非劣前沿集合,fi,fi"iyQ｝。将群体°内的所有染色体按照步骤（1）的方法划分非劣等级；初始化非劣前沿层内的等级计数器，设为/“：若非劣前