×

A branch, bound, and remember algorithm for the simple disassembly line balancing problem. (English) Zbl 1458.90235

Summary: In this paper, we deal with a disassembly line balancing problem (DLBP), using an AND/OR graph (AOG) to represent the precedence relations between tasks. The decision maker needs to select a proper processing alternative and assigns the corresponding tasks among stations to minimise the number of stations, without violating the cycle time constraint and the precedence relations. The problem was first formulated by A. Koc et al. [“Two exact formulations for disassembly line balancing problems with task precedence diagram construction using an AND/OR graph”, IIE Trans. 41, No. 10, 866–881 (2009; doi:10.1080/07408170802510390)] and is denoted as type 1 simple DLBP (SDLBP-1) in this study. We prove that an SDLBP-1 with no parallel tasks is polynomially solvable and develop a branch, bound, and remember (BB&R) algorithm for the general SDLBP-1 with parallel tasks. Moreover, two lower bounding schemes, a strengthened Koc’s integer programming (IP) model and a new benchmark instance generation scheme are proposed. Computational results show that the BB&R algorithm is the state-of-the-art exact algorithm for SDLBP-1, and that it can be easily truncated into a state-of-the-art heuristic which optimally solves most instances in very short time. In addition, the lower bounds and the strengthened IP model are also demonstrated to be effective.

MSC:

90B30 Production models
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aydemir-Karadag, A.; Turkbey, O., Multi-objective optimization of stochastic disassembly line balancing with station paralleling, Comput. Ind. Eng., 65, 3, 413-425 (2013)
[2] Battaïa, O.; Dolgui, A., A taxonomy of line balancing problems and their solution approaches, Int. J. Prod. Econ., 142, 2, 259-277 (2013)
[3] Bentaha, ML; Battaïa, O.; Dolgui, A., A sample average approximation method for disassembly line balancing problem under uncertainty, Comput. Oper. Res., 51, 111-122 (2014) · Zbl 1348.90219
[4] Bentaha, ML; Battaïa, O.; Dolgui, A.; Hu, SJ, Dealing with uncertainty in disassembly line design, CIRP Ann. Manuf. Technol., 63, 1, 21-24 (2014)
[5] Bentaha, ML; Battaïa, O.; Dolgui, A., An exact solution approach for disassembly line balancing problem under uncertainty of the task processing times, Int. J. Prod. Res., 53, 6, 1807-1818 (2015)
[6] Bentaha, ML; Battaïa, O.; Dolgui, A.; Hu, SJ, Second order conic approximation for disassembly line design with joint probabilistic constraints, Eur. J. Oper. Res., 247, 3, 957-967 (2015) · Zbl 1346.90298
[7] Brucker, P., Scheduling Algorithms (2007), Springer-Verlag: Springer-Verlag Berlin · Zbl 1126.90001
[8] Fekete, SP; Schepers, J., New classes of fast lower bounds for bin packing problems, Math. Program., 91, 1, 11-31 (2001) · Zbl 1051.90020
[9] Fleszar, K.; Hindi, KS, An enumerative heuristic and reduction methods for the assembly line balancing problem, Eur. J. Oper. Res., 145, 3, 606-620 (2003) · Zbl 1011.90039
[10] Güngör, A.; Gupta, SM, Disassembly line balancing, (Proceedings of the 1999 Annual Meeting of the Northeast Decision Sciences Institute (1999)), 24-26
[11] Güngör, A.; Gupta, SM, A solution approach to the disassembly line balancing problem in the presence of task failures, Int. J. Prod. Res., 39, 7, 1427-1467 (2001)
[12] Güngör, A.; Gupta, SM, Disassembly line in product recovery, Int. J. Prod. Res., 40, 11, 2569-2589 (2002) · Zbl 1023.90507
[13] Hezer, S.; Kara, Y., A network-based shortest route model for parallel disassembly line balancing problem, Int. J. Prod. Res., 53, 6, 1849-1865 (2015)
[14] Hoffmann, TR, Assembly line balancing with a precedence matrix, Manag. Sci., 9, 4, 551-562 (1963)
[15] Kalayci, CB; Polat, O.; Gupta, SM, A hybrid genetic algorithm for sequence-dependent disassembly line balancing problem, Ann. Oper. Res., 242, 2, 321-354 (2016) · Zbl 1350.90009
[16] Kalaycılar, EG; Azizoğlu, M.; Yeralan, S., A disassembly line balancing problem with fixed number of workstations, Eur. J. Oper. Res., 249, 2, 592-604 (2016) · Zbl 1346.90614
[17] Koc, A.; Sabuncuoglu, I.; Erel, E., Two exact formulations for disassembly line balancing problems with task precedence diagram construction using an AND/OR graph, IIE Trans., 41, 10, 866-881 (2009)
[18] Lambert, AJ, Generation of assembly graphs by systematic analysis of assembly structures, Eur. J. Oper. Res., 168, 3, 932-951 (2006) · Zbl 1083.90508
[19] Mete, S.; Çil, ZA; Ağpak, K., A solution approach based on beam search algorithm for disassembly line balancing problem, J. Manuf. Syst., 41, 188-200 (2016)
[20] Özceylan, E.; Paksoy, T.; Bektaş, T., Modeling and optimizing the integrated problem of closed-loop supply chain network design and disassembly line balancing, Transp. Res. Part E Logis. Transp. Rev., 61, 142-164 (2014)
[21] Paksoy, T.; Güngör, A.; Özceylan, E., Mixed model disassembly line balancing problem with fuzzy goals, Int. J. Prod. Res., 51, 20, 6082-6096 (2013)
[22] Pereira, J., Empirical evaluation of lower bounding methods for the simple assembly line balancing problem, Int. J. Prod. Res., 53, 11, 3327-3340 (2015)
[23] Sewell, EC; Jacobson, SH, A branch, bound, and remember algorithm for the simple assembly line balancing problem, INFORMS J. Comput., 24, 3, 433-442 (2012) · Zbl 1462.90112
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.