Shortest-route formulation of mixed-model assembly line balancing problem

A shortest-route formulation of the mixed-model assembly line balancing problem is presented. Common tasks across models are assumed to exist and these tasks are performed in the same stations. The formulation is based on an algorithm which solves the single-model version of the problem. The mixed-model system is transformed into a single-model system with a combined precedence diagram. The model is capable of considering any constraint that can be expressed as a function of task assignments.     

A survey on problems and methods in generalized assembly line balancing

Assembly lines are traditional and still attractive means of mass and large-scale series production. Since the early times of Henry Ford several developments took place which changed assembly lines from strictly paced and straight single-model lines to more flexible systems including, among others, lines with parallel work stations or tasks, customer-oriented mixed-model and multi-model lines, U-shaped lines as well as unpaced lines with intermediate buffers.In any case, an important decision problem, called assembly line balancing problem, arises and has to be solved when (re-) configuring an assembly line. It consists of distributing the total workload for manufacturing any unit of the product to be assembled among the work stations along the line.Assembly line balancing research has traditionally focused on the simple assembly line balancing problem (SALBP) which has some restricting assumptions. Recently, a lot of research work has been done in order to describe and solve more realistic generalized problems (GALBP). In this paper, we survey the developments in GALBP research.     

On a learning precedence graph concept for the automotive industry

Assembly line balancing problems (ALBP) consist in assigning the total workload for manufacturing a product to stations of an assembly line as typically applied in automotive industry. The assignment of tasks to stations is due to restrictions which can be expressed in a precedence graph. However, (automotive) manufacturers usually do not have sufficient information on their precedence graphs. As a consequence, the elaborate solution procedures for different versions of ALBP developed by more than 50 years of intensive research are often not applicable in practice.Unfortunately, the known approaches for precedence graph generation are not suitable for the conditions in the automotive industry. Therefore, we describe a new graph generation approach that is based on learning from past feasible production sequences and forms a sufficient precedence graph that guarantees feasible line balances. Computational experiments indicate that the proposed procedure is able to approximate the real precedence graph sufficiently well to detect optimal or nearly optimal solutions for a well-known benchmark data set. Even for additional large instances with up to 1,000 tasks, considerable improvements of line balances are possible. Thus, the new approach seems to be a major step to close the gap between theoretical line balancing research and practice of assembly line planning.     

A two-process implicit enumeration algorithm for the simple assembly line balancing problem

We present an implicit-enumeration algorithm for the simple assembly line balancing problem, with the objective of minimizing the number of stations along the line for a fixed cycle time. The algorithm traverses two branch-and-bound trees, one assigning tasks that appear earlier in the precedence network at lower levels of the tree, the other assigning later tasks at lower levels. The two processes alternately expand nodes of their respective trees, and share information about each other's progress in the form of global bounds. Computational results are reported on several well-known problems from the literature.     

Balancing U-lines in a multiple U-line facility

U-shaped production lines and facilities consisting of many such lines are important parts of modem manufacturing systems. The problem of balancing and rebalancing U-line facilities is studied in this paper. Like the traditional line balancing problem this problem is NP-hard. The objective is to assign tasks to a minimum number of regular, crossover, and multiline stations while satisfying cycle time, precedence, location, and station-type constraints. A secondary objective is to concentrate the idle time in one station so that improvement efforts can be focused there in accordance with modern just-in-time principles. A reaching dynamic programming algorithm is presented for determining optimal balances. It is effective for balancing and rebalancing facilities with any number of U-lines, provided that individual U-lines do not have more than 22 tasks and do not have wide, sparse precedence graphs.     

Simple assembly line balancing—Heuristic approaches

In this paper heuristics for Type 1 and Type 2 of the Simple Assembly Line Balancing Problem (SALBP) are described. Type 1 of SALBP (SALBP-1) consists of assigning tasks to work stations such that the number of stations is minimized for a given production rate whereas Type 2 (SALBP-2) is to maximize the production rate, or equivalently, to minimize the sum of idle times for a given number of stations. In both problem types, precedence constraints between the tasks have to be considered.We describe bidirectional and dynamic extensions to heuristic priority rules widely used for SALBP-1. For the solution of SALBP-2 we present search methods which involve the repetitive application of procedures for SALBP-1. Furthermore, improvement procedures for SALBP-2 are developed and combined with tabu search, a recent strategy to overcome local optimality. Several optional elements of tabu search are discussed. Finally, the application of a nontraditional tabu search approach to solve SALBP-1 is investigated. Computational experiments validate the effectiveness of our new approaches.     

Heuristics and lower bounds for the simple assembly line balancing problem type 1: Overview,computational tests and improvements

Assigning tasks to work stations is an essential problem which needs to be addressed in an assembly line design. The most basic model is called simple assembly line balancing problem type 1 (SALBP-1). We provide a survey on 12 heuristics and 9 lower bounds for this model and test them on a traditional and a lately-published benchmark dataset. The present paper focuses on algorithms published before 2011.     

