A genetic algorithm for robotic assembly line balancing

Flexibility and automation in assembly lines can be achieved by the use of robots. The robotic assembly line balancing (RALB) problem is defined for robotic assembly line, where different robots may be assigned to the assembly tasks, and each robot needs different assembly times to perform a given task, because of its capabilities and specialization. The solution to the RALB problem includes an attempt for optimal assignment of robots to line stations and a balanced distribution of work between different stations. It aims at maximizing the production rate of the line. A genetic algorithm (GA) is used to find a solution to this problem. Two different procedures for adapting the GA to the RALB problem, by assigning robots with different capabilities to workstations are introduced: a recursive assignment procedure and a consecutive assignment procedure. The results of the GA are improved by a local optimization (hill climbing) work-piece exchange procedure. Tests conducted on a set of randomly generated problems, show that the Consecutive Assignment procedure achieves, in general, better solution quality (measured by average cycle time). Further tests are conducted to determine the best combination of parameters for the GA procedure. Comparison of the GA algorithm results with a truncated Branch and Bound algorithm for the RALB problem, demonstrates that the GA gives consistently better results.     

Metaheuristic algorithms for balancing robotic assembly lines with sequence-dependent robot setup times

Industries are incorporating robots into assembly lines due to their greater flexibility and reduced costs. Most of the reported studies did not consider scheduling of tasks or the sequence-dependent setup times in an assembly line, which cannot be neglected in a real-world scenario. This paper presents a study on robotic assembly line balancing, with the aim of minimizing cycle time by considering sequence-dependent setup times. A mathematical model for the problem is formulated and CPLEX solver is utilized to solve small-sized problems. A recently developed metaheuristic Migrating Birds Optimization (MBO) algorithm and set of metaheuristics have been implemented to solve the problem. Three different scenarios are tested (with no setup time, and low and high setup times). The comparative experimental study demonstrates that the performance of the MBO algorithm is superior for the tested datasets. The outcomes of this study can help production managers improve their production system in order to perform the assembly tasks with high levels of efficiency and quality.     

Gossip algorithms for heterogeneous multi-vehicle routing problems

In this paper we address a class of heterogeneous multi-vehicle task assignment and routing problems. We propose two distributed algorithms based on gossip communication: the first algorithm is based on a local exact optimization and the second is based on a local approximate greedy heuristic. We consider the case where a set of heterogeneous tasks arbitrarily distributed in a plane has to be serviced by a set of mobile robots, each with a given movement speed and task execution speed. Our goal is to minimize the maximum execution time of robots.     

Balancing assembly lines with tabu search

Balancing assembly lines is a crucial task for manufacturing companies in order to improve productivity and minimize production costs. Despite some progress in exact methods to solve large scale problems, softwares implementing simple heuristics are still the most commonly used tools in industry. Some metaheuristics have also been proposed and shown to improve on classical heuristics but, to our knowledge, no computational experiments have been performed on real industrial applications to clearly assess their performance as well as their flexibility. Here we present a new tabu search algorithm and discuss its differences with respect to those in the literature. We then evaluate its performance on the Type I assembly line balancing problem. Finally, we test our algorithm on a real industrial data set involving 162 tasks, 264 precedence constraints, and where the assembly is carried out on a sequential line with workstations located on both sides of the conveyor, with two possible conveyor heights and no re-positioning of the product. We discuss the flexibility of the metaheuristic and its ability to solve real industrial cases.     

Balancing and scheduling tasks in assembly lines with sequence-dependent setup times

The classical Simple Assembly Line Balancing Problem (SALBP) has been widely enriched over the past few years with many realistic approaches and much effort has been made to reduce the distance between the academic theory and the industrial reality. Despite this effort, the scheduling of the execution of tasks assigned to every workstation following the balancing of the assembly line has been scarcely reported in the scientific literature. This is supposed to be an operational concern that the worker should solve himself, but in several real environments, setups between tasks exist and optimal or near-optimal tasks schedules should be provided inside each workstation. The problem presented in this paper adds sequence-dependent setup time considerations to the classical SALBP in the following way: whenever a task is assigned next to another at the same workstation, a setup time must be added to compute the global workstation time. After formulating a mathematical model for this innovative problem and showing the high combinatorial nature of the problem, eight different heuristic rules and a GRASP algorithm are designed and tested for solving the problem in reasonable computational time.     

