Hemşire nöbet çizelgeleme probleminin tavlama benzetimi algoritması ile çözümü
The solution of nurse scheduling problem with simulated annealing algorithm
Yazar: BİLGEN AYAN KOÇ
Danışman: PROF. DR. MEHMET AKTAN
Necmettin Erbakan Üniversitesi / Fen Bilimleri Enstitüsü / Endüstri Mühendisliği Ana Bilim Dalı
Derece: Yüksek Lisans, 2019
Konu: Endüstri ve Endüstri Mühendisliği = Industrial and Industrial Engineering
Dizin: Nöbet çizelgeleme = Duty scheduling

Özet:
Hemşire çizelgeleme problemi (HÇP), personel çizelgeleme problemleri içerisinde spesifik, daha zor ve insan sağlığıyla ilgili olması nedeniyle daha hassas ve önemli bir konudur. Bu çalışmada, haftanın her günü 24 saat kesintisiz hizmet veren bir hastanede 2 vardiya halinde (08:00-16:00 arası 8 saat ve 16:00-08:00 arası 16 saat) çalışan 15 hemşire için varsayılan kısıtlar çerçevesinde tavlama benzetimi algoritması kullanılarak en iyi çalışma çizelgesinin oluşturulması amaçlanmıştır. Araştırmada yöntem olarak, HÇP'nin çözümüne yönelik geliştirilen sezgisel yöntemlerden biri olan Tavlama Benzetimi Algoritması (TBA) kullanılmıştır. Verilerin analizinde kısıtların matematiksel formüllerle ifade edilebilmesini kolaylaştırmak, ana amaç ve alt amaç fonksiyonlarının değerlerinin doğru olarak hesaplandığından emin olmak için öncelikle Microsoft Office Excel programından faydalanılmıştır. Daha sonra oluşturulan ve doğruluğu test edilen matematiksel ifadelerin kodları Matlab programıyla eşdeğer olup kullanımı ücretsiz olan GNU Octave (2018) Version 4.4.1'in Windows-64 işletim sistemi için geliştirilen versiyonunda yazılmıştır. Araştırma kapsamında geliştirilen tavlama algoritması, genel tavlama algoritmasının temel mantığına sadık kalınarak ancak geliştirilerek yeniden yazılmıştır. Algoritma ile ele alınan problemin uyması beklenen 8'i zorunlu ve 8'i esnek olmak üzere 16 kısıtın tamamını sağlayarak en iyi çizelgeyi oluşturması sağlanabilmiştir. En iyi çözüme ulaşma süresi verilen problemde 0-8 izinli hemşire durumunda yani 7-15 çalışan hemşire durumunda ortalama 34 saniye (min.150-maks.1.338 deneme) olarak hesaplanmıştır. Algoritma, 9 izinli hemşire yani 6 çalışan hemşire durumu için de test edilmiş ve 195 saniyede (min.456-maks.4.864 deneme) tüm kısıtları sağlayan en iyi çözüme ulaşmıştır. Algoritma toplamda 200 kere test edilmiş, tamamında 0-9 izinli (6-15 çalışan) hemşire için 5.000 denemenin (500 saniyenin) altında çözüme ulaşmıştır. Araştırmada tavlama algoritması için yeni bir sıcaklık düşürme tekniği (logaritmik-üstel soğutma) ve yeni bir atama tekniği (belirli kritik değerlerin altında ve üstünde farklı atama tekniği kullanma) geliştirilmiş, bu iki tekniği içeren tavlama algoritmasına "çifte atamalı çoklu tavlama algoritması" adı verilmiştir.

Abstract:
Amongst the personnel scheduling problems, the nurse scheduling problem (HCP) is a more sensitive and important because it is specific, more difficult and related to human health. In this study, it is intended to create the best work schedule by using a simulated simulation algorithm for 15 nurses working in 2 shifts (the day shift as 8 hours between 08:00-16:00 and the night shift as 16 hours between 16:00-08:00) at a hospital operating 24 hours a day. In the study, the Simulated Annealing (SA) Algorithm, one of the heuristic methods developed for the solution of NSP, is is used as the method. In the analysis of the data, in order to make it easier to express the constraints with mathematical formulas, firstly, Microsoft Office Excel program was used to ensure that the values of the main and sub-objective functions were calculated correctly. The codes of the mathematical expressions, which are generated and tested for accuracy, are written in GNU Octave (2018) Version 4.4.1 which are free to use, developed for Windows-64 operating system and equivalent to the Matlab program. The annealing algorithm developed within the scope of the research has been rewritten in accordance with the basic logic of the general annealing algorithm but has been improved. The problem addressed by the algorithm which was expected to provide the best sheduling for the nurses by providing all 16 constraints (8 hard and 8 flexible) could be solved by the developed algorithm. The time to reach the best solution for 0-8 off (7-15 working) nurses in the given problem, on average, was calculated as 34 seconds (min.150-max.1,338 trials) in the case of 7-15 working nurses. The algorithm has also been tested for the case of 9 off (i.e. 6 working) nurses and the best solution in 195 seconds (min.456-max.4,864 iterations) providing all the constraints. The algorithm has been tested 200 times in total, reaching the best solution under the 5,000 trials (500 seconds) for the 0-9 off (i.e. 6-15 working) nurses in all tests. In the study, a new temperature reduction technique (logarithmic-exponential cooling) and a new assignment technique (using different assignment techniques above and below a certain critical values depending on the number of nurses off) were developed for the annealing algorithm. The new developed technique is called as "multiple simulated annealing with double assignment".