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.     

Optimal air-move path generation based on MMAS algorithm

Air-move paths are executed by machine tools to cut 2D patterns that must retract (or turn off) when travelling from one pattern to the next. These retractions are nonproductive and hence their travelling distances should be minimised. For instance, reducing air-move time can increase the efficiency of cloth cutting in the garment industry. In this paper, a novel algorithm is proposed to solve this problem. In several past works, this problem is formulated as an instance of the generalised travelling salesman problem. We divide this problem into two independent sub-optimal problems (pattern cutting order and entry/exit cutting point) and iteratively solve them using a max–min ant system. This strategy can greatly narrow down the search space. We also perturb the pattern cutting order to avoid dowelling at a local minimum. Experiments show that the proposed algorithm is able to obtain near-optimal solutions, with the results beating the three state-of-the-art algorithms that were used as the benchmarks.     

Tool path optimisation for flank milling ruled surface based on the distance function

This paper deals with optimised tool path generation for five-axis flank milling using signed point-to-surface distance function. The main idea is that the geometrical deviations between the design surface and the machined surface are minimised by fine tuning the cutter locations. Based on the tangency conditions in envelope theory, the analytic representation of the envelope surface of a cutter undergoing five-axis motion is first obtained. Then the geometrical deviations between the envelope surface (i.e. machined surface) and the design surface are calculated. Optimisation of the five-axis tool path is modeled as the fine tuning of the initial cutter locations under the minimum zone criterion recommended by ANSI and ISO, which requires minimisation of the maximum geometrical deviation between the design surface and the envelope surface. Using the signed point-to-surface distance function, tool path optimisation for finish milling is formulated as a constrained optimisation problem. Based on the first-order Taylor approximation of the signed distance function, two sequential approximation algorithms for the Minimax and Least Square optimisations are developed. Numerical examples, in which a conical tool is chosen as a special case of flank machining ruled surface, verify the proposed strategy.     

Model of megalopolises in the tool path optimisation for CNC plate cutting machines

We consider the issues of tool path optimisation under constraints and formulate a mathematical problem of visiting megalopolises. The megalopolises model is the result of the discretisation of the tool path problem for CNC plate cutting machines. The order of visits is subject to precedence constraints. In addition, the cost functions depend on the set of pending tasks. The quality criterion is a variety of the additive criterion. The problem is established within the dynamic programming framework, however, a heuristic is proposed and implemented to solve practical problems of large dimensionality.     

Tool path generation via the multi-criteria optimisation for flat-end milling of sculptured surfaces

A method of generating optimal tool paths for sculptured surface machining with flat-end cutters is presented in this paper. The inclination and tilt angles, as well as the feed directions of the cutter at each cutter contact point on a machining path are optimised as a whole so that the machining width of the tool path can be as large as possible, and concerns such as smooth cutter motion, gouging avoidance, scallop height and machining widths overlap are also considered when calculating a path. A multi-criteria tool path optimisation model is introduced, and it is converted into a single objective optimisation with the weighted sum method. The Differential Evolution (DE) algorithm is suitable for solving this highly non-linear problem. However, the searching process of the DE algorithm may be trapped in local minima due to large number of design variables. Therefore, an algorithm combining the DE algorithm and the sequence linear programming algorithm is developed to solve this optimisation model. The proposed method is applied to two freeform surfaces to illustrate its effectiveness.     

A lower bound for the shortest Hamiltonean path in directed graphs

Summary We present in this paper a Lagrangean relaxation of a particular formulation for the shortest Hamiltonean path problem in a directed graph. The dual problem defined gives a lower bound. This relaxation has not the integrality property. To solve the dual problem we have to find a shortest path (not constrained to be elementary) with a fixed number of arcs, and solve a classical shortest path problem with nonnegative lengths.     

A hybrid particle swarm based method for process planning optimisation

