A new mathematical formulation and a hybrid evolutionary algorithm for re-entrant flow-shop problem with release date

Document Type : Article

Authors

1 Department of Industrial Engineering, Naghshejahan Higher Education Institute, Isfahan 8144167984, Iran

2 Faculty of Engineering, University of Isfahan, Isfahan 81746-73441, Iran

Abstract

In this paper, we address the weighted multi-objective re-entrant flow-shop scheduling problem considering release dates in order to minimize makespan, total completion time, total tardiness, maximum idle time, and number of tardy jobs. Each job is taken into account with deterministic processing times, and release dates. The flow-shop comprised of two workshops in whose jobs are entered to the main workshop and after the first part of the processing, they are transferred to the second workshop and after this stage, the jobs are returned to the main workshop for the last part of the processing. We model the problem by a new mixed integer programming based on formulating sum of idle time as a new concept. Moreover, a hybrid evolutionary algorithm is proposed based on some dispatching rules, ant colony optimization, and genetic algorithm. The performance of the proposed algorithm on some test instances is compared to the mixed integer linear programming model as well as the state-of-the-art algorithms called genetic algorithm, tabu search, bio-geography based optimization, and artificial bee colony. The computational experiments show that our proposed approach outperforms other algorithms and the results indicate efficiency and capability of the proposed algorithm in comparison with the traditional algorithms.

Keywords

References

