Disassembly scheduling : models and algorithms

This dissertation focuses on disassembly scheduling, which is the problem of determining the quantity and timing of disassembling used or end-of-life products while satisfying the demand of their parts/components over a given planning horizon. The objective is to minimize the sum of purchase, setup, disassembly operation, and inventory holding costs. In general, disassembly scheduling is one of the important mid-term (or short-term) planning problems in disassembly systems. In contrast to assembly, disassembly systems have the special characteristic that a product diverges into multiple demand sources of parts/components. This makes the disassembly scheduling problem more complex than the ordinary production planning problems in assembly systems. We consider two versions of disassembly scheduling: the uncapacitated and capacitated version. For the uncapacitated version of the problem, three cases are considered: the two-level disassembly; the multi-level disassembly; and the multiple product types with parts commonality structures. The two-level disassembly structure describes the direct relationship between the product and its parts/components without intermediate subassemblies. Parts commonality implies that products or subassemblies share their parts and/or components. For the capacitated version of the problem, the case with single product type without parts commonality is considered. In the first part of this dissertation, we consider the case with the two-level disassembly structure. We propose a dynamic programming model after characterizing the properties of optimal solutions. Based on the dynamic programming model, an exact algorithm is proposed by which the optimal solutions can be obtained in polynomial time. The second part considers the case with the multi-level disassembly structure. An integer programming model is proposed to represent and optimally solve the case of single product type without parts commonality. Then, the model is extended to consider single and multiple product types with parts commonality. The results of computational experiments show that the proposed integer programming approach works well. The case with multiple product types and parts commonality is considered in the third part. A two-phase heuristic is proposed in which an initial solution is obtained using a linear programming relaxation, and then improved by perturbing the initial solution using a dynamic programming algorithm with look-ahead check, together with methods of generating new solutions and checking their feasibilities. The results of computational experiments show that the proposed heuristic can give good solutions within short computation time. We consider in the last part the resource capacity restrictions over the planning horizon, which makes the problem more realistic. To solve the problem, a heuristic is developed using a Lagrangean relaxation technique together with a method to find a good feasible solution while considering the trade-