Multi-plant assembly planning models for a collaborative manufacturing environment

In a global supply chain, the components or parts of a product may be distributed and produced at various plants in a collaborative way for the purpose of expanding capacity and reducing costs. For an assembled product, the assembly operations for assembling the product may be performed at different assembly plants at various geographical locations. Therefore, in this collaborative manufacturing environment, it is required that one develops a multi-plant assembly planning model for organizing and distributing the assembly operations to the suitable plants for completing the final product. In this research, a multi-plant assembly planning model for generating and evaluating the multi-plant assembly sequences is presented. New graph-based models are developed to model and generate the assembly sequences. The feasible assembly sequences are analysed and evaluated based on several cost objectives. The multi-plant assembly planning model is formulated with the aim of minimizing the total of assembly costs and multi-plant costs. As a result, the optimized multi-plant assembly sequences can be obtained and each of the assembly operations is assigned to the suitable plant with a minimized cost. Example parts are tested and discussed.     

Robotic disassembly sequence planning using enhanced discrete bees algorithm in remanufacturing

Increasing attention is being paid to remanufacturing due to environmental protection and resource saving. Disassembly, as an essential step of remanufacturing, is always manually finished which is time-consuming while robotic disassembly can improve disassembly efficiency. Before the execution of disassembly, generating optimal disassembly sequence plays a vital role in improving disassembly efficiency. In this paper, to minimise the total disassembly time, an enhanced discrete Bees algorithm (EDBA) is proposed to solve robotic disassembly sequence planning (RDSP) problem. Firstly, the modified feasible solution generation (MFSG) method is used to build the disassembly model. After that, the evaluation criterions for RDSP are proposed to describe the total disassembly time of a disassembly sequence. Then, with the help of mutation operator, EDBA is proposed to determine the optimal disassembly sequence of RDSP. Finally, case studies based on two gear pumps are used to verify the effectiveness of the proposed method. The performance of EDBA is analysed under different parameters and compared with existing optimisation algorithms used in disassembly sequence planning (DSP). The result shows the proposed method is more suitable for robotic disassembly than the traditional method and EDBA generates better quality of solutions compared with the other optimisation algorithms.     

拆卸序列规划中子装配体的识别与生成

子装配体识别是解决大规模拆卸序列规划"组合爆炸"问题的有效方法之一.为了准确有效地识别与生成子装配体,在装配体零部件间接触关系、联接关系和向位妨碍关系及其相应图模型、矩阵的基础上,提出了一种基于图模型和判断矩阵的拆卸序列规划子装配体的识别算法.该算法利用图模型对子装配体集合做加法,利用判断矩阵对子装配体集合做减法,首先依据子装配体识别准则对图模型检索生成潜在子装配体集合,然后依据矩阵判断公式从集合中排除不符合连续性原则、稳定性原则和可行性原则的子装配体,并筛选理想个数的符合重量标准、同质标准和价值标准的最终子装配体集合.以减速器实例验证方法的可行性和有效性.     

Applying case-based reasoning in assembly sequence planning

Assembly sequence planning (ASP) is the foundation of the assembly process planning which plays a key role in the whole product life cycle. In this paper, a unique ASP reasoning method supported by the artificial intelligent technique of case-based reasoning (CBR) is proposed and developed. First, based on the previous ASP literatures review and the CBR characteristics analysis, the systematic architecture of the CBR based ASP is presented. Then, some key techniques including assembly case modelling, similar case retrieving, case based reasoning, and case base maintenance, etc., are explored thoroughly. To enhance the efficiency and quality of the reasoning process, genetic algorithm (GA) is designed and applied to automatically inferring of the reference assembly sequence. Finally, the corresponding software system with an engineering example is given to demonstrate the effectiveness of the CBR based ASP.     

An exact solution approach for disassembly line balancing problem under uncertainty of the task processing times

The purpose of this work is to efficiently design disassembly lines taking into account the uncertainty of task processing times. The main contribution of the paper is the development of a decision tool that allows decision-makers to choose the best disassembly alternative (process), for an End of Life product (EOL), and assign the corresponding disassembly tasks to the workstations of the line under precedence and cycle time constraints. Task times are assumed to be random variables with known normal probability distributions. The case of presence of hazardous parts is studied and cycle time constraints are to be jointly satisfied with at least a certain probability level, or service level, fixed by the decision-maker. An AND/OR graph is used to model the precedence relationships among tasks. The objective is to minimise the line cost composed of the workstation operation costs and additional costs of workstations handling hazardous parts of the EOL product. To deal with task time uncertainties, lower and upper-bounding schemes using second-order cone programming and approximations with convex piecewise linear functions are developed. The applicability of the proposed solution approach is shown by solving to optimality a set of disassembly problem instances (EOL industrial products) from the literature.     

