New mathematical modeling and a constructive heuristic algorithm for integrated process planning and scheduling

Document Type : Research Paper

Authors

School of Industrial Engineering, Iran University of Science and Technology, Tehran, Iran

Abstract

Recent advances in manufacturing systems and multifunction machines have caused products to be produced through several alternative process plans. Therefore, the integration of process planning and scheduling, as two of the most critical functions, becomes essential to enhance manufacturing systems’ productivity. Several different algorithms have solved the integrated process planning and scheduling (IPPS) problem in the literature. All proposed algorithms require a list of available process plans in advance (type-1). In this paper, an efficient mixed-integer linear programming (MILP) model is presented based on the term "combination." Besides, a type-2 priority-based heuristic algorithm (PBHA II) is proposed using dispatching rules with prioritizing jobs, combinations, and operations to solve the IPPS problems expressed by AND/OR graphs and with a makespan criterion. The MILP model and proposed heuristic algorithm are tested on the most challenging benchmark problems. Experimental results show the superiority of the MILP model over the best one in the literature, as well as the effectiveness and high performance of PBHA II. New upper bounds have been obtained in a short computational time for 7 of 24 most complex problems, which have been used by many researchers over the last two decades.

Keywords

Main Subjects

References

Amin-Naseri, M. R. & Afshari, A. J. (2012). A hybrid genetic algorithm for integrated process planning and scheduling problem with precedence constraints. The International Journal of Advanced Manufacturing Technology, 59, 273-287.
 
Ausaf, M. F., Gao, L., Li, X. & Al Aqel, G. (2015). A priority-based heuristic algorithm (PBHA) for optimizing integrated process planning and scheduling problem. Cogent Engineering, 2, 1070494.
 
Awad, M. A. & Abd-Elaziz, H. M. An Efficient Modified Genetic Algorithm for Integrated Process Planning-Job Scheduling.  (2021) International Mobile, Intelligent, and Ubiquitous Computing Conference, MIUCC 2021, 2021. 319-323.
 
Barzanji, R., Naderi, B. & Begen, M. A. (2019). Decomposition algorithms for the integrated process planning and scheduling problem. Omega, 102025.
 
Bensmaine, A., Dahane, M. & Benyoucef, L. (2014). A new heuristic for integrated process planning and scheduling in reconfigurable manufacturing systems. International Journal of Production Research, 52, 3583-3594.
 
Chan, F. T. S., Chung, S. H. & Chan, L. Y. (2008). An introduction of dominant genes in genetic algorithm for FMS. International Journal of Production Research, 46, 4369-4389.
 
Chryssolouris, G., Pierce, J. E. & Dicke, K. (1992). A decision-making approach to the operation of flexible manufacturing systems. International Journal of Flexible Manufacturing Systems, 4, 309-330.
 
Fuqing, Z., Aihong, Z., Dongmei, Y. & Yahong, Y. A Hybrid Particle Swarm Optimization(PSO) Algorithm Schemes for Integrated Process Planning and Production Scheduling.  (2006) 6th World Congress on Intelligent Control and Automation, 21-23 June 2006 2006. 6772-6776.
 
Guo, Y. W., Li, W. D., Mileham, A. R. & Owen, G. W. (2009). Optimisation of integrated process planning and scheduling using a particle swarm optimisation approach. International Journal of Production Research, 47, 3775-3796.
 
Hengyun, Z., Wenhua, Y. & Guangxia, B. A particle swarm optimization for integrated process planning and scheduling.  (2009) IEEE 10th International Conference on Computer-Aided Industrial Design & Conceptual Design, 26-29 Nov. 2009 2009. 1070-1074.
Jain, A. K. & Elmaraghy, H. A. (1997). Production scheduling/rescheduling in flexible manufacturing. International Journal of Production Research, 35, 281-309.
 
Jin, L., Tang, Q., Zhang, C., Shao, X. & Tian, G. (2016a). More MILP models for integrated process planning and scheduling. International Journal of Production Research, 54, 4387-4402.
 
Jin, L., Zhang, C. & Shao, X. (2015). An effective hybrid honey bee mating optimization algorithm for integrated process planning and scheduling problems. The International Journal of Advanced Manufacturing Technology, 80, 1253-1264.
 
Jin, L., Zhang, C., Shao, X., Yang, X. & Tian, G. (2016b). A multi-objective memetic algorithm for integrated process planning and scheduling. The International Journal of Advanced Manufacturing Technology, 85, 1513-1528.
 
