1459. A Surgery Scheduling Problem Solved by Branch and Price Enhanced by Machine Learning
Invited abstract in session TA-7: Scheduling models and algorithms II, stream Scheduling and Project Management.
Tuesday, 8:30-10:00Room: Clarendon GR.01
Authors (first author is the speaker)
| 1. | Přemysl Šůcha
|
| Czech Technical University in Prague | |
| 2. | Broos Maenhout
|
| Business Informatics and Operations Management, Ghent University | |
| 3. | Pavlína Koutecká
|
| Czech Technical University in Prague |
Abstract
This paper presents an operating room scheduling problem solved by the branch-and-price algorithm enhanced by machine learning. When branch and price is applied to large real-world problems, the problem is often decomposed into many subproblems with still non-negligible computational complexity. Since pricing problems often consume the majority of CPU time, we introduce a machine learning-based ranker that strategically guides the search for new columns in the column generation process. The solution to the master problem is analyzed by the ranker, which then suggests an order for solving the pricing problems to prioritize those with the potential to improve the master problem the most. This prioritization mechanism is essential for speeding up the column generation process since, by identifying new columns early in the process, we can terminate the search procedure sooner. Furthermore, our technique shows applicability to all nodes of the branching tree, making it a valuable tool for solving a wide range of optimization problems. We demonstrate the usefulness of this approach in the challenging domain of operating room scheduling. Experimental evaluations underscore the effectiveness of the developed algorithm, which consistently outperforms traditional search strategies in terms of time, number of pricing problems solved, nodes searched in the branch tree, and column generation iterations performed.
Keywords
- Scheduling
- Algorithms
- Machine Learning
Status: accepted
Back to the list of papers