Particle swarm optimization for minimizing total earliness/tardiness costs of two-stage assembly flowshop scheduling problem in a batched delivery system

Document Type : Research Paper


1 Islamic Azad university- Tehran south branch- School of industrial engineering-

2 Islamic Azad university- South Tehran Branch, Tehran-Iran


This paper considers a two-stage assembly flow shop scheduling problem. When all parts of each product are completed in the first stage, they are assembled into a final product on an assembly machine in the second stage. In order to reduce the delivery cost, completed products can be held until completion of some other products to be delivered in a same batch. The proposed problem addresses scheduling a set of operation with specific due date in a batch delivery system. The aim is to minimize total weighted earliness/tardiness and delivery costs. As the problem is demonstrated to be NP-hard, a genetic algorithm (GA) and a particle swarm optimization (PSO) are presented to solve the problem in real scales. Number of problems are solved by them and the results are compared. The computational results illustrate that the proposed PSO has a qualifier performance than the GA.


Main Subjects

Potts, C.N., Sevast'janov, S.V.,VanWassenhove, L.N.,  and Zwaneveld, C.M.,  (1995). The two-stage assembly scheduling problem: complexity and approximation. Operations Research, 43 (2): 346–355.
 Lee, C-Y., Cheng, T.C.E., and Lin, B.M.T., (1993). Minimising the makespan in the 3-machineassembly-type flowshop scheduling problem. Management Science, 39 (5): 616–625.
Hariri, A. M. A., and C. N. Potts. (1997). A Branch and Bound Algorithm for the Two-Stage Assembly Scheduling Problem. European Journal of Operational Research, 103: 547–556.
Haouari, M., and Daouas, T .,(1999). Optimal scheduling of the 3-machine assembly-type flow shop. RAIRO Operation Research, 33(4):439–445.
Tozkapan, A., Kirca, O., and Chung, C.-S., (2003). A branch and bound algorithm to minimise the total weighted flow time for the two-stage assembly scheduling problem. Computers and Operations Research, 30 (2): 309–320.
Sun, X., Morizawa, K.andNagasawa, H .,(2003). Powerful heuristics to minimize makespan  in fixed, 3-machine, assembly-type flowshop scheduling. European Journal of Operational Research, 146(3):498–516.
Allahverdi, A. and Al-Anzi, FS., (2007). The two-stage assembly flowshop scheduling problem with bicriteria of makespan and mean completion time. International Journal of Advanced Manufacturing Technology, 37 (1): 166–177.
Sung, C.S., and Kim, H. A., (2008). A two-stage multiple-machine assembly scheduling problem for minimizing sum of completion times. International Journal of Production Economics, 113: 1038-1048.
Sung, C.S., and  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.
Al-Anzi, FS. and  Allahverdi, A.,(2007). A self-adaptive differential evolution heuristic for two- stage assembly scheduling problem to minimize maximum lateness with setup times. European Journal of Operational Research,182:80–94.
Shokrollahpour, E., Zandieh, M., and Dorri, Behrooz.,(2011). A novel imperialist competitive algorithm for bi-criteria scheduling of the assembly flow shop problem. International Journal of Production Research,49(11):3087-3103.
Torabzadeh, E., and Zandieh,M.,(2010). Cloud theory-based simulated annealing approach for scheduling in the two-stage assembly flow shop. Advances in Engineering Software.41:1238-1243.
Mozdgir, A., FatemiGhomi, S.M.T., Joli, F., and  Navaei, J., (2013). Two-stage assembly flow-shop scheduling problem with non-identical assembly machines considering setup times. International Journal of Production Research, 51:3625-3642.
Seidgar, H., Kiani, M., Abedi, M., and Fazlollahtabar, H. (2014). An efficient imperialist competitive algorithm for scheduling in the two-stage assembly flow shop problem. International Journal of Production Research, 52(4):1240-1256.
Xiong, F., and Xing, K., (2014). Meta-heuristics for the distributed two-stage assembly scheduling problem with bi-criteria of makespan and mean completion time, International Journal of Production Research, 52(9):2743-2766.
Seidgar, H., Zandieh, M., Fazlollahtabar, H. and Mahdavi, I., (2015). Simulated imperialist competitive algorithm in two-stage assembly flow shop with machine breakdowns and preventive maintenance. Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture,doi:10.1177/0954405414563554.
Goldberg, D. (1989). Genetic algorithms in search: Optimization and machine learning. Reading, MA: Addison-Wesley.
Haq, A.N. and Kannan, G. (2006). Effect of forecasting on the multi-echelon distribution inventory supply chain cost using neural network, genetic algorithm and particle swarm optimization. International Journal of Services Operations and Informatics, 1(1-2), 1–22.
Holland, J.M. (1975). Adaption in natural and artificial systems. Ann Arbor, MI: The University of Michigan.
Kennedy, J. and Eberhart, R. (1995). Particle swarm optimization. Proceedings of the 1995 IEEE International Conference on Neural Network, IV, 4, 1942–1948.
Sha, D.Y. and Hsu, C.Y. (2008). A new particle swarm optimization for the open shop scheduling problem. Computers & Operations Research, 35(10), 3243-3261.
Umarani, R. and Selvi, V. (2010). Particle Swarm Optimization-Evolution, Overview and Applications. International Journal of Engineering Science and Technology, 2(7), 2802-2806.