资源描述:
《solving job-shop scheduling problems by genetic algorithms based on building block hypothesis》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、SolvingJob-ShopSchedulingProblemsbyGeneticAlgorithmsBasedonBuildingBlockHypothesisInternati0nalJournalofP1antEngineeringandManagementVo1.11No.2June2006SolvingJob.ShopSchedulingProblemsbyGeneticAlgorithmsBasedonBuildingBlockHypothesisCHENGRong.CHENYou-ping,LIZhi—ga
2、ng'1.CollegeofEngineeringandTechnology,ShenzhenUniversity,Shenzhen518060,P.R.China2.SchoolofMaterialsScience&Engineering,HuazhongUniversityofScienceandTechnology,Wuhan430070,P.R.China/nthispaper.wepropose口ngeneticalgorithmforjob—shopschedulingproblems(JSP)?met
3、hodusestheoperation—basedrepresentation,basedonschematheoremandbuildingblockhypothesis.口删crossoverisproposed:Byselectingshort,loworderhighlyfitschemastogenet—icoperator,thecrossovercanexchangemeaningfulorderinginformationofparentseffectivelyandcansearchtheglobalop
4、timization.SimulationresultsonMTbenchmarkproblemcodedbyC++showthatourgeneticoperatorsareverypowerfulandsuitabletojob—shopschedulingproblemsandOUI"methodoutpeoCo几thepreviousGA—basedapproaches.Keywords:job—shopscheduling,geneticalgorithm,schematheorem,buildingblockh
5、ypothesis1IntroductionJob..shopschedulingproblem(JSP)areknownasoneofthemostdifficultorderingproblems.Severalgeneticalgorithm(GA)approacheshavebeentriedtoJSP,,',,.AlthoughtheGAenablesUStoobtaingood—qualitysolutionsquicklyandeasilycomparedtoothersearchtechniques,the
6、restillexistperformancegapsbetweenGA—basedapproachesandotherspecializedexacttechniques.Inthispaper,thecrossoverisconsideredasamainsearchoperator.ToapplyGAsuccessfullytoJSP,thefollowingcriteriashouldbesatisfied引:(1)completeness,anysolutionshouldhaveitsencoding;(2)s
7、oundness,anycodeproducedbygeneticoperatorsshouldhaveitscorrespondingsolution;(3)non—redundancy.codesandsolutionshouldbeonetoone;(4)characteristics—preserving,childrenshouldinheritusefulcharacteristicsfromparents.Inthispaper,weuseoperation—basedrepresenta—tionasenc
8、odingandintroduceanimprovedpartialschedulingexchangecrossoverbasedonschematheoremandbuildingblockhypothesisascrossoveroperator,byselectingshort,loworder