A new diversity induction mechanism for a multi-objective ant colony algorithm to solve a real-world time and space assembly line balancing problem

Time and space assembly line balancing considers realistic multi-objective versions of the classical assembly line balancing industrial problems. It involves the joint optimisation of conflicting criteria such as the cycle time, the number of stations, and/or the area of these stations. The different problems included in this area also inherit the precedence constraints and the cycle time limitations from assembly line balancing problems. The presence of these hard constraints and their multi-criteria nature make these problems very hard to solve. Multi-objective constructive metaheuristics (in particular, multi-objective ant colony optimisation) have demonstrated to be suitable approaches to solve time and space assembly line balancing problems. The aim of this contribution is to present a new mechanism to induce diversity in an existing multi-objective ant colony optimisation algorithm for the 1/3 variant of the time and space assembly line balancing problem. This variant is quite realistic in the automative industry as it involves the joint minimisation of the number and the area of the stations given a fixed cycle time limit. The performance of our proposal is validated considering ten real-like problem instances. Moreover, the diversity induction mechanism is also tested on a real-world instance from the Nissan plant in Barcelona (Spain).     

Multiple-source learning precedence graph concept for the automotive industry

In modern production systems, customized mass production of complex products, such as automotive or white goods, is often realized at assembly lines with a high degree of manual labor. For firms that apply assembly systems, the assembly line balancing problem (ALBP) arises, which is to assign optimally tasks to stations or workers with respect to some constraints and objectives. Although the literature provides a number of relevant models and efficient solution methods for ALBP, firms, in most cases, do not use this knowledge to balance their lines. Instead, the planning is mostly performed manually by numerous planners responsible for small sub-problems. This is because of the lack of data, like the precedence relations between the tasks to be performed. Such data is hard to collect and to maintain updated.     

Scenario based robust line balancing: Computational complexity

This paper studies the following line balancing problem with uncertain operation execution times. Operations on the same product have to be assigned to the stations of a transfer line. The product moves along the stations in the same direction, and operations assigned to the same station are executed sequentially. Exclusion, inclusion and precedence relations are given on the set of operations. Operation execution times are uncertain in the sense that their set belongs to a given set of scenarios. The objective is to minimize the line cycle time, which is equal to the maximum total execution time of operations of the same station, for the worst scenario. An approach to reducing the scenario set is described. Several special cases of the problem are proved NP-hard and strongly NP-hard. Enumerative dynamic programming algorithms and problem-specific polynomial time algorithms are suggested for some cases.     

Balancing assembly lines with variable parallel workplaces: Problem definition and effective solution procedure

Assembly line balancing problems (ALBP) arise whenever an assembly line is configured, redesigned or adjusted. An ALBP consists of distributing the total workload for manufacturing any unit of the products to be assembled among the work stations along the line subject to a strict or average cycle time. Traditionally, stations are considered to be manned by one operator, respectively, or duplicated in form of identical parallel stations, each also manned by a single operator. In practice, this assumption is usually too restrictive. This is particularly true for large products like cars, trucks, busses and machines, which can be handled by several operators performing different tasks at the same time. Only restricted research has been done on such parallel workplaces within the same station though they have significant relevance in real-world assembly line settings.     

Monolithic vs. hierarchical balancing and scheduling of a flexible assembly line

A monolithic and a hierarchical approach are presented for balancing and scheduling of a flexible assembly line (FAL). The system is made up of a set of assembly stations in series, each with limited work space and is capable of simultaneously producing a mix of product types. The objective is to determine an assignment of assembly tasks to stations and an assembly schedule for all products so as to complete the products in minimum time. In the monolithic approach balancing and scheduling decisions are made simultaneously. In the hierarchical approach, however, first the station workloads are balanced, and then detailed assembly schedule is determined for prefixed task assignments and assembly routes by solving a permutation flowshop problem. Mixed integer programming formulations are presented for the two approaches. Numerical examples are included to illustrate and compare the approaches and some computational results are reported.     

混合型装配线平衡问题求解方法研究

对混合型装配线平衡问题进行了描述和数学建模,提出一种启发式求解算法,求解目标是最小化工作站数目.为进一步优化求解结果,对启发式算法求解的结果进行仿真研究,分析各工作站的工作率、等待率和阻塞率,并以此为依据调整部分作业任务的分配,允许不同品种产品的相同作业任务安排在不同的工作站中,以对求解结果进行修正,进一步均衡各工作站的作业量.该求解方法既简化了求解过程,又兼顾到了系统的瞬时特性和作业任务的不可拆分性对求解结果的影响,实例分析验证了方法的有效性.     

A heuristic solution for fuzzy mixed-model line balancing problem

