Balancing transfer lines using Benders decomposition and ant colony optimisation techniques

In this paper, we investigate a transfer line balancing problem in order to find the line configuration that minimises the non-productive time. The problem is defined at an auto manufacturing company where the cylinder head is manufactured. Technological restrictions among design features and manufacturing operations are taken into consideration. The problem is represented by an integer programming model that assigns design features and cutting tools to machining stations, and specifies the number of machines and production sequence in each station. Three algorithms are developed to efficiently solve the problem under study. The first algorithm uses Benders decomposition approach that decomposes the proposed model into an assignment problem and a sequencing problem. The second algorithm is a hybrid algorithm that mixes Benders decomposition approach with the ant colony optimisation technique. The third algorithm solves the problem using two nested ant colonies. Using 15 different problem dimensions, we compare results of the three algorithms in a computational study. The first algorithm finds optimal solutions of small problem instances only. Second and third algorithms demonstrate optimality gaps less than 4.04 and 3.8%, respectively, when compared to the optimal results given by the first algorithm. Moreover, the second and third algorithms are very promising in solving medium and large-scale problem instances.     

Optimum drilling path planning for a rectangular matrix of holes using ant colony optimisation

This paper investigates optimum path planning for CNC drilling machines for a special class of products that involve a large number of holes arranged in a rectangular matrix. Examples of such products include boiler plates, drum and trammel screens, connection flanges in steel structures, food-processing separators, as well as certain portions of printed circuit boards. While most commercial CAD software packages include modules that allow for automated generation of the CNC code, the tool path planning generated from the commercial CAD software is often not fully optimised in terms of the tool travel distance, and ultimately, the total machining time. This is mainly due to the fact that minimisation of the tool travel distance is a travelling salesman problem (TSP). The TSP is a hard problem in the discrete programming context with no known general solution that can be obtained in polynomial time. Several heuristic optimisation algorithms have been applied in the literature to the TSP, with varying levels of success. Among the most successful algorithms for TSP is the ant colony optimisation (ACO) algorithm, which mimics the behaviour of ants in nature. The research in this paper applies the ACO algorithm to the path planning of a CNC drilling tool between holes in a rectangular matrix. In order to take advantage of the rectangular layout of the holes, two modifications to the basic ACO algorithm are proposed. Simulation case studies show that the average discovered path via the modified ACO algorithms exhibit significant reduction in the total tool travel distance compared to the basic ACO algorithm or a typical genetic algorithm.     

Performance of an ant colony optimisation algorithm in dynamic job shop scheduling problems

The goal of the current study is to identify appropriate application domains of Ant Colony Optimisation (ACO) in the area of dynamic job shop scheduling problem. The algorithm is tested in a shop floor scenario with three levels of machine utilisations, three different processing time distributions, and three different performance measures for intermediate scheduling problems. The steady-state performances of ACO in terms of mean flow time, mean tardiness, total throughput on different experimental environments are compared with those from dispatching rules including first-in-first-out, shortest processing time, and minimum slack time. Two series of experiments are carried out to identify the best ACO strategy and the best performing dispatching rule. Those two approaches are thereafter compared with different variations of processing times. The experimental results show that ACO outperforms other approaches when the machine utilisation or the variation of processing times is not high.     

Open shop scheduling problem with a multi-skills resource constraint: a genetic algorithm and an ant colony optimisation approach

The continuous evolution of manufacturing environments leads to a more efficient production process that controls an increasing number of parameters. Production resources usually represent an important constraint in a manufacturing activity, specially talking about the management of human resources and their skills. In order to study the impact of this subject, this paper considers an open shop scheduling problem based on a mechanical production workshop to minimise the total flow time including a multi-skill resource constraint. Then, we count with a number of workers that have a versatility to carry out different tasks, and according to their assignment a schedule is generated. In that way, we have formulated the problem as a linear as and a non-linear mathematical model which applies the classic scheduling constraints, adding some different resources constraints related to personnel staff competences and their availability to execute one task. In addition, we introduce a genetic algorithm and an ant colony optimisation (ACO) method to solve large size problems. Finally, the best method (ACO) has been used to solve a real industrial case that is presented at the end.     

Ant colony optimisation with elitist ant for sequencing problem in a mixed model assembly line

