A modified integer and categorical PSO algorithm for solving integrated process planning, dynamic scheduling, and due date assignment problem

Document Type : Article

Authors

1 Department of International Trade and Finance, Faculty of Applied Science, Sakarya University of Applied Science, Sakarya, Turkey

2 Department of Industrial Engineering, Faculty of Engineering, Sakarya University, Turkey

Abstract

Particle Swarm Optimization (PSO) has many successful applications on solving continuous optimization problems. It has been adapted to solve discrete optimization problems using different variants, such as integer PSO (IPSO), discrete PSO (DPSO) and integer and categorical PSO (ICPSO). ICPSO, a recent PSO variant, uses probability distributions instead of the solution values. In this study, we applied ICPSO algorithm to solve dynamic integrated process planning, scheduling and due date assignment (DIPPSDDA) problem which is a higher integration level of well-known problems which are integrated process planning and scheduling (IPPS) and scheduling with due date assignment (SWDDA). Briefly, due date assignment function is integrated to IPPS problem as the third manufacturing function in DIPPSDDA. Furthermore, DIPPSDDA performs scheduling function in a dynamic environment in where jobs arrive to shop floor in any time. The objective of DIPPSDDA problem is to minimize the earliness, tardiness and given due dates length. Since the experimental results show that ICPSO does not find better solutions, crossover and mutation operators used in genetic algorithm were implemented to ICPSO, namely modified ICPSO (MICPSO). Finally, experimental results indicate that the proposed MICPSO provides better performance as compared to genetic algorithm, ICPSO and modified discrete PSO.

Keywords

References

