Optimizing the first type of U-shaped assembly line balancing problems

Document Type : Original Article


1 Computer Engineering Department, Eastern Mediterranean University, Via Mersin 10, Famagusta, TRNC, Turkey

2 Department of Industrial Engineering, Girne American University, Via Mersin 10, Kyrenia, TRNC, Turkey

3 Industrial Engineering Department, Girne American University, Via Mersin 10, Kyrenia, TRNC, Turkey


In the literature, there are various types of assembly line balancing problems. Consequently, different types of solution approaches such as exact, heuristic, and metaheuristics have been proposed to solve such problems. In this research, we are going to propose a metaheuristic solution method based on applied grouping evolution strategies to solve the u-shaped assembly line balancing problem where the aim is the minimization of the number of workstations considering a given cycle time for the assembly line. By introducing the just-in-time (JIT) production principle, it can be proven that the U-shaped assembly line system has a better performance than the traditional straight-line system. Different test problems from the literature are solved and key indexes like the line efficiency, smoothness index, and variation, are calculated for the problems. Then the proposed method is compared to one of the recent solutions approached based on the genetic algorithm. The results show that the proposed method has the potential t be considered as one of the most efficient methods in this field.


ARCUS*, A. L. (1965). A computer method of sequencing operations for assembly lines. International Journal of Production Research, 4(4), 259-277.‏
Becker, C., & Scholl, A. (2006). A survey on problems and methods in generalized assembly line balancing. European journal of operational research, 168(3), 694-715.‏
Beyer, H. G., & Schwefel, H. P. (2002). Evolution strategies–a comprehensive introduction. Natural computing, 1(1), 3-52.‏
Boros, P., Fehér, O., Lakner, Z., Niroomand, S., & Vizvári, B. (2016). Modeling supermarket re-layout from the owner’s perspective. Annals of Operations Research238(1-2), 27-40.
Boysen, N., Fliedner, M., & Scholl, A. (2007). A classification of assembly line balancing problems. European journal of operational research, 183(2), 674-693.‏
Dorigo, M., Birattari, M., & Stutzle, T. (2006). Ant colony optimization. IEEE computational intelligence magazine, 1(4), 28-39.‏
Erel, E., Sabuncuoglu, I., & Aksu, B. A. (2001). Balancing of U-type assembly systems using simulated annealing. International Journal of Production Research, 39(13), 3003-3015.‏
Falkenauer, E. (1994). A new representation and operators for genetic algorithms applied to grouping problems. Evolutionary computation, 2(2), 123-144.‏
Fathi, M., Alvarez, M. J., & Rodríguez, V. (2011). A new heuristic approach to solving u-shape assembly line balancing problems type-1. International Journal of Industrial and Manufacturing Engineering, 5(11), 2115-2123.‏
Ghadiri Nejad, M., & Banar, M. (2018). Emergency response time minimization by incorporating ground and aerial transportation. Annals of Optimization Theory and Practice, 1(1), 43-57.‏
Ghadiri Nejad, M., Gueden, H., Vizvari, B., & Vatankhah Barenji, R. (2018). A mathematical model and simulated annealing algorithm for solving the cyclic scheduling problem of a flexible robotic cell. Advances in Mechanical Engineering, 10(1), 1687814017753912.‏
Ghadirinejad, M. A. Z. Y. A. R., & Mosallaeipour, S. (2013). A new approach to optimize a flexible manufacturing cell. In 1st international conference on new directions in business, management, finance and economics (Vol. 38).‏
GHADIRINEJAD, M., KASHAN, A. H., & RISMANCHIAN, F. (2013). A new competitive method for solving assembly line balancing problem. In 1st Int. Conf. New Directions in Business, Management, Finance and Economics.‏
Glonegger, M. and G. Reinhart, Planning of synchronized assembly lines taking into consideration human performance fluctuations. Production Engineering, 2015. 9(2): p. 277-287.
Gökçen, H., & Agˇpak, K. (2006). A goal programming approach to simple U-line balancing problem. European journal of operational research, 171(2), 577-585.‏
Gökçen, H., Ağpak, K., Gencer, C., & Kizilkaya, E. (2005). A shortest route formulation of simple U-type assembly line balancing problem. Applied Mathematical Modelling, 29(4), 373-380.‏
Helgeson, W. B., & Birnie, D. P. (1961). Assembly line balancing using the ranked positional weight technique. Journal of industrial engineering, 12(6), 394-398.‏
Hwang, R. K., Katayama, H., & Gen, M. (2008). U-shaped assembly line balancing problem with genetic algorithm. International Journal of Production Research, 46(16), 4637-4649.‏
Jayaswal, S., & Agarwal, P. (2014). Balancing U-shaped assembly lines with resource dependent task times: A Simulated Annealing approach. Journal of Manufacturing Systems, 33(4), 522-534.‏
Kashan, A. H., Jenabi, M., & Kashan, M. H. (2009, December). A new solution approach for grouping problems based on evolution strategies. In 2009 International Conference of Soft Computing and Pattern Recognition (pp. 88-93). IEEE.‏
Kashan, A. H., Kashan, M. H., & Karimiyan, S. (2013). A particle swarm optimizer for grouping problems. Information Sciences, 252, 81-95.‏
Kumar, N., & Mahto, D. (2013). Assembly line balancing: a review of developments and trends in approach to industrial application. Global Journal of Research In Engineering.‏
Li, X., & Zhang, K. (2018). Single batch processing machine scheduling with two-dimensional bin packing constraints. International Journal of Production Economics, 196, 113-121.‏
López-Ibáñez, M., Stützle, T., & Dorigo, M. (2015). Ant Colony Optimization: A Component-Wise Overview.‏
Miltenburg, G. J., & Wijngaard, J. (1994). The U-line line balancing problem. Management science, 40(10), 1378-1388.‏
Miltenburg, J., & Sparling, D. (1995). Optimal solution algorithms for the U-line balancing problem. Relatrio tecnico, McMaster University, Hamilton, Canada. Citado na.‏
Mirzaei, N., Niroomand, S., & Zare, R. (2016). Application of statistical process control in service industry: A case study of the restaurant sector. Journal of Modelling in Management.
Monden, Y. (2011). Toyota production system: an integrated approach to just-in-time. CRc Press.‏
Mosa, M. A., Hamouda, A., & Marei, M. (2017). Graph coloring and ACO based summarization for social networks. Expert Systems with Applications, 74, 115-126.‏
Mosallaeipour, S., Nazerian, R., & Ghadirinejad, M. (2018). A Two-Phase Optimization Approach for Reducing the Size of the Cutting Problem in the Box-Production Industry: A Case Study. In Industrial Engineering in the Industry 4.0 Era (pp. 63-81). Springer, Cham.‏
Mosallaeipour, S., Nejad, M. G., Shavarani, S. M., & Nazerian, R. (2018). Mobile robot scheduling for cycle time optimization in flow-shop cells, a case study. Production Engineering, 12(1), 83-94.‏
Nadimi-Shahraki, M. H., Taghian, S., & Mirjalili, S. (2021). An improved grey wolf optimizer for solving engineering problems. Expert Systems with Applications, 166, 113917.‏
Nejad, M. G., & Kashan, A. H. (2019). An Effective Grouping Evolution Strategy Algorithm Enhanced with Heuristic Methods for Assembly Line Balancing Problem. Journal of Advanced Manufacturing Systems, 18(03), 487-509.‏
Nejad, M. G., Güden, H., & Vizvári, B. (2019). Time minimization in flexible robotic cells considering intermediate input buffers: a comparative study of three well-known problems. International Journal of Computer Integrated Manufacturing, 32(8), 809-819.‏
Nejad, M. G., Kashan, A. H., & Shavarani, S. M. (2018). A novel competitive hybrid approach based on grouping evolution strategy algorithm for solving U-shaped assembly line balancing problems. Production Engineering, 12(5), 555-566.‏
Nejad, M. G., Kovács, G., Vizvári, B., & Barenji, R. V. (2018). An optimization model for cyclic scheduling problem in flexible robotic cells. The International Journal of Advanced Manufacturing Technology, 95(9), 3863-3873.‏
Nejad, M. G., Shavarani, S. M., Güden, H., & Barenji, R. V. (2019). Process sequencing for a pick-and-place robot in a real-life flexible robotic cell. The International Journal of Advanced Manufacturing Technology, 103(9), 3613-3627.‏
Nejad, M. G., Shavarani, S. M., Vizvári, B., & Barenji, R. V. (2018). Trade-off between process scheduling and production cost in cyclic flexible robotic cells. The International Journal of Advanced Manufacturing Technology, 96(1), 1081-1091.‏
Niroomand, S. (2018). A multi-objective based direct solution approach for linear programming with intuitionistic fuzzy parameters. Journal of Intelligent & Fuzzy Systems35(2), 1923-1934.
Niroomand, S., Bazyar, A., Alborzi, M., & Mahmoodirad, A. (2018). A hybrid approach for multi-criteria emergency center location problem considering existing emergency centers with interval type data: a case study. Journal of Ambient Intelligence and Humanized Computing9(6), 1999-2008.
Niroomand, S., Hadi-Vencheh, A., Mirzaei, N., & Molla-Alizadeh-Zavardehi, S. (2016). Hybrid greedy algorithms for fuzzy tardiness/earliness minimisation in a special single machine scheduling problem: case study and generalisation. International Journal of Computer Integrated Manufacturing29(8), 870-888.
Niroomand, S., Takács, S., & Vizvári, B. (2011). To lay out or not to lay out?. Annals of Operations Research191(1), 183-192.
Niroomand, S., & Vizvári, B. (2013). A mixed integer linear programming formulation of closed loop layout with exact distances. Journal of Industrial and Production Engineering30(3), 190-201.
Pereira, J. (2016). Procedures for the bin packing problem with precedence constraints. European Journal of Operational Research, 250(3), 794-806.‏
Pereira, J., Ritt, M., & Vásquez, Ó. C. (2018). A memetic algorithm for the cost-oriented robotic assembly line balancing problem. Computers & Operations Research, 99, 249-261.‏
Rechenberg, I. (1978). Evolutionsstrategien. In Simulationsmethoden in der Medizin und Biologie (pp. 83-114). Springer, Berlin, Heidelberg.‏
Salehi, M., Maleki, H. R., & Niroomand, S. (2020). Solving a new cost-oriented assembly line balancing problem by classical and hybrid meta-heuristic algorithms. Neural Computing and Applications32(12), 8217-8243.
Sanei, M., Mahmoodirad, A., & Niroomand, S. (2016). Two-stage supply chain network design problem with interval data. International Journal of e-Navigation and Maritime Economy5, 74-84.
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., & Klein, R. (1999). ULINO: Optimally balancing U-shaped JIT assembly lines. International Journal of Production Research, 37(4), 721-736.‏
Shavarani, S. M., Nejad, M. G., Rismanchian, F., & Izbirak, G. (2018). Application of hierarchical facility location problem for optimization of a drone delivery system: a case study of Amazon prime air in the city of San Francisco. The International Journal of Advanced Manufacturing Technology, 95(9), 3141-3153.‏
Taassori, M., Taassori, M., Niroomand, S., Vizvári, B., Uysal, S., & Hadi-Vencheh, A. (2015). OPAIC: An optimization technique to improve energy consumption and performance in application specific network on chips. Measurement74, 208-220.
Tavana, M., Santos-Arteaga, F. J., Mahmoodirad, A., Niroomand, S., & Sanei, M. (2018). Multi-stage supply chain network solution methods: hybrid metaheuristics and performance measurement. International Journal of Systems Science: Operations & Logistics5(4), 356-373.
Toklu, B., & özcan, U. (2008). A fuzzy goal programming model for the simple U-line balancing problem with multiple objectives. Engineering Optimization, 40(3), 191-204.‏
Vatankhah Barenji, R., Ghadiri Nejad, M., & Asghari, I. (2018). Optimally sized design of a wind/photovoltaic/fuel cell off-grid hybrid energy system by modified-gray wolf optimization algorithm. Energy & Environment, 29(6), 1053-1070.‏
Vizvari, B., Guden, H., & G Nejad, M. (2018). Local search based meta-heuristic algorithms for optimizing the cyclic flexible manufacturing cell problem. Annals of Optimization Theory and Practice, 1(3), 15-32.‏
Yuan, L., Qin, L., Lin, X., Chang, L., & Zhang, W. (2017). Effective and efficient dynamic graph coloring. Proceedings of the VLDB Endowment, 11(3), 338-351.‏