Robot arc welding task sequencing using genetic algorithms

This paper addresses welding task sequencing for robot arc welding process planning. Although welding task sequencing is an essential step in welding process planning, it has been considered through empirical knowledge, rather than a systematic approach. Thus, an effective task sequencing method for robot arc welding is required. Welding operations can be classified by the number of weldlines and layers. Genetic algorithms are applied to tackle those welding task sequencing problems in productivity and welding quality aspects. A genetic algorithm for the Traveling Salesman Problem (TSP) is utilized to determine welding task sequencing for a multiweldline-singlepass problem. Further, welding task sequencing for multiweldline-multipass welding is investigated and appropriate genetic algorithms are introduced. A random key genetic algorithm is presented to solve multi-robot welding task sequencing: mutliweldline with multiple robots. Finally, the genetic algorithms are implemented for the welding task sequencing of three-dimensional weld plate assemblies. Various simulation tests for a welded structure are performed to find the combination of genetic algorithm parameters suitable to weld sequencing problems and to verify the quality of genetic algorithm solutions. Robot operations for weld sequences are simulated graphically using the robot simulation software IGRIP.     

Sequencing algorithms for multiple arc-welding robots considering thermal distortion

This paper focuses on sequencing welding lines in multiple arc-welding robot systems, which is the problem of assigning individual welding operations to robots as well as determining their sequences with the objective of minimizing the maximum completion time. Each welding operation is denoted by a weld line with two end-points, each of which can be a possible starting point for the welding operation. Thermal distortion is explicitly considered by introducing a delay between welding operations associated with weld lines near each other. Due to the complexity of the problem, this paper suggests three types of search heuristics, genetic algorithms, simulated annealing and tabu search, each of which incorporates new methods to generate neighbourhood solutions. To show the performances of the heuristics, computational experiments are performed on a number of randomly generated test problems, and the results are reported. In particular, some of the search heuristics outperform the exiting method.     

Response to Al-Hakim's note

Storage location assignment and interleaving policy are two closely related problems in warehousing management. This paper addresses the location assignment and interleaving problem at the same time in an automated storage/retrieval system with duration-of-stay based shared storage policy. Based on the heuristics for single command operation, a two-step procedure is developed to solve the problem. A tabu search algorithm is proposed to improve the solution for medium and large sized problems. The computational results indicate that the tabu search algorithm is effective in finding high quality solutions, and efficient in solving large sized problems.     

Mathematical model and metaheuristics for simultaneous balancing and sequencing of a robotic mixed-model assembly line

This article presents the first method to simultaneously balance and sequence robotic mixed-model assembly lines (RMALB/S), which involves three sub-problems: task assignment, model sequencing and robot allocation. A new mixed-integer programming model is developed to minimize makespan and, using CPLEX solver, small-size problems are solved for optimality. Two metaheuristics, the restarted simulated annealing algorithm and co-evolutionary algorithm, are developed and improved to address this NP-hard problem. The restarted simulated annealing method replaces the current temperature with a new temperature to restart the search process. The co-evolutionary method uses a restart mechanism to generate a new population by modifying several vectors simultaneously. The proposed algorithms are tested on a set of benchmark problems and compared with five other high-performing metaheuristics. The proposed algorithms outperform their original editions and the benchmarked methods. The proposed algorithms are able to solve the balancing and sequencing problem of a robotic mixed-model assembly line effectively and efficiently.     

Integrated optimization of location assignment and sequencing in multi-shuttle automated storage and retrieval systems under modified 2n-command cycle pattern

