A priority rule-based constructive heuristic and an improvement method for balancing assembly lines with parallel multi-manned workstations

Assembly lines of big-size products such as buses, trucks and helicopters are very different from the lines studied in the literature. These products’ manufacturing processes have a lot of tasks most of which have long task times. Since traditional assembly line models including only one worker in each station (i.e. simple assembly lines) or at most two workers (two-sided assembly lines) may not be suitable for manufacturing these type of products, they need much larger shop floor for a number of stations and long product flow times. In this study, an assembly line balancing problem (ALBP) with parallel multi-manned stations is considered. Following the problem definition, a mixed integer programming formulation is developed. A detailed study of priority rules for simple ALBPs is also presented, and a new efficient constructive heuristic algorithm based on priority rules is proposed. In order to improve solutions found by the constructive heuristic, a genetic algorithm-based solution procedure is also presented. Benchmark instances in the literature are solved by using the proposed mathematical programming formulation. It has been seen that only some of the small-size instances can be solved optimally by this way. So the efficiency of the proposed heuristic method is verified in small-size instances whose optimal solutions are found. For medium- and big-size instances, heuristics’ results and CPU times are demonstrated. A comparative evaluation with a branch and bound algorithm that can be found in the literature is also carried out, and results are presented.     

Simulated annealing algorithms for the multi-manned assembly line balancing problem: minimising cycle time

Multi-manned assembly lines are often designed to produce big-sized products, such as automobiles and trucks. In this type of production lines, there are multi-manned workstations where a group of workers simultaneously performs different operations on the same individual product. One of the problems, that managers of such production lines usually encounter, is to produce the optimal number of items using a fixed number of workstations, without adding new ones. In this paper, such a class of problems, namely, the multi-manned assembly line balancing problem is addressed, with the objective of minimising the cycle time. A mixed-integer mathematical programming formulation is proposed for the considered problem. This model has the primary objective of minimising the cycle time for a given number of workstations and the secondary objective of minimising the total number of workers. Since the addressed problem is NP-hard, two meta-heuristic approaches based on the simulated annealing algorithm have been developed: ISA and DSA. ISA solves the problem indirectly while DSA solves it directly. The performance of the two algorithms are tested and compared on a set of test problems taken from the literature. The results show that DSA outperforms ISA in term of solution quality and computational time.     

Disassembly line design with multi-manned workstations: a novel heuristic optimisation approach

As the first and the most time consuming step of product recovery, disassembly is described as the systematic separation of constituent parts from end-of-life products through a series of operations. In this context, designing and balancing disassembly lines are critical in terms of the efficiency of product recovery. Recent research on disassembly line balancing (DLB) has focused on classical stations where only one worker is allocated. However, such a line results in larger space requirement and longer disassembly lead time. In this paper, disassembly line balancing problem (DLBP) with multi-manned stations is introduced to the relevant literature as a solution to overcome these disadvantages. A mixed integer linear programming (MILP) model and two novel framework heuristic algorithms are developed to minimise the number of workers and workstations. MILP model has been applied to a dishwasher disassembly system. The application results indicate the superiority of establishing multi-manned stations over classical disassembly system design with single-worker stations with shorter disassembly lead time (80.9%) and line length (60.2%). Moreover, the proposed heuristics have been compared on newly generated test problems (instances) for DLBP. The results validate that the heuristics provide acceptable solutions in a reasonable amount of time even for large-sized problems.     

Using response surface design to determine the optimal parameters of genetic algorithm and a case study

Genetic algorithms (GAs) are efficient stochastic search techniques for approximating optimal solutions within complex search spaces and used widely to solve NP-hard problems. Genetic algorithm includes a number of parameters whose different levels strictly affect the performance of the algorithm. The general approach to determine the appropriate parameter combination of GA depends on too many trials of different combinations, and the best one of them that produces good results is selected for the programme, which would be used for problem solving. A few researchers studied on the parameter optimisation of GA. In this paper, response surface-dependent parameter optimisation is proposed to determine the optimal parameters of GA. Results are tested for benchmark problems that are most common in mixed-model assembly line balancing problems of type-I.     

Simultaneous balancing and sequencing of mixed-model parallel two-sided assembly lines

Growing interests from customers in customised products and increasing competitions among peers necessitate companies to configure their manufacturing systems more effectively than ever before. We propose a new assembly line system configuration for companies that need intelligent solutions to satisfy customised demands on time with existing resources. A mixed-model parallel two-sided assembly line system is introduced based on the parallel two-sided assembly line system previously proposed in the literature. The mixed-model parallel two-sided assembly line balancing problem is illustrated with examples from the perspective of simultaneous balancing and sequencing. An agent-based ant colony optimisation algorithm is proposed to solve the problem. This algorithm is the first attempt in the literature to solve an assembly line balancing problem with an agent-based ant colony optimisation approach. The algorithm is illustrated with an example and its operational procedures and principles are explained and discussed.     

