Solving the integrated process planning and scheduling problem using an enhanced constraint programming-based approach

Abstract

Due to various factors of flexibility introduced into manufacturing systems, researchers have gradually shifted their focus to the integrated process planning and scheduling (IPPS) problem to improve productivity. The previous literature rarely associates IPPS with constraint programming, even though constraint programming has achieved success in the scheduling field. Furthermore, existing approaches are usually customized to certain types of IPPS problems and cannot handle the general problem. In this paper, with a view to obtaining the optimal AND/OR graph automatically, a depth first search generating algorithm is designed to convert the type-1 IPPS problem into our approach's standard input format. Moreover, we propose an approach based on enhanced constraint programming to cope with the general problem, employing advanced schemes to enhance the constraint propagation and improve the search efficiency. Our approach is implemented on ORTOOLS, and its superiority is verified by testing on 15 benchmarks with 50 instances. Experimental results indicate that 41 instances are solved optimally, among which the optimality of the solutions for 20 instances is newly confirmed, and the solutions of six instances are improved. Our approach is the first method to reach the overall optimum in the most influential benchmark with 24 instances.

Keywords:

• integrated process planning and scheduling
• constraint programming
• AND/OR graph
• graph-based model
• depth first search

Acknowledgments

We would like to thank the anonymous reviewers for their comments that greatly improve the manuscript.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

The work is supported by Anhui Center for Applied Mathematics, and the NSF of China (No. 11871447, 71991464/71991460).

Notes on contributors

Ganquan Shi

Ganquan Shi is currently a Ph.D. student in the School of Mathematical Sciences at University of Science and Technology of China (USTC). His research interests include operations research, discrete optimization, and scheduling problems.

Zhouwang Yang

Zhouwang Yang is a Professor in the School of Mathematical Sciences at University of Science and Technology of China (USTC). He received his Bachelor degree, Master degree and Ph.D. degree in Mathematics from USTC in 1997, 2000, and 2005, respectively. He worked at Seoul National University as a postdoctoral researcher from 2006 to 2007. He was a visiting scholar in School of Industrial and Systems Engineering (ISyE) at Georgia Institute of Technology during 2010-2011. He has been working on computation and optimization in data science. His main research interests include geometric modeling and processing, data-driven optimization modeling, mathematical theory of machine learning, etc.

Yang Xu

Yang Xu is currently a Ph.D. student in the School of Data Science at University of Science and Technology of China (USTC). His research interests include operations research, reinforcement learning, and packing problem.

Yuchen Quan

Yuchen Quan is currently pursuing the Bachelor degree in the School of Mathematical Sciences at University of Science and Technology of China (USTC). His research interests include operations research and computer graphics.