Keddari, N., Mebarki, N., Shahzad, A., & Sari, Z. (2018). Solving an integration process planning and scheduling in a flexible job shop using a hybrid approach. In Computational Intelligence and Its Applications: 6th IFIP TC 5 International Conference, CIIA 2018, Oran, Algeria, May 8-10, 2018, Proceedings 6 (pp. 387-398). Springer International Publishing.
 
MOHAMED, O. & DJEBBAR, B., eds. Computational Intelligence and Its Applications, (2018) Cham. Springer International Publishing, 387-398.
 
Kim, K. H. & Egbelu, P. J. (1999). Scheduling in a production environment with multiple process plans per job. International Journal of Production Research, 37, 2725-2753.
 
Kim, Y. K., Kim, J. Y. & Shin, K. S. (2007). An asymmetric multileveled symbiotic evolutionary algorithm for integrated FMS scheduling. Journal of Intelligent Manufacturing, 18, 631-645.
 
Kim, Y. K., Park, K. & Ko, J. (2003). A symbiotic evolutionary algorithm for the integration of process planning and job shop scheduling. Computers & Operations Research, 30, 1151-1171.
 
Lee, H. & Kim, S.-S. (2001). Integration of Process Planning and Scheduling Using Simulation Based Genetic Algorithms. The International Journal of Advanced Manufacturing Technology, 18, 586-590.
 
Leung, C., Wong, T., Mak, K.-L. & Fung, R. Y. (2010). Integrated process planning and scheduling by an agent-based ant colony optimization. Computers & Industrial Engineering, 59, 166-180.
 
Li, W. & Mcmahon, C. A. (2007). A simulated annealing-based optimization approach for integrated process planning and scheduling. International Journal of Computer Integrated Manufacturing, 20, 80-95.
 
Li, X., Gao, L. & Li, W. (2012a). Application of game theory based hybrid algorithm for multi-objective integrated process planning and scheduling. Expert Systems with Applications, 39, 288-297.
 
Li, X., Gao, L., Pan, Q., Wan, L. & Chao, K.-M. (2019). An Effective Hybrid Genetic Algorithm and Variable Neighborhood Search for Integrated Process Planning and Scheduling in a Packaging Machine Workshop. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 49, 1933-1945.
 
Li, X., Gao, L. & Shao, X. (2012b). An active learning genetic algorithm for integrated process planning and scheduling. Expert Systems with Applications, 39, 6683-6691.
 
Li, X., Gao, L., Shao, X., Zhang, C. & Wang, C. (2010a). Mathematical modeling and evolutionary algorithm-based approach for integrated process planning and scheduling. Computers & Operations Research, 37, 656-667.
Li, X., Gao, L., Zhang, C. & Shao, X. (2010b). A review on integrated process planning and scheduling. International Journal of Manufacturing Research, 5, 161-180.
 
Li, X., Gao, L., Zhang, G., Zhang, C., & Shao, X. (2008). A genetic algorithm for integration of process planning and scheduling problem. In Intelligent Robotics and Applications: First International Conference, ICIRA 2008 Wuhan, China, October 15-17, 2008 Proceedings, Part II 1 (pp. 495-502). Springer Berlin Heidelberg.
 
Li, X., Shao, X., Gao, L. & Qian, W. (2010c). An effective hybrid algorithm for integrated process planning and scheduling. International Journal of Production Economics, 126, 289-298.
 
Li, X., Zhang, C., Gao, L., Li, W. & Shao, X. (2010d). An agent-based approach for integrated process planning and scheduling. Expert Syst. Appl., 37, 1256-1264.
 
Lian, K., Zhang, C., Gao, L. & Li, X. (2012). Integrated process planning and scheduling using an imperialist competitive algorithm. International Journal of Production Research, 50, 4326-4343.
 
Lihong, Q. & Shengping, L. (2012). An improved genetic algorithm for integrated process planning and scheduling. The International Journal of Advanced Manufacturing Technology, 58, 727-740.
 
Liu, M., Yi, S. & Wen, P. (2018). Quantum-inspired hybrid algorithm for integrated process planning and scheduling. Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture, 232, 1105-1122.
 
Liu, N., Zhang, Y. F. & Lu, W. F. (2020). Energy-efficient integration of process planning and scheduling in discrete parts manufacturing with a heuristic-based two-stage approach. The International Journal of Advanced Manufacturing Technology, 106, 2415-2432.
 
Liu, X., Ni, Z. & Qiu, X. (2016). Application of ant colony optimization algorithm in integrated process planning and scheduling. The International Journal of Advanced Manufacturing Technology, 84, 393-404.
 
