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.     

Assembly line balancing and group working: A heuristic procedure for workers’ groups operating on the same product and workstation

In this paper, we examine an assembly line balancing problem that differs from the conventional one in the sense that there are multi-manned workstations, where workers’ groups simultaneously perform different assembly works on the same product and workstation. This situation requires that the product is of sufficient size, as for example in the automotive industry, so that the workers do not block each other during the assembly work. The proposed approach here results in shorter physical line length and production space utilization improvement, because the same number of workers can be allocated to fewer workstations. Moreover, the total effectiveness of the assembly line, in terms of idle time and production output rate, remains the same. A heuristic assembly line balancing procedure is thus developed and illustrated. Finally, experimental results of a real-life automobile assembly plant case and well-known problems from the literature indicate the effectiveness and applicability of the proposed approach in practice.     

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 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 recursive operator allocation approach for assembly line-balancing optimization problem with the consideration of operator efficiency

This paper addresses an optimization model for assembly line-balancing problem in order to improve the line balance of a production line under a human-centric and dynamic apparel assembly process. As the variance of operator efficiency is vital to line imbalance in labor intensive industry, an approach is proposed to balance production line through optimal operator allocation with the consideration of operator efficiency. Two recursive algorithms are developed to generate all feasible solutions for operator allocation. Three objectives, namely, the lowest standard deviation of operation efficiency, the highest production line efficiency and the least total operation efficiency waste, are devised to find out the optimal solution of operator allocation. The method in this paper improves the flexibility of the operator allocation on different sizes of data set of operations and operators, and enhances the efficiency of searching for the optimal solution of big size data set. The results of experiments are reported. The performance comparison demonstrates that the proposed optimization method outperforms the industry practice.     

A recursive operator allocation approach for assembly line-balancing optimization problem with the consideration of operator efficiency

This paper addresses an optimization model for assembly line-balancing problem in order to improve the line balance of a production line under a human-centric and dynamic apparel assembly process. As the variance of operator efficiency is vital to line imbalance in labor intensive industry, an approach is proposed to balance production line through optimal operator allocation with the consideration of operator efficiency. Two recursive algorithms are developed to generate all feasible solutions for operator allocation. Three objectives, namely, the lowest standard deviation of operation efficiency, the highest production line efficiency and the least total operation efficiency waste, are devised to find out the optimal solution of operator allocation. The method in this paper improves the flexibility of the operator allocation on different sizes of data set of operations and operators, and enhances the efficiency of searching for the optimal solution of big size data set. The results of experiments are reported. The performance comparison demonstrates that the proposed optimization method outperforms the industry practice.     

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.     

工位数固定的U型拆卸线部分拆卸平衡问题

为提高工位数固定的U型拆卸线拆卸效率, 减少有害部件对操作人员的潜在威胁, 针对高价值零部件和有害零部件的拆卸需求, 本文提出了工位数固定的U型拆卸线部分拆卸平衡问题, 建立了以最小化节拍时间、高危工位数目和负载均衡为目标的优化模型, 并设计了改进的变邻域搜索算法进行求解. 在编码过程中提出一种基于零部件释放位置的选择策略, 以减少前继零部件拆卸顺序对编码的影响; 提出最小偏差二分法, 有效减少解码的迭代次数; 提出瓶颈挤压局部搜索策略, 用以优化节拍时间和均衡负载指标. 通过与其他算法对比, 结果表明改进的变邻域搜索算法求解具有优越性, 并且可实现对工位数固定的U型拆卸线部分拆卸平衡问题的高效求解.     

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.     

A Simulated Annealing algorithm for a mixed model assembly U-line balancing type-I problem considering human efficiency and Just-In-Time approach

This research deals with balancing a mixed-model U-line in a Just-In-Time (JIT) production system. The research intends to reduce the number of stations via balancing the workload and maximizing the weighted efficiency, which both are considered as the objectives of this research paper.After balancing the line and determining the number of stations, the labor assignment policy should be set. In this study, it was assumed that there are two types of operators: permanent and temporary. Both types can work in regular and overtime periods. Based on their skill levels, workers are classified into four types. The sign at each work station indicates types of workers allowed to work at that station. An alert system using the hybrid kanban systems was also considered. To solve this problem, a Simulated Annealing algorithm was applied in the following three stages. First, the balancing problem was solved and the number of stations was determined. Second, workers were assigned to the workstations in which they are qualified to work. Following that, an alert system based on the kanban system was designed to balance the work in the process inventory. This was achieved by defining control points based on the processing time and making control decisions to minimize the number of kanban cards. In the proposed SA algorithm, two methods for the temperature cooling schedule were considered and two methods were defined for determining the number of neighborhood search. The initial temperature was considered equal to the cost of the initial solution to reach the convergence situation as soon as possible. Five problems were solved in small size using the GAMS software. The results obtained from the GAMS software were compared with those obtained from the SA algorithm to determine the performance difference. The computational results demonstrated that the SA algorithm is more consistent with the answers obtained. Also seven large scale problems were solved. The results showed that the SA algorithm still have better reliability. To show the efficiency of the proposed SA algorithm, an axel assembly company was studied. To satisfy demands and reduce backlogging, a mixed model assembly line was designed for this case study. The results showed that the mixed model assembly line designed using the SA algorithm had good efficiency.     

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.     

A hybrid ant colony algorithm for U-line balancing and rebalancing in just-in-time production environment

