多构造蚁群优化求解置换流水车间调度问题

针对置换流水车间调度问题,提出了一种多构造蚁群优化求解算法。在该算法中,蚁群采用两种方式构造解,分别是基于NEH(Nawaz-Enscore-Ham,NEH)启发式算法和Rajendran启发式算法,并根据解的质量,自适应地调整两种构造方式在蚁群中所占的比例。对置换流水车间调度问题的基准问题测试表明,提出的算法是有效的。     

基于蚁群算法的车间作业调度问题研究

对基于蚁群算法的车间作业调度问题求解进行了研究,在分析了传统蚁群算法求解车间作业调度问题容易出现早熟、收敛于局部最优解以及搜索速度慢的缺陷,提出了一种改进的混合蚁群算法。该方法在信息素更新规则上利用信息素局部更新策略和全局更新策略来进行信息素的更新,并将领域搜索与蚁群算法相结合,从而求得问题的可行解。最后,基于benchmarks问题进行了实验仿真,实验结果证明该改进混合算法的有效性及可行性。     

车间作业调度问题的仿真研究

研究车间作业调度优化问题,使资源、车辆调试、交通分配等达到优化配置,因此车间作业调度问题是一个多约束条件的目标优化问题,采用多项式求解方法不能获得最优解,导致车间作业调度效率低.为了提高车间作业调度效率,提出了一种蚁群算法的车间作业调度优化算法.首先以最小加工时间作为优化目标,蚂蚁爬行路径为作业调度方案,通过蚁群中个体间互相协作和信息交流获得最优车间作业调度方案.通过车间作业调度测试案例对算法进行验证性实验,实验结果表明,蚁群算法提高了车间作业调度效率,能在最短时间找到最优调度方案,为车间作业调度优化提供了依据.     

作业车间调度转换瓶颈算法的不可行解问题

文章讨论了作业车间调度问题转换瓶颈算法的一个缺陷。转换瓶颈算法是解决作业车间调度最小makespan(完工时间)问题的很有效的启发式算法。它是基于反复的解决某些单机调度问题。然而在转换瓶颈算法中用Carlier算法解单机调度问题并不总能得到可行解,文中给出了一个反例证明了有产生不可行解的情况。另外,文章还以简洁的方法证明了转换瓶颈算法若用Schrage算法替代Carlier算法解单机调度问题不会产生不可行解。     

基于自适应蚁群算法的JSP问题仿真研究

研究车间作业调度优化问题,以实现资源优化配置。针对提高生产效率,缩短周期,降低成本,传统蚁群算法应用于JSP(车间作业调度问题)易出现停滞和陷入局部最优,以致作业调度效率低。为改善传统蚁群算法在车间作业调度的状况,提高车间作业调度效率,提出一种基于自适应蚁群(AACA)优化的车间作业调度算法模型。算法在基本蚁群算法中引入一种新的自适应机制,用于车间作业调度中。AACA在迭代初期快速搜索,可对后期精细寻优,克服了传统调度算法搜索JSP最优解时出现的收敛速度慢、精度不高的缺陷,对照实例进行仿真。仿真结果表明,采用的AACA调度算法在迭代100次以内能找到最优解或满意解,收敛速度快,精度高,优于传统的调度方法 GA、SA和SB,提高了作业调度效率,验证了AA-CA在实际生产中的有效性和实用性。     

置换流水车间调度的蚁群优化算法

提出了一种求解置换流水车间调度的蚁群优化算法。该算法的要点是结合了NEH启发式算法和蚁群优化方法。理论论证和对置换流水车间调度问题的基准测试表明了该算法的有效性。     

作业车间调度转换瓶颈算法可行性研究*

讨论了转换瓶颈( SB) 算法在解作业车间调度问题时需要解决的子问题。转换瓶颈算法是解决作业车间调度最小makespan( 完工时间) 问题的有效启发式算法。它是基于反复地解决某些单机调度问题这样的子问题。然而所解决的单机调度问题的解可能会导致算法最终得不到可行解, 即使是单机调度最优解也可能得到不可行解。为此, 给出了一个简单的反例证明了产生不可行解的情况, 并对产生不可行解的原因作了详细分析。该研究有利于对转换瓶颈技术进行更好的理解和应用。     

流水作业批调度问题优化算法研究

