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 mixed-model assembly line balancing problem with setups. Part I: A mixed integer linear programming model

This paper is the first one of the two papers entitled “modeling and solving mixed-model assembly line balancing problem with setups”, which has the aim of developing the mathematical programming formulation of the problem and solving it with a hybrid meta-heuristic approach. In this current part, a mixed-integer linear mathematical programming (MILP) model for mixed-model assembly line balancing problem with setups is developed. The proposed MILP model considers some particular features of the real world problems such as parallel workstations, zoning constraints, and sequence dependent setup times between tasks, which is an actual framework in assembly line balancing problems. The main endeavor of Part-I is to formulate the sequence dependent setup times between tasks in type-I mixed-model assembly line balancing problem. The proposed model considers the setups between the tasks of the same model and the setups because of the model switches in any workstation. The capability of our MILP is tested through a set of computational experiments. Part-II tackles the problem with a multiple colony hybrid bees algorithm. A set of computational experiments is also carried out for the proposed approach in Part-II.     

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.     

A simulated annealing algorithm based approach for balancing and sequencing of mixed-model U-lines

It is known that two interrelated problems called as line balancing and model sequencing should be solved simultaneously for an efficient implementation of a mixed-model U-shape assembly line in a JIT (Just in Time) environment. On the other hand, three versions of assembly line balancing problem can be identified: Type I, Type II, and Type E. There are only two articles ( Kara, Ozcan, & Peker, 2007a and Hamzadayi & Yildiz, 2012) related to simultaneous balancing and sequencing of mixed-model U-lines for minimizing the number of stations (Type 1 problem) by ignoring the fixed model sequence in the current literature. In this paper, a simulated annealing algorithm is proposed for solving a problem of type 1 by ignoring the fixed model sequence. Accordingly, simulated annealing based fitness evaluation approach proposed by Hamzadayi and Yildiz (2012) is enhanced by adding the tabu list, and inserted into the proposed algorithm. Implementation difficulties experienced in meta-heuristics based on solution modification for solving these types of problems are demonstrated. ‘Absolute deviation of workloads’ (ADW) is quite frequently used as performance criteria in the literature. It is found that ADW is an insufficient performance criterion for evaluating the performance of the solutions, and this is showed by means of an illustrative example. The parameters of the proposed algorithm are reviewed for calibrating the algorithm by means of Taguchi design of experiments. Performance of the proposed approach is tested through a set of test problems. The results of computational experiments indicate that the proposed approach is an effective method in solving simultaneous line balancing/model sequencing problems for mixed-model U-lines for minimizing the number of stations.     

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.     

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.     

混合装配线平衡排产协同优化新算法

装配线平衡和产品排序是紧密相关而且对目标值存在交互影响作用的两个NP—hard问题。文中基于这两个问题的交互影响以及贪婪随机自适应算法（GI己AsP）比较好的收敛速度和全局满意度,设计了协同优化贪婪随机自适应算法（（X）GRASP）,并行协同地优化混合装配线,并用实例对此算法进行了仿真研究。此外,文中还考虑了可能存在的瓶颈工序对协同优化效果的影响,将一种基于OPT思想的关键资源调度方法融入原来的COGRASP中,通过相应实例验证,取得的效果也非常好。     

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.     

A study on sequencing method for the mixed-model assembly line in just-in-time production systems

This paper deals with the problem of sequencing products on the mixed-model assembly line in a multi-level JIT production system. We consider both Goal(1) which levels the load at each station on the mixed-model assembly line, and Goal(2) which keeps a constant rate of production of every part in the preceding processes which are used on the mixed-model assembly line, together. We propose a mathematical model which determines the number of every product to be scheduled in each withdrawal position to realize making each withdrawal quantity of all the parts, with a fixed interval, as constant as possible. A sequencing method based on the solution stated above is given. Finally, an example is shown.     

Mixed-model assembly line balancing using a multi-objective ant colony optimization approach

Mixed-model assembly lines are production systems at which two or more models are assembled sequentially at the same line. For optimal productivity and efficiency, during the design of these lines, the work to be done at stations must be well balanced satisfying the constraints such as time, space and location. This paper deals with the mixed-model assembly line balancing problem (MALBP). The most common objective for this problem is to minimize the number of stations for a given cycle time. However, the problem of capacity utilization and the discrepancies among station times due to operation time variations are of design concerns together with the number of stations, the line efficiency and the smooth production. A multi-objective ant colony optimization (MOACO) algorithm is proposed here to solve this problem. To prove the efficiency of the proposed algorithm, a number of test problems are solved. The results show that the MOACO algorithm is an efficient and effective algorithm which gives better results than other methods compared.     

On solving the assembly line worker assignment and balancing problem via beam search

Certain types of manufacturing processes can be modelled by assembly line balancing problems. In this work we deal with a specific assembly line balancing problem that is known as the assembly line worker assignment and balancing problem (ALWABP). This problem appears in settings where tasks must be assigned to workers, and workers to work stations. Task processing times are worker specific, and workers might even be incompatible with certain tasks. The ALWABP was introduced to model assembly lines typical for sheltered work centers for the Disabled.     

