A mathematical model and ant colony algorithm for multi-manned assembly line balancing problem

In real-world assembly lines, that the size of the product is large (e.g., automotive industry), usually there are multi-manned workstations where a group of workers simultaneously perform different operations on the same individual product. This paper presents a mixed integer programming model to solve the balancing problem of the multi-manned assembly lines optimally. This model minimizes the total number of workers on the line as the first objective and the number of opened multi-manned workstations as the second one. Since this problem is well known as NP (nondeterministic polynomial-time)-hard, a heuristic approach based on the ant colony optimization approach is developed to solve the medium- and large-size scales of this problem. In the proposed algorithm, each ant tries to allocate given tasks to multi-manned workstations in order to build a balancing solution for the assembly line balancing problems by considering the precedence relations, multi-manned assembly line configuration, task times, and cycle time constraints. Through computational experiments, the performance of the proposed ACO is compared with some existing heuristic on various problem instances. The experimental results validate the effectiveness and efficiency of the proposed algorithm.     

Balancing of stochastic U-type assembly lines: an imperialist competitive algorithm

Recently, there is a growing interest in the industry to replace traditional straight assembly lines with U-shaped lines for more flexibility and higher productivity. Due to mathematical and computational complexity, assembly line balancing problems are known to be NP hard in nature. Therefore, many meta-heuristics have been proposed to find optimal solution for these problems. This paper presents a new hybrid evolutionary algorithm to solve stochastic U-type assembly line balancing problems, with the aim of minimizing the number of work stations, idle time at each station, and non-completion probabilities of each station (probability of the station time exceeding cycle time). The proposed algorithm is a combination of computer method for sequencing operations for assembly lines (COMSOAL), task assignment rules heuristic, and newly introduced imperialist competitive algorithm (ICA). Unlike the current evolutionary algorithms that are computer simulation of natural processes, ICA is inspired from socio-political evolution processes. Since appropriate design of the parameters has a significant impact on the algorithm efficiency, various parameters of the ICA are tuned by means of the Taguchi method. For the evaluation of the proposed hybrid algorithm, the performance of the proposed method is examined over benchmarks from the literature and compared with the best algorithm proposed before. Computational results demonstrate the efficiency and robustness of our algorithm.     

基于遗传算法的直线型和U型混流装配线平衡问题研究

针对混流装配线上不同产品作业时间差异导致的工作站瞬时负荷不均衡问题,提出了一种改进的直线型和U型混流装配线多目标平衡方法,并以装配线平衡率、平滑指数作为平衡效果的评价指标。综合考虑工序分配约束、工作站约束、优先关系约束和节拍约束等约束条件,同时兼顾工作站数最小和各工作站内不同品种产品负荷均衡2个目标函数,分别建立直线型和U型混流装配线多目标平衡优化模型。采用遗传算法作为优化算法,并在变异环节加入强制规则,使得变异过程能够朝着规定方向进行,以提高可行解的比例。最后通过对比算例分析结果,表明所提方法能够快速有效求解直线型和U型混流装配线平衡问题,可以为企业在直线型和U型混流装配线规划阶段制定平衡方案提供参考。     

基于元胞自动机的第Ⅱ类装配线平衡问题求解

针对第Ⅱ类装配线平衡问题的特点,给出其数学描述,并提出了一种基于元胞自动机的动态仿真求解算法。将实际装配线平衡问题抽象成由操作、工位及操作分配规则构成的系统,定义工位为模型网络空间的固定格点,操作为移动粒子,平衡装配线的方式为状态演化规则,并细分为转移规则和交换规则;同时设计规则的执行条件以及算法的总流程。标杆问题的求解结果证明了该算法的可行性,与相关文献的比对试验说明该算法得到最优解的几率更大,所求解的相对误差更小,算法性能更优。

     

Station ant colony optimization for the type 2 assembly line balancing problem

An improved ant colony optimization (ACO), namely, station ant colony optimization (SACO), is proposed to solve the type 2 assembly line balancing problem (ALBP-2). In the algorithm, ACO is employed to search different better combinations of tasks (component solutions) for each station; an iteration compress mechanism is proposed to reduce the searching space of feasible solutions of ALBP-2. Three heuristic factors [i.e., (1) task time, (2) number of successors, and (3) number of releasable successors], two pheromones, and a task assignment mechanism are proposed to search better component solutions for every station. Finally, the effectiveness and stability of SACO are confirmed through comparison with literatures in 23 instances included in nine examples.     

管控一体柔性装配线平衡问题研究

