浅议两个求解jsp问题的遗传算法

《浅议两个求解jsp问题的遗传算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、哈尔滨理工大学硕士学位论文两个求解JSP问题的遗传算法姓名：张宏芳申请学位级别：硕士专业：计算机应用技术指导教师：李小平20050301童玺鎏垩三查耋三兰堡圭兰竺鎏圣两个求解JSP问题的遗传算法摘要车间作业调度(JobShopProblem)是一类典型的NP．hard问题，已被证明在多项式时间内得不到最优值。该问题是生产管理中的核心问题，好的求解方法可以促进企业提高生产率。因此，该研究无论从理论还是实际都有重要意义。近年来，对于JSP问题的求解主要有启发式算法和元启发式算法，但各有其不足之处：元启发式方法的

2、运行时间长，可获得较好的解，但其解不稳定；启发式方法可在较短的时间内得到鲁棒性较强的解，但是极少获得较优的解。为了更好地解决问题，将一些解决某类问题较好的算法组合起来，使所形成的混合算法具有两者不可比拟的优势，成为目前研究的热点。本文分别应用病毒遗传算法和混合遗传算法来求解车间作业问题JSP(JobShopProblems)。针对遗传算法求解的早熟和收敛速度慢等问题，提出面向车间作业调度的病毒遗传算法JVGA(JobshoporientedVirusGeneticAlgorithm)，从横向和纵向同时搜索解

3、空间；并提出一种新的病毒浓度概念不仅可以增强病毒群体模式的多样性还可以定量地评价染色体中某段基因的数量，克服了遗传算法固有的早熟问题；其次，定义了基于工件序的十进制编码方式，既避免了死锁的产生也便于解空间和染色体空间转换。根据19个典型JSP问题的对比实验，证明了该理论对于求解JSP问题的有效性。遗传算法初始解的质量对于算法的收敛速度有重要的影响，将解决JSP较理想的改进瓶颈移动启发式算法MSB得到的解作为遗传算法的一个初始解，主群体中其它体随机产生，提出混合遗传算法HGA(HybridGenetic．Al

4、gorithm)。由于MSB所得解的质量较高，而GA算法的精英策略保证HGA所得解的质量不低于MSB算法所得解的质量。两种算法的结合，使算法的时间性能有较大的提高。关键词车间作业调度；病毒遗传算法；瓶颈移动算法；混合算法哈尔滨理工大学工学硕士学位论文TwoGeneticAlgorithmForJobShopProblemsAbstractJSP(Jobshopproblem)istypicallyNP—hard，whichmeansthatitisimpossibletofindtheglobaloptim

5、uminpolynomialcomplexity．JSPisoneofthekeyproblemsintheproductionmanagement．Goodalgorithmsforthisproblemcanpromoteproductivityofenterprises．Sothisthesiscanprovidegoodresultsforboththeoryandpractice．Inrecentyears，meta-heuristicsandheuristicsaretwokindsofalgo

6、rithmforJSP．However,theyaredifferentinCPU—timeandperformance．Meta-heuristiescanalwaysobtainbettersolutionsthanheuristicsbuttheyneedmuchmoreCPU—times．Aswell，robustnessofheuristicsisgoodbutoptimumcanseldombeobtained．CPU—timeisnotcriticalasthedevelopmentofcom

7、putertechniques．Sothequalityofsolutionsispursuedbymostresearchersatpresentbyintegratingsomeheuristicwithameta—heuristicInthisthesis，aVirusEvolutionaryGeneticAlgorithm(VEGA)andaHybridGeneticAlgorithm(HGA)arerespectivelyproposedforJSP．Pre··maturityandslow—co

8、nvergencearetwoissuesexistinginGeneticAlgorithm(GA)forJSP．Fortheabovetwoissues，JVGA(JobshoporientedVirusevolutionaryGeneticAlgorithm)isdevelopedforJSPwiththeobjectiveofmakespanminimization．JVGAsearchesthesolu