Implementasi Harmony Search untuk Penjadwalan Perawat

Implementasi Harmony Search untuk Penjadwalan Perawat Mohammad Arif Rasyidi#1, Mahendrawathi Erawan#2 #

Jurusan Sistem Informasi, Institut Teknologi Sepuluh Nopember Kampus ITS Sukolilo Surabaya, Indonesia 1

[email protected] [email protected]

2

Abstrak— Algoritma metaheuristik Harmony Search (HS) diterapkan untuk menyelesaikan permasalahan penjadwalan perawat (Nurse Scheduling Problem/NSP). Implementasi algoritma ini pertama kali dilakukan dengan cara menyesuaikan model NSP sehingga dapat diselesaikan dengan HS. Penyesuaian tersebut melibatkan modifikasi model dengan memasukkan komponen fungsi penalti dan fungsi perbaikan dengan mempertimbangkan jalannya algoritma HS tanpa mengubah inti dari NSP. Dari analisis yang telah dilakukan didapatkan bahwa parameter yang menghasilkan nilai fitness terbaik dari hasil uji coba adalah HMS = 5, HMCR = 0.99, dan PAR = 0.01. Dibandingkan dengan tiga metode lainnya, yaitu Electromagnetism Meta-heuristic (EM), Scatter Search Algorithm (SS), dan Genetic Algorithm (GA), HS memberikan solusi terbaik pada kasus 9, N30 NSPLib dengan rata-rata nilai fitness sebesar 1857.48 dan feasibilitas sebesar 92.29%. Kata Kunci— penjadwalan perawat, Nurse Scheduling Problem, NSP, Harmony Search, HS, metaheuristik

I. PENDAHULUAN Permasalahan penjadwalan perawat atau Nurse Scheduling Problem (NSP) melibatkan pembuatan jadwal individual untuk perawat yang terdiri atas hari kerja dan hari libur dalam periode perencanaan yang terdiri atas beberapa minggu. Penjadwalan perawat dilakukan dengan mempertimbangkan dua jenis batasan, yaitu hard dan soft constraint. Hard constraint merupakan batasan yang harus dipenuhi sehingga solusi dari penjadwalan menjadi layak atau mungkin untuk digunakan. Sedangkan soft constraint merupakan jenis batasan yang tidak harus dipenuhi dan dapat dilanggar. Kualitas dari solusi dioptimalkan dengan memenuhi soft constraint. Beberapa fungsi tujuan yang umum digunakan untuk NSP antara lain:  meminimalkan jumlah pelanggaran batasan  meminimalkan jumlah perawat  meminimalkan overtime  memaksimalkan pemenuhan kebutuhan perawat  memaksimalkan pemenuhan permintaan/harapan perawat Permasalahan ini telah menarik banyak peneliti untuk menghasilkan prosedur eksak maupun (meta)heuristik bagi permasalahan tersebut [1]. Tsai dan Li misalnya mengembangkan model matematis dua tingkat dan

menerapkan algoritma genetika untuk menyelesaikan permasalahan NSP [2]. Akan tetapi, model yang dikembangkan oleh Tsai & Li belum mempertimbangkan prioritas preferensi dari perawat. Menhout dan Vanhoucke menggunakan tiga buah metode untuk menyelesaikan NSP, yaitu Electromagnetism Meta-heuristic (EM) [3], Scatter Search Algorithm (SS) [4], dan Genetic Algorithm (GA) [5]. Permasalahan penjadwalan perawat merupakan permasalahan optimasi kombinatorial kompleks yang dikategorikan sebagai NP-hard [6]. Kompleksitas dari permasalahan ini disebabkan oleh banyaknya jumlah variabel yang terlibat di dalamnya, antara lain jumlah perawat, jumlah shift, batasan-batasan yang ada, serta parameter-parameter yang terlibat dalam fungsi tujuan. Dengan kompleksnya permasalahan ini, maka metode eksak akan memakan waktu yang cukup lama untuk mendapatkan solusi yang optimal. Oleh karena itu peneliti mulai beralih untuk menggunakan metode evolusioner atau metaheuristik yang tidak bertujuan mendapatkan solusi yang optimal namun untuk mendapatkan solusi yang baik dalam jangka waktu yang dapat diterima. Salah satu teknik metaheuristik terbaru adalah Harmony Search (HS) yang dikembangkan pertama kali oleh Geem et al. [7]. Algoritma HS dikembangkan dengan analogi terhadap proses improvisasi musik dimana musisi dalam grup berusaha terus menerus untuk memperbaiki nadanya untuk mendapatkan harmoni yang lebih baik. Algoritma HS telah banyak diterapkan pada berbagai macam permasalahan optimasi kombinatorial seperti optimasi di bidang irigasi, Routing di 4th Party Logistics [8], dan Vehicle Routing Problem (VRP) [9]. Algoritma HS juga telah digunakan dan memberikan kinerja yang cukup memuaskan dalam permasalahan sejenis NSP, yaitu penjadwalan mata kuliah di universitas atau yang dikenal dengan University Course Timetabling Problem (UCTP) [10]. Dengan demikian, algoritma HS memberikan kemungkinan sukses yang cukup besar dalam permasalahan optimasi kombinatorial termasuk NSP. II. HAMONY SEARCH UNTUK NSP Isu yang berkaitan dengan NSP adalah banyaknya variasi permasalahan. Batasan dan fungsi tujuan NSP bergantung pada kebutuhan dan kebijakan masing-masing rumah sakit. Hal ini menimbulkan banyaknya variasi permasalahan pada NSP. Pada paper ini, tujuan dari NSP yang diambil adalah memaksimalkan pemenuhan preferensi/harapan dari perawat