Methods for optimum and near optimum disassembly sequencing

This paper considers disassembly sequencing problems subjected to sequence dependent disassembly costs. In practice, the methods for dealing with such problems rely mainly on metaheuristic and heuristic methods, which intrinsically generate suboptimum solutions. Exact methods are NP-hard and therefore unsuitable to most of the practical problems. Nevertheless, it is useful to have exact methods available that can be applied in order to check, at least medium sized problems, to what extent the heuristically obtained solutions deviate from the optimum solution. The existing exact approaches, which are based on integer linear programming (ILP), become unmanageable, even for the cases of modest product complexity. To alleviate this problem to some extent, the iterative method that has been proposed by Lambert (2006) is applied here. This method is based on repeatedly solving a binary integer linear programming (BILP) problem instead of an ILP problem. The method appears to converge sufficiently quickly to be valuable for dealing with medium sized problems. We then use the iterative method for the validation of a new heuristic method that is also proposed in this paper. Finally, both the heuristic and the iterative BILP methods are implemented on a cellphone from practice consisting of 25 components that are represented, according to a set of precedence relationships, via a disassembly precedence graph.     

Optimal order release dates for two-level assembly systems with stochastic lead times at each level

In this paper, we examine an optimisation problem for component replenishment in two-level assembly systems under stochastic lead times. The Assembly-to-Order principle is applied. The demand for a finished product and its planned due date are known. The capacity of the assembly system at each level is considered infinite. At each level, the assembly process starts when all the required components or semi-finished items are available. At the second level, the components are ordered from external suppliers and order release dates are decision variables of the problem. A backlogging cost is incurred if the finished product demand is satisfied after the planned due date. If the finished product, a given component or a semi-finished product is available before the corresponding assembly date, an inventory holding cost is considered. Genetic algorithms (GA) reinforced with different techniques are developed to find order release dates that minimise the total expected cost. A Branch and Bound method is also developed to assess the effectiveness of the hybrid GA. Regardless of the number of components and the variability of the costs related to the finished product, the experimental results indicate that the proposed GA are highly efficient.     

Discrete electromagnetism-like mechanism algorithm for assembly sequences planning

Assembly sequence planning (ASP) plays an important role in digital manufacturing. It is a combinatorial optimisation problem with strong constraints aiming to work out a specific sequence to assemble together all components of a product. The connector-based ASP, which uses the connector to simplify the complex assembly problem, is one of the most important and hardest types. In order to solve this problem effectively, a discrete electromagnetism-like mechanism (DEM) algorithm is proposed. A charge formula and a force formula are redefined in DEM algorithm. An adjacency list is applied to handle the precedence relationship and prevent infeasible solutions. Two movements based on path relinking are employed. Moreover, with two different guided mutations, the population diversity can be guaranteed. Five examples are used to test and evaluate the performance of DEM. The comparisons among the proposed DEM, traditional genetic algorithms (GAs), guided GAs, memetic algorithms and artificial immune systems show that DEM outperforms among these algorithms in terms of running time, computation accuracy, convergence speed and parameter robustness.     

Interactive AR-assisted product disassembly sequence planning (ARDIS)

This paper presents a proof-of-concept novel near real-time interactive AR-assisted product disassembly sequence planning system (ARDIS) based on product information, such as interference matrix and 3D models. The system is developed using Unity and consists of three modules, including an intelligent disassembly sequence planning module, an automatic content authoring module and an intuitive augmented reality (AR) user interface (UI) with various features, such as a virtual panel for customisation and an option panel for sequence regeneration. Given the retrieval targets specified by a user, optimised disassembly sequences are computed using an evolutionary computing algorithm. For the sequences computed, the respective AR disassembly instruction sequences, such as 2D text instructions and animated 3D models, are generated dynamically based on a taxonomy that links each disassembly step in a sequence with the corresponding Unity templates that have been created beforehand. Hence, the need for manual authoring to provide AR disassembly guidance is reduced. If necessary, the user can request for alternative disassembly sequences which can be re-computed in near real-time. Several case studies have been carried out to demonstrate and evaluate the performance of the system within the laboratory environment.     

Mathematical model and solution algorithms for selective disassembly sequencing with multiple target components and sequence-dependent setups

