A meta-heuristic algorithm for the fuzzy assembly line balancing type-E problem

Consideration is given to a single-model assembly line balancing problem with fuzzy task processing times. The problem referred to herein as f-SALBP-E consists of finding a combination of the number of workstations and the cycle time as well as a respective line balance such that the efficiency of the line is maximized. f-SALBP-E is an extension of the classical SALBP-E under fuzziness. First, a formulation of the problem is given with the tasks processing times presented by triangular fuzzy membership functions. Then, since the problem is known to be NP-hard, a meta-heuristic based on a Genetic Algorithm (GA) is developed for its solution. The performance of the proposed solution approach is studied and discussed over multiple benchmarks test problems taken from the open literature. The results demonstrate very satisfactory performance for the developed approach in terms of both solution time and quality.     

Multi-objective migrating bird optimization algorithm for cost-oriented assembly line balancing problem with collaborative robots

Neural Computing and Applications - Industries are increasingly looking for opportunities at utilizing collaborative robots in assembly lines to perform the tasks independently or assist the human...     

Discrete cuckoo search algorithms for two-sided robotic assembly line balancing problem

Neural Computing and Applications - Robotics are extensively utilized in modern industry to replace human labor and achieve high automation and flexibility. In order to produce large-size products,...     

用改进的遗传算法解决ALB问题

针对生产装配线平衡问题,提出一种改进的遗传算法.算法采用缩放适应度法、随机普遍取样的选择策略、线性可变的杂交和变异算子.使用PB语言实现了这一应用平台,给出了系统的功能结构图和主要的数据结构,并结合实例给出了ALB-2问题的解决方案.实例对比证明,改进的算法很好地解决了简单遗传算法易早熟的问题,大大改善了简单算法的性能.     

Modeling and solving constrained two-sided assembly line balancing problem via bee algorithms

Designing and operating two-sided assembly lines are crucial for manufacturing companies which assemble large-sized products such as trucks, buses and industrial refrigerators. This type of assembly line structure has several advantages over one-sided assembly lines such as shortened line length and reduced throughput time. The research area has recently focused on balancing two-sided assembly lines owing to these advantages. However, due to the complex structure of this problem, some practical constraints have been disregarded or have not been fully incorporated. In order to overcome these deficiencies, a fully constrained two-sided assembly line balancing problem is addressed in this research paper. Initially, a mathematical programming model is presented in order to describe the problem formally. Due to the problem complexity, two different swarm intelligence based search algorithms are implemented to solve large-sized instances. Bees algorithm and artificial bee colony algorithm have been applied to the fully constrained two-sided assembly line balancing problem so as to minimize the number of workstations and to obtain a balanced line. An extensive computational study has also been performed and the comparative results have been evaluated.     

Fuzzy assembly line balancing using genetic algorithms

In this paper, we implement genetic algorithms to synthesis fuzzy assembly line balancing problem which is well-known as a NP-hard problem. The genetic operators concerned with the feasibility of chromosomes will be discussed, and its performance will be shown with a numerical example.     

A new bidirectional heuristic for the assembly line balancing problem

Assembly line balancing problem (ALBP) is one of the well-known NP-hard layout planning problems for mass production systems. Many exact solution approaches have been developed, including 0–1 integer programming model, branch and bound algorithm, dynamic programming model, etc.; however, all optimal approaches are computationally inefficient in solving large-scale problems, which makes heuristic approaches a necessity in practice. In this paper we propose a new efficient heuristic, based on a recent bidirectional approach and the famous critical path method (CPM) widely used in project management, to resolve the issue of task assignment for ALBP. An example is given for illustration, and numerical results of sample problems selected from the literature are also given to show the effectiveness of the proposed heuristic.     

Solving fuzzy assembly-line balancing problem with genetic algorithms

Assembly-line balancing problem is known as one of difficult combinatorial optimization problems. This problem has been solved with linear programming, dynamic programming approaches, but unfortunately these approaches do not lead to efficient algorithms. Recently, genetic algorithm has been recognized as an efficient and usefull procedure for solving large and hard combinatorial optimization problems, such as scheduling problems, travelling salesman problems, transportation problems, and so on. Fuzzy sets theory is frequently used to represent uncertainty of information. In this paper, to treat the data of real-world problems we use a fuzzy number to represent the processing time and show that we can get a good performance in solving this problem using genetic algorithms.     

