Mixed-model U-shaped assembly lines: Balancing and comparing with straight lines with buffers and parallel workstations

In the paper a genetic algorithm approach is proposed to balance asynchronous mixed-model U-shaped lines with stochastic task times. U-shaped lines have become popular in recent years for their ability to outperform straight assembly lines in terms of line efficiency. The great majority of studies in the literature deal with paced synchronous U-shaped lines. Asynchronous lines can be more efficient than synchronous lines, but are more difficult to study, due to blocking and starvation phenomena caused by the variability of completion times: this makes it difficult to calculate the effective throughput. This variability, that in straight lines comes from the stochastic nature of task times and from the changing of models entering the line, is even higher in U-shaped lines, where an operator can work at two different models in the same cycle at the two sides of the line. For this reason, the genetic algorithm proposed is coupled to a parametric simulator for the evaluation of the objective function, which contains the simulated throughput. Two alternative chromosomal representations are tested on an ample set of instances from the literature. The best solutions are also compared with the best solutions known in the literature, on the same instances, for straight lines with buffers and parallel workstations. From the comparison it turns out that U-shaped lines are generally more efficient with respect to straight lines with buffers. This is because crossover work centers naturally act similarly to unitary buffers, providing two places in which two loads can be placed simultaneously. The superiority of U-shaped lines holds true as long as it is possible to take full advantage of the employment of crossover work centers. For particular types of instances, depending on the distribution of task times, this possibility decreases, so that straight lines with parallel workstations and buffers are preferable.     

Bacterial Foraging Optimization Algorithm for assembly line balancing

Assembly line balancing is the problem of assigning tasks to workstations by optimizing a performance measure while satisfying precedence relations between tasks and cycle time restrictions. Many exact, heuristic and metaheuristic approaches have been proposed for solving simple straight and U-shaped assembly line balancing problems. In this study, a relatively new optimization algorithm, Bacterial Foraging Optimization Algorithm (BFOA), based heuristic approach is proposed for solving simple straight and U-shaped assembly line balancing problems. The performance of the proposed algorithm is evaluated using a well-known data set taken from the literature in which the number of tasks varies between 7 and 111, and results are also compared with both an ant-colony-optimization-based heuristic approach and a genetic-algorithm-based heuristic approach. The proposed algorithm provided optimal solutions for 123 out of 128 (96.1 %) test problems in seconds and is proven to be promising.     

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.     

Mixed model U-line balancing type-1 problem: A new approach

Avoiding work overload (imbalance) in mixed model U-line production systems entails an investigation into both balancing and sequencing problems at the same time and that is why some authors have considered both planning problems simultaneously. However because of the existing differences between planning horizons of balancing and sequencing problems (the former is a long to mid-term planning problem whereas the latter has a short term planning horizon) this simultaneous approach is only practical under very special conditions. It is also known that installation of an assembly line usually needs considerable capital investments and consequently it is necessary to design and balance such a system so that it works as efficiently as possible. To do so, in this paper, we develop a new approach to balance a mixed model U-shaped production system independent of what product sequences may be. This new approach is based on minimization of crossover workstations. Due to utilization of crossover workstations, balancing mixed model assembly lines in U-shaped line layouts is more complicated than that of straight lines. Some kind of issues including the ‘model mixes’ appearing in such workstations and the time taken for an operator to move from one side of the line to another increase the complexity of mixed model U-line balancing problems (MMULBP). Therefore it seems reasonable to develop a model in which minimizing the number of crossover workstations and maximizing the line efficiency are considered at the same time. Such a model is presented in this paper. In the proposed model, minimizing the variation of workload is also considered and taking into account operator's travel times, an extra time is assigned to workload of crossover workstations. Furthermore a genetic algorithm (GA) is proposed and a number of well-known test problems are solved by the GA and the related results are illustrated. Finally, the conclusion is presented.     

Multi-rule Multi-objective Simulated Annealing Algorithm for Straight and U Type Assembly Line Balancing Problems