Worker allocation in lean U-shaped production lines

U-shaped lines are widely used in lean systems. In U-shaped production lines, each worker handles one or more machines on the line: the worker allocation problem is to establish which machines are handled by which worker. This differs from the widely-investigated U-line assembly line balancing problem in that the assignment of tasks to line locations is fixed. This paper address the worker allocation problem for lean U-shaped production lines where the objectives are to minimize the quantity of workers and maximize full work: such allocations provide the opportunity to eliminate the least-utilized worker by improving processes accordingly. A mathematical model is developed: the model allows for any allocation of machines to workers so long as workers do not cross paths. Walking times are considered, where workers follow circular paths and walk around other worker(s) on the line if necessary. A heuristic algorithm for tackling the problem is developed, along with a procedure representing the ‘traditional’ approach of constructing standard operations routines. Computational experiments considering three line sizes (up to 20 machines) and three takt time levels are performed. The results show that the proposed algorithm both improves upon the traditional approach and is more likely to provide optimal solutions.     

A Pareto firefly algorithm for multi-objective disassembly line balancing problems with hazard evaluation

The safety hazards existing in the process of disassembling waste products pose potential harms to the physical and mental health of the workers. In this article, these hazards involved in the disassembly operations are evaluated and taken into consideration in a disassembly line balancing problem. A multi-objective mathematical model is constructed to minimise the number of workstations, maximise the smoothing rate and minimise the average maximum hazard involved in the disassembly line. Subsequently, a Pareto firefly algorithm is proposed to solve the problem. The random key encoding method based on the smallest position rule is used to adapt the firefly algorithm to tackle the discrete optimisation problem of the disassembly line balancing. To avoid the search being trapped in a local optimum, a random perturbation strategy based on a swap operation is performed on the non-inferior solutions. The validity of the proposed algorithm is tested by comparing with two other algorithms in the existing literature using a 25-task phone disassembly case. Finally, the proposed algorithm is applied to solve a refrigerator disassembly line problem based on the field investigation and a comparison of the proposed Pareto firefly algorithm with another multi-objective firefly algorithm in the existing literature is performed to further identify the superior performance of the proposed Pareto firefly algorithm, and eight Pareto optimal solutions are obtained for decision makers to make a decision.     

Analysis of the type II robotic mixed-model assembly line balancing problem

In recent years, there has been an increasing trend towards using robots in production systems. Robots are used in different areas such as packaging, transportation, loading/unloading and especially assembly lines. One important step in taking advantage of robots on the assembly line is considering them while balancing the line. On the other hand, market conditions have increased the importance of mixed-model assembly lines. Therefore, in this article, the robotic mixed-model assembly line balancing problem is studied. The aim of this study is to develop a new efficient heuristic algorithm based on beam search in order to minimize the sum of cycle times over all models. In addition, mathematical models of the problem are presented for comparison. The proposed heuristic is tested on benchmark problems and compared with the optimal solutions. The results show that the algorithm is very competitive and is a promising tool for further research.     

Multi-objective evolutionary simulated annealing optimisation for mixed-model multi-robotic disassembly line balancing with interval processing time

This paper considers the design and balancing of mixed-model disassembly lines with multi-robotic workstations under uncertainty. Tasks of different models are performed simultaneously by the robots which have different capacities for disassembly. The robots have unidentical task times and energy consumption respectively. Task precedence diagrams are used to model the precedence relations among tasks. Considering uncertainties in disassembly process, the task processing times are assumed to be interval numbers. A mixed-integer mathematical programming model is proposed to minimise the cycle time, peak workstation energy consumption, and total energy consumption. This model has a significant managerial implication in real-life disassembly line systems. Since the studied problem is known as NP-hard, a metaheuristic approach based on an evolutionary simulated annealing algorithm is developed. Computational experiments are conducted and the results demonstrate the proposed algorithm outperforms other multi-objective algorithms on optimisation quality and computational efficiency.     

Balancing manual mixed-model assembly lines using overtime work in a demand variation environment