U-line balancing is an important problem for designing a new U-line. It is about combining a finite set of tasks to form workstations optimally with the restriction of given precedence relationships in a new U-line. As the demand varies, the U-line should be rebalanced to eliminate waste and improve the production efficiency as part of just-in-time principles. If all machines can be moved freely, the rebalancing problem equals to the balancing problem. In practice, some machines are stationary or need certain moving cost. In this paper, U-line rebalancing problem is formalized with respect to minimization the moving cost of machines and labor cost. The walking time of operators is considered to avoid generating awkward walking path. A new hybrid algorithm of ant colony optimization and filtered beam search is presented to solve the problem. The hybrid algorithm adopts the framework of ant colony optimization. In the process of constructing path, each ant explores several nodes for one step and chooses the best one by global and local evaluation at a given probability. Computational results show that the proposed algorithm performs quite effectively for solving U-line balancing problems in the literature by comparing to the existing solutions. Finally, the proposed algorithm for solving U-line rebalancing problem is demonstrated with an example and also yields optimal solutions.     

A genetic algorithm based approach to the mixed-model assembly line balancing problem of type II

Mixed-model assembly lines allow for the simultaneous assembly of a set of similar models of a product, which may be launched in the assembly line in any order and mix. As current markets are characterized by a growing trend for higher product variability, mixed-model assembly lines are preferred over the traditional single-model assembly lines.

This paper presents a mathematical programming model and an iterative genetic algorithm-based procedure for the mixed-model assembly line balancing problem (MALBP) with parallel workstations, in which the goal is to maximise the production rate of the line for a pre-determined number of operators.

The addressed problem accounts for some relevant issues that reflect the operating conditions of real-world assembly lines, like zoning constraints and workload balancing and also allows the decision maker to control the generation of parallel workstations.     

Balancing U-shaped assembly lines with resource dependent task times: A Simulated Annealing approach

The advent of Just-in-Time (JIT) and Group Technology philosophies has popularized U-shaped assembly lines, which help overcome many of the disadvantages, like line inflexibility, job monotony, large inventories, etc., typically associated with straight assembly lines. Although U-shaped layout has demonstrated its supremacy over the traditional straight layout, the problem of U-shaped assembly line balancing (ULB) is much more complex. The extant literature on ULB assumes that each assembly task requires a fixed (or no) equipment and a fixed number of workers. However, it is often desirable to reduce certain task times by assigning more workers or alternative equipments at a given workstation. The problem in such cases is to assign not only the task but also resource alternatives (number of workers and equipment type) to workstations. Research on such resource dependent U-shaped assembly line balancing (RDULB) is scarce. We address the problem of RDULB and propose a Simulated Annealing (SA) based metaheuristic, which gives optimal solution for most of the small-to-medium problem instances. For very large problems, while SA generates a good feasible solution within half an hour to 1.5 h, Cplex is unable to find a single feasible solution even after 10 times the CPU time required by SA.     

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.     

A heuristic approach for U-shaped assembly line balancing to improve labor productivity

The assembly line balancing problem is a non deterministic polynomial type planning problem for mass production. Layout design changes constitute a major decision that yields investment for assembly operations and numerous heuristics have been reported in the literature for solving the line balancing problems. U-shaped assembly layout offers several benefits over traditional straight-line layout in implementation of lean manufacturing and Just-In-Time technology. In the paper an attempt has been made to evaluate labor productivity in U-shaped line system and straight line system. A Critical Path Method (CPM) based approach for U-shaped assembly line has been applied for assigning the task to the work stations for assembly line layout. Results show that the CPM based U-shaped approach performs better and improve the labor productivity of assembly line layout.     

Including different kinds of preferences in a multi-objective ant algorithm for time and space assembly line balancing on different Nissan scenarios

Most of the decision support systems for balancing industrial assembly lines are designed to report a huge number of possible line configurations, according to several criteria. In this contribution, we tackle a more realistic variant of the classical assembly line problem formulation, time and space assembly line balancing. Our goal is to study the influence of incorporating user preferences based on Nissan automotive domain knowledge to guide the multi-objective search process with two different aims. First, to reduce the number of equally preferred assembly line configurations (i.e., solutions in the decision space) according to Nissan plants requirements. Second, to only provide the plant managers with configurations of their contextual interest in the objective space (i.e., solutions within their preferred Pareto front region) based on real-world economical variables. We face the said problem with a multi-objective ant colony optimisation algorithm. Using the real data of the Nissan Pathfinder engine, a solid empirical study is carried out to obtain the most useful solutions for the decision makers in six different Nissan scenarios around the world.     

基于遗传算法的焊接生产线工位平衡规划方法

在现代化大规模大批量的流水装配制造业中,数量众多的作用分配和多工位的合理安排使工位平衡问题显得更为突出。针对第一类工位平衡问题,即在给定的生产节拍下最小化工位数,首先分析了该问题并建立了数学模型,进而提出了一种基于改进遗传算法求解工位平衡问题的方法。该算法以焊接任务的操作顺序优先关系为约束前提,在初始种群的生产以及交叉和变异过程中保证了染色体解的可行性,同时在遗传算法的选择过程中考虑了具有相同工位数的最优作业方案的工时标准差,从而提高了算法的搜索效率和解的可靠性。最后通过实例求解验证了该算法的有效性。     

A multi-agent-based approach for personnel scheduling in assembly centers

This paper presents a multi-agent-based approach for personnel scheduling problems in the context of a paced multi-product assembly center. Our purpose is to elaborate daily assignment of employees to workstations in order to minimize simultaneously the operational costs and personnel dissatisfactions. The proposed approach considers the individual competencies, mobility and preferences of each employee, as well as the personnel and competency requirements associated with each assembly activity given both the current master assembly schedule and the line balancing for each product. To benchmark the performance of the multi-agent approach, we use optimal solutions obtained through a linear programming model resolution using a commercial solver. Experimental results show that our multi-agent approach can produce high-quality and efficient solutions in a short computational time.