置换流水车间调度粒子群算法与参数设置分析

1、置换流水车间调度粒子群算法与参数设置分析第34卷第6期2021年12月武汉理工大学(交通科学与工程版)JournalofWuhanUniversityofTechnology(TransportationScience&.Engineering)置换流水车间调度粒子群算法与参数设置分析*刘志雄.'严新平.'赵润军'(武汉科技大学机械自动化学院"武汉430081)(天津港(集团)博士后科研工作站天津300461)(武汉理工大学水路公路交通平安控制与装备教育部工程研究中心武汉430063)摘要:针对置换流水车间调度问题,在介绍了基于粒子位置次序的粒

2、子群算法二维编码方法之后,采用惯性权重线性递减粒子群算法对置换流水车间调度问题进行了优化.在此根底上,对粒子群算法的相关参数设置问题展开分析,主要针对惯性权重的取值,粒子群种群数量,粒子位置和速度将有助于提高求解置换流水车间调度问题的粒子群算法优化效率和优化性能.关键词:粒子群算法;置换流水车间;调度;参数设置;实验分析0引言置换流水车间调度问题(permutationflowshopschedulingproblem,PFSP)是对流水车间调度问题(flowshopschedulingproblem)的延伸.对于流水车间调度问题,如果在每台机器上加工的工件顺序也相同,那么此时的问题就是置换流

3、一定的加工工艺约束,随着问题规模的增加,调度问题的解空间容量巨大,其求解过程仍十分复杂.已有的研究成果已经说明,智能优化算法能够有效地对调度问题进行优化,从而得到调度问题的最优解或者次优解.粒子群算法(particleswarmoptimization,PSO)是一种基于群体智能的进化类算法,在连续函数优化问题领域,粒子群算法显示了其有效问题,如调度问题.目前,对于连续空问的函数优化问题,粒子群算法相关参数的设置已经得到一些学者的分析蜘,其研究结果也说明粒子群算法的相关参数设置对粒子群算法的优化性能有着较大的影响.而对于调度问题,更多的研究那么放在了对粒子群计算模型的改良以及相关的编码及解码方

4、法等方面,而对于粒子群算法相关参数问题的探讨,相关研究比拟少.本文在介绍了置换流水车间调度问题粒子群优化算法的编码方法后,分别利用根本PSO,惯性权重线性递减PSO和带收敛因子的PSO对置PSO算法,对粒子群算法的相关参数,包括惯性权重,粒子种群数量,粒子位置和速度的初始化以及粒子位置和速度限制等进行分析.1置换流水车间调度问题的描述假设t,.,为工件.,在机器J上的加工时间;.J为机器志上加工完工件.,后马上加工工件所需的准备时间(如果不加特殊说明,一设各工件按照机器1m的顺序进行加工,令J=(1,.,)为所有工件的一个加工排序,那么有收稿日期:2()lO0710刘志雄(1975一):男,在

5、站博士后,副教授,主要研究领域为生产凋度及其智能优化算法国家自然科学基金工程(批准号:70801047),中国博士后科研基金工程(批准号:20210450769),湖北省教育厅科学技术研究计划优秀中青年人才工程(批准号:Q2021l115)资助武汉理T大学(交通科学与工程版)2021年第34卷fCtjJCj,一Cj厂l,-+.,+,ICj一Cj1一l+【CJ,maxC2+厂l,Cj一l+tj,i一2,m;J一2,n(1)minfminCj.,(2)2求解PFSP的粒子群算法设计采用基于粒子位置次序(particlepositionsequence,PPS)的二维编码方法,即采用粒子位置的次序来

6、映射调度问题巾的工件或者任务次序,维粒子编码方法时,第一维用自然数1,2,3,n来表示个工件,第二维表示粒子的位置向量值.粒子的长度为所有加工工件的数量,一个完整的二维粒子如表1所列.表1二维粒子编码方法工件1位置zn2.2解码过程(调度方案的生成)在进行调度计算之fjif,对二维粒子巾的粒子位置向量值进行从小到大的排序,同时,各位置向量值对应的工件序弓'排列也发牛改变,由此生成的新的工件排序即为有效的调度方案,即将位置向量值较小的对应的工什先加工.采用惯性权重线性递减PSO,对置换FlowShop调度中的典型算例(Car类问题)进行优化的一类针对置换FlowShop调度问题的典型汁算

7、算例,包含8个算例,分别是Carl(11×5)(11×5表示问题的规模,即11个工件5台机器,其他算例类似),Carl(13×4),Carl(12×5),Carl(14×4),Carl(10×6),Carl(8×9),Carl(7X7)和Carl(8×8).性权重线性递减PSO模型,那么是设定式(3)中的惯性权重训随着迭代次数线性递减时,本文设定从0.9线性递减至0.4.c一f一2.Vi+l一酬z+f1nd.m()(一)+(3)C2random()(g)z件1一:ri+l(4)对于每个问题,设定最大迭代次数为300

8、次,粒子的初始位置是在0,2之间随机产生,而速度时,为了对算法进行比拟,本文采用遗传算法GA对Car类问题进行了计算,计算结果如表2所列.表中最大偏差,最小偏差是指每个算例20次计算指2O次计算后得到的平均值与最优值之间的偏差.表2PSO和GA优化Car类问题的计算结果由表2可见,PSO能够有效地对Car类问题进行优化,其优化结果要好于遗传算法GA的计算结果.3粒子群算法的参数设置分析为了对惯性权重的取值进行分析,本文采用性权重分别取o.2,2之间的不同值,计算结果如图1所示.璺/,t.l/,/,/,.1_|.卜.,叫惯性权重图l不陨性权重取值F的计算结果算结果中,不惯性权重取值下,对于8个C

9、ar类问题,PSO算法的最小偏差均为0,即都找到了最优解.从计算结果看,当权重值在0.8,1,1.3,1.51和1.7,2等范围内取值时,计算结果的最大1,1.5和2时,计算结果的最大偏差和平均偏差者5很/J,.为了分析粒子种群数量对优化性能的影响,这里采用惯性权重线性递减PSO对Car类问题的优化进行分析(下文的参数分析均是采用惯性权重PSO得到的计算结果).设定最大迭代次数为300,重复优化2o次,分别设定种群的数量为第6期刘志雄,等:置换流水车间调度粒子群算法参数设置分析10,20,30,40和5O,计算结果如图2所示67薹;3lO一最大偏差平均值一平均偏差平均值一l【)2():jU4U

