Mathematical models and an elephant herding optimization for multiprocessor-task flexible flow shop scheduling problems in the Manufacturing Resource Planning (MRPII) system

Document Type : Article


1 Faculty of Industrial and Mechanical Engineering, Qazvin Branch, Islamic Azad University, Qazvin, Iran.

2 Department of Industrial Engineering, Faculty of Engineering, Kharazmi University, Tehran, Iran.


Shop floor control (SFC) is one of the main concepts in manufacturing resource planning (MRPII) and production scheduling is a key element in SFC. This paper studies the hybrid flow shop scheduling problem where jobs are multiprocessor. The objective is to minimize total completion time. Although there are several papers considering hybrid flow-shop scheduling problem with multiprocessor tasks, but none propose a mathematical model for this problem. At first, the two problems (fixed and selective cases) are mathematically formulated by mixed integer linear programming models. Using commercial software, the model is used to solve the small instances of the problems. Moreover, an elephant herding optimization is developed to solve large instances of the problems. To numerically evaluate the proposed algorithm, it is compared with two available algorithms in the literature, simulated annealing and shuffled frog-leaping algorithm in the literature.


Main Subjects

1. Sheikh, K., Manufacturing Resource Planning (MRP II): With Introduction to ERP, SCM and CRM, McGraw-Hill Professional Publishing (2003). 2. Pinedo, M.L., Scheduling: Theory, Algorithms, and Systems, Springer (2016). 3. Aminnayeri, M. and Naderi, B. Novel properties along with solution methods for permutation owshop scheduling", Scientia Iranica. Transaction E, Industrial Engineering, 23(5), pp. 2261{2276 (2016). 4. Vasiljovic, D. and Danilovic, M. Handling ties in heuristics for the permutation ow shop scheduling problem", Journal of Manufacturing Systems, 35, pp. 1{9 (2015). 5. Ye, H., Li, W., and Miao, E. An e_ective heuristic for no-wait ow shop production to minimize makespan", Journal of Manufacturing Systems, 40, pp. 2{7 (2016). 6. Linn, R. and Zhang, W. Hybrid ow shop scheduling: a survey", Computers & Industrial Engineering, 37(1- 2), pp. 57{61 (1999). 7. Naderi, B., Gohari, Sh., and Yazdani, M. Hybrid exible owshop problems: Models and solution methods", Applied Mathematical Modelling, 38(24), pp. 5767{ 5780 (2014). 8. Naderi, B. and Yazdani, M. A model and imperialist competitive algorithm for hybrid ow shops with sublots and setup times", Journal of Manufacturing Systems, 33(4), pp. 647{653 (2014). 9. Dal Cin, M. and Dilger, E. On the diagnosability of self-testing multi-microprocessor systems", Microprocessing and Microprogramming, 7(3), pp. 177-184 (1981). 10. Chen, J., and Lee, C.-Y. General multiprocessor task scheduling", Naval Research Logistics (NRL), 46(1), pp. 57{74 (1999). 11. Bertel, S. and Billaut, J.-C. A genetic algorithm for an industrial multiprocessor ow shop scheduling problem with recirculation", European Journal of Operational Research, 159(3), pp. 651{662 (2004). 12. Ercan, M.F. and Fung, Y.F. Real-time image interpretation on a multi-layer architecture", TENCON 99, Proceedings of the IEEE Region 10 Conference, 2, IEEE (1999). 13. Janson, K. and Porkolab, L. General multiprocessor task scheduling: Approximate solutions in linear time", SIAM Journal on Computing, 35(3), pp. 519{ 530 (2005). 14. Mehdizadeh, E., Tavakkoli-Moghaddam, R., and Yazdani, M. A vibration damping optimization algorithm for a parallel machines scheduling problem with sequence-independent family setup times", Applied Mathematical Modelling, 39(22), pp. 6845{6859 (2015). 15. Serifoglu, F.S. and Ulusoy, G. Multiprocessor task scheduling in multistage hybrid ow-shops: a genetic algorithm approach", Journal of the Operational Research Society, 55(5), pp. 504{512 (2004). 16. O_guz, Y., Zinder Y., Ha Do, V., Janiak A., and Lichtenstein, M. Hybrid ow-shop scheduling problems with multiprocessor task systems", European Journal of Operational Research, 152(1), pp. 115{131 (2004). 17. Oguz, C. and Ercan, M.F. A genetic algorithm for hybrid ow-shop scheduling with multiprocessor tasks", Journal of Scheduling, 8(4), pp. 323{351 (2005). 18. Ying, K.C. and Lin, S.W. Multiprocessor task scheduling in multistage hybrid ow-shops: an ant colony system approach", International Journal of Production Research, 44(16), pp. 3161{3177 (2006). 19. Tseng, C.T. and Liao, C.J. A particle swarm optimization algorithm for hybrid ow-shop scheduling with multiprocessor tasks", International Journal of Production Research, 46(17), pp. 4655{4670 (2008). H.R. Gholami et al./Scientia Iranica, Transactions E: Industrial Engineering 27 (2020) 1562{1571 1571 20. Kahraman, C., Engin, O, Kaya, I., and Ozturk, R.E. Multiprocessor task scheduling in multistage hybrid ow-shops: A parallel greedy algorithm approach", Applied Soft Computing, 10(4), pp. 1293{1300 (2010). 21. Engin, O., Coran, G., and Yilmaz, M.K. An e_cient genetic algorithm for hybrid ow shop scheduling with multiprocessor task problems", Applied Soft Computing, 11(3), pp. 3056{3065 (2011). 22. Wang, H.M., Chou, F.D., and Wu, F.C. A simulated annealing for hybrid ow shop scheduling with multiprocessor tasks to minimize makespan", The International Journal of Advanced Manufacturing Technology, 53(5{8), pp. 761{776 (2011). 23. Xu, Y., Wang, L., Liu, M., and Wang, S.Y. An effective shu_ed frog-leaping algorithm for hybrid owshop scheduling with multiprocessor tasks", The International Journal of Advanced Manufacturing Technology, 68(5{8), pp. 1529{1537 (2013). 24. Lahimer, A., Lopez, P., and Haouar, M. Improved bounds for hybrid ow shop scheduling with multiprocessor tasks", Computers & Industrial Engineering, 66(4), pp. 1106{1114 (2013). 25. Jolai, F., Tavakkoli-Moghaddam, R., Rabiee, M., and Gheisariha, E. An enhanced invasive weed optimization for makespan minimization in a exible owshop scheduling problem", Scientia Iranica, Transactions E, Industrial Engineering, 21(3), p. 1007 (2014). 26. Hidri, L., Elkosantini, S., and Mabkhot, M.M. Exact and heuristic procedures for the two-center hybrid ow shop scheduling problem with transportation times", IEEE Access, 6, pp. 21788{21801 (2018). 27. Ziaeifar, A., Tavakkoli-Moghaddam, R., and Pichka, Kh. Solving a new mathematical model for a hybrid ow shop scheduling problem with a processor assignment by a genetic algorithm", The International Journal of Advanced Manufacturing Technology, 61(1{ 4), pp. 339{349 (2012). 28. Behnamian, J., and Fatemi Ghomi, S.M.T. Multiobjective fuzzy multiprocessor owshop scheduling", Applied Soft Computing, 21, pp. 139{148 (2014). 29. Wang, G.G., Deb, S., and Coelho, L.dos S. Elephant herding optimization", Computational and Business Intelligence (ISCBI), 2015 3rd International Symposium on, IEEE (2015). 30. Liao, C.J., Tseng, C.T., and Luarn, P. A discrete version of particle swarm optimization for owshop scheduling problems", Computers & Operations Research, 34(10), pp. 3099{3111 (2007). 31. Rodger, J.A. Application of a fuzzy feasibility Bayesian probabilistic estimation of supply chain backorder aging, un_lled backorders, and customer wait time using stochastic simulation with Markov blankets", Expert Systems with Applications, 41(16), pp. 7005{7022 (2014).