Applications of operations research techniques for operational decisions in healthcare industry

Abstract

Bu tez çalışmasında sağlık endüstrisinde yaygın olarak görülen iki tip çizelgeleme problemi üzerinde durulmaktadır, hasta kabul çizelgeleme problemi ve hemşire çizelgeleme problemi. İlk problemde yatan hastalar medikal ihtiyaçlarına ve tercihlerine göre tedavi süresince yataklara atanırlar. Bu tezde bu problemin hem statik hem de dinamik versiyonları çalışılır. Hasta kabul zamanlarının bilindiği statik versiyon için karma tamsayılı programlama önerilir. Bu yöntemde, problem daha küçük problemler kümesine ayrıştırılarak tekrarlı bir şekilde çözülür. Acil hastaların, ameliyathane kısıtlarının ve hasta ertelemelerinin de incelendiği problemin dinamik versiyonu için de çok benzer bir ayrıştırma ve çözüm yaklaşımı tercih edilmiştir. Statik versiyonuna uygulanan yöntem bilinen sonuçlara yüzde on beşten az bir farkla çok daha hızlı hesaplama zamanlarında çizelgeler oluşturabilmektedir. Dinamik versiyon çözümü ise altı yeni en iyi sonuç elde etmektedir. Bu tez çalışmasında yer verilen diğer problem ise hemşirelerin belirli kısıtlara göre vardiyalara atandığı kompleks bir çizelgeleme problemi olan hemşire çizelgelemedir. Araştırmalarda bu problemin iki farklı versiyonu çalışılmıştır, standart ve genişletilmiş versiyonlar. Standart versiyon yaygın olarak bilinen vardiya ve hemşire ihtiyaç kısıtlarının değerlendirildiği temel versiyon iken, genişletişmiş versiyon hemşire yeteneklerini ve departman atamalarını da göz önünde bulundurur. Standart versiyonun çözümünde karma tamsayılı programlama ile ileri sezgisel yaklaşımlar melezlenmiştir. Genişletilmiş versiyon için ise matematik sezgisel bir yöntem önerilmiştir. Melez yöntem literatüre göre yedi tane, matematiksel sezgisel ise çözücülerin yetersiz kaldığı örneklerde altı tane en iyi bilinen sonuç elde etmektedir.

This thesis addresses two common scheduling problems that are encountered in the health care industry, the patient admission scheduling (PAS) problem and nurse rostering problem (NRP). The PAS automatically assigns elective patients to beds for the duration of their stays considering medical needs and preferences. Both static and dynamic versions are studied in this dissertation. For the static version where patient admissions are known in advance, a mixed integer programming (MIP) based heuristics are proposed. The problem is decomposed into a set of smaller problems and iteratively solved. A similar approach is also proposed for the dynamic version which several real life applications such as existence of the emergency patients, operating room constraints, and patient delays are additionally considered. The approach on the PAS generates schedules within fifteen percent gaps from best known solutions in faster times. The DPAS solution reports six new best-known solutions on test data. The last problem in the thesis, NRP, is a complex scheduling problem in which nurses must be assigned to shifts according to a set of constraints. Two variants of the problem are studied. While one of the versions deals with common constraints such as shift requests and cover needs, the other version extends the previous one with skills and departmental assignments. The standard version is solved via a hybrid of MIP-based heuristics and meta-heuristics approaches to provide powerful schedules. A mat-heuristic algorithm is proposed for the extended version. Computational experiments show that the hybrid algorithm obtains seven new best-known results and the mat-heuristic approach reports six new best-known solutions on instances when a stand-alone IP solver is not able to provide schedules.