蚁群算法求解装配线平衡第一类问题

装配线平衡问题是生产管理中重要且较难解决的问题,其中第一类问题是装配线平衡问题的关键问题。本文通过对装配线平衡问题的分析与建模,提出了利用蚁群算法这种人工智能优化算法求解一般装配线平衡第一类问题的步骤和算法。采用启发式的方法构造分配方案的生成策略,并对信息素的更新采用局部更新与全局更新相结合的规则,从而使得该算法具有较好的目的性,大大提高了获得最优解的效率。通过该蚁群算法能得到装配线平衡第一类问题质量较优的解,且有速度快、鲁棒性、通用性等优势。     

A simulated annealing algorithm for multi-manned assembly line balancing problem

Assembly line balancing problems with multi-manned workstations usually occur in plants producing high volume products (e.g. automotive industry) in which the size of the product is reasonably large to utilize the multi-manned assembly line configuration. In these kinds of assembly lines, usually there are multi-manned workstations where a group of workers simultaneously performs different operations on the same individual product. However, owing to the high computational complexity, it is quite difficult to achieve an optimal solution to the balancing problem of multi-manned assembly lines with traditional optimization approaches. In this study, a simulated annealing heuristic is proposed for solving assembly line balancing problems with multi-manned workstations. The line efficiency, line length and the smoothness index are considered as the performance criteria. The proposed algorithm is illustrated with a numerical example problem, and its performance is tested on a set of test problems taken from literature. The performance of the proposed algorithm is compared to the existing approaches. Results show that the proposed algorithm performs well.     

2-ANTBAL: An ant colony optimisation algorithm for balancing two-sided assembly lines

Two-sided assembly lines are a special type of assembly lines in which workers perform assembly tasks in both sides of the line. This type of lines is of crucial importance, especially in the assembly of large-sized products, like automobiles, buses or trucks, in which some tasks must be performed at a specific side of the product. This paper presents an approach to address the two-sided mixed-model assembly line balancing problem. First, a mathematical programming model is presented to formally describe the problem. Then, an ant colony optimisation algorithm is proposed to solve the problem. In the proposed procedure two ants ‘work’ simultaneously, one at each side of the line, to build a balancing solution which verifies the precedence, zoning, capacity, side and synchronism constraints of the assembly process. The main goal is to minimise the number of workstations of the line, but additional goals are also envisaged. The proposed procedure is illustrated with a numerical example and results of a computational experience that exhibit its superior performance are presented.     

Integrating data envelopment analysis and analytic hierarchy for the facility layout design in manufacturing systems

Facility layout design (FLD) has a very important effect on the performance of a manufacturing system. The concept of FLD is usually considered as a multiobjective problem. For this reason, a layout generation and its evaluation are often challenging and time consuming due to their inherent multiple objectives in nature and their data collection process. In addition, an effective facility layout evaluation procedure necessitates the consideration of qualitative criteria, e.g., flexibility in volume and variety and quality related to the product and production, as well as quantitative criteria such as material handling cost, adjacency score, shape ratio, and material handling vehicle utilization in the decision process. This paper presents a decision-making methodology based on data envelopment analysis (DEA), which uses both quantitative and qualitative criteria, for evaluating FLD. The criteria that are to be minimized are viewed as inputs whereas the criteria to be maximized are considered as outputs. A computer-aided layout-planning tool, VisFactory, is adopted to facilitate the layout alternative design process as well as to collect quantitative data by using exact and vague data by means of fuzzy set theory. Analytic hierarchy process (AHP) is then applied to collect qualitative data related to quality and flexibility. The DEA methodology is used to solve the layout design problem by simultaneously considering both the quantitative and qualitative data. The purposed integrated procedure is applied to a real data set of a case study, which consists of 19 FLDs provided of the plastic profile production system.     

A review of the current applications of genetic algorithms in assembly line balancing

Most of the problems involving the design and plan of manufacturing systems are combinatorial and NP-hard. A well-known manufacturing optimization problem is the assembly line balancing problem (ALBP). Due to the complexity of the problem, in recent years, a growing number of researchers have employed genetic algorithms. In this article, a survey has been conducted from the recent published literature on assembly line balancing including genetic algorithms. In particular, we have summarized the main specifications of the problems studied, the genetic algorithms suggested and the objective functions used in evaluating the performance of the genetic algorithms. Moreover, future research directions have been identified and are suggested.     