1

atau dengan kata lain meminimalkan preference cost dari perawat. Dengan demikian, NSP dapat diformulasikan sebagai berikut: 𝑚𝑒𝑚𝑖𝑛𝑖𝑚𝑎𝑙𝑘𝑎𝑛 𝑃 𝑥 =

𝑛 𝑖=1

𝑑 𝑗 =1

𝑠 𝑘=1 𝑥𝑖𝑗𝑘

∗ 𝑝𝑖𝑗𝑘

(1)

Dengan pijk = preference cost untuk perawat i, bekerja pada hari j dengan shift kerja k, dan 1: jika perawat 𝑖 ditugaskan bekerja pada shift kerja 𝑘, hari 𝑗 𝑥𝑖𝑗𝑘 = 0: sebaliknya Batasan-batasan yang harus dipenuhi dalam penjadwalan perawat ini antara lain adalah 1. Batasan kebutuhan perawat (coverage constraint) 2. Batasan penugasan minimal bagi masing-masing perawat selama periode penjadwalan 3. Batasan penugasan maksimal bagi masing-masing perawat selama periode penjadwalan 4. Batasan maksimal hari kerja berturut-turut (consecutive working days) 5. Untuk jumlah shift kerja lebih dari atau sama dengan empat (termasuk shift libur), perawat tidak boleh ditugaskan untuk bekerja berturut-turut pada shift larut malam diikuti dengan shift pagi. Solusi penjadwalan akan dianggap feasible (memungkinkan) apabila memenuhi batasan 1 hingga 5. Batasan tersebut dapat dituliskan sebagai berikut. 𝑠 𝑖 = 1. . 𝑛, 𝑗 = 1. . 𝑑 𝑘=1 𝑥𝑖𝑗𝑘 = 1, 𝑛 𝑗 = 1. . 𝑑, 𝑘 = 1. . 𝑠 𝑖=1 𝑥𝑖𝑗𝑘 ≥ 𝐶𝑗𝑘 , 𝑑 𝑠−1 𝑥 ≥ 𝑚𝑖𝑛 𝑎𝑠𝑔 , 𝑖 = 1. . 𝑛 𝑗 =1 𝑘 =1 𝑖𝑗𝑘 𝑑 𝑠−1 𝑗 =1 𝑘 =1 𝑥𝑖𝑗𝑘 ≤ 𝑚𝑎𝑥𝑎𝑠𝑔 , 𝑖 = 1. . 𝑛 𝑗 𝑖 = 1. . 𝑛, 𝑗 𝑝=𝑗 +1−𝑚𝑎𝑥 𝑐𝑜𝑛𝑠 𝑥𝑖𝑝𝑠 ≥ 1,

𝑥𝑖 𝑗 −1 (𝑠−1) + 𝑥𝑖𝑗 (1) < 2, 𝑥𝑖𝑗𝑘 ∈ 0,1

= 𝑚𝑎𝑥𝑐𝑜𝑛𝑠 . . 𝑑 𝑖 = 1. . 𝑛, 𝑗 = 2. . 𝑑

(2) (3) (4) (5) (6) (7) (8)

Persamaan (2) menjamin bahwa setiap perawat hanya mendapatkan satu shift kerja setiap harinya. Persamaan (3) menjamin coverage constraint, yaitu kebutuhan perawat untuk setiap shift kerja benar-benar dipenuhi. Persamaan (4) dan (5) menjamin bahwa setiap perawat benar-benar mendapatkan jadwal kerja antara jumlah penugasan minimal dan maksimal selama periode penjadwalan. Persamaan (6) merupakan batasan maksimal hari kerja berturut-turut (consecutive working days). Persamaan (7) berlaku apabila banyaknya jenis shift kerja pada NSP lebih dari atau sama dengan empat (termasuk shift libur). Persamaan (7) ini menjamin bahwa perawat tidak ditugaskan bekerja pada shift pagi jika pada hari sebelumnya ia bekerja pada shift larut malam. Sedangkan persamaan (8) menjamin nilai dari variabel keputusan x bertipe binary. A. Formulasi NSP untuk HS Untuk menyelesaikan model NSP yang telah dikembangkan di atas dengan menggunakan algoritma HS,

perlu dilakukan penyesuaian terhadap variabel keputusan yang ada. Penyesuaian ini dilakukan untuk mempermudah jalanya proses-proses dalam HS, yaitu memory consideration, pitch adjustment, dan random selection. Untuk mempermudah proses tersebut, maka dibuat variabel baru yaitu vektor y yang terdiri atas elemen-elemen yij untuk merepresentasikan variabel keputusan sebelumnya, yaitu xijk dalam bentuk lain. Variabel keputusan baru tersebut dapat didefinisikan sebagai berikut. 𝑦𝑖𝑗 = 𝑘 jika 𝑥𝑖𝑗𝑘 = 1, 𝑖 = 1. . 𝑛, 𝑗 = 1. . 𝑑, 𝑘 = 1. . 𝑠 (9) atau dengan kata lain 1 ∶ jika 𝑦𝑖𝑗 = 𝑘 𝑖 = 1. . 𝑛, 𝑗 = 1. . 𝑑, 𝑘 = 1. . 𝑠 (10) 𝑥𝑖𝑗𝑘 = 0 ∶ sebaliknya Setiap elemen dalam yij dari vektor y direpresentasikan sebagai suatu nilai bulat (integer) yang bernilai antara 1 hingga s (banyak shift). Dengan demikian, NSP untuk HS dapat diformulasikan sebagai berikut. 𝑚𝑒𝑚𝑖𝑛𝑖𝑚𝑎𝑙𝑘𝑎𝑛 𝑃 𝑦 = 𝑛𝑖=1 𝑑𝑗=1 𝑝𝑖𝑗 (𝑦 𝑖𝑗 ) Dengan batasan 1 ≤ 𝑦𝑖𝑗 ≤ 𝑠, 𝑖 = 1. . 𝑛, 𝑗 = 1. . 𝑑, 𝑠 = |𝑆|

