Fitness landscape analysis of the simple assembly line balancing problem type 1

Ghandi, S.; Masehian, E.

Abstract: As the simple assembly line balancing problem type 1 (SALBP1) has been proven to be NP-hard, heuristic and metaheuristic approaches are widely used for solving middle to large instances. Nevertheless, the characteristics (fitness landscape) of the problem’s search space have not been studied so far and no rigorous justification for implementing various metaheuristic methods has been presented. Aiming to fill this gap in the literature, this study presents the first comprehensive and in-depth Fitness Landscape Analysis (FLA) study for SALBP1. The FLA was performed by generating a population of 1000 random solutions and improving them to local optimal solution, and then measuring various statistical indices such as average distance, gap, entropy, amplitude, length of the walk, autocorrelation, and fitness-distance among all solutions, to understand the complexity, structure, and topology of the solution space. We solved 83 benchmark problems with various cycle times taken from Scholl’s dataset which required 83000 local searches from initial to optimal solutions. The analysis showed that locally optimal assembly line balances in SALBP1 are distributed nearly uniformly in the landscape of the problem, and the small average difference between the amplitudes of the initial and optimal solutions implies that the landscape was almost plain. In addition, the large average gap between local and global solutions showed that global optimum solutions in SALBP1 are difficult to find, but the problem can be effectively solved using a single-solution-based metaheuristic to near-optimality. In addition to the FLA, a new mathematical formulation for the entropy (diversity) of solutions in the search space for SALBP1 is also presented in this paper.

How to cite this paper

 Ghandi, S & Masehian, E. (2023). Fitness landscape analysis of the simple assembly line balancing problem type 1.International Journal of Industrial Engineering Computations , 14(4), 589-608.

References