This article explores the integrated optimization problem of location assignment and sequencing in multi-shuttle automated storage/retrieval systems under the modified 2n-command cycle pattern. The decision of storage and retrieval (S/R) location assignment and S/R request sequencing are jointly considered. An integer quadratic programming model is formulated to describe this integrated optimization problem. The optimal travel cycles for multi-shuttle S/R machines can be obtained to process S/R requests in the storage and retrieval request order lists by solving the model. The small-sized instances are optimally solved using CPLEX. For large-sized problems, two tabu search algorithms are proposed, in which the first come, first served and nearest neighbour are used to generate initial solutions. Various numerical experiments are conducted to examine the heuristics’ performance and the sensitivity of algorithm parameters. Furthermore, the experimental results are analysed from the viewpoint of practical application, and a parameter list for applying the proposed heuristics is recommended under different real-life scenarios.     

Efficient heuristics for robot acquisition planning for a CIM system

In this paper, a planning model and three efficient heuristics are developed for equipment acquisition planning for a CIM system using multiple-type robots. Our planning model considers selection of a proper mix of multiple-type robots such that operational requirements (i.e., time and space) from a given number of work stations are satisfied at minimal system cost. In specific, each robot is characterized by its fixed charge and subject to two capacity constraints on machine time and work space; and each work station has known demands for both machine time and work space, and is to be served by only one robot. The model is formulated as a pure 0–1 mathematical program and is shown to be harder than two-dimensional bin packing, a well-known NP-hard problem. The three heuristics developed are: a greedy heuristic, tabu thresholding, and simulated annealing. All heuristics are tested by solving 450 randomly generated problems. Computational results indicate that all three heuristics are effective and efficient in solving problems of a practical size (i.e., 50 work stations and a maximum of 20 robots). However, none of the heuristics are overwhelmingly better than the others in terms of both solution time and quality. Future research issues are also discussed.     

Integrated task sequencing and path planning for robotic remote laser welding

This paper investigates the problem of integrated task sequencing and path planning in Remote Laser Welding (RLW). It is shown that finding the appropriate order of welding tasks is crucial for exploiting the efficiency of this new joining technology, and this can be achieved only if the robot path is considered already at the time of sequencing. For modelling the problem, a novel extension of the well-know Travelling Salesman Problem with neighbourhoods and durative visits, denoted as TSP-ND, is introduced. Basic properties of this problem are formally proven, and a GRASP meta-heuristic algorithm is proposed for solving it. Extensive computational experiments demonstrate that the novel approach solves efficiently industrially relevant problems, and it achieves substantial improvement in cycle time compared to the single earlier approach in the literature dedicated to RLW, as well as compared to a decomposition approach to solving the TSP-ND model.     

A filtered-beam-search-based heuristic algorithm for flexible job-shop scheduling problem

Scheduling for the flexible job-shop is a very important issue in both fields of combinatorial optimization and production operations. However, due to combination of the routing and sequencing problems, flexible job-shop scheduling problem (FJSP) presents additional difficulty than the classical job-shop scheduling problem and requires more effective algorithms. This paper developed a filtered-beam-search-based heuristic algorithm (named as HFBS) to find sub-optimal schedules within a reasonable computational time for the FJSP with multiple objectives of minimising makespan, the total workload of machines and the workload of the most loaded machine. The proposed algorithm incorporates dispatching rules based heuristics and explores intelligently the search space to avoid useless paths, which makes it possible to improve the search speed. Through computational experiments, the performance of the presented algorithm is evaluated and compared with those of existing literature and those of commonly used dispatching rules, and the results demonstrate that the proposed algorithm is an effective and practical approach for the FJSP.     

Industrial robot layout based on operation sequence optimisation

The robot layout is one of the primary problems in the robot work cell design. An optimal layout not only makes the robotic end-effector reach the desired position with the desired orientation, but also minimises the robot cycle time for completing a given task with collision avoidance. There may be many feasible robot operation sequences for a given task. The optimisation of operation sequence for a robot placed in a fixed location is NP-complete. There may be different optimal operation sequences as the robot is placed in the different locations. Hence the problem of robot layout is quite complex. This paper presents a method of industrial robot layout based on operation sequence optimisation. The robot motion control model with velocity, acceleration and jerk is established. The feasible space of robot base is calculated and then divided into discrete grids before the optimisations. Then the ant colony algorithm is applied to optimise the operation sequence for each grid. The adjacent grids are merged or divided enough times to form the bigger grids. The pattern search algorithm is adopted to solve the local optimal position and orientation of the robot base in each big grid, and the global optimal layout is found through the comparison of the local solutions. The industrial robot layout method has been applied to the work cell design for car door welding.     

