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

Authors

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.

Abstract

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.

Keywords

Main Subjects

References

References:
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 flowshop 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 flow shop scheduling problem", Journal of Manufacturing Systems, 35, pp. 1-9 (2015).
5. Ye, H., Li, W., and Miao, E. "An effective heuristic for no-wait flow shop production to minimize makespan", Journal of Manufacturing Systems, 40, pp. 2-7 (2016).
6. Linn, R. and Zhang, W. "Hybrid  flow shop scheduling: a survey", Computers & Industrial Engineering, 37(1- 2), pp. 57-61 (1999).
7. Naderi, B., Gohari, Sh., and Yazdani, M. "Hybrid flexible flowshop 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  flow 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  flow 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  flow-shops: a genetic algorithm approach", Journal of the Operational Research Society, 55(5), pp. 504-512 (2004).
16. Oguz, Y., Zinder Y., Ha Do, V., Janiak A., and  ichtenstein, M. "Hybrid  flow-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 flow-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  flow-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 flow-shop scheduling with multiprocessor tasks", International Journal of Production Research, 46(17), pp. 4655-4670 (2008).
20. Kahraman, C., Engin, O, Kaya, I., and Ozturk, R.E. "Multiprocessor task scheduling in multistage hybrid flow-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 efficient genetic algorithm for hybrid flow 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 flow 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 shued frog-leaping algorithm for hybrid  flowshop 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 flow 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  flexible  flowshop 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 flow 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 flow 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  flowshop 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  flowshop 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, unfilled backorders, and customer wait time using stochastic simulation with Markov blankets", Expert Systems with Applications, 41(16), pp. 7005-7022 (2014).
Scientia Iranica
Volume 27, Issue 3
Transactions on Industrial Engineering (E)
May and June 2020
Pages 1562-1571

Files

History

  • Receive Date: 10 November 2017
  • Revise Date: 09 September 2018
  • Accept Date: 05 November 2018

Share

How to cite

Statistics