An advanced multiobjective genetic algorithm design for the time and space assembly line balancing problem

Time and space assembly line balancing considers realistic multiobjective versions of the classical assembly line balancing industrial problems involving the joint optimization of conflicting criteria such as the cycle time, the number of stations, and/or the area of these stations. In addition to their multi-criteria nature, the different problems included in this field inherit the precedence constraints and the cycle time limitations from assembly line balancing problems, which altogether make them very hard to solve. Therefore, time and space assembly line balancing problems have been mainly tackled using multiobjective constructive metaheuristics. Global search algorithms in general - and multiobjective genetic algorithms in particular - have shown to be ineffective to solve them up to now because the existing approaches lack of a proper design taking into account the specific characteristics of this family of problems. The aim of this contribution is to demonstrate the latter assumption by proposing an advanced multiobjective genetic algorithm design for the 1/3 variant of the time and space assembly line balancing problem which involves the joint minimization of the number and the area of the stations given a fixed cycle time limit. This novel design takes the well known NSGA-II algorithm as a base and considers the use of a new coding scheme and sophisticated problem specific operators to properly deal with the said problematic questions. A detailed experimental study considering 10 different problem instances (including a real-world instance from the Nissan plant in Barcelona, Spain) will show the good yield of the new proposal in comparison with the state-of-the-art methods.     

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.     

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.     

Lexicographic bottleneck mixed-model assembly line balancing problem: Artificial bee colony and tabu search approaches with optimised parameters

The lexicographic bottleneck assembly line balancing problem is a recently introduced problem which aims at obtaining a smooth workload distribution among workstations. This is achieved hierarchically. The workload of the most heavily loaded workstation is minimised, followed by the workload of the second most heavily loaded workstation and so on. This study contributes to knowledge by examining the application of the lexicographic bottleneck objective on mixed-model lines, where more than one product model is produced in an inter-mixed sequence. The main characteristics of the lexicographic bottleneck mixed-model assembly line balancing problem are described with numerical examples. Another contribution of the study is the methodology used to deal with the complex structure of the problem. Two effective meta-heuristic approaches, namely artificial bee colony and tabu search, are proposed. The parameters of the proposed meta-heuristics are optimised using response surface methodology, which is a well-known design of experiments technique, as a unique contribution to the expert and intelligent systems literature. Different from the common tendency in the literature (which aims to optimise one parameter at a time), all parameters are optimised simultaneously. Therefore, it is shown how a complex production planning problem can be solved using sophisticated artificial intelligence techniques with optimised parameters. The methodology used for parameter setting can be applied to other metaheuristics for solving complex problems in practice. The performances of both algorithms are assessed using well-known test problems and it is observed that both algorithms find promising solutions. Artificial bee colony algorithm outperforms tabu search in minimising the number of workstations while tabu search shows a better performance in minimising the value of lexicographic bottleneck objective function.     

Two-sided assembly line balancing considering the relationships between tasks

Previous studies of the two-sided assembly line balancing problem assumed equal relationships between each two tasks assignable to a side of the line. In practice, however, this relationship may be related to such factors as the distance between the implementation place and the tools required for implementation. We know that the more relationships exist between the tasks assigned to each station, the more efficient will be the assembly line. In this paper, we suggest an index for calculating the value of the relationship between each two tasks, and define a performance criterion called ‘assembly line tasks consistency’ for calculating the average relationship between the tasks assigned to the stations of each solution. We propose a simulated annealing algorithm for solving the two-sided assembly line balancing problem considering the three performance criteria of number of stations, number of mated-stations, and assembly line tasks consistency. Also, the simulated annealing algorithm is modified for solving the two-sided assembly line balancing problem without considering the relationships between tasks. This modification finds five new best solutions for the number of stations performance criterion and ten new best solutions for the number of mated-stations performance criterion for benchmark instances.     

基于遗传的装配线平衡系统研究