The task of balancing of assembly lines is of considerable industrial importance. It consists of assigning operations to workstations in a production line in such a way that (1) no assembly precedence constraint is violated, (2) no workstations in the line takes longer than a predefined cycle time to perform all tasks assigned to it, and (3) as few workstations as possible are needed to perform all the tasks in the set. This paper presents a new multiple objective simulated annealing (SA) algorithm for simple (line) and U type assembly line balancing problems with the aim of maximizing “smoothness index” and maximizing the “line performance” (or minimizing the number of workstations). The proposed algorithm makes use of task assignment rules in constructing feasible solutions. The proposed algorithm is tested and compared with literature test problems. The proposed algorithm found the optimal solutions for each problem in short computational times. A detailed performance analysis of the selected task assignment rules is also given in the paper.     

A hybrid algorithm for allocating tasks,operators, and workstations in multi-manned assembly lines

In a car, there are approximately 30,000 parts produced by many different industries. This is due to the complexity and enormity of the automotive industry chain. The vehicle assembly process comprises welding, painting, prefabrication, and final entire-vehicle assembly. The assembly line has the largest labor force, which should be arranged and balanced to increase production efficiency and reduce labor force requirements. Unlike traditional studies on assembly line balancing problems (ALBPs), this study considers the characteristics of the automotive industry, such as multi-manned workstations, minimization in terms of the numbers of operators and workstations for streamlined production, budget constraints, the optimization of both task and operator allocation among workstations, and the determination of the start/end processing time of each task at different workstations. To address these NP-hard problems, a hybrid heuristic approach that combines the procedure of building feasible balancing solutions and the simulated annealing algorithm is proposed to map out an optimal line balancing plan for multi-manned workstations and to reduce the required workspace for shop operations. Based on the design and analysis of experiments, the effects of the maximum number of allowed operators per workstation and those of the cycle time on ALBP solutions are explored. The optimal combination of algorithm parameters is also determined. The results of this study can serve as a practical reference in planning the allocation of tasks, workstations, and operators in the industry.     

A mathematical model and a genetic algorithm for two-sided assembly line balancing

A two-sided assembly line is a type of production line where tasks are performed in parallel at both sides of the line. The line is often found in producing large products such as trucks and buses. This paper presents a mathematical model and a genetic algorithm (GA) for two-sided assembly line balancing (two-ALB). The mathematical model can be used as a foundation for further practical development in the design of two-sided assembly lines. In the GA, we adopt the strategy of localized evolution and steady-state reproduction to promote population diversity and search efficiency. When designing the GA components, including encoding and decoding schemes, procedures of forming the initial population, and genetic operators, we take account of the features specific to two-ALB. Through computational experiments, the performance of the proposed GA is compared with that of a heuristic and an existing GA with various problem instances. The experimental results show that the proposed GA outperforms the heuristic and the compared GA.     

附带翻转工位双边装配线蚁群算法优化设计

双边装配线应用广泛,翻转工位操作能有效降低部分零件装配难度与操作风险,但增加了设计难度。基于此,研究了附带翻转工位操作的挖掘机底盘双边装配线规划设计问题,针对该问题提出了一种改进蚁群算法求解。给出了问题求解的启发式任务分配规则,提出可采用启发式任务选择规则以提高算法收敛速率。进而分析某型挖掘机底盘装配线得出先后约束关系图,将问题抽象为双边装配线优化设计问题。随后,采用两种蚁群算法进行附带翻转工位的装配线优化,分析比较了两种算法因结构差异对优化结果所造成的影响。     

Assembly line balancing in garment industry

Garment manufacturing is a traditional industry with global competition. The most critical manufacturing process is sewing, as it generally involves a great number of operations. The aim of assembly line balance planning in sewing lines is to assign tasks to the workstations, so that the machines of the workstation can perform the assigned tasks with a balanced loading. Assembly line balancing problem (ALBP) is known as an NP-hard problem. Thus, the heuristic methodology could be a better way to plan the sewing lines within a reasonable time.This paper develops a grouping genetic algorithm (GGA) for ALBP of sewing lines with different labor skill levels in garment industry. GGA can allocate workload among machines as evenly as possible for different labor skill levels, so the mean absolute deviations (MAD) can be minimized. Real data from garment factories and experimental design are used to evaluate GGA’s performance. Production managers can use the research results to quickly design sewing lines for important targets such as short cycle time and high labor utilization.     

Event and object oriented simulation to fast evaluate operational objectives of mixed model assembly lines problems