Optimised sequencing in the Mixed Model Assembly Line (MMAL) is a major factor to effectively balance the rate at which raw materials are used for production. In this paper we present an Ant Colony Optimisation with Elitist Ant (ACOEA) algorithm on the basis of the basic Ant Colony Optimisation (ACO) algorithm. An ACOEA algorithm with the taboo search and elitist strategy is proposed to form an optimal sequence of multi-product models which can minimise deviation between the ideal material usage rate and the practical material usage rate. In this paper we compare applications of the ACOEA, ACO, and two other commonly applied algorithms (Genetic Algorithm and Goal Chasing Algorithm) to benchmark, stochastic problems and practical problems, and demonstrate that the use of the ACOEA algorithm minimised the deviation between the ideal material consumption rate and the practical material consumption rate under various critical parameters about multi-product models. We also demonstrate that the convergence rate for the ACOEA algorithm is significantly more than that for all the others considered.     

Quantum-inspired ant colony optimisation algorithm for a two-stage permutation flow shop with batch processing machines

This paper studied two-stage permutation flow shop problems with batch processing machines, considering different job sizes and arbitrary arrival times, with the optimisation objective of minimising the makespan. The quantum-inspired ant colony optimisation (QIACO) algorithm was proposed to solve the problem. In the QIACO algorithm, the ants are divided into two groups: one group selects the largest job in terms of job size as the initial job for each batch and the other group selects the smallest job as the initial job for each batch. Each group of ants has its own pheromone matrix. In the computational experiment, our novel algorithm was compared with the hybrid discrete differential evolution (HDDE) algorithm and the batch-based hybrid ant colony optimisation (BHACO) algorithm. Although the HDDE algorithm has a shorter run time, the quality of the solution for large-scale jobs is not good, while the BHACO algorithm always obtains a better solution but requires a longer run time. The computational results show that the QIACO algorithm embedded in the quantum information has advantages in terms of both solution quality and running time.     

An ant colony optimisation algorithm for scheduling in agile manufacturing

Producing customised products in a short time at low cost is one of the goals of agile manufacturing. To achieve this goal an assembly-driven differentiation strategy has been proposed in the agile manufacturing literature. In this paper, we address a manufacturing system that applies the assembly-driven differentiation strategy. The system consists of machining and assembly stages, where there is a single machine at the machining stage and multiple identical assembly stations at the assembly stage. An ant colony optimisation (ACO) algorithm is developed for solving the scheduling problem of determining the sequence of parts to be produced in the system so as to minimise the maximum completion time (or makespan). The ACO algorithm uses a new dispatching rule as the heuristic desirability and variable neighbourhood search as the local search to make it more efficient and effective. To evaluate the performance of heuristic algorithms, a branch-and-bound procedure is proposed for deriving the optimal solution to the problem. Computational results show that the proposed ACO algorithm is superior to the existing algorithm, not only improving the performance but also decreasing the computation time.     

Applying ant colony system algorithm in the navigation process for plastic injection mould manufacturing scheduling optimisation

Under the computer-aided design (CAD) software architecture, this study aims to develop navigation processes for plastic injection mould manufacturing scheduling optimisation. Mould manufacturing is a job-shop scheduling problem, with components processing sequence under limited conditions. This study uses the search capabilities of the ant colony system (ACS) to determine a set of optimal schedules, under the condition of not violating the processing sequences, in order to minimise the total processing time and realise makespan minimisation. As the test results suggest, it can save up to 52% of manufacturing time, and also substantially shorten the processing time of the production plan. This study completes the algorithm steps and manufacturing process time estimation by operations on the navigation interface, and uses mould manufacturing scheduling to make optimised arrangements of finished components. The method can comply with the on-site manufacturing processes, improve scheduling prediction accuracy and consistently and efficiently integrate the optimisation scheduling system and mould manufacturing system. Visualised information of the scheduling results can be provided, thus allowing production management personnel to ensure smooth scheduling.     

Reactive manufacturing control using the ant colony approach

