Hemşire vardiyalama problemine genetik algoritmaların uygulanması
Application of a genetic algorithm to a real world nurse rostering problem instance
Yazar: ÖZGÜR KELEMCİ
Danışman: YRD. DOÇ. DR. A. ŞİMA UYAR
İstanbul Teknik Üniversitesi / Bilişim Enstitüsü
Derece: Yüksek Lisans, 2007
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control
Dizin: Genetik algoritmalar = Genetic algorithms ; Yapay zeka = Artificial intelligence

Özet:
Hem şire Vardiyalama problemi, farklı özellikteki hem şirelere farklı  vardiya tiplerinin problemin içerdi ği bir çok katı ve gev şek kısıtın sa ğlanarak  atanmaya çalı şıldı ğı nöbet çizelgesi  hazırlama problemidir. Bu çalı şmada, Gerçek bir hem şire vardiyalama problemi  (Fatih Sultan Mehmet Hastanesi, İstanbul) genetik algoritmalar kullanılarak çözülür. Nöbet çizelgeleri elle yetkili ki şiler tarafından  hazırlanmaya çalı şılmaktadır. Bir çok kısıttan  dolayı  elle hazırlama i şlemi çok vakit harcamayı gerektirmektedir ve genelde tüm kısıtlar sa ğlanamamaktadır. Çalı şmanın amacı gerçek bir vardiyalama problemine otomatik  olarak üretilebilecek nöbet çizelgeleri hazırlamaktır. Bu çalı şma nöbet çizelgelerini genetik algoritmalar kullanarak çözüm bulma yolu ile ilgili çalı şmaların sonuçlarını içermektedir. De ğişken a ğırlık yöntemi gev şek kısıtların a ğırlı ğını üstel olarak artırmaktadır. Bu durumda gev şek kısıtlar daha hızlı  çözülmekte ve ceza puanlarının ku şaklar boyunca dü şmesine yol açmaktadır ancak bu durum katı kısıtları etkilemektedir. Göreceli olarak ba şarım puanında katı kısıtların a ğırlı ğının katkısı dü şmeye ba şlamaktadır. Bölümler arasında hem şire transferine yardımcı olması amacıyla bir yöntem  geli ştirildi ve uygulandı. Di ğer kısıtların ceza puanlarında herhangi bir de ğişikli ğe yol açmaksızın bazı kısıtların ceza puanlarını dü şürmede etkili bir yöntem oldu ğu ortaya çıktı. Onarma yönteminin ve ceza puanının normalizasyonun etkisi  bu çalı şmada ara ştırıldı. Farklı ilk toplum olu şturma yöntemleri incelendi. Sonuçlar bazı kısıtların di ğer kısıtlara göre çözülmesinin çok daha zor oldu ğu sonucuna ula şıldı. Katı kısıtlara uymayan aday çözümler geçersiz çözümler kabul edildi. Çıkan sonuçlardan ceza puanı normalizasyonu, onarma yöntemi, de ğişken a ğırlık kullanma iyi sonuçlar alınmasını sa ğlamaktadır.

Abstract:
The nurse rostering problem involves assigning shifts to qualified personel using timetable under some hard and soft constraint. In this study, the nurse rostering problem instance of the Fatih Sultan Mehmet Hospital is being attempted to be solved using  genetic algorithm. Currently, the rosters are neing prepared by a head nurse who performs this tedious tas by hand. Due to the existence of many constraints usually the resulting schedules are suboptinal. The aim is this study is to generate better schedules automatically for this specific real world instance of the nurse rostering problem. The adaptive weight method increases the weight of the soft constraints exponentially, so the penalty points of soft constraints decrease, but this affects hard constraints, because the relative effect of the weights of the hard constraints on the overall fitness also decreases.  The method is created to help transferring nurse between departments. This method decreases the penalty points of some constraint without increasing penalty points of other constraints. The effect of two constraint handling methods, a repair technique, normalization of fitness values and parameters settings for these are explored in this study. Different initial population methods are explored in this study. Different initialization methods are used to solve problematic constraints. A solution candidate is infeasible and unacceptable  if it violates any one of the hard constraints. From the methods tested, it is seen that normalization of the penalty scores, repairing of constraint violations and using adaptive weights for the constraints are all useful to obtain good results.