(11) (12)

Formulasi problem NSP untuk HS ini menghiraukan batasan-batasan sebelumnya yaitu batasan kebutuhan perawat (coverage constraint), batasan jumlah minimal dan maksimal hari kerja, batasan maksimal hari kerja berturut-turut, dan batasan shift kerja larut malam yang diikuti oleh shift kerja pagi. Dengan demikian, semua solusi yang dievaluasi ada proses pencarian akan memiliki kemungkinan yang tinggi untuk melanggar batasan-batasan tersebut, sehingga akan menjadi sangat sulit untuk menemukan solusi yang mungkin (feasible). Pada subbab selanjutnya akan dijelaskan pendekatan HS untuk formulasi NSP ini dan pendekatan spesifik yang dilakukan untuk menghindari pembuatan solusi yang infeasible (melanggar batasan-batasan yang ada). B. Algoritma HS-NSP Prosedur HS untuk NSP dimulai dengan penentuan fungsi objektif yang telah diformulasikan sebelumnya. Selanjutnya dilakukan inisialisasi parameter dari HS, yaitu Harmony Memory Considering Rate (HMCR), Pitch Adjusting Rate (PAR), Harmony Memory Size (HMS), dan jumlah iterasi (Number of Iterations, NI) atau stopping criterion. Langkah selanjutnya yaitu membuat harmony memory. Harmony Memory (HM) merupakan vektor solusi sebesar HMS. Untuk mengisi HM, dibuatlah harmoni (solusi) acak sebanyak HMS. Untuk membuat solusi acak ini, dilakukan prosedur khusus dengan mempertimbangkan hard constraints yang telah disebutkan sebelumnya, yaitu batasan kebutuhan perawat (coverage constraint), batasan jumlah minimal dan maksimal hari kerja, batasan maksimal hari kerja berturutturut, dan batasan shift kerja larut malam yang diikuti oleh shift kerja pagi. Langkah ini secara khusus akan dibahas dalam bagian selanjutnya. Harmoni-harmoni yang ada dalam harmony memory selanjutnya dihitung nilai objektifnya berdasarkan

2

berdasarkan fungsi objektif yang telah ditentukan sebelumnya dan kemudian diurutkan. Tahapan selanjutnya yaitu pembuatan harmoni (solusi) baru. Harmoni baru ini dibuat dengan menggunakan tiga proses, yaitu memory consideration, pitch adjustment, dan random selection. Untuk masing-masing variabel penyusun vektor harmoni, memory consideration akan dilakukan dengan peluang sebesar HMCR, sedangkan random selection akan dilakukan dengan peluang sebesar (1-HMCR). Apabila memory consideration telah dilakukan pada suatu variabel penyusun vektor harmoni, maka peluang dilakukannya pitch adjustment pada variabel tersebut adalah sebesar PAR. C. Pembuatan Harmony Memory pada HS-NSP Pada HS-NSP harmony memory dihasilkan dengan membuat harmoni (solusi) acak sebanyak HMS. Proses pembuatan harmoni acak ini harus mempertimbangkan hard constraint yang ada sehingga harmoni yang dihasilkan menjadi feasible. Proses pembuatan harmoni acak pada HS-NSP dapat ditunjukkan pada pseudocode berikut. PSEUDOCODE I PEMBUATAN HARMONI ACAK PADA HS-NSP Pembuatan Harmoni Acak pada HS-NSP begin // pembuatan jadwal libur do untuk masing-masing perawat, buat jadwal libur acak dengan jumlah libur antara (d-maxasg) dan (d-minasg) untuk masing-masing hari, cek apakah jumlah perawat yang bekerja >= total kebutuhan perawat pada masing-masing-shift jika kurang, perbaiki waktu libur perawat untuk masing-masing perawat, cek pelanggaran pada jumlah maksimal hari kerja berturut-turut jika terdapat pelanggaran, perbaiki waktu libur while (jumlah perawat yang bekerja di masingmasing hari < total kebutuhan perawat pada masing-masing-shift atau terdapat pelanggaran pada jumlah maksimal hari kerja berturut-turut) dan jumlah perbaikan maksimal belum tercapai // end of pembuatan jadwal libur // pembuatan jadwal kerja untuk masing-masing hari, alokasikan shift pagi sebanyak total kebutuhan perawat pada shift pagi secara acak pada perawat yang pada hari sebelumnya tidak bekerja larut malam. untuk masing-masing shift kerja selain pagi, alokasikan shift sebanyak kebutuhannya secara acak ke perawat yang belum dijadwalkan untuk perawat yang belum dijadwalkan, if (hari sebelumnya ia bekerja shift larut malam) berikan shift kerja acak kecuali

shift pagi dan libur else berikan shift kerja secara acak kecuali shift libur end if // end of pembuatan jadwal kerja end