As a reaction to the volatile market demands with regards to the number and variants of products offered, ever more complex procedures for manufacturing control are being developed. Most recently, self-organising procedures, which often mimic the behaviour of natural systems, have arisen. The method of ant colony optimisation (ACO), which was inspired by ants, can provide the necessary fundamentals in order to realise self-organising manufacturing control. In this context, the ifab-Institute has developed the AntControl tool for self-organising manufacturing control based on ACO. In order to investigate the potential of ACO, several concepts have been developed and integrated into the existing OSim simulation tool to create the new OSim-Ant tool. An exemplary simulation study within a manufacturing system has been carried out to evaluate the behaviour of AntControl. This paper presents this tool as well as the results of the simulation study.     

An improved ant colony optimisation algorithm for three-tier supply chain scheduling based on networked manufacturing

This paper presents a study on supply chain scheduling from the perspective of networked manufacturing (NM). According to feature analysis of supply chain scheduling based on NM, we comprehensively consider the combined benefits of cost, time, and satisfaction level for customised services. In order to derive a scheduling strategy among supply chain members based on NM, we formulate a three-tier supply chain scheduling model composed of manufacturer, collaborative design enterprise and customer. Three objective functions – time function, cost function and delay punishment function – are employed for model development. We also take into account multi-objective optimisation under the constraint of product capacity. By using an improved ant colony optimisation algorithm, we add different pheromone concentrations to selected nodes that are obtained from feasible solutions and we confine pheromone concentrations τ within the minimum value τ _min and the maximum value τ _max, thus obtaining optimal results. The results obtained by applying the proposed algorithm to a real-life example show that the presented scheduling optimisation algorithm has better convergence, efficiency, and stability than conventional ant colony optimisation. In addition, by comparing with other methods, the output results indicate that the proposed algorithm also has better solutions.     

An ant colony system-based hybrid algorithm for square root concave cost transhipment problems

Concave cost transhipment problems are difficult to optimally solve for large-scale problems within a limited period of time. Recently, some modern meta-heuristics have been employed for the development of advanced local search based or population-based stochastic search algorithms that can improve the conventional heuristics. Besides these meta-heuristics, the ant colony system algorithm is a population-based stochastic search algorithm which has been used to obtain good results in many applications. This study employs the ant colony system algorithm, coupled with some genetic algorithm and threshold accepting algorithm techniques, to develop a population based stochastic search algorithm for efficiently solving square root concave cost transhipment problems. The developed algorithms are evaluated with a number of problem instances. The results indicate that the proposed algorithm is more effective for solving square root concave cost transhipment problems than other recently designed local search based algorithms and genetic algorithm.     

A new distribution-free model for disassembly line balancing problem with stochastic task processing times

Effective conduct with End of Life (EOL) products is a hot research topic in green and smart manufacturing. For EOL product recycling and remanufacturing, a fundamental problem is to design an efficient disassembly line under consideration of stochastic task processing times. This problem focuses on selecting alternative task processes, determining the number of opened workstations, and assigning operational tasks to the workstations. The goal is to minimise the total cost consisting of workstation operational cost and hazardous component processing cost. Most existing works assume that the probability distribution of task processing times can be estimated, however, it is often not likely to access the complete probability distribution due to various difficulties. Therefore, this study investigates disassembly line design with the assumption that only the mean, standard deviation and an upper bound of task processing times are known. Our main contributions include: (i) a new decomposition color graph is proposed to intuitively describe all possible processes, (ii) a new distribution-free model is proposed, and (iii) some problem properties are established to solve the model. Experimental results show that the distribution-free model can effectively deal with stochastic task processing times without given probability distributions.     

Ant colony optimisation algorithm for distribution-allocation problem in a two-stage supply chain with a fixed transportation charge

In a fixed charge transportation problem, each route is associated with a fixed charge (or a fixed cost) and a transportation cost per unit transported. The presence of the fixed cost makes the problem difficult to solve, thereby requiring the use of heuristic methods. In this paper, an algorithm based on ant colony optimisation is proposed to solve the distribution-allocation problem in a two-stage supply chain with a fixed transportation cost for a route. A numerical study on benchmark problem instances has been carried out. The results obtained for the proposed algorithm have been compared with that for the genetic algorithm-based heuristic currently available in the literature. It is statistically confirmed that the proposed algorithm provides significantly better solutions.     

Aircraft technology portfolio optimization using ant colony optimization

