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

doi:10.1080/00207543.2021.1963496

Return

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

2021-08-30

PRE

Ganquan Shi

杨

杨周旺 (Zhouwang Yang) *

Yang Xu

Yuchen Quan

DOI：10.1080/00207543.2021.1963496

Original

Original request for help

Save

Abstract

En 中文

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