Ant algorithms for a time and space constrained assembly line balancing problem

The present article focuses on the application of a procedure based on ant colonies to solve an assembly line balancing problem. After an introduction to assembly line problems, the problem under study is presented: the Time and Space constrained Assembly Line Balancing Problem (TSALBP); and a basic model of one of its variants is put forward for study. Subsequently, an ant algorithm is presented that incorporates some ideas that have offered good results with simple balancing problems. Finally, the validity of the proposed algorithms is tested by means of a computational experience with reference instances, and the conclusions of the study are presented.     

Bees Algorithm for constrained fuzzy multi-objective two-sided assembly line balancing problem

Bees Algorithm is one of the swarm intelligence based heuristics which tries to model natural behaviour of honey bees in food foraging and used to solve optimization problems. On the other hand, Two-sided Assembly Line Balancing Problem is a generalization of simple Assembly Line Balancing Problem where different assembly tasks are carried out on the same product in parallel at both left and right sides of the line. Two-sided assembly lines are generally employed for the assembly of large-sized products such as buses and trucks. Furthermore, many real life problems contain imprecise objectives and Fuzzy Multi-objective Programming gives an opportunity to handle such situations. In this study, Two-sided Assembly Line Balancing Problem is considered more realistically by employing positional, zoning and synchronous task constraints and by utilizing fuzzy approaches so as to maximize work slackness index and line efficiency, and minimize total balance delay. For solving this problem Bees Algorithm is used as a search mechanism for obtaining good solutions and extensive computational results are presented.     

A versatile algorithm for assembly line balancing

This paper discusses a two stage graph-algorithm, which was designed to solve line balancing problems including practice relevant constraints (GALBP), such as parallel work stations and tasks, cost synergies, processing alternatives, zoning restrictions, stochastic processing times or U-shaped assembly lines. Unlike former procedures, the presented approach can be easily modified to incorporate all of the named extensions. It is not only possible to select and solve single classes of constraints, but rather any combination of them with just slight modifications.     

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.     

A two-process implicit enumeration algorithm for the simple assembly line balancing problem

We present an implicit-enumeration algorithm for the simple assembly line balancing problem, with the objective of minimizing the number of stations along the line for a fixed cycle time. The algorithm traverses two branch-and-bound trees, one assigning tasks that appear earlier in the precedence network at lower levels of the tree, the other assigning later tasks at lower levels. The two processes alternately expand nodes of their respective trees, and share information about each other's progress in the form of global bounds. Computational results are reported on several well-known problems from the literature.     

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.     

求解图着色问题的量子蚁群算法

针对经典的图着色问题,在蚁群算法的基础上结合量子计算提出一种求解图着色问题的量子蚁群算法. 将量子比特和量子逻辑门引入到蚁群算法中,较好地避免了蚁群算法搜索易陷入局部极小的缺陷,并显著加快了算法的运算速度. 通过图着色实例的大量仿真实验,表明算法对图着色问题的求解是可行的、有效的,且具有通用性.     

A station-oriented enumerative algorithm for two-sided assembly line balancing

In this paper, a station-oriented enumerative algorithm for two-sided assembly lines balancing (TALB) is proposed. First, the time transfer function is defined and combined with the precedence relation to compute the earliest and the latest start time of tasks. With the direction and cycle time constraints, a station-oriented procedure based on the start time is designed to assign tasks, starting from the left station to the rightstation of the position. Some unsuitable position assignments would be finally removed by checking the precedence constraints among the assigned tasks. The proposed algorithm is integrated with the Hoffmann heuristic to develop a system for solving TALB problems. The test is performed on the well-known benchmark set of problem instances. Experimental results demonstrate that the proposed procedure is efficient.     

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.     

A new mechanism to maintain diversity in multi-objective metaheuristics

In this article, a new mechanism to spread the solutions generated by a multi-objective evolutionary algorithm is proposed. This approach is based on the use of stripes that are applied in objective function space and is independent of the search engine adopted. Additionally, it overcomes some of the drawbacks of other previous proposals such as the ?-dominance method. In order to validate the proposed approach, it is coupled to a multi-objective particle swarm optimizer and its performance is assessed with respect to that of state-of-the-art algorithms, using standard test problems and performance measures taken from the specialized literature. The results indicate that the proposed approach is a viable diversity maintenance mechanism that can be incorporated to any multi-objective metaheuristic used for multi-objective optimization.     

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.     

An effective ant colony optimization algorithm (ACO) for multi-objective resource allocation problem (MORAP)

The multi-objective resource allocation problem (MORAP) addresses the important issue which seeks to find the expected objectives by allocating the limited amount of resource to various activates. Resources may be manpower, assets, raw material or anything else in limited supply which can be used to accomplish the goals. The goals may be objectives (i.e., minimizing costs, or maximizing efficiency) usually driven by specific future needs. In this paper, in order to obtain a set of Pareto solution efficiently, we proposed a modified version of ant colony optimization (ACO), in this algorithm we try to increase the efficiency of algorithm by increasing the learning of ants. Effectiveness and efficiency of proposed algorithm was validated by comparing the result of ACO with hybrid genetic algorithm (hGA) which was applied to MORAP later.     