Pembuatan harmoni baru secara acak ini terbagi menjadi dua proses utama, yaitu pembuatan jadwal libur dan pembuatan jadwal kerja. Jadwal libur dibuat dengan membuat jadwal libur masing-masing perawat secara acak. Untuk masing-masing perawat diberikan jatah libur antara (d-maxasg) dan (d-minasg). Hal ini dilakukan untuk menjamin batasan jumlah minimal dan maksimal hari kerja. Selanjutnya, untuk masing-masing hari, dicek apakah jumlah perawat yang bekerja lebih dari atau sama dengan total kebutuhan perawat pada masing-masing shift. Jika kurang maka dilakukan perbaikan pada jadwal libur ini. Perbaikan ini dimaksudkan untuk menangani batasan kebutuhan perawat pada masing-masing harinya (coverage constraint). Setelah itu dilakukan pengecekan apakah jadwal libur tersebut telah memenuhi batasan jumlah maksimal hari kerja berturut-turut (maximum consecutive working days). Jika masih terdapat pelanggaran, maka jadwal diperbaiki. Perbaikan terhadap jadwal libur ini akan dilakukan selama masih ada pelanggaran terhadap salah satu dari coverage constraint maupun batasan maximum consecutive working days atau dan jumlah perbaikan maksimal belum tercapai. Hal ini disebabkan karena perbaikan pada coverage constraint akan mempengaruhi hari kerja berturut-turut dari masingmasing perawat dan demikian pula sebaliknya. Jumlah perbaikan maksimal ditetapkan agar dalam model yang infeasible (tidak dapat diselesaikan) algoritma ini tidak terjebak dalam perulangan tak terhingga (endless-loop). Detail lebih lanjut mengenai proses perbaikan jadwal libur ini akan dijelaskan pada bagian selanjutnya. Setelah jadwal libur dihasilkan, maka dilakukan penjadwalan hari kerja pada perawat yang tidak libur. Penjadwalan hari kerja pertama kali dilakukan dengan mengalokasikan perawat yang bertugas di pagi hari sebanyak total kebutuhan shift pagi pada hari tersebut. Alokasi shift pagi dilakukan dengan mempertimbangkan jadwal perawat tersebut pada hari sebelumnya. Jika pada hari sebelumnya ia bekerja pada shift larut malam, maka ia tidak boleh bekerja pada shift bagi di hari tersebut (batasan shift kerja larut malam tidak boleh diikuti shift pagi). Lalu untuk masing-masing shift kerja lainnya diberikan kepada perawat yang belum dijadwalkan sebanyak kebutuhan dari masing-masing shift tersebut. Ini akan menjamin kebutuhan perawat dari masingmasing shift tersebut terpenuhi (coverage constraint). Langkah terakhir, bagi perawat yang belum dijadwalkan akan diberikan shift kerja acak dengan pertimbangan jika pada hari sebelumnya ia bekerja pada shift larut malam, maka ia tidak boleh mendapatkan jadwal kerja pada shift pagi. D. Pembuatan Harmoni Baru pada HS-NSP Harmoni baru pada HS-NSP dibuat dengan tiga prosedur, yaitu memory consideration, pitch adjustment, dan random

3

selection. Sama dengan pembuatan harmoni acak pada harmony memory, pembuatan harmoni baru pada HS-NSP ini juga terdiri atas dua proses utama, yaitu pembuatan jadwal libur dan pembuatan jadwal kerja. Proses pembuatan harmoni baru pada HS-NSP dapat ditunjukkan pada pseudocode berikut. PSEUDOCODE II PEMBUATAN HARMONI BARU PADA HS-NSP Pembuatan Harmoni Baru pada HS-NSP begin // pembuatan jadwal libur do untuk masing-masing perawat, if (rand= total kebutuhan perawat pada masing-masing-shift jika kurang, perbaiki waktu libur perawat untuk masing-masing perawat, cek pelanggaran pada jumlah maksimal hari kerja berturut-turut jika terdapat pelanggaran, perbaiki waktu libur while (jumlah perawat yang bekerja di masingmasing hari < total kebutuhan perawat pada masing-masing-shift atau jumlah terdapat pelanggaran pada jumlah maksimal hari kerja berturut-turut) dan jumlah perbaikan maksimal belum tercapai // end of pembuatan jadwal libur // pembuatan jadwal kerja untuk masing-masing hari dan perawat yang dijadwalkan bekerja, if (rand
end if cek dan perbaiki coverage requirement dari masing-masing shift cek dan perbaiki jadwal perawat yang bekerja pada shift larut malam yang diikuti shift pagi // end of pembuatan jadwal kerja end

