【多目标加工作业调度问题算法分析案例7700字】

多目标加工作业调度问题算法分析案例目录TOC\o"1-3"\h\u2533多目标加工作业调度问题算法分析案例 1241551.1引言 1289321.2问题介绍 2118661.3基于中小规模问题的NSABC算法 3261361.3.1支配关系 3165261.3.2拥挤度计算 3310491.3.3精英策略 4202761.3.4算法框架 59701.4基于大规模问题的DS-LPT启发式算法 6243101.5数值仿真实验 8201871.1.1智能优化算法 8303071.1.2启发式算法 11265801.6加工作业调度系统的设计与实现 13128871.6.1数据输入 13126711.6.2运行结果 141.1引言在航空发动机的制造过程中，企业的优化目标往往不是单一的。这些优化目标包括降低能耗、减少在制库存或者提高客户的满意度等，而这些目标之间往往是相互冲突的。例如，企业希望在最短的时间内按时生产出最多的商品，而时间和产量这两个目标之间就是相互制衡的，缩短生产时间势必会导致产量降低，反之亦然。在这个多目标问题中，无法使得每个子目标一起达到最优值，一个子目标的优化势必会导致另一目标的恶化，因而只能调和所有的给定目标，使用折中方式优化每个子目标。相对于单目标问题最优解唯一的特点，多目标问题则需要求得问题的所有帕累托最优点。这个概念最早出现在经济领域[58]，因意大利的著名经济学家维弗雷多·帕累托而得名。帕累托最优指无论怎样改变当前解，均无法找到所有目标全部优于当前解的状态。多目标问题可以通过下述式子定义。(1.1)(1.2)(1.3)(1.4)多目标问题也可以简单的将每个目标函数赋予权重进而转化为单目标问题。(1.5)尽管如此，在赋予每个目标函数权重的过程中难免会出现各种问题。首先，待优化的多个目标之间往往没有关联，每个目标函数的标量范围很可能差距过大。为了平衡各个目标间的关系，就需要将较小标量范围的目标函数赋予较大的权值。当该目标函数出现较小偏差时，就会对整体目标函数产生较大影响。其次，权值的大小往往没有实际意义，只能通过不断实验来找到一组合适的权值，整个过程耗时耗力。本章将针对双目标的加工作业问题，目标函数分别为极小化两个代理的最大完工时间和以及每个任务的平均完工时间，设计多目标智能优化算法与启发式算法求解该问题。对于中小规模的问题，本文设计了一种基于非支配排序的NSABC算法求解该问题，并与求解多目标问题常用的NSDE算法进行了数值对比实验。对于大规模问题，本文设计了一种高效的DS-LPT启发式算法，尽可能的平衡两个目标函数。并分别针对每个目标函数设计一个有效下界，验证启发式算法的收敛性。1.2问题介绍在多目标加工作业问题中，共有n个任务需在m台设备上进行作业。这n个任务分属于不同的代理商A和B，并有自己固定的加工顺序。同时每个任务j需在其对应的释放时间rj之后才可以开始作业。在任务作业的过程中，所有设备的作业过程均不可中断。任务j在任意一台设备上完成该道工序后，若下一道工序对应设备仍被其他任务占用，该任务将在缓冲区等待，直到被占用的设备达到可用状态时才可进行作业。假设待处理任务的缓冲区是无限的，即不对缓冲区的容量进行考虑。本章将两个代理商对应的最大完工时间和以及所有任务的平均完工时间作为优化目标，并给出该双目标问题的帕累托解集。本章整数规划模型中变量定义与约束部分与4.2.2节中的模型相同。在本章的多目标问题中代理商A和代理商B的优先级相同。由于本章问题为多目标加工作业问题，因此相对于单目标优化问题来说，本章的优化目标将会有所不同，具体的目标函数如下。(1.6)(1.7)1.3基于中小规模问题的NSABC算法1.3.1支配关系对于多目标优化问题来说，在算法的运行过程中，若种群中随机两个个体Xi和Xj满足任意一个目标函数均有的条件，或者至少存在一个目标函数，使得，并且同时满足其他目标函数，则称该个体Xi支配个体Xj。以此类推，当前种群中所有的非支配解就构成了非支配解集，即此时的帕累托解集。在当前种群中，如果找不到其他个体Xj可以支配个体Xi，那么个体Xi就是当前种群的非支配解。在完成种群更新过程后，最终所有的非支配解集合就构成了该多目标问题的帕累托解集。在迭代过程中，需要将种群中的所有个体赋予支配等级Rank用于随后的精英选择过程。以当前种群中处在帕累托前沿面的个体为基准，将其Rank值设定为1，即种群中不存在其他个体可以支配该个体。设定完毕后，将当前种群中Rank值为1的个体移除，重新进行确定新的支配关系，并找出该状态下的帕累托解集。同时将更新后解集中的所有前沿面个体Rank值设定为2，循环往复，直到得出种群中所有个体的Rank等级。图1.1为种群个体Rank等级的示意图。该图中，两个目标均为极小化问题。图1.1种群个体Rank等级示意图Fig.1.1SchematicdiagramofindividualRankofpopulation1.3.2拥挤度计算在确定了所有个体的Rank值之后，为了进一步确保精英选择过程中保留较为优秀的父代个体，使用拥挤度来衡量同一等级间个体的质量好坏。多目标问题的帕累托解集不仅需要确保解的数量，同时也要衡量解集中解的离散程度。拥挤度可以很好的反映每个解之间的距离关系，拥挤度越小，则说明解集中的解越密集，反之则说明该解集中的解较为广泛。拥挤度需要对种群中所有个体的每个目标函数进行升序排序。对于每个目标函数，边界解（即每个目标函数的最大值与最小值）的拥挤度为无穷大。其它解的拥挤度则与其相邻解有关，为其最近两个邻解进行归一化处理后的函数绝对差值。每个目标函数在计算拥挤度时都会进行归一化处理。图1.2为计算拥挤度的实例。在图1.2中，黑色框线的边界点即为个体i的两个相邻解。拥挤度计算的具体步骤如下。初始每个个体的拥挤度di为0。将种群中所有个体基于每个目标函数进行升序排序，并记录于。令边界对应个体di的拥挤度记为无穷大。对其他个体进行拥挤度计算，。图1.2种群个体拥挤度示意图Fig.1.2Schematicdiagramofindividualcrowdingdegreeofpopulation1.3.3精英策略在经过支配排序与拥挤度的计算之后，种群中的任意两个个体Xi和Xj都可根据上述属性进行优劣比较。若Xi处于非支配层，即Xi的Rank值大于Xj，则个体Xi相对于个体Xi较优。如果二者Rank值相同，则比较他们的拥挤度数值，拥挤度较大的个体较优，即id>jd。精英选择策略可以将种群中的优秀个体保留下来，作为新一代的父代个体，进而提高子代解的质量，同时也确保了当前种群中的最优解不会丢失。精英选择过程首先将父代种群Pd与子代种群Qd合并成新的种群Rd，此时Rd种群的大小为2n。合并完成后对Rd中个体进行Rank等级以及拥挤度计算。计算完毕后按Rank等级从小到大的顺序以此将个体添加到新父代种群Pd+1中。当某个Rank等级添加完毕后超出Pd+1规模时，按该Rank等级拥挤度大小重新添加，直到填满新父代种群Pd+1。精英选择过程如图1.3所示。图1.3精英选择过程示意图Fig.1.3Schematicdiagramofeliteselectionprocess1.3.4算法框架在多目标问题中，由于各目标之间往往相互约束，因此需要将单目标的人工蜂群算法的邻域结构进行调整。本章根据多目标问题的特点，对已有邻域搜索方式进行改进以适用多目标问题。在保留交换、前插、保留等基本结构不变的前提下，根据目标函数的性质，引入LPT以及SPT启发式思想，丰富邻域结构。LPT策略在解序列长度内随机生成两个不同的数和，并令大于。将到之间编码按对应工序的处理时间进行降序排序，即LPT规则，生成一个新的解序列。SPT策略在解序列长度内随机生成两个不同的数和，并令大于。将到之间编码按对应工序的处理时间进行升序排序，即SPT规则，生成一个新的解序列。在单目标问题中，人工蜂群算法通过轮盘赌的方式选择搜索蜜源。而在多目标问题中，由于各目标函数之间无法进行线性归一化，因此需要更改选择方式。在NSABC算法中，跟随蜂通过二进制择优的方法，随机选择某个个体进行搜索，搜索过程与单目标问题类似。在侦察蜂搜索过程中，单目标问题对当前最好解进行10次侦察蜂搜索。而在多目标问题中，则对当前帕累托解集中所有个体进行10次侦察蜂搜索。完整的NSABC算法流程由如下伪代码给出。NSABC算法伪代码1开始2;3初始化蜜源列表Ps，进行快速非支配排序；4；5Whileτ<geneartiondo6Forn=1topopnum7对Ps中个体进行搜索过程8将当前蜜源列表记为Qs9Endfor10合并两个蜜源列表Ps和Qs记为Rs11对新蜜源列表Rs进行快速非支配排序，相同等级个体记为Fi12对相同Rank等级个体进拥挤度计算，并按数值大小进行升序排序13Fori=1toRANKdo14IfPs+1+Fi<=popsize15将Fi的个体全部并入新的蜜源列表Ps+1中；16Else17计算Fi中个体的拥挤度并按照非降序排序，并将新的父代Ps+1中的个体数补全至popsize18Endif19Endfor20s=s+121Endwhile22返回帕累托解集F23End1.4基于大规模问题的DS-LPT启发式算法(1)DS-LPT启发式算法流程在多目标的加工作业问题中，在优化每个代理商的最大完工时间和这一目标函数时，将势必会导致另一目标函数的恶化。因此本节将结合上述两个不同目标对应的启发式算法思想，设计了一种DS-LPT启发式算法。在DS-LPT启发式算法中使用任务的总剩余处理时间来确定当前设备进行作业的任务。若当前任务为最后一道工序，则抢占该设备，优先进行加工。该启发式算法思想可以被描述为：任务i在调度过程中的任意时间点到达，若其工序对应的设备可用则立即开始作业。若该设备被占用，则该设备完成当前工序后，若可处理任务数大于1，根据所有任务的已完成工序情况及处理时间来决定排序。若存在某个任务当前设备为最后一道工序则优先选择。若不存在该任务，则选择当前剩余总处理时间最大的任务进行排序。在满足上述情况下，若仍存在多个处理时间相同的任务，则根据给定任务编号从小到大依次排序。下面给出一个设备数为3，任务数为4的DS-LPT启发式算法实例。该例子中任务的处理时间，释放时间与工序则分别由如下矩阵给出。在该例中，J1和J2仍为代理商A所属任务，J3和J4则对应B代理商所属任务。图1.4为该例子对应的最终调度甘特图。该甘特图对应的A、B代理的完工时间和为55，所有任务的平均完工时间则为21.75。图1.4DS-LPT启发式算法甘特图Fig.1.4GanttchartofDS-LPTheuristicalgorithmDS-LPT启发式算法框架DS-LPT启发式算法的具体过程由如下伪代码给出。DS-LPT启发式算法伪代码1开始2Forj=1todo3If当前只有一个任务j可被处理4将该任务j的当前工序安排到所对应的设备m上，更新任务j当前工序对应设备上的完工时间Cm,j，当前设备m处理过的任务数加15Endif6If当前设备m有多个任务可被处理7首先考虑是否存在最后一道工序的任务。若存在该类任务，则选择处理时间最长的任务j。若无该类任务则记录当前设备待处理任务的剩余处理时间，选择剩余处理时间最长的任务j。若此时仍存在多个处理时间相同任务，则选择任务编码最小的任务j。更新任务j当前工序对应设备上的完工时间Cm,j，当前设备m处理过的任务数加18Endif9Endfor10返回以及11结束1.5数值仿真实验本章实验算法均由C++语言编写，CodeBlocks编译。实验所用环境的操作系统为WindowsServer2016标准版。服务器CPU型号为Inter(r)Xeon(r)Gold6278CCPU@2.60Ghz2。系统的运行内存为8GB。在本节的数值实验中，A代理的任务数仍为总任务数的30%至50%。1.1.1智能优化算法本节将通过NSABC算法与NSDE算法的数值仿真实验来验证算法求解多目标加工作业问题的能力。数值实验中设备数m={3,5,8}，任务数n={30,50,80,100}。处理时间与释放时间仍为U(1,10)与U(0,3n)的离散均匀分布。在单目标问题的实验分析过程中，可以直接将目标函数值进行比较。而在多目标问题中，由于各目标之间相互独立，因此无法进行简单的数值比较。本节将使用一些针对多目标问题的评价指标来衡量算法性能。在数值实验中，NP为最终帕累托解集中解的个数，该指标可以直观的反应解的广泛性。为了验证最终解的质量，则使用C-metric指标比较两种算法间的支配关系。该指标的计算方法如下。(1.8)其中A，B为待比较算法，|A|表示该算法中最终解集解的个数。a，b分别代表该算法得到的帕累托解集中的某个解。表示对于A算法中的某个解a，在B算法中存在a可支配的解。该指标的取值范围为[0，1]，同时。0表示A算法中的所有解均无法支配B算法得到的解。该指标数值越大，则表明A算法得到的解可支配B算法的比值越大。D-metric指标衡量了算法所获得最终解集的均匀性，该指标的计算方法如下。(1.9)其中为算法获得该问题的帕累托解集，为除去当前解之外的其余帕累托解对应集合，表示解集中任意解v到其余解的欧氏距离。超体积指标HV为算法获得的帕累托解集和参照点所围目标空间区域的超立方体体积。该指标同时衡量了解集的收敛性与多样性。该指标的数值越大，则说明算法的综合性能越好。HV的计算方法如下。(1.10)该式中，表示勒贝格测度，用以计算超立方体体积。为帕累托解集中解的个数，vi表示参照点与解集中第i个解所围成的超立方体体积。在本章对应的二维优化问题中，首先将帕累托解集中的所有解根据第一维目标函数值进行降序排序，则该超立方体体积即排序后相邻解在平面直角坐标系中根据两个目标函数值所围城的平面面积。针对多目标问题，正交实验的主效应值则为该参数组合下获得的帕累托解个数占最终解集的百分比。根据正交实验获得的人工蜂群算法参数为：邻域列表长度为15；邻域搜索次数为25。不同设备数与任务数的组合均生成十组数据。每组数据则进行5次的独立重复实验来减少随机误差。实验结果如表1.1所示，实验数据为对应问题规模的十组数据均值。数据表中，为了防止HV指标一列数据差异过大，使用了对数归一化的方法。由于多目标优化问题相对于单目标问题更加复杂，因此智能优化算法在求解时有很强的随机性，进而导致NP指标在不同规模上的波动性较大。但从总体上看，两种算法在求解不同规模的问题时均在合理范围内上下浮动，因此问题规模对该指标影响不大。从均值上看，NSABC算法每次可以生成2.52个解，NSDE算法该指标则为2.55。尽管NSABC算法解的个数较小，但是差距也微乎其微。在衡量帕累托解集质量的指标C-metric上可以看出，NSABC算法取得了压倒性的优势。C(NSABC,NSDE)在所有规模上均大于C(NSDE,NSABC)。同时当问题规模扩大时，C(NSDE,NSABC)有逐渐减小的趋势，这说明NSDE算法随着问题规模的扩大，解决多目标加工作业问题的能力相对于NSABC算法有所下降。从该指标均值来看，C(NSABC,NSDE)为0.917，而NSDE算法对应的数值仅为0.225。这表明NSABC算法所获得最终解的质量更高。这是因为NSABC算法的邻域搜索过程融合了加工作业问题的性质，相对于NSDE算法，搜索效率更高，得到较好解的几率也就更大。从均匀性指标D-metric来看，NSABC算法在10个问题规模中的数值较小，占到了所有规模总数的83.3%。同时从指标均值看，NSABC算法为9.613，也小于NSDE算法的10.401。这说明NSABC算法在帕累托解集质量较好的前提下，最终解集内的解分布较为均匀。而从综合性评价指标HV来看，NSABC算法也在10个问题规模上占优，同时均值也要优于NSDE算法。结合上述指标来说，NSABC算法无论是从综合评价上来看，还是解的质量与解集均匀性来看，均优于NSDE算法。仅在最终解个数NP这一指标上略低于NSDE算法。尽管如此，该指标数值差距也不足2%。因此可以说明，在解决多目标加工作业问题上，NSABC算法相对于NSDE算法的求解性能更优。表1.1多目标加工作业智能优化算法结果Table1.1Resultofintelligentalgorithmsformulti-objectivejobshop问题规模NPC-metricD-metricHVNSDENSABCNSDENSABCNSDENSABCNSDENSABC3*3070.947.154.421.851.673*5000.918.167.426.297.303*8030.897.9310.306.437.763*10080.8913.8212.917.328.565*3090.868.326.541.526.065*502.039.338.771.746.295*8030.889.858.027.797.945*10070.9613.4210.867.557.128*3020.967.566.726.106.198*503.058.619.606.496.918*8080.9010.9310.026.917.348*10070.9616.4814.587.638.17Ave2.552.520.2250.91710.4019.6136.7067.2401.1.2启发式算法本节数值实验将验证所提出的DS-LPT算法在求解大规模多目标加工作业问题时的性能。数值实验中，设备数m={3,5,8}，任务数n={100,200,500,800,1000,1500}。任务的处理时间，释放时间与工序的生成方式与4.1.2节中DA-LPT启发式算法的数值实验保持一致。与单目标问题的启发式算法数值实验不同之处在于，在本节的数值实验中将会分别与每个目标函数对应的下界进行对比。本章多目标问题的两个目标下界首先均松弛掉工序约束及设备运行时不可中断约束。在松弛掉该约束的基础上针对每个代理完工时间和目标函数使用LPT规则，所有任务的平均完工时间则使用SPT规则进行调度排序。DS-LPT启发式算法得到的目标函数值记为Obj，每个目标函数的下界值为LB，同样使用GAP指标来评价启发式算法的性能。表1.2多目标均匀分布处理时间实验结果Table1.2Multi-objectiveexperimentresultinuniformdistribution问题规模m=3m=5m=8f1f2f1f2f1f2n=10031.36%20.08%41.41%34.64%57.94%53.48%n=20031.54%19.67%38.30%30.28%44.36%34.51%n=50031.79%17.75%31.60%21.64%40.19%30.69%n=80030.36%17.98%32.84%21.33%37.34%27.77%n=100029.79%18.02%32.04%23.55%31.41%28.15%n=150029.91%17.16%31.12%22.47%34.10%26.61%表1.3多目标正态分布处理时间实验结果Table1.3Multi-objectiveexperimentresultinnormaldistribution问题规模m=3m=5m=8f1f2f1f2f1f2n=10034.33%23.66%42.65%32.31%62.75%54.04%n=20032.62%22.75%37.04%26.72%44.62%31.85%n=50033.55%20.17%36.29%27.72%41.79%29.65%n=80032.76%18.69%34.82%26.52%36.90%30.06%n=100031.85%19.85%33.02%21.02%31.82%30.04%n=150031.29%17.96%32.91%23.23%31.19%27.46%表1.2和1.3分别为均匀分布处理时间及正态分布生成处理时间下的实验结果。其中f1对应为每个代理完工时间和目标函数的实验结果。f2则对应所有任务平均完工时间的实验结果。实验结果表明，无论处理时间服从均匀分布或是正态分布，尽管实验结果随着问题规模的改变略有波动，但每个目标函数对应的GAP值随任务数增大而减小的趋势还是十分明显的。这说明本章提出的DS-LPT启发式算法适用于求解大规模的多目标加工作业问题。以均匀分布处理时间，设备数为3的情况为例，每个代理完工时间和的目标函数GAP值从100任务数的31.36%下降至1500任务数时的29.91%。而相对应所有任务的平均完工时间目标函数则从100任务数的20.08%下降至1500任务数时的17.16%。而当正处理时间服从正态分布时，设备数为5的情况为例，每个代理完工时间和一列的GAP值从100任务数的42.64%下降到1500任务数时的32.91%。所有任务的平均完工时间的一列则从100任务数的32.31%下降到1500任务数时的23.23%。为了更直观的展现实验数据所呈现的规律，图1.5为均匀分布处理时间情况下两个目标函数对应的实验结果折线图。图1.6则为正态分布处理时间情况下不同目标函数的GAP值变化情况。从图1.5和1.6可以看出，尽管偶尔出现数据波动的情况，但GAP值总体的下降趋势仍十分明显。处理时间服从不同分布时的实验规律也大致相同。同时可以看出，尽管数据总体呈现下降趋势，但相比与