Integrated process planning and scheduling by an agent-based ant colony optimization

This paper presents an ant colony optimization (ACO) algorithm in an agent-based system to integrate process planning and shopfloor scheduling (IPPS). The search-based algorithm which aims to obtain optimal solutions by an autocatalytic process is incorporated into an established multi-agent system (MAS) platform, with advantages of flexible system architectures and responsive fault tolerance. Artificial ants are implemented as software agents. A graph-based solution method is proposed with the objective of minimizing makespan. Simulation studies have been established to evaluate the performance of the ant approach. The experimental results indicate that the ACO algorithm can effectively solve the IPPS problems and the agent-based implementation can provide a distributive computation of the algorithm.     

改进的势场蚁群算法的移动机器人路径规划

针对蚁群算法路径规划初期信息素浓度差异较小,正反馈作用不明显,路径搜索存在着盲目性、收敛速度相对较慢、易陷入局部最优等情况,人工势场算法的势场力可引导机器人快速朝目标位置前进,提出势场蚁群算法,通过栅格法对机器人的工作环境进行建模,利用人工势场中的势场力、势场力启发信息影响系数及蚁群算法中机器人与目标位置的距离构造综合启发信息,并利用蚁群算法的搜索机制在未知环境中寻找一条最优路径。大量的仿真实验表明势场蚁群算法路径规划能找到更优路径和收敛速度更快。     

Application of ant colony optimization algorithm in process planning optimization

One objective of process planning optimization is to cut down the total cost for machining process, and the ant colony optimization (ACO) algorithm is used for the optimization in this paper. Firstly, the process planning problem, considering the selection of machining resources, operations sequence optimization and the manufacturing constraints, is mapped to a weighted graph and is converted to a constraint-based traveling salesman problem. The operation sets for each manufacturing features are mapped to city groups, the costs for machining processes (including machine cost and tool cost) are converted to the weights of the cities; the costs for preparing processes (including machine changing, tool changing and set-up changing) are converted to the ‘distance’ between cities. Then, the mathematical model for process planning problem is constructed by considering the machining constraints and goal of optimization. The ACO algorithm has been employed to solve the proposed mathematical model. In order to ensure the feasibility of the process plans, the Constraint Matrix and State Matrix are used in this algorithm to show the state of the operations and the searching range of the candidate operations. Two prismatic parts are used to compare the ACO algorithm with tabu search, simulated annealing and genetic algorithm. The computing results show that the ACO algorithm performs well in process planning optimization than other three algorithms.     

整合Petri网和蚁群优化算法用于柔性制造系统调度优化研究

以Petri网与蚁群优化算法相结合，求解柔性制造系统的调度问题，取得了明显的优化效果。以一个典型算例的调度优化为例，证明了算法的有效性。     

On solving permutation scheduling problems with ant colony optimization

A new approach for solving permutation scheduling problems with ant colony optimization (ACO) is proposed in this paper. The approach assumes that no precedence constraints between the jobs have to be fulfilled. It is tested with an ACO algorithm for the single-machine total weighted deviation problem. In the new approach the ants allocate the places in the schedule not sequentially, as in the standard approach, but in random order. This leads to a better utilization of the pheromone information. It is shown by experiments that adequate combinations between the standard approach which can profit from list scheduling heuristics and the new approach perform particularly well.     

Solving software project scheduling problems with ant colony optimization

Software project scheduling problem (SPSP) is one of the important and challenging problems faced by the software project managers in the highly competitive software industry. As the problem is becoming an NP-hard problem with the increasing numbers of employees and tasks, only a few algorithms exist and the performance is still not satisfying. To design an effective algorithm for SPSP, this paper proposes an ant colony optimization (ACO) approach which is called ACS-SPSP algorithm. Since a task in software projects involves several employees, in this paper, by splitting tasks and distributing dedications of employees to task nodes we get the construction graph for ACO. Six domain-based heuristics are designed to consider the factors of task efforts, allocated dedications of employees and task importance. Among these heuristic strategies, the heuristic of allocated dedications of employees to other tasks performs well. ACS-SPSP is compared with a genetic algorithm to solve the SPSP on 30 random instances. Experimental results show that the proposed algorithm is promising and can obtain higher hit rates with more accuracy compared to the previous genetic algorithm solution.     

Mechanical assembly planning using ant colony optimization

In mechanical assembly planning research, many intelligent methods have already been reported over the past two decades. However, those methods mainly focus on the optimal assembly solution search while another important problem, the generation of solution space, has received little attention. This paper proposes a new methodology for the assembly planning problem. On the basis of a disassembly information model which has been developed to represent all theoretical assembly/disassembly sequences, two decoupled problems, generating the solution space and searching for the best result, are integrated into one computation framework. In this framework, using an ant colony optimization algorithm, the solution space of disassembly plans can be generated synchronously during the search process for best solutions. Finally, the new method’s validity is verified by a case study.     

