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...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2025-12-01
|
| Series: | Operations Research Perspectives |
| Subjects: | |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S2214716025000193 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850164351724421120 |
|---|---|
| author | Dung-Ying Lin Che-Hao Chen |
| author_facet | Dung-Ying Lin Che-Hao Chen |
| author_sort | Dung-Ying Lin |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-541b326c14164e63aab9f6da60b59272 |
| institution | OA Journals |
| issn | 2214-7160 |
| language | English |
| publishDate | 2025-12-01 |
| publisher | Elsevier |
| record_format | Article |
| series | Operations Research Perspectives |
| spelling | doaj-art-541b326c14164e63aab9f6da60b592722025-08-20T02:22:01ZengElsevierOperations Research Perspectives2214-71602025-12-011510034310.1016/j.orp.2025.100343A branch-and-price solution strategy for integrated process planning and scheduling problemsDung-Ying Lin0Che-Hao Chen1Department of Industrial Engineering and Engineering Management, National Tsing Hua University, Hsinchu, TaiwanDepartment of Industrial Engineering and Engineering Management, National Tsing Hua University, Hsinchu, TaiwanThis 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.http://www.sciencedirect.com/science/article/pii/S2214716025000193ProductionIntegrated process planning and scheduling problemColumn generationDantzig-wolfe decompositionBranch-and-price |
| spellingShingle | Dung-Ying Lin Che-Hao Chen A branch-and-price solution strategy for integrated process planning and scheduling problems Operations Research Perspectives Production Integrated process planning and scheduling problem Column generation Dantzig-wolfe decomposition Branch-and-price |
| title | A branch-and-price solution strategy for integrated process planning and scheduling problems |
| title_full | A branch-and-price solution strategy for integrated process planning and scheduling problems |
| title_fullStr | A branch-and-price solution strategy for integrated process planning and scheduling problems |
| title_full_unstemmed | A branch-and-price solution strategy for integrated process planning and scheduling problems |
| title_short | A branch-and-price solution strategy for integrated process planning and scheduling problems |
| title_sort | branch and price solution strategy for integrated process planning and scheduling problems |
| topic | Production Integrated process planning and scheduling problem Column generation Dantzig-wolfe decomposition Branch-and-price |
| url | http://www.sciencedirect.com/science/article/pii/S2214716025000193 |
| work_keys_str_mv | AT dungyinglin abranchandpricesolutionstrategyforintegratedprocessplanningandschedulingproblems AT chehaochen abranchandpricesolutionstrategyforintegratedprocessplanningandschedulingproblems AT dungyinglin branchandpricesolutionstrategyforintegratedprocessplanningandschedulingproblems AT chehaochen branchandpricesolutionstrategyforintegratedprocessplanningandschedulingproblems |