给出了用于求解装配线平衡的遗传算法。在此基础上,分析了装配线平衡系统的功能和工作机理。并采用面向对象语言开发了装配线平衡系统。最后将此系统用于某装配线的平衡,并依据平衡结果进行仿真,证明该算法效果较好。利用该系统可以有效地解决装配线平衡问题,大大降低成本,为提高装配线的生产效率和改进装配线提供了技术依据。     

A branch-and-bound algorithm for assembly line worker assignment and balancing problems

In this paper, we studied the assembly line worker assignment and balancing problem, which is an extension of the classical assembly line balancing problem in which an optimal partition of the assembly work among the stations is sought along with the assignment of the operators to the stations. The relationship between this problem and several other well-studied problems is explored, and new lower bounds are derived. Additionally, an exact enumeration algorithm, which makes use of the lower bounds, is developed to solve the problem. The algorithm is tested by using a standard benchmark set of instances. The results show that the algorithm improves upon the best-performing methods from the literature in terms of solution quality, and verifies more optimal solutions than the other available exact methods.     

Collaborative optimization of robotic disassembly sequence planning and robotic disassembly line balancing problem using improved discrete Bees algorithm in remanufacturing✰

Remanufacturing helps to reduce manufacturing cost and environmental pollution by reusing end-of-life products. Disassembly is an inevitable process of remanufacturing and it is always finished by manual labor which is high cost and low efficiency while robotic disassembly helps to cover these shortages. Before the execution of disassembly, well-designed disassembly sequence and disassembly line balancing solution help to improve disassembly efficiency. However, most of the research used for disassembly sequence planning and disassembly line balancing problem is only applicable to manual disassembly. Also, disassembly sequence planning and disassembly line balancing problem are separately studied. In this paper, an improved discrete Bees algorithm is developed to solve the collaborative optimization of robotic disassembly sequence planning and robotic disassembly line balancing problem. Robotic workstation assignment method is used to generate robotic disassembly line solutions based on feasible disassembly solutions obtained by the space interference matrices. Optimization objectives of the collaborative optimization problem are described, and the analytic network process is used to assign suitable weights to different indicators. With the help of variable neighborhood search, an improved discrete Bees algorithm is developed to find the optimal solution. Finally, based on a gear pump and a camera, case studies are used to verify the effectiveness of the proposed method. The results under different cycle time of robotic disassembly line are analyzed. Under the best cycle time, the performance of the improved discrete Bees algorithm under different populations and iterations are analyzed and compared with the other three optimization algorithms. The results under different assessment methods and scenarios are also analyzed.     

Firing sequences backward algorithm for simple assembly line balancing problem of type 1

The objective of simple assembly line balancing problem type-1 (SALBP-1) is to minimize the number of workstations on an assembly line for a given cycle time. Since SALBP-1 is NP-hard, many iterative backtracking heuristics based on branch and bound procedure, tabu search, and genetic algorithms were developed to solve SALBP-1. In this study, a new heuristic algorithm based on Petri net approach is presented to solve the problem. The presented algorithm makes an order of firing sequence of transitions from Petri net model of precedence diagram. Task is assigned to a workstation using this order and backward procedure. The algorithm is coded in MATLAB, and its efficiency is tested on Talbot’s and Hoffmann’s benchmark datasets according to some performance measures and classifications. Computational study validates its effectiveness on the benchmark problems. Also comparison results show that the algorithm is efficiency to solve SALBP-1.     

Smart control of the assembly process with a fuzzy control system in the context of Industry 4.0

