基于改进蚁群算法的车间调度问题研究

《基于改进蚁群算法的车间调度问题研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、东南人学硕士学位论文基于改进蚁群算法的车间调度问题研究姓名：张学权申请学位级别：硕士专业：管理科学与工程指导教师：陈伟达20080301基于改进蚁群算法的车间调度问题研究研究生：张学权导师：陈伟达东南大学摘要车间调度问题是现代制造业中共存的问题。随着制造业的发展，出现了大量复杂的制造系统，如柔性制造系统、计算机集成制造系统，为车间调度问题的研究提出了新的要求，追切需要研究与Z相适应的车间调度方法，近年来，用蚁群算法研究车间调度问题成为新的研究热点，并取得了良好的寻优效果。但H前对于蚁群算法的理论研究和实际应用远不及对遗传算法，模拟退火等算法

2、的研究成熟，存在诸多需要研究和探索的问题。本文首先论述了蚁群算法与遗传算法的算法机理、国内学者对于蚁群遗传复合算法的研究成果，并用蚁群算法解决TSP问题以论证蚁群算法在解决组合优化问题上的有效性。然后用基木蚁群算法研究了JSP问题，主要研究成果有：在有约束条件下对Job・shop问题进行模型化，用图形法表示作业调度工序集，并针对图形法引入蚁群算法寻优。给出了蚂蚁搜索的虚拟起点概念及每步搜索的可行结点集与算法详细步骤。并基于基本蚁群算法，对Muth&ThomPson6*6标准JSP问题进行了仿真实验。针对传统的蚁群算法解决Job.shop问题

3、的不足，本文对此算法进行改进，主要研究成果有：取消了传统蚁群算法中的路径启发信息素，采用了带随机因子的状态转移规则，使用双挥发系数的双向收敛蚁群算法为轨迹更新规则，用改进的蚁群算法來解决JSP问题，与基本算法作了对比，优化了算法参数.对于较复杂的车间调度问题，由于单纯用蚁群算法解决不够理想，本文提出一种新的蚁群遗传复合算法，将遗传算法融入到蚁群算法的算法流程屮，用遗传算法来改进蚁群算法。针对遗传算法解决Job.shop的特点，引用一种新的交叉操作，对跨机器调度作随机保持的交叉算了，最后利用复合算法对JsP问题进行了仿真实验。关键词：蚁群算法

4、；遗传算法；蚁群遗传复合算法；车间调度；双挥发系数BASEONIMPROVEDANTCOLONYALG0RITHMTo0PTIMIZEJ0B.SH0ps；CHEDULINGPROBLEMGraduate：ZhangxuequanInstructor：ChenweldsSoutheastuniversityAbstractJobSchedu1ingprob1emisthecoexistenceinmodernmanufacturingissues.Withthedeve1opmentofthemanufacturingsector,ther-

5、ehasbeenalargenumberofc0mp1exmanufactur•1ngsysteims,suehasF1exib1eMa:nufactur•1ngSystems,Com1puterIntegratedManufacturingSystem.Forj0b-shopscjhedu1ingprob1emsincreasingdifficu1tyandthenewrequirements,■1tisanurgentneedtostudyandcorreSPondtotheshopschedu1ing,Inrecentyears,an

6、tco1onya1g0rithmasanewresearchmethodSt0studyJsp,andhaveachievedgoodresu1ts.Buttetica1sfarmahm(GA),hm,heantcolonya1gorithmoftheorstudyandpracticalapplicationturityfromthegeneticalgoFitsimulatedannealing(SA)algoritthereareexploration.s1ferithriantco1on?athmmechanitheAntarchr

7、hmso1verifhmforgenmanyTh1gosm,etiofresspaperfirstithmandetrob1ems.Thenneedsearchanddiscusseticalgorcho1arsogorithmralgoeminalgoionpcantarchtionsgenes1hedomesticcompositeaanduseantestandardTSPtheantcIts,vetheicationofo1onyprob1o1colonyalgorithm,resu1ts0nthessedJaphyaAntCoco

8、mbinatorialoptimisolvetheJSPbybandthemainrare：therestrictiveJob.shopmodeloftheobSchedulin