This study deals with the balancing problem of a manual mixed-model assembly line, where the production volume or the product mix changes from shift to shift during the planning horizon. The unstable demand can be characterised by several representative scenarios, and the line uses overtime work to meet the demand variation. The balancing problem concerns how to assign assembly tasks to stations and determine the amount of overtime in each possible demand scenario. The objective is to satisfy the demand in each possible scenario with the minimum labour costs paid for both normal shifts and overtime work. A lower bound on the labour costs is proposed, and a heuristic algorithm is developed to quickly find a feasible solution. A branch, bound and remember (BB&;R) algorithm is then proposed to find better solutions. These solution methods are tested on 765 instances. The BB&;R algorithm obtains optimal solutions for 510 instances and gives high-quality solutions for the remaining 255 instances within 60?s. The experimental results show that the use of overtime work and adjustable cycle times significantly reduces the labour costs, especially when the demand or task processing time variations are large.     

Design of stochastic assembly lines considering line balancing and part feeding with supermarkets

This article aims to address the assembly line balancing problem (ALBP) and supermarket location problem (SLP) as two long-term interrelated decision problems considering the stochastic nature of the task times and demands. These problems arise in real-world assembly lines during the strategic decision-making phase of configuring new assembly lines from both line balancing and part-feeding (PF) aspects. A hierarchical mathematical programming model is developed, in which the first level resolves the stochastic ALBP by minimizing the workstation numbers and the second level deals with the stochastic SLP while optimizing the PF shipment, inventory and installation costs. The results of case data from an automotive parts manufacturer and a set of standard test problems verified that the proposed model can optimize the configuration of assembly lines considering both ALBP and SLP performance measures. This study also validates the effect of the stochastic ALBP on the resulting SLP solutions.     

Ant colony optimisation with parameterised search space for the job shop scheduling problem

The job-shop scheduling problem (JSSP) is known to be NP-hard. Due to its complexity, many metaheuristic algorithm approaches have arisen. Ant colony metaheuristic algorithm, lately proposed, has successful application to various combinatorial optimisation problems. In this study, an ant colony optimisation algorithm with parameterised search space is developed for JSSP with an objective of minimising makespan. The problem is modelled as a disjunctive graph where arcs connect only pairs of operations related rather than all operations are connected in pairs to mitigate the increase of the spatial complexity. The proposed algorithm is compared with a multiple colony ant algorithm using 20 benchmark problems. The results show that the proposed algorithm is very accurate by generating 12 optimal solutions out of 20 benchmark problems, and mean relative errors of the proposed and the multiple colony ant algorithms to the optimal solutions are 0.93% and 1.24%, respectively.     

Two-sided U-type assembly line balancing problem

U-type and two-sided assembly lines are two types of design having advantages over traditional straight assembly lines. In this paper, a new line design hybrid of U-type and two-sided lines is presented. A bi-objective 0-1 integer programming model is developed to solve the line balancing problem of the proposed design. Zoning constraints are also considered for the proposed design. A number of test problems from the literature with up to 65 tasks are solved. Benefits of two-sided U-type lines are discussed.     

求解考虑顺序相关调整时间的双边装配线平衡问题的变邻域搜索算法

为有效解决带有顺序相关调整时间的双边装配线平衡问题,提出了一种简单高效的变邻域搜索算法。该算法通过将优先关系约束融入到交换、插入、交叉、变异等算子中,分别得到4个不同的邻域结构来保证搜索过程中解的可行性,避免过多重复邻域解的生成。4个邻域结构的搜索空间依次变大,以增强算法搜索能力。同时,结合装配线的特点,提出基于作业序列的编码和解码方式,在解码过程中,优先选择空闲时间较多的边,引入启发式目标加快算法收敛。分配结束后,对装配线末端的工作站组进行局部调整。通过将该算法先后用于求解无/有顺序相关调整时间的双边装配线平衡第一类问题,并与已有的算法进行对比,验证了所提的变邻域搜索算法的优越性和有效性。     

A cross-entropy approach to the single row facility layout problem

The single row facility layout problem is to arrange a given number of facilities along a straight line so as to minimise the total cost associated with the interactions between the facilities. In this paper, a metaheuristic algorithm based on the cross-entropy method, incorporating a local search procedure and symmetry-breaking techniques, is developed to solve this problem. The proposed algorithm has been tested on some widely used benchmark instances. The computational results show that the proposed algorithm has found the optimal or the best solutions known so far for the instances of size with up to 100 facilities and is competitive with some existing algorithms.     

Profit-oriented disassembly-line balancing