Technology portfolio selection is a combinatorial optimization problem often faced with a large number of combinations and technology incompatibilities. The main research question addressed in this article is to determine if Ant Colony Optimization (ACO) is better suited than Genetic Algorithms (GAs) and Simulated Annealing (SA) for technology portfolio optimization when incompatibility constraints between technologies are present. Convergence rate, capability to find optima, and efficiency in handling of incompatibilities are the three criteria of comparison. The application problem consists of finding the best technology portfolio from 29 aircraft technologies. The results show that ACO and GAs converge faster and find optima more easily than SA, and that ACO can optimize portfolios with technology incompatibilities without using penalty functions. This latter finding paves the way for more use of ACO when the number of constraints increases, such as in the technology and concept selection for complex engineering systems.     

Multiple colony ant algorithm for job-shop scheduling problem

Ant colony optimization (ACO) is a metaheuristic that takes inspiration from the foraging behaviour of a real ant colony to solve the optimization problem. This paper presents a multiple colony ant algorithm to solve the Job-shop Scheduling Problem with the objective that minimizes the makespan. In a multiple colony ant algorithm, ants cooperate to find good solutions by exchanging information among colonies which are stored in a master pheromone matrix that serves the role of global memory. The exploration of the search space in each colony is guided by different heuristic information. Several specific features are introduced in the algorithm in order to improve the efficiency of the search. Among others is the local search method by which the ant can fine-tune their neighbourhood solutions. The proposed algorithm is tested over set of benchmark problems and the computational results demonstrate that the multiple colony ant algorithm performs well on the benchmark problems.     

改进蚁群算法设计拉式膜片弹簧

 通过对拉式膜片弹簧载荷-变形特性的综合分析,考虑各种约束条件,提出了一种新的多目标优化设计数学模型．该模型以在摩擦片磨损极限范围内,弹簧压紧力变化的平均值最小及驾驶员作用在分离轴承装置上的分离操纵力的平均值最小为共同优化目标,使离合器后备系数稳定,离合器分离力的平均作用力较小．蚁群算法是一种新型的元启发式优化算法,该算法具有较强的发现较好解的能力,但同时也存在一些缺点,如容易出现停滞现象、收敛速度慢等．将遗传算法和蚁群算法结合起来,在蚁群算法的每一次迭代中,首先根据信息量选择解分量的初值,然后使用变异操作来确定解的值．最后,通过实例与其他优化方法的结果进行比较．结果表明,该算法有较好的收敛速度及稳定性．     

Solving a time constrained two-crane routing problem for material handling with an ant colony optimisation approach: an application in the roof-tile industry

This paper presents an ant colony optimisation (ACO)-based solution approach for a real-world two-crane routing problem, where a number of different load carriers must be moved within a given cycle time by two gantry cranes in a continuous production process for roof tiles. The cranes have to transport the roof-tile batches and to return the load carriers and intermediate pads for subsequent batches. A feasible solution has to observe workflow-, space-, collision-, and machine-cycle constraints. The objective is to find a feasible schedule that minimises the working time for both cranes. The authors compare different solution approaches in terms of learning – and visibility strategies based on ACO in extensive numerical studies. A visibility concept is used to both partition and balance workload between the cranes.     

Large neighbourhood search based on mixed integer programming and ant colony optimisation for car sequencing

We investigate the problem of scheduling a sequence of cars to be placed on an assembly line. Stations, along the assembly line install options (e.g. air conditioning), but have limited capacities, and hence cars requiring the same options need to be distributed far enough apart. The desired separation is not always feasible, leading to an optimisation problem that minimises the violation of the ideal separation requirements. In order to solve the problem, we use a large neighbourhood search (LNS) based on mixed integer programming (MIP). The search is implemented as a sliding window, by selecting overlapping subsequences of manageable sizes, which can be solved efficiently. Our experiments show that, with LNS, substantial improvements in solution quality can be found.     

改进的蚁群算法及其在卫星网络路由计算中的应用

介绍了蚁群算法的原理，然后对现有蚁群算法进行了一些改进，使它能够快速地收敛以满足高速变化的卫星网络拓扑结构．采用改进的虚拟拓扑策略解决了卫星网络拓扑高速变换的问题．将改进的蚁群算法应用于其上，并给出了相应的性能评估．所提出的改进的虚拟拓扑策略，能够大大减少一个系统周期内卫星网的时间片个数．应用于此基础上的改进的蚁群算法也体现了较好的性能．