Job—shop调度求解广义蚁群算法,关于免费蚁群算法论文范文在这里免费下载与阅读,为您的蚁群算法相关论文写作提供资料。
蚁群算法论文参考文献：
摘 要：针对蚁群算法求解Job-shop调度问题,该算法考虑到利用析取图来描述工件加工关系给算法带来的复杂度,提出了一种广义蚁群算法.在综合考虑设备和工序关系约束的前提下,将信息素更新机制运用到求解Job-shop调度问题中,从而提高解的质量.为了提高搜索效率,根据蚁群算法的状态转移规则,对算法中参数的选择进行了详细的研究,设计了信息素更新策略.仿真实验结果表明,广义蚁群算法得到的解更接近最优解,该算法的收敛速度明显高于其他算法的收敛速度.
关键词：Job-shop调度问题；广义蚁群算法；信息素更新机制
中图分类号：TP391 文献标志码：A 文章编号：1007-2683（2017）01-0091-05
0 引言
现*造业的市场竞争日益激烈,生产调度是现*造业面临的重要问题,它的解决有利于提高企业的生产效率和经济.Job-shop调度问题（Job-shop scheduling problem,JSP）是生产调度中最基本的组合优化问题,在满足工艺路线、交货期和资源利用等约束条件下,合理安排工艺加工时间、先后顺序及使用资源,可以减小生产周期,减少库存,获得产品时间或成本的优化.因此Job-shop调度问题的优化求解具有重要的理论价值和实际意义,是学术界和工程界共同关注的热点.
目前求解Job-shop调度问题的主要方法是建立智能优化算法,以禁忌搜索、模拟退火、遗传算法为代表.蚁群算法具有正反馈、较强的鲁棒性、全局性、普遍性、优良的分布式并行计算机机制,易于和其他方法相结合等诸多优点.近年来,很多学者将蟻群算法逐渐地应用于Job-shop调度求解中.文提出了一种自适应蚁群算法（AACA）,自适应地初始化信息素并限定其大小范围以得到优解.文提出了最大最小蚁群算法,对信息素进行限制防止算法陷入局部最优.文提出了混合算法,将蚁群算法和遗传算法相结合的ACSGA算法,充分利用它们的特性.
但上述文献都是采用传统蚁群算法中析取图的方式对工件加工关系进行描述的.虽然析取图是用来描述路径关系比较好的视图形式,但是车间生产中各工件之间的加工关系不同于旅行商问题（TSP）中的路径选择.特别是对于加工规模较大的Job-shop调度问题,每增加一个机器,析取图就会增加条边,则形成的析取图结构会十分复杂,使得算法的复杂度增加,收敛速度变慢,影响解的质量.
本文提出一种广义蚁群算法,将其用于Job-shop调度求解中.该算法利用一次调度就是蚂蚁的一次爬行的思想,摆脱传统的析取图方式,把信息素更新机制应用到Job-shop调度问题中,这样能有效的简化算法复杂度,提高算法的收敛速度,优化解的质量.将信息素机制合理的应用在每一道工序上,在满足约束条件和解的合法性的前提下,越早完成加工的工序和同一工件优先进行加工的工序上残留的信息素浓度越高.
1 Job-shop调度问题分析
1.1 问题描述
n个工件在m台机器上加工,每个工件有m道工序,加工时间已知,要求总完工时间最小.针对Job-shop调度问题的具体约束条件如下：
1）同一时刻同一台机器只能加工一个工序；
2）前一道工序加工完毕后才能加工下一道工序；
3）每个工序在可用机器上的加工时间不同且已经确定；
4）允许工件在工序间等待,也允许机器在工件未到达前闲置；
5）工序一旦开始,不允许中断.
1.2 问题建模
关于Job-shop调度问题,作如下定义：1）n：工件数目；
2）m：机器数目；
3）工件集J等于{J1,J2,等,Jn},1≤i≤n；
4）机器集M等于{M1,M2,等,Mm},1≤k≤m；
5）工序集Oi等于{Oi,1,Oi,2,等,Oi,m},其中Oi,j表示工件i的第j道工序；
6）Mi,j表示Oi,j占用的机器,Mi,j∈M；
7）Ti,j表示第i个工件第j道工序的加工时间；
8）Si,j表示第i个工件第j道工序的开始时间；
9）Ci,j表示第i个工件第j道工序的完工时间,Ci,j等于Si,j+Ti,j.
因为工件完工要求所有工序加工完毕,并且每道工序开始加工时,它的紧前工序必须加工完毕,所以工件加工完毕的时间为各设备完工的最大时间值.因此在给定约束条件的前提下,调度的最短时间值是所求的结果,其数学描述为：
（1）
（2）
（3）
在上面式子中,式（1）表示目标函数,调度的整体完工时间最短.式（2）表示对于同一工件i来说,工序j+1的开始加工时间,一定会大于其紧前工序j的开始加工时间和连续加工时间之和.式（3）表示对于同一设备来说,同一设备在同一时刻只能加工一道工序.
2 Job-shop调度求解的广义蚁群算法
2.1 广义蚁群算法的总体思想
蚁群算法是一种基于反馈机制和并行机制的模拟进化算法,在大规模的调度问题中有其固有的优势,但也容易出现搜索时间过长导致局部优解.传统的蚁群算法用析取图来求解JSP问题,析取图被描述为一个有向图,更直观的展现便于分析.但对于规模大的JSP问题会加剧蚁群算法的缺陷,因需要优化的问题规模变大,那么得到相应的解就会增加迭代次数,增加了相应的计算时问,进而影响解的质量和算法的收敛速度.
结论：关于蚁群算法方面的论文题目、论文提纲、蚁群算法 matlab论文开题报告、文献综述、参考文献的相关大学硕士和本科毕业论文。
基于改进蚁群算法侦察无人机航路规划和实现
摘要：文章针对侦察无人机航路规划这一问题，分析了影响航路规划的因素，构建了航路规划的模型。结合侦察无人机航路规划的特点与模型，论证了基于蚁群算法。
自适应蚁群算法在双向生产车间调度中应用
摘要：本文将蚁群算法与双向调度算法结合，用以解决以生产周期和关键工件交货期为优化目标的车间作业调度问题。在传统的蚁群算法的基础上自适应调整挥发系。
蚁群算法和其他原理相结合在机械优化设计中应用
摘 要：通常我们在机械结构优化设计中，常借助基本蚁群算法进行优化设计，虽然能使得到的结构能够达到预期的目标与要求。但是这种基本蚁群算法通过实践发。
改进蚁群算法在全终端网络可靠性优化问题上的应用
摘要：本文着重解决全终端网络成本优化问题，以达到最佳的寻优效果和寻优速度，基于泰国学者KanyapatWatcharasitthiwat在解决网。