A process planning (PP) problem is defined as to determine a set of operation-methods (machine, tool, and set-up configuration) that can convert the given stock to the designed part. Essentially, the PP problem involves the simultaneous decision making of two tasks: operation-method selection and sequencing. This is a combinatorial optimisation problem and it is difficult to find the best solution in a reasonable amount of time. In this article, an optimisation approach based on particle swarm optimisation (PSO) is proposed to solve the PP problem. Due to the characteristic of discrete process planning solution space and the continuous nature of the original PSO, a novel solution representation scheme is introduced for the application of PSO in solving the PP problem. Moreover, two kinds of local search algorithms are incorporated and interweaved with PSO evolution to improve the best solution in each generation. The numerical experiments and analysis have demonstrated that the proposed algorithm is capable of gaining a good quality solution in an efficient way.     

Non-productive tool path optimisation for four-axis milling using the simulated annealing algorithm

The paper concerns the development of generic computer aided optimisation techniques for the minimisation of residence time of a multi-component pallet in a horizontal machining centre. A general methodology has been established to take a part program for a multi-faced pallet, that involves many components, typically 20–30, and tool changes, segment it to extract the position and machining conditions embedded in it, automatically re-sequence the machining operations to find the optimum total tool path, and regenerate a new part program with the optimised machining sequence. A range of case studies has been used to: validate the software, and to demonstrate its ability to minimise the total pallet residence time. The techniques developed can be used for semi-automatic part programming of the entire pallet with multi-components, and with an auto-selection multi-tool facility. The software is capable of achieving a large reduction in part programming time, as well as reducing the non-machining time. It is shown that the use of the optimisation package with a range of part programs reduces the total pallet residence time by a factor between 9.5 and 36%, and consequently has the potential to achieve considerable economic gains.     

假肢接受腔阳模数控加工刀具的运动轨迹规划

应用表面建模方法，建立了假肢接受腔的三维数学模型。针对假肢接受腔的独特外形特征，研制了加工假肢接受腔阳模的三轴联动数控机床，该机床控制系统采用开环系统，可以运行CAD／CAM软件。对加工假肢接受腔阳模的刀具进行了运动轨迹规划，推导出了切削点的计算公式。根据三维刀具半径补偿原理，确定了刀具的刀位点运动轨迹。经过临床实例加工表明：该数控机床和刀具运动轨迹规划算法完全满足实际应用要求。     

Cutter size optimisation and interference-free tool path generation for five-axis flank milling of centrifugal impellers

Strategies for cutter size optimisation and interference-free tool path generation are proposed for five-axis flank milling of centrifugal impellers. To increase the material removal rate and provide a stronger tool shank during flank milling, the cutter size is first maximised under a set of geometric constraints. The tool path is then globally optimised in accordance with the minimum zone criterion for the determined optimal cutter size. Aside from the local interference of the cutter with the design surface, the global interferences with the hub surface and the adjacent blade surface are also considered in the optimisation models. Interference is indicated by the signed distance from the sampled point on the blade surface to the tool envelope surface. This distance is calculated without constructing the envelope surface. On the basis of the differential property of the distance function, we choose a sequential linear programming method in implementing the optimisations. This approach applies to generic rotary cutters, such as cylindrical and conical tools. Simulations are conducted to obtain the optimal cutter size and generate an interference-free tool path for a practical impeller. Simultaneously, a software module that can generate tool envelope surfaces and verify geometric errors is used to validate the proposed method.     

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.     

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.     

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.     

基于Dijkstra-蚁群算法的泊车系统路径规划研究

针对智能停车库中自动导引运输车(automated guided vehicle,AGV)存取车路径规划问题,提出了一种基于Dijkstra-蚁群算法(Dijkstra-ACO)的泊车系统路径规划方法.首先利用链接可视图法建立环境模型,并在此环境模型下,采用Dijkstra算法规划出AGV的初始路径;其次,通过引入节点随机选择机制、调整信息素更新方式和限定信息素阈值策略等对基本蚁群算法进行优化改进;最后,选用改进的蚁群算法对初始路径进行优化.结果显示:Dijkstra算法和混合算法均能使AGV有效避开障碍物,然后搜索到一条从起点到终点的无碰优化路径;与Dijkstra算法相比,混合算法能有效提高路径搜索效率,缩短搜索路径长度,改善搜索路径质量,表明该算法正确、可行及有效,且具有较强的全局搜索能力和较好的收敛性能,能够满足AGV存取车路径规划的要求.     

A new approach for rebalancing of U-lines with stochastic task times using ant colony optimisation algorithm