Multi-objective fuzzy assembly line balancing using genetic algorithms

This paper presents a fuzzy extension of the simple assembly line balancing problem of type 2 (SALBP-2) with fuzzy job processing times since uncertainty, variability, and imprecision are often occurred in real-world production systems. The jobs processing times are formulated by triangular fuzzy membership functions. The total fuzzy cost function is formulated as the weighted-sum of two bi-criteria fuzzy objectives: (a) Minimizing the fuzzy cycle time and the fuzzy smoothness index of the workload of the line. (b) Minimizing the fuzzy cycle time of the line and the fuzzy balance delay time of the workstations. A new multi-objective genetic algorithm is applied to solve the problem whose performance is studied and discussed over known test problems taken from the open literature.     

Solving a timetabling problem using hybrid genetic algorithms

All over the world, human resources are used on all kinds of different scheduling problems, many of which are time-consuming and tedious. Scheduling tools are thus very welcome. This paper presents a research project, where Genetic Algorithms (GAs) are used as the basis for solving a timetabling problem concerning medical doctors attached to an emergency service. All the doctors express personal preferences, thereby making the scheduling rather difficult. In its natural form, the timetabling problem for the emergency service is stated as a number of constraints to be fulfilled. For this reason, it was decided to compare the strength of a Co-evolutionary Constraint Satisfaction (CCS) technique with that of two other GA approaches. Distributed GAs and a simple special-purpose hill climber were introduced, to improve the performance of the three algorithms. Finally, the performance of the GAs was compared with that of some standard, nonGA approaches. The distributed hybrid GAs were by far the most successful, and one of these hybrid algorithms is currently used for solving the timetabling problem at the emergency service. © 1997 John Wiley & Sons, Ltd.     

Line balancing of PCB assembly line using immune algorithms

Printed Circuit Boards (PCBs) are widely used in most electronic devices. Typically, a PCB design has a set of components that needs to be assembled. In a broad sense, this assembly task involves placing PCB components at designated location on a PCB board; fixing PCB components; and testing the PCB after assembly operation to ensure that it is in proper working order. The stringent requirements of having a higher component density on PCBs, a shorter assembly time, and a more reliable product prompt manufacturers to automate the process of PCB assembly. Frequently, a few placement machines may work together to form an assembly line. Thus, the application of more than one machine for component placement on a PCB presents a line-balancing problem, which is basically concerned with balancing the workload of all the machines in an assembly line. This paper describes the application of a new artificial intelligence technique known as the immune algorithm to PCB component placement as well as the line balancing of PCB assembly line. It also includes an overview of PCB assembly and an outline of the assembly line balancing problem. Two case studies are used to validate the IA engine developed in this work. The details of IA, the IA engine and the case studies are presented.     

Multiobjective memetic algorithms for time and space assembly line balancing

This paper presents three proposals of multiobjective memetic algorithms to solve a more realistic extension of a classical industrial problem: time and space assembly line balancing. These three proposals are, respectively, based on evolutionary computation, ant colony optimisation, and greedy randomised search procedure. Different variants of these memetic algorithms have been developed and compared in order to determine the most suitable intensification–diversification trade-off for the memetic search process. Once a preliminary study on nine well-known problem instances is accomplished with a very good performance, the proposed memetic algorithms are applied considering real-world data from a Nissan plant in Barcelona (Spain). Outstanding approximations to the pseudo-optimal non-dominated solution set were achieved for this industrial case study.     

An efficient hybrid genetic algorithm to solve assembly line balancing problem with sequence-dependent setup times

In this paper the setup assembly line balancing and scheduling problem (SUALBSP) is considered. Since this problem is NP-hard, a hybrid genetic algorithm (GA) is proposed to solve the problem. This problem involves assigning the tasks to the stations and scheduling them inside each station. A simple permutation is used to determine the sequence of tasks. To determine the assignment of tasks to stations, the algorithm is hybridized using a dynamic programming procedure. Using dynamic programming, at any time a chromosome can be converted to an optimal solution (subject to the chromosome sequence).     

A comprehensive review of robotic assembly line balancing problem