A General Algorithm of Rotating/tilting Positioner InverseKinematics for Robotic Arc Welding Off-line Programming

Off-line programming provides an essential link between CAD and CAM, whose development should result in greater use of robotic arc welding. An arc welding system with a robot and a rotating/tilting positioner is a major application area, where manual programming is a very tedious job. Off-line programming is a constructive way to solve the problem. The inverse kinematics algorithm of robot and positioner is the foundation of the off-line programming system. Although previously there were some researchers who studied the positioner inverse kinematics algorithm, they only focused on a special solution of the positioner inverse kinematics, which is the solution at down-hand welding position. However, in welding production, welding position other than down-hand position is also needed. A method for representing welding position was introduced. Then a general algorithm of rotating/tilting positioner inverse kinematics is presented.     

Nonlinear predictive control of a mobile robot: a solution using metaheuristcs

The basic features of model-based predictive control (MBPC) make it an interesting candidate for the control of mobile robots. However, fast solution procedures remain a challenge for nonlinear MBPC problems such as the one arising in mobile robot control. Metaheuristics are general purpose heuristics which have been successful in solving difficult optimization problems in a reasonable computation time. In this work, we present a comparison between the uses of three different heuristics, namely particle swarm optimization (PSO), ant colony optimization, and gravitational search algorithm for the solution of the nonlinear MBPC for a mobile robot tracking trajectory with dynamic obstacle avoidance. The computation times obtained show that PSO is a feasible alternative for real-time applications. The MBPC based on the PSO is applied to controlling a LEGO mobile robot with encouraged results.     

焊接机器人系统通信的实现

针对自行开发的弧焊机器人系统 ,包括焊接机械臂、变位机、专用电源和传感系统 ,进行了通信系统的设计并介绍了软件和硬件的实现     

激光单目视觉焊缝起始点导引技术

针对弧焊机器人自动化焊接过程中初始焊接位置定位问题,本文提出了一种十字激光单目视觉的两步导引法.首先,找到成像平面上焊缝起始点坐标,以光轴中心为原点,光轴中心与该点的连线为z轴建立新的坐标系,通过求解新旧坐标系之间的旋转矩阵,控制机器人调整摄像机的姿态,使目标点位于摄像机光轴;然后,结合十字激光发生器,控制机器人沿摄像机z轴逐渐向焊缝起始点靠近,直至十字激光交叉点与焊缝起始点重合,即获得焊缝起始点的三维坐标,将该坐标反馈给机器人,控制焊枪运动至焊缝起始点.试验结果表明,该方法能够在保证焊接精确度的情况下实现对焊缝起始点导引.     

Mixed-model assembly line sequencing heuristics for smoothing component parts usage: A comparative analysis

This paper addresses the mixed-model sequencing problem by providing a controlled comparison of six sequencing heuristics. The sequencing heuristics are evaluated for several test problems on the basis of their ability to develop a sequence which smoothes out the rate of use of each component part as much as possible. The test problems were designed to determine whether problem size, product range, product structure, or product mix affects the relative ranking of the performance of the heuristics.     

JIT mixed-model sequencing with batching and setup considerations via search heuristics

