PERANCANGAN SISTEM PENJADUALAN PERKULIAHAN MENGGUNAKAN ALGORITMAGENETIK Samuel Lukas*, Sutrisno", Lutfia Rachman"*
Abstract Timetabling problem is a kind of complex problem. There are some resources that need to be scheduled and they should fit with all set unique conditions. Moreover, the schedule should be an optimum solution of the case. There are some resources to be allocated such as lecturers, facilities (classrooms), time, and subjects. The conditions that should be accommodated consist of two kind, hard constraints and soft constraints. The hard constraints such as the relationship between lecturers and the subjects, classroom availability, time availability whereas the soft constraints are the relationship among all subjects, the total number of subjects scheduled in a day, the total number of credit tought by one lecturer in a week. This paper discusses how the genetic algorithm can optimize the schedule with the objective of maximizing the number of classrooms used.
1. Latar Belakang Kebutuhan akan kualitas sumber daya manusia di Indonesia semakin meningkat dan diperlukan dalam berbagai bidang sehingga membutuhkan suatu kreativitas dan ilmu pengetahuan yang tinggi. Salah satu sarana yang mendukung adalah melalui bidang pendidikan. Namun proses pendidikan tidak akan berjalan secara maksimal tanpa didukung oleh sistem pengaturan dan pengajaran yang ada. Oleh karena itu dalam pencapaiannya dibutuhkan suatu dukungan dan motivasi dari para pengajar (pembimbing) yang berkualitas dan bermutu tinggi. Proses pendidikan yang baik sudah tentu memiliki penjadualan perkulihan yang baik, karena pada penjadualan perkuliahan seluruh interaksi antara dosen dengan mahasiswa akan dimulai. Permasalahnya adalah banyak batasan dalam penjadwalan ini untuk dapat mengakomodasi seluruh kepentingan. Perkembangan Teknologi Informasi yang pesat mendorong terbentuknya algoritma pemecahan masalah. Salah satunya adalah algoritma genetik. Algoritma ini mampu memecahkan banyak masalah yang relatif komplek. Pada makalah ini akan disajikan bagaimana perancangan sistem penjadualan perkuliahan dapat diterapkan. 2. Ruang Lingkup Pembahasan Sistem Sistem penjadualan perkuliahan yang dirancang mengikuti sistem dimana bagian administrasi melakukan pemasukan data nama-nama mata kuliah yang akan dijadualkan beserta besar sistem kredit semesternya (sks), ketersediaan ruangan ' Dosen Tetap Jurusan Teknik Informatika, FIK UPH " Dosen Tetap Jurusan Sistem Informasi, FIK UPH *" Alumni Jurusan Teknik Informatika, FIK UPH Perancangan Sistem Penjadualan ... (S. Lukas, Sutrisno, R.Rachman)
199
yang akan digunakan, ketersediaan waktu dosen untuk mengajar, ketersediaan dosen untuk mengajar suatu matakuliah. Secara otomatis sistem akan melakukan pencarian penjadualan terbaik dengan batasan: • Jika ada dua jenis matakuliah yaitu matakuliah tatap muka dan matakuliah laboratorium, maka masing-masing matakuliah tatap muka dan laboratorium dianggap sebagai matakuliah yang berbeda • Maksimum sks tatap muka untuk satu matakuliah adalah 3 yang terjadual satu kali dalam satu minggu selama 150 menit. • Sistem berlaku hanya untuk satu kelas. • Sistem penjadwalan ini menggunakan bahasa pemrograman Visual Basic. 3. Perancangan Umum Sistem Penjadualan Sistem Penjadualan menerima 3 masukan data yaitu matakuliah dan sks, ketersediaan dosen dan ketersediaan ruangan, ditambah dengan satu himpunan data batasan sistem dan satu himpunan hubungan dosen dengan matakuliah. Sistem penjadualan digambarkan pada blok diagram gambar 1. Batasan
Matakuliah & sks Ketersediaan Dosen
A PROSES PENJADUALAN PERKULIAHAN
"^
Jadual Perkuliahan
Ketersediaan Ruang
T Hubungan Dosen rlenpan Matakuliah Gambar 1. Blok Diagram Sistem Penjadualan
Data matakuliah dan sks adalah suatu tabel matakuliah yang berisi field kode matakuliah, field nama matakuliah, field sksnya, field jumlah kelas yang akan dibuka dan field terjadual. Ketersediaan dosen adalah tabel dosen yang berisi field kode dosen, field nama dosen, field ketersediaan slot waktu yang diberikan dosen luar biasa untuk mengajar matakuliah, field jumlah sks maksimum, field terjadual. Untuk dosen biasa maka ketersediaan waktu adalah sepanjang waktu perkuliahan yang dioperasikan. Sedangkan ketersediaan ruangan adalah tabel ruangan yang berisi field kode ruang, nama ruang, kode slot. Himpunan data batasan sistem adalah sekumpulan aturan yang membatasi penjadualan itu sendiri. Batasan itu bisa yang hard constraints atau soft constraints. Batasan hard constraints dinyatakan sebagai berikut: • Tidak boleh ada ketumpangtindihan waktu mengajar dosen, ruang mengajar dosen dan matakuliah yang diajar dosen. • Tidak boleh ada dosen yang beban SKS-nya melebihi maksimal yang ditentukan. Soft contraints dikategorikan sebagai berikut: • Setiap dosen luar biasa jumlah sks mengajarnya dalam satu minggu maksimum 8 sks. • Perubahan terhadap mata kuliah, dosen pengajar dan ruangan sebagai data masukan (input) awal sistem (masukan (input)) dapat diatur oleh pengguna algoritma secara bebas (disesuaikan dengan kebutuhan). 200 Jurnal llmiah llmu Komputer, Vol. 3 No. 3 September 2005: 199-207
3.1
Sistem Pengkodean
Satu jadual perkuliahan terdiri dari 50 slot waktu perminggu dengan 5 hari kerja. Jadi satu hari kerja tersedia 10 slot waktu yang dimulai dari jam 7.30 dan berakhir jam 15.50. Satu slot waktu adalah 50 menit. Khusus untuk hari jumat slot waktu jam 10.50 sampai dengan 13.20 tidak diperkenankan untuk waktu kuliah. Pengkodean untuk satu jadwal ini terdiri dari 50 bit biner. 10 bit biner pertama merepresentasikan 10 slot waktu pada hari senin, 10 bit berikutnya masing-masing merepresentasikan slot-slot pada hari selasa, rabu dan kamis hingga 10 bit terakhir merupakan representasi dari 10 slot waktu pada hari jumat. Satu slot waktu hanya bernilai 1 atau 0. Slot itu menyatakan matakuliah apa yang diajar oleh dosen siapa dan menempati ruang yang mana. Oleh karena itu sebelum slot itu ditentukan bernilai 1 atau 0 maka slot itu terdiri dari 6 digit angka. Dua digit pertama adalah kode untuk nama matakuliah, dua digit berikutnya adalah kode untuk nama dosen pengajar sedangkan dua digit berikutnya adalah kode untuk nama ruangan. Slot waktu bernilai 1 apabila ke enam digit memenuhi batasan sistem. Jika kode matakuliah dengan kode dosennya dapat memenuhi persyaratan pada hubungan dosen dengan matakuliah serta kode ruangan pada slot itu kosong maka pada slot itu bernilai 1 selain itu maka slot bernilai 0. Gambar 2 dan gambar 3 memperlihatkan bentuk kromosom umum dan kromosom binernya
KrVSIot K,
1 114111
4 132713
3
2 114111
5 132713
132713 132713 132713 Gambar 2 : Bentuk kromosom umum
Kpopsize
KrtSlot K,
1 1
2 1
3 0
4 1
5 1
6 1
K'popsize
o
0
1
1
1
0
I ... I
49 181415
6 132713
| ... | 114111
50 181415 114111
49 1
50 1
1
1 | 30 | 0.6 Total Fitness = 11,44908
X 39
Fitness 0.78
Gambar 3 : Bentuk kromosom biner
3.2
Algoritma Pembentukan Satu Kromosom
Satu kromosom merepresentasikan satu jadual perkuliahan untuk satu kelas. Mengikuti sistem pengkodean diatas maka satu kromosom terdiri dari 50 bit biner. Pembentukan kromosom ini mengikuti algoritma berikut: 1. Bangkitkan satu bilangan random dua digit. 2. Petakan bilangan random itu ke kode matakuliah dan tentukan kode matakuliah yang bersesuaian dan ambil sksnya. 3. Bangkitkan satu bilangan random dua digit. __ 4. Petakan bilangan random itu ke kode dosen dan tentukan nama dosen yang bersesuaian sesuai dengan kode dosen. 5. Bangkitkan satu bilangan random dua digit. 6. Petakan bilangan random itu ke kode ruangan dan tentukan ruangan yang bersesuaian sesuai dengan kode ruangan. 7. Gabungkan kode matakuliah, kode dosen dan kode ruang menjadi 6 digit angka. Perancangan Sistem Penjadualan ... (S. Lukas, Sutrisno, R.Rachman)
201
8.
Berikan nilai slot waktu jadual sama dengan 1 apabila kode 6 digit angka memenuhi batasa sistem selain itu berikan nilai slot waktu jadual sama dengan 0. 9. Jika nilai slot waktu jadual = 1 maka Ubah parameter field database matakuliah dan sks, dosen dan ruang seperlunya 10. Ulangi dari langkah 1 sampai ke slot 50 terisi Langkah 1 hingga 7 dilakukan untuk mendapatkan 6 digit angka yang terdiri dari kode matakuliah, kode dosen dan kode ruangan. Langkah ke 8 untuk menentukan apakah slot waktu jadual pada saat itu valid atau tidak Slot waktu jadual valid apabila ia memenuhi seluruh batasan yang ada. Parameter field database matakuliah dan sks yang perlu diubah adalah field terjadual. Field ini harus ditambah dengan 1. Nilai field ini harus tidak lebih besar dari nilai yang dinyatakan pada field jumlah kelas yang akan dibuka. Field pada tabel dosen yang berubah adalah field terjadual. Nilai Field ini harus ditambah dengan jumlah sks matakuliah terpilih. Jumlah sks terjadual harus tidak lebih besar dari nilai yang dinyatakan pada field jumlah sks maksimum. Field pada tabel ruang yang berubah adalah field slot. Nilai field ini menjadi sama dengan slot waktu terjadual yang menandakan bahwa ruang itu telah terisi. 3.3
Penentuan Fungsi Fitness
Penentuan nilai fitness setiap individu ditentukan dengan menghitung jumlah slot waktu jadual(Sw) yang bernilai 1 dibagi dengan jumlah slot waktu jadual maksimum. 50
fl Terjadual Sw = { (0 Tidak _Ter-jadual 3.4
dan
~\ ' Fitness^— 50
(1)
Mekanisme penjadualan
Sistem penjadualan dimulai dengan membangkitkan satu populasi awal yang terdiri dari sejumlah kromosom. Algoritma penjadualan sebagai berikut 1.
Bangkitkan populasi awal sebanyak P kromosom dan hitung nilai fitness setiap kromosom. 2 Lakukan penseleksian kromosom induk sebanyak Q buah dengan nilai probabilitas penyilangannya yaitu PS. Q- PSxP 3. Lakukan mutasi gen sebanyak M dengan nilai probabilitas mutasinya adalah PM. M = PM x P x 50 4. Ulangi langkah 2 dan 3 hingga dicapai generasi yang diharapkan 5. Pilih kromosom dengan nilai fitness terbaik yang merupakan jadual yang terbaik.
202 Jurnal llmiah llmu Komputer, Vol. 3 No. 3 September 2005: 199-207
Bagan arus sistem penjadualan diperlihatkan pada gambar 4 Bangkitkan populasi awal Bangkitkan populasi baru
Seleksi
\r Rekombinasi V Mutasi
Tidak
Jadual
Gambar 4 : Bagan Arus Sistem Penjadualan
Populasi awal dibentuk dengan membangkitkan sejumlah kromosom sebanyak P (Ukuran populasi) dengan melakukan penguiangan algoritma pembentukan kromosom sebanyak P kali. Metoda seleksi yang digunakan adalah roda roulette. Metoda ini merupakan metoda seleksi yang paling sering digunakan karena proses seleksi yang sederhana. Adapun algoritmanya untuk satu kali pemilihan adalah sebagai berikut: 1.
Hitung total fitness (FT):
2.
Hitung fitness relatif tiap kromosom (FR): FR(i) •. Fitness(i) FT Hitung fitness kumulatif (FK): FK(I) = FK(I -1) + FR(I) dan FK(N) = 1 Pilih kandidat kromosom sebagai kromosom induk dengan membangkitkan bilangan acak R. Kandidat kromosom induk terpilih adalah kromosom yang memiliki FKyang paling menekati R.
3. 4.
FT
= JT Fitness(i)
Perancangan Sistem Penjadualan ... (S. Lukas, Sutrisno, R.Rachman)
203
Rekombinasi (Crossover) dilakukan atas 2 kromosom untuk menghasilkan kromosom anak (offspring). Kromosom anak yang terbentuk akan mewarisi sebagian sifat kromosom induknya. Metode crossover yang paling sering digunakan dengan kromosom berbentuk string biner adalah crossover satu titik (one point crossover). Pada metode ini, pilih satu bilangan acak antara satu sampai jumlah gen dalam 1 kromosom untuk menentukan posisi persilangan. Kemudian kita tukarkan bagian kanan titik potong dari kedua induk kromosom tersebut untuk menghasilkan kromosom anak. Selain gen kromosom biner, proses crossover juga dilakukan pada gen kromosom umumnya sesuai dengan data binernya. Proses satu kali crossover adalah sebagai berikut: 1. Tentukan dua buah kromosom induk dan bangkitkan satu bilangan random bulat S yang terletak diantara 1 sampai dengan jumlah gen dalam kromosom (50). 2. Semua gen pada kromosom induk yang nomor posisinya lebih kecil dari S menjadi gen pada kromosom anak pertama pada posisi yang sama. Gen pada kromosom anak pertama lainnya (nomor posisi gennya lebih besar atau sama dengan S ) sama dengan gen pada kromosom induk kedua pada posisi yang sama. Untuk gen pada kromosom anak kedua dilakukan seperti anak pertama dan diperlihatkan pada gambar 5. Kromosom induk K1' K2'
1 132721 1 181415
o 1 181415
1 144224 1 144012
1 ,144224 0
0
.
If 0
0 I
0
0
.—,
1 144224
,
1 181415 1 144224
Dengan S = 4 maka didapat kromosom anak sebagai berikut K1" K2"
'1 132721 1 181415
0 1 181415
!
1 144224 1 144012
1 144224 0
0
0
0
0
1 144224 0
—
1 144224 1 181415
Gambar 5 : Proses penyilangan dengan satu titik penyilangan
3.
4.
Lakukan pengecekan ulang atas gen kromosom anak pertama yang nomor posisinya lebih besar atau sama dengan S yang bernilai 1. Harus dapat dipastikan bahwa gen biner yang bernilai 1 adalah juga benar untuk gen umumnya. Sebagai contoh gen umum kromosom anak pertama 144224 yang posisinya lebih dari S, diuji apakah ia valid di posisi itu, jika tidak maka gen umumnya harus diubah sehingga menjadi valid. Untuk itu maka lakukan langkah 3.2 dari langkah pertama hingga langkah ke 9. Lakukan langkah ke tiga untuk anak kedua.
Mutasi yang digunakan adalah dengan teknik acak. Pada dasarnya akan mengubah secara acak nilai suatu gen pada posisi tertentu. Kemudian mengganti gen 1 dengan 0, atau mengganti gen 0 dengan 1. Gen pada posisi dan pada kromosom yang mana ditentukan dari bilangan acak yang dibangkitkan. Banyaknya bilangan acak yang dibangkitkan (M) sangat ditentukan dengan nilai probabilitas mutasi yang dipilih (PM). Selain gen biner pada proses mutasi dilakukan juga pada gen umumnya sesuai dengan data binernya. Proses satu kali mutasi adalah sebagai berikut: 204 Jurnal llmiah llmu Komputer, Vol. 3 No. 3 September 2005: 199-207
1.
Bangkitkan bilangan acak M1 yang besarnya antara 1 sampai dengan K dimana K = P*50 2 Dari M1, tentukan kromosom yang akan mengalami mutasi dan tentukan gennya yang bermutasi. Kromosom yang bermutasi adalah yang ke I dimana I = 1 + M1 div 50 dan gennya adalah gen yang ke J (J = M1 mod 50). 3. Jika gen bernilai 1 maka ubah menjadi 0 dan gen umumnya dikosongkan. Jika tidak maka gen binernya berubah menjadi 1. Gen umumnya diisi dengan mencari dosen dan matakuliah yang sesuai dengan waktu yang direpresentasikan dengan posisi gen itu. 4. Implementasi Sistem dan Bahasan Sistem diimplementasikan IT dengan rancangan menu seperti diperlihatkan pada Gambar 6 sebagai berikut
1
. i a ii s a s,
«—, i _ Mil* ubah
[
MaWlanri Ruang
1
Down
1
PanHa|aa>
MM Klilah
>*»'
MT.HHM.H UMhtn
r»n r a n riH» r«mi r M *
•
t"l""l"
I'M*
>P
.7.
rwi r»»« »»*» m i v«<
MM...... -
>' w * i"
MM
I ' M ''an*
r m* t~M* " wa r M
r •"»
1 P"_JL «*•*•» 1 I l * » * I
*«* , 1
U T H
9M*
; *•
F
Utti
CM*
-•>•*
rM* r a i
BM« WM*
1 »a
» * r a n ." *m : MM
* ana r M l "W) f M l
i| ;ntin
M* r M« ' M*
;
| 8MM '
«n» |
•MaalMg &<
a) Gambar Menu Inisialisasi Matakuliah
act
|
s.u*
]
b) Gambar Menu Inisialisasi Ruangan
L-_; ir^n S ~C 1 «— 1 !
c) Gambar Menu Inisialisasi Dosen
d) Gambar Menu Pengajaran i
,
•*•»«* [
Dal*
uvurw Populm ;r.),iiij*> ProMMHiK Crotiover (Pc) WrMMbHitn xhilMI l*Tn) Prc6*W1H*Pal*il*r!»MPI) IWllmiTi G*fl.T*ll
0Ua*
• N M M B B L 7 7 ! U H BBBBBBBl BBBBBBI
MtRvwaaw
nsn n^n rj£D rjr-j [jSD
n
Jiirilati Pupiiavl dflani talu | « n r . l
,!
*-' *-'
b.1»
•
»
;1
1
"""75)
Nilal M M M 30. {mMt HO)
£'.'.-
! a.»i
If*
1 . It" 1 1 •**' I e) Gambar Menu Parameter Genetika
*'**
•
•
—__'__"—-' !""! 45S
S'UMMl
,"„'
~rzr-
|f
j
—— ' 1 ii• ]I
EopAwW || MacMd j | frouOver i!
Mutatl
| Palaitarlan, | Qui Rawll |
Hdi
_J
•* -
VS
"
' ]'
HBrt
i
&ekMf
j
f) Gambar Menu Pemrosesan
Gambar 6 : Seluruh rancangan menu penerapan sistem
Perancangan Sistem Penjadualan ... (S. Lukas, Sutrisno, R.Rachman)
205
Setiap langkah pada sistem penjadualan ini diperlihatkan dengan tambahan tombol pelestarian sistem untuk memastikan bahwa kromosom terbaik akan tetap bertahan di generasi berikutnya. Parameter pelestarian ini dinyatakan dengan simbol PL yang menyatakan probabilitas populasi terbaik yang akan tetap bertahan pada generasi berikutnya. Sistem diuji coba dengan percobaan pertama untuk melihat pengaruh jumlah populasi dalam setiap generasi dengan parameter PS = 0.45, PM = 0.01 dan PL = 0.2 maka didapat hasil percobaan pada gambar 6. Terlihat bahwa makin besar jumlah populasi maka untuk mencapai penjadualan terbaik makin dibutuhkan jumlah generasi yang semakin kecil. Akan tetapi waktu yang dibutuhkan untuk mencapai keadaan optimum berbanding lurus dengan jumah populasinya.
Gambar 6a : Jumlah Populasi versus Jumlah generasi
Gambar 6b : Jumlah Populasi vs Waktu
Apabila peluang penyilangan djadikan variabel bebas dengan variabel lainnya dipegang tetap PM = 0.01, PL = 0.2 dan P = 100 dengan jumlah generasi maksimum 100 maka didapat gambar 7 berikut. Our* Panaaiuh N H « W
PaluanB Cnxaovar Ipcl B«aa*wtw> O M M I U
Gambar 7a : Peluang penyilangan versus Jumlah generasi
Of*'* Paaaanih Paiaaiawr Pitnaa Cnuovw |p«| a . . • • . » » . . waaiu
Gambar 7b : Peluang penyilangan versus Waktu
Dari hasil simulasi di atas terlihat bahwa semakin besar jumlah peluang crossover (Pc) maka hasil yang optimal diperoleh pada generasi yang semakin kecil demikian juga dari sisi waktu yang dibutuhkan. Hasil ini sesungguhnya tidak terlalu mengejutkan mengingat makin besarnya peluang penyilangan maka makin banyaknya kemungkinan baru yang timbul dari hasil penyilangan sehingga memungkinkan terbentuknya kondisi maksimal yang makin cepat.
206 Jurnal llmiah llmu Komputer, Vol. 3 No. 3 September 2005: 199-207
Percobaan selanjutnya dilakukan dengan menjadikan peluang mutasi sebagai variabel bebasnya dari 0.01 s/d 0.1 dan hasilnya memperlihatkan bahwa semakm besar peluang mutasi (PM) maka hasil optimal yang diperoleh pada jumlah generasi yang makin besar dan waktu pencapaian semakin lambat. Hal ini disebabkan karena makin besarnya peluang mutasi maka makin besar pula peluang ketidak stabilansisem sehingga memperlambat pencapaian hasil optimal. Percobaan terakhir dengan menjadikan peluang pelestarian sebagai variabel bebas dari 0.05 dengan step 0.05 hingga 0.50 maka didapat kesimpulan bahwa semakin besar peluang pelestarian maka semakin kecil jumlah generasi yang dibutuhkan untuk mecapai kondisi optimal demikian juga waktu pencapaiannya. Hasil ini cukup rasional mengingat makin besarnya peluang pelestarian berarti makin besar pula peluang kromosom terbaik pada setiap generasi terpilih pada generasi berikutnya. 5. KESIMPULAN DAN SARAN Dalam proses penjadwalan terdapat beberapa parameter yang penting dalam pencapaian solusi yang optimal dengan waktu yang efisien. Parameter yang dimaksud adalah popsize, peluang crossover, peluang mutasi dan peluang pelestarian yang masing-masing memiliki peranan yang berbeda. Sistem penjadwalan ini dapat menghasilkan suatu jadwal yang optimal atau beberapa kombinasi jadwal yang optimal yang dipengaruhi oleh penggunaan parameter dan data masukan (input) yang ada (data mata kuliah, data dosen dan data ruangan). Hasil optimal didapat dengan melakukan beberapa kali percobaan dengan mengubah keempat variabel bebasnya secara terstruktur. Daftar Pustaka [1] Chipperfield Andrew; Peter Fleming; Hartmut Polheim; dan Carlos Fonseca. Genetic Algorithm, 1994. [2] Frenzel, L.W., Artificial Intelligence and Expert System. 1 st Edition.USA: Howard W. Sams & Co. 1987. [3] Jeff S Smith, What Are Genetic Algorithms (GAs)?, http://www.softtechdesiqn.com/, 2002. [4] Packard, N. (1990). A genetic learning algorithm for the analysis of complex data. Complex System, 4, pp.573-586. [5] Pearl, Judea, Heuristics: Intelligent Search Strategies for Computer Problem Solving, Addison-Wesley Publishing Company, Reading, Massachusettes, 1984. [6] Robert Setiadi dan Anbulagan, Pemecahan Masalah Penjadwalan Kuliah dengan Menggunakan Teknik Intelligent Search, 2001. [7] Smith, Christopher, Course lecture notes from Artificial Intelligence, University of Colorado at Denver, Fall 1999. [8] Sri Kusumadewi, Artificial Intelligence (Teknik dan Aplikasinya), Graha llmu, 2002. [9] Lewis, John B., The Auraria Campus Scheduling Algorithm, http://ouray.cudenver.edu/~jblewis/csc5811/final.htm, 2000.
Perancangan Sistem Penjadualan ... (S. Lukas, Sutrisno, R.Rachman)
207
