Robotic disassembly line balancing problem: A mathematical model and ant colony optimization approach

The use of robots is significantly increasing day by day in manufacturing systems, and especially improving the efficiency of the lines. Robots can be used to complete disassembly tasks, and each of the robots can need different operation times to perform the tasks. In this paper, the balancing of the robotic disassembly line problem has been studied to develop efficient solution techniques. Firstly, a mixed-integer linear mathematical model is proposed to determine and solve the problem optimally. A case study from literature is addressed to assess and show the efficiency and effectiveness of the model to minimize cycle time. Secondly, a heuristic algorithm based on ant colony optimization is also proposed to discover a solution for especially the large-size test problems due to the complexity of the problem. The performance of the proposed heuristic algorithm is verified and compared with the different heuristic on data sets. The computational results indicate that the proposed mathematical model and the algorithms are promising for the small and large-size test problems, respectively. Finally, it should be stated that robots have great potential to use in the area of disassembly line and useful solutions provide according to test 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.     

A branch-and-bound algorithm to minimize the line length of a two-sided assembly line

A new branch-and-bound algorithm is presented to solve the two-sided assembly line balancing problem of type 1 (TALB-1). First, a pair of two directly facing station is defined as a position, and then the two-sided assembly line (TAL) is relaxed to a one-sided assembly line (OAL). Some new lower bound on positions are computed, and dominance rules and reduction rules for the one-sided assembly line balancing problem of type 1 (OALB-1) are extended and incorporated into a station-oriented assignment procedure for the TALB-1 problem. Finally, the tests are carried out on a well-known benchmark set of problem instances, and experimental results demonstrate that the proposed procedure is efficient.     

Solving a robotic assembly line balancing problem using efficient hybrid methods

In this paper we are studying a robotic assembly line balancing problem. The goal is to maximize the efficiency of the line and to balance the different tasks between the robots by defining the suitable tasks and components to assign to each robot. We are interested in a robotic line which consists of seizing the products on a moving conveyor and placing them on different location points. The performances evaluations of the system are done using a discret event simulation model. This latter has been developed with C++ language. As in our industrial application we are bounded by the execution time, we propose some resolution methods which define the suitable component and point positions in order to define the strategy of pick and place for each robot. These methods are based on the ant colony optimization, particle swarm optimization and genetic algorithms. To enhance the quality of the developed algorithms and to avoid local optima, we have coupled these algorithms with guided local search. After that, an exact method based on full enumeration is also developed to assess the quality of the developed methods. Then, we try to select the best algorithm which is able to get the best solutions with a small execution time. This is the main advantage of our methods compared to exact methods. This fact represents a great interest taking in consideration that the selected methods are used to manage the functioning of real industrial robotic assembly lines. Numerical results show that the selected algorithm performs optimally for the tested instances in a reasonable computation time and satisfies the industrial constraint.     

An imperialist competitive algorithm for multi-objective U-type assembly line design

Many assembly lines are now being designed as U-type assembly lines rather than straight lines because of the pressure of the just-in-time (JIT) manufacturing concept. Since any type of an assembly line balancing problem is known to be NP-hard, there has been a growing tendency toward using evolutionary algorithms to solve such a hard problem. This paper proposes a new population-based evolutionary algorithm, namely imperialist competitive algorithm (ICA) inspired by the process of socio-political evolution, to address the multi-objective U-type assembly line balancing problem (UALBP). Two considered objectives are to minimize the line efficiency and minimize the variation of workload. Furthermore, the Taguchi design is applied to tune the effective parameters of the proposed ICA. To demonstrate the efficiency of the proposed algorithm, the associated results are compared against an efficient genetic algorithm (GA) in the literature over a large group of benchmarks taken from the literature. The computational results show that the proposed ICA outperforms GA.     

Absalom: Balancing assembly lines with assignment restrictions

Assembly line balancing problems (ALBPs) arise whenever an assembly line is configured, redesigned or adjusted. An ALBP consists of distributing the total workload for manufacturing products among the work stations along the line. On the one hand, research has focussed on developing effective and fast solution methods for exactly solving the simple assembly line balancing problem (SALBP). On the other hand, a number of real-world extensions of SALBP have been introduced but solved with straight-forward and simple heuristics in many cases. Therefore, there is a lack of procedures for exactly solving such generalized ALBP.In this paper, we show how to extend the well-known solution procedure Salome [Scholl, A., Klein, R., 1997. Salome: A bidirectional branch-and-bound procedure for assembly line balancing. Informs J. Comput. 9 319–334], which is able to solve even large SALBP instances in a very effective manner, to a problem extension with different types of assignment restrictions (called ARALBP). The extended procedure, referred to as Absalom, employs a favorable branching scheme, an arsenal of bounding rules and a variety of logical tests using ideas from constraint programming.Computational experiments show that Absalom is a very promising exact solution approach although the additional assignment restrictions complicate the problem considerably and necessitate a relaxation of some components of Salome.     