In this paper an event and object oriented simulator for assembly lines is presented. The tool, developed in Java, is capable to simulate mixed model assembly lines, with stochastic task times, parallel stations, fixed scheduling sequences, and buffers within workstations. The simulator is a flexible supporting tool in finding solution of the mixed model assembly line balancing problem (and the optimal sequencing and buffer allocation problems associated to it). It is capable to immediately calculate the throughput of a complex line, by simply receiving as inputs three arrays representing: the task times durations, the line configuration (number of workcentres, of buffers within them, of parallel workstations in each workcentre, of tasks assigned to each workcentre), and the sequence of models entering the line. Its fastness and flexibility allow its utilization in those algorithms and procedures where the evaluation of a fitness function (which includes the throughput as performance indicator) has to be performed several times. It allows overcoming the limit of using others measures of throughput, presented in literature, that are poorly correlated to its real value when the complexity of the line increases. The simulator is an expandable tool; in its current version provides the possibility to simulate both straight and U-shaped lines, and to generate both random and fixed sequences of models entering the line.     

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.     

An efficient branch and bound algorithm for assembly line balancing problems with parallel multi-manned workstations

In the event that big-sized complex products (containing a large number of assembly tasks most of which have long task times) are produced in simple or two-sided assembly lines, hundreds of stations are essentially required. Long product flow time, a large area for establishment of the line, a high budget for the investment of equipment, and tools in stations and several work-in-process are also required for these kinds of products. In order to avoid these disadvantages, assembly lines with parallel multi-manned workstations can be utilized. In this paper, these lines and one of their balancing problems are addressed, and a branch and bound algorithm is proposed. The algorithm is composed of a branching scheme, some efficient dominance and feasibility criteria based on a problem-specific knowledge. A heuristic-based guidance for enumeration process is included as an efficient component of the algorithm as well. VWSolver algorithm proposed for a special version of the problem in the literature has been modified and compared with the proposed algorithm. Results show that proposed algorithm outperforms VWSolver in terms of both CPU times and quality of feasible solutions found.     

Sequencing in mixed model assembly lines: A genetic algorithm approach

The mixed model assembly lines are becoming increasingly popular in a wide area of industries. We consider the sequencing problem in mixed model assembly lines, which is critical for efficient utilization of the lines. We extend standard formulation of the problem to allow a hybrid assembly line, in which closed and open workstations are intermixed, and sequence-dependent setup time. A new approach using an artificial intelligence search technique, called genetic algorithm, is proposed. A genetic representation suitable for the problem is investigated, and genetic control parameters that yield good results are empirically found. A new genetic operator, Immediate Successor Relation Crossover (ISRX), is introduced and several existing ones are modified. An extensive experiment is carried out to determine a proper choice of the genetic operators. The performance of the genetic algorithm is compared with those of heuristic algorithm and of branch-and-bound method. The results show that our algorithm greatly reduces the computation time and its solution is very close to the optimal solution. We have identified the ISRX operator to play a significant role in improving the performance.     

An efficient approach for type II robotic assembly line balancing problems

In the past decades, robots have been extensively applied in assembly systems as called robotic assembly lines. When changes in the production process of a product take place, the line needs to be reconfigured in order to improve its productivity. This study presents a type II robotic assembly line balancing (rALB-II) problem, in which the assembly tasks have to be assigned to workstations, and each workstation needs to select one of the available robots to process the assigned tasks with the objective of minimum cycle time. An innovative genetic algorithm (GA) hybridized with local search is proposed for the problem. The genetic algorithm uses a partial representation technique, where only part of the decision information about a candidate solution is expressed in the chromosome and the rest is computed via a heuristic method. Based on different neighborhood structures, five local search procedures are developed to enhance the search ability of GA. The coordination between these procedures is well considered in order to escape from local optima and to reduce computation time. The performance of the hybrid genetic algorithm (hGA) is tested on 32 rALB-II problems and the obtained results are compared with those by other methods.     

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.     

Accumulated risk of body postures in assembly line balancing problem and modeling through a multi-criteria fuzzy-genetic algorithm

