Profit-oriented partial disassembly line design: dealing with hazardous parts and task processing times uncertainty

This paper addresses the problem of profit-oriented disassembly line design and balancing considering partial disassembly, presence of hazardous parts and uncertainty of task processing times. Few papers have studied the stochastic disassembly line balancing problem and existing approaches have focused on heuristic and metaheuristic methods. Most existing work has concentrated on complete disassembly where task times are assumed to be normal random variables and where AND/OR graphs are not considered. The objective of this paper is the design of a serial line that obtains the maximum revenue and then balances the workload under uncertainty. The processing time of a disassembly task is assumed to be a random variable with any known probability distribution. An AND/OR graph is used to model the precedence relationships among tasks. Stochastic programming models and exact-based solution approaches combining the L-shaped algorithm and Monte Carlo sampling techniques are proposed. The relevance and applicability of the proposed models and solution methods are shown by solving efficiently a set of disassembly problem instances from the literature.     

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.     

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.     

Joint decision-making on automated disassembly system scheme selection and recovery route assignment using multi-objective meta-heuristic algorithm

Green treatment on Waste Electrical and Electronic Equipmenthas increasingly attracted attention due to its significant environmental benefits and potential recovery earnings. Automated disassembly has been regarded as a powerful solution to enable more efficient recovery operations. Although numerous studies have contributed to the issues of disassembly, there are few researches that focus on decision model for selecting disassembly system scheme and recovery route in automated disassembly. In this paper, we propose a two-phase joint decision-making model to address this problem with the goal of balancing disassembly profit with environmental impact. First, we establish a multi-objective optimisation model to obtain the Pareto optimal recovery routes for each automated disassembly system scheme. Both recovery profit and energy consumption are evaluated for multi-station disassembly system. We design a multi-objective hybrid particle swarm optimisation algorithm based on symbiotic evolutionary mechanism to solve the proposed model. Then, we compare the Pareto optimal solutions of all the system schemes using a fuzzy set method and identify the best scheme. Finally, we conduct real case studies on the automated disassembly of different waste electric metres. The results demonstrate the superiority of automated disassembly and validate the effectiveness of our proposed model and algorithm.     

A solution approach to the disassembly line balancing problem in the presence of task failures

In this paper, we discuss the disassembly line balancing problem in the presence of task failures (DLBP-F). There are precedence relationships among disassembly tasks and the tasks must be completed within a given time, determined by the demand in a given period. However, if a task (or more than one task) cannot be performed because of some defect, some or all of the remaining tasks may be disabled due to the precedence relationships among tasks. This may result in various complications in the flow of workpieces on the disassembly line, e.g. early-leaving, self-skipping, skipping, disappearing and revisiting workpieces. We discuss these complications and highlight their effects on the disassembly line. The problem is to assign tasks to workstations such that the effect of the defective parts on the disassembly line is minimized. This paper presents a solution procedure to the DLBP-F. An example is provided to illustrate the approach.     

Evaluation model and algorithm of product disassembly process with stochastic feature

Disassembly planning is considered as the optimization of disassembly sequences with the target of the shortest disassembly time, the lowest disassembly cost, and the minimum disassembly energy consumption. However, obsolete products suffer from the influence of a variety of uncertainties, the disassembly process of products has the strong uncertain feature. Traditionally, to account for this uncertainty, each removal operation or removal task is assumed to be an activity or event with certain probability, and the determination of the optimal path of a disassembly process is merely a probabilistic planning problem based on this assumption. In this article, based on the established stochastic disassembly network graph, combined with different disassembly decision-making criterion, typical stochastic models for disassembly time analysis are developed. In addition, a two-phase approach is proposed to solve the typical stochastic models. Initially, according to different removal probability density functions, disassembly probability density functions of feasible disassembly paths are determined by a time-domain method or frequency-domain method, and additionally, after the disassembly probability density functions have been obtained, the quantitative evaluation of a product disassembly process and stochastic optimization of feasible disassembly paths are realized by a numerical solution method. Finally, a numerical example is illustrated to test the proposed concepts and the effectiveness of the proposed approach.     

基于改进社会工程算法的拆解线平衡多目标优化设计

目的 为了提高拆卸效率,减少拆卸成本和拆卸能耗,提出一种基于社会工程算法的优化方法。方法 首先根据社会工程算法的原理设计了编码和解码方式,然后引入交换子和交换序列的概念,对算法中的训练和再训练、发现攻击和响应攻击等步骤进行设计,最后选取一个高速电子套结机作为实验对象进行了验证。结果 与其他多目标优化算法相比,具有良好的寻优能力。结论 提出的算法有效地解决了拆解线平衡问题,与其他算法相比具有更好的性能。     

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.     

Integrated assembly and disassembly sequence planning using a GA approach