An efficient multiobjective genetic algorithm for mixed-model assembly line balancing problem considering demand ratio-based cycle time

Mixed-model assembly lines (mALs) are becoming more and more important by producing different models of the same product on an assembly line. How to calculate the cycle time based on demand of different models also making problem more difficult. According to different work experiences and skill level, the processing time of a given task and the operating costs such as wages differ among workers. Appointing the proper worker to the proper station and assigning the suitable task to the suitable station in order to decrease the cycle time, increase the line efficiency, and reduce the total cost make the problem more complex. This paper proposes a new concept for calculating the cycle time based on demand ratio of each model and another one for calculating the human resource cost. A generalized Pareto-based scale-independent fitness function genetic algorithm (gp-siffGA) is described for solving mixed-model assembly lines balancing (mALB) problems to minimize the cycle time, the variation of workload and the total cost under the constraint of precedence relationships at the same time. The gp-siffGA uses Pareto dominance relationship to solve the problems without using relative preferences of multiple objectives. Comparisons with existing multiobjective genetic algorithms demonstrate that our approach efficiently solves mALB problems.     

A modified particle swarm optimization algorithm to mixed-model two-sided assembly line balancing

In this paper, a new modified particle swarm optimization algorithm with negative knowledge is proposed to solve the mixed-model two-sided assembly line balancing problem. The proposed approach includes new procedures such as generation procedure which is based on combined selection mechanism and decoding procedure. These new procedures enhance the solution capability of the algorithm while enabling it to search at different points of the solution space, efficiently. Performance of the proposed approach is tested on a set of test problem. The experimental results show that the proposed approach can be acquired distinguished results than the existing solution approaches.     

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.     

Balancing and scheduling of flexible mixed model assembly lines

Mixed model assembly line literature involves two problems: balancing and model sequencing. The general tendency in current studies is to deal with these problems in different time frames. However, in today’s competitive market, the mixed model assembly line balancing problem has been turned into an operational problem. In this paper, we propose mixed integer programming (MIP) and constraint programming (CP) models which consider both balancing and model sequencing within the same formulation along with the optimal schedule of tasks at a station. Furthermore, we also compare the proposed exact models with decomposition schemes developed for solving different instances of varying sizes. This is the first paper in the literature which takes into account the network type precedence diagrams and limited buffer capacities between stations. Besides, it is the first study that CP method is applied to balancing and scheduling of mixed model assembly lines. Our empirical study shows that the CP approach outperforms the MIP approach as well as the decomposition schemes.     

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.     

Utilizing variant differentiation to mitigate manufacturing complexity in mixed-model assembly systems

A measure of product variety induced complexity has been proposed for mixed-model assembly systems with serial, parallel and hybrid configurations. The complexity model was built based on the assumption of identical parallel stations, i.e., same product variants are produced at all parallel stations in the same volume and with the same mix ratio. In this paper, the existing complexity model is extended to general mixed-model assembly systems with non-identical parallel stations in the presence of product variety. Then it is discussed that how to reduce the system complexity using the variant differentiation, based on which a mathematical formulation is developed to minimize the complexity of a mixed-model assembly system. The formulated problem is a non-linear programming problem and then solved by genetic algorithm. Last the developed complexity mitigation model is applied to the configuration selection of assembly systems, i.e., to identify the system configuration with the minimum complexity.     

Fuzzy activity time-based model predictive control of open-station assembly lines

The sequencing and line balancing of manual mixed-model assembly lines are challenging tasks due to the complexity and uncertainty of operator activities. The control of cycle time and the sequencing of production can mitigate the losses due to non-optimal line balancing in the case of open-station production where the operators can work ahead of schedule and try to reduce their backlog. The objective of this paper is to provide a cycle time control algorithm that can improve the efficiency of assembly lines in such situations based on a specially mixed sequencing strategy. To handle the uncertainty of activity times, a fuzzy model-based solution has been developed. As the production process is modular, the fuzzy sets represent the uncertainty of the elementary activity times related to the processing of the modules. The optimistic and pessimistic estimates of the completion of activity times extracted from the fuzzy model are incorporated into a model predictive control algorithm to ensure the constrained optimization of the cycle time. The applicability of the proposed method is demonstrated based on a wire-harness manufacturing process with a paced conveyor, but the proposed algorithm can handle continuous conveyors as well. The results confirm that the application of the proposed algorithm is widely applicable in cases where a production line of a supply chain is not well balanced and the activity times are uncertain.     

多目标粒子群算法在混装线再平衡中的应用

企业对产品进行创新改进,带来装配线上装配任务的变化,从而造成已平衡装配线的失衡。针对上述变化给企业混流装配线带来的影响进行了研究,以最小化生产节拍,工作站间的负荷,和工人完成新装配任务的调整成本为优化目标去建立混装线再平衡的数学模型。并设计了一种新的多目标粒子群算法求解模型,算法中引入各粒子动态密集距离去筛选外部文档的非劣解和指导全局最优值的更新,在控制解的容量同时保持Pareto解集分布均匀。此外,引入变异机制,提高了种群的全局搜索能力。最后,结合具体实例的验证表明,该改进多目标粒子群算法能有效地解决混装线再平衡问题。     

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.