×

zbMATH — the first resource for mathematics

An asynchronous parallel disassembly planning based on genetic algorithm. (English) Zbl 1388.90105
Summary: Disassembly is one of the most crucial remanufacturing activities. Disassembly sequence planning (DSP) is a combinatorial optimization problem and has been studied by many researchers. Conventional DSP techniques focus on sequential disassembly planning (SDP) in which only one manipulator is used to remove a single part or subassembly at a time such that it is inefficient when disassembling large or complex products. Recently, parallel disassembly has attracted some interest as it employs several manipulators to remove multiple components simultaneously. However, most of the work to date focuses on parallel disassembly techniques which require synchronization between manipulators, i.e., they must start their tasks simultaneously. This simplifies the modeling and analysis efforts but fails to fully realize the benefits of parallel disassembly. In this work, we propose asynchronous parallel disassembly planning (aPDP) which eliminates the synchronization requirement. In addition to precedence constraints, aPDP becomes highly operation time-dependent. To deal with this, we design an efficient encoding and decoding strategy for the disassembly process. In this paper, a metaheuristic approach, based on a genetic algorithm, is developed to solve the aPDP problem. The proposed algorithm is applied to four products which require disassembly processes of varying complexity, and the results are compared with two methods reported in literature. It is suggested that the proposed approach can identify faster disassembly processes, especially when solving large-scale problems.