This paper addresses the mixed-model line balancing problem with fuzzy processing time. A fuzzy binary linear programming model is formulated for the problem. This fuzzy model is then transformed to a mixed zero–one program. Due to the complexity nature in handling fuzzy computation, new approximated fuzzy arithmetic operation is presented. A fuzzy heuristic is developed to solve this problem based on the aggregating fuzzy numbers and combined precedence constraints. The general idea of our approach is to arrange the jobs in a sequence by a varying-section exchange procedure. Then jobs are allocated into workstations based on these aggregated fuzzy times with the considerations of technological constraint and cycle time limit. Promising results are obtained by experiments.     

A versatile algorithm for assembly line balancing

This paper discusses a two stage graph-algorithm, which was designed to solve line balancing problems including practice relevant constraints (GALBP), such as parallel work stations and tasks, cost synergies, processing alternatives, zoning restrictions, stochastic processing times or U-shaped assembly lines. Unlike former procedures, the presented approach can be easily modified to incorporate all of the named extensions. It is not only possible to select and solve single classes of constraints, but rather any combination of them with just slight modifications.     

An efficient grouping genetic algorithm for U-shaped assembly line balancing problems with maximizing production rate

U-type assembly line is one of the important tools that may increase companies’ production efficiency. In this study, two different modeling approaches proposed for the assembly line balancing problems have been used in modeling type-II U-line balancing problems, and the performances of these models have been compared with each other. It has been shown that using mathematical formulations to solve medium and large size problem instances is impractical since the problem is NP-hard. Therefore, a grouping genetic and simulated annealing algorithms have been developed, and a particle swarm optimization algorithm is adapted to compare with the proposed methods. A special crossover operator that always obtains feasible offspring has been suggested for the proposed grouping genetic algorithm. Furthermore, a local search procedure based on problem-specific knowledge was applied to increase the intensification of the algorithm. A set of well-known benchmark instances was solved to evaluate the effectiveness of the proposed and existing methods. Results showed that while the mathematical formulations can only be used to solve small size instances, metaheuristics can obtain high quality solutions for all size problem instances within acceptable CPU times. Moreover, grouping genetic algorithm has been found to be superior to the other methods according to the number of optimal solutions, or deviations from the lower bound values.     

Dynamic task assignment for throughput maximization with worksharing

The traditional assembly line balancing problem involves assigning a set of partially precedence constrained tasks to workstations to maximize efficiency. Each task is assigned to a unique workstation. The case is considered where task sequences are known but the workforce is partially cross-trained and some tasks can alternate between workstations. The flexibility afforded by cross-training allows the line balance to improve. Task times are allowed to be random and small buffers are allowed between workstations. Decision rules are developed and tested for various levels of cross-training between adjacent workers. Cross-training is shown to have significant impact on throughput and easy to administer rules are proven to be effective. The number of decision points for deciding to hold or pass a unit of product is also shown to be important.     

Simple heuristics for the assembly line worker assignment and balancing problem

We propose simple heuristics for the assembly line worker assignment and balancing problem. This problem typically occurs in assembly lines in sheltered work centers for the disabled. Different from the well-known simple assembly line balancing problem, the task execution times vary according to the assigned worker. We develop a constructive heuristic framework based on task and worker priority rules defining the order in which the tasks and workers should be assigned to the workstations. We present a number of such rules and compare their performance across three possible uses: as a stand-alone method, as an initial solution generator for meta-heuristics, and as a decoder for a hybrid genetic algorithm. Our results show that the heuristics are fast, they obtain good results as a stand-alone method and are efficient when used as a initial solution generator or as a solution decoder within more elaborate approaches.     

Robust balancing of straight assembly lines with interval task times

This paper addresses the balancing problem for straight assembly lines where task times are not known exactly but given by intervals of their possible values. The objective is to assign the tasks to workstations minimizing the number of workstations while respecting precedence and cycle-time constraints. An adaptable robust optimization model is proposed to hedge against the worst-case scenario for task times. To find the optimal solution(s), a breadth-first search procedure is developed and evaluated on benchmark instances. The results obtained are analysed and some practical recommendations are given.     

A station-oriented enumerative algorithm for two-sided assembly line balancing

In this paper, a station-oriented enumerative algorithm for two-sided assembly lines balancing (TALB) is proposed. First, the time transfer function is defined and combined with the precedence relation to compute the earliest and the latest start time of tasks. With the direction and cycle time constraints, a station-oriented procedure based on the start time is designed to assign tasks, starting from the left station to the rightstation of the position. Some unsuitable position assignments would be finally removed by checking the precedence constraints among the assigned tasks. The proposed algorithm is integrated with the Hoffmann heuristic to develop a system for solving TALB problems. The test is performed on the well-known benchmark set of problem instances. Experimental results demonstrate that the proposed procedure is efficient.