×

Optimizing disassembly processes subjected to sequence-dependent cost. (English) Zbl 1113.90029

Summary: Detection of the optimum disassembly sequence for a given product can proceed via mathematical programming, which is based on the AND/OR graph representation of its disassembly process. This is called the exact method for it reveals the global optimum. This paper describes an extension of the exact method in case sequence-dependent costs are considered. Previously presented methods confined themselves either to sequential disassembly, or were based on heuristics. The only exact method for the full problem known so far, needs an elaborate transformation of the AND/OR graph, and is based on integer linear programming. This paper discusses an alternate approach that uses a binary integer linear programming approach and that lacks the need of transforming the AND/OR graph. The proposed method is applied to arbitrary instances of some product structures that have been taken from the literature. Apart from this, the method is applied to an expandable AND/OR graph, that enables gradual increase of product complexity. It is demonstrated that the convergence of the iteration process is satisfactory, and the required CPU time appears comparatively small and only moderately increases with the number of constraints. It appears that the method applies to products with a complexity that cannot be managed with the integer linear programming model. The iterative method is promising for dealing with modularized products and as a benchmark for heuristic algorithms, which are used if products exhibit still higher complexity.

MSC:

90B10 Deterministic network models in operations research
90C30 Nonlinear programming
90C27 Combinatorial optimization

Software:

AIMMS
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bourjault A. Contribution à une approche méthodologique de l’assemblage automatisé: elaboration automatique des séquencs opératoires (contribution to a methodological approach of automatic assembly: automatic determination of operation sequences). PhD thesis, Université de Franche-Comté, Besançon, France (in French); 1984.; Bourjault A. Contribution à une approche méthodologique de l’assemblage automatisé: elaboration automatique des séquencs opératoires (contribution to a methodological approach of automatic assembly: automatic determination of operation sequences). PhD thesis, Université de Franche-Comté, Besançon, France (in French); 1984.
[2] Homem de Mello, L. S.; Sanderson, A. C., And/or graph representation of assembly plans, IEEE Transactions on Robotics and Automation, 6, 2, 188-189 (1990)
[3] Homem de Mello, L. S.; Sanderson, A. C., A correct and complete algorithm for the generation of mechanical assembly sequences, IEEE Transactions on Robotics and Automation, 7, 2, 228-240 (1991)
[4] De Fazio, T. L.; Whitney, D. E., Simplified generation of all mechanical assembly sequences, IEEE Journal of Robotics and Automation, RA-3, 6, 640-658 (1987)
[5] Baldwin, D. F.; Abell, T. E.; Lui, M. M.; De Fazio, T. L.; Whitney, D. E., An integrated computer aid for generating and evaluating assembly sequences for mechanical products, IEEE Transactions on Robotics and Automation, 7, 78-94 (1991)
[6] Boothroyd G, Poli C, Murch LE. Automatic assembly, manufacturing engineering and materials processing, vol. 6, New York: Marcel Dekker Inc.; 1982 [chapter 9].; Boothroyd G, Poli C, Murch LE. Automatic assembly, manufacturing engineering and materials processing, vol. 6, New York: Marcel Dekker Inc.; 1982 [chapter 9].
[7] Kanehara T, Suzuki T, Inaba A, Okuma S. On algebraic and graph structural properties of assembly Petri net. Proceedings of IEEE/RSJ international conference on intelligent robots and systems. Yokohama (Japan); 1993. p. 2286-93.; Kanehara T, Suzuki T, Inaba A, Okuma S. On algebraic and graph structural properties of assembly Petri net. Proceedings of IEEE/RSJ international conference on intelligent robots and systems. Yokohama (Japan); 1993. p. 2286-93.
[8] Lambert, A. J.D., Optimal disassembly of complex products, International Journal of Production Research, 35, 9, 2509-2523 (1997) · Zbl 0943.90536
[9] Lambert, A. J.D., Linear programming in disassembly/clustering sequence generation, Computers and Industrial Engineering, 36, 723-738 (1999)
[10] Gungor, A.; Gupta, S. M., An evaluation methodology for disassembly processes, Computers and Industrial Engineering, 33, 1-2, 329-332 (1997)
[11] Kaebernick, H.; O’Shea, B.; Grewal, S. S., A method for sequencing the disassembly of products, Annals of the CIRP, 49, 1, 13-16 (2000)
[12] Yee, S. T.; Ventura, J. A., A Petri net model to determine optimal assembly sequences with assembly operation constraints, Journal of Manufacturing Systems, 18, 3, 203-213 (1999)
[13] Rosell J, Muñoz N, Gambin A. Robot tasks sequence planning using Petri nets. Proceedings of fifth IEEE international symposium on assembly and task planning, 2003. p. 24-9.; Rosell J, Muñoz N, Gambin A. Robot tasks sequence planning using Petri nets. Proceedings of fifth IEEE international symposium on assembly and task planning, 2003. p. 24-9.
[14] Moore, K. E.; Gungor, A.; Gupta, S. M., Petri net approach to disassembly process planning for products with complex AND/OR precedence relationships, European Journal of Operations Research, 135, 428-449 (2001) · Zbl 1004.90030
[15] Johnson, M. R.; Wang, M. H., Economical evaluation of disassembly operations for recycling, International Journal of Production Research, 36, 12, 3227-3252 (1998) · Zbl 0946.90507
[16] Kang, J. G.; Lee, D. H.; Xirouchakis, P.; Persson, J. G., Parallel disassembly sequencing with sequence-dependent operation times, Annals of CIRP, 50, 1, 343-346 (2001)
[17] Bisschop, J.; Entriken, R., AIMMS, the modeling system (1993), Paragon Decision Technology: Paragon Decision Technology Haarlem
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.