针对影响管控一体柔性装配线平衡因素的复杂性与多样性问题,提出一种基于实时分析工序装配柔性因子的管控策略和改进型遗传算法的优化处理方法。首先综合权衡管控一体柔性装配线不平衡的各类因素,为装配工序建立装配次数-预期时间函数与平衡模型;其次在管控决策台对平衡状态实时分析的基础上,构建了基于改进型遗传算法的优化处理模型,并给出基于动态工位分割算法和动态交叉、变异概率的算法改进步骤。     

Product family assembly line balancing based on an improved genetic algorithm

Product family assembly line (PFAL) is a mixed-model assembly line on which a family of similar products can be assembled at the same time. Aiming at the balance problem of PFAL, a balancing model for PFAL is established, and simultaneously an improved dual-population genetic algorithm is proposed. Firstly, through the characteristic analysis of PFAL, the tasks on PFAL are divided into three categories, namely the common, optional, and personality tasks. In addition, the correlation between the tasks is mainly considered. In the improved genetic algorithm, minimizing the number of stations, minimizing the load indexes between stations and within each station, and maximizing task-related degree are used as optimization objectives. In the initialization process, a method based on a TOP sorting algorithm is adopted for generating chromosomes. Furthermore, a new decoding algorithm is proposed to make up for the lack of the traditional decoding method, and individuals in the two populations are exchanged. Therefore, the search speed of the algorithm is accelerated, which shows good performance through classic tested problems. Finally, the effectiveness and feasibility of the method were validated by optimizing assembly line balancing of loaders.     

Multi-objective artificial bee colony algorithm for simultaneous sequencing and balancing of mixed model assembly line

In recent years, mixed model assembly lines are gaining popularity to produce a variety of models on the single-model assembly lines. Mixed model assembly lines have two types of problems which include sequencing of different models on the line and balancing of assembly line. These two problems collectively affect the performance of assembly lines, and therefore, current research is aimed to balance the workload of different models on each station, to reduce the deviation of workload of a station from the average workload of all the stations and to minimize the total flow time of models on different stations simultaneously. A multi-objective artificial bee colony (multi-ABC) algorithm for simultaneous sequencing and balancing problem with Pareto concepts and local search mechanism is presented. Two kinds of mixed model assembly line problems are analysed. For the first and second problems, each model task time data and precedence relation data are taken from standard assembly line problems, from operation research library (ORL) and from a truck manufacturing company in China, respectively. Both problems are solved using the proposed multi-ABC algorithm on two different demand scenarios of models, and the results are compared against the results obtained from a famous algorithm in the literature, i.e. non-dominated sorting genetic algorithm (NSGA) II. Computational results of the selected problems indicate that the proposed multi-ABC algorithm outperforms NSGA II and gives better Pareto solutions for the selected problems on different demand scenarios of models.     

[工艺规划与装配线平衡]基于果蝇算法的第二类装配线平衡问题

根据第二类装配线平衡问题的特点,兼顾生产节拍最小和工作负荷均衡,建立了多目标研究模型,运用果蝇算法对标杆案例进行求解,并通过MATLAB进行了仿真研究。将果蝇算法优化结果与标杆案例中自适应遗传算法求解的结果进行对比可知,生产节拍缩短,装配线平衡率进一步提升,且各工作站的负荷更加均衡,从而验证了果蝇算法求解第二类装配线平衡问题的有效性,果蝇算法在获取全局最优解的能力上比自适应遗传算法更强。     

Literature review of assembly line balancing problems

Mass production system design is a key for the productivity of an organization. Mass production system can be classified into production line machining a component and production line assembling a product. In this paper, the production line assembling a product, which is alternatively called as assembly line system, is considered. In this system, balancing the assembly line as per a desired volume of production per shift is a challenging task. The main objectives of the assembly line design are to minimize the number of workstations for a given cycle time (type 1), to minimize the maximum of the times of workstations for a given number of workstations (type 2), and so forth. Because this problem comes under combinatorial category, the use of heuristics is inevitable. Development of a mathematical model may also be attempted, which will help researchers to compare the solutions of the heuristics with that of the model. In this paper, an attempt is made to present a comprehensive review of literature on the assembly line balancing. The assembly line balancing problems are classified into eight types based on three parameters, viz. the number of models (single-model and multi-model), the nature of task times (deterministic and probabilistic), and the type of assembly line (straight-type and U-type). The review of literature is organized as per the above classification. Further, directions for future research are also presented.     

Design configuration for a mixed-model assembly system in case of low product demand