Assembly line balancing is important for the efficiency of the assembly process, however, a wide range of disruptions can break the current workload balance. Some researchers explored the task assignment plan for the assembly line balancing problem with the assumption that the assembly process is smooth with no disruption. Other researchers considered the impacts of disruptions, but they only explored the task re-assignment solutions for the assembly line re-balancing problem with the assumption that the re-balancing decision has been made already. There is limited literature exploring on-line adjustment solutions (layout adjustment and production rate adjustment) for an assembly line in a dynamic environment. This is because real-time monitoring of an assembly process was impossible in the past, and it is difficult to incorporate uncertainty factors into the balancing process because of the randomness and non-linearity of these factors. However, Industry 4.0 breaks the information barriers between different parts of an assembly line, since smart, connected products, which are enabled by advanced information and communication technology, can intelligently interact and communicate with each other and collect, process and produce information. Smart control of an assembly line becomes possible with the large amounts of real-time production data in the era of Industry 4.0, but there is little literature considering this new context. In this study, a fuzzy control system is developed to analyze the real-time information of an assembly line, with two types of fuzzy controllers in the fuzzy system. Type 1 fuzzy controller is used to determine whether the assembly line should be re-balanced to satisfy the demand, and type 2 fuzzy controller is used to adjust the production rate of each workstation in time to eliminate blockage and starvation, and increase the utilization of machines. Compared with three assembly lines without the proposed fuzzy control system, the assembly line with the fuzzy control system performs better, in terms of blockage ratio, starvation ratio and buffer level. Additionally, with the improvement of information transparency, the performance of an assembly line will be better. The research findings shed light on the smart control of the assembly process, and provide insights into the impacts of Industry 4.0 on assembly line balancing.     

A beam search approach for solving type II robotic parallel assembly line balancing problem

In a robotic assembly line, a series of stations are arranged along a conveyor belt and a robot performs on tasks at each station. Parallel assembly lines can provide improving line balance, productivity and so on. Combining robotic and parallel assembly lines ensure increasing flexibility of system, capacity and decreasing breakdown sensitivity. Although aforementioned benefits, balancing of robotic parallel assembly lines is lacking – to the best knowledge of the authors- in the literature. Therefore, a mathematical model is proposed to define/solve the problem and also iterative beam search (IBS), best search method based on IBS (BIBS) and cutting BIBS (CBIBS) algorithms are presented to solve the large-size problem due to the complexity of the problem. The algorithm also tested on the generated benchmark problems for robotic parallel assembly line balancing problem. The superior performances of the proposed algorithms are verified by using a statistical test. The results show that the algorithms are very competitive and promising tool for further researches in the literature.     

Mixed-model assembly line balancing in the make-to-order and stochastic environment using multi-objective evolutionary algorithms

The present study introduces a multi-objective genetic algorithm (MOGA) to solve a mixed-model assembly line problem (MMALBP), considering cycle time (CT) and the number of stations simultaneously. A mixed-model assembly line is one capable of producing different types of products to respond to different market demands, while minimizing on capital costs of designing multiple assembly lines. In this research, according to the stochastic environment of production systems, a mixed-model assembly line has been put forth in a make-to-order (MTO) environment. Furthermore, a MOGA approach is presented to solve the corresponding balancing problem and the decision maker is provided with the subsequent answers to pick one based on the specific situation. Finally, a comparison is carried out between six multi-objective evolutionary algorithms (MOEA) so as to determine the best method to solve this specific problem.     

Assembly line balancing under uncertainty: Robust optimization models and exact solution method

This research deals with line balancing under uncertainty and presents two robust optimization models. Interval uncertainty for operation times was assumed. The methods proposed generate line designs that are protected against this type of disruptions. A decomposition based algorithm was developed and combined with enhancement strategies to solve optimally large scale instances. The efficiency of this algorithm was tested and the experimental results were presented. The theoretical contribution of this paper lies in the novel models proposed and the decomposition based exact algorithm developed. Moreover, it is of practical interest since the production rate of the assembly lines designed with our algorithm will be more reliable as uncertainty is incorporated. Furthermore, this is a pioneering work on robust assembly line balancing and should serve as the basis for a decision support system on this subject.     

A team-oriented design methodology for mixed model assembly systems

Team-oriented approaches are widely being used in modern real life assembly systems, as are other modern systems. In this paper, first the literature of single and mixed model assembly line balancing, which plays an important role for the design of assembly systems, is reviewed. The associated literature matrixes reveal that team-oriented approaches do not have an intensive research area. Second, a team-oriented mathematical programming model for creating assembly teams (physical stations) in mixed model assembly lines is devised. Owing to the fact that this model is NP hard, a scheduling based heuristic algorithm is developed. The mixed model assembly line design methodology, which includes a team-oriented algorithm as a step, is proposed. Both model sequencing and worker transfer systems are included in the methodology. The algorithms for each step of the methodology are also coded by using MATLAB and MS Excel is used as the user interface. Furthermore, the presented methodology was applied in a chosen segment of a real life mixed model tractor assembly system.