Journal of Intelligent Manufacturing - The research on the robotic assembly line balancing problem (RALBP) was originated for the first time nearly three decades ago. This problem is under the...     

考虑多专业协同的装配线平衡问题研究

为改善飞机总装线平衡效果,提出考虑多专业协同分配的第一类装配线平衡方法。首先,分析各专业间的关联性,建立基于动态模糊聚类的专业划分方法,获取资源-功能的多专业集合;然后,根据飞机总装环境及所涉及专业的特点,建立了多专业协同分配的平衡模型;再根据专业划分结果及作业分配规则,提出了混合模拟退火-遗传算法(HSAGA),将专业间关联度高的作业分配到工作面(指专业关联度高的作业的集合,也指能完成一项装配任务的作业执行操作空间),实现工作面数的最小化;最后,以某型飞机总装作业为例,验证了平衡方法的有效性。     

A new hybrid improvement heuristic approach to simple straight and U-type assembly line balancing problems

This paper presents a new hybrid improvement heuristic approach to simple straight and U-type assembly line balancing problems which is based on the idea of adaptive learning approach and simulated annealing. The proposed approach uses a weight parameter to perturb task priorities of a solution to obtain improved solutions. The weight parameters are then modified using a learning strategy. The maximization of line efficiency (i.e., the minimization of the number of stations) and the equalization of workloads among stations (i.e., the minimization of the smoothness index or the minimization of the variation of workloads) are considered as the performance criteria. In order to clarify the proposed solution methodology, a well known problem taken from literature is solved. A computational study is conducted by solving a large number of benchmark problems available in the literature to compare the performance of the proposed approach to the existing methods such as simulated annealing and genetic algorithms. Some test instances taken from literature are also solved by the proposed approach. The results of the computational study show that the proposed approach performs quite effectively. It also yields optimal solutions for all test problems within a short computational time.     

A new heuristic approach to assembly line balancing

The main feature of the method suggested in this paper is the assignment of priority to elements and priority elements are preferred to non-priority elements when assigning elements to stations. It gives the minimum number of stations under a predetermined cycle time. The work element time is considered to be invariant. This method has been tested by solving nearly all the problems available in the pertinent literature. This method yields better or similar results as available in the literature. A computer program incorporating the new heuristic method is presented in the paper.     

A hybrid genetic algorithm for mixed model assembly line balancing problem with parallel workstations and zoning constraints

In this paper, we propose a hybrid genetic algorithm to solve mixed model assembly line balancing problem of type I (MMALBP-I). There are three objectives to be achieved: to minimize the number of workstations, maximize the workload smoothness between workstations, and maximize the workload smoothness within workstations. The proposed approach is able to address some particular features of the problem such as parallel workstations and zoning constraints. The genetic algorithm may lack the capability of exploring the solution space effectively. We aim to improve its exploring capability by sequentially hybridizing the three well known heuristics, Kilbridge & Wester Heuristic, Phase-I of Moodie & Young Method, and Ranked Positional Weight Technique, with genetic algorithm. The proposed hybrid genetic algorithm is tested on 20 representatives MMALBP-I and the results are compared with those of other algorithms.     

Optimisation of mixed-model assembly line balancing problem under uncertain demand

Assembly lines play a crucial role in determining the profitability of a company. Market conditions have increased the importance of mixed-model assembly lines. Variations in the demand are frequent in real industrial environments and often leads to failure of the mixed-model assembly line balancing scheme. Decision makers have to take into account this uncertainty. In an assembly line balancing problem, there is a massive amount of research in the literature assuming deterministic environment, and many other works consider uncertain task times. This research utilises the uncertainty theory to model uncertain demand and introduces complexity theory to measure the uncertainty of assembly lines. Scenario probability and triangular fuzzy number are used to describe the uncertain demand. The station complexity was measured based on information entropy and fuzzy entropy to assist in balancing systems with robust performances, considering the influence of multi-model products in the station on the assembly line. Taking minimum station complexity, minimum workload difference within station, maximum productivity as objective functions, a new optimization model for mixed-model assembly line balancing under uncertain demand was established. Then an improved genetic algorithm was applied to solve the model. Finally, the effectiveness of the model was verified by several instances of mixed-model assembly line for automobile engine.