Landscape Analysis and a Hybrid Iterated Local Search (HILS) for Solving Simple Assembly Line Balancing Problem type 2 (SALBP2)

Document Type : Research Paper

Authors

Department of Industrial Engineering, Faculty of Engineering, University of Kashan, Kashan, Iran

10.22070/jqepo.2021.13856.1175

Abstract

The Assembly Line Balancing (ALB) problem is one of the subproblems of the Assembly Planning(AP) problem and is defined as the process of partitioning the assembly operations into a set of tasks and assigning them to assembly workstations such that all workstations approximately have equal times. The most basic model in ALB is the Simple Assembly Line Balancing Problem for type 2 (SALBP2). The mentioned problem is an NP-hard problem and thus many researchers in the field tried to find an effective and efficient solution for it. However, the fitness landscape of this problem has not been yet studied despite the existence of numerous works on solving it. In this article, different statistical correlation and distribution measures are used and calculated in order to analyze the fitness landscape of the SALBP2 problem for 44 test problems. The results reveal that the problem's landscape is approximately uniform based on the distribution of the locally optimal assembly sequences. Therefore, for obtaining an effective and efficient solution to SALBP2 a suitable Hybrid Iterated Local Search (HILS) is designated and used to solve a number of SALBP2 problems. Comparison results with the other approaches in the SALBP2 literature represent that the HILS produces the optimal or best known solutions on most problem instances, and it performs better than other algorithms.

Keywords

References

