BAB 2 LANDASAN TEORI
2.1. Penjadwalan 2.1.1 Definisi Penjadwalan M enurut Stevenson (Stevenson, 2009), penjadwalan adalah kegiatan yang berkaitan dengan membangun jaringan waktu dengan satu atau lebih sumber daya dari organisasi tersebut. Sumber daya yang dimaksud bisa berupa perlengkapan, peralatan, fasilitas, dan aktivitas manusia. Penjadwalan selalu berhubungan dengan pengalokasian sumber daya yang ada pada jangka waktu tertentu. Kegiatan penjadwalan disebabkan karena adanya beberapa pekerjaan yang dikerjakan secara bersamaan, sedangkan sumber daya yang dimiliki terbatas (Pinedo, 2002). 2.1.2 Tujuan Penjadwalan M enurut Stevenson (Stevenson, 2009), secara umum penjadwalan dilakukan untuk mencari dan mendapatkan titik temu di antara beberapa tujuan yang saling bertentangan. Tujuan tersebut di antaranya efisiensi kinerja staff, perlengkapan, dan fasilitas, dan meminimalisasikan inventaris, waktu proses, dan waktu menunggu pelanggan. M enurut Russel dan Taylor (Russell & Taylor, 2009), tujuan dari penyusunan jadwal pada umumnya adalah: 1.
M engetahui tanggal jatuh tempo.
2.
M eminimalkan keterlambatan kerja.
3.
M eminimalkan waktu respon.
4.
M eminimalkan waktu penyelesaian.
5.
M eminimalkan waktu proses dalam sistem.
6.
M eminimalkan waktu lembur.
7.
M eminimalkan rentang waktu (idle time).
8.
M emaksimalkan penggunaan mesin atau tenaga kerja.
Secara spesifik disebutkan untuk institusi pendidikan, penjadwalan yang baik bisa mengurangi kebutuhan penambahan fasilitas sehingga bisa mengoptimalkan penggunaan fasilitas yang ada (Stevenson, 2009). 2.1.3 Peranan Penjadwalan M enurut Pinedo (Pinedo, 2002), penjadwalan mengambil peran dalam proses pembelian dan produksi, transportasi dan distribusi, pemrosesan informasi dan komunikasi. Penjadwalan sendiri biasanya menggunakan teknik-teknik yang matematis atau metode heuristik dalam melakukan pengalokasian sumber daya yang terbatas ke dalam proses yang lebih spesifik. Untuk mengatur dan menjaga pemerataan utilitas dari sumber daya, penjadwalan harus bisa membagi proses tersebut ke dalam prioritas. Dalam praktiknya, penjadwalan akan berhadapan langsung dengan banyak fungsi, yang bisa berdiri sendiri ataupun berbeda-beda dari satu situasi ke situasi yang lainnya. Secara umum, proses penjadwalan yang baik diharapkan dapat mengoptimalkan sumber daya yang ada, meminimalisasi waktu proses, dan meminimalisasi keterlambatan proses dalam berbagai situasi yang ada selama penjadwalan berlangsung.
2.2. Penjadwalan Universitas 2.2.1 Deskripsi Penjadwalan Universitas M asalah penjadwalan pada universitas dikenal dengan nama University Course Timetabling Problem (UCTP). Penjadwalan universitas merupakan salah satu penjadwalan dengan tingkat kompleksitas yang tinggi dan memiliki batasan yang banyak. Permasalahan penjadwalan untuk masing-masing universitas sangatlah berbeda antar satu dengan yang lain. Tugas utama dari UCTP adalah untuk mengalokasikan sejumlah tenaga kerja, atau dalam hal ini dosen, ke dalam satuan slot waktu dan ruang dengan memperhatikan pada batasan-batasan yang harus dipenuhi (Irene, Safaai-Deris, & Hashim, 2009). 2.2.2 Jenis Penjadwalan Universitas Klasifikasi jenis penjadwalan pada universitas dibagi menjadi lima klasifikas i menurut kegunaan dan implementasinya (Adriaen, Causmaecker, Demeester, & Berghe, 2006): 1.
Penjadwalan fakultas, untuk mengalokasikan dosen yang berkualifikasi ke matakuliah yang ada, dengan hasil berupa jadwal dosen.
2.
Penjadwalan kelas-dosen, untuk mengalokasikan kelas mahasiswa sesuai dengan ketersediaan dosen, dengan hasil berupa jadwal transaksi tiap kelas.
3.
Penjadwalan matakuliah, untuk mengalokasikan matakuliah ke tiap-tiap mahasiswa, dengan hasil berupa jadwal mahasiswa.
4.
Penjadwalan pelaksanaan ujian, untuk mengalokasikan kebutuhan ujian, dengan ketentuan tidak ada dua atau lebih ujian dalam waktu yang bersamaan.
5.
Penjadwalan ruang kelas, untuk mengalokasikan transaksi tiap kelas ke ruangan yang tersedia.
M asing-masing dari penjadwalan tersebut saling esensial, namun urutan dalam pengerjaannya bisa berubah sesuai dengan sistem dan aturan masing-masing universitas. Klasifikasi ini membuat penjadwalan universitas yang kompleks bisa menjadi lebih sederhana. 2.2.3 Parameter Penjadwalan Universitas M enurut Burke (Burke, Kingston, & Werra, 2004), secara spesifik permasalahan penjadwalan bisa diuraikan menjadi empat parameter utama, T (himpunan waktu), R (himpunan sumber daya), M (himpunan pertemuan atau transaksi), C (himpunan batasan atau constraint): 1.
Time (T) Satuan waktu t adalah elemen himpunan T
dari sebuah contoh masalah
penjadwalan. Satuan waktu ini menjadi sebuah variabel batasan untuk mewakili satu waktu. Biasanya satuan waktu ini diukur dalam bentuk shift per matakuliah. 2.
Resources (R) Satuan sumber daya r adalah elemen himpunan R dari sebuah contoh masalah penjadwalan. Satuan sumber daya ini menjadi sebuah variabel batasan untuk mewakili satu sumber daya. Sumber daya yang dimaksud adalah para dosen, ruangan, peralatan khusus, asisten pembantu, ketersediaan alat-alat pendukung dan lainnya.
3.
Meeting (M ) Satuan pertemuan atau transaksi m adalah kumpulan hubungan dari satuan waktu dan satuan sumber daya. Pemberian nilai pada satuan ini menunjukkan bahwa terjadi pemenuhan transaksi antara sumber daya dengan waktu yang ada.
4.
Constraint (C) Satuan batasan, dibagi menjadi dua, hard constraint dan soft constraint. M erupakan sekumpulan batasan-batasan dari sumber daya atau fasilitas terhadap pertemuan atau transaksi.
Untuk parameter keempat akan dibahas lebih lanjut pada bagian selanjutnya, tentang batasan penjadwalan pada universitas. 2.2.4 Batasan Penjadwalan Universitas Seperti yang sudah dibahas sebelumnya, batasan pada penjadwalan universitas dibagi menjadi dua, yaitu hard constraint (hc) dan soft constraint (sc). Untuk hard constraint adalah batasan yang harus dipenuhi, sedangkan soft constraint adalah batasan yang bila dipenuhi akan membuat jadwal lebih optimal. Batasan pada universitas umumnya berbeda antara yang satu dengan lainnya, namun bila melihat pada pemenuhan tiap-tiap hard constraint, beberapa yang menjadi batasan utamanya: 1.
Tidak ada sumber daya, baik itu dosen, mahasiswa, ruangan, dan lainnya yang dijadwalkan lebih dari satu pada waktu yang bersamaan.
2.
Tidak ada dua atau lebih dosen yang mengajar pada satu transaksi matakuliah di kelas yang sama.
3.
Penjadwalan dosen harus disesuaikan dengan kemampuan dan kualifikasi di bidangnya.
Pada soft constraint diuraikan berbagai kebijakan dan keputusan yang ada pada organisasi untuk mengoptimalkan sumber daya, sehingga untuk soft constraint tidak bisa dijabarkan secara umum, tergantung pada masing-masing organisasi.
2.3. Harmony Search 2.3.1 Pengenalan Harmony Search termasuk salah satu dari algoritma evolusi dan metaheuristik yang digunakan untuk pemecahan masalah optimalisasi. Harmony Search diinspirasi dari fenomena para musisi jazz dalam berimprovisasi sehingga menghasilkan harmonisasi nada yang indah. Cara para musisi jazz ini berimprovisasi menjadi inspirasi bagi Dr. Zong Woo Geem, dkk (Geem, Kim, & Loganathan, A New Heuristic Optimization Algorithm: Harmony Search, 2001). 2.3.2 Analogi Harmonisasi dan Optimalisasi Pada Gambar 1, memperlihatkan secara detail tentang analogi antara improvisasi music dan teknik optimalisasi. Dalam improvisasi musik, masing-masing musisi membunyikan sebuah nada dalam tingkat nada yang mungkin dihasilkan, nada-nada tersebut membuat sebuah vektor harmoni. Jika semua nada menghasilkan harmoni yang bagus, maka pengalaman membuat harmoni tersebut akan tersimpan di ingatan para musisi, sehingga kemungkinan untuk membuat harmoni bagus lainnya akan meningkat. Hal ini diadaptasi dalam teknik optimalisasi, dengan masing-masing variabel keputusan
memilih nilai awal (initial value) dalam batasan yang mungkin membentuk sebuah vektor solusi. Jika masing-masing variabel keputusan membentuk harmoni yang baik, pengalaman tersebut akan disimpan dalam variabel memori, yang nantinya akan memperbesar kemungkinan untuk mendapatkan vektor solusi yang lebih baik (Geem & Lee, 2005).
G ambar 1 Analogi antara improvisasi musik dan teknik optimalisasi
Sebagai contoh, pada Gambar 2, diperlihatkan struktur dari harmony memory yang merupakan bagian inti dari harmony search. Terlihat pada gambar dicontohkan dengan tiga musisi jazz yang masing-masing menggunakan saxofon, dual bass, dan gitar. Tertera pada masing-masing musisi berupa nada yang tersimpan di memori, musisi saxofon dengan {Do, M i, Sol}, musisi dual bass dengan {Si, Sol, Re}, dan musisi gitar dengan {La, Fa, Do}. Jika saxofon menghasilkan nada {Sol} dari memorinya {Do, M i, Sol}, dual bass menghasilkan nada {Si} dari memorinya {Si, Sol, Re}, dan gitar menghasilkan {Do} dari memorinya {Do, M i, Sol}, maka akan terbentuk sebuah memori harmoni baru dengan nilai { Sol, Si, Do} (dalam musik dikenal sebagai akor C7). Bila harmoni baru dengan nilai {Sol, Si, Do} lebih baik dari harmoni lama yang
ada di memori maka harmoni baru tersebut dimasukkan ke dalam memori harmoni, sedangkan yang lebih buruk akan dike luarkan. Langkah ini akan terus dilakukan hingga harmoni yang fantastis (optimal) ditemukan.
G ambar 2 Contoh struktur dari harmony me mory
Dalam kasus nyatanya, setiap musisi dianalogikan sebagai variabel-variabel keputusan dengan nada yang tersimpan di memori adalah nilai-nilai yang didapat dari pengumpulan data atas variabel keputusan. Jika variabel keputusan berupa ukuran diameter antara dua node, dengan X1 {100mm, 300mm, 500mm}, X2 {700mm, 500mm, 200mm}, dan X3 {600mm, 400mm, 100mm}, dan dari masing-masing node didapatkan harmoni baru dengan nilai Xt {100mm, 500mm, 400mm}. Bila hasil harmoni baru lebih baik dari yang sebelumnya, maka harmoni baru akan disimpan dan harmoni yang lebih buruk yang ada di memori harmoni akan dike luarkan. Hal ini dilakukan secara berulang sampai beberapa kriteria terpenuhi dan dianggap memuaskan (Geem & Lee, 2005).
2.3.3 S trategi Pencarian Ada beberapa strategi yang bisa digunakan untuk mendapatkan harmonisasi yang baik. Pada pertunjukan musik yang dilakukan oleh para musisi jazz, biasanya mereka memiliki tiga pilihan untuk melakukan improvisasi: 1.
M emainkan nada yang sering dimainkan, yang merupakan karakteristik dari bagian musik tersebut. Dalam musik, nada ini dikenal dengan sebutan nada dasar. Pada dasarnya semua musisi mengerti nada dasar tersebut dan dapat memainkan nada tersebut dengan sendirinya, dengan kata lain nada-nada dasar ini sudah tersimpan dalam memori mereka.
2.
M emainkan nada yang serupa dengan nada dasar. Biasanya musisi memperkaya musik dengan menaikkan atau menurunkan nada dasar sesuai dengan eksplorasi mereka. Hal ini akan menyebabkan permainan musik serupa dengan variasi nada yang berbeda.
3.
M emainkan nada sembarang, yang memberikan musisi kebebasan untuk berimprovisasi. Dengan cara seperti ini, ada kemungkinan not yang dihasilkan sedikit atau tidak memiliki hubungan dengan lagu yang ditampilkan. Hal ini membutuhkan bakat dan imajinasi dari musisi, yang membuatnya menjelajahi dunia musik dan memberikan nuansa baru pada musik dengan tema-tema segar dan baru.
Dari tiga pilihan berimprovisasi di atas, memberikan para peneliti strategi untuk mendapatkan harmonisasi yang baik. Hal ini diadaptasi, sehingga setiap variabel keputusan dalam mengambil sebuah nilai dalam algoritma harmony search harus berpedoman pada tiga aturan ini (Geem & Lee, 2005):
1.
M engambil nilai yang sudah terdapat pada memori harmoni, biasanya didefinisikan sebagai memory considerations.
2.
M engambil nilai yang berdekatan dari satu nilai pada memori harmoni, biasanya didefinisikan sebagai pitch adjustments.
3.
M engambil nilai acak dari rentang nilai yang mungkin, biasanya didefinisikan sebagai randomization.
Tiga aturan ini nantinya akan dibutuhkan dalam menyusun algoritma harmony search yang diwakilkan oleh beberapa parameter.Secara umum parameter-parameter ini akan sangat mempengaruhi kinerja dari harmony search dalam mendapatkan solusi yang optimal. 2.3.4 Parameter Harmony Search Berikut adalah parameter yang digunakan secara umum dalam harmony search (Geem & Lee, 2005): 1.
HM S (Harmony Memory Size), adalah jumlah dari kumpulan harmoni memori, bisa disebut sebagai jumlah populasi.
2.
HM CR (Harmony Memory Consideration Rate), adalah probabilitas dari harmoni memori untuk digunakan kembali sebagai hasil dari vektor solusi. Parameter ini memiliki rentang nilai dari 0 sampai dengan 0,99. Parameter ini tidak menggunakan nilai 1, untuk mencegah terjadinya stagnansi nilai (range nilai tidak berubah dan perbaikan minimal).
3.
PAR (Pitch Adjustment Rate), adalah parameter yang mempunyai peran signifikan dalam menentukan jumlah nilai yang harus diubah, disesuaikan,
atau ditukar dengan nilai yang lain. Parameter ini memiliki rentang nilai dari nol sampai dengan satu. 4.
NI (Number of Improvisations), adalah parameter yang digunakan sebagai kriteria pemberhenti perulangan, biasanya berupa jumlah iterasi untuk mendapatkan nilai yang optimal.
2.3.5 Algoritma Harmony Search Langkah-langkah yang digunakan dalam melakukan algoritma harmony search adalah (Geem & Lee, 2005): 1.
Inisialisasi Harmony Search Algorithm (HSA) dan parameter-parameter permasalahan optimasi.
2.
Inisialisasi Harmony Memory (HM ).
3.
Improvisasi sebuah harmoni baru.
4.
M emperbarui Harmony Memory (HM ).
5.
M elakukan pengecekan kondisi berhenti.
Dalam langkah (1), perlu diperhatikan fungsi objektif yang akan digunakan untuk menghitung nilai perbaikan dari HM . Fungsi objektif bisa dispesifikasikan sebagai berikut: |
|
atau
Keterangan: a. b.
, fungsi objektif. , himpunan dari setiap variabel keputusan
untuk
1…
.
c.
, himpunan dari rentang nilai yang mungkin untuk setiap variabel keputusan, 1 ,
dengan,
2 ,…,
.
d.
adalah jumlah variabel keputusan.
e.
adalah jumlah rentang nilai yang mungkin untuk setiap variabel keputusan.
Dalam langkah (2), HM adalah vektor solusi dengan banyak sejumlah HM S. Pada langkah ini solusi-solusi yang dibentuk merupakan nilai random. Bentuk HM bila digambarkan dalam M atriks bisa berbentuk seperti:
.
Untuk setiap
dengan
1…
.
.
.
, perlu ditentukan nilai fungsi objektifnya
,
agar bisa diketahui mana himpunan yang memiliki nilai terbaik dan nilai terburuk. Dalam prosesnya, himpunan dengan nilai terbaik akan menjadi solusi yang dipakai, sedangkan himpunan dengan nilai terburuk akan tereliminasi dan digantikan dengan yang himpunan dengan nilai yang lebih baik selama perulangan berlangsung. Dalam langkah (3), HSA akan secara otomatis membuat vektor solusi yang baru, ,
,
,…,
, berdasarkan pada tiga operator: (a) memory
consideration, (b) random consideration, dan (c) pitch adjustment. a.
M emory Consideration Pada operator ini, pencarian variabel keputusan akan berdasarkan pada memori yang tersimpan sebelumnya di posisi yang sama dengan kemungkinan
pemilihan operator ini sebesar parameter HM CR, dengan kemungkinan 0
1 .
Bila operator ini dilaksanakan, maka untuk mendapatkan variabel keputusan yang baru
akan dipilih dari himpunan
,
,
,…,
yang
disimpan dalam HM . Untuk mendapatkan variabel keputusan selanjutnya maka akan dipilih dari himpunan
,
,
,…,
yang disimpan
dalam HM . Hal ini berlaku juga untuk variabel-variabel keputusan yang lain , b.
,
… .
Random Consideration Operator ini akan terlaksanakan dengan kemungkinan 1
, yang
merupakan alternatif apabila operator memory consideration tidak digunakan dalam mencari vektor solusi. Bila operator ini dilaksanakan, maka untuk mendapatkan variabel keputusan yang baru adalah nilai yang termasuk dalam
. Jadi operator ini akan
mengambil calon vektor solusi dari semua variabel keputusan yang terdapat pada HM . c.
Pitch Adjustment Operator ini akan terlaksana dengan sebuah prasyarat, terlaksananya operator memory consideration. Operator ini akan melakukan improvisasi nilai dari variabel keputusan secara lokal. Operator ini memiliki kemungkinan terjadi . Bila operator ini dilaksanakan, dengan varibel keputusan
dengan
adalah posisi elemen / nilai pada
, dengan
, maka
… , 2, 1, 0, 1, 2, … . Operator ini akan
adalah neighborhood index,
mengambil calon vektor solusi dari vektor neighborhood yang mungkin. ,
Dalam langkah (4), jika hasil vektor harmoni
,
,…,
,
memiliki nilai fungsi objektif yang lebih baik dari vektor harmoni dengan nilai fungsi objektif terburuk di HM , maka vektor harmoni yang baru akan dimasukkan ke dalam HM , sedangkan vektor harmoni dengan nilai fungsi objektif terburuk di HM akan dike luarkan. Dalam langkah (5), akan dilakukan pengecekan sampai kondisi berhenti dari algoritma harmony search terpenuhi. Biasanya kondisi berhenti dari algoritma adalah nilai dari parameter NI (jumlah maksimal dari perbaikan harmoni). Bila kondisi berhenti salah, maka ulangi langkah (3) dan langkah (4). 2.3.6 Contoh Untuk lebih memperjelas algoritma harmony search, akan disertakan contoh dari pencarian harmoni secara sederhana tanpa menampilkan batasan-batasan yang kompleks. Contoh yang diambil dari slide pendukung harmony search(Geem, 2009): Bila diberikan fungsi min hasil 0
2
3
1
3 dengan range
5 dan tempat penyimpanan harmoni sebesar 3 (HM S). Hasil generate
awal untuk pencarian ini (HM ):
Rank 1
2
2
1
4
Rank 2
1
3
4
13
Rank 3
5
3
3
16
Generate secara random dengan nilai untuk masing-masing
adalah
,
yang didapatkan dengan kemungkinan generalisasi dari HM CR dan PAR. M aka untuk hasil generate selanjutnya:
Rank 1
2
2
1
4
Rank 2
1
2
3
9
Rank 3
1
3
4
13
Proses generate akan berlangsung selama parameter NI belum terpenuhi, dengan NI merupakan banyaknya perulangan yang diinginkan untuk perbaikan harmoni memori. Dari 2 hasil generate dapat dilihat bila hasil generate yang lebih baik akan dimasukkan dan dibuat peringkat dalam memory. Data tersebut bisa dibaca berdasarkan baris dan kolom, baris akan memperlihatkan ranking dan kolom akan memperlihatkan lokal optimal. Dari sini bisa dilihat perubahan yang terjadi untuk mendapatkan global optimal. 2.4. Rapid Application Development
G ambar 3 Model Rapid Application Development
M erupakan salah satu metode pembuatan software untuk dengan menggabungkan metode iterative development dan metode prototyping (Whitten & Bentley, 2005). Rapid Application Development (RAD) biasanya digunakan dalam pembuatan aplikasi atau piranti lunak yang membutuhkan flexibilitas dan mobilitas yang tinggi. Beberapa langkah dalam metode RAD: 1.
Requirement and Planning Tahap ini digunakan untuk mencari tahu kebutuhan user dan batasan-batasan apa saja yang ada. Tahapan ini juga digunakan untuk melakukan perencanaan dalam pembuatan program atau aplikasi.
2.
Prototyping Dalam tahapan ini, secara berkala akan saling berdiskusi dan memberikan feedback langsung kepada developer. Tahapan ini dibagi menjadi dua proses: a.
User Design Proses dalam membangun interface yang diharapkan bisa membantu memudahkan pengguna dalam menggunakan aplikasi.
b.
Construction Proses dalam membangun logika aplikasi agar hasil yang diharapkan dari user bisa tersampaikan dan membantu user untuk mendapatkan hal yang diinginkan.
3.
Cutover M erupakan tahap akhir, dengan melakukan testing dan implementasi akhir. Tahapan ini juga biasanya diisi dengan pelatihan bagi para pengguna aplikasi, disertai dengan pemeliharaan aplikasi (maintenance).