10、0U粒子种群数量图2Car类问题的计算结果图2是对Car类问题的计算结果(最小偏差均为O).随着粒子种群数量的增加,最大和平均偏差平均值均是逐渐递减的,说明粒子种群数量的增加可以进一步提高粒子群算法优化调度问题的性能,但同时需要注意的是,当粒子种群数量大于40以后,最大和平均偏差平均值的减小幅度不是很大.因此,综合上述分析,对于优化置换FlowShop调度问题,粒子种群数量取4O50时可以取得较好的优化结果.对于凋度问题,粒子初始位置和初始速度的取值范围是否对优化结果产生影响需要进行分置初始化的取值范围分别为0,2,0,2o,0,6O和0.1ool,同时对于每个位罱取值范,分别没定速度的取值范

11、围为2,2,5,5,1O,1ol,一20,2O,一3O,3O,一4O.40.一50,5o1.L一60,60,一80,sol和100,loo.在每个位置和速度取值范同下,分别计算8个Car类问题的最大偏差和平均偏差(最小偏差均为0),每种情况下Car类问题最大偏差和平均偏差的平均值分别如图3和图4所示.从计算结果看,当粒子速度的取值范围一定时,粒子何置的取值范围越大,优化结果的最大偏差和平均偏差均有增大的趋势;而当粒子位置的取值范围一定时,随着粒子速度取值范罔的增加,一2,21O,1O30,30一5O,5O一8O,8O速度取值范冈图3小同位置和速度取值范围时Car类问题的最大偏差堡诬腰取值范J图

12、4不同位置和速度取值范时Car类问题的平均偏差速度取值范围增加一定幅度时,最大偏差和平均偏差的这种减少趋势那么出现波动,反而可能出现最大偏差和平均偏差逐渐增加的趋势,这种情况对于平均偏差的计算结果较为明显.因此,保持较小的位置初始化取值范围,同时使速度在一个相对较大的范围内初始化取值,PSO算法的优化结果会较好.化范围为0,2,速度初始化的范围为一2,2,在计算过程中,对位置和速度值进行限制,将粒子的速度值限定在一2.2之内,而将粒子的位置向量值分别限定在2,2,一5,5,一10,10,一50,5ol和一10000,10ooo之问,对Car类的8个问题进行优化,每个问题重复优化20次,得到的优

