自适应蚁群算法在Job Shop调度问题中的研究.pdfVIP

2010年第9期 ·先进管理技术 · 文章编号 ：1001—2265(20t0)09—0099—05 自适应蚁群算法在 JobShop调度问题中的研究术 张家兴 一，夏筱筠 ，蒋焕军 (1．中国科学院 研究生院，北京 100049；2．中国科学院 沈阳计算技术研 究所 ，沈阳 11017I) 摘要 ：研究了JobShop调度 问题 ，分析 了蚁群算法 (ACA)与最大最小蚁群 系统 (MMAS)算法在解决 JobShop调度 问题 中的不足，提出了一种解决JobShop调度 问题的 自适应蚁群算法(SACA)。此算 法根据蚂蚁群体寻找路径的阶段性 ，使用了参数在各阶段 自适应变化的策略和关键工序块邻域有哪些信誉好的足球投注网站 策略，加快 了蚁群算法的收敛速度 ，避免 了早熟现象和陷入局部最优调度解，提高了蚁群算法的灵活 性和鲁棒性。通过仿真实验验证 了自适应蚁群算法在解决 JobShop调度 问题 中的性能优 于蚁群算 法和 MMAS算法。 关键词 ：蚁群算法；最大最小蚁群系统；自适应蚁群算法；JobShop调度 中图分类号 ：TH16；TG65 文献标识码 ：A ResearchofSelf-adaptiveAntColonyAlgorithm intheJobShopSchedulingProblem ZHANGJia—xing一，XIAXiao．jun，JIANGHuan．jun， (1．GraduateUniversityofChineseAcademyofSciences，Beijing100049，China；2．ShenyangInstituteof ComputingTechnology，ChineseAcademyofSciences，Shenyang110171，China) Abstract：ThepaperstudiedtheJobShop schedulingproblem，analyzedthedeficienciesofantcolony al· gorithm (ACA)andthemax-minantsystem (MMAS)algorithmonsolvingtheJobShopSchedulingProb- lemsandproposedself-adaptiveantcolonyalgorithm (SACA)．Accordingtothestageofnatcolonyto findthepath，thealgorithm speededuptheconvergencerateoftheantcolonyalogrithm，avoidedthepre- maturephenomenaandtofallinto localoptimalschedulnigsolution，improvedtheflexibility androbust- nessofantcolonyalgorithm，employingthestrategy oftheparameters’self-adaptivechna gesandneigh- borhoodsearchingstrateyg ofthekey processblock．Thesimulation resultsverify thattheself-adaptive antcolony algorithm onsolvingtheJobShop SchedulnigProblemsisbetterthanantcolony algorithm and M M ASalgorithm． Keywords：antcolonyalgorithm；max-minantsystem；self-adaptiveantcolonyalgorithm；jobshop scheduling 英策略的蚂蚁系统、最优最差蚂蚁系统等。以上改 O 引言 进算法虽在一定程度上克服了蚁群算法的缺点 ，但 JobSh