置换流水车间调度问题的两阶段分布估计算法

置换流水车间调度问题的两阶段分布估计算法孙良旭;曲殿利浏国莉【摘要】Aimingtosolvethepermutationflowshopschedulingproblem,minimizingthetotalflowtimeastheobjectivefunction,itproposesanoveltwo-stageestimationofdistributionalgorithm.Inthefirststage,itfirstlyusesNEH(Nawaz-Enscore-Ham,NEH)heuristictoconstructarelativelyoptimalinitialindividual,andthengeneratesinitialpopu-lationrandomly.Tokeepthediversitiesofthepopulation,itputsforwardapreferredmechanismtoselectindividualsandestablishtheprobabilitymodel,andatthesametime,useselitemechanismtokeeptheoptimalindividualinthecontem-porarypopulations.Finallyitusesprobabilitymodeltosampleandgeneratethenextgenerationofpopulation.Inthesecondstage,itusestheinsertandinterchangeoperatortodoneighborhoodsearcharoundtheoptimalindividualwhichisgotinthefirststageinordertoimprovetheglobalsearchabilityofestimationofdistributionalgorithmandpreventitfromentrappingthelocaloptimal.Throughsufficientexperiments,contrastandanalysisforoutcomeoftheexamples,itprovesthefeasibilityandeffectivenessoftheproposedalgorithm.%针对置换流水车间调度问题，以最小化总流水时间为目标，提出了一种新颖的两阶段分布估计算法。第一阶段先利用NEH(Nawaz-Enscore-Ham，NEH)启发式构造一个较优的初始个体，然后随机生成初始种群，为保留种群的多样性，提出一种择优机制来选择个体并建立概率模型，同时在当代种群中利用精英机制保留当代种群中的最优解，最后利用概率模型采样并生成下一代种群。第二阶段采用插入、互换操作算子对第一阶段得到的最优解进行邻域搜索，来提高分布估计算法的全局搜索能力，阻止其陷入局部最优解。通过对算例进行实验、对比和分析，证明该算法的可行性和有效性。【期刊名称】《计算机工程与应用》【年(勤期】2017(053)002【总页数】8页(P64-71)【关键词】分布估计算法;置换流水车间调度问题;NEH启发式;择优机制;邻域搜索【作者】孙良旭;曲殿利浏国莉【作者单位】辽宁科技大学软件学院，辽宁鞍山114051;辽宁科技大学高温材料与镁资源学院，辽宁鞍山114051;辽宁科技大学理学院，辽宁鞍山114051【正文语种】中文【中图分类】TP301SUNLiangxu,QUDianli,LIUGuoli.ComputerEngineeringandApplications,2017,53(2)：64-71.置换流水车间调度问题(PermutationFlowshopSchedulingProblem，PFSP)，是对流水车间调度问题(FlowShopSchedulingProblem，FSP)的扩展，是一类经典的组合优化NP难问题°Johnson最早提出PFSP问题［1］，置换流水车间调度问题的求解方法早期主要是精确算法和启发式算法。精确算法包括解析法［2］、分制定界法［3］等，在理论上可以得到最优解，但是计算时间长，通常只适用于小规模的问题求解。启发式算法，例如NEH［4］，可以在较短的时间内构造问题解，但是解的质量难以保证。近年来，求解流水车间调度问题的智能优化方法得到了广泛的研究，例如遗传算法[5]GeneticAlgorithm，GA）、模拟退火算法[6]SimulatedAnnealing，SA）、禁忌搜索算法[7]TabuSearch，TS）、人工神经网络[8]ArtificialNeuralNetwork，ANN）、粒子课群算法[9]ParticleSwarmOptimization，PSO）、蚁群算法[10]AntColonyOptimization，ACO）、人工免疫算法[11]ArtificialImmuneSystem，AIS）等。分布估计算法[12]EstimationofDistributionAlgorithm，EDA）是近几年在进化计算领域兴起的一类新型优化算法，其提出一种全新的进化模式，成为一个新的研究热点。分布估计算法采用概率模型估计解的分布。相对于遗传算法，分布估计算法不采用交叉和变异操作来生成种群，而是根据对优势群体分布的统计信息，构造概率模型，并使用概率模型来对下一代群体进行采样，避免了由交叉、变异操作带来的缺点。针对置换流水车间调度问题提出一种基于置换的解的个体表达方式，并设计和描述解空间的概率模型及更新机制，提出了一种新颖的两阶段EDA算法，通过实验对比和分析，证明算法的性能和解的质量。PFSP问题可以描述为n个工件在m台机器上进行加工，每个工件有m道工序，每道工序在不同的机器上完成，所有工件加工顺序相同，确定每台机器上工件的加工顺序和调度时间，使工期或总流水时间最小。以总流水时间最小作为调度目标的PFSP问题，使用三元组法可以描述为{n,m,TFT}，即n个工件，m台机器和总流水车间。置换流水车间调度问题可以使用n={n1,n2,...,nn}表示所有工件的一次调度排序，C（ni,k）表示工件ni在机器k上的流水时间，则PFSP问题的模型可以描述为下式表示。分布估计算法是一种基于种群的进化算法，其核心思想是分析优势群体的分布概率模型，并利用概率模型采样和生成下一代群体，即利用概率模型影响新一代群体的分布。选择优势群体、估计优势群体的概率分布模型以及根据模型进行采样是分布估计算法的主要步骤。EDA算法的通用框架如图1所示。EDA算法的核心是概率模型建立和更新，描述解空间分布和种群整体进化态势。根据概率模型的结构和变量间关系，算法分为变量无关、双变量相关和多变量相关三个类型。另外，根据整数编码和实数编码方式，也可分为离散和连续两个类型。根据优化问题类型的不同，需要设计不同的概率模型，描述解空间的分布情况。EDA在解决非线性和变量耦合的优化问题时，可以利用问题的结构信息，产生更好的个体。相对于其他算法，EDA由于采用群体的整体进化方式，使其可以利用解空间的全局信息和进化历史信息，具有更强的全局搜索能力和更快的收敛速度。3.1解的个体表达置换流水车间调度问题中，以工件调度的顺序号的置换，即选用自然数对加工的工件进行编号，工件的编号作为加工顺序，解的长度为工件的数量n，即取所有工件序号的置换n=｛n1,n2,...,nn｝作为一个个体，工件号在置换中的位置标示其在第一个阶段的加工顺序。例如，对于有5个工件的流水车间调度问题，个体｛5,3,2,1,4｝表示在加工的第一个阶段，工件5最先加工，其次是工件3和工件2，然后是工件1,最后加工工件4。3.2初始化种群可以按照均匀分布的方法随机生成含有Psize个个体的种群。为了加快收敛速度，减少解空间的探索时间，对初始种群的生成进行优化。鉴于NEH算法是目前求解置换流水车间调度问题较好的启发式算法，本文利用NEH启发式算法产生一个初始解。种群的第一个解采用NEH启发式算法生成。该算法假设在所有机器上的总加工时间较大的工件比总加工时间较小的工件得到越高的优先级。每次加入一个新工件，求得最好的局部解，最后构造出所有工件的加工顺序。具体步骤如下：按照工件在机器上的总加工时间递减的顺序置换n个工件。取前两个工件调度，使部分最大流水时间达到极小。从k=3到n，把第k个工件插入到第k个可能的位置，求最大的流程时间。为了保证初始种群的多样性，其余初始个体按照均匀分布方法产生Psize-1个个体，即生成个体总数为Psize的初始种群。3.3种群的择优机制为了保留迭代过程中的较优个体，引入保优机制，其实现过程为：在每一次迭代过程中，按照一定的比例选择种群中较优秀的个体，这里的选择比例记作保优比例n。这些被保留下来的个体不经过选择过程，直接作为下一代种群中的个体。步骤如下：(1)对种群中Psize个个体分别计算其TFT值，并将TFT值按照递增顺序置换。(2)以保优比例n选择前nPsize个个体。(3)对剩余的(l-n)Psize个个体，按照式(6)的相对概率选择SPsize-nPsize个个体。其中r表示个体在置换中的位置。通过择优机制从种群规模为Psize的个体中选择其中的SPsize个个体作为优势群体。3.4概率模型建立与更新机制为最大限度获得解空间的分布信息来构建概率模型，并保证初始种群的分散性，初始产生Psize个个体作为初始种群，并计算每个个体的目标值，然后通过择优机制选择其中的SPsize个优良个体，基于SPsize个优良个体建立概率矩阵。本文采用一个NxN维的矩阵P表示解分布的概率模型[13],概率矩阵中每一个元素pij(l)表示第l次迭代中工件nj出现在i位置或i位置之前的概率。即在第l代每个阶段工件nj的加工顺序不迟于i的概率是pij(l)。通过矩阵P可以从数值上反映出不同工件的加工次序关系。对于若干优良解构成的群体，pij(l)越大，表示在第l代工件nj在第i个位置或之前被加工的概率越大。第0代时概率矩阵采用均匀分布的方式对概率矩阵进行初始化，即。概率模型可以表示为式(7)。其中以表示学习率，i表示工件nj所处的位置，j表示工件nj的编号，k表示在优良解中的第k个优质解。其中可以表示为式(8)。3.5采样算法根据初始种群中的优势群体在解空间的分布建立概率模型，在随后的每次迭代中，基于概率矩阵P对下一代群体进行采样。在产生一个新个体时，按照从第1位到第n位顺序采样，依次确定每一个位置的工件编号。对于待确定的第i个位置，则采用轮盘赌的方式选择一个工件号，第l次迭代中工件nj被选择的概率为pij(l)。由于已选择的工件可不能再在i之后的位置出现，需要将pkj(l)赋值为0,其中k>i。如此反复，采样生成第1+1代种群。在第1+1代种群中采用精英机制保留本代种群中的1个最优个体，然后使用概率矩阵采样得到的剩下的Psize-1个个体。3.6停止准则一般EDA算法可以选择最大迭代次数，处理器最大处理时间，目标函数值未改进最大迭代次数，目标函数的最大评价次数作为停止准则，本文算法采用最大迭代次数(MaxTimes)作为停止准则。3.7CEDA算法用于解决流水车间调度问题的混合EDA算法(CombinedEstimationofDistributionAlgorithm,CEDA)的伪代码：有效的邻域搜索策略是改进算法效率和解的质量的有效方法，本文算法在EDA算法找到的最优解的基础上，对其邻域采用交换(interchange)、插入(insert)操作算子，对CEDA算法进行改进，提高算法的全局搜索能力。interchange操作算子是交换最优个体中两个工件的调度顺序，其他位置的调度顺序不发生变化，通过交换操作得到新个体，交换操作算子可以表示为式(9)。insert操作算子是通过对个体中调度排序的移动，将源位置的工件插入到目标位置，其他位置的工件的调度次序也会依次向前或者向后移动，通过这样的方法达到生成新个体的目表，可以表示为式（10）。本文采用两阶段的方法CEDA-VNS算法来改进CEDA算法，在第一阶段先对PFSP问题采用CEDA算法进行求解，第二阶段对CEDA获得的最优解先进行interchange操作算子进行邻域搜索，再进行insert操作算子进行邻域搜索，迭代指定的次数以后，输出最优解来改进CEDA算法的解的质量。邻域搜索算法的伪代码：5.1算例算法采用C++语言编写，使用IntelI3处理器，使用Win7操作系统，处理器为2.4GHz,8GB内存。为检验提出的两阶段EDA算法的性能，采用Taillard标准测试问题中的部分实例进行测试，选取问题规模为20x5、20x10、20x20、50x5、50x10、50x20、100x5、100x10、100x20共9组，每组使用10个实例对算法进行测试。对每个实例分别执行20次，利用式（11）取20次中最好解与最优解比较得到相对百分比偏差，最后将这20次执行结果的平均相对百分比偏差ARPD作为算法的性能指标。为了验证两阶段EDA算法（CEDA-VNS）对PFSP问题的求解质量，将CEDA-VNS算法的实验结果与本文提出的第一阶段采用的混合分布估计算法（CEDA）以及较先进算法混合遗传算法（HybridGeneticAlgorithm,HGA）、邻域搜索算法（VariableNeighborhoodSearchAlgorithm,VNS）以及基本EDA算法进行比较，实验结果如表1~3所示。其中迭代次数MaxTimes=1000，邻域搜索迭代次数MaxEvaluateTimes=100，种群个数Psize=100，保优比例q=2%,优良种群规模SPsize=20，学习率a=10%。5.2提出算法与基本EDA算法比较本节针对文中提出的两阶段分布估计算法（CEDAVNS）与基本EDA算法的实验结果进行比较。两个算法均采用C++语言编写，主机操作系统和配置完全相同，参数设置也完全相同。即基本EDA算法的迭代次数MaxTimes=1000，种群规模Psize=100，优良种群规模SPsizea=20，学习率a=10%。对同一组测试实例，比较目标函数值总流水时间（TFT）与迭代次数间的变化关系。如图2~10所示，显示了不同种群规模实例TFT值与迭代次数之间的关系。图2~4显示了工件数为20，机器数分别为5,10和20的两种算法的实验对比结果，图5~7显示了工件数为50，机器数分别为5,10和20的两种算法的实验对比结果，图8~10显示了工件数为50,机器数分别为5,10和20的两种算法的实验对比结果。显然对于不同规模的算例，两个算法都能最终收敛，但是CEDA-VNS算法较基本EDA算法具有更好的收敛性和全局搜索能力。5.3实验结果分析表1~3中用斜体来表示最优解，用星号来表示在执行过程中至少有一次能够得到最优解，加粗表示最小的相对百分比偏差。由表1数据可以看出，在种群规模为20x5、20x10、20x20时，CEDA算法在30个测试实例中有21个能够得到最优解，基本EDA算法有19个能够得到最优解。HGA算法、VNS算法和CEDA-VNS算法都能取得最优解，而且相对百分比偏差均为0。这说明在问题规模较小时，CEDA-VNS算法的求解质量较HGA算法、VNS算法在求解时，解的质量都比较好。相反，基本EDA算法和CEDA算法在求解质量方面没有提出的两阶段EDA算法佳。但是CEDA算法相较基本EDA算法而言，求解质量稍好。由表2数据可以看出，当种群规模为50x5、50x10、50x20时，CEDA算法在30个测试实例中仅有2个能够得到最优解，基本EDA算法仅有1个能够获得最优解。VNS能够获得7个最优解，HGA算法能够获得20个最优解，而CEDA-VNS能够获得22个最优解。从统计结果看，当种群规模中等时，HGA算法和CEDA-VNS算法获得最优解数量差不多，但HGA算法得到的解的质量更好。表3数据显示当种群规模为100x5、100x10、100x20时，CEDA-VNS算法在30个测试实例中有22个能够获得最优解，其中13个为新的最优解，HGA算法获得了30个实例中9个最优解，VNS算法、基本EDA算法和CEDA算法都没有获得最优解，统计结果说明对于大规模种群，CEDA-VNS算法无论从解的质量还是最优解的获取都明显好于其他几种算法，这充分证明了两阶段EDA算法在解决高维问题方面所具有的优势。总之，CEDA-VNS算法在求解不同规模问题时，都具有比较明显的优势。CEDA算法由于其加入了NEH启发式来构造初始解，在提升了初始解的质量的同时，使算法容易陷入局部最优，而加入邻域搜索阶段的CEDA-VNS算法，很好地弥补了启发式带来的影响，在提升初始解的质量同时，保证最优解的获取。本文提出了一种新颖的两阶段分布估计算法（CEDAVNS）解决流水车间调度问题，第一阶段提出CEDA算法，首先利用NEH启发式构造一个较优初始个体，然后随机生成初始种群，为保持种群的多样性提出一种择优机制来选择优良个体，并在此基础上建立概率模型，同时在当代种群中利用精英机制保留当代种群中的最优解，利用概率模型采样生成下一代种群。第二阶段是以CEDA算法获得的最优解作为输入，采用邻域搜索算法来提高分布估计算法的全局搜索能力，阻止其陷入局部最优解。通过对9组每组10个测试实例分别采用HGA算法、VNS算法、基本EDA算法、CEDA算法和CEDA-VNS算法进行实验对比和分析，证明CEDA-VNS算法的性能和解的质量。【相关文献】JohnsonS.M.Optimaltwo-andthree-stageproductionscheduleswithsetuptimesincluded[J].NavalResearchLogisticsQuarterly，1954，1（1）：61-68.ChuC，PortmannMC，ProthJM.Asplitting-upapproachtosimplifyjob-shopschedulingproblems[J].InternationalJournalofProductionResearch，1992，30（4）：859-870.BalasE.Machineschedulingviadisjunctivegraphs:animplicitenumerationalgorithm[J].OperationsResearch，1969，17:941-957.NawazM，EnscoreE，HamI.Aheuristicalgorithmforthem-machine，n-jobflowshopsequencingproblem[J].Omega，1983，11（1）：91-95.ValladaE，RuizR.Geneticalgorithmwithpathrelinkingfortheminimumtardinesspermutationflowshopproblem[J].Omega，2010，33:57-67.OsmanI，PottsC.Simulatedannealingforpermutationflow-shopscheduling[J].Omega，1989，17:551-557.NowickiE，SmutnickiC.Afas