Pembuatan jadwal libur dilakukan dengan mempertimbangkan jadwal libur perawat tersebut sebelumnya (memory consideration) dengan peluang sebesar HMCR. Memory consideration dilakukan dengan memilih salah satu jadwal libur perawat tersebut pada harmony memory untuk keseluruhan periode penjadwalan. Jika jadwal libur telah didapatkan, maka ditentukan apakah masing-masing komponen hari libur pada jadwal tersebut perlu disesuaikan dengan menggunakan pitch adjustment. Peluang dilakukannya pitch adjustment pada masing-masing komponen libur pada jadwal perawat adalah sebesar PAR. Pitch adjustment ini dilakukan dengan memindahkan hari libur tersebut ke satu hari sebelum atau sesudahnya jika memungkinkan. Random selection dilakukan dengan peluang sebesar (1HMCR). Dengan kata lain, random selection ini dilakukan jika pembuatan jadwal tidak mempertimbangkan jadwal perawat tersebut sebelumnya. Sama seperti proses pembuatan harmoni acak, jadwal libur dibuat dengan membuat jadwal libur masing-masing perawat secara acak. Untuk masingmasing perawat diberikan jatah libur antara (d-maxasg) dan (dminasg). Hal ini dilakukan untuk menjamin batasan jumlah minimal dan maksimal hari kerja. Proses selanjutnya sama seperti pembuatan harmoni acak untuk mengisi harmony memory, jadwal dievaluasi dan diperbaiki sehingga sebisa mungkin memenuhi batasan kebutuhan perawat dan jumlah maksimal hari kerja berturutturut. Proses pembuatan jadwal kerja bagi perawat yang dijadwalkan bekerja juga terdiri atas memory consideration, pitch adjustment, dan random selection. Pada masing-masing hari, untuk setiap perawat yang dijadwalkan bekerja akan dilakukan memory consideration dengan peluang sebesar HMCR. Memory consideration dilakukan dengan memilih salah satu jadwal kerja perawat tersebut pada hari yang sama di harmony memory. Namun, jika pada harmony memory perawat tersebut belum pernah mendapatkan jadwal kerja pada hari tersebut (pada semua jadwal yang ada di harmony memory pada hari tersebut perawat itu selalu dijadwalkan libur), maka dilakukan random selection. Jika telah didapatkan jadwal kerja, maka perlu ditentukan apakah pitch adjustment perlu dilakukan. Pitch adjustment dilakukan dengan peluang sebesar PAR. Proses ini dilakukan dengan memindahkan shift kerja tersebut ke shift kerja terdekat. Proses pitch adjustment dapat dituliskan pada persamaan (22). (𝑦𝑖𝑗 ) 𝑚𝑜𝑑 (𝑠 − 1) + 1, 𝑟𝑎𝑛𝑑 < 0.5 𝑦𝑖𝑗 = (13) 𝑦𝑖𝑗 + 𝑠 − 3 𝑚𝑜𝑑 𝑠 − 1 + 1, 𝑟𝑎𝑛𝑑 ≥ 0.5 Random selection dilakukan dengan peluang sebesar (1HMCR). Proses ini dilakukan jika penentuan shift kerja tidak

4

mempertimbangkan harmoni sebelumnya. Random selection pada penjadwalan shift kerja ini dilakukan dengan memilih shift kerja secara acak dari semua kemungkinan yang ada. Proses terakhir dari pembuatan jadwal kerja ini yaitu perbaikan atas batasan-batasan yang ada. Karena pemberian shift dilakukan dengan pertimbangan atas tiga proses yaitu memory consideration, pitch adjustment, dan random selection, maka pelanggaran atas batasan sangat mungkin terjadi. Pada langkah ini, dilakukan perbaikan atas batasan kebutuhan perawat pada masing-masing shift dan batasan perawat yang bekerja pada shift larut malam tidak boleh diikuti shift pagi. E. Repair Functions pada HS-NSP Ada dua cara yang dilakukan untuk menangani solusi yang infeasible, yaitu dengan menggunakan penalty functions dan repair functions (Beasley & Chu, 1996). Repair functions mencoba untuk mengubah solusi yang infeasible menjadi solusi yang feasible. Pada NSP-HS, ada dua buah repair functions yang digunakan, yaitu repair function untuk memperbaiki jadwal libur dan repair function untuk memperbaiki jadwal kerja. Repair function untuk memperbaiki jadwal libur digunakan untuk memperbaiki jumlah libur pada masing-masing hari sehingga kebutuhan perawat pada masing-masing shift kerja dapat dipenuhi (coverage requirements). Repair function ini juga digunakan untuk memperbaiki pelanggaran terhadap batasan jumlah maksimal hari kerja berturut-turut. Repair function yang kedua digunakan untuk memperbaiki jadwal kerja. Repair function ini digunakan untuk memperbaiki jadwal perawat tiap harinya pada masing-masing shift sehingga memenuhi kebutuhan minimalnya (coverage requirements). Repair function ini juga digunakan untuk memperbaiki pelanggaran terhadap shift kerja larut malam yang diikuti dengan shift kerja pagi. 1) Repair Functions untuk Memperbaiki Jadwal Libur: Repair function untuk memperbaiki jadwal libur terdiri dari dua proses yaitu perbaikan jumlah perawat yang libur setiap harinya dan perbaikan pelanggaran terhadap batasan jumlah maksimal hari kerja berturut-turut. Perbaikan jumlah perawat yang libur setiap harinya dilakukan dengan menghitung jumlah perawat yang libur pada masing-masing harinya. Misalkan vj = jumlah perawat yang libur pada hari j (𝑣𝑗 = 𝑛𝑖=1 𝑥𝑖𝑗𝑠 , 𝑠 = |𝑆|) mj = jumlah perawat dengan jadwal libur yang jadwal liburnya perlu dipindahkan dari hari j 𝑖𝑓 (𝑣𝑗 > 𝑛 −

𝑠−1

𝑘 =1

𝐶𝑗𝑘 )

𝑚𝑗 = 𝑟𝑎𝑛𝑑𝐵𝑒𝑡𝑤𝑒𝑒𝑛 𝑣𝑗 − 𝑛 +

𝑠−1 𝑘=1 𝐶𝑗𝑘

, 𝑣𝑗

(14)

Untuk masing-masing hari j = 1..d, jika jumlah perawat yang libur pada hari j lebih banyak daripada selisih jumlah perawat yang ada dengan total kebutuhan perawat pada semua shift kerja pada hari j ( 𝑣𝑗 > 𝑛 − 𝑠−1 𝑘=1 𝐶𝑗𝑘 ) , maka ada