Balancing stochastic two-sided assembly lines: A chance-constrained,piecewise-linear,mixed integer program and a simulated annealing algorithm

Two-sided assembly lines are often designed to produce large-sized products, such as automobiles, trucks and buses. In this type of a production line, both left-side and right-side of the line are used in parallel. In all studies on two-sided assembly lines, the task times are assumed to be deterministic. However, in real life applications, especially in manual assembly lines, the tasks may have varying execution times defined as a probability distribution. The task time variation may result from machine breakdowns, loss of motivation, lack of training, non-qualified operators, complex tasks, environment, etc. In this paper, the problem of balancing two-sided assembly lines with stochastic task times (STALBP) is considered. A chance-constrained, piecewise-linear, mixed integer program (CPMIP) is proposed to model and solve the problem. As a solution approach a simulated annealing (SA) algorithm is proposed. To assess the effectiveness of CPMIP and SA algorithm, a set of test problems are solved. Finally, computational results indicating the effectiveness of CPMIP and SA algorithm are reported.     

Minimal distance calculation between the industrial robot and its workspace based on circle/polygon-slices representation

The real-time and reliable collision detection is the vital basis for the robotic motion control in real applications. In this work, the minimal distance calculation between the industrial robot and its workspace is presented. This method first uses circular/polygonal slices to represent robotic sub-structures with curved edges more accurately, and uses polygonal planes to construct its workspace. Being the basis of the distance calculation, the shortest distance between the spatial circle/polygon and the polygonal plane, as well as that between the circular/polygonal plane and the polygonal plane are first modelled through spatial relation analysis. The simulation validation indicates that the proposed algorithm is more efficient and reliable than both the point-clouds-based and bounding-volume-hierarchies-based algorithms. And the influence of the refinement size on the performance of the proposed model is revealed. Finally, the application example shows that this work is a significant contribution for the collision-free motion control of the industrial robot. The proposed algorithm can also be applied to the distance calculation of other complex objects because of the generality of the proposed slices representation way.     

Robot Manipulations: A Synergy of Visualization, Computation and Action for Spatial Instruction

This article considers the use of a learning environment, RoboCell, where manipulations of objects are performed by robot operations specified through the learner's application of mathematical and spatial reasoning. A curriculum is proposed relating to robot kinematics and point-to-point motion, rotation of objects, and robotic assembly of spatial puzzles. Various instructional methods are supported by the RoboCell robot system, such as interactive demonstrations, modeling, computer simulations and robot operations, providing diverse activities in spatial perception, mental rotation and visualization. Pre-course and post-course tests in two middle schools and a high school indicated significant student progress in the tasks related to the categories of spatial ability which were practiced in the course. This revised version was published online in July 2006 with corrections to the Cover Date.     

Parallelization Strategies for Rollout Algorithms

Rollout algorithms are innovative methods, recently proposed by Bertsekas et al. [3], for solving NP-hard combinatorial optimization problems. The main advantage of these approaches is related to their capability of magnifying the effectiveness of any given heuristic algorithm. However, one of the main limitations of rollout algorithms in solving large-scale problems is represented by their computational complexity. Innovative versions of rollout algorithms, aimed at reducing the computational complexity in sequential environments, have been proposed in our previous work [9]. In this paper, we show that a further reduction can be accomplished by using parallel technologies. Indeed, rollout algorithms have very appealing characteristics that make them suitable for efficient and effective implementations in parallel environments, thus extending their range of relevant practical applications.We propose two strategies for parallelizing rollout algorithms and we analyze their performance by considering a shared-memory paradigm. The computational experiments have been carried out on a SGI Origin 2000 with 8 processors, by considering two classical combinatorial optimization problems. The numerical results show that a good reduction of the execution time can be obtained by exploiting parallel computing systems.     

Accelerating autonomous learning by using heuristic selection of actions

This paper investigates how to make improved action selection for online policy learning in robotic scenarios using reinforcement learning (RL) algorithms. Since finding control policies using any RL algorithm can be very time consuming, we propose to combine RL algorithms with heuristic functions for selecting promising actions during the learning process. With this aim, we investigate the use of heuristics for increasing the rate of convergence of RL algorithms and contribute with a new learning algorithm, Heuristically Accelerated Q-learning (HAQL), which incorporates heuristics for action selection to the Q-Learning algorithm. Experimental results on robot navigation show that the use of even very simple heuristic functions results in significant performance enhancement of the learning rate.     