Capacity planning with ant colony optimization for TFT-LCD array manufacturing

Array manufacturing in thin film transistor-liquid crystal display (TFT-LCD) production network is characterized as a capital-intensive and capacity-constrained production system with re-entrance and batch operations. Effectively using associated machines through optimal capacity planning and order scheduling decisions is a critical issue for array manufacturing. This study develops a capacity planning system (CPS) for TFT-LCD array manufacturing. CPS uses information including master production schedule, order due date, process routing, processing time, and number of machines. In addition, CPS derives the order release time, estimated machine start and finish time, machine allocation, and order completion time to maximize machine workload, improve lateness, and eliminate setup time. This research also develops ant colony optimization (ACO) to seek the optimal order release schedule to maximize a combination of the above objectives. The preliminary experiments are first applied to identify the optimal tuning parameters of the ACO algorithm. Computational experiments are then conducted to evaluate the significance and the robustness of the proposed algorithm compared with other competitive algorithms by full factorial experimental design.     

基于改进势场蚁群算法的机器人路径规划

提出一种全局静态环境下移动机器人路径规划的改进势场蚁群算法.该算法采用人工势场法求得的初始路径和机器人与下一个节点之间的距离综合构造启发信息,并引入启发信息递减系数,避免了传统蚁群算法由于启发信息误导所致的局部最优问题;依据零点定理, 提出初始信息素不均衡分配原则,不同的栅格位置赋予不同的初始信息素,降低蚁群搜索的盲目性,提高算法的搜索效率;设定迭代阈值,自适应调节信息素挥发系数,使得该算法具有较高的全局搜索能力,避免出现停滞现象.仿真结果验证了所提出算法的可行性和有效性.     

Beam-ACO—hybridizing ant colony optimization with beam search: an application to open shop scheduling

Ant colony optimization (ACO) is a metaheuristic approach to tackle hard combinatorial optimization problems. The basic component of ACO is a probabilistic solution construction mechanism. Due to its constructive nature, ACO can be regarded as a tree search method. Based on this observation, we hybridize the solution construction mechanism of ACO with beam search, which is a well-known tree search method. We call this approach Beam-ACO. The usefulness of Beam-ACO is demonstrated by its application to open shop scheduling (OSS). We experimentally show that Beam-ACO is a state-of-the-art method for OSS by comparing the obtained results to the best available methods on a wide range of benchmark instances.     

An ant colony optimization for single-machine tardiness scheduling with sequence-dependent setups

In many real-world production systems, it requires an explicit consideration of sequence-dependent setup times when scheduling jobs. As for the scheduling criterion, the weighted tardiness is always regarded as one of the most important criteria in practical systems. While the importance of the weighted tardiness problem with sequence-dependent setup times has been recognized, the problem has received little attention in the scheduling literature. In this paper, we present an ant colony optimization (ACO) algorithm for such a problem in a single-machine environment. The proposed ACO algorithm has several features, including introducing a new parameter for the initial pheromone trail and adjusting the timing of applying local search, among others. The proposed algorithm is experimented on the benchmark problem instances and shows its advantage over existing algorithms. As a further investigation, the algorithm is applied to the unweighted version of the problem. Experimental results show that it is very competitive with the existing best-performing algorithms.     

基于改进蚁群算法的网格资源调度研究

为进一步掌握网格资源动态运行状态,以便合理调度网格资源,提高任务执行效率,提出了一种基于改进蚁群算法的网格资源调度策略。该算法引入了一个网格资源空闲所需时间向量F,通过向量F动态调整网格资源负载情况,达到快速实现遥感资源空间检索的目的。从仿真实验结果可以看出,改进蚁群算法比蚁群算法和其他算法更优,网格资源的利用效率更高。     

基于免疫蚂蚁算法的Job-shop调度问题

描述了作业调度问题，借鉴生物免疫机理提出了求解车间调度问题的免疫蚁群算法，该方法在蚂蚁搜索程中，运用免疫机理提取疫苗，并对进化种群进行免疫操作，从而有效地抑制了蚁群算法的“早熟”和搜索效率低下的问题，显著地提高了蚁群算法对全局最优解的搜索能力和收敛速度，给出了免疫蚁群算法的具体步骤，并对算法进行了实例验证。     

Multi-satellite control resource scheduling based on ant colony optimization