Alakaş, H. M. (2021), "General resource-constrained assembly line balancing problem: conjunction normal form based constraint programming models," Soft Computing, 25 (8), 6101-6111.
Alavidoost, M., Babazadeh, H., and Sayyari, S. (2016), "An interactive fuzzy programming approach for bi-objective straight and U-shaped assembly line balancing problem," Applied Soft Computing, 40, 221-235.
Anderson, E. J., and Ferris, M. C. (1994), "Genetic algorithms for combinatorial optimization: the assemble line balancing problem," ORSA Journal on Computing, 6 (2), 161-173.
Battaïa, O., and Dolgui, A. (2013), "A taxonomy of line balancing problems and their solutionapproaches," International Journal of Production Economics, 142 (2), 259-277.
Bautista, J., and Pereira, J. (2007), "Ant algorithms for a time and space constrained assembly line balancing problem," European Journal of Operational Research, 177 (3), 2016-2032.
Beham, A., Pitzer, E., Wagner, S., and Affenzeller, M. 2017. Integrating Exploratory Landscape Analysis into Metaheuristic Algorithms. In International Conference on Computer Aided Systems Theory: Springer.
Belver, M., Gomez, A., Lopez, J., De la Fuente, D., and Ponte, B. 2017. Solving Vehicle Routing Problem with Multiple Trips using Iterative Local Search with Variable Neighborhood Search. In Proceedings on the International Conference on Artificial Intelligence (ICAI): The Steering Committee of The World Congress in Computer Science.
Blum, C. (2011), "Iterative beam search for simple assembly line balancing with a fixed number of work stations," SORT, 35 (2), 145-164.
Buyukozkan, K., Kucukkoc, I., Satoglu, S. I., and Zhang, D. Z. (2016), "Lexicographic bottleneck mixed-model assembly line balancing problem: artificial bee colony and tabu search approaches with optimised parameters," Expert Systems with Applications, 50, 151-166.
Capacho Betancourt, L. (2007), "ASALBP: the alternative subgraphs assembly line balancing problem. Formalization and resolution procedures," PHD thesis, Technical University of Catalonia.
Chantarasamai, K., and Lasunon, O.-U. (2021), "Modified Differential Evolution Algorithm for U-Shaped Assembly Line Balancing Type 2."
Chiang, W.-C. (1998), "The application of a tabu search metaheuristic to the assembly line balancing problem," Annals of Operations Research, 77, 209-227.
Eghtesadifard, M., Khalifeh, M., and Khorram, M. (2020), "A systematic review of research themes and hot topics in assembly line balancing through the web of science within 1990–2017," Computers & Industrial Engineering, 139, 106182.
Esmaeilbeigi, R., Naderi, B., and Charkhgard, P. (2015), "The type E simple assembly line balancing problem: A mixed integer linear programming formulation," Computers & Operations Research, 64, 168-177.
Ghandi, S., and Masehian, E. (2015), "A breakout local search (BLS) method for solving the assembly sequence planning problem," Engineering applications of artificial intelligence, 39, 245-266.
González-Almagro, G., Luengo, J., Cano, J.-R., and García, S. (2020), "DILS: constrained clustering through Dual Iterative Local Search," Computers & Operations Research, 104979.
Hackman, S. T., Magazine, M. J., and Wee, T. (1989), "Fast, effective algorithms for simple assembly line balancing problems," Operations Research, 37 (6), 916-924.
Heinrici, A. (1994), "A comparison between simulated annealing and tabu search with an example from the production planning," in Operations research proceedings 1993: Springer, pp. 498-503.
Jana, N. D., Sil, J., and Das, S. (2017), "Selection of appropriate metaheuristic algorithms for protein structure prediction in AB off-lattice model: a perspective from fitness landscape analysis," Information Sciences, 391, 28-64.
Jirasirilerd, G., Pitakaso, R., Sethanan, K., Kaewman, S., Sirirak, W., and Kosacka–Olejnik, M. (2020), "Simple Assembly Line Balancing Problem Type 2 By Variable Neighborhood Strategy Adaptive Search: A Case Study Garment Industry," Journal of Open Innovation: Technology, Market, and Complexity, 6 (1), 21.
Kilincci, O. (2010), "A Petri net-based heuristic for simple assembly line balancing problem of type 2," The International Journal of Advanced Manufacturing Technology, 46 (1-4), 329-338.
Klein, R., and Scholl, A. (1996), "Maximizing the production rate in simple assembly line balancing—a branch and bound procedure," European Journal of Operational Research, 91 (2), 367-385.
Kriengkorakot, N., and Pianthong, N. (2012), "The assembly line balancing problem: review articles," Engineering and Applied Science Research, 34 (2), 133-140.
Li, Z., Kucukkoc, I., and Tang, Q. (2021), "Enhanced branch-bound-remember and iterative beam search algorithms for type II assembly line balancing problem," Computers & Operations Research, 131, 105235.
Liu, X., Yang, X., and Lei, M. (2021), "Optimisation of mixed-model assembly line balancing problem under uncertain demand," Journal of Manufacturing Systems, 59, 214-227
Malan, K. M., and Engelbrecht, A. P. (2014), "Fitness landscape analysis for metaheuristic performance prediction," in Recent advances in the theory and application of fitness landscapes: Springer, pp. 103-132.
McNaughton, R. (1959), "Scheduling with deadlines and loss functions," Management Science, 6 (1), 1-12.
Merengo, C., Nava, F., and Pozzetti, A. (1999), "Balancing and sequencing manual mixed-model assembly lines," International Journal of Production Research, 37 (12), 2835-2860.
Nagata, Y., and Ono, I. (2018), "A guided local search with iterative ejections of bottleneck operations for the job shop scheduling problem," Computers & Operations Research, 90, 60-71.
Nearchou, A. C. (2008), "Multi-objective balancing of assembly lines by population heuristics," International Journal of Production Research, 46 (8), 2275-2297.
Nourmohammadi, A., Fathi, M., and Ng, A. H. 2019. Choosing efficient meta-heuristics to solve the assembly line balancing problem: A landscape analysis approach. In Procedia CIRP: Elsevier.
Penna, P. H. V., Afsar, H. M., Prins, C., and Prodhon, C. (2016), "A hybrid iterative local search algorithm for the electric fleet size and mix vehicle routing problem with time windows and recharging stations," IFAC-PapersOnLine, 49 (12), 955-960.
Pinarbasi, M., Alakas, H. M., and Yuzukirmizi, M. (2019), "A constraint programming approach to type-2 assembly line balancing problem with assignment restrictions," Assembly Automation.
Pitakaso, R., Sethanan, K., Jirasirilerd, G., and Golinska-Dawson, P. (2021), "A novel variable neighborhood strategy adaptive search for SALBP-2 problem with a limit on the number of machine’s types," Annals of Operations Research, 1-25.
Rashid, M. F. F., Hutabarat, W., and 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.
Razali, M. M., Kamarudin, N. H., Rashid, M. F. F. A., and Rose, A. N. M. (2019), "Recent trend in mixed-model assembly line balancing optimization using soft computing approaches," Engineering Computations.
Scholl, A., and 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.
Sepahi, A., and Naini, S. G. J. (2016), "Two-sided assembly line balancing problem with parallel performance capacity," Applied Mathematical Modelling, 40 (13-14), 6280-6292.
Sotskov, Y. N., Dolgui, A., Lai, T.-C., and Zatsiupa, A. (2015), "Enumerations and stability analysis of feasible and optimal line balances for simple assembly lines," Computers & Industrial Engineering, 90, 241-258.
Sungur, B., and Yavuz, Y. (2015), "Assembly line balancing with hierarchical worker assignment," Journal of Manufacturing Systems, 37, 290-298.
Talbi, E.-G. (2009), Metaheuristics: from design to implementation (Vol. 74): John Wiley & Sons.
Wang, M., Li, B., Zhang, G., and Yao, X. (2017), "Population evolvability: Dynamic fitness landscape analysis for population-based metaheuristic algorithms," IEEE Transactions on Evolutionary Computation, 22 (4), 550-563.
Wang, X., Shao, S., and Tang, J. (2020), "Iterative Local-Search Heuristic for Weighted Vehicle Routing Problem," IEEE Transactions on Intelligent Transportation Systems.
Watanabe, T., Hashimoto, Y., Nishikawa, I., and Tokumaru, H. (1995), "Line balancing using a genetic evolution model," Control Engineering Practice, 3 (1), 69-76.
Yadav, A., Kulhary, R., Nishad, R., and Agrawal, S. (2019), "Parallel two-sided assembly line balancing with tools and tasks sharing," Assembly Automation.
Zhang, H., Yan, Q., Liu, Y., and Jiang, Z. (2016), "An integer-coded differential evolution algorithm for simple assembly line balancing problem of type 2," Assembly Automation.
Zheng, Q., Li, M., Li, Y., and Tang, Q. (2013), "Station ant colony optimization for the type 2 assembly line balancing problem," The International Journal of Advanced Manufacturing Technology, 66 (9-12), 1859-1870.
Zohali, H., Naderi, B., and Roshanaei, V. (2021), "Solving the Type-2 Assembly Line Balancing with Setups Using Logic-Based Benders Decomposition," INFORMS Journal on Computing.
Journal of Quality Engineering and Production Optimization
Volume 7, Issue 1
May 2022
Pages 25-53

Files

Share

How to cite

Statistics