References:
1. Chang, T.C. and Wysk, R.A. "An introduction to automated process planning systems", Prentice Hall Professional Technical Reference (1984).
2. Kahlbacher, H.G. and Cheng, T.C.E. "Parallel machine scheduling to minimize costs for earliness and number of tardy jobs", Discrete Appl. Math., 47(2), pp. 139-164 (1993).
3. Zhang, S. and Wong, T.N. "Integrated process planning and scheduling: an enhanced ant colony optimization heuristic with parameter tuning", J. Intell. Manuf., 29(3), pp. 585-601 (2018).
4. Sobeyko, O. and Monch, L. "Integrated process planning and scheduling for large-scale flexible job shops using metaheuristics", Int. J. Prod. Res., 55(2), pp. 392-409 (2017).
5. Chaudhry, I.A. "A genetic algorithm approach for process planning and scheduling in job shop environment", Proceedings of the World Congress on Engineering 2012, pp. 1-6 (2012).
6. Luo, G., Wen, X., Li, H., et al. "An effective multiobjective genetic algorithm based on immune principle and external archive for multi-objective integrated process planning and scheduling", Int. J. Adv. Manuf. Technol., 91(9), pp. 3145-3158 (2017).
7. Zhang, S. and Wong, T.N. "Studying the impact of sequence-dependent set-up times in integrated process planning and scheduling with E-ACO heuristic", Int. J. Prod. Res., 54(16), pp. 4815-4838 (2016).
8. Petrovic, M., Petronijevic, J., Mitic, M., et al. "The ant lion optimization algorithm for integrated process planning and scheduling", Applied Mechanics and Materials, 834(5), pp. 187-192 (2016). DOI: 10.4028/www.scientific.net/AMM.834.187.
9. Manupati, V.K., Putnik, G.D., Tiwari, M.K., et al. "Integration of process planning and scheduling using mobile-agent based approach in a networked manufacturing environment", Comput. Ind. Eng., 94, pp. 63-73 (2016).
10. Meenakshi Sundaram, R. and Fu, S. "Process planning and scheduling - A method of integration for productivity improvement", Comput. Ind. Eng., 15(1-4), pp. 296-301 (1988).
11. Khoshnevis, B. and Chen, Q.M. "Integration of process planning and scheduling functions", J. Intell. Manuf., 2(3), pp. 165-175 (1991).
12. Zhang, H.C. and Mallur, S. "An integrated model of process planning and production scheduling", Int. J. Comput. Integr. Manuf., 7(6), pp. 356-364 (1994).
13. Morad, N. and Zalzala, A. "Genetic algorithms in integrated process planning and scheduling", J. Intell. Manuf., 10(2), pp. 169-179 (1999).
14. Phanden, R.K., Jain, A., and Verma, R. "Integration of process planning and scheduling: a state-of-the-art review", Int. J. Comput. Integr. Manuf., 24(6), pp. 517-534 (2011).
15. Li, X. and Gao, L. "Effective methods for integrated process planning and scheduling", Engineering Applications of Computational Methods, Springer-Verlag, Berlin Heidelberg (2020).
16. Phanden, R.K., Jain, A., and Davim, J.P., Eds. Integration of Process Planning and Scheduling: Approaches and Algorithms, 1st Edn., CRC Press, Boca Raton (2019).
17. Li, X., Gao, L., Pan, Q., et al. "An effective hybrid  genetic algorithm and variable neighborhood search for integrated process planning and scheduling in a packaging machine workshop", IEEE Trans. Syst. Man Cybern. Syst., 49(10), pp. 1933-1945 (2019).
18. Lin, C.S., Li, P.Y., Wei, J.M., et al. "Integration of process planning and scheduling for distributed  flexible job shops", Comput. Oper. Res., 124, p. 105053 (2020).
19. Chen, Z.L. "Scheduling and common due date assignment with earliness-tardiness penalties and batch delivery costs", Eur. J. Oper. Res., 93(1), pp. 49-60 (1996).
20. Gordon, V., Proth, J.M., and Chu, C. "A survey of the state-of-the-art of common due date assignment and scheduling research", Eur. J. Oper. Res., 139(1), pp. 1-25 (2002).
21. Zhao, C., Hsu, C.J., Lin, W.C., et al. "Due date assignment and scheduling with time and positional dependent effects", J. Inf. Optim. Sci., 39, pp. 1613- 1626 (2018). DOI: 10.1080/02522667.2017.1367515.
22. Xiong, X., Wang, D., Cheng, T.C.E., et al. "Singlemachine scheduling and common due date assignment with potential machine disruption", Int. J. Prod. Res., 56(3), pp. 1345-1360 (2018).
23. Yin, Y., Wang, W., Wang, D., et al. "Multi-agent single-machine scheduling and unrestricted due date assignment with a fixed machine unavailability interval", Comput. Ind. Eng., 111, pp. 202-215 (2017).
24. Liu, W., Hu, X., and Wang, X. "Single machine scheduling with slack due dates assignment", Eng. Optim., 49(4), pp. 709-717 (2017).
25. Wang, D.J., Yin, Y., Cheng, S.R., et al. "Due date assignment and scheduling on a single machine with two competing agents", Int. J. Prod. Res., 54(4), pp. 1152-1169 (2016).
26. Yin, Y., Wang, D., and Cheng, T.C.E. "Due daterelated scheduling with two agents: Models and algorithms", Uncertainty and Operations Research, Springer Singapore (2020).
27. Wang, Y., Wang, J.Q., and Yin, Y. "Multitasking scheduling and due date assignment with deterioration effect and efficiency promotion", Comput. Ind. Eng., 146, p. 106569 (2020).
28. Shabtay, D. "Scheduling and due date assignment to minimize earliness, tardiness, holding, due date assignment and batch delivery costs", Int. J. Prod. Econ., 123(1), pp. 235-242 (2010).
29. Yin, Y., Cheng, T.C.E., Wu, C.C., et al. "Singlemachine batch delivery scheduling and common duedate assignment with a rate-modifying activity", Int. J. Prod. Res., 52(19), pp. 5583-5596 (2014).
30. Yuan, J. "A note on the complexity of singlemachine scheduling with a common due date, earlinesstardiness, and batch delivery costs", Eur. J. Oper. Res., 94(1), pp. 203-205 (1996).
31. Demir, H.I. and Taskin, H. "Integrated process planning, scheduling and due-date assignment", PhD Thesis, Sakarya University (2005).
32. Ceven, E. and Demir, H.I. "Benefits of integrating duedate assignment with process planning and scheduling", Master of Science Thesis, Sakarya University (2007).
33. Demir, H.I. and Erden, C. "Dynamic integrated process planning, scheduling and due-date assignment using ant colony optimization", Comput. Ind. Eng., 149, p. 106799 (2020).
34. Demir, H.I. and Phanden, R.K., Due-Date Agreement in Integrated Process Planning and Scheduling Environment Using Common Meta-Heuristics, CRC Press (2019).
35. Ouelhadj, D. and Petrovic, S. "A survey of dynamic scheduling in manufacturing systems", J. Sched., 12(4), pp. 417-431 (2009).
36. Ramasesh, R. "Dynamic job shop scheduling: A survey of simulation research", Omega, 18(1), pp. 43-57 (1990).
37. Yin, L., Gao, L., Li, X., et al. "An improved genetic algorithm with rolling window technology for dynamic integrated process planning and scheduling problem", 2017 IEEE 21st Int. Conf. Comput. Support. Coop. Work Des. CSCWD, pp. 414-419 (2017).
38. Ba, L., Li, Y., Yang, M., et al. "A mathematical model for multiworkshop IPPS problem in batch production", Math. Probl. Eng., 2018, p. 7948693 (2018).
39. Petrovic, M., Vukovic, N., Mitic, M., et al. "Integration of process planning and scheduling using chaotic particle swarm optimization algorithm", Expert Syst. Appl., 64, pp. 569-588 (2016).
40. Yu, M., Zhang, Y., Chen, K., et al. "Integration of process planning and scheduling using a hybrid GA/PSO algorithm", Int. J. Adv. Manuf. Technol., 78(1), pp. 583-592 (2015).
41. Petrovic, M., Mitic, M., Vukovic, N., et al. "Chaotic particle swarm optimization algorithm for  flexible process planning", Int. J. Adv. Manuf. Technol., 85(9), pp. 2535-2555 (2016).
42. Wang, Y.F., Zhang, Y.F., and Fuh, J.Y.H. "A PSObased multi-objective optimization approach to the integration of process planning and scheduling", IEEE ICCA 2010, pp. 614-619 (2010).
43. Erden, C., Demir, H.I., and Kokcam, A.H. "Solving integrated process planning, dynamic scheduling, and due date assignment using metaheuristic algorithms", Math. Probl. Eng., 2019, p. 1572614 (2019).
44. Janiak, A., Janiak, W.A., Krysiak, T., et al. "A survey on scheduling problems with due windows", Eur. J. Oper. Res., 242(2), pp. 347-357 (2015).
45. Yin, Y., Wang, D.J., Wu, C.C., et al. "CON/SLK due date assignment and scheduling on a single machine with two agents", Nav. Res. Logist. NRL, 63(5), pp. 416-429 (2016).
46. Browning, T.R. and Yassine, A.A. "Resourceconstrained multi-project scheduling: Priority rule performance revisited", Int. J. Prod. Econ., 126(2), pp. 212-228 (2010).
47. Sha, D.Y. and Liu, C.H. "Using data mining for due date assignment in a dynamic job shop environment", Int. J. Adv. Manuf. Technol., 25(11), pp. 1164-1174 (2005).
48. Haupt, R. "A survey of priority rule-based scheduling", Oper. Res. Spektrum, 11(1), pp. 3-16 (1989).
49. Adibi, M.A., Zandieh, M., and Amiri, M. "Multiobjective scheduling of dynamic job shop using variable neighborhood search", Expert Syst. Appl., 37(1), pp. 282-287 (2010).
50. Amin, G.R. and El-Bouri, A. "A minimax linear programming model for dispatching rule selection", Comput. Ind. Eng., 121, pp. 27-35 (2018).
51. Dominic, P.D.D., Kaliyamoorthy, S., and Kumar, M.S. "Efficient dispatching rules for dynamic job shop scheduling", Int. J. Adv. Manuf. Technol., 24(1), pp. 70-75 (2004).
52. Heger, J., Branke, J., Hildebrandt, T., et al. "Dynamic adjustment of dispatching rule parameters in flow shops with sequence-dependent set-up times", Int. J. Prod. Res., 54(22), pp. 6812-6824 (2016).
53. Pierreval, H. and Mebarki, N. "Dynamic scheduling selection of dispatching rules for manufacturing system", Int. J. Prod. Res., 35(6), pp. 1575-1591 (1997).
54. Qi, J.G., Burns, G.R., and Harrison, D.K. "The application of parallel multipopulation genetic algorithms to dynamic job-shop scheduling", Int. J. Adv. Manuf. Technol., 16(8), pp. 609-615 (2000).
55. Baker, K.R. and Kanet, J.J. "Job shop scheduling with modified due dates", J. Oper. Manag., 4(1), pp. 11-22 (1983).
56. Raghu, T.S. and Rajendran, C. "An efficient dynamic dispatching rule for scheduling in a job shop", Int. J. Prod. Econ., 32(3), pp. 301-313 (1993).
57. Vepsalainen, A.P.J. and Morton, T.E. "Priority rules for job shops with weighted tardiness costs", Manag. Sci., 33(8), pp. 1035-1047 (1987).
58. Strasser, S., Goodman, R., Sheppard, J., et al. "A new discrete particle swarm optimization algorithm", Proc. 2016 Genet. Evol. Comput. Conf.-GECCO 16, ACM Press, Denver, Colorado, USA, pp. 53-60 (2016).
59. Holland, J.H. "Genetic algorithms", Sci. Am., 267(1), pp. 66-73 (1992).
60. Li, X., Gao, L., and Shao, X. "An active learning genetic algorithm for integrated process planning and scheduling", Expert Syst. Appl., 39(8), pp. 6683-6691 (2012).
61. Lin, S., Goodman, E.D., and Punch, W.F. "A genetic algorithm approach to dynamic job shop scheduling", Probl. Proc. Seventh Int. Conf. Genet. Algorithms, pp. 481-489 (1997).
62. Park, B.J. and Choi, H.R. "A genetic algorithm for integration of process planning and scheduling in a job shop", AI 2006 Adv. Artif. Intell., A. Sattar and B. Kang, Eds., Lecture Notes in Computer Science, Springer, Berlin, Heidelberg, pp. 647-657 (2006).
63. Pezzella, F., Morganti, G., and Ciaschetti, G. "A genetic algorithm for the  flexible job-shop scheduling problem", Comput. Oper. Res., 35(10), pp. 3202-3212 (2008).
64. Xia, H., Li, X., and Gao, L. "A hybrid genetic algorithm with variable neighborhood search for dynamic integrated process planning and scheduling", Comput. Ind. Eng., 102, pp. 99-112 (2016).
65. Zhang, L., Gao, L., and Li, X. "A hybrid genetic algorithm and tabu search for a multi-objective dynamic job shop scheduling problem", Int. J. Prod. Res., 51(12), pp. 3516-3531 (2013).
66. Pan, Q.K., Tasgetiren, M.F., and Liang, Y.C. "A discrete particle swarm optimization algorithm for the no-wait  flowshop scheduling problem", Comput. Oper. Res., 35(9), pp. 2807-2839 (2008).
67. Oliphant, T.E., A Guide to NumPy, Trelgol Publishing USA (2006). 
68. Hunter, J.D. "Matplotlib: A 2D graphics environment", Comput. Sci. Eng., 9(3), p. 90 (2007).
69. McKinney, W., Python for Data Analysis: Data Wrangling with Pandas, NumPy, and IPython, 2 Edn., O'Reilly Media (2017).
70. Van der Ham, R. "Salabim: discrete event simulation and animation in Python", J. Open Source Softw., 3(27), p. 767 (2018).
71. Demir, H.I., Canpolat, O., Erden, C., et al. "Process planning and scheduling with WNOPPT weighted duedate assignment where earliness, tardiness and duedates are penalized", J. Intell. Syst., p. 10 (2018).
72. Demir, H.I. and Erden, C. "Solving process planning and weighted scheduling with WNOPPT weighted due-date assignment problem using some pure and hybrid meta-heuristics", Sak. Univ. J. Sci., 21(2), pp. 210-222 (2017).
73. Garey, M.R., Johnson, D.S., and Sethi, R. "The complexity of  flowshop and jobshop scheduling", Math. Oper. Res., 1(2), pp. 117-129 (1976).
Scientia Iranica
Volume 30, Issue 2
Transactions on Industrial Engineering (E)
March and April 2023
Pages 738-756

Files

Share

How to cite

Statistics