Luo, G., Wen, X., Li, H., Ming, W. & Xie, G. (2017). An effective multi-objective genetic algorithm based on immune principle and external archive for multi-objective integrated process planning and scheduling. The International Journal of Advanced Manufacturing Technology, 91, 3145-3158.
 
Manne, A. S. (1960). On the Job-Shop Scheduling Problem. Operations Research, 8, 219-223.
 
Özgüven, C., Özbakır, L. & Yavuz, Y. (2010). Mathematical models for job-shop scheduling problems with routing and process plan flexibility. Applied Mathematical Modelling, 34, 1539-1548.
 
Park, B. J. & Choi, H. R. A Genetic Algorithm for Integration of Process Planning and Scheduling in a Job Shop. (2006) Berlin, Heidelberg. Springer Berlin Heidelberg, 647-657.
 
Rajkumar, M., Asokan, P., Page, T. & Arunachalam, S. (2010). A GRASP algorithm for the Integration of Process Planning and Scheduling in a flexible job-shop. International Journal of Manufacturing Research, 5, 230-251.
 
Shao, X., Li, X., Gao, L. & Zhang, C. (2009). Integration of process planning and scheduling—a modified genetic algorithm-based approach. Computers & Operations Research, 36, 2082-2096.
 
Tan, W. & Khoshnevis, B. (2004). A linearized polynomial mixed integer programming model for the integration of process planning and scheduling. Journal of Intelligent Manufacturing, 15, 593-605.
 
Tian, Y., Jiang, P. & Zheng, M. (2008). An Immune Algorithm for the integration of process planning and scheduling. International Journal of Materials and Product Technology, 33, 95.
 
Uslu, M. F., Uslu, S. & Bulut, F. (2022). An adaptive hybrid approach: Combining genetic algorithm and ant colony optimization for integrated process planning and scheduling. Applied Computing and Informatics, 18, 101-112.
 
Wagner, H. M. (1959). An integer linear-programming model for machine scheduling. Naval Research Logistics Quarterly, 6, 131-140.
 
Wang, J., Fan, X., Zhang, C. & Wan, S. (2014). A graph-based ant colony optimization approach for integrated process planning and scheduling. Chinese Journal of Chemical Engineering, 22, 748-753.
 
Wong, T., Leung, C., Mak, K.-L. & Fung, R. Y. (2006a). Dynamic shopfloor scheduling in multi-agent manufacturing systems. Expert Systems with Applications, 31, 486-494.
 
Wong, T., Zhang, S., Wang, G. & Zhang, L. (2012). Integrated process planning and scheduling–multi-agent system with two-stage ant colony optimisation algorithm. International Journal of Production Research, 50, 6188-6201.
 
Wong, T. N., Leung, C. W., Mak, K. L. & Fung, R. Y. K. (2006b). An agent-based negotiation approach to integrate process planning and scheduling. International Journal of Production Research, 44, 1331-1351.
 
Wong, T. N., Leung, C. W., Mak, K. L. & Fung, R. Y. K. (2006c). Integrated process planning and scheduling/rescheduling—an agent-based approach. International Journal of Production Research, 44, 3627-3655.
 
Wu, X. & Li, J. (2021). Two layered approaches integrating harmony search with genetic algorithm for the integrated process planning and scheduling problem. Computers and Industrial Engineering, 155.
 
Zhang, L. & Wong, T. N. (2015). An object-coding genetic algorithm for integrated process planning and scheduling. European Journal of Operational Research, 244, 434-444.
 
Zhang, L. & Wong, T. N. (2016). Solving integrated process planning and scheduling problem with constructive meta-heuristics. Information Sciences, 340–341, 1-16.
 
Zhang, S. & Wong, T. N. (2014). Integrated process planning and scheduling: an enhanced ant colony optimization heuristic with parameter tuning. Journal of Intelligent Manufacturing, 29, 585-601.
 
Zhao, F., Zhu, A., Ren, Z., & Yang, Y. (2006, June). Integration of process planning and production scheduling based on a hybrid PSO and SA algorithm. In 2006 International Conference on Mechatronics and Automation (pp. 2290-2295). IEEE.
 
Zhu, X., Guo, X., Wang, W. & Wu, J. (2022). A Genetic Programming-Based Iterative Approach for the Integrated Process Planning and Scheduling Problem. IEEE Transactions on Automation Science and Engineering, 19, 2566-2580.
Journal of Industrial and Systems Engineering
Volume 14, Issue 4 - Serial Number 4
November 2022
Pages 30-49

Files

History

  • Receive Date: 07 October 2022
  • Revise Date: 02 December 2022
  • Accept Date: 15 December 2022

Share

How to cite

Statistics