A dynamic programming based heuristic for the assembly line balancing problem

The simple assembly line balancing problem is the simplification of a real problem associated to the assignment of the elementary tasks required for assembly of a product in an assembly line. This problem has been extensively studied in the literature for more than half a century. The present work proposes a new procedure to solve the problem we call Bounded Dynamic Programming. This use of the term Bounded is associated not only with the use of bounds to reduce the state space but also to the reduction of such space based on heuristics. This procedure is capable of obtaining an optimal solution rate of 267 out of 269 instances, which have been used in previous works, thus obtaining the best-known performance for the problem. These results are an improvement from any previous procedure found in the literature even when using smaller computing times.     

Simple heuristics for the assembly line worker assignment and balancing problem

We propose simple heuristics for the assembly line worker assignment and balancing problem. This problem typically occurs in assembly lines in sheltered work centers for the disabled. Different from the well-known simple assembly line balancing problem, the task execution times vary according to the assigned worker. We develop a constructive heuristic framework based on task and worker priority rules defining the order in which the tasks and workers should be assigned to the workstations. We present a number of such rules and compare their performance across three possible uses: as a stand-alone method, as an initial solution generator for meta-heuristics, and as a decoder for a hybrid genetic algorithm. Our results show that the heuristics are fast, they obtain good results as a stand-alone method and are efficient when used as a initial solution generator or as a solution decoder within more elaborate approaches.     

Multi-degree cyclic scheduling of a no-wait robotic cell with multiple robots

This paper addresses cyclic scheduling of a no-wait robotic cell with multiple robots. In contrast to many previous studies, we consider r-degree cyclic (r > 1) schedules, in which r identical parts with constant processing times enter and leave the cell in each cycle. We propose an algorithm to find the minimal number of robots for all feasible r-degree cycle times for a given r (r > 1). Consequently, the optimal r-degree cycle time for any given number of robots for this given r can be obtained with the algorithm. To develop the algorithm, we first show that if the entering times of r parts, relative to the start of a cycle, and the cycle time are fixed, minimizing the number of robots for the corresponding r-degree schedule can be transformed into an assignment problem. We then demonstrate that the cost matrix for the assignment problem changes only at some special values of the cycle time and the part entering times, and identify all special values for them. We solve our problem by enumerating all possible cost matrices for the assignment problem, which is subsequently accomplished by enumerating intervals for the cycle time and linear functions of the part entering times due to the identification of the special values. The algorithm developed is shown to be polynomial in the number of machines for a fixed r, but exponential if r is arbitrary.     

A Hybrid Genetic Algorithm for Assembly Line Balancing

This paper presents a hybrid genetic algorithm for the simple assembly line problem, SALBP-1. The chromosome representation of the problem is based on random keys. The assignment of the operations to the workstations is based on a heuristic priority rule in which the priorities of the operations are defined by the chromosomes. A local search is used to improve the solution. The approach is tested on a set of problems taken from the literature and compared with other approaches. The computation results validate the effectiveness of the algorithm.     

一种类微粒群算法及其在混流装配线调度问题中的应用

混流装配生产线的调度问题是准时化生产系统中最重要的问题之一.基于微粒群算法的原理,提出了一种类微粒群算法——PPSO(Pseudo Particle Swarm Optimization),可应用于解决准时化生产方式下的混流装配线调度问题.数值试验表明,采用PPSO方法比采用目标追随法、遗传算法和模拟退火算法的求解质量有很大提高.     

求解带有时间窗和提前/拖期惩罚的飞机着陆问题的遗传算法

研究了带有时间窗、飞机着陆的总提前/拖期惩罚最小为目标函数的飞机着陆问题。针对此问题设计了一种遗传算法进行求解。染色体表示为飞机着陆次序和着陆跑道两个向量,一个新的解码算法来计算飞机的着陆时间。采用数据库OR-Library中的实例进行数值实验,实验结果表明：设计的算法是有效的, 主要原因是解码算法能大大提高解的质量。该算法对于求解带有时间窗、目标函数为提前/拖期惩罚最小的调度问题具有借鉴意义。     

A genetic algorithm approach to the product line design problem using the seller's return criterion: An extensive comparative computational study

In this paper we deal with the product line design problem employing the seller's marginal return criterion. Because this problem is NP-Hard, many researchers proposed heuristic methods. We present a genetic algorithm (GA) based heuristic for solving the above problem. In the implementation, the GA is initialized in two different ways. In the first way, the GA is initialized with a random population. We call this algorithm GA1. In the second way, the solution of the beam search (BS) method is included in the first population of the GA. We call this algorithm GA2. We compare GA1, a recently developed BS method and GA2 on randomly generated problems. GA1 seems to be substantially better than the BS method in terms of CPU time. Also, the solutions found by GA1 are substantially better than those found by the BS method in comparable times. In many cases, GA2 improves the solution found by the BS method. Consequently, it is a good second step of the BS method.     