This research addresses the problem of sequencing items for production when it is desired that the production sequences result in minimal usage rates–surrogate measures for flexibility in a JIT environment. While seeking sequences with minimal usage rates, the number of required setups for the sequences is also considered, along with feasible batch-sizing combinations. The general intent is to find minimum usage-rate sequences for each associated number of setups and total batches. This multiple objective problem is addressed via a three-dimensional efficient frontier. Because the combinatorial nature of sequencing problems typically provides an intractable search space for problems of ‘real world’ size, the search heuristics of simulated annealing and genetic algorithms are presented and used to find solutions for several problem sets from the literature. Experimentation shows that the simulated annealing approach outperforms the genetic algorithm approach in both objective function and CPU performance.     

Robust sensing of arc length

During arc welding, the arc heats and melts the workpiece as heat flux. When the welding current is given, the distribution and the intensity of the heat flux are determined by the length of the are. The measurement and control of the are length are fundamental in robotic and automated welding operations. Length of welding arc determines the distribution of the arc energy and thus the heat input and width of the weld. This work aims at improving the measurement accuracy of arc length using the spectrum of are light at a particular wavelength during gas tungsten arc welding (GTAW) with argon shield. To this end, effects of welding parameters on spectral distributions were studied. To verify the effects of base metal and arc length, the arc column was also sampled horizontally as Layers for spectral analysis. Results show that spectral lines of argon atoms are determined by are length, independent of welding parameters other than the current. Based on these findings, a compact arc light sensor has been designed to measure the arc length with adequate accuracy. A closed-loop arc length control system has been developed with the proposed sensor     

一种弧焊机器人实时激光扫描视觉系统

研制了一种小型高精度弧焊机器人实时激光扫描视觉系统，对其各项性能进行了测试，并进行了抗电弧光干扰试验，结果表明，此系统精度高，抗干扰能力强，检测范围宽，能广泛地应秀于机器人和自动化焊接中。     

Job shop scheduling with a non-regular objective: A comparison of neighbourhood structures based on a sequencing/timing decomposition

Commercial software packages for production management are characterized by a gap between MRP logic, based on a backward scheduling approach, and finite capacity scheduling, usually based on forward scheduling. In order to partially bridge that gap, we need scheduling algorithms able to meet due dates while keeping WIP and inventory costs low. This leads us to consider job shop scheduling problems characterized by non-regular objective functions; such problems are even more difficult than classical job shop scheduling, and suitable heuristics are needed. One possibility is to consider local search strategies based on the decomposition of the overall problem into sequencing and timing sub-problems. For given job sequences, the optimal timing problem can be solved as a node potential problem on a graph. Since solving the timing problem is a relatively time-consuming task, we need to define a suitable neighbourhood structure to explore the space of job sequences; this can be done by generalizing well-known results for the minimum makespan problem. A related issue is if solving timing problems exactly is really necessary, or if an approximate solution is sufficient; hence, we also consider solving the timing problem approximately by a fast heuristic. We compare different neighbourhood structures, by embedding them within a pure local improvement strategy. Computational experiments show that the overall approach performs better than release/dispatch rules, although the performance improvement depends on the problem characteristics, and that the fast heuristic is quite competitive with the optimal timing approach. On the one hand, these results pave the way to the development of better local search algorithms (based e.g. on tabu search); on the other hand, it is worth noting that the heuristic timing approach, unlike the optimal one, can be extended to cope with the complicating features typical of practical scheduling problems.     

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.     

Search heuristics for operation sequencing in process planning

The operation-sequencing problem in process planning is considered to produce a part with the objective of minimizing the sum of machine, setup and tool change costs. In general, the problem has combinatorial characteristics and complex precedence relations, which makes the problem difficult to solve. Six local search heuristics have been developed based on simulated annealing and tabu search to obtain good solutions for practical-sized problems within a reasonable amount of computation time. Application of the algorithms is illustrated using an example part. Also, computational experiments were done on randomly generated problems and the results show that the tabu search-based algorithms are better than the simulated annealing-based algorithms on overall average. In particular, one of the tabu search algorithms suggested here gave optimal solutions for most small-sized test problems within very short computation times.