资源描述：
《基于主_从遗传算法求解柔性调度问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、第12卷第8期计算机集成制造系统Vol.12No.82006年8月ComputerIntegratedManufacturingSystemsAug.2006文章编号:1006-5911(2006)08-1241-05基于主-从遗传算法求解柔性调度问题1,212张维存,郑丕谔,吴晓丹(1.天津大学管理学院,天津300072;2.河北工业大学管理学院,天津300130)摘要:通过分析柔性作业车间调度问题中工件与设备的特征及两者间的关系,提出了一种主-从遗传算法的调度方案。在该算法中,主、从染色体分别采用工件基因块和设备基因块的分块编码。主染色体代表可行加工路径组合,从染色体代表主染色体约束
2、下的可行调度方案。然后,以最小化工件延迟时间为目标,为主染色体设计选择和多点变异两类遗传操作;以最小化设备空闲时间为目标,为从染色体设计选择、多点交叉和多点变异3类遗传操作。从染色体适应值取其代表的调度方案中工件流通时间的倒数,主染色体适应值取其对应从染色体种群的最优适应值。这种双层多点遗传操作避免了非可行解的产生,并可采用类似旅行商问题的遗传操作。最后,通过仿真和比较实验,验证了该算法的有效性。关键词:遗传算法;柔性作业车间调度;优化中图分类号:F406.2文献标识码:ASolvingflexibleJob-Shopschedulingproblemsbasedonmaster-sla
3、vegeneticalgorithm1,212ZHANGWei-cun,ZHENGPi'e,WUXiao-dan(1.Sch.ofManagement,TianjinUniv.,Tianjin300072,China;2.Sch.ofManagement,HebeiUniv.ofTech.,Tianjin300130,China)Abstract:Ageneticalgorithmwithmaster-slavestructurewasproposedtosolvetheflexibleJob-Shopschedulingproblemsbasedontheanalysisofjobs,
4、machinesandtheirrelationships.Themasterandslavechromosomeswerebrokenintoblocksaccordingtojobsormachinesrespectively.Themasterchromosomesrepresentedfeasiblepro2cessingroutecombinations,whiletheslavechromosomesrepresentedfeasibleschedulingschemessubjectedtomas2terchromosome.Inordertominimizedelayti
5、meofjobs,thegeneticoperatorssuchasselection,multi-pointcrossoverweredesignedforjob-geneblock.Atthesametime,theselectionoperator,multi-pointcrossoveroper2atorandmulti-pointmutationoperatorweredesignedformachine-geneblockinordertominimizeidletimeofma2chines.Thereciprocalofmake-spanwasobtainedasfitn
6、essvalueofoneschedulingschemefromslavechromo2somes.Then,themasterchromosomegotitsfitnessvaluefromthebestfitnessvalueofitsconstrainedslavechro2mosomes.Furthermore,illegalschemescouldbeavoidedandsomegeneticoperatorsdesignedforTravelingSales2manProblems(TSP)couldbeadoptedbecauseofourproposeddoublele
7、velsstructureandmulti-pointsoperators.Thesimulationresultsandcomparisonwithothers'verifiedtheeffectivenessoftheproposedalgorithm.Keywords:geneticalgorithm;flexibleJob-Shopscheduling;optimization所有生产调度中最复杂、最困难,也最具普遍性的问0
