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

Alexander Alekseevich Lazarev, Darya Vladimirovna Lemtyuzhnikova and Mikhail Lvovich Somov
Additional contact information
Alexander Alekseevich Lazarev: Institute of Control Sciences, 65 Profsoyuznaya Street, 117997 Moscow, Russia
Darya Vladimirovna Lemtyuzhnikova: Institute of Control Sciences, 65 Profsoyuznaya Street, 117997 Moscow, Russia
Mikhail Lvovich Somov: Institute of Control Sciences, 65 Profsoyuznaya Street, 117997 Moscow, Russia

Mathematics, 2022, vol. 10, issue 5, 1-18

Abstract: 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: health scheduling; approximation algorithms; decomposition; capacity increase; bin packing problem; scheduling problem (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/5/784/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/5/784/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:10:y:2022:i:5:p:784-:d:761580

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().