A branch-and-price solution strategy for integrated process planning and scheduling problems

This research investigates the integrated process planning and scheduling (IPPS) problem that considers process planning and production scheduling simultaneously with the aim of minimizing makespan. To solve the IPPS problem, we propose a branch-and-price (B&P) solution strategy that decomposes the problem according to the Dantzig-Wolfe principle and searches for integer solutions with a branch-and-bound framework. The decomposed master problem solves the scheduling problem and determines the corresponding timing information. The subproblem finds the optimal processing route and machine assignment based on the pricing information passed from the master problem. One of the critical features of the decomposition strategy is that the resulting subproblem can be reduced to a shortest path problem and can be solved with a proposed linear time algorithm. Numerical results show that the proposed B&P solution strategy can effectively and efficiently solve benchmark problem instances. Managerial insights are drawn based on the numerical results and sensitivity analysis to demonstrate the practical use of the proposed framework.