Swarm approach based on gravity for optimizing energy savings in grid systems

Execution time optimization is one of the most important objectives to accomplish for experiments launched on grid environments. However, the computing community is becoming more conscious about energy savings, seeking their optimization. In this work, both execution time and energy consumption are optimized through two swarm and multi-objective algorithms based on both physics and biology fields. On the one hand, multi-objective gravitational search algorithm (MOGSA) is inspired by the gravity forces between the planet masses. On the other hand, Multi-Objective Firefly Algorithm is based on the light attraction between the fireflies. These swarm algorithms are compared with the standard multi-objective algorithm non-dominated sorting genetic algorithm II to study their efficiency as multi-objective algorithms. Moreover, the best algorithm proposed, MOGSA, is compared with MOHEFT (a multi-objective version of one of the most-used algorithms in workflow scheduling, HEFT), and also with two real grid schedulers: Workload Management System and deadline budget constraint. Results show the superior performance of MOGSA regarding the others.     

Rank-k modification methods for recursive least squares problems

In least squares problems, it is often desired to solve the same problem repeatedly but with several rows of the data either added, deleted, or both. Methods for quickly solving a problem after adding or deleting one row of data at a time are known. In this paper we introduce fundamental rank-k updating and downdating methods and show how extensions of rank-1 downdating methods based on LINPACK, Corrected Semi-Normal Equations (CSNE), and Gram-Schmidt factorizations, as well as new rank-k downdating methods, can all be derived from these fundamental results. We then analyze the cost of each new algorithm and make comparisons tok applications of the corresponding rank-1 algorithms. We provide experimental results comparing the numerical accuracy of the various algorithms, paying particular attention to the downdating methods, due to their potential numerical difficulties for ill-conditioned problems. We then discuss the computation involved for each downdating method, measured in terms of operation counts and BLAS calls. Finally, we provide serial execution timing results for these algorithms, noting preferable points for improvement and optimization. From our experiments we conclude that the Gram-Schmidt methods perform best in terms of numerical accuracy, but may be too costly for serial execution for large problems.Research supported in part by the Joint Services Electronics Program, contract no. F49620-90-C-0039.     

一类非单调保守BFGS算法研究

基于非单调线搜索在寻求优化问题最优解中的优越性,提出了一类新的非单调保守BFGS算法.同已有方法不同,该算法中用来控制非单调性程度的算法参数不是取固定值,而是利用已有目标函数和梯度函数的信息自动调整其取值,以改善算法的数值表现.在合适的假设条件下,建立了新的非单调保守BFGS算法的全局收敛性.用基准测试优化问题测试了算...     

Optimal timing of a sequence of tasks with general completion costs

Scheduling a sequence of tasks––in the acceptation of finding the execution times––is not a trivial problem when the optimization criterion is irregular as for instance in earliness–tardiness problems. This paper presents an efficient dynamic programming algorithm to solve the problem with general cost functions depending on the end time of the tasks, idle time costs and variable durations also depending on the execution time of the tasks. The algorithm is also valid when the precedence graph is a tree and it can be adapted to determine the possible execution windows for each task not exceeding a maximum fixed cost.     

Exploiting subproblem optimization in SAT-based MaxSAT algorithms

The Maximum Satisfiability (MaxSAT) problem is an optimization variant of the Satisfiability (SAT) problem. Several combinatorial optimization problems can be translated into a MaxSAT formula. Among exact MaxSAT algorithms, SAT-based MaxSAT algorithms are the best performing approaches for real-world problems. We have extended the WPM2 algorithm by adding several improvements. In particular, we show that by solving some subproblems of the original MaxSAT instance we can dramatically increase the efficiency of WPM2. This led WPM2 to achieve the best overall results at the international MaxSAT Evaluation 2013 (MSE13) on industrial instances. Then, we present additional techniques and heuristics to further exploit the information retrieved from the resolution of the subproblems. We exhaustively analyze the impact of each improvement what contributes to our understanding of why they work. This architecture allows to convert exact algorithms into efficient incomplete algorithms. The resulting solver had the best results on industrial instances at the incomplete track of the latest international MSE.     

A case study of algorithm selection for the traveling thief problem