References:
1. Pinedo, M.L., Scheduling: Theory, Algorithms, and Systems, Springer International Publishing, p. 670 (2016). DOI: 10.1007/978-3-319-26580-3.
2. Baker, K.R., Introduction to Sequencing and Scheduling, Wiley New York, p. 305 (1974).
3. Che, A., Chabrol, M., Gourgand, M., et al. "Scheduling multiple robots in a no-wait re-entrant robotic  flowshop", International Journal of Production Economics, 135(1), pp. 199-208 (2012). DOI:10.1016/j.ijpe.2011.07.008.
4. Pan, J.-H. and Chen, J.S. "Minimizing makespan in re-entrant permutation  flow-shops", Journal of the Operational Research Society, 54(6), pp. 642-653 (2003). DOI: 10.1057/palgrave.jors.2601556.
5. Choi, S.W. and Kim, Y.D. "Minimizing makespan on a two-machine re-entrant flowshop", Journal of the Operational Research Society, 58(7), pp. 972-981 (2007). DOI: 10.1057/palgrave.jors.2602220.
6. Bootaki, B. and Paydar, M.M. "On the n-job, m-machine permutation flow shop scheduling problems with makespan criterion and rework", Scientia Iranica, 25(3), pp. 1688-1700 (2018). DOI: 10.24200/sci.2017.4443.
7. Abbaszadeh, N., Asadi-Gangraj, E., and Emami, S. "Flexible flow shop scheduling problem to minimize makespan with renewable resources", Scientia Iranica, 28(3), pp. 1853-1870 (2021). DOI: 10.24200/sci.2019.53600.3325.
8. Gholami, H.R., Mehdizadeh, E., and Naderi, B. "Mathematical models and an elephant herding optimization for multiprocessor-task flexible flow shop scheduling problems in the Manufacturing Resource Planning (MRPII) system", Scientia Iranica, 27(3), pp. 1562-1571 (2020). DOI: 10.24200/sci.2018.5552.1343.
9. Shao, Z., Shao, W., and Pi, D. "Effective heuristics and metaheuristics for the distributed fuzzy blocking flow-shop scheduling problem", Swarm and Evolutionary Computation, 59, p. 100747 (2020). DOI: 10.1016/j.swevo.2020.100747.
10. Wang, G., Gao, L., Li, X., et al. "Energy-efficient distributed permutation flow shop scheduling problem using a multi-objective whale swarm algorithm", Swarm and Evolutionary Computation, 57, p. 100716 (2020). DOI: 10.1016/j.swevo.2020.100716.
11. Baskar, A. and Xavior, M.A. "New idle time-based tie-breaking rules in heuristics for the permutation flowshop scheduling problems", Computers & Operations Research, 133, p. 105348 (2021). DOI:10.1016/j.cor.2021.105348.
12. Ozcan, B., Yavuz, M., and Figlali, A. "A data miningbased solution method for flow shop scheduling problems", Scientia Iranica, 28(2), pp. 950-969 (2021). DOI: 10.24200/SCI.2020.50995.1957.
13. Wu, C.-C., Liu, S.-C., Cheng, T.C.E., et al. "Reentrant flowshop scheduling with learning considerations to minimize the makespan", Iranian Journal of Science and Technology, Transactions A: Science, 42(2), pp. 727-744 (2018). DOI: 10.1007/s40995-017-0236-7.
14. Rifai, A.P., Kusumastuti, P.A., and Mara, S.T.W. "Multi-operator hybrid genetic algorithm-simulated annealing for reentrant permutation flow-shop scheduling", ASEAN Engineering Journal, 11(3), pp. 109-126 (2021). DOI: 10.11113/aej.v11.16875.
15. Huang, J.D., Liu, J.J., Chen, Q.X., et al. "Minimizing makespan in a two-stage flow shop with parallel batchprocessing machines and re-entrant jobs", Engineering Optimization, 49(6), pp. 1010-1023 (2017). DOI: 10.1080/0305215X.2016.1231307.
16. Geng, K., Ye, C., Cao, L., et al. "Multi-objective reentrant hybrid flowshop scheduling with machines turning on and off control strategy using improved multi-verse optimizer algorithm", Mathematical Problems in Engineering, 2019, p. 2573873 (2019). DOI: 10.1155/2019/2573873.
17. Amin Naseri, M.R., Tasouji Hassanpour, S., and Nahavandi, N. "Solving re-entrant no-wait flow shop scheduling problem", International Journal of Engineering, 28(6), pp. 903-912 (2015). DOI: 10.5829/idosi.ije.2015.28.06c.11.
18. Chen, J.-S. and Chao-Hsien Pan, J. "Integer programming models for the re-entrant shop scheduling problems", Engineering Optimization, 38(5), pp. 577- 592 (2006). DOI: 10.1080/03052150600574341.
19. Chen, J.-S., Pan, J.C.-H., and Lin, C.-M. "A hybrid genetic algorithm for the re-entrant flow-shop scheduling problem", Expert  Systems with Applications, 34(1), pp. 570-577 (2008). DOI: 10.1016/j.eswa.2006.09.021.
20. Jing, C., Tang, G., and Qian, X. "Heuristic algorithms for two machine re-entrant flow shop", Theoretical Computer Science, 400(1), pp. 137-143 (2008). DOI: 10.1016/j.tcs.2008.02.046.
21. Lin, D., Lee, C.K.M., and Ho, W. "Multi-level genetic algorithm for the resource-constrained re-entrant scheduling problem in the flow shop", Engineering Applications of Arti cial Intelligence, 26(4), pp. 1282- 1290 (2013). DOI: 10.1016/j.engappai.2012.10.006.
22. Xu, J., Yin, Y., Cheng, T.C.E., et al. "A memetic algorithm for the re-entrant permutation flowshop scheduling problem to minimize the makespan", Applied Soft Computing, 24, pp. 277-283 (2014). DOI: 10.1016/j.asoc.2014.07.002.
23. Choi, S.-W. and Kim, Y.-D. "Minimizing total tardiness on a two-machine re-entrant flowshop", European Journal of Operational Research, 199(2), pp. 375-384 (2009). DOI: 10.1016/j.cor.2014.02.002.
24. Lin, D., Lee, C.K.M., and Wu, Z. "Integrating analytical hierarchy process to genetic algorithm for reentrant flow shop scheduling problem", International Journal of Production Research, 50(7), pp. 1813-1824 (2012). DOI: 10.1080/00207543.2011.561884.
25. Xu, J., Lin, W.-C., Wu, J., et al. "Heuristic based genetic algorithms for the re-entrant total completion time flowshop scheduling with learning consideration", International Journal of Computational Intelligence Systems, 9(6), pp. 1082-1100 (2016). DOI: 10.1080/18756891.2016.1256572.
26. Chamnanlor, C., Sethanan, K., Chien, C.-F., et al. "Re-entrant flow shop scheduling problem with time windows using hybrid genetic algorithm based on auto-tuning strategy", International Journal of Production Research, 52(9), pp. 2612-2629 (2014). DOI: 10.1080/00207543.2013.861949.
27. Chamnanlor, C., Sethanan, K., Gen, M., et al. "Embedding ant system in genetic algorithm for reentrant hybrid flow shop scheduling problems with time window constraints", Journal of Intelligent Manufacturing, 28(8), pp. 1915-1931 (2017). DOI:
10.1007/s10845-015-1078-9.
28. Waqas, U., Geilen, M., Kandelaars, J., et al. "A re-entrant flowshop heuristic for online scheduling of the paper path in a large scale printer", Design, Automation & Test in Europe Conference & Exhibition (DATE), pp. 573-578 (2015). DOI: 10.7873/DATE.2015.0519.
29. Jeong, B. and Kim, Y.-D. "Minimizing total tardiness in a two-machine re-entrant  flowshop with sequence-dependent setup times", Computers & Operations Research, 47, pp. 72-80 (2014). DOI: 10.1016/j.cor.2014.02.002.
30. Kim, H. and Lee, D.H. "Heuristic algorithms for re-entrant hybrid  flow shop scheduling with unrelated parallel machines", Proceedings of The Institution of Mechanical Engineers Part B-Journal of Engineering Manufacture - PROC INST MECH ENG B-J ENG MA, 223, pp. 433-442 (2009). DOI: 10.1243/09544054JEM1318.
31. Lee, C.K.M., Lin, D., Ho, W., et al. "Design of a genetic algorithm for bi-objective flow shop scheduling problems with re-entrant jobs", The International Journal of Advanced Manufacturing Technology, 56(9), pp. 1105-1113 (2011). DOI: 10.1007/s00170-011-3251- 4.
32. Mousavi, S.M., Mahdavi, I., Rezaeian, J., et al. "An efficient bi-objective algorithm to solve re-entrant hybrid  flow shop scheduling with learning effect and setup times", Operational Research, 18(1), pp. 123- 158 (2018). DOI: 10.1007/s12351-016-0257-6.
33. El-Khouly, I.A., El-Kilany, K.S., and El-Sayed, A.E. "Modelling and simulation of re-entrant  flow shop scheduling: An application in semiconductor manufacturing", International Conference on Computers & Industrial Engineering, pp. 211-216 (2009). DOI: 10.1109/ICCIE.2009.5223754.
34. Moghaddam, A., Yalaoui, F., and Amodeo, L. "A genetic-based algorithm to find better estimation of non-dominated solutions for a bi-objective re-entrant  flowshop scheduling problem with outsourcing", IFAC Proceedings Volumes, 45(6), pp. 1383-1388 (2012). DOI: 10.3182/20120523-3-RO-2023.00165.
35. Mousavi, S.M., Mahdavi, I., Rezaeian, J., et al.  Biobjective scheduling for the re-entrant hybrid flow shop with learning effect and setup times", Scientia Iranica, 25(4), pp. 2233-2253 (2018). DOI: 10.24200/sci.2017.4451.
36. Behmanesh, R., Zandieh, M., and Hadji, M. "Multiple resource surgical case scheduling problem: Ant colony system approach", Economic Computation and Economic Cybernetics Studies and Research, 54, pp. 251-268 (2020). DOI: 10.24818/18423264/54.1.20.16.
37. Behmanesh, R., Zandieh, M., and Hadji Molana, S.M. "The surgical case scheduling problem with fuzzy duration time: An ant system algorithm", Scientia Iranica, 26(3), pp. 1824-1841 (2019). DOI: 10.24200/sci.2018.20602.
38. Zhang, G. and Xing, K. "Differential evolution metaheuristics for distributed limited-buffer  flowshop  scheduling with makespan criterion", Computers & Operations Research, 108, pp. 33-43 (2019). DOI: 10.1016/j.cor.2019.04.002.
39. Chen, J.-S., Pan, J.C.-H., and Wu, C.-K. "Hybrid tabu search for re-entrant permutation  flowshop scheduling problem", Expert Systems with Applications, 34(3), pp. 1924-1930 (2008). DOI: 10.1016/j.eswa.2007.02.027.
40. Sangsawang, C., Sethanan, K., Fujimoto, T., et al. "Metaheuristics optimization approaches for two-stage reentrant  flexible  flow shop with blocking constraint", Expert Systems with Applications, 42(5), pp. 2395- 2410 (2015). DOI: 10.1016/j.eswa.2014.10.043.
41. Oyetunji, E.O. and Oluleye, A.E. "Minimizing makespan on single machine with release dates", International Journal of Advancements in Technology, 2(1), pp. 3-13 (2011).
42. Simon, D. "Biogeography-based optimization", IEEE Transactions on Evolutionary Computation, 12(6), pp. 702-713 (2008). DOI: 10.1109/TEVC.2008.919004.
43. Karaboga, D., An Idea Based on Honey Bee Swarm for Numerical Optimization, Technical Report - TR06, Technical Report, Erciyes University (2005).
44. Glover, F. "Future paths for integer programming and links to arti cial intelligence", Computers & Operations Research, 13(5), pp. 533-549 (1986). DOI: 10.1016/0305-0548(86)90048-1.
45. Lawler, E.L. "Optimal sequencing of a single machine subject to precedence constraints", Management Science, 19(5), pp. 544-546 (1973). DOI: 10.1287/mnsc.19.5.544.
46. Bean, J.C. "Genetic algorithms and random keys for sequencing and optimization", ORSA Journal on Computing, 6(2), pp. 154-160 (1994). DOI: 10.1287/ijoc.6.2.154.
47. Solimanpur, M. and Elmi, A. "A tabu search approach for cell scheduling problem with makespan criterion", International Journal of Production Economics, 141(2), pp. 639-645 (2013). DOI: 10.1016/j.ijpe.2012.10.001.
48. Kaplan, A.C. and Unal, A.T. "A probabilistic costbased due date assignment model for job shops", International Journal of Production Research, 31(12), pp. 2817-2834 (1993). DOI: 10.1080/00207549308956902.
49. Seidgar, H., Fazlollahtabar, H., and Zandieh, M. "Scheduling two-stage assembly  flow shop with random machines breakdowns: Integrated new self-adapted differential evolutionary and simulation approach", Soft Computing, 24(11), pp. 8377-8401 (2020). DOI: 10.1007/s00500-019-04407-3.
Scientia Iranica
Volume 31, Issue 6 - Serial Number 6
Transactions on Industrial Engineering (E)
March and April 2024
Pages 500-517

Files

History

  • Receive Date: 22 August 2020
  • Revise Date: 03 June 2021
  • Accept Date: 02 August 2021

Share

How to cite

Statistics