Integrated cell formation and part scheduling: A new mathematical model along with two meta-heuristics and a case study for truck industry

Document Type : Article

Authors

Department of Industrial Engineering, Eskisehir Osmangazi University, Eskisehir, Turkey.

Abstract

This paper proposes a new linearized mathematical model to solve integrated cell formation and job scheduling problem. The model aims to minimize the exceptional elements, voids and the make-span of the jobs. The results of test problems show that the proposed model is very effective to obtain best solutions for small sized problems in reasonable computation times. However, due to the NP-hard nature of the considered problem, the best solutions couldn’t be obtained in acceptable times for large sized test problems whereas the real-life applications of the problem addressed here are often much larger in size. To meet the requirement of solving larger sized problems, Genetic Algorithm, which is, today, considered as one of the artificial intelligence and machine learning technique and Marine Predators Algorithm as a new and a nature-inspired metaheuristic, are proposed. The success of the algorithms was investigated and compared. The test results reveal the fact that the Marine Predators algorithm with optimized parameters has a high potential to solve real life problems. At last, an attempt is made to re-design an existing real-life production system by the proposed algorithms. Eventually, a considerable improvement is obtained on performance compared to the current situation of the system.

Keywords

References

References:
1. Mahdavi, I., Aalaei, A., Paydar, M.M., et al. "Multiobjective cell formation and production planning in dynamic virtual cellular manufacturing systems", Int. J. Prod. Res., 49(21), pp. 6517-6537 (2011). DOI: 10.1080/00207543.2010.524902.
2. Buruk Sahin, Y. and Alpay, S. "A metaheuristic approach for a cubic cell formation problem", Expert Syst. Appl., 65, pp. 40-51 (2016). DOI: 10.1016/j.eswa.2016.08.034.
3. Buruk Sahin, Y. and Alpay, S. "A new mathematical model for the integrated solution of cell formation and part scheduling problem", Gazi Uni. J. Sci., 32(4), pp. 1196-1210 (2019). DOI: 10.35378/gujs.471637.
4. Pinedo, M.L., Scheduling: Theory, Algorithms, and Systems, Prentice Hall, USA (2002). 
5. Li, D., Wang, Y., Xiao, G., et al. "Dynamic parts scheduling in multiple Jop shop cells considering intercell moves and  flexible routes", Comput Oper Res., 40(5), pp. 1207-1223 (2013). https://doi.org/10.1016/j.cor.2012.11.024.
6. Amjad, M.K., Butt, S.I., Kousar, R., et al. "Recent research trends in genetic algorithm based flexible jop shop scheduling problems", Math. Probl. Eng., 2018(8), p. 9270802 (2018). DOI: 10.1155/2018/9270802.
7. Chaudhry, I.A. and Khan, A.A. "A research survey: review of  flexible Jop shop scheduling techniques", Int T Oper Res., 23(3), pp. 551-591 (2016). 
8. Wu, X., Chu, C., Wang, Y., et al. "A genetic algorithm for cellular manufacturing design and layout", Eur. J. Oper. Res., 181(1), pp. 156-167 (2007). https://doi.org/10.1016/j.ejor.2006.05.035.
9. Wang, X., Tang, J., and Yung, K. "A scatter search approach with dispatching rules for a joint decision of cell formation and parts scheduling in batches", Int. J. Prod. Res., 48(12), pp. 3513-3534 (2010). DOI: 10.1080/00207540902922828.
10. Ghezavati, V. and Saidi-Mehrabad, M. "Designing integrated cellular manufacturing systems with scheduling considering stochastic processing time", Int J Adv Manuf Tech., 48(5), pp. 701-717 (2010).
11. Kesen, S.E., Das, S.K., and Gungor, Z. "A genetic algorithm based heuristic for scheduling of virtual manufacturing cells (VMCs)", Comput Oper Res., 37(6), pp. 1148-56 (2010). https://doi.org/10.1016/j.cor.2009.10.006.
12. Tang, J., Wang, X., Kaku, I., et al. "Optimization of parts scheduling in multiple cells considering intercell move using scatter search approach", J. Intell. Manuf., 21(4), pp. 525-537 (2010).
13. Aryanezhad, M.B., Aliabadi, J., and Tavakkoli- Moghaddam, R. "A new approach for cell formation and scheduling with assembly operations and product structure", Int. J. Ind. Eng. Comput., 2(3), pp. 533- 546 (2011). http://growingscience.com/ijiec/ijiec.html.
14. Tang, J., Yan, C., Wang, X., et al. "Using lagrangian relaxation decomposition with heuristic to integrate the decisions of cell formation and parts scheduling considering intercell moves", IEEE Trans. Autom. Sci. Eng., 11(4), pp. 1110-1121 (2014). DOI: 10.1109/TASE.2014.2325860.
15. Liu, C. and Wang, J. "Cell formation and task scheduling considering multi-functional resource and part movement using hybrid simulated annealing", Int. J. Comput. Intell. Syst., 9(4), pp. 765-777 (2016). DOI: 10.1080/18756891.2016.1204123.
16. Rafiei, H., Rabbani, M., Gholizadeh, H., et al. "A novel hybrid SA/GA algorithm for solving an integrated cell formation job scheduling problem with sequence-dependent set-up times", Int. J. Manag. Sci. Eng. Manag., 11(3), pp. 134-142 (2016). DOI:
10.1080/17509653.2014.1003109.
17. Liu, C., Wang, J., Leung, J.Y.T., et al. "Solving cell formation and task scheduling in cellular manufacturing system by discrete bacteria foraging algorithm", Int. J. Prod. Res., 54(3), pp. 923-944 (2016). DOI: 10.1080/00207543.2015.1113328.
18. Iqbal, N., Aziz, M.H., Jahanzaib, M., et al. "Integration of cell formation and job sequencing to minimize energy consumption with minimum make-span", P I Mech Eng B-J Eng., 231(14), pp. 2636-2651 (2017).
19. Costa, A., Cappadonna, F.A., and Fichera, S. "A hybrid genetic algorithm for minimizing makespan in a flow-shop sequence-dependent group scheduling problem", J. Intell. Manuf., 28(6), pp. 1269-1283 (2017). DOI: 10.1007/s10845-015-1049-1.
20. Feng, H., Xia, T., Da, W., et al. "Concurrent design of cell formation and scheduling with consideration of duplicate machines and alternative process routings", J. Intell. Manuf., 30, pp. 275-289 (2019). DOI: 10.1007/s10845-016-1245-7.
21. Far, M.H., Haleh, H., and Saghaei, A. "A fuzzy biobjective  flexible cell scheduling optimization model under green and energy-efficient strategy using Paretobased algorithms: SATPSPGA, SANRGA, and NSGA-II", Int J Adv Manuf Tech., 105, pp. 3853-3879 (2019). DOI: 10.1007/s00170-019-03797-w.
22. Forghani, K. and Ghomi, S.F. "Joint cell formation, cell scheduling, and group layout problem in virtual and classical cellular manufacturing systems", Appl. Soft Comput., 97(10), p. 106719 (2020). DOI: 10.1016/j.asoc.2020.106719.
23. Halat, K. and Bashirzadeh, R. "Concurrent scheduling of manufacturing cells considering sequence-dependent family setup times and intercellular transportation times", Int J Adv Manuf Tech., 77(9-12), pp. 1907-1915 (2015). DOI: 10.1007/s00170-014-6511-2.
24. Ebrahimi, A., Kia, R., and Komijan, A.R. "Solving a mathematical model integrating unequal-area facilities layout and part scheduling in a cellular manufacturing system by a genetic algorithm", SpringerPlus, 5(1), p. 1254 (2016). DOI: 10.1186/s40064-016-2773-5.
25. Subhaa, R., Jawahar, N., and Ponnambalam, S.G. "An improved design for cellular manufacturing system associating scheduling decisions", Sadhana, 44(7), p. 155 (2019). DOI: 10.1007/s12046-019-1135-8.
26. Rahimi, V., Arkat, J., and Farughi, H. "A vibration damping optimization algorithm for the integrated problem of cell formation, cellular scheduling, and intercellular layout", Comput Ind Eng., 143, p. 106439 (2020). DOI: 10.1016/j.cie.2020.106439.
27. Neufeld, J.S., Teucher, F.F., and Buscher, U. "Scheduling  flowline manufacturing cells with intercellular moves: non-permutation schedules and material flows in the cell scheduling problem", Int. J. Prod. Res., 58(21), pp. 6568-6584 (2020). https://doi.org/10.1080/00207543.2019.1683251.
28. Alimian, M., Ghezavati, V., and Tavakkoli-Moghaddam, R. "New integration of preventive maintenance and production planning with cell formation and group scheduling for dynamic cellular manufacturing systems", J. Manuf. Syst., 56, pp. 341-358 (2020). https://doi.org/10.1016/j. jmsy.2020.06.011.
29. Wang, J., Liu, C., and Zhou, M. "Improved bacterial foraging algorithm for cell formation and product scheduling considering learning and forgetting factors in cellular manufacturing systems", IEEE Syst J., 14(2), pp. 3047-3056 (2020). DOI: 10.1109/JSYST.2019.2963222.
30. Rafiee, M., Kayvanfar, V., Mohammadi, A., et al. "A robust optimization approach for a cellular manufacturing system considering skill-leveled operators and multi-functional machines", Appl. Math. Model., 107, pp. 379-397 (2022). DOI: 10.1016/j.apm.2022.02.028.
31. Goli, A., Tirkolaee, E.B., and Ayd in, N.S. "Fuzzy integrated cell formation and production scheduling considering automated guided vehicles and human factors", IEEE Trans Fuzzy Syst, 29(12), pp. 3686- 3695 (2021). DOI: 10.1109/TFUZZ.2021.3053838.
32. Kazemi, M., Sadegheih, A., Lotfi, M.M., et al. "Developing a bi-objective schedule for an online cellular manufacturing system in an MTO environment", Soft Comput., 26(2), pp. 807-828 (2022). DOI: 10.1007/s00500-021-06402-z.
33. Holland, J.H. "Adaptation in natural and artificial systems. an introductory analysis with applications to biology, control and artificial intelligence", Ann Arbor: University of Michigan Press (1975).
34. Shapiro, J. "Genetic algorithms in machine learning", In Advanced Course on Artificial Intelligence, pp. 146- 168, Springer, Berlin, Heidelberg (1999).
35. Grefenstette, J.J. "Optimization of control parameters for genetic algorithms", IEEE T Syst Man Cy., 16(1), pp. 122-128 (1986). DOI: 10.1109/TSMC.1986.289288.
36. Gen, M. and Cheng, R., Genetic Algorithms and Manufacturing Systems Design, John Wiley and Sons, Inc (1996).
37. Gopalakrishnan, H. and Kosanovic, D. "Operational planning of combined heat and power plants through genetic algorithms for mixed 0-1 nonlinear programming", Comput Oper Res., 56(3), pp. 51-67 (2015). DOI: 10.1016/j.cor.2014.11.001.
38. Chakrabortty, R. and Hasin, M. "Solving an aggregate production planning problem by using multiobjective genetic algorithm (MOGA) approach", Int J Ind Eng Comp., 4(1), pp. 1-12 (2013). DOI: 10.5267/j.ijiec.2012.09.003.
39. Faramarzi, A., Heidarinejad, M., Mirjalili, S., et al. "Marine predators algorithm: A nature-inspired metaheuristic", Expert Syst. Appl., 152, 113377 (2020). DOI: 10.1016/j.eswa.2020.113377.
40. Hu, G., Zhu, X., Wei, G., et al. "An improved marine predators algorithm for shape optimization of developable Ball surfaces", Eng. Appl. Artif. Intell., 105(10), p. 104417 (2021). DOI: 10.1016/j.engappai.2021.104417.
41. Gonggui, C., Ying, X., and Fangjia, L. "An improved marine predators algorithm for short-term hydrothermal scheduling", IAENG Int. J. Appl. Math., 51(4) (2021).
42. Fattahi, P., Saidi Mehrabad, M., and Jolai, F. "Mathematical modeling and heuristic approaches to  flexible jop shop scheduling problems", J. Intell. Manuf., 18(3), pp. 331-42 (2007). DOI: 10.1007/s10845-007- 0026-8.
43. Candan, G. and Yazgan, H.R. "Genetic algorithm parameter optimisation using Taguchi method for a  flexible manufacturing system scheduling problem", Int J Prod Res., 53(3), pp. 897-915 (2015). DOI: 10.1080/00207543.2014.939244.
44. Far, M.H., Haleh, H., and Saghaei, A. "A flexible cell scheduling problem with automated guided vehicles and robots under energy-conscious policy", Sci. Iran., 25(1), pp. 339-358 (2018). DOI: 10.24200/SCI.2017.4399.
45. Esmailnezhad, B. and Saidi-Mehrabad, M. "A twostage stochastic supply chain scheduling problem with production in cellular manufacturing environment: A case study", Sci Iran, 30(4), pp. 1399-1422 (2023). DOI: 10.24200/sci.2021.53506.3277.
46. Cheng, L., Tang, Q., Zhang, L., et al. "Scheduling flexible manufacturing cell with no-idle  flowlines and job-shop via Q-learning-based genetic algorithm", Comput. Ind. Eng., 108293 (2022). https://doi.org/10.1016/j.cie.2022.108293.
47. Majumdar, A. and Ghosh, D. "Genetic algorithm parameter optimization using Taguchi robust design for multi-response optimization of experimental and historical data", Int. J. Comput. Appl., 127(5), pp. 26-32 (2015). DOI: 10.5120/ijca2015906383.
Scientia Iranica
Volume 31, Issue 11
Transactions on Industrial Engineering (E)
May and June 2024
Pages 888-905

Files

Share

How to cite

Statistics