The multi-satellite control resource scheduling problem (MSCRSP) is a kind of large-scale combinatorial optimization problem. As the solution space of the problem is sparse, the optimization process is very complicated. Ant colony optimization as one of heuristic method is wildly used by other researchers to solve many practical problems. An algorithm of multi-satellite control resource scheduling problem based on ant colony optimization (MSCRSP–ACO) is presented in this paper. The main idea of MSCRSP–ACO is that pheromone trail update by two stages to avoid algorithm trapping into local optima. The main procedures of this algorithm contain three processes. Firstly, the data get by satellite control center should be preprocessed according to visible arcs. Secondly, aiming to minimize the working burden as optimization objective, the optimization model of MSCRSP, called complex independent set model (CISM), is developed based on visible arcs and working periods. Ant colony algorithm can be used directly to solve CISM. Lastly, a novel ant colony algorithm, called MSCRSP–ACO, is applied to CISM. From the definition of pheromone and heuristic information to the updating strategy of pheromone is described detailed. The effect of parameters on the algorithm performance is also studied by experimental method. The experiment results demonstrate that the global exploration ability and solution quality of the MSCRSP–ACO is superior to existed algorithms such as genetic algorithm, iterative repair algorithm and max–min ant system.     

一种求解Job-Shop调度问题的新型蚁群算法

Job-Shop调度问题是一类具有很高理论研究和工程应用价值的问题。针对使用蚁群算法求解Job-Shop调度问题时较难设置合适参数的问题,提出一种动态设置参数的新型蚁群求解算法。分析了蚁群算法中参数对求解结果的影响,给出了算法求解Job-Shop调度问题的关键技术和实现过程。最后对五个基本测试问题进行了仿真实验,并与遗传算法、模拟退火算法、基本蚁群算法进行了比较。结果表明,该算法能得到较优的结果,具有一定的应用价值。     

机组检修计划优化模型及改进蚁群算法求解

根据传统发电机组检修计划优化的背景,建立了考虑经济性与技术性的新的检修计划优化模型,并根据蚁群算法收敛速度慢,易于陷入局部最优的缺点,通过模糊控制规则对蚁群算法影响信息素更新方式的两个参数进行动态变换,使其满足在蚁群搜索过程的不同状态下自适应调整,以影响收敛速度和搜索状态,并将改进算法应用到文中提出的机组检修计划优化模型,仿真验证改进算法及模型可取得良好效果.     

Data mining with an ant colony optimization algorithm

The paper proposes an algorithm for data mining called Ant-Miner (ant-colony-based data miner). The goal of Ant-Miner is to extract classification rules from data. The algorithm is inspired by both research on the behavior of real ant colonies and some data mining concepts as well as principles. We compare the performance of Ant-Miner with CN2, a well-known data mining algorithm for classification, in six public domain data sets. The results provide evidence that: 1) Ant-Miner is competitive with CN2 with respect to predictive accuracy, and 2) the rule lists discovered by Ant-Miner are considerably simpler (smaller) than those discovered by CN2     

基于启发式蚁群算法的VRP问题研究

针对蚁群算法求解VRP问题时收敛速度慢,求解质量不高的缺点,把城市和仓库间的距离矩阵和路径节约矩阵信息融入到初始信息素矩阵中作为启发式信息引入到蚁群算法中用于求解有容量限制的车辆路径规划问题（CVRP）,在三个基准数据集上的实验研究表明,基于启发式信息的蚁群算法与基本蚁群算法相比能够以较快的速度收敛到较好的解。     

Disassembly sequence planning using component-joint graph and ant colony optimization

Disassembly sequence planning is an important step of mechanical maintenance.This article presents an integrated study about the generation and optimizing algorithm of the disassembly sequence.Mechanical products are divided into two categories of components and connectors.The article uses component-joint graph to represent assembly constraints,including the incidence constraints are represented by incidence matrix and the interference constraints are represented by interference constraints.The inspiring factor and pheromone matrix are calculated according to assembly constraints.Then the ant generates its own disassembly sequences one by one and updates the inspiring factor and pheromone matrix.After all iterations,the best disassembly sequence planning of components and connectors are given.Finally,an application instance of the disassembly sequence of the jack is presented to illustrate the validity of this method.     

混合蚁群优化算法求解卫星数传调度问题

为了求解卫星数传调度问题,提出了混合蚁群优化算法。算法设计了基于任务数传操作的解构造图,提出了基于解构造图的任务调度序列和资源分配序列概率决策模型,采用基于随机加权的混合策略综合利用问题的启发式信息。算法通过基于混沌变异的列信息素向量更新策略增强解构造的多样性,通过具有补偿机制的全局信息素更新策略来保证算法的收敛性。利用STK工具设计了五个调度场景,并利用计算机生成各场景的数传任务。仿真实验结果表明,该算法是可行、有效的,收敛性和解多样性较好。