求解jobshop车间作业调度的混合算法研究

《求解jobshop车间作业调度的混合算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、摘要摘要作业车间调度问题(JobShopSchedulingProblem，JSP)是一类满足任务配置和顺序约束要求的资源分配问题，是最困难的组合优化问题之一。有效的生产调度方法和优化技术的研究和应用是实现先进制造和提高生产效益的基础和关键。求解的方法以启发式算法为主，基于优先权规则，即从未排序的工序特定子集中选用工序的规则。鉴于精确方法仅适合于小规模问题，本文以混合算法来求解Job．shop调度问题。主要工作如下：首先，通过对国内外作业车间调度问题的研究，介绍了已有的求解Job—shop调度问题的各种算法。其次，在阐述遗传算法基本概念、原理、方

2、法的基础上，针对普通遗传算法在求解Job．shop调度问题时，存在着收敛速度慢和易出现“早熟’’现象的缺点，提出算法混合思想。接下来分析了遗传算法和禁忌搜索算法及蚁群算法的优缺点，遗传算法能以较大概率找到全局最优，但局部搜索能力不强，对车间调度系统进行优化时需较长时间。禁忌搜索算法收敛较快，局部搜索能力强，但其收敛性和初值的选择有很大关系。蚁群算法的正反馈和并行搜索特点提高解的质量和稳定性，但算法时间长，且容易陷入局部最优解。本文提出了作业车间调度的混合算法。经过多次试验，发现在遗传算法完成后，直接选用遗传算法得到的最优解作为禁忌搜索的初始解进行

3、计算得到的最终解和用遗传算法所得到的最终解相差无几，但平均进化代数减少，避免了遗传算法的早熟收敛。对于混合蚁群遗传算法由于遗传算法具有快速随机的全局搜索能力，但对于系统中的反馈信息利用却无能为力，当求解到一定范围时往往做大量无为的冗余迭代，求精确解效率低，蚂蚁算法是通过信息素的累积和更新收敛于最优路径上，具有分布式并行全局搜索能力，但初期信息素匮乏，求解速度慢，算法是将遗传算法与蚂蚁算法融合，采用遗传算法生成信息素分布，利用蚂蚁算法求精确解，优势互补。最后通过对标准作业车间调度问题的测试，与传统算法进行比较，证明了本文的算法在求解Job．shop

4、调度问题方面有较好的效果。关键词：作业车间调度；遗传算法；禁忌搜索；蚁群算法AbstractJobShopSchedulingProblem(JSP)iSoneofthemostdimcultcombinatorialoptimizationproblems．whichallocatesresourcesinordertoperformanumberoftasks，suchaShaskscollocatingandordinalrestriction．Torealizemodemmanufactureandpromoteproductioneff

5、iciency，researchoneffectiveproductionschedulingmethodsandoptimizationtechniquesanditsapplicationarethefundamentalandessentialproblems．AsearlyaSinthe1950’Smuchresearchhavebeendoneandthemainsolvingmethodsareheuristicalgorithms，whichbasedonpri耐ty，that’Sarrangingoperationsfromthe

6、specialsubsetsofunorderedoperations．Astheexactmethodsareonlysuitableforsmallscaleproblemsandtheconstructivemethodsperformpoorlyandlackflexibilitiesaswell．T11iSdissertationproposesaHybridAlgorithmtosolveJSP．ThemainresearchworkiSlistedasfollows：Firstly，thedissertationreviewshis

7、toricaldevelopmentsonJSPdomesticallyandinternationally，introducesexistingmethodssolvingJSP．Secondly，basedonthedescriptionofbasicconcepts，theoryandfundamentalprocedure．thedissertationputsforwardthehybridGAwh记hcombinesTabuSearch(TS)andGAandAntColonywhenconsideringthedisadvantag

8、esofthestandardGAonJSP(e．g．pre．matureandlowconvergencespeed)．Finally