AUTOMATISASI TIMETABLING ASISTEN PENGAJAR PADA SOFTWARE LABORATORY CENTER MENGGUNAKAN HARMONY SEARCH Niko Sutiono Binus University, Jakarta, DKI Jakarta, Indonesia
Ngarap Immanuel M anik Binus University, Jakarta, DKI Jakarta, Indonesia
Rojali Binus University, Jakarta, DKI Jakarta, Indonesia
ABSTRAK Proses penjadwalan asisten pengajar yang dijalankan unit lembaga ini, masih memerlukan waktu yang cukup lama dengan batasan-batasan yang cukup banyak untuk dipenuhi. Hal ini menyebabkan tingginya tingkat human error, yang mengakibatkan kurangnya efisiensi waktu selama proses penjadwalan terjadi. Tujuan dari penulisan skripsi ini adalah untuk membantu menyelesaikan masalah pada proses penjadwalan tersebut, dengan membuat sebuah program sederhana untuk membantu menjalankan algoritma harmony search. Proses algoritma ini dibagi menjadi lima tahapan, yaitu: melakukan inisialisasi parameter permasalahan dan parameter algoritma, melakukan inisialisasi harmoni memori awal, generate harmoni baru, update harmoni memori, dan pengecekan kondisi berhenti. Algoritma ini digunakan untuk mengoptimalkan nilai objektif dari hasil penjadwalan, yang didapatkan dari hasil formulasi model optimasi untuk setiap harmoni memori. Kondisi optimal didapatkan bila nilai objektif yang didapat dari model optimasi adalah minimal. M odel optimasi menggunakan harmony search ini diharapkan dapat membantu proses penjadwalan dalam efisiensi waktu dan mengurangi human error.
Kata Kunci: penjadwalan, algoritma, harmony search, model optimasi
1.
Pendahuluan Berkembangnya sebuah perusahaan sangat dipengaruhi dari kemampuan mengatur
dan mengolah operasional perusahaan tersebut, salah satunya adalah penjadwalan, terutama dalam penjadwalan menggunakan sumber daya yang ada. Dalam proses penjadwalan itu sendiri biasanya menghabiskan waktu yang cukup lama, hal ini disebabkan karena batasan-batasan (constraints) yang harus diperhatikan cukup banyak untuk mendapatkan jadwal yang sesuai dan diinginkan. Untuk masalah penjadwalan ini yang lebih dikenal dengan University Timetabling Problem (UTP), sebelumnya sudah banyak diteliti dan dikembangkan dengan menggunakan beberapa metode dan algorima, seperti pada pemecahan masalah tentang penjadwalan perkuliahan menggunakan algoritma genetik (Wijaya & M anurung, 2009) dan aplikasi algoritma genetik untuk optimasi penjadwalan (Nugraha, 2008). Adapun pemecahan masalah penjadwalan ini dikembangkan dan diteliti lebih lanjut oleh Geem, dengan menggunakan pengembangan pada evolutionary algorithm, sehingga ditemukan algoritma harmony search(Geem, Kim, & Loganathan, 2001). Dengan menggunakan algoritma baru ini, Geem sudah menerapkannya dalam berbagai aplikasi, diantaranya perancangan struktur (Geem, 2004), perencanaan bus sekolah (Geem, 2005), dan game sudoku (Geem, 2007). Penelitian oleh Geem ini masih dikembangkan dan diteliti oleh para akademisi dari berbagai penjuru dunia. Permasalahan yang dihadapi dalam melakukan penjadwalan ini adalah bagaimana membuat penjadwalan asisten pengajar yang otomatis, yang bisa menghemat waktu, dan memenuhi batasan-batasan dalam penjadwalan, serta adanya penyebaran bobot yang merata untuk setiap asisten pengajar.
2.
Metodologi
2.1. Metode Penelitian Dalam melakukan penelitian akan permasalahan ini, penulis menggunakan metode rapid application development (RAD), dengan alur pengerjaan sebagai berikut:
G ambar 1 Proses pengerjaan penelitian
Pada gambar dapat dilihat langkah-langkah yang dilakukan penulis dalam melakukan pengumpulan data dan pengerjaan disesuaikan dengan metode pengerjaan yang
digunakan. Proses pemilihan topik, mencari dan memahami makalah-makalah yang relevan, dan mengumpulkan data-data penjadwalan termasuk dalam Requirement and Planning. Proses diskusi dengan tim Resources M anagement, membuat model matematika optimasi, dan membuat aplikasi dari model matematika yang telah dibuat termasuk dalam Prototyping. Proses penerapan aplikasi dan memperbaiki kekurangankekurangan program termasuk ke dalam Cut Over. Bila dilihat maka ada sedikit pengembangan metode RAD yang diterapkan, ini disebabkan jenis prototype yang digunakan dalam melakukan penelitian ini adalah model matematika. Penulis merasa perlu untuk memasukkan pembuatan model matematika ke dalam proses prototyping, karena model matematika yang digunakan nantinya diharapkan bisa dikembangkan untuk aplikasi-aplikasi penjadwalan lainnya. Dalam pemrograman matematika, model matematika yang valid bisa memberikan gambaran secara umum proses algoritma yang dilakukan dalam aplikasi, hal ini juga yang membuat penulis memasukkannya ke dalam bagian prototyping. 2.2. Inisialisasi Batasan Dari proses mengumpulkan data-data penjadwalan dan diskusi langsung dengan tim Resources M anagement, Dalam membuat penjadwalan penugasan asisten, ada beberapa hal yang perlu diperhatikan sebagai hard constraint, antara lain: 1.
Asisten pengajar mengajar matakuliah praktikum yang sudah dikuasainya, sesuai dengan data kualifikasi yang ada. (H1)
2.
Asisten pengajar tidak diperbolehkan mengajar diluar shift kerja yang sudah ditetapkan. (H2)
Batasan-batasan di atas harus dipenuhi dalam penjadwalan yang dibuat, bila ada salah satu di antara hard constraint ini dilanggar, maka jadwal tidak bisa digunakan dan harus digenerate ulang. Beberapa batasan tambahan yang perlu diperhatikan dan terhitung sebagai soft constraint adalah sebagai berikut: 1.
Asisten pengajar diharapkan mengajar tidak lebih dari jumlah variasi yang ditentukan. (C1)
2.
Asisten pengajar diharapkan mengajar tidak lebih dari 2 shift per hari, agar bisa mengerjakan tugas lain yang diberikan. (C2)
3.
Para pengajar diharapkan memiliki bobot tidak lebih dari bobot yang sudah ditentukan. (C3)
Untuk batasan-batasan di atas, merupakan gambaran penjadwalan yang optimal. Batasan ini tidak akan mengganggu operasional secara signifikan bila tidak dipenuhi, namun penjadwalan akan lebih optimal apabila terpenuhi. Fokus dari pembahasan ini adalah untuk meminimalkan soft constraint di atas. 2.3. Inisialisasi Parameter Parameter-parameter dan inisialisasi himpunan yang digunakan dalam algoritma harmony search sebagai berikut: a.
Himpunan
1…
untuk transaksi praktikum semester berjalan.
b.
Himpunan
1…
untuk para pengajar praktikum.
c.
Himpunan
1…
untuk matakuliah praktikum.
d.
Himpunan
1…
untuk ruangan praktikum.
e.
1…
Himpunan
untuk periode dengan 34 slot waktu, yang tersebar
menjadi 6 hari dengan masing-masing hari menjadi 6 shift (kecuali jumat dan sabtu menjadi 5 shift). f.
Himpunan
~
,…,
~
untuk menyatakan hari, dimulai dengan hari
~
senin dan berakhir pada hari sabtu. g.
Subset himpunan ,
~
h.
…,
~
,
~ ~
,…, ,
~
, sehingga bila dijabarkan menjadi
…,
, dan seterusnya.
, , , , adalah jumlah dari transaksi, keseluruhan asisten pengajar, group asisten pengajar, group staff pengajar, matakuliah praktikum, periode praktikum berlangsung.
i.
adalah bobot minimal untuk setiap pengajar ,
j.
adalah bobot maksimal unutk setiap pengajar ,
.
k.
adalah variasi maksimal untuk setiap pengajar ,
.
l.
adalah bobot untuk setiap matakuliah praktikum ,
.
m.
(shift kerja pengajar) adalah variabel biner, bernilai 1 jika dan hanya jika pengajar
n.
available pada periode .
,
.
.
(kualifikasi pengajar) adalah variabel biner, bernilai 1 jika dan hanya jika pengajar
memiliki kualifikasi matakuliah praktikum .
,
.
Dari parameter-parameter di atas, perlu ditentukan juga variabel-variabel keputusan yang nantinya akan mempengaruhi optimasi dari penjadwalan itu sendiri.
2.4. Inisialisasi Variabel Keputusan Untuk mendapatkan optimasi penjadwalan, maka perlu dibuat rumusan dalam meminimalkan nilai pelanggaran softconstraint tanpa melanggar hard constraint. Rumusan yang didapat nantinya akan mengacu pada variabel-variabel keputusan yang ada. Beberapa variabel keputusan untuk batasan-batasan di atas: a.
, ,
adalah variabel keputusan biner yang memiliki indeks berupa transaksi,
matakuliah praktikum dan asisten. Variabel untuk transaksi pengajar . b.
1 , jika dan hanya jika
, ,
dengan matakuliah praktikum ,
,
teralokasikan asisten
.
adalah variabel keputusan yang memiliki indeks berupa asisten. Variabel ini menandakan terjadinya pelanggaran pada batasan C1. Variasi yang ada pada C1, disesuaikan dengan pemerataan dan kesanggupan pengajar, ditentukan oleh tim Resources M anagement.
c.
.
adalah variabel keputusan yang memiliki indeks berupa asisten. Variabel ini menandakan terjadinya pelanggaran pada batasan C2.
d.
.
adalah variabel keputusan yang memiliki indeks berupa asisten. Variabel ini menandakan terjadinya pelanggaran pada batasan C3. Bobot yang ada pada C3, disesuaikan dengan pemerataan dan kesanggupan pengajar, ditentukan oleh tim Resources M anagement.
e.
,
.
adalah variabel keputusan biner yang memiliki indeks berupa transaksi
dan periode. Variabel periode .
,
,
.
1, jika dan hanya jika transaksi
ada pada
2.5. Formulasi Fungsi objektif yang akan digunakan untuk mendapatkan optimasi jadwal asisten pengajar adalah: 1 min Fungsi (1) meminimalkan pelanggaran-pelanggaran pada soft constraint C1, C2, C3. Setiap pelanggaran pada soft constraint akan mendapatkan nilai 1 sebagai nilai penalti. Untuk setiap nilai dari pelanggaran soft constraint didapatkan dari: 2
,
3
,
, ,
,
, ,
2
~
1, 4
,
, ,
1,
, ,
0, Fungsi (2), untuk melakukan pengecekan variasi pada masing-masing asisten, dengan menghitung pada jumlah jenis matakuliah yang berbeda. Fungsi (3), untuk melakukan pengecekan jumlah event untuk setiap pengajar per hari. Fungsi (4), untuk melakukan pengecekan terhadap pelanggaran bobot asisten pengajar. Fungsi objektif dan fungsi yang mewakili soft constraint di atas bersifat optimasi. Untuk bisa menjalankan fungsi objektif dan fungsi optimasi, ada beberapa fungsi yang
mewakili persyaratan utama (hard constraint) dan harus dipenuhi terlebih dahulu. Untuk fungsi yang harus dipenuhi dan mewakili hard constraint didapatkan dari: 5
,
6
,
7
,
1
, ,
1
, ,
,
, ,
1
Fungsi (5), untuk menyatakan penjadwalan sudah utuh dan semua transaksi sudah teralokasikan pengajar. Fungsi (6), untuk menyatakan pengajar yang sudah dialokasikan sesuai dengan kualifikasi yang terdata. Fungsi (7), untuk menyatakan pengajar available pada periode terjadinya transaksi. 2.6. Hasil Penerapan Algoritma Pembahasan untuk penerapan algoritma harmony search yang dilakukan dalam penjadwalan asisten ini, akan dijabarkan dengan ulasan hasil dari inputan parameterparameter yang berbeda. Untuk hasil penjadwalan, dapat dipastikan berbeda dari percobaan yang pertama hingga yang terakhir walaupun parameter yang diinput sama, hal ini karena adanya random value yang digunakan dalam algoritma. Untuk hasil-hasil yang dijabarkan di sini, adalah hasil-hasil selama penulis melakukan percobaan. Dari hasil inisialisasi matriks penampung yang dibaca dari file excel, ada beberapa parameter tetap yang perlu diketahui: 1.
81.
adalah jumlah asisten pengajar untuk dialokasikan.
26.
2.
adalah jumlah ruangan praktikum yang tersedia untuk alokasi transaksi
praktikum. 35.
3.
adalah jumlah periode yang digunakan dalam transaksi praktikum.
Untuk tiga tetapan di atas, akan digunakan secara konstan dalam melakukan algoritma penjadwalan ini. Dalam melakukan implementasi untuk pengujian algoritma ini pada program, akan dilakukan secara bertahap dan terbagi menjadi tiga langkah utama: 1.
Konversi raw data ke matriks penampung
Langkah ini akan mengubah data-data mentah (raw data) yang didapatkan dari tim Resources M anagement dan Database Administrator menjadi data olahan dasar, berupa matriks biner 0,1 dan bipolar
1,1 .
Contoh data mentah untuk data kualifikasi yang akan diolah datanya dilampirkan pada lampiran. Berikut sample yang diambil untuk keterangan:
G ambar 2 Contoh raw data kualif ikasi
Keterangan: a.
Kolom “A” mewakili asisten pengajar.
b.
Setiap kolom mewakili kode-kode matakuliah yang dilayani oleh Software Laboratory Center.
c.
Nilai “Q” menandakan asisten memiliki kualifikasi untuk matakuliah pada kolom yang diwakilinya.
d.
Nilai selain “Q” menandakan asisten tidak memiliki kualifikasi untuk matakuliah pada kolom yang diwakilinya. Pada contoh nilai tersebut adalah “PT”.
Hasil konversi dari data di atas, akan dituliskan dalam file “qualification_t.xlsx”, sebagai contoh:
G ambar 3 Hasil konversi data kualifikasi
Keterangan: a.
Setiap kolom dan baris akan terproyeksi sama seperti data mentah.
b.
Nilai hasil konversi akan berbentuk biner, nilai 1 akan mewakili status “Q”, sedangkan 0 untuk lainnya.
Contoh data mentah untuk data asisten pengajar yang akan diolah datanya dilampirkan pada lampiran. Berikut sample yang diambil untuk keterangan:
G ambar 4 Contoh raw data asisten pengajar
Keterangan: a.
Data yang dibutuhkan ada pada kolom “INISIAL” dan “SHIFT”.
b.
Untuk nilai pada kolom “SHIFT” terdiri dari pagi dan malam.
Hasil konversi dari data di atas, akan dituliskan dalam file “resources_t.xlsx”, sebagai contoh:
G ambar 5 Hasil konversi data asisten pengajar
Keterangan: a.
Kolom “A” mewakili asisten pengajar.
b.
Setiap kolom mewakili periode praktikum yang ada pada transaksi.
c.
Nilai -1 mengindikasikan pada periode tersebut, asisten yang diwakili kolom “A” tidak bisa dialokasikan untuk mengajar, karena asisten yang bersangkutan berada di luar shift kerja.
d.
Nilai 0 mengindikasikan pada periode tersebut, asisten yang diwakili kolom “A” available untuk dialokasikan mengajar. Bila pada tahapan selanjutnya ada alokasi yang terjadi, maka nilai 0 akan berubah menjadi 1 atau 0,5 sesuai dengan bobot matakuliah yang dialokasikan.
Contoh data mentah untuk data transaksi yang akan diolah datanya dilampirkan pada lampiran. Berikut sample yang diambil untuk keterangan:
G ambar 6 Contoh raw data transaksi praktikum
Keterangan: a.
Data dikonversi menjadi matriks dua dimensi dengan Kode M tk sebagai nilai.
b.
Nilai pada kolom ruang, akan menjadi baris. Nilai pada kolom hari dan shift akan menjadi kolom, pada hasil konversi.
Hasil konversi dari data di atas, akan dituliskan dalam file “transaction_t.xlsx”, dan disimpan sebagai matriks
,
, sebagai contoh:
G ambar 7 Hasil konversi data transaksi praktikum
Keterangan: a.
Setiap baris mewakili ruangan praktikum.
b.
Setiap kolom mewakili periode praktikum.
c.
Setiap matakuliah yang diwakili pada nilai matriks, akan terkorespondensi dari data asal.
2.
Inisialisasi HM
Pada langkah ini, data-data hasil konversi yang tersimpan dalam masingmasing excel ([nama_file]_t.xlsx) akan digunakan untuk diisikan pada harmoni memori, yang merupakan matriks cerminan matriks
,
,
. Untuk matriks
,
sendiri merupakan
yang juga hasil konversi data transaksi praktikum, namun
dengan nilai berupa asisten pengajar. Untuk mengisi matriks
,
perulangan sesuai dengan jumlah baris dan kolom pada matriks matakuliah pada matriks
,
, dilakukan ,
. Nila i
digunakan sebagai referensi untuk mendapatkan
asisten yang memiliki kualifikasi matakuliah tersebut dan available pada shift
sesuai dengan kolom pada matriks
,
. Contoh untuk matriks
,
dalam file
excel:
G ambar 8 Contoh matriks
Jumlah matriks
,
, pada file excel
yang dihasilkan akan sebanyak jumlah parameter HM S yang
akan dimasukkan dalam array multi-dimensi, dengan susunan array berupa array 3 dimensi [$HM S][$r][$p]. Bila matriks
,
sejumlah HM S sudah didapatkan, maka dilanjutkan untuk
mendapatkan nilai objektif untuk masing-masing HM . Untuk mewakili nilai objektif, dalam penerapan digunakan variabel tValues yang merupakan array 2 dimensi [$HM S][$penalty]. Untuk $penalty = 0, mewakili penalti untuk batasan C3. $penalty = 1, mewakili penalti untuk batasan C2. $penalty = 2, mewakili penalti untuk batasan C1. Dari hasil tValues yang didapatkan, nilai objektif akan didapat dengan menjumlahkan nilai penalty yang ada untuk masing-masing HM S. ∑ $ 3.
,
1…
.
Improvisasi harmoni baru
Untuk mendapatkan harmoni baru, dilakukan cara yang sama dalam melakukan inisialisasi disertai dengan kemungkinan kondisi pengisian dengan nilai pada harmoni memori yang sudah ada (HM CR), dan nilai neighbourhood pada harmoni memori yang sudah ada (PAR).
Bagian yang penting dalam langkah ini adalah mengupdate data harmoni memori dan nilai objektif dari harmoni memori yang sudah ada dengan nilai objektif harmoni memori baru yang lebih baik. Bila hal ini dilakukan berulan g (dalam hal ini sesuai dengan parameter NI), maka akan ada kemungkinan terjadi perbaikan harmoni memori, maksimal sebanyak NI. Dari semua langkah yang dilakukan dalam menerapkan algoritma, nantinya akan menghasilkan sebuah
dengan nilai objektif yang diharapkan (minimal). Hasil
akhir dari algoritma program yang digunakan dalam membantu penerapan algoritma akan dijabarkan dalam tiga bentuk matriks, matrik , , dan
, dan akan disimpan dalam
sebuah file excel. Berikut akan ditampilkan hasil dari percobaan untuk penjadwalan asisten pengajar dengan menggunakan parameter-parameter HSA dan parameter permasalahan sebagai berikut: HM S = 5, M inimum Weight = 4,5, M aximum Weight = 5,5, Variation M ax = 5, HM CR = 90, PAR = 20, dan NI = 75. Sedikit tampilan hasil dalam file excel:
G ambar 9 Contoh matriks w hasil algoritma
G ambar 10 Contoh matriks t hasil algoritma
G ambar 11 Contoh matriks e hasil algoritma
3.
Simpulan Simpulan yang didapat dari hasil penulisan skripsi ini dalam melakukan
penjadwalan dengan menggunakan algoritma harmony search adalah: 1.
Algoritma harmony searchbisa digunakan untuk membantu menyelesaikan permasalahan pada penjadwalan asistensi di Software Laboratory Center, namun dengan cakupan batasan yang terbatas.
2.
Beberapa batasan yang sudah diselesaikan dalam penulisan ini adalah batasan kualifikasi asisten pengajar dan batasan bekerja pada jam kerja asisten pengajar, dengan mengoptimasikan batasan variasi mengajar, batasan jumlah shift mengajar per hari, dan batasan bobot mengajar asisten pengajar.
DAFTAR PUSTAKA Adriaen, M., Causmaecker, P. D., Demeester, P., & Berghe, G. V. (2006). Tackling the University Course T imetabling Problem with an Aggregation Approach. International Conference on the Practice and Theory of Automated Timetabling, (hal. 330-335). Brno. Al-Betar, M. A., & Khader, A. T . (2009). A Hybrid Harmony Search for University Course T imetabling. Multidisciplinary International Conference on Scheduling: Theory and Application, (hal. 157-179). Dublin. Banowosari, L. Y., & Valentine, V. (2011). University T imetabling Algorithm Considering Lecturer's Workload. International Multi-Conference on Computing in the Global Information Technology. Luxemburg: IARIA. Brownlee, J. (2011). Clever Algorithm: Nature-Inspired Programming Recipes. Melbourne: LuLu. Burke, E., Kingston, J., & Werra, D. D. (2004). Application to Timetabling. Dalam J. Gross, & J. Yellen, The Handbook of Graph Theory (hal. 445-474). Chapman Hall. Geem, Z. W. (2009, October 12). Introduction to Harmony Search (PowerPoint). Dipetik November 20, 2011, dari Harmony Search Algorithm: http://harmonysearch.info/ Geem, Z. W., & Lee, K. S. (2005). A New Meta-heuristic Algorithm for Continous Engineering Optimization: Harmony Search Theory and Practice. Comput. Methods Appl. Mech. Engrg. 194, 3902-3933. Geem, Z. W., Kim, J. H., & Loganathan, G. V. (2001). A New Heuristic Optimization Algorithm: Harmony Search. Simulation, 60-68. Guna wan, A., Ng, K. M., & Ong, H. L. (2008). A Genetic Algorithm for the T eacher Assignment Problem for a University in Indonesia. Information and Management Sciences, 1-16. Irene, H. S., Safaai-Deris, & Hashim, S. Z.-M. (2009). Investigating Constraint-Based Reasoning for University T imetabling Problem. International MultiConference of Engineers and Computer Scientists (hal. 139-143). Hong Kong: IAENG. Kazarlis, S., Petridis, V., & Fragkou, P. (2005). Solving University T imetabling Problem Using Advanced Genetic Algorithms. International Conference on Technology and Automation, (hal. 131-136). Thessaloniki. Mahdavi, M., Fesanghary, M., & Damangir, E. (2007). An Improved Harmony Search Algorithm for Solving Optimization Problems. Applied Mathematics and Computation 188, 1567-1579. Nugraha, I. (2008). Aplikasi Algoritma Genetik Untuk Optimasi Penjadwalan Kegiatan Belajar Mengajar. IF2551 Strategi Algoritmik.
Pinedo, M. (2002). Scheduling: Theory, Algorithm, and Systems. New Jersey: Prentice Hall. Russell, & T aylor. (2009). Operation Management: Along the Supply Chain. International: Wiley. Stevenson. (2009). Operations Management. International: McGraw-Hill. Whitten, J. L., & Bentley, L. (2005). System Analysis and Design Methods (7th ed.). McGrawHill. Wijaya, T ., & Manurung, R. (2009). Solving University Timetabling As a Constraint Satisfaction Problem with Genetic Algorithm. International Conference on Advanced Computer Science and Information Systems . Depok.
