用改进遗传算法解JobShop问题

《用改进遗传算法解JobShop问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、中山大学硕士学位论文用改进遗传算法解Job-Shop问题姓名：朱旭东申请学位级别：硕士专业：计算机软件与理论指导教师：常会友2003.5.18摘要遗传算法作为一种全局随机搜索算法引起了人们的广泛关注，具有通用性、隐含并行性和全局解空间搜索等特点，在机器学习、模式识别、图像处理、组合优化等领域得到了成功应用。jJob--Shop问题(简称JSP)是NP完全问题，是许多实际问题的简化模型。开发求解JSP的有效算法是调度和优化领域的重要课题，迄今，研究JSP的方法包括传统的运筹学方法、启发式规则、DEDS方法、仿真方法、神经网络等。由于遗传算法的隐含』1：

2、行性和全局解空问搜索能力等特点，使遗传算法在解JSP中得到，’。泛的关注，并成为研究热点。但是标准遗传算法解JSP有收敛速度慢或不能收敛、易陷于局部最优等缺点。本文提出一种新型的改进遗传算法，通过抢占式解码和其他改进操作相结合，能有效的改善算法的全局收敛性、提高算法的收敛速度。通过对比试验表明，在解决JSP问题方面有较好的效果。关键词：遗传算法，Job--Shop，’调度。抢占式解码AbstractThegeneticalgorithm，aglobalrandomsearchingmethodwhichischaracterizedbygeneral

3、ity,implicitparallelismandglobalsearching，hasattractedalotofattentioninrecentlyyearsandhasbeensuccessfullyappliedinthefieldofmachine-learning，patternrecognition，imageprocessingandcombinatorialoptimizationJob-ShopProblem(JSP)isanNPcompleteproblemandasimplifiedpatternofmanypracti

4、calproblemsTherefore，howtofindeffectivesolutionstoJSPisakeyissueinthefieldofscheduleandoptimizationSofar,themethodsofstudyingJSPinclude：operationalresearchmethod，heuristicmethod，DEDSmethod，emulationalmethodandneutralnetworkmethodetc．Withitsadvantagesofimplicitparallelismandglob

5、alsearching,geneticalgorithmhasattractedalotofattentionandhasbecomeahotspotinsolvingJSP．However，standardgeneticalgorithm(SGA)tendstoconvergeslowlyorfailtoconvergeandfallsintothetrapoflocaloptimization．Inthisthesis，anewimprovedgeneticalgorithm(IGA)ispresentedtosolveJSP．Bythecomb

6、inationofrace—to—occupydecodingandotherimprovedoperations，IGAiseffectivetoimproveglobalconvergenceandconvergencespeedofalgorithmTheresultsindicatethatIGAisapracticablewaytosolveJSPKeyWords：geneticalgorithm，Job—Shop，schedule，race·to—occupydecodingIn用改进遗传算法解Job--Shop问题1．1课题的背景与意义

7、第一章绪论Job．Shop问题(简称JSP)是NP完全问题，是典型的调度问题，也是许多实际问题的简化模型，具有很强的工程背景，许多实际工程问题可以与之相互转化。Job—Shop可以描述为：n个工件在m台机器上加工，各工件在各机器上的操作时间已知，事先给定各工件在各机器上的加工次序(称为技术约束条件)，要求确定与技术约束条件相容的各机器上所有工件的加工次序，使某些加工性能指标达到最优。解决JSP的方法(也是求解所有调度问题的方法)，可以分成两类：1、求最优解方法。主要的数学工具有运筹学方法、线性规划方法、非线，H．规划方法、动态规Jiq(DP)方法、组

8、合优化、拉格朗目乘子法、随机优化等等。2、寻找近似最优解方法：包括规则调度方法、仿真调度方法、智能搜索方法(