Algorithm for Assembly Flowshops

Document Type : Original Article


1 PhD student, Islamic Azad University, Qazvin.

2 Associate Professor, Islamic Azad University, Qazvin.

3 Associate Professor, Kharazmi University.


Assembly flowshop with setup times is one of the newset production scheduling problems. In this problem, parts in the first stage that is a flow shop system are produced. Then, in the second stage, they are assembled. The objective is to sequence the parts production and assembly to minimize makespan. There is not an effective mathematical model for this problem. This paper first reviews the available model and then proposes a mixed integer linear programming model. To solve the model, it proposes two metaheuristics, imperialist competitive and genetic algorithms. Finally, the performance of the model and algorithms are evaluated, and the results show that imperialist competitive algorithm performs well.


1. Allahverdi, A., & Al-Anzi, F.S. (2006). A PSO and a tabu search heuristics for assembly scheduling problem of the two-stage. Computers & Operations Research33, 1056-1080.
2. Asadzadeh, L., & Zamanifar, K. (2010). An agent-based parallel approach for the job shop scheduling problem with genetic algorithms. Mathematical and Computer Modelling52, 1957-1965.
3. Atashpaz-Gargari, E., & Lucas, C. (2007). Imperialist competitive algorithm: an algorithm for optimization inspired by imperialistic competition. IEEE Congress, 4661-4670.
4. Attar, S.F., Mohammadi, M., & Tavakkoli-Moghaddam, M. (2011). A novel imperialist competitive algorithm to solve flexible flow shop scheduling problem in order to minimize maximum completion time, International Journal of Computer Applications28, 27-32.
5. Caraffa, V., Ianes S.P., Bagchi, T., & Sriskandarajah, C. (2001). Makespan Minimizing makespan in a blocking flowshop using genetic algorithms. International Journal of Production Economics70(2), 101-115.
6. Forst, F. (1983). Minimizing total expected costs in the two-machine, stochastic flow shop. Operations Research Letters2(2), 58-61.
7. Hariri, A.M.A., & Potts, C.N. (1997). A branch and bound algorithm for the two-stage assembly scheduling Problem. European Journal of Operational Research, 103, 547-556.
8. Hatami, S., Ebrahimnejad, S., Tavakkoli-Moghaddam R., & Maboudian, Y. (2010). Two meta-heuristics for three stage assembly flowshop scheduling with sequence-dependent setup times. International Journal ofAdvanced Manufacturing Technology50, 1153-1164.
9. Hendizadeh, S.H., ElMekkawy, T.Y., & Wang, G.G. (2007). Bi-criteria scheduling of a flowshop manufacturing cell with sequence dependent setup times. European Journal of Industrial Engineering1, 391-413.
10. Khakbiz, M., Rezaei Pendari, A., Dehghan Niri, M., (2017). Mathematical model for diversifying stock portfolio and solving with genetic algorithm, Industrial Management Prespective, 24, 173-196 (In Persian).
13. Koulamas, C., & Kyparisis, G.J. (2001). The three-stage assembly flowshop scheduling problem. Computers & Operations Research28, 689-704.
14. Javadian, N., Mozdgir, A., Gazani Koohi, E., Davallo Qajar, M.R., & Shiraqai M.E. (2009). Solving assembly flowshop scheduling problem with parallel machines using variable neighborhood search. In Proceedings of 39th International Conference of Computers and Industrial Engineering, University ofTechnology of Troyes, Paris, France, 102-107.
15. Lee, C.Y., Cheng, T.C.E., & Lin, B.M.T. (1993). Minimizing the makespan in the 3-machine assembly-type flowshop scheduling problem, Management Science39, 616-625.
17. Navaei J., Ghomi S.M.T.F., Jolai F., Shiraqai M.E., & Hidaji H., (2013). Two-stage flow-shop scheduling problem with non-identical second stage assembly machines. International Journal of Advanced Manufacturing Technology, 69, 2215-2226.
18. Navaei, J., Fatemi Ghomi, S.M.T., Jolai, F., & Mozdgir, A. (2014). Heuristics for an assembly flow-shop with non-identical assembly machines and sequence dependent setup times to minimize sum of holding and delay costs. Computers & Operations Research, 4452-65.
19. Navaei, J., Mozdgir, A., & Hidaji, H. (2010). Two-stage assembly flow-shop scheduling problem with bi-objective of number of tardy and makespan minimization. In: Proceedings of the 2010 International Conferenceon Artificial Intelligence, Las Vegas, Nevada, USA, 704-709.
20. Potts, C.N., Sevastjanov, S.V., Strusevich, V.A., Van Wassenhove, L.N., & Zwaneveld, C.M. (1995). The two-stage assembly scheduling problem: complexity and approximation, Operations Research, 43, 346-355.
21. Rahimi Shekh, H, Sharifi, M, & Shahriari M.R, A model for resialent supply chain: Case study in National healthcare organization, Industrial Management Prespective, 27, 127-150 (In Persian).
22. Ruiz, R, & Allahverdi, A. (2007). No-wait flowshop with separate setup times to minimize maximum lateness. International Journal of Advanced Manufacturing Technology35, 551-565.
23. Soke, A., & Bingul, Z. (2006). Hybrid genetic algorithm and simulated annealing for two-dimensional nonguillotine rectangular packing problems. Engineering Applications of Artificial Intelligence, 19, 557-567.
24. Sung, C.S., & Juhn, J. (2009). Makespan minimization for a 2-stage assembly scheduling problem subject to component available time constraint. International Journal of Production Economics119, 392- 401.
25. Torabzadeh, E., & Zandieh. M. (2010). Cloud Theory-Based Simulated Annealing Approach for Scheduling in the Two-Stage Assembly Flowshop. Advances in Engineering Software, 41, 1238-1243.
26. Tozkapan, A., Kirca, O., and Chung, C.S. (2003). A branch and bound algorithm to minimize the total weighted flow time for the two-stage assembly scheduling problem, Computers & Operations Research30, 309-320.
27. Wu C.C., Chen J.Y., Lin W.C., Lai K., Liu S.C., & Yu P.W., (2018). A two-stage three-machine assembly flow shop scheduling with learning consideration to minimize the flowtime by six hybrids of particle swarm optimization, Swarm and Evolutionary
28. Zandieh, M., Fotovat, A. (2015). A general flow shop scheduling problem with consideration of position- based learning effect and multiple availability constraints. Industrial Management Prespective, 20, 41-58 (In Persian).