13、化结果的平均偏差如表3所列.从上述计算结果看,山于粒子位置和速度的初始化范围较小,当粒子位置的限定范围较小时,其计算结果的平均偏差平均值就较大,优化性能相对较差;当粒子位置的限定范围变大时,计算结果的平均偏差平均值变小,这是因为粒子的位置向量值呈现多样性,进而使得生成的调度方案也呈现多样性,算法的搜索范围扩大,从而使得算法的优化性能较好.综合上述分析,对于本文所设计的粒子群算法,可以不对粒子的位置向量设定范罔限制.限制与否对调度优化结果的影响,设定粒子位置子速度的初始化范同和限制范围分别取值在一2,2,一5,5,L一10,10,2O,20和一30,3ol之内.对Car类的8个调度问题进行优化,

14、每个问题重复优化2O次,最大迭代次数为300,经过计算后8个问题的最大偏差和平均偏差平均值如表4所列.1ll11O0OO765432lO瑶?1132?武汉理工大学(交通科学与程版)2021年第34卷表3不同粒子位置限定范围下Car类问题的平均偏差粒子速度的对速度小加限制对速度限制限制范围最大偏差平均偏差最大偏差平均偏差从上述计算结果看,无论是优化结果中的最大偏差还是平均偏差,不限定粒子速度的计算结果均好于限定速度的计算结果.因此,用本文所设计PSO算法优化置换FlowShop调度问题(至少是针对Car类调度问题),对粒子速度不加限制的优化结果要好于限制粒子速度的优化结果.4结束语对于一种优化算

15、法,算法参数的设定直接影问题的粒子群算法,对不同粒子群模型,惯性权重的取值,粒子种群数量,位置和速度的初始化取值范围以及位置和速度的限制范围等相关参数的取置的分析研究,为置换FlowShop调度问题的求解提供了参数的设置范围,有助于提高粒子群算法优化调度问题的优化性能.参考文献1郑大钟,赵千川.离散事件动态系统E1.北京:清华大学出版社,2001.2BruckerP.SchedulingalgorithmM.Fhefifthedition.Berlin:SpringerVerlag,2007.tionC/ProceedingsofIEEEInternationalConferenceonNeu

16、tralNetworks,Perth,Australia,1995:l9421948.E43EberhartRC,ShiYH.Particleswarmoptimization:development,applicationsandresourcesC/Proceedingsof2001CongressonEvolutionaryComputation,Seoul,korea,200l'8186粒子群优化算法J2.河南科技大学:自然科学版,2021,29(6):4952.cleswarn-ioptimizationc/Proceedingofthe7thAnnualConference

17、onEvolutionaryProgramming.WashingtonDC.1998.59卜600.swarmoptimizationc/Proceedingsof1999CongressonEvolutionaryComputation,Washington,D.E82C.USA,Piscataway,N:IEEEServiceCenter,1999,19451949.EiGalladA,Eicingtheparticleswarmoptimizerviaproperparameteesselectionc/Proceedingsofthe2002IEEECanadianConferenc

18、eonElectrical&ComputerEngineering,2002,792797.(下转第1137页)第6期肖同权,等:轿车发动机舱内流动与散热特性数值研究?l137?rateandairrecirculationatvehicleidleconditions_J.SAEpaper,2004010053SimulationonVehicleUnderhoodThermalManagementSystemXiaoGuoquanYangZhigang(SchoolofMechanical&AutomotiveEngineering,SouthChinaUn

19、iversityofTechnology,Guangzhou510640,China)(SchooloAutomotive,TongjiUniversity,Shanghai202104,China)Abstract:TheobiectiveofthisworkistoanalysistheunderhoodairflowandheattransfercharacteristicsofthesamevehicleoperationconditionbyStarCDcodeandtheF1uentcodewereobtainedanddifferentvehicleoperationcondit

20、ionswereobtainedandtheresultsshowedtheETAdecreasesandthemassfluxincreaseastheincreaseofthevehiclespeed.Moreover,theunderhoodheattransfercharacteristicsofdifferentvehicleoperationconditionswerealsosimulatedandanalyzed,theresultsshowtheexistenceofthefrontendairrecirculationshouldbenotedespeciallyatveh

21、icleidlecondition,therearethemosttemperaturedistributionatvehicleuphillconditionwithfull1oadandthefanscanbeshutoffathighspeedfromthepointofviewoftheunderhoodthermalenvironment.Keywords:underhood;airflow;heattransfer;thermalmanagement;numericalsimulation(上接第1132页)ParticleSwarmOptimizationandParameter

22、SettingAnalysisforPermutationFlowShopSchedulingProblemLiuZhixiong''.'YanXinping.'ZhaoRunjun(CollegeofMachinervandAutomation,WuhanUniversityo/ScienceandTechnology,ban430081,China)"(PostdoctoralResearchCenter,TianJinPort(GrouP)Co.,LTDTianin300461,China)(EngineeringResearchCenterofTr""s户