As product and material recovery has gained importance, disassembly volumes have increased, justifying construction of disassembly lines similar to assembly lines. Recent research on disassembly lines has focused on complete disassembly. Unlike assembly, the current industry practice involves partial disassembly with profit-maximization or cost-minimization objectives. Another difference between assembly and disassembly is that disassembly involves additional precedence relations among tasks due to processing alternatives or physical restrictions. In this study, we define and solve the profit-oriented partial disassembly-line balancing problem. We first characterize different types of precedence relations in disassembly and propose a new representation scheme that encompasses all these types. We then develop the first mixed integer programming formulation for the partial disassembly-line balancing problem, which simultaneously determines (1) the parts whose demand is to be fulfilled to generate revenue, (2) the tasks that will release the selected parts under task and station costs, (3) the number of stations that will be opened, (4) the cycle time, and (5) the balance of the disassembly line, i.e. the feasible assignment of selected tasks to stations such that various types of precedence relations are satisfied. We propose a lower- and upper-bounding scheme based on linear programming relaxation of the formulation. Computational results show that our approach provides near optimal solutions for small problems and is capable of solving larger problems with up to 320 disassembly tasks in reasonable time.     

Balancing mixed-model assembly lines to reduce work overload

We propose a new line balancing approach for mixed-model assembly lines with an emphasis on how the assignment of tasks to stations affects the ability to construct daily sequences of jobs (customer orders) that provide stable workloads (in a minute-to-minute sense) on the assembly line, while also achieving reasonable workload balance among the stations. The issue of short-term workload stability has received little attention in the assembly line balancing literature. Such stability allows assembly workers to complete their tasks without being rushed and thereby contributes to product quality. We propose a new objective for assembly line balancing that helps to achieve better short-term workload stability and develop a heuristic solution procedure based on filtered beam search for this new objective. Computational results show that for small problems (which can be solved optimally), this approach provides near optimal solutions, and for larger problems, it provides significantly better results than traditional assembly line balancing methods.     

Reverse supply chain optimisation with disassembly line balancing

Due to responding environmental issues, conforming governmental legislations and providing economic benefits, there has been a growing interest in recycling activities through the supply chains. Reverse supply chain (RSC) optimisation problem has a great potential as an efficient tactic to achieve this goal. While disassembly, one of the main activities in RSC, enables reuse and recycling of products and prevents the overuse, disassembly line balancing problem involves determination of a line design in which used products are partially/completely disassembled to obtain available components. The aim of this study is to optimise a RSC, involving customers, collection/disassembly centres and plants, that minimises the transportation costs while balancing the disassembly lines, which minimises the total fixed costs of opened workstations, simultaneously. A non-linear mixed-integer programming model, which simultaneously determines: (i) optimal distribution between the facilities with minimum cost, (ii) the number of disassembly workstations that will be opened with minimum cost, (iii) the cycle time in each disassembly centre and (iv) optimal assignment of tasks to workstations, is developed. A numerical example is given to illustrate the applicability of the proposed model. Different scenarios have been conducted to show the effects of sensitivity analyses on the performance measures of the problem.     

Balancing and sequencing of stochastic mixed-model assembly U-lines to minimise the expectation of work overload time

A mixed-model assembly U-line is a flexible production system capable of manufacturing a variety of similar models, and it has become popular as an important component of the just-in-time production system. However, it poses new challenges for the optimal design of assembly lines because both the task assignment and the production sequence affect the workload variance among workstations. As a consequence, this paper addresses the line balancing problem and the model sequencing problem jointly and proposes a 0–1 stochastic programming model. In this model, task times are assumed to be stochastic variables independently distributed with normal distributions and the objective is to minimise the expectation of work overload time for a given combination of cycle time and number of workstations. To solve the problem, a simulated annealing-based algorithm is developed, which can also be used to minimise the absolute deviation of workloads in a deterministic environment. The experimental results for a set of benchmark problems show that the proposed algorithm outperforms the existing algorithms in terms of solution quality and running time.     

Balancing transfer lines using Benders decomposition and ant colony optimisation techniques

In this paper, we investigate a transfer line balancing problem in order to find the line configuration that minimises the non-productive time. The problem is defined at an auto manufacturing company where the cylinder head is manufactured. Technological restrictions among design features and manufacturing operations are taken into consideration. The problem is represented by an integer programming model that assigns design features and cutting tools to machining stations, and specifies the number of machines and production sequence in each station. Three algorithms are developed to efficiently solve the problem under study. The first algorithm uses Benders decomposition approach that decomposes the proposed model into an assignment problem and a sequencing problem. The second algorithm is a hybrid algorithm that mixes Benders decomposition approach with the ant colony optimisation technique. The third algorithm solves the problem using two nested ant colonies. Using 15 different problem dimensions, we compare results of the three algorithms in a computational study. The first algorithm finds optimal solutions of small problem instances only. Second and third algorithms demonstrate optimality gaps less than 4.04 and 3.8%, respectively, when compared to the optimal results given by the first algorithm. Moreover, the second and third algorithms are very promising in solving medium and large-scale problem instances.