A new solution algorithm for improving performance of ant colony optimization

This study proposes an improved solution algorithm using ant colony optimization (ACO) for finding global optimum for any given test functions. The procedure of the ACO algorithms simulates the decision-making processes of ant colonies as they forage for food and is similar to other artificial intelligent techniques such as Tabu search, Simulated Annealing and Genetic Algorithms. ACO algorithms can be used as a tool for optimizing continuous and discrete mathematical functions. The proposed algorithm is based on each ant searches only around the best solution of the previous iteration with β. The proposed algorithm is called as ACORSES, an abbreviation of ACO Reduced SEarch Space. β is proposed for improving ACO’s solution performance to reach global optimum fairly quickly. The ACORSES is tested on fourteen mathematical test functions taken from literature and encouraging results were obtained. The performance of ACORSES is compared with other optimization methods. The results showed that the ACORSES performs better than other optimization algorithms, available in literature in terms of minimum values of objective functions and number of iterations.     

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.     

A hybrid heuristic for a multi-objective real-life car sequencing problem with painting and assembly line constraints

We address a multi-objective version of the car sequencing problem, which consists in sequencing a given set of cars to be produced in a single day, minimizing the number of violations of assembly constraints and the number of paint color changes in the production line. We propose a set of heuristics for approximately solving this problem, based on the paradigms of the VNS and ILS metaheuristics, to which further intensification and diversification strategies have been added. Computational results on real-life test instances are reported. The work presented in this paper obtained the second prize in the ROADEF challenge 2005 sponsored by Renault.     

Tabu search algorithms for an industrial multi-product and multi-objective assembly line balancing problem,with reduction of the task dispersion

This paper presents a real-world industrial application of the multi-product and multi-objective assembly line balancing problem, for a company involved in the production of four models of a white goods product. The problem solved is a GALBP-2, with 10 workstations and multiple objectives (to maximize the production rate in order to deal with an increase of the demand forecasted, to reach an equal cycle time of all the models and an equal workload of the different workstations, and finally, to minimize the dispersion of worker tasks on each one of the different models—the common tasks of the different models at the same workstation). The paper presents an integrated approach based on four heuristics cited in the literature and: (1) an improvement procedure based on tabu search, with the objective of minimizing the cycle time; and, subsequently, (2) a second tabu search in order to increase the uniformity of the tasks performed at each workstation (the common tasks at the same workstation).     

A new exact algorithm to solve the multi-trip vehicle routing problem with time windows and limited duration

This article tackles the multi-trip vehicle routing problem with time windows and limited duration. A trip is a timed route such that a succession of trips can be assigned to one vehicle. We provide an exact two-phase algorithm to solve it. The first phase enumerates possible ordered lists of clients which match the maximum trip duration criterion. The second phase uses a Branch and Price scheme to generate and choose a best set of trips so that all customers are visited. We propose a set covering formulation as the column generation master problem, where columns (variables) represent trips. The sub-problem selects appropriate timing for trips and has a pseudo-polynomial complexity. Computational results on Solomon’s benchmarks are presented. The computational times obtained with our new algorithm are much lower than the ones recently obtained in the only two studies published on this problem to date.     

An enumeration procedure for the assembly line balancing problem based on branching by non-decreasing idle time

In this article, we present a new exact algorithm for solving the simple assembly line balancing problem given a determined cycle time (SALBP-1). The algorithm is a station-oriented bidirectional branch-and-bound procedure based on a new enumeration strategy that explores the feasible solutions tree in a non-decreasing idle time order. The procedure uses several well-known lower bounds, dominance rules and a new logical test based on the assimilation of the feasibility problem for a given cycle time and number of stations (SALBP-F) to a maximum-flow problem.     

A balancing method and genetic algorithm for disassembly line balancing

Disassembly activities take place in various recovery operations including remanufacturing, recycling and disposal. The disassembly line is the best choice for automated disassembly of returned products. It is therefore important that the disassembly line be designed and balanced so that it works as efficiently as possible. The disassembly line balancing problem seeks a sequence which: is feasible, minimizes workstations, and ensures similar idle times, as well as other end-of-life specific concerns. However finding the optimal balance is computationally intensive with exhaustive search quickly becoming prohibitively large even for relatively small products. In this paper the problem is mathematically defined and proven NP-complete. Additionally, a new formula for quantifying the level of balancing is proposed. A first-ever set of a priori instances to be used in the evaluation of any disassembly line balancing solution technique is then developed. Finally, a genetic algorithm is presented for obtaining optimal or near-optimal solutions for disassembly line balancing problems and examples are presented to illustrate implementation of the methodology.     

An application of the branch,bound, and remember algorithm to a new simple assembly line balancing dataset

The simple assembly line balancing problem (SALBP) is a well-studied NP-complete problem for which a new problem database of generated instances was published in 2013. This paper describes the application of a branch, bound, and remember (BB&R) algorithm using the cyclic best-first search strategy to this new database to produce provably exact solutions for 86% of the unsolved problems in this database. A new backtracking rule to save memory is employed to allow the BB&R algorithm to solve many of the largest problems in the database.