Agatha, Sisca Threecya (2020) Optimasi Nurse Rostering Problem (NRP) Menggunakan Algoritma Tabu-Simulated Annealing Based Hyper-Heuristics dengan Benchmark Dataset Norwegian Hospitals. Other thesis, Institut Teknologi Sepuluh Nopember.
Preview |
Text
05211640000037-Undergraduate_Thesis.pdf Download (1MB) | Preview |
Abstract
Nurse Rostering atau penjadwalan perawat merupakan permasalahan penjadwalan yang kompleks, karena biasanya rumah sakit memiliki permintaan terkait personil yang bervariasi dari waktu ke waktu. Proses penjadwalan perawat membutuhkan ketelitian tinggi karena harus memperhatikan berbagai batasan, baik hard constraint maupun soft constraint. Berdasarkan optimasi kombinatorik permasalahan penjadwalan perawat merupakan NP-Hard yang artinya belum ada algoritma secara eksak yang mampu menyelesaikan permasalahan karena banyaknya kombinasi kemungkinan yang terbentuk, sehingga muncul algoritma approximate untuk mengatasi permasalahan. Tugas akhir ini membahas penjadwalan perawat secara otomatis untuk mengurangi nilai penalti akibat adanya pelanggaran soft constraint. Optimasi penjadwalan perawat menggunakan benchmark dataset Norwegian Hospitals. Algoritma yang akan digunakan yaitu Tabu Search dan Simulated Annealing berbasis Hyper-Heuristics. Tabu Search akan melakukan seleksi low-level heuristics. Low level heuristics yang tidak menghasilkan solusi lebih baik akan disimpan di Tabu List agar tidak digunakan pada iterasi selanjutnya. Sedangkan Simulated Annealing akan menentukan acceptance criteria dari solusi serta melakukan proses evaluasi terhadap solusi tersebut. Pencarian solusi baru akan diterima sebagai solusi sementara jika solusi tersebut memiliki hasil yang lebih optimal dibandingkan solusi awal. Kedua algoritma yang digabungkan mampu melakukan diversifikasi sehingga menghindari adanya local optima. Hasil dari tugas akhir ini yaitu algoritma Tabu-Simulated Annealing berhasil membentuk solusi feasible untuk 3 instance dan menghasilkan luaran berupa jadwal kerja perawat dari dataset Norwegian Hospitals. Algoritma Tabu-Simulated Annealing juga mampu menurunkan nilai penalti hingga 80% dari penalti awal dan memberikan performa yang lebih baik jika dibandingkan dengan algoritma algoritma Hill Climbing, algoritma Tabu Search, dan algoritma Simulated Annealing.
=========================================================
Nurse Rostering is a complex scheduling problem because hospitals usually have personnel-related requests that vary from time to time. Nurse scheduling process requires high accuracy because they have to pay attention to various constraints, both hard and soft constraints. Based on combinatoric optimization the nurse scheduling problem is NP-Hard which means there is no exact algorithm that is able to solve the problem because of the many possible combinations that are formed, so the approximate algorithm appears to overcome the problem. This final project discusses the scheduling of nurses automatically to reduce the penalty value due to soft constraint violations. Nurse scheduling optimization uses the Norwegian Hospitals benchmark dataset. The algorithm that will be used is Taboo and Simulated Annealing based on Hyper-Heuristics. Taboo Search will select the low-level heuristics. Low-level heuristics that do not produce better solutions will be stored in the Taboo List so that they are not used in the next iteration. While Simulated Annealing will determine the acceptance criteria of the solution and evaluate the solution. The search for new solutions will be accepted as a temporary solution if the solution has more optimal results than the initial solution. The two algorithms combined are able to diversify so as to avoid local optima. The result of this final project is the Taboo Simulated Annealing algorithm that successfully formed a feasible solution for 3 instances and produced an output in the form of a nurse work schedule from the Norwegian Hospitals dataset. The Taboo-Simulated Annealing algorithm is also able to reduce the penalty value by up to 80% from the initial penalty and provide better performance when compared to the Hill Climbing algorithm, the Taboo Search algorithm, and the Simulated Annealing algorithm.
| Item Type: | Thesis (Other) |
|---|---|
| Uncontrolled Keywords: | Nurse Rostering, Optimasi, Tabu Search, Simulated Annealing, Hyper-Heuristics, Nurse Rostering, Optimization, Taboo Search, Simulated Annealing, Hyper-Heuristics |
| Subjects: | T Technology > T Technology (General) > T57.84 Heuristic algorithms. |
| Divisions: | Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Information System > 57201-(S1) Undergraduate Thesis |
| Depositing User: | Sisca Threecya Agatha |
| Date Deposited: | 14 Aug 2020 08:57 |
| Last Modified: | 20 Jun 2023 14:10 |
| URI: | http://repository.its.ac.id/id/eprint/78220 |
Actions (login required)
 |
View Item |