Monotonous body postures during repetitive jobs negatively affect assembly-line workers with the developing of Work-related Musculoskeletal Disorders (WMSDs). Ergonomics specialists have offered auxiliary posture diversity to deal with the lack of varieties, especially for high-risk ones. Meanwhile, Assembly Line Balancing (ALB) problem has been recognized as a prior thinking to (re)configure assembly lines via the balancing of their tasks among their workstations. Some conventional criteria, cycle time and overall workload are often considered during the balancing. This paper presents a novel model of ALB problem that incorporates assembly worker postures into the balancing. In addition to the conventional ALB criteria, a new criterion of posture diversity is defined and contributes to enhance the model. The proposed model suggests configurations of assembly lines via the balancing; so that the assigned workers encounter the opportunities of changing their body postures, regularly. To address uncertainties in the conventional criteria, a fuzzy goal programming is used, and an appropriate genetic algorithm is developed to deal with the model. Various computational tests are performed on the different models made with combinations of the three criteria mentioned above. Comparing the pay-offs among the combinations, results show that well balanced task allocation can be obtained through the proposed model.     

A comparative study of Multi-Objective Ant Colony Optimization algorithms for the Time and Space Assembly Line Balancing Problem

Assembly lines for mass manufacturing incrementally build production items by performing tasks on them while flowing between workstations. The configuration of an assembly line consists of assigning tasks to different workstations in order to optimize its operation subject to certain constraints such as the precedence relationships between the tasks. The operation of an assembly line can be optimized by minimizing two conflicting objectives, namely the number of workstations and the physical area these require. This configuration problem is an instance of the TSALBP, which is commonly found in the automotive industry. It is a hard combinatorial optimization problem to which finding the optimum solution might be infeasible or even impossible, but finding a good solution is still of great value to managers configuring the line. We adapt eight different Multi-Objective Ant Colony Optimization (MOACO) algorithms and compare their performance on ten well-known problem instances to solve such a complex problem. Experiments under different modalities show that the commonly used heuristic functions deteriorate the performance of the algorithms in time-limited scenarios due to the added computational cost. Moreover, even neglecting such a cost, the algorithms achieve a better performance without such heuristic functions. The algorithms are ranked according to three multi-objective indicators and the differences between the top-4 are further reviewed using statistical significance tests. Additionally, these four best performing MOACO algorithms are favourably compared with the Infeasibility Driven Evolutionary Algorithm (IDEA) designed specifically for industrial optimization problems.     

A Lagrangian relaxation technique for the general assembly line balancing problem

This paper addresses the problem of balancing assembly or fabrication lines. In order to achieve a given production rate or to optimize the use of workstations, one has to tackle the problem of balancing the production lines. It is well known that this problem belongs to the class of NP-hard problems. In this paper the polyhedron of the feasible solutions of the assembly line balancing problem is first studied. Then a Lagrangian relaxation algorithm that incorporates the set of cycle constraints in the objective function is proposed. These constraints are the complicating restrictions in the model. The relaxed problem has the interesting property that its linear programming relaxation always has integer optimal solutions. The subgradient algorithm is then used to maximize the Lagrangian dual. A heuristic is also used to find primal feasible solutions for the original line balancing integer program. These two bounds are then used to reduce the size of the branch-and-bound tree.     

A Knowledge Based Design Methodology for manufacturing assembly lines

In assembly line design, the problem of balancing has received most attention from past researchers, and a number of algorithms have been devised for the analysis of single, multi- and mixed-product assembly lines [Int. J. Prod. Res. 27 (1989) 637]. In many cases, such algorithms seek a solution for the particular situation, which is under consideration and therefore have very little flexibility for generic application to assembly line design. Real life practical design issues include stochastic operation times, parallel workstation requirements, feasibility for workstation combining, and parallel line implementations, all of which are features which are ignored in many analyses. This paper presents a Knowledge Based Design Methodology (KBDM) for automated and manual assembly lines, which can be applied equally well to single, multi- and mixed-product assembly lines with either deterministic operation times or stochastic operation times. The methodology starts from a suitable assembly system selection and thereafter decides suitable cycle times, parallel workstation requirements, and parallel line implementation for the type of assembly system being selected. An economical number of workstations are decided with the aid of workstation combining options depending upon the factual information provided. The end result is the detailed design of a manufacturing assembly line. A case study from a practical assembly line is presented to illustrate how the KBDM works.