In a product life cycle, an assembly sequence is required to produce a new product at the start, whereas a disassembly sequence is needed at the end. In typical assembly and disassembly sequence planning approaches, the two are performed as two independent tasks. In this way, a good assembly sequence may contradict the cost considerations in the disassembly sequence, and vice versa. In this research, an integrated assembly and disassembly sequence planning model is presented. First, an assembly precedence graph (APG) and a disassembly precedence graph (DPG) are modelled. The two graphs are transformed into an assembly precedence matrix (APM) and a disassembly precedence matrix (DPM). Second, a two-loop genetic algorithm (GA) method is applied to generate and evaluate the solutions. The outer loop of the GA method performs assembly sequence planning. In the inner loop, the reverse order of the assembly sequence solution is used as the initial solution for disassembly sequence planning. A cost objective by integrating the assembly costs and disassembly costs is formulated as the fitness function. The test results show that the developed method using the GA approach is suitable and efficient for the integrated assembly and disassembly sequence planning. Example products are demonstrated and discussed.     

Modelling and planning of the disassembly processes using an enhanced expert Petri net

A sound disassembly Petri net model for the effective planning of disassembly processes and tasks is outlined. Owing to the unmanageable complexity associated with modelling of the disassembly processes and tasks, it becomes essential to have a more powerful Petri net model developed by incorporating the concepts of expert system, knowledge representation techniques, etc. Disassembly task planning at high and low levels can easily be represented by proposed high- and low-level expert Petri net. An algorithmic approach is also suggested for evaluating the end-of-life values of a product. These values are used to determine an optimal disassembly sequence and it is incorporated in the expert disassembly Petri net. A proposed expert enhanced high-level coloured disassembly Petri net is empowered to express such details vividly. The application of the proposed expert enhanced high-level coloured disassembly Petri net model is demonstrated through the sample disassembly of a flashlight.     

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.     

Design of high-performing hybrid meta-heuristics for unrelated parallel machine scheduling with machine eligibility and precedence constraints

This study involves an unrelated parallel machine scheduling problem in which sequence-dependent set-up times, different release dates, machine eligibility and precedence constraints are considered to minimize total late works. A new mixed-integer programming model is presented and two efficient hybrid meta-heuristics, genetic algorithm and ant colony optimization, combined with the acceptance strategy of the simulated annealing algorithm (Metropolis acceptance rule), are proposed to solve this problem. Manifestly, the precedence constraints greatly increase the complexity of the scheduling problem to generate feasible solutions, especially in a parallel machine environment. In this research, a new corrective algorithm is proposed to obtain the feasibility in all stages of the algorithms. The performance of the proposed algorithms is evaluated in numerical examples. The results indicate that the suggested hybrid ant colony optimization statistically outperformed the proposed hybrid genetic algorithm in solving large-size test problems.     

A fast branch,bound and remember algorithm for disassembly line balancing problem

In recent years, the interests of disassembly line have increased owing to economic reasons and the increase of environmental awareness. Effective line can provide many advantages in terms of economic aspect and it facilitates competition the companies with others. This study contributes to the relevant literature by a branch, bound and remember algorithm for disassembly line balancing problem with AND/OR precedence. The proposed exact solution method employs the memory-based dominance rule to eliminate the reduplicated sub-problems by storing all the searched sub-problems and to utilise cyclic best-first search strategy to obtain high-quality complete solutions fast. In this paper, minimising the number of stations is taken as the performance measure. The proposed methodology is tested on a set of 260 instances and compared with the mathematical model using CPLEX solver and five well-known metaheuristics. Computational results show that the proposed method is capable of obtaining the optimal solutions for all the tested instances with less than 0.1?seconds on average. Additionally, comparative study demonstrates that the proposed method is the state-of-the-art algorithm and outperforms the CPLEX solver and metaheuristics in terms of both solution quality and search speed aspects.     

Selective disassembly sequencing with random operation times in parallel disassembly environment

Selective disassembly sequencing is the problem of determining the sequence of disassembly operations to extract one or more target components of a product. This study considers the problem with random operation times in the parallel disassembly environment in which one or more components can be removed at the same time by a single disassembly operation. After representing all possible disassembly sequences using the extended process graph, a stochastic integer programming model is developed for the objective of minimising the sum of disassembly and penalty costs, where the disassembly costs consist of sequence-dependent set-up and operation costs and the penalty cost is the expectation of the costs incurred when the total disassembly time exceeds a threshold value. A sample average approximation-based solution algorithm is proposed that incorporates an optimal algorithm to solve the sample average approximating problem under a given set of scenarios for disassembly operation times. The algorithm is illustrated with a hand-light case and a large-sized random instance, and the results are reported.     

Robust disassembly line balancing with ambiguous task processing times

