A multi-objective genetic algorithm (MOGA) for hybrid flow shop scheduling problem with assembly operation

Document Type : Research Paper


Department of Industrial Engineering and management, Shahrood University of technology, Shahrood, Iran


Scheduling for a two-stage production system is one of the most common problems in production management. In this production system, a number of products are produced and each product is assembled from a set of parts. The parts are produced in the first stage that is a fabrication stage and then they are assembled in the second stage that usually is an assembly stage. In this article, the first stage assumed as a hybrid flow shop with identical parallel machines and the second stage will be an assembling work station. Two objective functions are considered that are minimizing the makespan and minimizing the sum of earliness and tardiness of products. At first, the problem is defined and its mathematical model is presented. Since the considered problem is NP-hard, the multi-objective genetic algorithm (MOGA) is used to solve this problem in two phases. In the first phase the sequence of the products assembly is determined and in the second phase, the parts of each product are scheduled to be fabricated. In each iteration of the proposed algorithm, the new population is selected based on the non-dominance rule and fitness value. To validate the performance of the proposed algorithm, in terms of solution quality and diversity level, various test problems are designed and the reliability of the proposed algorithm is compared with two prominent multi-objective genetic algorithms, i.e. WBGA, and NSGA-II. The computational results show that the performance of the proposed algorithms is good in both efficiency and effectiveness criteria. In small-sized problems, the number of non-dominance solution come out from the two algorithms N-WBGA (the proposed algorithm) and NSGA-II is approximately equal. Also, more than 90% solution of algorithms N-WBGA and NSGA-II are identical to the Pareto-optimal result. Also in medium problems, two algorithms N-WBGA and NSGA-II have approximately an equal performance and both of them are better than WBGA. But in large-sized problems, N-WBGA presents the best results in all indicators.


Main Subjects

Allahverdi A, Al-Anzi FS., (2009). The two-stage assembly scheduling problem to minimize total completion time with setup times. Computers & Operations Research 36: 2740-2747
Allahverdi, A., Aydilek, H., (2015). The two stage assembly flowshop scheduling problem to minimize total tardiness. Journal of Intelligent Manufacturing 26: 225-237.
Allahverdi, A., Aydilek H., Aydilek A., (2016). Two-Stage Assembly Scheduling Problem to Minimize Total Tardiness with Setup Times. Applied Mathematical Modelling 40: 7796-7815
Arroyo JAC, Armentano VA., (2005). Genetic local search for multi-objective flowshop scheduling problems. European Journal of Operational Research 167: 717–738
Cheng TCE, Wang G., (1999). Scheduling the fabrication and assembly of components in a two-machine flow shop. IIE Transactions 31: 135-143
Coello CA, Lamont GB, Veldhuizen DAV., (2007). Evolutionary Algorithms for Solving Multi-Objective Problems. Second edition, Springer.
Ehrgott M., (2005). Multicriteria Optimization. Springer, Berlin, second edition, ISBN
Fattahi P, Hosseini SMH, Jolai F., (2012). A mathematical model and extension algorithm for assembly flexible flow shop scheduling problem. International Journal of Advance Manufacture Technology 65:787–802. DOI 10.1007/s00170-012-4217-x.
Fattahi, P., Hosseini, S.M.H., Jolai, F. and Tavakoli-Moghadam, R. (2014). A branch and bound algorithm for hybrid flow shop scheduling problem with setup time and assembly operations. Applied Mathematical Modelling. 38 :119-134.
Fattahi, P., Hosseini, S.M.H., Jolai, F. and Safi-Samghabadi, A. (2014). Multi-objective scheduling problem in a threestage production system. International Journal of Industrial Engineering & Production Research. 25 :1-12.
Hariri AMA, Potts CN (1997). A branch and bound algorithm for the two-stage assembly scheduling problem. European Journal of Operational Research 103: 547-556
Jung s., Woo yb., Soo Kim B., (2017). Two-stage assembly scheduling problem for processing products with dynamic component-sizes and a setup time. Computers & Industrial Engineering 104:  98–113
Karimi N, Zandieh M, Karamooz HR (2010). Bi-objective group scheduling in hybrid flexible flowshop: A multi-phase approach. Expert Systems with Applications 37: 4024–4032
Konak A, Coit DW, Smith AE (2006). Multi-objective optimization using genetic algorithms: A tutorial. Reliability Engineering and System Safety 91: 992–1007
Koulamas Ch, Kyparisis GJ (2007). A note on the two-stage assembly flow shop scheduling problem with uniform parallel machines. European Journal of Operational Research 182: 945–951
Lee CY, Cheng TCE, Lin BMT (1993). Minimizing the makespan in the 3-machine assembly-type flowshop scheduling problem. Management Science 39: 616-625
Lin R, Liao ChJ (2012). A case study of batch scheduling for an assembly shop. International Journal of Production Economics 139: 473–483
Loukil T, Teghem J, Tuyttens D (2005). Solving multi-objective production scheduling problems using metaheuristics. European Journal of Operational Research 161: 42–61
Moslehi G, Mirzaee M, Vasei M, Modarres M, Azaron A (2009). Two-machine flow shop scheduling to minimize the sum of maximum earliness and tardiness. International Journal of Production Economics 122: 763–773
Potts CN, Sevast'Janov SV, Strusevich VA, Van Wassenhove LN, Zwaneveld CM (1995). The two-stage assembly scheduling problem: Complexity and approximation. Operations Research 43: 346-355
Rahimi-Vahed AR, Rabbani M, Tavakkoli-Moghaddam R, Torabi SA, Jolai F., (2007). A multi-objective scatter search for a mixed-model assembly line sequencing problem. Advanced Engineering Informatics 21: 85–99
Sukkerd, W. Wuttipornpun T., (2016). Hybrid genetic algorithm and tabu search for finite capacity material requirement planning system in flexible flow shop with assembly operations. Computers & Industrial Engineering, 97: p. 157-169.
Sun Y, Zhang Ch, Gao L, Wang X., (2010). Multi-objective optimization algorithms for flow shop scheduling problem: a review and prospects. Int J Adv Manuf Technol DOI 10.1007/s00170-010-3094-4
Sung CS, Kim Hah., (2008). A two-stage multiple-machine assembly scheduling problem for minimizing sum of completion times. International Journal of Production Economics 113: 1038-1048
Sup Sung Ch, Juhn J (2009). Makespan minimization for a 2-stage assembly scheduling problem subject to component available time constraint. International Journal of Production Economics 119: 392–401
Yokoyama M., (2001). Hybrid flow-shop scheduling with assembly operations. International Journal of Production Economics 73: 103-116
Yokoyama M, Santos DL (2005). Three-stage flow-shop scheduling with assembly operations to minimize the weighted sum of product completion times. European Journal of Operational Research 161: 754-770
Yokoyama M., (2008). Flow-shop scheduling with setup and assembly operations. European Journal of Operational Research 187: 1184–1195