I PENDAHULUAN 1.1 Latar Belakang Sukarelawan adalah seseorang atau sekelompok orang yang secara ikhlas karena panggilan nuraninya memberikan apa yang dimilikinya tanpa mengharapkan imbalan. Sukarelawan memiliki peran yang sangat penting dalam kehidupan masyarakat. Mereka sangat dibutuhkan ketika ada suatu masalah yang sedang terjadi di suatu tempat, seperti saat terjadi bencana alam gunung meletus yang terjadi di Jawa Tengah dan Yogyakarta, serta bencana gempa bumi dan tsunami di Jepang baru-baru ini. Organisasi kemanusiaan yang bertugas menangani masalah sukarelawan masih mengalami kesulitan dalam mengelola para sukarelawan tersebut. Mereka kesulitan dalam masalah pengiriman dan penugasan para sukarelawan ke daerah-daerah yang membutuhkan. Oleh sebab itu, perlu dibuat sebuah model penjadwalan sukarelawan sebaik mungkin. Model penjadwalan sukarelawan ini akan mempertimbangkan keinginan dari setiap sukarelawan untuk menentukan pilihan blok waktu dan tugas yang diinginkannya. Masalah penjadwalan
sukarelawan ini dapat dimodelkan dalam bentuk pengoptimuman multikriteria. Pengoptimuman multikriteria merupakan masalah pengoptimuman yang memiliki lebih dari satu fungsi objektif. Masalah penjadwalan sukarelawan dapat diselesaikan dengan beberapa metode, di antaranya metode kendala-ε dan metode pembobotan. Karya ilmiah ini merupakan rekonstruksi dari tulisan Falasca et al. (2009) yang berjudul “An optimization model for humanitarian relief volunteer management”. Dalam karya ilmiah ini akan diperlihatkan formulasi dan penyelesaian masalah penjadwalan sukarelawan kemanusiaan dengan menggunakan bantuan software LINGO 8.0. 1.2 Tujuan Karya tulis ini bertujuan: 1. memformulasikan masalah penjadwalan tenaga sukarelawan dalam bentuk pengoptimuman multikriteria, 2. menyelesaikan masalah pengoptimuman multikriteria tersebut dengan metode kendala-ε dan metode pembobotan.
II LANDASAN TEORI 2.1 Pemrograman Linear Definisi 1 (Fungsi Linear) Misalkan , , … , menyatakan suatu fungsi dalam variabel-variabel , , … , . , , … , adalah suatu fungsi linear jika dan hanya jika untuk himpunan konstanta , , … , , dapat ditulis , , … , . (Winston 1995)
Sebagai gambaran, , 2 merupakan fungsi linear dengan c1 = 2 dan c2 = 1, sementara , bukan fungsi linear. Untuk sembarang bilangan b, persamaan , , … , merupakan persamaan linear, apabila f fungsi linear.
Definisi 2 (Pertidaksamaan Linear) Untuk sembarang fungsi linear , , … , dan sembarang bilangan b, pertidaksamaan , , … , dan , , … , disebut dengan pertidaksamaan linear. (Winston 1995)
Menurut Winston (1995), pemrograman linear (PL) adalah suatu masalah pengoptimuman yang memenuhi ketentuanketentuan sebagai berikut: a) Tujuan masalah tersebut adalah memaksimumkan atau meminimumkan suatu fungsi linear dari sejumlah variabel keputusan. Fungsi linear yang akan dimaksimumkan atau diminimumkan ini disebut fungsi objektif. b) Nilai variabel-variabel keputusannya harus memenuhi suatu himpunan kendala. Setiap kendala harus berupa persamaan linear atau pertidaksamaan linear. c) Variabel keputusan harus taknegatif atau tidak dibatasi tandanya. Suatu PL dikatakan memiliki bentuk standar jika berbentuk seperti yang didefinisikan di bawah ini. Definisi 3 (Bentuk Standar PL) Suatu pemrograman linear didefinisikan mempunyai bentuk standar sebagai berikut: Minimumkan
2
terhadap
0
(1)
Dengan c dan x merupakan vektor berukuran n, vektor b berukuran m, sedangkan A merupakan matriks berukuran m × n. Matriks A disebut matriks kendala. (Nash & Sofer 1996) Definisi 4 (Daerah Fisibel) Daerah fisibel untuk suatu PL adalah himpunan semua titik yang memenuhi semua kendala dan pembatasan tanda pada PL tersebut. (Winston 2004) Definisi 5 (Solusi Optimum) Solusi optimum terbaik adalah suatu titik dalam daerah fisibel yang menyebabkan nilai fungsi objektif terkecil (masalah minimisasi). Sedangkan, solusi optimum suatu PL maksimisasi adalah suatu titik dalam daerah fisibel yang menyebabkan nilai fungsi objektif terbesar. (Winston 1995) 2.1.1 Solusi PL Untuk menyelesaikan suatu masalah PL, metode simpleks merupakan salah satu metode yang dapat menghasilkan solusi optimum. Metode ini mulai dikembangkan oleh Dantzig pada tahun 1947. Metode ini adalah metode yang umum digunakan untuk menyelesaikan masalah PL. Metode simpleks ini berupa metode iteratif (proses mencari solusi yang dilakukan secara berulang-ulang hingga didapatkan solusi yang diinginkan) untuk menyelesaikan masalah PL berbentuk standar. Pada PL (1), vektor x yang memenuhi kendala disebut sebagai solusi dari PL (1). Misalkan matriks A dapat dinyatakan sebagai , sedangkan B merupakan matriks berukuran m × m yang elemennya berupa koefisien variabel basis dan N merupakan matriks yang elemennya berupa koefisien variabel nonbasis pada matriks kendala. Matriks B disebut matriks basis untuk PL (1). Misalkan x dapat dinyatakan sebagai vektor dengan adalah vektor variabel basis dan adalah vektor variabel nonbasis, maka
(2)
Karena B adalah matriks taksingular, maka B memiliki invers, sehingga dari (2) dapat dinyatakan sebagai berikut:
(3)
Definisi 6 (Solusi Basis) Solusi dari suatu PL disebut solusi basis jika: i. Solusi tersebut memenuhi kendala PL. ii. Kolom-kolom dari matriks koefisien yang berpadanan dengan komponen taknol adalah bebas linear. (Nash & Sofer 1996) Definisi 7 (Solusi Fisibel Basis) Vektor x disebut solusi fisibel basis jika x merupakan solusi basis dan 0. (Nash & Sofer 1996) Contoh 1 Misalkan diberikan pemrograman berikut: minimumkan 2 3 ,
linear
dengan kendala 2 4
2 ! 11
2 % 1 1
1 2 0
# 5.
1 0 0 0 1 0', 0 0 1
Dari PL tersebut didapatkan
!
Misalkan dipilih
4 %11'. 5
# ( dan
Maka matriks basisnya adalah 1 %0 0
0 0 1 0'. 0 1
0
0 ( ,
(4)
(
Dengan menggunakan matriks basis tersebut diperoleh 4
11
5 ( .
(5)
Solusi (5) merupakan solusi basis, karena memenuhi kendala pada PL (4) dan kolomkolom pada matriks kendala yang berpadanan dengan komponen taknol dari (5) yaitu B adalah bebas linear (kolom yang satu bukan merupakan kelipatan dari kolom yang lain). Solusi (5) juga merupakan solusi fisibel basis, karena nilai-nilai variabelnya lebih dari atau sama dengan nol.
3
Definisi 8 (Matriks Basis) Suatu matriks disebut matriks basis untuk PL jika matriks tersebut adalah matriks taksingular, yaitu matriks yang determinannya tidak sama dengan nol. (Garfinkel & Nemhauser 1972) 2.2 Pemrograman Linear Bilangan Bulat Model pemrograman linear bilangan bulat (PLBB) atau integer linear programming (ILP) adalah suatu model pemrograman linear dengan variabel yang digunakan berupa bilangan bulat. Model PLBB yang semua variabelnya bernilai bilangan bulat disebut pemrograman bilangan bulat murni. Sedangkan, model PLBB yang hanya sebagian variabelnya bernilai bilangan bulat disebut pemrograman bilangan bulat campuran. Model PLBB yang hanya mengharuskan nilai nol atau satu untuk variabelnya dinamakan pemrograman bilangan bulat 0-1. (Garfinkel & Nemhauser 1972) Definisi 9 (Pemrograman Linear Relaksasi) PL-relaksasi merupakan pemrograman linear yang diperoleh dari suatu PLBB dengan menghilangkan kendala bilangan bulat atau kendala 0-1 pada setiap variabelnya. Untuk masalah meminimumkan, nilai fungsi objektif yang optimum di PL-relaksasi lebih kecil atau sama dengan nilai fungsi objektif yang optimum di PLBB, sedangkan untuk masalah memaksimumkan nilai fungsi objektif yang optimum di PL-relaksasi lebih besar atau sama dengan nilai fungsi objektif yang optimum di PLBB. (Winston 1995)
sumber i ditugaskan pada tujuan j, sedangkan bernilai nol jika selainnya. Parameter bij adalah biaya penugasan untuk sumber i ke tujuan j. Parameter 1- adalah jumlah penugasan setiap sumber i pada tujuan j. Parameter 7. adalah jumlah sumber i yang ditugaskan pada setiap tujuan j. (Siswanto 2006) 2.3 Pemrograman Multiobjektif Masalah pengoptimuman yang telah didiskusikan sebelumnya adalah masalah pengoptimuman yang hanya memiliki satu fungsi objektif. Sedangkan, masalah pengoptimuman yang akan dibahas sekarang adalah masalah pengoptimuman yang memiliki lebih dari satu fungsi objektif. Masalah pengoptimuman yang dimaksud adalah masalah pengoptimuman multikriteria. Pada masalah pengoptimuman multikriteria ini, ada beberapa istilah yang harus diketahui seperti pengambilan keputusan multikriteria atau multiple criteria decision making (MCDM). Sebuah masalah pengoptimuman multikriteria dapat dikatakan sebagai MCDM jika terdapat lebih dari satu hal yang harus diperhatikan dalam model tersebut sebagai tujuan atau kriterianya. (Eiselt & Sandblom 2007) Definisi 11 (Formulasi MCDM) Masalah pengoptimuman multikriteria biasanya diformulasikan sebagai berikut. min
[f1(x), f2(x), …, fk(x)],
dengan kendala gj (x) ≤ 0, j = 1, 2, …, m dan x = { xi | i = 1, 2, …, n }.
Definisi 10 (Model Matematika Penugasan) Bentuk umum dari model matematika masalah penugasan adalah sebagai berikut: 0
min , , -. -. , -/ ./
dengan kendala
, -. 1- , ./ 0
, -. 7. , -/
untuk 5 1, 2, … , 6 untuk 8 1, 2, … , 9
-. 0. Misalkan tujuan model di atas adalah meminimumkan biaya penjadwalan. Asumsikan xij sebagai penugasan dari sumber i ke tujuan j. Nilai xij sama dengan satu jika
(6)
keterangan: fl (x) = fungsi objektif ke-l, l = 1, 2, …, k, gj (x) = fungsi kendala ke-j, j = 1,2, …, n. (Ravindran 2009) 2.4 Metode Penyelesaian Ada banyak metode penyelesaian yang dapat dipergunakan untuk menyelesaikan masalah pengoptimuman multikriteria ini. Contohnya adalah metode pembobotan, metode kendala, metode kendala-ε, metode simpleks banyak tujuan, metode preference prior technique, dsb. Namun, pada tulisan ini metode yang akan dibahas adalah metode pembobotan dan metode kendala-ε.
4
2.4.1 Metode Pembobotan Metode pembobotan merupakan salah satu metode penyelesaian yang tertua dan metode yang paling sederhana dari MCDM. Metode ini pertama kali direkomendasikan oleh Zadeh. Metode ini menggabungkan semua fungsi objektif yang ada dalam model, dan setiap fungsi objektif tersebut diberikan bobot (w) yang berbeda. Misalkan diberikan permasalahan MCDM seperti pada model (6). Setelah dilakukan metode pembobotan, fungsi objektif gabungannya akan seperti persamaan berikut min z = w1 f1(x) + …+ wk fk(x).
(7)
Fungsi objektif tersebut selanjutnya dioptimumkan dengan menggunakan variasi bobot yang berbeda. Nilai total dari bobotbobot tersebut harus satu, yaitu: w1 + w2 + …. + wk = 1. (Eiselt & Sandblom 2007) 2.4.2 Metode Kendala-ε Ide dasar metode ini adalah mengubah hampir semua fungsi objektifnya menjadi kendala. Metode ini hanya menyisakan satu fungsi objektif saja, misalkan fungsi objektifnya adalah f1(x). Fungsi objektif lainnya akan diubah menjadi kendala. Fungsi objektif yang akan diubah menjadi kendala pertama-tama harus dicari solusi optimalnya. Solusi optimal tersebut setelah dikalikan dengan parameter ε akan menjadi nilai dari sisi kanan kendala baru. Setelah itu, optimumkan fungsi objektif f1(x) dengan menambahkan kendala-kendala baru tersebut. Fungsi objektif tersebut dicari solusi optimalnya dengan mencoba beberapa nilai ε berbeda. Misalkan formulasi model (6) akan dicoba diselesaikan dengan menggunakan metode kendala-ε. Tahapan pengoptimuman model (6), yaitu: Langkah 1 max fi(x) ; i = 2, 3, …, k, dengan kendala gj (x) ≤ 0
; j = 1, 2, …, m.
Langkah 2 dilakukan berulang kali dengan menggunakan nilai ε yang berbeda sehingga didapatkan nilai f1*(x) dan x. Nilai x yang didapat dari Langkah 1 digunakan untuk mencari nilai fi* (x) yang baru. Terakhir, buatlah trade-off nilai f1*(x) dan fi* (x) yang baru. (Falasca et al. 2009) Contoh 2 Misalkan diberikan model seperti di bawah ini: max z1 = –2x1 + 3x2 max z2 = 3x1 – x2 dengan kendala –x1 + x2 ≤ 2 x1 + 2x2 ≤ 6 x1 ≤ 4 x1 + x2 ≥ 1 x1, x2 ≥ 0
Model (8) di atas akan diselesaikan dengan menggunakan metode kendala-ε. Misalkan fungsi objektif 1 ditetapkan sebagai fungsi objektif, maka fungsi objektif 2 harus diubah menjadi kendala. Tahapan pengoptimuman model (8), yaitu: Langkah 1 max z2 = 3x1 – x2 dengan kendala –x1 + x2 ≤ 2 x1 + 2x2 ≤ 6 x1 ≤ 4 x1 + x2 ≥ 1 x1, x2 ≥ 0
dengan kendala –x1 + x2 ≤ 2
dengan kendala
x1 + x2 ≥ 1
fi (x) ≥ ε
fi* (x)
(9)
Solusi optimum yang diperoleh dari langkah 1 adalah x1 = 4, x2 = 0 dan z1*= 12 (lihat Lampiran 1). Langkah 2 max z1 = –2x1 + 3x2
Pada Langkah 1, akan diperoleh fi*(x) yang merupakan solusi dari fungsi objektif ke-i. Langkah 2 max f1(x) gj (x) ≤ 0
(8)
x1 + 2x2 ≤ 6 x1 ≤ 4
; j = 1, 2, …, m
3x1 – x2 ≥ 12ε
; 0 ≤ ε ≤ 1, i = 2, 3, …, k
x1, x2 ≥ 0
(0 ≤ ε ≤ 1) (10)
5
Sekarang nilai z1 bergantung pada nilai ε. Nilai ε yang diperbolehkan adalah yang kurang dari satu karena jika nilai ε lebih besar dari satu maka nilai sisi kanan dari kendala baru 3x1 – x2 ≥ 12ε akan lebih besar dari dua belas. Sedangkan pada Langkah 1 diketahui bahwa solusi maksimum kendala baru tersebut adalah dua belas (z1*= 12). Karena itu tidak akan ditemukan solusi jika nilai dari sisi kanan kendala baru tersebut lebih besar dari dua belas. Model (10) harus diselesaikan berulang-ulang untuk nilai ε yang berbeda. Solusi yang didapatkan dari pengoptimuman Langkah 2 disajikan pada Tabel 1. Tabel 1 Solusi pengoptimuman Langkah 2 Ε x1 x2 z1* z2* 0.25 1.71 2.14 3 3 0.33 2 2 2 4 0.5 2.57 1.71 0 6 0.67 3.14 1.43 8 -2 0.75 3.43 1.285 9 -3
Dilihat dari Tabel 1, dapat disimpulkan semakin besar nilai ε yang dipakai, nilai z1* akan semakin kecil sedangkan nilai z2* akan semakin besar. Untuk lebih jelas, disajikan grafik perubahan nilai z1* dan z2* pada Gambar 1 (lihat Lampiran 1). 10 9 8 7 6 5 4 3 2 1 0 -4
-3
-2
-1
z2*
0
1
2
3
4
z1* Gambar 1 Grafik perubahan nilai z1* dan z2* pada bobot yang berbeda.
III DESKRIPSI DAN FORMULASI MASALAH 3.1 Deskripsi Masalah Model penjadwalan tenaga sukarelawan berbeda dengan model penjadwalan tenaga kerja biasa. Kunci utama perbedaan kedua model tersebut adalah tujuannya. Tujuan model penjadwalan tenaga sukarelawan lebih mementingkan misi kemanusiaan daripada memaksimumkan keuntungan. Perbedaan penting lainnya adalah terkait dengan keahlian yang dimiliki sumberdaya manusianya. Model
penjadwalan tenaga kerja yang biasa mengasumsikan bahwa semua tenaga kerja memiliki keahlian yang dibutuhkan untuk menyelesaikan tugas. Namun, pada masalah penjadwalan tenaga sukarelawan harus dipertimbangkan bahwa adanya beberapa sukarelawan mungkin tidak memiliki tingkat keterampilan yang diperlukan untuk menyelesaikan tugas-tugas tertentu.
Tabel 2 Perbedaan antara model tenaga kerja dan model sukarelawan Atribut Model
Model Penjadwalan Tenaga Kerja
Tujuan
Memaksimumkan keuntungan dan meminimumkan biaya
Kendala kunci
Tugas-tugas yang dibutuhkan
Biaya tenaga kerja
Diasumsikan mencukupi atau tidak menjadi kendala Taknol
Preferensi tenaga kerja
Beberapa model mempertimbangkan preferensi waktu
Kekurangan tugas kerja
Tidak dibahas
Jumlah tenaga kerja
Model manajemen sukarelawan tersebut juga harus mempertimbangkan hipotesis-hipotesis
Model Penjadwalan Tenaga Sukarelawan Memaksimumkan penyelesaian tugas dengan meminimumkan kekurangan Sukarelawan yang memiliki komitmen Ditentukan oleh banyaknya sukarelawan yang berkomitmen Rendah namun masih taknol Model harus mempertimbangkan preferensi tugas dan waktu yang diinginkan sukarelawan Kekurangan antara tugas-tugas harus seimbang
lain yang sebelumnya Sampson (2006), yaitu:
telah diuji
oleh