In order to accompany the increasing variety of costumers’ demands, manufacturers tend to produce different models of the same product on an assembly line by introducing group assembly (GA) design concepts that improve the flexibility of assembly systems. Generally, when the demand for a set of similar products is relatively low and the set-up time is significant, the beneficial effects of the task repeatability of the straight line configuration are difficult to achieve. As a consequence, the fixed-point assembly philosophy is often preferred. This paper addresses the application of a mixed-model assembly balancing problem to an assembly-to-order environment in the case of low production rates and large number of tasks. The aim of this work is to propose an alternative design procedure for the balancing of semi-automated and mixed-model assembly systems under low product demand effects by the application of multi-turn circular transfers, such as a multi-stations rotating table. This layout configuration permits a job enlargement for human operators and, at the same time, provides an increment in task repeatability through the work-pieces assembling by increasing the number of the turns of the transfer. Finally, the developed heuristic procedure is tested on a simple rotating table assembly cell, a partial representation of a complete assembly system of domestic air compressors.     

Sequencing mixed-model assembly lines by considering feeding lines

A mixed-model assembly line is a type of production line where different models of a product are assembled on. Mixed-model assembly lines can respond to unanticipated changes in product demands quickly without keeping so many inventories. Designing mixed-model assembly line involves solving the traditional problems of the assembly line design (consists of balancing problem, determining cycle time, and the number and sequence of stations) in addition of determining the sequence of products in assembly line. The main goal of this paper is presenting a method in order to determine the sequence of products in mixed-model assembly line by considering Just-in-Time systems. Moreover, supplying some required components from feeding lines is considered. A mathematical model is presented which is capable of specifying the sequence of products in the mixed-model assembly line by considering main criteria and keeping feeding lines balanced. Mathematical model can be used for solving small-size problems. Because the combinatorial nature of sequencing problems typically provides an intractable search space for problems of “real world” size, the search heuristics of simulated annealing and ant colony algorithms are presented and used to find solutions for several problem sets. Experimentations show that the simulated annealing approach outperforms the ant colony approach in objective function performance.     

基于混合优化算法的装配线平衡问题

为求解给定装配线生产节拍、最大化装配效率的装配线平衡问题,根据装配线的特点和平衡优化需求,分析了装配作业顺序、站位数量等因素对装配线站位内作业分配的影响,综合考虑装配线平衡率和平滑系数,建立了装配线平衡问题数学模型,并设计了一种结合遗传算法(Genetic Algorithm,GA)、蚁群算法(Ant Colony Optimization algorithm,ACO)的混合优化算法进行求解。采用遗传算法进行快速随机的全局搜索,并生成信息素矩阵初始分布,利用蚁群算法进行精确求解。最后通过标准案例测试,证明了该混合优化算法具有更高的优化效率,同时验证了算法的可行性和有效性。     

A Petri net approach for simple assembly line balancing problems

A simple assembly line balancing problem of type-1 (SALBP-1) aims to minimize the number of workstations for a given cycle time. In the relevant literature, several heuristics based on a branch-and-bound procedure, tabu search, and genetic algorithms (GAs) were proposed to solve SALBP-1. In this paper, an algorithm based on the reachability analysis of Petri nets is developed for SALBP-1. The proposed algorithm searches enabled transitions (or assignable tasks) in the Petri net model of precedence relations between tasks, and then the task minimizing the idle time is assigned to the station under consideration. 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. A computational study validates its effectiveness on Tonge’s 70-task problem by comparison with optimal solutions of traditional heuristics and a GA.     

Stochastic U-line balancing using genetic algorithms

The advantages of U-type lines are very well known in industry. They offer improved productivity and quality, and are considered as one of the better techniques in implementing just-in-time (JIT) systems. There is a growing interest in the literature to organize traditional assembly lines as U-lines for improved performance. U-type assembly line balancing is an extension of the traditional line balancing problem, in which tasks can be assigned from both sides of the precedence diagram. Although there are many studies in the literature for the design of traditional straight assembly lines, the work on U-type lines is limited. Moreover, in most of the previous studies, task times are assumed to be deterministic. In this paper, a new multiple-rule-based genetic algorithm (GA) is proposed for balancing U-type assembly lines with stochastic task times.     

A bidirectional heuristic for stochastic assembly line balancing Type II problem

In this paper, a heuristic algorithm is proposed to solve the single-model stochastic assembly line balancing Type II problem. For a given number of workstations and a pre-specified assembly line reliability, which is the probability of the workload not exceeding the cycle time for the whole assembly line, the proposed algorithm tries to obtain a solution with the smallest cycle time. In the first stage, the tasks are assigned to workstations from the forward and backward directions alternatively. In the second stage, the workload is smoothed by swapping tasks among workstations. At last, the upper bound of the cycle time obtained in the second stage is reduced step by step until the smallest cycle time satisfies the pre-specified assembly line reliability. The performance of the proposed algorithm is compared with a modified version of Moodie and Youngs algorithm by applying them to some literature problems. The computational results show that the proposed algorithm is efficient in minimizing the cycle time for the single-model stochastic assembly line balancing problem.     

Modelling human performance within an automotive engine assembly line

