Solving Weighted Number of Operation Plus Processing Time Due-Date Assignment, Weighted Scheduling and Process Planning Integration Problem Using Genetic and Simulated Annealing Search Methods

Authors: Halil Ibrahim Demir, Caner Erden, Mumtaz Ipek, Ozer Uygun

Abstract:

Traditionally, the three important manufacturing functions, which are process planning, scheduling and due-date assignment, are performed separately and sequentially. For couple of decades, hundreds of studies are done on integrated process planning and scheduling problems and numerous researches are performed on scheduling with due date assignment problem, but unfortunately the integration of these three important functions are not adequately addressed. Here, the integration of these three important functions is studied by using genetic, random-genetic hybrid, simulated annealing, random-simulated annealing hybrid and random search techniques. As well, the importance of the integration of these three functions and the power of meta-heuristics and of hybrid heuristics are studied.

Keywords: Process planning, weighted scheduling, weighted due-date assignment, genetic search, simulated annealing, hybrid meta-heuristics.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1128107

References:

[1] X. Xu, L. Wang, and S. T. Newman, “Computer-aided process planning–A critical review of recent developments and future trends,” Int. J. Comput. Integr. Manuf., vol. 24, no. 1, pp. 1–31, 2011.
[2] X. Li, L. Gao, and X. Wen, “Application of an efficient modified particle swarm optimization algorithm for process planning,” Int. J. Adv. Manuf. Technol., vol. 67, no. 5–8, pp. 1355–1369, Nov. 2012.
[3] X. Shao, X. Li, L. Gao, and C. Zhang, “Integration of process planning and scheduling—a modified genetic algorithm-based approach,” Comput. Oper. Res., vol. 36, no. 6, pp. 2082–2096, 2009.
[4] T. Sauter, J. Peschke, A. Luder, and others, “Distributed automation: PABADIS vs. HMS,” in Industrial Informatics, 2003. INDIN 2003. Proceedings. IEEE International Conference on, 2003, pp. 294–300.
[5] H. H. Cheng, F. Proctor, J. L. Michaloski, and W. P. Shackleford, “Real-time computing in open systems for manufacturing,” J. Comput. Inf. Sci. Eng., vol. 1, no. 1, pp. 92–99, 2001.
[6] J. Y.-T. Leung, Handbook of Scheduling: Algorithms, Models, and Performance Analysis. CRC Press, 2004.
[7] H. Lee and S.-S. Kim, “Integration of process planning and scheduling using simulation based genetic algorithms,” Int. J. Adv. Manuf. Technol., vol. 18, no. 8, pp. 586–590, 2001.
[8] G. Chryssolouris, S. Chan, and N. P. Suh, “An integrated approach to process planning and scheduling,” CIRP Ann.-Manuf. Technol., vol. 34, no. 1, pp. 413–417, 1985.
[9] R. M. Sundaram and S. Fu, “Process planning and scheduling—a method of integration for productivity improvement,” Comput. Ind. Eng., vol. 15, no. 1, pp. 296–301, 1988.
[10] K. Srihari and T. J. Greene, “MACRO-CAPP: a prototype CAPP system for an FMS,” Int. J. Adv. Manuf. Technol., vol. 5, no. 1, pp. 34–51, 1990.
[11] X. Li, L. Gao, C. Zhang, and X. Shao, “A review on integrated process planning and scheduling,” Int. J. Manuf. Res., vol. 5, no. 2, pp. 161–180, 2010.
[12] R. K. Phanden, A. Jain, and R. Verma, “Integration of process planning and scheduling: a state-of-the-art review,” Int. J. Comput. Integr. Manuf., vol. 24, no. 6, pp. 517–534, 2011.
[13] W. Tan and B. Khoshnevis, “Integration of process planning and scheduling—a review,” J. Intell. Manuf., vol. 11, no. 1, pp. 51–63, 2000.
[14] A. Baykasoğlu and L. Özbakır, “A grammatical optimization approach for integrated process planning and scheduling,” J. Intell. Manuf., vol. 20, no. 2, pp. 211–221, 2009.
[15] Y. W. Guo, W. D. Li, A. R. Mileham, and G. W. Owen, “Optimisation of integrated process planning and scheduling using a particle swarm optimisation approach,” Int. J. Prod. Res., vol. 47, no. 14, pp. 3775–3796, 2009.
[16] A. Jain, P. K. Jain, and I. P. Singh, “An integrated scheme for process planning and scheduling in FMS,” Int. J. Adv. Manuf. Technol., vol. 30, no. 11–12, pp. 1111–1118, 2006.
[17] M. Kumar and S. Rajotia, “Integration of process planning and scheduling in a job shop environment,” Int. J. Adv. Manuf. Technol., vol. 28, no. 1–2, pp. 109–116, 2006.
[18] A. H. Mantawy, Y. L. Abdel-Magid, and S. Z. Selim, “Integrating genetic algorithms, tabu search, and simulated annealing for the unit commitment problem,” IEEE Trans. Power Syst., vol. 14, no. 3, pp. 829–836, 1999.
[19] N. Morad and A. M. S. Zalzala, “Genetic algorithms in integrated process planning and scheduling,” J. Intell. Manuf., vol. 10, no. 2, pp. 169–179, 1999.
[20] H.-S. Yan, Q.-F. Xia, M.-R. Zhu, X.-L. Liu, and Z.-M. Guo, “Integrated production planning and scheduling on automobile assembly lines,” Iie Trans., vol. 35, no. 8, pp. 711–725, 2003.
[21] W. D. Li, S. K. Ong, and A. Y. C. Nee, “Optimization of process plans using a constraint-based tabu search approach,” Int. J. Prod. Res., vol. 42, no. 10, pp. 1955–1985, 2004.
[22] C. Moon, J. Kim, and S. Hur, “Integrated process planning and scheduling with minimizing total tardiness in multi-plants supply chain,” Comput. Ind. Eng., vol. 43, no. 1, pp. 331–349, 2002.
[23] X. Li, X. Shao, L. Gao, and W. Qian, “An effective hybrid algorithm for integrated process planning and scheduling,” Int. J. Prod. Econ., vol. 126, no. 2, pp. 289–298, 2010.
[24] P. Brandimarte, “Routing and scheduling in a flexible job shop by tabu search,” Ann. Oper. Res., vol. 41, no. 3, pp. 157–183, 1993.
[25] G. H. Ma, Y. F. Zhang, and A. Y. C. Nee, “A simulated annealing-based optimization algorithm for process planning,” Int. J. Prod. Res., vol. 38, no. 12, pp. 2671–2687, 2000.
[26] W. D. Li and C. A. McMahon, “A simulated annealing-based optimization approach for integrated process planning and scheduling,” Int. J. Comput. Integr. Manuf., vol. 20, no. 1, pp. 80–95, 2007.
[27] D.-H. Lee, D. Kiritsis, and P. Xirouchakis, “Search heuristics for operation sequencing in process planning,” Int. J. Prod. Res., vol. 39, no. 16, pp. 3771–3788, 2001.
[28] S. Wan, T. N. Wong, S. Zhang, L. Zhang “Integrated process planning and scheduling with setup time consideration by ant colony optimization,” HKU Theses Online HKUTO, 2012.
[29] W. D. Li, S. K. Ong, and A. Y. C. Nee, “Hybrid genetic algorithm and simulated annealing approach for the optimization of process plans for prismatic parts,” Int. J. Prod. Res., vol. 40, no. 8, pp. 1899–1922, 2002.
[30] M. Yu, Y. Zhang, K. Chen, and D. Zhang, “Integration of process planning and scheduling using a hybrid GA/PSO algorithm,” Int. J. Adv. Manuf. Technol., vol. 78, no. 1–4, pp. 583–592, 2015.
[31] Y. Wang and J. H. Liu, “Chaotic particle swarm optimization for assembly sequence planning,” Robot. Comput.-Integr. Manuf., vol. 26, no. 2, pp. 212–222, 2010.
[32] F. Zhao, Y. Hong, D. Yu, Y. Yang, and Q. Zhang, “A hybrid particle swarm optimisation algorithm and fuzzy logic for process planning and production scheduling integration in holonic manufacturing systems,” Int. J. Comput. Integr. Manuf., vol. 23, no. 1, pp. 20–39, 2010.
[33] Y. K. Kim, K. Park, and J. Ko, “A symbiotic evolutionary algorithm for the integration of process planning and job shop scheduling,” Comput. Oper. Res., vol. 30, no. 8, pp. 1151–1171, 2003.
[34] M. K. Lim and D. Z. Zhang, “An integrated agent-based approach for responsive control of manufacturing resources,” Comput. Ind. Eng., vol. 46, no. 2, pp. 221–232, 2004.
[35] V. Gordon, J.-M. Proth, and C. Chu, “A survey of the state-of-the-art of common due date assignment and scheduling research,” Eur. J. Oper. Res., vol. 139, no. 1, pp. 1–25, 2002.
[36] J.-B. Wang, “Single machine scheduling with common due date and controllable processing times,” Appl. Math. Comput., vol. 174, no. 2, pp. 1245–1254, 2006.
[37] S.-W. Lin, S.-Y. Chou, and S.-C. Chen, “Meta-heuristic approaches for minimizing total earliness and tardiness penalties of single-machine scheduling with a common due date,” J. Heuristics, vol. 13, no. 2, pp. 151–165, 2007.
[38] K.-C. Ying, “Minimizing earliness–tardiness penalties for common due date single-machine scheduling problems by a recovering beam search algorithm,” Comput. Ind. Eng., vol. 55, no. 2, pp. 494–502, 2008.
[39] A. C. Nearchou, “A differential evolution approach for the common due date early/tardy job scheduling problem,” Comput. Oper. Res., vol. 35, no. 4, pp. 1329–1343, 2008.
[40] Y. Xia, B. Chen, and J. Yue, “Job sequencing and due date assignment in a single machine shop with uncertain processing times,” Eur. J. Oper. Res., vol. 184, no. 1, pp. 63–75, 2008.
[41] V. S. Gordon and V. A. Strusevich, “Single machine scheduling and due date assignment with positionally dependent processing times,” Eur. J. Oper. Res., vol. 198, no. 1, pp. 57–62, 2009.
[42] H. I. Demir, T. Cakar, M. Ipek, O. Uygun, and M. Sari, “Process Planning and Due-date Assignment with ATC Dispatching where Earliness, Tardiness and Due-dates are Punished,” J. Ind. Intell. Inf. Vol, vol. 3, no. 3, 2015.
[43] H. I. Demir, O. Uygun, I. Cil, M. Ipek, and M. Sari, “Process Planning and Scheduling with SLK Due-Date Assignment where Earliness, Tardiness and Due-Dates are Punished,” J. Ind. Intell. Inf. Vol, vol. 3, no. 3, 2015.
[44] C. E. and D. Halil Ibrahim, “Benefits of integrating due date assignment with process planning and scheduling,” Master Thesis, Sakarya University, 2007.
[45] D. Halil Ibrahim and T. Harun, “Integrated process planning, scheduling and due date assignment,” PhD thesis, Sakarya University, 2005.
[46] H. John, Holland, Adaptation in natural and artificial systems. MIT Press, Cambridge, MA, 1992.
[47] S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi, and others, “Optimization by simmulated annealing,” science, vol. 220, no. 4598, pp. 671–680, 1983.
[48] V. Černỳ, “Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm,” J. Optim. Theory Appl., vol. 45, no. 1, pp. 41–51, 1985.