Abdeljaouad, M. A., & Klement, N. (2021). Tabu search algorithm for single and multi-model line Balancing problems. In Advances in Production Management Systems. Artificial Intelligence for Sustainable and Resilient Production Systems: IFIP WG 5.7 International Conference, APMS 2021, Nantes, France, September 5–9, 2021, Proceedings, Part I (pp. 409-415). Springer International Publishing.
Álvarez-Miranda, E., Pereira, J., Torrez-Meruvia, H., & Vilà, M. (2021). A Hybrid Genetic Algorithm for the Simple Assembly Line Balancing Problem with a Fixed Number of Workstations. Mathematics, 9(17), 2157.
Álvarez-Miranda, E., Pereira, J., Vargas, C., & Vilà, M. (2022). Variable-depth local search heuristic for assembly line balancing problems. International Journal of Production Research, 61(9), 3103-3121.
Baskar, A., & Xavior, M. A. (2020). Heuristics based on slope indices for simple type I assembly line balancing problems and analyzing for a few performance measures. Materials Today: Proceedings, 22, 3171-3180.
Bautista, J., & Pereira, J. (2002, August). Ant algorithms for assembly line balancing. In International Workshop on Ant Algorithms (pp. 65-75). Berlin, Heidelberg: Springer Berlin Heidelberg.
Bautista, J., & Pereira, J. (2007). Ant algorithms for a time and space constrained assembly line balancing problem. European Journal of Operational Research, 177(3), 2016-2032.
Baykasoglu, A. (2006). Multi-rule multi-objective simulated annealing algorithm for straight and U type assembly line balancing problems. Journal of Intelligent Manufacturing, 17(2), 217-232.
Boysen, N., Schulze, P., & Scholl, A. (2022). Assembly line balancing: What happened in the last fifteen years?. European Journal of Operational Research, 301(3), 797-814.
Capacho Betancourt, L. (2007). ASALBP: the alternative subgraphs assembly line balancing problem. Formalization and resolution procedures [PHD thesis, Technical University of Catalonia].
Chutima, P. (2022). A comprehensive review of robotic assembly line balancing problem. Journal of Intelligent Manufacturing, 33(1), 1-34.
Dolgui, A., & Gafarov, E. (2019). Can a Branch and Bound algorithm solve all instances of SALBP-1 efficiently? IFAC-PapersOnLine, 52(13), 2788-2791.
Dou, J., Li, J., & Zhao, X. (2017). A novel discrete particle swarm algorithm for assembly line balancing problems. Assembly Automation, 37(4), 452-463.
Fathi, M., Fontes, D. B. M. M., Urenda Moris, M., & Ghobakhloo, M. (2018). Assembly line balancing problem: A comparative evaluation of heuristics and a computational assessment of objectives. Journal of Modelling in Management, 13(2), 455-474.
Ghandi, S., & Masehian, E. (2015). A breakout local search (BLS) method for solving the assembly sequence planning problem. Engineering applications of artificial intelligence, 39, 245-266.
Ghandi, S., & Masehian, E. (2015). Review and taxonomies of assembly and disassembly path planning problems and approaches. Computer-Aided Design, 67, 58-86.
Gonçalves, J. F., & De Almeida, J. R. (2002). A hybrid genetic algorithm for assembly line balancing. Journal of heuristics, 8, 629-642.
Hackman, S. T., Magazine, M. J., & Wee, T. (1989). Fast, effective algorithms for simple assembly line balancing problems. Operations research, 37(6), 916-924.
Helgeson, W., & Birnie, D. P. (1961). Assembly line balancing using the ranked positional weight technique. Journal of industrial engineering, 12(6), 394-398.
Hong, D. S., & Cho, H. S. (1999, October). Generation of robotic assembly sequences using a simulated annealing. In Proceedings 1999 IEEE/RSJ International Conference on Intelligent Robots and Systems. Human and Environment Friendly Robots with High Intelligence and Emotional Quotients (Cat. No. 99CH36289) (Vol. 2, pp. 1247-1252). IEEE.
Hu, Y., Liu, C., Zhang, M., Jia, Y., & Xu, Y. (2023). A novel simulated annealing-based hyper-heuristic algorithm for stochastic parallel disassembly line balancing in smart remanufacturing. Sensors, 23(3), 1652.
Kilincci, O. (2011). Firing sequences backward algorithm for simple assembly line balancing problem of type 1. Computers & Industrial Engineering, 60(4), 830-839.
Li, Z., Janardhanan, M. N., Nielsen, P., & Tang, Q. (2018). Mathematical models and simulated annealing algorithms for the robotic assembly line balancing problem. Assembly Automation, 38(4), 420-436.
Meng, K., Tang, Q., Zhang, Z., & Yu, C. (2021). Solving multi-objective model of assembly line balancing considering preventive maintenance scenarios using heuristic and grey wolf optimizer algorithm. Engineering applications of artificial intelligence, 100, 104183.
Mohammed, F. D., Zakaria, M. Z., Ramli, M. F., Jusoh, M., Azizan, M., & Fadzli, N. (2021, May). Metaheuristic optimization in solving assembly line balancing problems: A short review. In AIP Conference Proceedings (Vol. 2339, No. 1). AIP Publishing.
Nagy, L., Ruppert, T., & Abonyi, J. (2020). Analytic hierarchy process and multilayer network-based method for assembly line balancing. Applied Sciences, 10(11), 3932.
Nourmohammadi, A., Fathi, M., & Ng, A. H. (2019). Choosing efficient meta-heuristics to solve the assembly line balancing problem: A landscape analysis approach. Procedia CIRP, 81, 1248-1253.
Özbakır, L., & Seçme, G. (2022). A hyper-heuristic approach for stochastic parallel assembly line balancing problems with equipment costs. Operational Research, 1-38.
Pape, T. (2015). Heuristics and lower bounds for the simple assembly line balancing problem type 1: Overview, computational tests and improvements. European Journal of Operational Research, 240(1), 32-42.
Pastor, R., & Ferrer, L. (2009). An improved mathematical program to solve the simple assembly line balancing problem. International Journal of Production Research, 47(11), 2943-2959.
Ponnambalam, S., Aravindan, P., & Naidu, G. M. (2000). A multi-objective genetic algorithm for solving assembly line balancing problem. The International Journal of Advanced Manufacturing Technology, 16(5), 341-352.
Rashid, M. F. F., Hutabarat, W., & Tiwari, A. (2012). A review on assembly sequence planning and assembly line balancing optimisation using soft computing approaches. The International Journal of Advanced Manufacturing Technology, 59(1-4), 335-349.
Ravelo, S. V. (2022). Approximation algorithms for simple assembly line balancing problems. Journal of Combinatorial Optimization, 43(2), 432-443.
Scholl, A., & Becker, C. (2006). State-of-the-art exact and heuristic solution procedures for simple assembly line balancing. European Journal of Operational Research, 168(3), 666-693.
Scholl, A., & Voß, S. (1997). Simple assembly line balancing—Heuristic approaches. Journal of Heuristics, 2, 217-244.
Seçme, G., & Özbakır, L. (2019). An assembly line balancing application on oven production line with hyper-heuristics. International Journal of Operations Research and Information Systems (IJORIS), 10(3), 44-58.
Talbi, E.-G. (2009). Metaheuristics: from design to implementation (Vol. 74). John Wiley & Sons.
Talbot, F. B., Patterson, J. H., & Gehrlein, W. V. (1986). A comparative evaluation of heuristic line balancing techniques. Management science, 32(4), 430-454.
Vilà, M., & Pereira, J. (2013). An enumeration procedure for the assembly line balancing problem based on branching by non-decreasing idle time. European Journal of Operational Research, 229(1), 106-113.
Wei, N.-C., & Chao, I.-M. (2011). A solution procedure for type E simple assembly line balancing problem. Computers & Industrial Engineering, 61(3), 824-830.
Yadav, A., Kulhary, R., Nishad, R., & Agrawal, S. (2020). Parallel two-sided assembly line balancing with tools and tasks sharing. Assembly Automation, 40(6), 833-846.
Zhang, H. Y. (2019). An immune genetic algorithm for simple assembly line balancing problem of type 1. Assembly Automation, 39(1), 113-123.
Zhong, Y.-g., & Ai, B. (2017). A modified ant colony optimization algorithm for multi-objective assembly line balancing. Soft Computing, 21(22), 6881-6894.