Decomposition of the Knapsack Problem for Increasing the Capacity of Operating Rooms

Mathematics. 2022. Vol. 10. No. 5. P. 1–18.

Lazarev A. A., Lemtyuzhnikova D. V., Somov M. L.

This paper is aimed at the problem of scheduling surgeries in operating rooms. To solve this problem, we suggest using some variation of the bin packing problem. The model is based on the actual operation of 10 operating rooms, each of which belongs to a specific department of the hospital. Departments are unevenly loaded, so operations can be moved to operating rooms in other departments. The main goal is to increase patient throughput. It is also necessary to measure how many operations take place in other departments with the proposed solution. The preferred solution is a solution with fewer such operations, all other things being equal. Due to the fact that the mixed-integer linear programming model turned out to be computationally complex, two approximation algorithms were also proposed. They are based on decomposition. The complexity of the proposed algorithms is estimated, and arguments are made regarding their accuracy from a theoretical point of view. To assess the practical accuracy of the algorithms, the Gurobi solver is used. Experiments were conducted on real historical data on surgeries obtained from the Burdenko Neurosurgical Center. Two decomposition algorithms were constructed and a comparative analysis was performed for 10 operating rooms based on real data.

Keywords: approximation algorithms, decomposition, scheduling problem, Bin packing problem, capacity increase, health scheduling

Publication based on the results of: Theoretical and Applied Problems of Data Analysis and Decision Making in the Socio-Economic and Financial Spheres (2022)