This study considers selective disassembly sequencing under the sequential disassembly environment in which one component is obtained at each disassembly operation. The problem is to determine the sequence of disassembly operations to obtain multiple target components of a used or end-of-life product for the purpose of repair, reuse, remanufacturing, disposal, etc. In particular, we consider sequence-dependent setups in which setup costs depend on the disassembly operation just completed and on the operation to be processed. The problem is represented as a disassembly precedence graph and then a new integer programming model is suggested for the objective of minimising the total disassembly cost. After it is proved that the problem is NP-hard, we suggest two types of heuristics: (1) branch and fathoming algorithm for small-to-medium-sized instances; and (2) priority-rule-based algorithm for large-sized instances. A series of computational experiments, i.e., effectiveness of the new integer programming model and performances of the two heuristic types, were done on various test instances, and the results are reported. In addition, to show the applicability of the mathematical model and the solution algorithms, a case study is reported on an end-of-life electronic calculator.     

Disassembly process planning algorithms for end-of-life product recovery and environmentally conscious disposal

Disassembly process planning is an act of preparing detailed operation instructions for disassembling used or an end-of-life (EOL) product to recover or dispose of its constituent parts or subassemblies. The main decisions are: (a) disassembly level; (b) disassembly sequence; and (c) EOL options such as reuse, remanufacturing, recycling, incineration, landfill, etc. This study deals with the three decision variables simultaneously in the parallel disassembly environment for the objective of maximising the profit. Unlike previous studies, we consider practical constraints, i.e., reuse probability and environmental impacts of parts or subassemblies, sequence-dependent setup costs, regulation on recovery rate, and incineration capacity. To represent and solve the problem, we develop an extended AND/OR graph, and then suggest a two-phase algorithm. To show the effectiveness of the proposed algorithm, two case studies have been carried out on an automatic pencil and a telephone. Also, test results on other general product structures are reported.     

Integrating assembly and machining planning using graph-based representation models

Traditionally, assembly planning and machining planning are considered as two independent tasks. In assembly planning, the components to be sequenced are considered as machined and finished. In machining planning, the focus has been on machining each individual component. In previous research, machining and assembly planning are analysed separately. However, in order to achieve some design specifications, the assembly and machining operations may need to be mixed in an integrated sequence. For example, a machining operation may need to be performed on a subassembly formed by a group of components in order to complete certain geometric features. In other cases, an assembly operation cannot be performed unless certain geometric features are completely machined. Therefore, the assembly and machining operations need to be planned in a combined sequence. In this research, new graph-based representation models were developed to integrate assembly and machining planning. First, an assembly-machining operation graph was developed to represent the spatial relationships between the components as well as to express the operational precedence of the machining and assembly operations. Next, the integrated assembly and machining sequences were generated using a tree structure called the assemblymachining sequence tree. Using the graph-based methodology, all the feasible integrated assembly and machining sequences can be generated and evaluated. The main objective is to provide a complete model for integrating assembly and machining sequences. A combined evaluation can be performed to find the best sequence based on certain time and cost objectives. The presented methodology is implemented on a personal computer and several example parts are discussed.     

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.     

Assembly/disassembly task planning and simulation using expert Petri nets

Automatic assembly/disassembly planning is recognized as an important tool for reducing the manufacturing costs in concurrent product and process development. This paper developed a knowledge-based expert Petri net model by incorporating expert system techniques in artificial intelligence into ordinary Petri nets for an analytical framework of understanding, representing and reasoning the assembly/disassembly tasks. Substantial extensions have been made to ordinary Petri nets by adding control places, time constraints, and place and transition knowledge annotations. The proposed expert Petri net model can be considered as the hybrid of expert systems and ordinary Petri nets. Through these extensions, the capacities of modelling and representation of ordinary Petri net models are largely enhanced, and thus the expert Petri net models are more powerful than ordinary Petri nets. Such intelligent Petri net models can combine the abilities of modelling, planning, and performance evaluation for assembly/disassembly tasks in an integrated and intuitive way, and can therefore be applied to either linear/non-linear, static/dynamic, or on-line/off-line assembly/disassembly tasks at both high and low levels. The developed assembly/disassembly planning system can generate the best strategies and plans for assembly/disassembly. The research findings are exemplified with a real assembly to show the effectiveness of the method.     

3D geometric constraint analysis and its application on the spatial assembly sequence planning

Focusing on the spatial geometric feasible assembly sequence planning and optimising, a novel approach entitled 3D-GCA is proposed based on the method of Geometric Constraint Analysis (GCA) incorporated with the Oriental Bounding Box (OBB) and Separation Axis Theory. Accordingly, the corresponding computer-aided 3D assembly sequence planning system is developed and two cases are studied in detail. The analysis results demonstrate that, with 3D-GCA method, the spatial assembly precedence relations (APRs) can be calculated out correctly and completely. Thereby, all the 3D geometric feasible assembly sequences can be derived automatically. Moreover, an optimisation algorithm is designed based on 3D-GCA method, by which, the optimal assembly sequences can be calculated out according to two criteria, e.g., assembly angle and assembly direction. The 3D-GCA method and its algorithms can provide significant assistance in the spatial geometric feasible assembly sequences reasoning and the optimal sequences selection.     