MSC:
90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Adenso-Díaz, B.; García-Carbajal, S.; Lozano, S., An efficient GRASP algorithm for disassembly sequence planning, OR spectrum, 29, 535-549, (2007) · Zbl 1146.90327
[2] Alshibli, M.; El Sayed, A.; Kongar, E.; Sobh, T. M.; Gupta, S. M., Disassembly sequencing using tabu search, Journal of Intelligent and Robotic Systems, 82, 69-79, (2016)
[3] Altekin, F. T.; Kandiller, L.; Ozdemirel, N. E., Profit-oriented disassembly-line balancing, International Journal of Production Research, 46, 2675-2693, (2008) · Zbl 1160.90360
[4] Aytug, H.; Khouja, M.; Vergara, F. E., Use of genetic algorithms to solve production and operations management problems: A review, International Journal of Production Research, 41, 3955-4009, (2003)
[5] Chaudhry, S. S.; Luo, W., Application of genetic algorithms in production and operations management: A review, International Journal of Production Research, 43, 4083-4101, (2005) · Zbl 1080.90514
[6] Dong, T.; Tong, R.; Zhang, L.; Dong, J., A collaborative approach to assembly sequence planning, Advanced Engineering Informatics, 19, 2, 155-168, (2005)
[7] Dutta, D.; Woo, T. C., Algorithm for multiple disassembly and parallel assemblies, Journal of Engineering for Industry, 117, 102-109, (1995)
[8] Goncalves, J. F.; Mendes, J.; Resende, M. G.C., A hybrid genetic algorithm for the job shop scheduling problem, European Journal of Operational Research, 167, 1, 77-95, (2005) · Zbl 1075.90028
[9] González, B.; Adenso-Díaz, B., A scatter search approach to the optimum disassembly sequence problem, Computers & Operations Research, 33, 1776-1793, (2006) · Zbl 1087.90045
[10] Güngör, A.; Gupta, S. M., Disassembly sequence plan generation using a branch-and-bound algorithm, International Journal of Production Research, 39, 481-509, (2001)
[11] Guo, X.; Liu, S.; Zhou, M.; Tian, G., Disassembly sequence optimization for large-scale products with multiresource constraints using scatter search and Petri nets, IEEE Transactions on Cybernetics, 46, 2435-2446, (2016)
[12] Hui, W.; Dong, X.; Guanghong, D., A genetic algorithm for product disassembly sequence planning, Neurocomputing, 71, 2720-2726, (2008)
[13] Kang, J. G.; Lee, D. H.; Xirouchakis, P.; Persson, J. G., Parallel disassembly sequencing with sequence-dependent operation times, CIRP Annals - Manufacturing Technology, 50, 343-346, (2001)
[14] Karimi-Nasab, M.; Seyedhoseini, S. M., Multi-level lot sizing and job shop scheduling with compressible process times: A cutting plane approach, European Journal of Operational Research, 231, 3, 598-616, (2013) · Zbl 1317.90103
[15] Kheder, M.; Trigui, M.; Aifaoui, N., Disassembly sequence planning based on a genetic algorithm, Proceedings of the Institution of Mechanical Engineers, Part C: Journal of Mechanical Engineering Science, 229, 2281-2290, (2015)
[16] Kim, H. W.; Lee, D. H., An optimal algorithm for selective disassembly sequencing with sequence-dependent set-ups in parallel disassembly environment, International Journal of Production Research, 55, 7317-7333, (2017)
[17] Kongar, E.; Gupta, S. M., Genetic algorithm for disassembly process planning, Proceedings of the SPIE International Conference on Environmentally Conscious Manufacturing II, Newton, Massachusetts, vol. 4569, 54-62, (2001)
[18] Kongar, E.; Gupta, S. M., Disassembly sequencing using genetic algorithm, The International Journal of Advanced Manufacturing Technology, 30, 497-506, (2006)
[19] Koulamas, C.; Panwalkar, S. S., The proportionate two-machine no-wait job shop scheduling problem, European Journal of Operational Research, 252, 1, 131-135, (2016) · Zbl 1346.90360
[20] Krüger, J.; Schreck, G.; Surdilovic, D., Dual arm robot for flexible and cooperative assembly, CIRP Annals-Manufacturing Technology, 60, 1, 5-8, (2011)
[21] Kumar, M.; Husian, M.; Upreti, N.; Gupta, D., Genetic algorithm: review and application, International Journal of Information Technology and Knowledge Management, 2, 451-454, (2010)
[22] Lambert, A.; Gupta, S. M., Methods for optimum and near optimum disassembly sequencing, International Journal of Production Research, 46, 2845-2865, (2008) · Zbl 1141.90404
[23] Lambert, A. J., Optimizing disassembly processes subjected to sequence-dependent cost, Computers & Operations Research, 34, 536-551, (2007) · Zbl 1113.90029
[24] Lambert, A. J.D., Linear programming in disassembly/clustering sequence generation, Computers & Industrial Engineering, 36, 723-738, (1999)
[25] Lambert, A. J.D., Disassembly sequencing: A survey, International Journal of Production Research, 41, 3721-3759, (2003) · Zbl 1059.90055
[26] Lee, S.; Shin, Y. G., Assembly planning based on geometric reasoning, Computers & Graphics, 14, 2, 237-250, (1990)
[27] Li, L.; Huang, H.; Zhao, F.; Sutherland, J. W.; Liu, Z., An energy-saving method by balancing the load of operations for hydraulic press, IEEE/ASME Transactions on Mechatronics, 22, 6, 2673-2683, (2017)
[28] Lu, Q.; Zhou, G.; Xiao, Z.; Chang, F.; Tian, C., A selection methodology of key parts based on the characteristic of carbon emissions for low-carbon design, International Journal of Advanced Manufacturing Technology, 94, 3359-3373, (2018)
[29] McGovern, S. M.; Gupta, S. M., 2-opt heuristic for the disassembly line balancing problem, Environmentally conscious manufacturing iii, vol. 5262, 71-85, (2004), International Society for Optics and Photonics
[30] McGovern, S. M.; Gupta, S. M., Ant colony optimization for disassembly sequencing with multiple objectives, The International Journal of Advanced Manufacturing Technology, 30, 481-496, (2006)
[31] 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 Operational Research, 135, 428-449, (2001) · Zbl 1004.90030
[32] Nof, S. Y.; Chen, J., Assembly and disassembly: an overview and framework for cooperation requirement planning with conflict resolution, Journal of Intelligent & Robotic Systems, 37, 3, 307-320, (2003) · Zbl 1057.68115
[33] Oliver, J. H.; Chou, S. Y.; Chen, L. L., Parallel disassembly by onion peeling, Journal of Mechanical Design, 119, 267-274, (1997)
[34] Ondemir, O.; Gupta, S. M., A multi-criteria decision making model for advanced repair-to-order and disassembly-to-order system, European Journal of Operational Research, 233, 408-419, (2014) · Zbl 1305.90234
[35] Pan, Q.-K.; Tasgetiren, M. F.; Liang, Y.-C., A discrete particle swarm optimization algorithm for the no-wait flowshop scheduling problem, Computers & Operations Research, 35, 2807-2839, (2008) · Zbl 1144.90393
[36] Pan, Q.-K.; Tasgetiren, M. F.; Suganthan, P. N.; Chua, T. J., A discrete artificial bee colony algorithm for the lot-streaming flow shop scheduling problem, Information Sciences, 181, 2455-2468, (2011)
[37] Rai, R.; Rai, V.; Tiwari, M.; Allada, V., Disassembly sequence generation: A Petri net based heuristic approach, International Journal of Production Research, 40, 3183-3198, (2002) · Zbl 1038.90013
[38] Ren, Y.; Tian, G.; Zhao, F.; Yu, D.; Zhang, C., Selective cooperative disassembly planning based on multi-objective discrete artificial bee colony algorithm, Engineering Applications of Artificial Intelligence, 64, 415-431, (2017)
[39] Ren, Y.; Zhang, C.; Zhao, F.; Tian, G.; Lin, W.; Meng, L., Disassembly line balancing problem using interdependent weights-based multi-criteria decision making and 2-optimal algorithm, Journal of Cleaner Production, 174, 1475-1486, (2018)
[40] Ren, Y.; Yu, D.; Zhang, C.; Zhao, F.; Tian, G.; Meng, L., An improved gravitational search algorithm for profit-oriented partial disassembly line balancing problem, International Journal of Production Research, 55, 7302-7316, (2017)
[41] Seo, K.-K.; Park, J.-H.; Jang, D.-S., Optimal disassembly sequence using genetic algorithms considering economic and environmental aspects, The International Journal of Advanced Manufacturing Technology, 18, 371-380, (2001)
[42] Shan, H.; Li, S.; Huang, J.; Gao, Z.; Li, W., Ant colony optimization algorithm-based disassembly sequence planning, (Proceedings of the International Conference on Mechatronics and Automation, (2007), IEEE), 867-872
[43] Smith, S.; Hung, P.-Y., A novel selective parallel disassembly planning method for Green design, Journal of Engineering Design, 26, 283-301, (2015)
[44] Tang, Y.; Zhou, M.; Zussman, E.; Caudill, R., Disassembly modeling, planning and application: A review, (Proceedings of the IEEE International Conference on Robotics and Automation, vol. 3, (2000), IEEE), 2197-2202
[45] Tang, Y.; Zhou, M.; Zussman, E.; Caudill, R., Disassembly modeling, planning, and application, Journal of Manufacturing Systems, 21, 200-217, (2002)
[46] Tang, Y.; Zhou, M. C.; Caudill, R. J., An integrated approach to disassembly planning and demanufacturing operation, IEEE Transactions on Robotics & Automation, 17, 773-784, (2002)
[47] Tian, G.; Zhou, M.; Chu, J., A chance constrained programming approach to determine the optimal disassembly sequence, IEEE Transactions on Automation Science and Engineering, 10, 1004-1013, (2013)
[48] Wang, L.; Keshavarzmanesh, S.; Feng, H.-Y.; Buchal, R. O., Assembly process planning and its future in collaborative manufacturing: A review, The International Journal of Advanced Manufacturing Technology, 41, 132, (2009)
[49] Zha, X.; Lim, S., Assembly/disassembly task planning and simulation using expert Petri nets, International Journal of Production Research, 38, 15, 3639-3676, (2000) · Zbl 1093.90530
[50] Zhang, C. Y.; Li, P. G.; Guan, Z. L.; Rao, Y. Q., A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem, Computers & Operations Research, 34, 3229-3242, (2007) · Zbl 1123.90041
[51] Zhang, C. Y.; Li, P. G.; Rao, Y. Q.; Guan, Z. L., A very fast TS/SA algorithm for the job shop scheduling problem, Computers & Operations Research, 35, 282-294, (2008) · Zbl 1149.90345
[52] Zhang, C. Y.; Rao, Y. Q.; Li, P. G., An effective hybrid genetic algorithm for the job shop scheduling problem, International Journal of Advanced Manufacturing Technology, 39, 9-10, 965-974, (2008)
[53] Zhang, J.; Knoll, A., A two-arm situated artificial communicator for human-robot cooperative assembly, IEEE Transactions on Industrial Electronics, 50, 4, 651-658, (2003)
[54] Zhang, X. F.; Yu, G.; Hu, Z. Y.; Pei, C. H.; Ma, G. Q., Parallel disassembly sequence planning for complex products based on fuzzy-rough sets, The International Journal of Advanced Manufacturing Technology, 72, 231-239, (2014)
[55] Zhang, X. F.; Zhang, S. Y., Product cooperative disassembly sequence planning based on branch-and-bound algorithm, The International Journal of Advanced Manufacturing Technology, 51, 1139-1147, (2010)
[56] Zhong, L.; Youchao, S.; Ekene Gabriel, O.; Haiqiao, W., Disassembly sequence planning for maintenance based on metaheuristic method, Aircraft Engineering and Aerospace Technology, 83, 138-145, (2011)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.