In real world, line balancing involves existing lines in existing factories and the line typically needs to be rebalanced rather than balanced. Rebalancing of a U-line can be defined as a changeover process from its initial configuration to a new configuration for a while due to the reasons such as demand variations, changes in product design and changes in task times, etc. This study defines U-line rebalancing problem with stochastic task times and proposes a solution procedure based on ant colony optimisation. The objective of the proposed algorithm is to minimise total cost of rebalancing which is the sum of task transposition costs, workstation opening/closing costs and operating costs of workstations for a particular planning horizon. A comprehensive experiment is conducted to generate problem instances and to compare rebalancing costs of U-lines by means of several factors. A total of 6600 rebalancing solutions are obtained and several comparisons are performed.     

Using the global optimisation methods to minimise the machining path length of the free-form surfaces in three-axis milling

During the machining of free-form surfaces using three-axis numerically controlled machine (NC), several parameters are chosen arbitrary and one of the most important is the feed motion direction. The main objective of this study is to minimise the machining time of complex surfaces while respecting a scallop height criteria. The analytical expression of the machining time is not known and by hypothesis, it is assumed to be proportional to the path length crossed by the cutting tool. This path length depends on the feed direction. To have an optimal feed direction at any point, the surface is divided into zones with low variation of the steepest slope direction. The optimization problem was formulated aiming at minimizing the global path length. Furthermore, a penalty reflecting the time loss due to the movement of the tool from one zone to another one is taken into account. Several heuristics are used to resolve this problem: Clarke and Wrights, Greedy randomized adaptive search procedure, Tabu search and Nearest neighbour search. An example illustrates our work by applying the different heuristics on a test surface. After simulations, the results obtained present a significant saving of paths length of 24% compared to the machining in one zone.     

An optimisation support for the design of hybrid production lines including assembly and disassembly tasks

The optimisation problems related to the assignment of tasks to workstations in assembly and disassembly lines have been largely discussed in the literature. They are known, respectively, as Assembly Line Balancing and Disassembly Line Balancing Problems. In this study, both types of task performed on the identical product are integrated in a common hybrid production system. Therefore, the logistic process is simplified and disassembly tasks can supply easier the assembly tasks with the required components. The considered production system has the layout of two parallel lines with common workstations. The product flow is conventional in the assembly line and reverse in the disassembly line. The paper provides a new mathematical model for designing such a hybrid system and an approximate approach based on ant colony optimisation for solving large-scale instances. The solution method is tested in a case study. The obtained results are compared with the solution provided by the design of two independent lines. The analysis of the results highlights the potential benefits of the hybrid production system.     

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.     

Simulation-based optimisation of logistics distribution system for an assembly line with path constraints

The design of logistics distribution system for an assembly line with given layout is usually constrained by various factors such as the vehicles for the distribution of assembly components and the paths on the shop floor for the vehicle movement. Since design optimisation of these production systems with such constraints is hard to solve by mathematic approaches, simulation-based approach is mostly used. In this paper, simulation-based analysis and optimisation of a logistic distribution system is performed combined with a heuristic algorithm to obtain a solution that most suits the practical requirements of an assembly line. The proposed simulation-based method builds a model that satisfied various complicated real-world problems at the work site of an investigated factory. Meanwhile, a dynamic dispatching method for vehicle movement is also presented which can adjust the control strategy and decision parameters dynamically in the process of simulation and contributes significantly to form a more fruitful design scheme. Experimental results show that proposed method performs better than the analytical model-based approach and some other methods, and the dynamic vehicle dispatching method presented performs better than some existing common strategies used in literature.     

Automatic production planning of press brakes for sheet metal bending

This paper discusses the planning module of system that has been developed in a research project investigating the possibilities for automatic planning of press brakes. Only limited attention has been given to production-planning problems for bending processes in the sheet-metal industry. A well-considered production-planning module provides an important opportunity for cost saving and flow-time reduction. The module will support and may replace an experienced planner. Under certain assumptions, the planning problem can be modelled both ways as a Travelling Purchaser Problem (TPP) and as a Generalized Travelling Salesperson Problem (GTSP). A hierarchical decomposition approach is presented to solve the TPP, while the GTSP is solved using guided local search (GLS). These methods are compared based on a set of problems from a real production environment and perform well.