为解决流水作业环境作业尺寸有差异的批调度问题,建立了基于混合整数规划方法的最大时间跨度模型,分析问题的计算复杂性,给出设备数、作业数既定情况下的可行解规模.设计一种混合蚁群算法对最大时间跨度进行优化,结合算法的搜索机制和批调度启发式规则,实现了最小化最大时间跨度.利用模拟退火方法改进蚁群算法路径选择,避免算法陷入局部最优和过早收敛.实验设计随机算例,对各类不同规模的算例进行仿真实验,实验结果表明混合蚁群算法在最优解、平均运行时间和最大时间跨度等方面优于其他同类算法.     

改进的蚁群算法求解多目标车间作业调度问题

目前已经有许多解决作业车间调度问题的启发式求解方法,但这些方法多数局限于单目标,因此不能满足现实生活中多目标作业车间调度问题的应用需求。提出一种改进的蚁群算法启发式地搜索多目标车间作业调度问题的近似最优解以满足实际的应用需求。通过对转移概率以及信息素更新方式进行改进,并融合交叉策略,确保算法在加快搜索收敛速度的同时又避免陷入局部最优。仿真实验证明,改进的算法具有较好的性能,能够解决实际生活中的多目标作业车间调度问题。     

改进的蚁群算法求解多目标车间作业调度问题

目前已经有许多解决作业车间调度问题的启发式求解方法,但这些方法多数局限于单目标,因此不能满足现实生活中多目标作业车间调度问题的应用需求.提出一种改进的蚁群算法启发式地搜索多目标车间作业调度问题的近似最优解以满足实际的应用需求.通过对转移概率以及信息素更新方式进行改进,并融合交叉策略,确保算法在加快搜索收敛速度的同时又避免陷入局部最优.仿真实验证明,改进的算法具有较好的性能,能够解决实际生活中的多目标作业车间调度问题.     

求解包含复杂关联约束的JSSP 的二级嵌套混合算法

作业车间调度问题(JSSP)包含“设备分配”和“工序排序” 2 个相互耦合的子问题,目 前的研究主要集中于工序串行的小规模问题。如果工序之间还存在并行、甚至嵌套等复杂关联 约束,则可行域性状非常复杂,当规模较大时,甚至难以求得可行解。针对以上难点问题,在 分别发挥遗传算法求解“分配问题”和蚁群算法求解“排序问题”的优势基础上,提出了二级嵌套 模型及其基本思路。通过一系列改进策略,如：基于工序的整数编码策略、基于设备类型的多 节点交叉策略、设备类别区间内基因互换的变异策略、基于逆向遍历的可行路径形成策略、基 于最短加工时间的信息素播洒与更新策略等等,构造了集成遗传算法与蚁群算法于同一循环体 的二级嵌套混合算法。针对中等规模问题,分别采用遗传算法、蚁群算法、二级嵌套蚁群算法、 遗传算法与蚁群算法相结合的二级嵌套混合算法,进行了对比试验研究。结果验证了所提算法 的可靠性和优越性,为求解包含复杂关联约束的JSSP 提供了新思路和新方法。     

Fusing ant colony optimization with Lagrangian relaxation for the multiple-choice multidimensional knapsack problem

The multiple-choice multidimensional knapsack problem (MMKP) concerns a wide variety of practical problems. It is strongly constrained and NP-hard; thus searching for an efficient heuristic approach for MMKP is of great significance. In this study, we attempt to solve MMKP by fusing ant colony optimization (ACO) with Lagrangian relaxation (LR). The algorithm used here follows the algorithmic scheme of max–min ant system for its outstanding performance in solving many other combinatorial optimization problems. The Lagrangian value of the item in MMKP, obtained from LR, is used as the heuristic factor in ACO since it performs best among the six domain-based heuristic factors we define. Furthermore, a novel infeasibility index is proposed for the development of a new repair operator, which converts possibly infeasible solutions into feasible ones. The proposed algorithm was compared with four existing algorithms by applying them to three groups of instances. Computational results demonstrate that the proposed algorithm is capable of producing competitive solutions.     

基于群体分类的自适应蚁群算法

针对基本蚁群算法在求解能力方面的不足,提出一种基于群体分类的自适应蚁群算法.该算法在智能蚁群的基础上引入随机蚁群以便扩大搜索空间,不同蚁群实行各自不同的搜索前进策略和信息更新机制,并可通过调节随机蚁群与智能蚁群的比例来控制收敛速度.多个旅行商问题的仿真实验证明,相比ACS、MMAX算法,该算法的求解能力得到了改进.     

异构多核计算系统的Codelet任务调度策略

Codelet数据流计算模型在处理大规模并行计算任务时效果显著,但该模型目前缺少在异构多核环境中的任务调度策略。因此,提出了一种在异构多核环境下基于蚁群算法的Codelet任务调度策略。该调度策略将启发式算法与蚁群算法相融合,在发挥各自优势的同时克服了启发式算法不能得出最优解的缺陷以及蚁群算法初始信息匮乏的问题。实验结果表明,智能蚁群任务调度策略相比Codelet运行时系统中原生的动态调度和静态调度策略具有更高的执行效率。     

