A Hybrid Grasp-genetic Algorithm for Mixed-model Assembly Line Balancing Problem Type 2


  • Lakhdar Belkharroubi
  • Khadidja Yahyaoui




Mixed model assembly line, Cycle time, GRASP, Genetic Algorithm, RPW, Neighborhood search


In manufacturing systems, mixed model assembly lines are used to produce different products to deal with the problem of customers’ demands variety, and minimizing the cycle time in such assembly line is a critical problem. This paper addresses the mixed model assembly line balancing problem type 2 that consists in finding the optimal cycle time for a given number of workstations.  A hybrid Greedy randomized adaptive search procedure-Genetic algorithm is proposed to find the optimal assignment of tasks among workstations that minimize the cycle. A Ranked Positional Weight heuristic is used in the construction phase of the proposed GRASP, and in the local search phase, a neighborhood search procedure is used to ameliorate the constructed solutions in the construction phase. The GRASP is executed many times in order to seed the initial population of the proposed genetic algorithm, and the results of the executions are compared with the final solutions obtained by the hybrid GRASP-GA. In order to test the proposed approaches, a numerical example is used.


P. Sivasankaran and P. Shahabudeen, “Literature review of assembly line balancing problems,” Int J Adv Manuf Technol, vol. 73, no. 9–12, pp. 1665–1694, 2014. https://doi.org/10.1007/s00170-014-5944-y.

D. Krenczyk, B. Skolud, and A. Herok, “A heuristic and simulation hybrid approach for mixed and multi model assembly line balancing,” Intelligent Systems in Production Engineering and Maintenance, vol. 637, pp. 99–108, 2018. https://doi.org/10.1007/978-3-319-64465-3_10.

A. Yadav, P. Verma, and S. Agrawal, “Mixed model two-sided assembly line balancing problem: an exact solution approach,” Int J Syst Assur Eng Manag, vol. 11, no. S2, pp. 335–348, 2020. https://doi.org/10.1007/s13198-020-00956-1.

M. M. Razali, M. F. F. Ab. Rashid, and M. R. A. Make, “Mathematical modelling of mixed-model assembly line balancing problem with resources constraints,” IOP Conf. Ser.: Mater. Sci. Eng., vol. 160, p. 012002, 2016. https://doi.org/10.1088/1757-899X/160/1/012002.

J. I. van Zante-de Fokkert and A. G. de Kok, “The mixed and multi model line balancing problem: a comparison,” European Journal of Operational Research, vol. 100, no. 3, pp. 399-412, 1997. https://doi.org/10.1016/S0377-2217(96)00162-2.

O. Banjo, D. Stewart, and M. Fasli, “Optimising mixed model assembly lines for mass customisation: A multi agent systems approach,” Advances in Manufacturing Technology, vol. 3, pp. 337-342, 2016.

T. Ziarnetzky, L. Mönch, and A. Biele, “Simulation of low-volume mixed model assembly lines: Modeling aspects and case study,” Proceedings of the 2014 Winter Simulation Conference, 2014, pp. 2101-2112. https://doi.org/10.1109/WSC.2014.7020055.

B. Yuan, C. Zhang, X. Shao, and Z. Jiang, “An effective hybrid honey bee mating optimization algorithm for balancing mixed-model two-sided assembly lines,” Computers & Operations Research, vol. 53, pp. 32–41, 2015. https://doi.org/10.1016/j.cor.2014.07.011.

J.-H. Zhang, A.-P. Li, and X.-M. Liu, “Hybrid genetic algorithm for a type-II robust mixed-model assembly line balancing problem with interval task times,” Adv. Manuf, vol. 7, pp. 117-132, 2019. https://doi.org/10.1007/s40436-019-00256-3.

P. Su and Y. Lu, “Combining genetic algorithm and simulation for the mixed model assembly line balancing problem,” Proceedings of the Third International Conference on Natural Computation, 2007, pp. 314-318. https://doi.org/10.1109/ICNC.2007.306.

M. G. C. Resende and C. C. Ribeiro, “Greedy randomized adaptive search procedures,” HandBook of Metaheuristics, vol. 272, pp. 169-220, 2003. https://doi.org/10.1007/978-3-319-91086-4_6.

G. Abdul-Nour, H. Beaudoin., P. Ouellet, R. Rochette, S. Lambert, “A reliability based maintenance policy: a case study,” Computers and Industrial Engineering, vol. 35, no. 3- 4, pp. 591-594, 1998. https://doi.org/10.1016/S0360-8352(98)00166-1.

P. R. McMullen, & G. V. Frazier, “A heuristic for solving mixed-modelline balancing problems with stochastic task durations and parallel stations,” International Journal Production Economics, vol. 51, pp. 177-190. 1997. https://doi.org/10.1016/S0925-5273(97)00048-0.

M. Rabbania, Z. Mousavia, and H. Farrokhi-Aslb, “Multi-objective metaheuristics for solving a type II robotic mixed-mode assembly line balancing problem,” Journal of Industrial and Production Engineering, vol. 33, no. 7, pp. 472-482, 2016. https://doi.org/10.1080/21681015.2015.1126656.

A. S. V. Raj, J. Mathew, P. Jose, and G. Sivan, “Optimization of cycle time in an assembly line balancing problem,” Procedia Technology, vol. 25, pp. 1146–1153, 2016. https://doi.org/10.1016/j.protcy.2016.08.231.

D. Thiruvady, A. Nazari, and A. Elmi, “An ant colony optimisation based heuristic for mixed-model assembly line balancing with setups,” Proceedings of the 2020 IEEE Congress on Evolutionary Computation (CEC), Glasgow, United Kingdom, 2020, pp. 1–8. https://doi.org/10.1109/CEC48606.2020.9185757.

M. Lalaoui and A. E. Afia, “A versatile generalized simulated annealing using type-2 fuzzy controller for the mixed-model assembly line balancing problem,” IFAC-PapersOnLine, vol. 52, no. 13, pp. 2804–2809, 2019. https://doi.org/10.1016/j.ifacol.2019.11.633.

I. Baybars, “A survey of exact algorithms for the simple assembly line balancing problem,” Management Science, vol. 32, no. 8, pp 909-932, 1986. https://doi.org/10.1287/mnsc.32.8.909.

H. Du, Z. Wang, W. Zhan and J. Guo, “Elitism and distance strategy for selection of evolutionary algorithms,” IEEE Access, vol. 6, pp. 44531-44541, 2018. https://doi.org/10.1109/ACCESS.2018.2861760.

R. O. Edokpia and F. U. Owu, “Assembly line re-balancing using ranked positional weight technique and longest operating time technique: A comparative analysis,” AMR, vol. 824, pp. 568–578, 2013. https://doi.org/10.4028/www.scientific.net/AMR.824.568.

R. Martí, M. G. C. Resende, and P. M. Pardalos, Handbook of Heuristics, Springer, pp. 741-758, 2018. https://doi.org/10.1007/978-3-319-07124-4.

N. Boysen, M. Kiel, and A. Scholl, “Sequencing mixed-model assembly lines to minimise the number of work overload situations,” International Journal of Production Research, vol. 49, no. 16, pp. 4735–4760, 2011. https://doi.org/10.1080/00207543.2010.507607.




How to Cite

Belkharroubi, L., & Yahyaoui, K. (2021). A Hybrid Grasp-genetic Algorithm for Mixed-model Assembly Line Balancing Problem Type 2. International Journal of Computing, 20(3), 424-432. https://doi.org/10.47839/ijc.20.3.2289