Many real-world problems are composed of several interacting components. In order to facilitate research on such interactions, the Traveling Thief Problem (TTP) was created in 2013 as the combination of two well-understood combinatorial optimization problems. With this article, we contribute in four ways. First, we create a comprehensive dataset that comprises the performance data of 21 TTP algorithms on the full original set of 9720 TTP instances. Second, we define 55 characteristics for all TPP instances that can be used to select the best algorithm on a per-instance basis. Third, we use these algorithms and features to construct the first algorithm portfolios for TTP, clearly outperforming the single best algorithm. Finally, we study which algorithms contribute most to this portfolio.     

A nonmonotone PSB algorithm for solving unconstrained optimization

PSB (Powell-Symmetric-Broyden) algorithm is a very important algorithm and has been extensively used in trust region methods. However, there are few studies on the line search type PSB algorithm. The primary reason is that the direction generated by this class of algorithms is not necessarily a descent direction of the objective function. In this paper, by combining a nonmonotone line search technique with the PSB method, we propose a nonmonotone PSB algorithm for solving unconstrained optimization. Under proper conditions, we establish global convergence and superlinear convergence of the proposed algorithm. At the same time we verify the efficiency of the proposed algorithm by some numerical experiments.     

An efficient grouping genetic algorithm for U-shaped assembly line balancing problems with maximizing production rate

U-type assembly line is one of the important tools that may increase companies’ production efficiency. In this study, two different modeling approaches proposed for the assembly line balancing problems have been used in modeling type-II U-line balancing problems, and the performances of these models have been compared with each other. It has been shown that using mathematical formulations to solve medium and large size problem instances is impractical since the problem is NP-hard. Therefore, a grouping genetic and simulated annealing algorithms have been developed, and a particle swarm optimization algorithm is adapted to compare with the proposed methods. A special crossover operator that always obtains feasible offspring has been suggested for the proposed grouping genetic algorithm. Furthermore, a local search procedure based on problem-specific knowledge was applied to increase the intensification of the algorithm. A set of well-known benchmark instances was solved to evaluate the effectiveness of the proposed and existing methods. Results showed that while the mathematical formulations can only be used to solve small size instances, metaheuristics can obtain high quality solutions for all size problem instances within acceptable CPU times. Moreover, grouping genetic algorithm has been found to be superior to the other methods according to the number of optimal solutions, or deviations from the lower bound values.     

On branching heuristics for the bi-objective 0/1 unidimensional knapsack problem

This paper focuses on branching strategies that are involved in branch and bound algorithms when solving multi-objective optimization problems. The choice of the branching variable at each node of the search tree constitutes indeed an important component of these algorithms. In this work we focus on multi-objective knapsack problems. In the literature, branching heuristics used for these problems are static, i.e., the order on the variables is determined prior to the execution. This study investigates the benefit of defining more sophisticated branching strategies. We first analyze and compare a representative set of classic branching heuristics and conclude that none can be identified as the best overall heuristic. Using an oracle, we highlight that combining branching heuristics within the same branch and bound algorithm leads to considerably reduced search trees but induces high computational costs. Based on learning adaptive techniques, we propose then dynamic adaptive branching strategies that are able to select the suitable heuristic to apply at each node of the search tree. Experiments are conducted on the bi-objective 0/1 unidimensional knapsack problem.     

A hybrid genetic algorithm for sequence-dependent disassembly line balancing problem

For remanufacturing or recycling companies, a reverse supply chain is of prime importance since it facilitates in recovering parts and materials from end-of-life products. In reverse supply chains, selective separation of desired parts and materials from returned products is achieved by means of disassembly which is a process of systematic separation of an assembly into its components, subassemblies or other groupings. Due to its high productivity and suitability for automation, disassembly line is the most efficient layout for product recovery operations. A disassembly line must be balanced to optimize the use of resources (viz., labor, money and time). In this paper, we consider a sequence-dependent disassembly line balancing problem (SDDLBP) with multiple objectives that requires the assignment of disassembly tasks to a set of ordered disassembly workstations while satisfying the disassembly precedence constraints and optimizing the effectiveness of several measures considering sequence dependent time increments. A hybrid algorithm that combines a genetic algorithm with a variable neighborhood search method (VNSGA) is proposed to solve the SDDLBP. The performance of VNSGA was thoroughly investigated using numerous data instances that have been gathered and adapted from the disassembly and the assembly line balancing literature. Using the data instances, the performance of VNSGA was compared with the best known metaheuristic methods reported in the literature. The tests demonstrated the superiority of the proposed method among all the methods considered.