beberapa perawat yang perlu dipindahkan sehingga perawat yang bekerja pada hari tersebut cukup untuk dialokasikan pada shift kerja yang ada. Variabel mj merupakan jumlah perawat yang jadwal liburnya perlu dipindahkan dari hari j ke hari lain. Variabel mj dihasilkan secara acak dan bernilai antara (𝑣𝑗 − 𝑛 + 𝑠−1 𝑘=1 𝐶𝑗𝑘 ) dan 𝑣𝑗 . Selanjutnya dipilih perawat dengan jadwal libur pada hari j secara acak sebanyak mj. Untuk masing-masing perawat, cari lokasi baru, yaitu hari dimana (𝑛 − 𝑠−1 𝑘=1 𝐶𝑗𝑘 − 𝑣𝑗 ) maksimal. Selanjutnya jadwal libur perawat tersebut dipindahkan ke lokasi baru yang dipilih. Setelah dilakukan perbaikan jumlah libur perawat setiap harinya, dilakukan perbaikan untuk mengatasi pelanggaran terhadap batasan jumlah maksimal hari kerja berturut-turut. Untuk setiap perawat, setiap harinya dihitung telah berapa hari ia dijadwalkan bekerja berturut-turut setelah hari libur sebelumnya. Jika ia sudah bekerja berturut-turut sebanyak maxcons, maka perlu dilakukan perbaikan. Misalkan Vi = himpunan hari libur perawat i selama periode penjadwalan 𝑓𝑖𝑛𝑑 𝑙𝑧 ∈ 𝑉𝑖 𝑠𝑢𝑐𝑕 𝑡𝑕𝑎𝑡 𝑙𝑧+1 − 𝑙𝑧−1 𝑚𝑖𝑛𝑖𝑚𝑢𝑚 (15) Perbaikan yang dilakukan yaitu mencari tiga shift libur yang berurutan dengan jarak libur pertama ke libur ketiga minimal ( 𝑙𝑧+1 − 𝑙𝑧−1 ). Selanjutnya perawat tersebut dijadwalkan libur pada hari dimana ia telah bekerja berturutturut sebanyak maxcons dan pada libur kedua dari tiga hari libur berurutan yang ditemukan sebelumnya (𝑙𝑧 ) dihapuskan. 2) Repair Functions untuk Memperbaiki Jadwal Kerja: Repair function untuk memperbaiki jadwal kerja ini dilakukan dengan dua proses utama, yaitu memperbaiki jadwal perawat tiap harinya pada masing-masing shift sehingga memenuhi kebutuhan minimalnya, dan memperbaiki pelanggaran terhadap shift kerja larut malam yang diikuti dengan shift kerja pagi. Untuk memperbaiki jadwal perawat setiap harinya sehingga kebutuhan minimal masing-masing shift terpenuhi maka pada masing-masing hari dihitung jumlah perawat yang bekerja pada shift k pada hari j ( 𝑛𝑖=1 𝑥𝑖𝑗𝑘 ). Jika ( 𝑛𝑖=1 𝑥𝑖𝑗𝑘 < 𝐶𝑗𝑘 ), berarti perawat yang bekerja pada shift tersebut masih kurang dari yang dibutuhkan sehingga perlu ditambah. Untuk menambahkan perawat yang bekerja pada shift yang kekurangan tersebut, perlu dicari shift lain yang mempunyai kelebihan jumlah perawat. Untuk itu, cari shift k dimana ( 𝑛𝑖=1 𝑥𝑖𝑗𝑘 − 𝐶𝑗𝑘 ) maksimal dan ubah jadwal salah satu perawat dari shift k ke shift yang mengalami kekurangan jumlah perawat tersebut. Langkah ini (pencarian shift dengan ( 𝑛𝑖=1 𝑥𝑖𝑗𝑘 − 𝐶𝑗𝑘 ) maksimal dan pengubahan shift kerja) dilakukan hingga tidak ada shift yang kekurangan atau pemindahan shift sudah tidak dapat lagi dilakukan. Proses kedua, yaitu perbaikan pelanggaran terhadap shift kerja larut malam yang diikuti dengan shift kerja pagi dilakukan dengan proses swap atau penukaran. Untuk masingmasing hari, jadwal kerja shift pagi perawat yang pada hari sebelumnya bertugas pada shift larut malam ditukar dengan

5

jadwal perawat lain yang tidak bertugas pada shift pagi dan pada hari sebelumnya tidak bertugas pada shift larut malam. F. Penalty Functions pada HS-NSP Penalty function memberikan penalti pada solusi yang infeasible tanpa menghilangkan dasar nilai fitness dari solusi yang feasible [3]. Penambahan fungsi objektif dengan penalty functions untuk menghindari infeasibility tidak memiliki pengaruh terhadap pendekatan fundamental dari algoritma HS. Pada bagian sebelumnya telah dijelaskan pendekatan HS dalam menyelesaikan NSP. Namun, hal ini masih memungkinkan terjadinya pelanggaran terhadap batasan yang ada, yaitu batasan kebutuhan perawat, batasan jumlah maksimal hari kerja berturut-turut dan batasan shift kerja malam tidak boleh diikuti shift kerja pagi. Oleh karena itu, digunakan penalty functions untuk memberikan penalti pada solusi yang infeasible sehingga dapat mengarahkan algoritma metaheuristik HM untuk melakukan pencarian ke arah solusi yang lebih feasible. Perbedaan dari kebutuhan perawat dan penugasan sebenarnya pada jadwal dapat dituliskan sebagai 𝐶𝑗𝑘 − 𝑛 𝑖=1 𝑥𝑖𝑗𝑘 . Sebuah pelanggaran pada kebutuhan perawat akan diberikan penalti apabila 𝐶𝑗𝑘 − 𝑛𝑖=1 𝑥𝑖𝑗𝑘 > 0. Jumlah hari libur setiap maxcons hari dapat dituliskan 𝑗 sebagai 𝑝=𝑗 +1−𝑚𝑎𝑥 𝑐𝑜𝑛𝑠 𝑥𝑖𝑝𝑠 . Pelanggaran pada jumlah maksimal hari kerja berturut-turut akan diberikan penalti 𝑗 apabila 𝑝=𝑗 +1−𝑚𝑎𝑥 𝑐𝑜𝑛𝑠 𝑥𝑖𝑝𝑠 < 1. Sedangkan jumlah pelanggaran pada batasan shift larut malam tidak boleh diikuti shift kerja pagi dapat dituliskan sebagai 𝑥𝑖 𝑗 −1 (𝑠−1) + 𝑥𝑖𝑗 (1) dan akan diberikan penalti apabila 𝑥𝑖 𝑗 −1 (𝑠−1) + 𝑥𝑖𝑗 (1) = 2. Dengan demikian, fungsi objektif (11) dapat dituliskan sebagai 𝑚𝑒𝑚𝑖𝑛𝑖𝑚𝑎𝑙𝑘𝑎𝑛 𝑃 𝑦 = 𝑛 𝑑 𝑖=1 𝑗 =1 𝑝𝑖𝑗 (𝑦 𝑖𝑗 ) + 𝑃1 𝑃2 𝑃3