群体智能优化算法

群体智能优化算法利用群体的优势,在没有集中控制并且不提供全局模型的前提下,为寻找复杂的分布式问题的解决方案提供了基础。介绍了两种群体智能算法模型:蚁群算法模型和粒子群算法模型,研究了两种算法的原理机制、基本模型、流程实现、改进思想和方法;通过仿真把蚁群算法与其他启发式算法的计算结果作对比,验证了蚁群算法具有很强的发现较好解的能力,不容易陷入局部最优;微粒群算法保留了基于种群的、并行的全局搜索策略,采用简单的速度-位移模型操作,在实际应用中取得了较高的成功率。     

用蚁群算法求解Job-Shop问题的机器分解方法

针对生产调度中Job-Shop问题,蚁群算法在求解Job-Shop问题时有计算量大的缺点,为了提高求解效率,将机器分解方法引入蚁群算法.机器分解方法在每次迭代中蚂蚁仅在子图中构造部分解,并与上次迭代中其他机器上的顺序共同构成本次解,提高了蚁群算法求解Job-Shop问题的效率.并且在算法中提出了一种新的状态转移规则和设计了蚂蚁起点位置的方法.通过在Benchmark算例上的仿真,与原有的一类集中式求解的蚁群算法作了比较,结果显示改进后的算法取得了较好的结果,大大缩短了计算时间,说明机器分解方法的有效性.     

Nested optimization method combining complex method and ant colony optimization to solve JSSP with complex associated processes

Job Shop Scheduling Problem (JSSP) is one of classic combinatorial optimization problems and has a long research history. Modern job shop has following characteristics: increasingly complicated processes, small batch and personalized requirement, which lead to complex correlations among processes. Complex correlations of processes, involving nested correlations besides serial and parallel correlations, propose a new task for JSSP research. Decomposing JSSP into two nested sub problems of order of arranging processes and machine arrangement, this research integrates the traditional thought of complex method into the ant colony optimization (ACO) to develop a nested optimization method in order to solve the new task. This paper is divided into four parts: first, the model of JSSP with complex associated processes is constructed and the difficulties to solve which are analyzed and listed; second, the definition of “order of arranging processes” is originally proposed, based on which the mathematical model available for the complex method is developed, taking process starting time as design variables of the first level optimization. The steps of the first level optimization and the secondary nested flow chart are detailed with the demonstration of the effectiveness of the complex method’s iteration mechanism; third, based on the representation of features the order of arranging processes obtained by the first level optimization combined with the first-in first-out rule owns, the corresponding modified ACO algorithm, involving pheromone positive perception and reverse spreading mechanism, is put forward to realize the second level optimization, which result is taken as the objective function value of the complex vertex to realize the secondary nested optimization strategy; finally, taking plentiful JSSP with complex associated processes as study cases, a serial of comparative experiments are done respectively adopting the genetic algorithm, ACO algorithm, particle swarm optimization algorithm, some combinations of heuristic algorithms respectively in the nested two levels, and the proposed nested optimization method, and experiment results attest the reliability and superiority of the proposed method.     

一种动态窗口下改进的机器人路径规划

提出了蚁群路径规划算法中一种动态候选解窗口的方法。该方法首先在固定均匀分布候选解的窗口上划分成若干分块,接着将负责路径规划的主蚁群的候选决策点看作一系列具有候选解属性的蚂蚁,再用该蚁群算法根据每分块上所有候选解上游连接边上的信息素及其启发信息以一定概率动态分布候选决策点,从而细化候选解,最终使蚁群能搜索到一条更好的路径解。仿真实验和对比的结果表明,动态候选解窗口方法比固定均匀分布候选解的方法可获得更优的性能。     

基于改进蚁群算法的机器人路径规划问题研究

针对蚁群算法收敛速度慢,容易陷入局部最优的问题,结合A*算法和蚁群算法提出了一种解决机器人路径规划问题的改进蚁群算法。自适应调整启发函数,在路径的后程借鉴启发式A*算法的估价函数,在ACS算法的启发函数中引入方向信息,提高算法的搜索效率,同时动态调整权重系数改变目标点的方向信息在蚂蚁移动过程中的影响,以平衡ACS算法解的多样性和收敛速度慢之间的关系。仿真实验表明,该算法不但可以提高收敛速度,而且在改善解的质量方面也取得了较好的效果。