维修拆装工艺规划系统的研究

结合装备维修活动中的拆卸与装配问题,明确了研发面向维修的拆装工艺规划系统的必要性.提出了一个拆装工艺规划系统的构架,论述了系统的主要功能模块、工作流程以及所采用的关键技术.实现了装配建模、拆装序列规划、拆装序列评估与优化,以及拆装作业仿真等关键功能.实践表明该原型系统的设计切实可行,具有良好的应用前景.     

An integrated setup/fixture planning approach for machining prismatic parts

Setup/fixture planning for machining prismatic parts is usually carried out by grouping features/operations into setups, determining suitable locating surfaces for each setup, and sequencing setups and operations in each setup. The presently developed setup/fixture planning methods can be classified into three categories: multi-constraints, fixture driven, and tolerance analysis planning methods. The multi-constraints planning is theoretically sound, but very difficult to use. In fixture driven planning, the generated setup plans are highly practical, but may not be optimal. Tolerance analysis based planning cannot be used to generate the optimal solution by itself. In this research, a new integrated setup/fixture planning approach is developed to identify the optimal and practical setup/fixture plan. The planning is conducted in four steps. (1) The dissimilarity degree matrix (DDM), operation precedence graph (OPG), and hybrid graph are used to describe the requirements and constraints for setup/fixture planning. (2) A setup precedence graph (SPG) is used to describe precedence constraints between setups. The SPG is generated by the vertex clustering algorithm. Precedence loops among setups are avoided by checking whether two serial vertex clusters can generate a loop. (3) Suitable locating surfaces are selected for each setup in a SPG. When the fixture locating surface and design datum surface are different, two types of dimension recalculations are employed to obtain the dimensions against the locating surfaces. (4) All the candidate setup/fixture plans are evaluated based on the number of setups and recalculation of dimensions. An example is given to demonstrate the effectiveness of the developed approach.     

Hybrid GA and SA dynamic set-up planning optimization

Set-up planning is used to determine the set-up of a workpiece with a certain orientation and fixturing on a worktable, as well as the number and sequence of set-ups and operations performed in each set-up. This paper presents a concurrent constraint planning methodology and a hybrid genetic algorithm (GA) and simulated annealing (SA) approach for set-up planning, and re-set-up planning in a dynamic workshop environment. The proposed approach and optimization methodology analyses the precedence relationships among features to generate a precedence relationship matrix (PRM). Based on the PRM and inquiry results from a dynamic workshop resource database, the hybrid GA and SA approach, which adopts the feature-based representation, optimizes the set-up plan using six cost indices. The PRM acts as the main constraints for the set-up planning optimization. Case studies show that the hybrid GA and SA approach is able to generate optimal results as well as carry out re-set-up planning on the occurrence of workshop resource changes.     

An optimal algorithm for selective disassembly sequencing with sequence-dependent set-ups in parallel disassembly environment

This study considers selective disassembly sequencing in parallel disassembly environment in which two or more components can be removed by a single disassembly operation. The problem is to determine the sequence of disassembly operations to extract multiple target components while satisfying the precedence relations among disassembly operations. The objective is to minimise the sum of sequence-dependent set-up and operation costs. An integer programming model is developed after representing all possible disassembly sequences using an extended process graph, and then an optimal branch and bound algorithm is proposed that incorporates the methods to obtain the lower and upper bounds as well as a dominance property to reduce the search space. To show the performance of the algorithm, computational experiments are done on various random instances, and the results are reported. In particular, it is shown from the test results that the optimal algorithm requires much shorter computation times than a competitive commercial software package. Finally, a case is reported to illustrate the extended process graph and the solution algorithm.     

A Petri Net based approach to determine the disassembly strategy of a product

In order to protect the environment and regain value added to products, a process known as disassembly has come into the limelight. This process is to be applied to reuse abandoned goods and materials. Manufacturers are being forced to establish disassembly plants and to develop their products' designs so as to maintain the government's dictate to dispose off their products in an environmentally responsible manner. This research presents a cost-based heuristic analysis for a circuit board assembly. Various components of the product and their assembly relationships are represented by a Petri Net diagram. Firing the transitions of the disassembly Petri Net is integrated with cost-based indices to develop an effective disassembly strategy. The methodology discussed here simplifies the decisionmaking process involved in disassembly planning. A comprehensive disassembly process planning system is proposed here and is exemplified by a case study of circuit board assembly.