Solving a multi-objective mixed-model assembly line balancing and sequencing problem

Document Type : Research Paper


1 School of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran

2 College of Engineering, University of Tehran, Tehran, Iran

3 School of Industrial Engineering, Iran University of Science &Technology, Tehran, Iran


This research addresses the mixed-model assembly line (MMAL) by considering various constraints. In MMALs, several types of products which their similarity is so high are made on an assembly line. As a consequence, it is possible to assemble and make several types of products simultaneously without spending any additional time. The proposed multi-objective model considers the balancing and sequencing problems, simultaneously. Based on the assembly problem, the various tasks of models are assigned to the workstations, while in the sequencing problem, a sequence of models for production is determined. The two meta-heuristic algorithms, namely MOPSO and NSGA-II are used to solve the developed model and different comparison metrics are applied to compare these two proposed meta-heuristics. Several test problems based on empirical data is used to illustrate the performance of our proposed model. The results show that NSGA-II outperforms the MOPSO algorithm in most metrics used in this paper. Moreover, the results indicate that our proposed model is more effective and efficient to assignment of tasks and sequencing models than manual strategy. Finally, conclusion remarks and future research are provided. 


Main Subjects

Asefi, H., F. Jolai, M. Rabiee, and M. T. Araghi. 2014. “A hybrid NSGA-II and VNS for solving a bi-objective no-wait flexible flowshop scheduling problem.” The International Journal of Advanced Manufacturing Technology 75: 1017-1033.
Becker, C. and Scholl, A., 2006. A survey on problems and methods in generalized assembly line balancing. European Journal of Operational Research, 168 (3), 694–715.
Behnamian, J., S. F. Ghomi, and M. Zandieh. 2009. “A multi-phase covering Pareto-optimal front method to multi-objective scheduling in a realistic hybrid flowshop using a hybrid metaheuristic.” Expert Systems with Applications 36: 11057-11069.
Bock, S., Rosenberg, O., and Brackel, T.V., 2006. Controlling mixed-model assembly lines in real-time by using distributed systems. European Journal of Operational Research, 168 (3), 880–904.
Boysen, N., Fliedner, M., and Scholl, A., 2007. A classification of assembly line balancing problems. European Journal of Operational Research, 183 (2), 674–693.
Boysen, N., Fliedner, M., and Scholl, A., 2009. Sequencing mixed-model assembly lines: survey, classification and model critique. European Journal of Operational Research, 192 (2), 349–373.
Bukchin, J., Dar-El, E.M., and Rubinovitz, J., 2002. Mixed model assembly line design in a make-to-order environment. Computers & Industrial Engineering, 41 (4), 405–421.
Bukchin, Y. and Rabinowitch, I., 2006. A branch-and-bound based solution approach for the mixed-model assembly linebalancing problem for minimizing stations and task duplication costs. European Journal of Operational Research, 174 (1), 492–508. International Journal of Production Research 5013
Cochran, W.G. and Cox, G.M., 1992. Experimental designs. 2nd ed. New York: Wiley.
Coello, C. A. C, Pulido, G. T, & Lechuga, M. S. handling multiple objectives with particle swarm optimization. Evolutionary Computation, IEEE Transactions on, 8(3), 256-279 (2004)
Dar-El, E.M. and Nadivi, A., 1981. A mixed–model sequencing application. International Journal of Production Research, 19 (1), 69–84.
Deb K, Pratap A, Agarwal S, and Meyarivan T. A. M. T, A fast and elitist multi-objective genetic algorithm: NSGA-II, IEEE Transactions on Evolutionary Computation, 6, 182-197 (2002)
Deb, K., Agrawal, S., Pratap, A., & Meyarivan, T. (2000). A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II. Lecture notes in computer science, 1917, 849-858.
Erel, E., Gocgun, Y., and Sabuncuog˘ lu, _I., 2007. Mixed-model assembly line sequencing using beam search. International Journal of Production Research, 45 (22), 5265 – 5284.
Gutjahr, A.L. and Nemhauser, G.L., 1964. An algorithm for the line balancing problem. Management Science, 11 (2), 308–315.
Holland, J, Adaptation in Natural and Artificial Systems. Ann Harbor:  University of Michigan (1975)
Hwang, R. and Katayama, H., 2010. Integrated procedure of balancing and sequencing for mixed-model assembly lines: a multiobjective evolutionary approach. International Journal of Production Research, 48 (21), 6417 – 6441.
Hyun, C.J., Kim, Y., and Kim, Y.K., 1998. A genetic algorithm for multiple objective sequencing problems in mixed model assembly lines. Computers & Operations Research, 25 (7–8), 675–690.
Karimi, N., M. Zandieh, and H. R. Karamooz. 2010. “Bi-objective group scheduling in hybrid flexible flow shop: A multi-phase approach.” Expert Systems with Applications 37: 4024-4032.
Kim, Y.K., Hyun, C.J, and Kim, Y., 1996. Sequencing in mixed model assembly lines: a genetic algorithm approach. Computers & Operations Research, 23 (12), 1131–1145.
Kim, Y.K., Kim, J.Y., and Kim, Y., 2000. A coevolutionary algorithm for balancing and sequencing in mixed model assembly lines. Applied Intelligence, 13 (3), 247–258.
Kim, Y.K., Kim, J.Y., and Kim, Y., 2006. An endosymbiotic evolutionary algorithm for the integration of   balancing and sequencing in mixed-model u-lines. European Journal of Operational Research, 168 (3), 838–852.
Mansouri, S.A., 2005. A multi-objective genetic algorithm for mixed-model sequencing on JIT assembly lines. European Journal of Operational Research, 167 (3), 696–716.
Miltenburg, J., 2002. Balancing and scheduling mixed-model u-shaped production lines. International Journal of Flexible Manufacturing Systems, 14 (2), 119–151.
Montgomery, D.C., 2000. Design and analysis of experiments. 5th ed. New York: Wiley.
Moore J, Chapman R, Application of particle swarm to multiobjective optimization. Department of Computer Science and Software Engineering, Auburn University (1999(
Naderi, B., Zandieh, M., and Fatemi Ghomi, S.M.T., 2009. Scheduling job shop problems with sequence-dependent setup times. International Journal of Production Research, 47 (21), 5959 – 5976.
Rabbani, M., Farrokhi-Asl, H., & Ameli, M. (2016). Solving a fuzzy multi-objective products and time planning using hybrid meta-heuristic algorithm: Gas refinery case study. Uncertain Supply Chain Management, 4(2), 93-106.
Rabbani, M., Mousavi, Z., & Farrokhi-Asl, H. (2016). Multi-objective metaheuristics for solving a type II robotic mixed-model assembly line balancing problem. Journal of Industrial and Production Engineering, 1-13.
Rabbani, M., Siadatian, R., Farrokhi-Asl, H., & Manavizadeh, N. (2016). Multi-objective optimization algorithms for mixed model assembly line balancing problem with parallel workstations. Cogent Engineering, (just-accepted), 1158903.
Rekiek, B. and Delchambre, A., 2006. Assembly line design: the balancing of mixed-model hybrid assembly lines with genetic algorithms. 1st ed. London: Springer.
Roberts, S.D. and Villa, C.D., 1970. On a multiproduct assembly line-balancing problem. AIIE Transactions, 2 (4), 361–364.
Sawik, T., 2002. Monolithic vs. hierarchical balancing and scheduling of a flexible assembly line. European Journal of Operational Research, 143 (1), 115–124.
Scholl, A., 2010. Homepage for assembly line optimization research. Available from:5http://www.assembly–line– [Accessed 10 July 2010].
Simaria, A.S. and Vilarinho, P.M., 2004. A genetic algorithm based approach to the mixed-model assembly line balancing problem of type ii. Computers & Industrial Engineering, 47 (4), 391–407.
Srinivas, N., & Deb, K. (1994). Muiltiobjective optimization using nondominated sorting in genetic algorithms. Evolutionary computation, 2(3), 221-248.
Taguchi, G., 1986. Introduction to quality engineering: designing quality into products and processes. 1st ed. White Plains, NY: Asian Productivity Organization.
Tavakkoli-Moghaddam, R. and Rahimi-Vahed, A.R., 2006. Multi-criteria sequencing problem for a mixed-model assembly line in a JIT production system. Applied Mathematics and Computation, 181 (2), 1471–1481.
Thomopoulos, N.T., 1967. Line balancing-sequencing for mixed-model assembly. Management Science, 14 (2), 59–75.
Tsai, L.H., 1995. Mixed-model sequencing to minimize utility work and the risk of conveyor stoppage. Management Science, 41 (3), 485–495.