𝑛 𝑖=1 𝑛 𝑖=1

𝑑 𝑗 =1

𝑠 (0, 𝐶𝑗𝑘 − 𝑛𝑖=1 𝑥𝑖𝑗𝑘 ) 𝑘=1 max⁡ 𝑗 − 𝑝=𝑗 +1−𝑚𝑎𝑥 𝑐𝑜𝑛𝑠 𝑥𝑖𝑝𝑠 ) +

𝑑 (0,1 𝑗 =𝑚𝑎𝑥 𝑐𝑜𝑛𝑠 max⁡ 𝑑 (0, 𝑥𝑖 𝑗 −1 𝑠−1 𝑗 =2 max⁡

+ 𝑥𝑖𝑗

1

− 1)

+

(16)

dengan P1 = penalti untuk setiap pelanggaran terhadap batasan kebutuhan perawat, P2 = penalti untuk pelanggaran terhadap batasan jumlah maksimal hari kerja berturut-turut, dan P3 = penalti untuk pelanggaran terhadap batasan shift larut malam tidak boleh diikuti shift kerja pagi. III. IMPLEMENTASI Algoritma HS untuk NSP yang telah dijelaskan sebelumnya kemudian diterapkan untuk menyelesaikan NSP dari benchmark dataset NSPLib. Kasus yang digunakan adalah kasus 9 dengan jumlah perawat sebanyak 30 orang (N30). Uji coba pertama kali dilakukan untuk mencari parameter yang menghasilkan nilai fitness terbaik. berikut merupakan rancangan uji coba yang dilakukan.

TABEL I RANCANGAN UJI COBA

Parameter Jumlah Iterasi Replikasi Eksperimen HMS HMCR PAR

Nilai 1000 5 kali 1, 2, 5, 10 0.5, 0.7, 0.9, 0.99 0.01, 0.1, 0.5

Parameter penalti untuk masing-masing pelanggaran yang terdapat pada persamaan (16) masing-masing ditetapkan sebesar 100. Dari hasil uji coba tersebut, didapatkan sepuluh eksperimen dengan nilai fitness terbaik yang ditunjukkan pada Tabel 2. Pada tabel tersebut terlihat bahwa parameter HS yang memberikan hasil terbaik (dalam hal ini ditentukan dengan rata-rata nilai fitness) adalah HMS = 5, HMCR = 0.99, dan PAR = 0.01. TABEL II SEPULUH EKSPERIMEN DENGAN RATA-RATA NILAI FITNESS TERBAIK No

1 2 3 4 5 6 7 8 9 10

HMS

5 5 5 5 5 10 10 10 10 10

HMCR

0.99 0.99 0.99 0.99 0.99 0.99 0.99 0.99 0.99 0.99

PAR

0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01

Fitness

1857.48 1857.92 1858.64 1858.84 1859.37 1860.59 1860.87 1861.09 1861.34 1861.42

Waktu (dt)

0.491203 0.490674 0.491133 0.493705 0.491087 0.57027 0.573248 0.570906 0.570937 0.571447

Feasibilitas

92.29% 92.29% 92.29% 92.29% 92.29% 92.29% 92.29% 92.29% 92.29% 92.29%

Feasibilitas dari semua hasil uji coba adalah sama, yaitu 92.29%. Dengan kata lain, HS mampu menghasilkan solusi feasible dengan jumlah yang sama pada setiap parameter yang diujikan. Hal ini menunjukkan bahwa feasibilitas HS dalam menyelesaikan kasus NSP tidak dipengaruhi oleh parameterparameternya, melainkan pada kasus yang ditanganinya. Tujuh puluh empat kasus yang memberikan solusi tidak feasible tersebut setelah dilihat lebih lanjut memang tidak mungkin untuk diselesaikan. Hal ini disebabkan karena terdapat suatu hari dimana jumlah perawat yang dibutuhkan pada shift malam dan shift pagi keesokan harinya lebih besar dibandingkan dengan jumlah perawat yang ada. Hal ini akan menimbulkan salah satu di antara batasan kebutuhan perawat dan batasan shift malam tidak boleh diikuti shift pagi harus dilanggar. Tabel 3 merupakan contoh kasus yang infeasible. Pada tabel tersebut terlihat bahwa pada shift malam (shift 3) pada hari ke-8 dibutuhkan 21 orang perawat. Karena terdapat 30 perawat yang dapat ditugaskan, jika kita ingin memenuhi batasan shift malam tidak boleh diikuti shift pagi, maka hanya ada 9 perawat yang boleh ditugaskan pada shift pagi pada hari ke-9. Namun pada shift pagi hari ke-9 dibutuhkan 23 orang perawat yang melebihi jumlah perawat yang mungkin untuk ditugaskan. Hal ini menyebabkan salah satu di antara batasan kebutuhan perawat dan batasan shift malam tidak boleh diikuti shift pagi harus dilanggar, sehingga solusi yang dihasilkan menjadi infeasible.

6

TABEL III CONTOH KEBUTUHAN PERAWAT PADA SALAH SATU KASUS YANG INFEASIBLE Hari 1 2 3 4 5 6 7 8 9 10 11 12 13 14

Shift 1 Shift 2 Shift 3 2 1 5 1 2 3 18 3 23 5 20 0 2 20

0 0 3 1 3 1 5 3 6 0 1 0 4 0

2 5 0 0 0 0 0 21 0 20 4 0 24 5

Shift 4 Hari (Libur) 0 15 0 16 0 17 0 18 0 19 0 20 0 21 0 22 0 23 0 24 0 25 0 26 0 27 0 28

Shift 1 Shift 2 Shift 3 5 1 2 5 1 7 1 2 3 21 5 4 3 3

21 1 1 0 0 2 4 7 1 5 18 17 5 3

0 0 0 19 0 0 19 0 0 0 0 0 0 21

Shift 4 (Libur) 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Hasil terbaik yang didapatkan Harmony Search tersebut selanjutnya dibandingkan dengan hasil yang didapatkan penelitian-penelitian sebelumnya yang menggunakan dataset yang sama. Beberapa metode yang digunakan dalam penelitian-penelitian sebelumnya yang akan dibandingkan adalah sebagai berikut 1. Electromagnetism Meta-heuristic (EM) [3] 2. Scatter Search Algorithm (SS) [4] 3. Genetic Algorithm (GA) [5] Tabel 4 menunjukkan perbandingan hasil terbaik yang diperoleh algoritma HS dengan beberapa metode lainnya untuk menyelesaikan kasus 9 dengan jumlah perawat 30 orang pada benchmark dataset NSPLib. Dari tabel tersebut, jelas terlihat bahwa HS memberikan hasil yang terbaik untuk kedua kriteria yang dibandingkan, yaitu rata-rata fitness serta feasibilitas dari solusi. TABEL IV PERBANDINGAN HASIL BEBERAPA METODE UNTUK KASUS 9, N30 NSPLIB

Metode EM SS GA HS

Fitness 1983.96 2016.42 1995.68 1857.48

Feasibilitas 66.98% 65.94% 67.81% 92.29%

IV. KESIMPULAN Harmony Search diterapkan untuk menyelesaikan NSP pada benchmark dataset NSPLib kasus 9 dengan jumlah

perawat sebanyak 30 orang (N30). Harmony Search menghasilkan nilai fitness terbaik pada level HMS = 5, HMCR = 0.99, dan PAR = 0.01. Dibandingkan dengan tiga metode lainnya, yaitu Electromagnetism Meta-heuristic (EM), Scatter Search Algorithm (SS), dan Genetic Algorithm (GA), HS memberikan solusi terbaik pada kasus 9, N30 NSPLib dengan rata-rata nilai fitness sebesar 1857.48 dan feasibilitas sebesar 92.29% Pada studi selanjutnya, perlu dieksplorasi lebih lanjut mengenai penerapan HS untuk menyelesaikan NSP pada kasus yang spesifik, misalkan pada kasus yang memiliki perbedaan kualifikasi perawat serta jumlah minimal hari kerja berturut-turut. REFERENCES [1] B. Maenhout and M. Vanhoucke, "An Electromagnetism meta-heuristic for the nurse scheduling problem," Journal of Heuristics, 2005. [2] Chang-Chun Tsai and Sherman H.A. Li, "A two-stage modeling with genetic algorithms for the nurse scheduling problem," Expert Systems with Applications, vol. 36, pp. 9506-9512, 2009. [3] Broos Maenhout and Mario Vanhoucke, "An Electromagnetic MetaHeuristic for the Nurse Scheduling Problem," Journal of Heuristics, vol. 13, no. 4, pp. 359-385, August 2007. [4] Broos Maenhout and Mario Vanhoucke, "New Computational Results for the Nurse Scheduling Problem: A Scatter Search Algorithm," in Evolutionary Computation in Combinatorial Optimization, Jens Gottlieb and Günther Raidl, Eds.: Springer Berlin / Heidelberg, 2006, vol. 3906, pp. 159-170. [5] Broos Maenhout and Mario Vanhoucke, "A Comparison and Hybridization of Crossover Operators for the Nurse Scheduling Problem," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium, 2006. [6] T. Osogami and H. Imai, "Classification of various neighbourhood operations for the nurse scheduling problem," Lecture Notes in Computer Science, vol. 1969, pp. 72-83, 2000. [7] Z.W. Geem, J.H. Kim, and G.V. Loganathan, "A new heuristic optimization algorithm: harmony search," Simulation, vol. 2, no. 76, pp. 60–68, 2001. [8] Huang M., Bo G., and Wang X., "The optimization of routing in fourthparty logistics with soft time windows using harmony search," Proc. ICNC, pp. 4344-4348, 2010. [9] Z.W. Geem, K.S. Lee, and Y. Park, "Application of harmony search to vehicle routing," American Journal of Applied Sciences 2 (12), pp. 15521557, 2005. [10] M.A. Al-Betar and A.T. Khader, "A hybrid harmony search for university course timetabling," in Proceedings of the 4th Multidisciplinary International Scheduling Conference: Theory and Applications (MISTA 2009), Dublin, Ireland, 2009, pp. 157-179.

7