A genetic algorithm of determining cycle time for printed circuit board assembly lines

The problem of allocating components to a printed circuit board (PCB) assembly line, which has several non-identical placement machines in series, is formulated as a minimax-type integer programming (IP) model in this paper. In order to achieve the best production throughput, the objective of the model is to minimize the cycle time of the assembly line. The IP model is proven to be NP-complete (non-deterministic polynomial), so a genetic algorithm (GA) is developed for the cycle time determination problem in this paper. Finally, the efficiency of the genetic algorithm is illustrated by a numerical example.     

Learning of shared attention in sociable robotics

Sociable robots are embodied agents that are part of a heterogeneous society of robots and humans. They should be able to recognize human beings and each other, and to engage in social interactions. The use of a robotic architecture may strongly reduce the time and effort required to construct a sociable robot. Such architecture must have structures and mechanisms to allow social interaction, behavior control and learning from environment. Learning processes described on Science of Behavior Analysis may lead to the development of promising methods and structures for constructing robots able to behave socially and learn through interactions from the environment by a process of contingency learning. In this paper, we present a robotic architecture inspired from Behavior Analysis. Methods and structures of the proposed architecture, including a hybrid knowledge representation, are presented and discussed. The architecture has been evaluated in the context of a nontrivial real problem: the learning of the shared attention, employing an interactive robotic head. The learning capabilities of this architecture have been analyzed by observing the robot interacting with the human and the environment. The obtained results show that the robotic architecture is able to produce appropriate behavior and to learn from social interaction.     

Enhanced multi-Hoffmann heuristic for efficiently solving real-world assembly line balancing problems in automotive industry

In production systems of automobile manufacturers, multi-variant products are assembled on paced final assembly lines. The assignment of operations to workplaces and workers deter mines the productivity of the manufacturing process. In research, various exact and heuristic solution procedures have been developed for different versions of the so-called assembly line balancing problem.     

求解机器人制造单元调度问题的化学反应优化算法

针对多类型工件加工机器人制造单元调度NP难题,提出一种局部搜索的化学反应优化算法。该算法采用基于迭代次数的线性排序选择,维持解的多样性;构建紧后工件阻塞时间最小化交换的邻域结构加快收敛速度。此外,该算法主要参数由正交试验获得。通过求解随机产生的算例,仿真结果表明,化学反应优化算法优于遗传算法,提出算法较化学反应优化算法能更有效地搜索到更好解。     

Bicriteria sequencing methods for the mixed-model assembly line in just-in-time production systems

A mixed-model manufacturing facility operating in a pull production environment can be controlled by setting a production schedule only for the last process in the facility which is usually an assembly line of mixed-model type. In the mixed-model sequencing problems, two major goals are considered: (1) smoothing the workload on each workstation on the assembly line, and (2) keeping a constant rate of usage of all parts used on the assembly line. In this study, first, some well-known solution approaches with goal 2 are analyzed through minimizing the sum-of-deviations of actual production from the desired amount. The approaches that are found to be performing better than the others are extended for the bicriteria problem considering goals 1 and 2, simultaneously. It is also shown that the bicriteria problem with the sum-of-deviations type objective function can also be formulated as an assignment problem, and the optimal solution to the small-sized problems can thus be obtained by solving the assignment problem. Finally, the conditions when it is important to take the workload-smoothing goal into consideration are analyzed.     

An optimal procedure for the single-model deterministic assembly line balancing problem

The purpose of this paper is to develop an optimal solution method for the single-model assembly line balancing problem with deterministic work element durations. The procedure we present is a branch-and-bound algorithm which concentrates on the special structure of the problem. The method is equipped with dominance rules, bounding arguments and reliable branching heuristics. Computational results are given, indicating the method to be more than competitive to ones previously reported.     

A Hybrid Metaheuristic for the Quadratic Assignment Problem

The quadratic assignment problem (QAP) is known to be NP-hard. We propose a hybrid metaheuristic called ANGEL to solve QAP. ANGEL combines the ant colony optimization (ACO), the genetic algorithm (GA) and a local search method (LS). There are two major phases in ANGEL, namely ACO phase and GA phase. Instead of starting from a population that consists of randomly generated chromosomes, GA has an initial population constructed by ACO in order to provide a good start. Pheromone acts as a feedback mechanism from GA phase to ACO phase. When GA phase reaches the termination criterion, control is transferred back to ACO phase. Then ACO utilizes pheromone updated by GA phase to explore solution space and produces a promising population for the next run of GA phase. The local search method is applied to improve the solutions obtained by ACO and GA. We also propose a new concept called the eugenic strategy intended to guide the genetic algorithm to evolve toward a better direction. We report the results of a comprehensive testing of ANGEL in solving QAP. Over a hundred instances of QAP benchmarks were tested and the results show that ANGEL is able to obtain the optimal solution with a high success rate of 90%. This work was supported in part by the National Science Council, R.O.C., under Contract NSC 91-2213-E-005-017.