基于免疫遗传算法的job shop调度问题研究

《基于免疫遗传算法的job shop调度问题研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、浙江．I：业人学硕+学位论文基于免疫遗传算法的JobShop调度问题研究摘要JobShop调度是计算机集成制造系统(CIMS)工程中的一个重要组成部分，它对企业的生产管理和控制系统有着重要的影响。同时，JobShop调度问题(JobShopschedulingproblem，JSP)又是一个典型的NPHard问题，是组合优化问题中最难求解的问题之一。将优化方法的理论研究引入至lJJobShop生产调度领域中，改进算法性能、拓宽算法应用领域，完善算法体系，是一个同时具有理论意义和应用价值的课题。本文分

2、析总结了一些现有的调度算法，针对它们的不足，基于免疫理论和遗传算法，设计了一种新颖的自适应混合免疫遗传算法SIGA(Self-adaptiveHybridImmuneGeneticAlgorithm)。为了更有效地求解JSP，基于SIGA提出了改进的调度算法SIGAII。本文的主要工作如下：1．针对传统免疫遗传算法存在过早收敛及后期搜索效率低的问题，提出一种基于浓度的自适应混合免疫遗传算法(SIGA)，该算法有效融合多种群遗传算法与模拟退火算法的优点，同时在算法中引入生物免疫系统中抗体多样性的维持机

3、制，提出了基于浓度的自适应交叉变异算子和选择策略，通过仿真实验，证明了算法的有效性；2．将该算法应用于求解JSP，给出了一种基于免疫遗传算法的求解方法，以及染色体的编码方法和相应的免疫遗传操作，针对JobShop调度问题的特殊复杂性，本文将转换瓶颈算法(ShiftingBottleneck)和禁忌算法(Tabu)两者相结合，提出了一种瓶颈禁忌算法(STA)，并将瓶颈禁忌算法引入SIGA中，提出改进的自适应混合免疫遗传算法(SIGAII)，加强算法在求解JSP的局部搜索能力，从而进一步提高算法的性能。

4、3．通过对JSP中的经典Benchmarks算例问题进行仿真实验，系统地分析了一些关键参数和算子对算法性能的影响，结果证明改进的自适应混合免疫遗传算法优于其他四种算法，具有更好的全局收敛性能。最后将SIGAII应用于实际的生产调度，满足企业的生产需求，验证算法的实用性。关键词：JobShop调度问题，免疫遗传算法，自适应，局部搜索浙江jr业人学硕+学位论文RESEARCHoNJoBSHoPSCHEDULINGPRoBLEMBASEDoNIMMUNEGENETICALGoRITHMABSTRACTJo

5、bShopschedulingproblem(JSP)，asanimportantpartofcomputerintegratedmanufacturingsystem(CIMS)engineering，isaclassicNP—hardcombinatorialoptimizationproblemandhasvitaleffectonproductionmanagementandcontrolsystem．Also，itisamagnificenttaskforapplyingtheoptimi

6、zationtheoriesintothefieldofJSEThiswillbehelpfultoimprovetheperformanceofexistingalgorithmsandextendtheappliedfields．Inthispaper,someexistingimmunegeneticalgorithmsareanalyzed，andthusanovelself-adaptivehybridimmunegeneticalgorithm(SIGA)basedontheimmune

7、theoryandgeneticalgorithmisdesignedtoalleviatedrawbacksoftheexistingalgorithms．Furthermore，allimprovedSIGA(SIGA-II)ispresentedforeffectivelysolvingJSP．Totally,themaincontributionsofthispaperareasfollows：Firstly,inordertoavoidtheprematureconvergenceandt

8、heslowsearchefficiencyatposteriorevolutionaryprocessofthetraditionalimmunegeneticalgorithm，aself-adaptivehybridimmunegeneticalgorithm(SIGA)isproposed．Thealgorithmefficientlycombinestheadvantagesofsimulatedannealingalgorithmandmulti—grou