In this paper, we first investigate a semi-automated automotive engine assembly line in which the traditional strategy of using fixed workers in each manual assembly section is replaced by a new strategy of using walking workers. With this approach, both worker and engine travel simultaneously down the line; each worker is previously trained to accomplish a series of assembly tasks independently from start to finish in each manual assembly section. The study has shown great improvement of the overall system performance in terms of flexibility, efficiency, responsiveness and re-configurability using dynamic, flexible and skilled walking workers. Nevertheless, the main problem of this design is that each worker needs to be cross-trained to acquire a satisfactory level of skills associated with the assignment of assembly tasks. This is crucial for achieving a relatively even working speed at which each worker assembles a product down the line without major interruption between two adjacent workstations. In theory, the familiar degree of completing assigned tasks by each worker through training can be measured and expressed as a learning curve. In this case, the learning curve has been used to determine a trade-off decision between the complexity of assigned tasks and the duration of completing these tasks by a walking worker at a stabilised level. It has also been used to investigate the impact of the system variation that may affect the performance of individual walking workers through a learning process. Thus, the paper also describes a framework to assess the human performance by modelling the learning curve for each walking worker based in an integrated model. This model was created using a simulation tool Witness with its key input/output data manipulated externally by a series of Microsoft Excel worksheets incorporating the effect of a number of human factors in terms of cognitive and physical elements. With this method, the possible and realistic assignment of selected assembly tasks for each walking worker can be quantified.     

Optimization of line configuration and balancing for flexible machining lines

Line configuration and balancing is to select the type of line and allot a given set of operations as well as machines to a sequence of workstations to realize high-efficiency production. Most of the current researches for machining line configuration and balancing problems are related to dedicated transfer lines with dedicated machine workstations. With growing trends towards great product variety and fluctuations in market demand, dedicated transfer lines are being replaced with flexible machining line composed of identical CNC machines. This paper deals with the line configuration and balancing problem for flexible machining lines. The objective is to assign operations to workstations and find the sequence of execution, specify the number of machines in each workstation while minimizing the line cycle time and total number of machines. This problem is subject to precedence, clustering, accessibility and capacity constraints among the features, operations, setups and workstations. The mathematical model and heuristic algorithm based on feature group strategy and polychromatic sets theory are presented to find an optimal solution. The feature group strategy and polychromatic sets theory are used to establish constraint model. A heuristic operations sequencing and assignment algorithm is given. An industrial case study is carried out, and multiple optimal solutions in different line configurations are obtained. The case studying results show that the solutions with shorter cycle time and higher line balancing rate demonstrate the feasibility and effectiveness of the proposed algorithm. This research proposes a heuristic line configuration and balancing algorithm based on feature group strategy and polychromatic sets theory which is able to provide better solutions while achieving an improvement in computing time.     

An integrated allocation method for the PCB assembly line balancing problem with nozzle changes

There are several placement machines connected by a conveyor in a printed circuit board assembly line. The objective of the line balancing problem is to minimize the cycle time of the assembly line, which is the maximum production time of the placement machines. In this paper, the nozzle factor, which is often ignored, is considered in estimating the production time of the placement machine, and the nozzle change is also allowed. The production time of a machine is a linear function of the number of components, the number of turns and the number of nozzle changes performed by the machine, which are determined by the component allocation problem, the nozzle set allocation problem and the head allocation problem. These three allocation problems compose the line balancing problem and are solved iteratively. First, the component allocation problem is solved by proposed genetic algorithms (GAs), which generate feasible allocation solutions directly. To search efficiently, non-selective and selective allocation strategies are proposed to solve the component allocation problem. A greedy heuristic (GH) is proposed to solve the nozzle set allocation problem and the head allocation problem simultaneously. Then, the GAs for the component allocation and the GH for the nozzle set and head allocation are integrated according to their interactive relations. Finally, the efficiency of the composite algorithm is illustrated by numerical analysis.     

A Multi-Objective Genetic Algorithm for Solving Assembly Line Balancing Problem

In this paper, a multi-objective genetic agorithm to solve assembly line balancing problems is proposed. The performance criteria considered are the number of workstations, the line efficiency, the smoothness index before trade and transfer, and the smoothness index after trade and transfer. The developed genetic algorithm is compared with six popular heuristic algorithms, namely, ranked positional weight, Kilbridge and Wester, Moodie and Young, Hoffmann precedence matrix, immediate update first fit, and rank and assign heuristic methods. For comparative evaluation, 20 networks are collected from open literature, and are used with five different cycle times. All the six heuristics and the genetic algorithm are coded in C++ language. It is found that the proposed genetic algorithm performs better in all the performance measures than the heuristics. However, the execution time for the GA is longer, because the GA searches for global optimal solutions with more iterations.