资源描述：
《基于克隆策略的作业车间调度算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、基于克隆策略的作业车间调度算法叶宁I,杨东升2,张晓琳2,宋晓峰2h宁夏民族职业技术学院，宁夏吴忠，75110Q2西安通信学院基础部，西安，710106摘要：深入分析了邻域结构对进化算法屮邻域搜索性能的影响，并提出改进的邻域结构。在此基础上，以发挥调度编码的优势和提高求解性能为出发点，有效结合邻域搜索和克隆选择算法设计了一种基于邻域搜索的克隆算子，并提出了运用此算子的克隆选择算法来求解作业车间调度问题。该算法对当询国际文献中的benchrarWu
2、题实例进行了测试，取得了较好的效果。关键词：作业车间调度：调
3、度编码：邻域搜索；克隆选择ClonalSelectionStrategyBasedonJob-ShopSchedulingAlgorithmYENing,YAMGDong-sheng,ZHANGXiao-Lin,SONGXiao-feng1.EducationDepartmentofNingXiapolytechnic,WuZhong,China,751100;2.BasicDepartmentofXi'anCommunicationInstitute,Xi'an[Abstract]Theneighborh
4、oodstructureisdiscussedfirstly,whichisimportantforneighborhoodsearchperformanceofevolutioncomputation.Andthentheimprovedneighborhoodstmctureisproposed・Onthisbasis,inordertotakeadvantageofschedulingcodeandimprovetheperformanceforsolvingJob-ShopSchedulingPro
5、blem(JSSP),aclonaloperatorbasedonneighborhoodsearchisdesigned,andtheclonalselectionalgorithmbasedonneighborhoodsearch(CSA_NS)forJSSPisproposed・Intheexperiments,thebenchmarkJSSPproblemsarcusedtotesttheperformance・Allexperimentalresultsshowthatourmethodiseff
6、ective・[Keywords]Job-Shopscheduling;Schedulingcode;Neighborhoodsearch;clonalselection1•引言作业车间调度问题⑴(Job-ShopSchedulingProblem,JSSP)是一种典型的组合优化问题，求解调度问题的算法很多。到日前为止，主要形成了三人类：精确算法、启发式方法利御能搜索算法。其屮比较典型的算法有调度规则、数学规划方法、人工神经网络、模拟退火算法、遗传算法2叭禁忌搜索算法和启发式搜索算法等。这些算法各有不同的特
7、点，在各种条件下的性能也各不相同。由TJSSP问题具有强约束和解的搜索空间大的特点，这是问题本身带来的求解复杂度，并且随问题规模的增大，复杂度将以更快的速度增长。木文在研究现有JSSP求解方法的基础上，重点关注了基于克隆策略⑷的JSSP求解。通过构造新的克隆算子，提出了基于邻域搜索克隆选择的作业车间调度算法。在用克隆策略求解作业车间调度问题时，当抗体种群采用调度编码⑸方式，不仅要考虑抗体所表示调度的可行性，而且还耍考虑克隆的合法性，保证克隆的质屋。因此克隆算子的构造成为了瑕主耍的问题，并且要针对调度编码的特
8、点，设计适合该编码的克隆算子。此外，山于关键块对调度解的决定性作用，所以木文中克隆算子的设计从关键块展开，紧紧围绕着最大限度提高解的质量这个目标，融入邻域搜索机制，设计了基于两种邻域结构的克隆算子，称为基于邻域搜索的克隆算子。借鉴免疫记忆克隆规划算法的记忆利遗忘的思想，在克隆选择算法中加入了死广策略，从而增加种群的多样性，加大搜索范围。最后提出了基于邻域搜索的克隆选择算法(简称为CSA_NS)求解作业车间调度问题。2•基于邻域搜索的克隆算子构造邻域搜索是一利「广泛应用于求解组合优化问题的局部搜索技术⑹，•其
9、求解速度快，可以满足解决实际问题的需要，而且可以通过优化设计局部搜索算法得到绘优解，因而已经成为求解JSSP的有效方法。基本邻域搜索方法通常从一个初始解龙开始进行搜索，对初始解龙做一些移动得到的解兀的邻域N("),然后在邻域N(")内搜索更好的解分，若有，则把它作为新的暂定解兀，再次变化得到邻域NS),继续搜索"3)中更好的解。否则输出暂定解，停止搜索。在邻域搜索屮，邻域结构的定义在很大程度上影响邻域搜索方法的效