Disassembly line balancing problem (DLBP), which is to select disassembly process, open workstations and assign selected tasks to opened workstations, plays an important role in the recycling of End Of Life products. In real-world disassembly operations, task processing times are usually stochastic due to various factors. Most related works address the uncertain processing times by assuming that the probability distribution is known and the task processing times are independent of each other. In practice, however, it is difficult to get the complete distributional information and there is always underlying correlation between the uncertain processing times. This paper investigates the DLBP with partial uncertain knowledge, i.e. the mean and covariance matrix of task processing times. A new distributionally robust formulation with a joint chance constraint is proposed. To solve the problem, an approximated mixed integer second-order cone programming (MI-SOCP) model is proposed, and a two-stage parameter-adjusting heuristic is further developed. Numerical experiments are conducted, to evaluate the performance of the proposed method. We also draw some managerial insights and consider an extension problem.     

A multi-objective distribution-free model and method for stochastic disassembly line balancing problem

End-of-life product recycling is a hot research topic in recent years, which can reduce the waste and protect the environment. To disassemble products, the disassembly line balancing is a principal problem that selects tasks and assigns them to a number of workstations under stochastic task processing times. In existing works, stochastic task processing times are usually estimated by probability distributions or fuzzy numbers. However, in real-life applications, only their partial information is accessible. This paper studies a bi-objective stochastic disassembly line balancing problem to minimise the line design cost and the cycle time, with only the knowledge of the mean, standard deviation and upper bound of stochastic task processing times. For the problem, a bi-objective chance-constrained model is developed, which is further approximated into a bi-objective distribution-free one. Based on the problem analysis, two versions of the ?-constraint method are proposed to solve the transformed model. Finally, a fuzzy-logic technique is adapted to propose a preferable solution for decision makers according to their preferences. A case study is presented to illustrate the validity of the proposed models and algorithms. Experimental results on 277 benchmark-based and randomly generated instances show the efficiency of the proposed methods.     

Applying data mining technique to disassembly sequence planning: a method to assess effective disassembly time of industrial products

Design for end-of-life and design for disassembly are enabling design strategies for the implementation of business models based on the circular economy paradigm. The paper presents a method for calculating the effective disassembly sequence and time for industrial products. Five steps support designers in defining liaisons and related properties and precedence among components with the aim to calculate the best disassembly sequence and time. The effective disassembly time is computed considering the actual conditions of a product and its components (e.g. deformation, rust and wear) using corrective factors. This aspect represents the main contribution to the state of the art in the field of design for disassembly. The corrective factors are derived from a specific data mining process, based on the observation of real de-manufacturing activities. The proposed approach has been used for calculating the disassembly times of target components in a washing machine and in a coffee machine. The case studies highlight the method reliability of both: definition of time-effective disassembly sequences and assessment of effective disassembly times. In particular, a comparison of experimental tests shows a maximum deviation of ?6% for the electric motor of the washing machine and ?3% for the water pump of the coffee machine.     

A new distribution-free model for disassembly line balancing problem with stochastic task processing times

Effective conduct with End of Life (EOL) products is a hot research topic in green and smart manufacturing. For EOL product recycling and remanufacturing, a fundamental problem is to design an efficient disassembly line under consideration of stochastic task processing times. This problem focuses on selecting alternative task processes, determining the number of opened workstations, and assigning operational tasks to the workstations. The goal is to minimise the total cost consisting of workstation operational cost and hazardous component processing cost. Most existing works assume that the probability distribution of task processing times can be estimated, however, it is often not likely to access the complete probability distribution due to various difficulties. Therefore, this study investigates disassembly line design with the assumption that only the mean, standard deviation and an upper bound of task processing times are known. Our main contributions include: (i) a new decomposition color graph is proposed to intuitively describe all possible processes, (ii) a new distribution-free model is proposed, and (iii) some problem properties are established to solve the model. Experimental results show that the distribution-free model can effectively deal with stochastic task processing times without given probability distributions.     

Task Scheduling Optimization in Cloud Computing by Rao Algorithm

Cloud computing is currently dominated within the space of high-performance distributed computing and it provides resource polling and on-demand services through the web. So, task scheduling problem becomes a very important analysis space within the field of a cloud computing environment as a result of user's services demand modification dynamically. The main purpose of task scheduling is to assign tasks to available processors to produce minimum schedule length without violating precedence restrictions. In heterogeneous multiprocessor systems, task assignments and schedules have a significant impact on system operation. Within the heuristic-based task scheduling algorithm, the different processes will lead to a different task execution time (makespan) on a heterogeneous computing system. Thus, a good scheduling algorithm should be able to set precedence efficiently for every subtask depending on the resources required to reduce (makespan). In this paper, we propose a new efficient task scheduling algorithm in cloud computing systems based on RAO algorithm to solve an important task and schedule a heterogeneous multiple processing problem. The basic idea of this process is to exploit the advantages of heuristic-based algorithms to reduce space search and time to get the best solution. We evaluate our algorithm's performance by applying it to three examples with a different number of tasks and processors. The experimental results show that the proposed approach significantly succeeded in finding the optimal solutions than others in terms of the time of task implementation.     

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.