Download - 06550003 Lina Maria Ulfa.ps
i
OPTIMASI PENJADWALAN PERKULIAHAN
MENGGUNAKAN ALGORITMA GENETIKA
(Studi Kasus: JurusanTeknik Informatika
UIN Maulana Malik Ibrahim Malang)
SKRIPSI
Oleh:
LINA MARIA ULFA
NIM. 06550003
JURUSAN TEKNIK INFORMATIKA
FAKULTAS SAINS DAN TEKNOLOGI
UNIVERSITAS ISLAM NEGERI
MAULANA MALIK IBRAHIM MALANG
2011
ii
OPTIMASI PENJADWALAN PERKULIAHAN
MENGGUNAKAN ALGORITMA GENETIKA
(Studi Kasus: JurusanTeknik Informatika
UIN Maulana Malik Ibrahim Malang)
SKRIPSI
Diajukan Kepada:
Fakultas Sains dan Teknologi
Universitas Islam Negeri Maulana Malik Ibrahim Malang
Untuk Memenuhi Salah Satu Persyaratan Dalam
Memperoleh Gelar Sarjana Komputer (S. Kom)
Oleh:
LINA MARIA ULFA
NIM. 06550003
JURUSAN TEKNIK INFORMATIKA
FAKULTAS SAINS DAN TEKNOLOGI
UNIVERSITAS ISLAM NEGERI
MAULANA MALIK IBRAHIM MALANG
2011
iii
OPTIMASI PENJADWALAN PERKULIAHAN
MENGGUNAKAN ALGORITMA GENETIKA
(Studi Kasus: JurusanTeknik Informatika
UIN Maulana Malik Ibrahim Malang)
SKRIPSI
Oleh:
LINA MARIA ULFA
NIM. 06550003
Telah Disetujui,
Malang, 21 September 2011
Dosen Pembimbing I
Ririen Kusumawati, M. Kom
NIP. 197203092005012002
Dosen Pembimbing II
Dr. Ahmad Barizi, MA
NIP. 197312121998031001
Mengetahui
Ketua Jurusan Teknik Informatika
Ririen Kusumawati, M. Kom
NIP. 197203092005012002
iv
OPTIMASI PENJADWALAN PERKULIAHAN
MENGGUNAKAN ALGORITMA GENETIKA
(Studi Kasus: JurusanTeknik Informatika
UIN Maulana Malik Ibrahim Malang)
SKRIPSI
Oleh:
LINA MARIA ULFA
NIM. 06550003
Telah Dipertahankan di Depan Dewan Penguji Skripsi dan
Dinyatakan Diterima Sebagai Salah Satu Persyaratan
Untuk Memperoleh Gelar Sarjana Sains (S.Kom)
Malang, 21 September 2011
Susunan Dewan Penguji: Tanda Tangan
1. Penguji Utama : Syahiduz Zaman, M.Kom ( )
NIP. 197005022005011005
2. Ketua : Ala Syauqi, M.Kom ( )
NIP. 197712012008011007
3. Sekretaris : Ririen Kusumawati, M. Kom ( )
NIP. 197203092005012002
4. Anggota : Dr. Ahmad Barizi, MA ( )
NIP. 197312121998031001
Mengetahui dan Mengesahkan,
Ketua Jurusan Teknik Informatika
Ririen Kusumawati, M.Kom
NIP. 197203092005012002
v
SURAT PERNYATAAN
Saya yang bertanda tangan di bawah ini:
Nama : Lina Maria Ulfa
NIM : 06550003
Fakultas / Jurusan : Sains dan Teknologi / Teknik Informatika
Judul Penelitian : Optimasi Penjadwalan Perkuliahan Menggunakan Algoritma
Genetika (Studi Kasus: Jurusan Teknik Informatika UIN
Malang)
Menyatakan dengan sebenar-benarnya bahwa skripsi saya ini tidak
terdapat unsur-unsur penjiplakan karya penelitian atau karya ilmiah yang pernah
dilakukan atau dibuat oleh orang lain, kecuali yang secara tertulis dikutip dalam
naskah ini dan disebutkan dalam sumber kutipan dan daftar pustaka.
Apabila ternyata hasil penelitian ini terbukti terdapat unsur-unsur
jiplakan, maka saya bersedia untuk mempertanggungjawabkan, serta diproses
sesuai peraturan yang berlaku.
Malang, 21 September 2011
Yang Membuat Pernyataan,
Lina Maria Ulfa
NIM. 06550003
vi
MOTTO
Saya tidak bisa memilih untuk lahir menjadi apa,
tetapi saya bisa memilih ingin mati sebagai apa ...
Bukan seberapa hebatmu,
bukan apa yang kau raih,
tapi apa yang kau beri ....
(Lagu "Setulus Hati")
vii
LEMBAR PERSEMBAHAN
Wahai Dzat Yang Maha Memberi Manfaat,
ini sedikit manfaat yang bisa saya berikan ...
Untuk Ibu, untuk Bapak,
untuk kakak-kakakku
viii
KATA PENGANTAR
Segala puji hanyalah milik Allah SWT, yang telah melimpahkan rahmat-
Nya sehingga penulis dapat menyelesaikan skripsi yang berjudul “Optimasi
Penjadwalan Perkuliahan Menggunakan Algoritma Genetika (Studi Kasus:
Jurusan Teknik Informatika UIN Maulana Malik Ibrahim Malang)” sebagai salah
satu syarat untuk memperoleh gelar sarjana komputer (S. Kom).
Dalam proses penyelesaian skripsi ini terdapat banyak pihak yang
membantu, dan dengan setulus hati penulis ucapkan terima kasih kepada:
1. Prof. Dr. H. Imam Suprayogo, selaku Rektor UIN Maulana Malik Ibrahim
Malang (UIN Maliki Malang).
2. Prof. Dr. Sutiman Bambang Sumitro, SU., DSc. selaku Dekan Fakultas Sains
dan Teknologi UIN Maliki Malang.
3. Ririen Kusumawati, M. Kom, selaku Ketua Jurusan Teknik Informatika UIN
Maliki Malang, sekaligus sebagai Dosen Pembimbing I, yang telah
membimbing penulis dalam menyelesaikan skripsi ini.
4. Dr. Ahmad Barizi M.A, selaku Dosen Pembimbing II atas bimbingan dalam
menyelesaikan skripsi ini.
5. Seluruh Dosen Jurusan Teknik Informatika UIN Maliki Malang, atas ilmu dan
segala hal yang membuat kami menjadi lebih berani menatap masa depan.
6. Teman-teman Jurusan Teknik Informatika UIN Maliki Malang khususnya
angkatan 2006 Kelas A, dan teman-teman asisten lab.
7. Semua pihak yang telah membantu dalam penyelesaian skripsi ini.
Penulis menyadari bahwa dalam penyusunan skripsi ini masih terdapat
kekurangan dan penulis berharap semoga skripsi ini bisa memberikan manfaat
kepada para pembaca khususnya bagi penulis secara pribadi.
Malang, September 2011
Penulis
ix
DAFTAR ISI
HALAMAN JUDUL ..................................................................................... i
HALAMAN PENGAJUAN .......................................................................... ii
HALAMAN PERSETUJUAN ...................................................................... iii
HAMALAN PENGESAHAN ...................................................................... iv
SURAT PERNYATAAN .............................................................................. v
MOTTO ....................................................................................................... vi
LEMBAR PERSEMBAHAN ...................................................................... vii
KATA PENGANTAR ................................................................................... viii
DAFTAR ISI ................................................................................................. ix
DAFTAR TABEL ......................................................................................... xii
DAFTAR GAMBAR ..................................................................................... xiii
ABSTRAK ..................................................................................................... xv
BAB I PENDAHULUAN .............................................................................. 1
1.1. Latar Belakang ......................................................................................... 1
1.2. Rumusan Masalah .................................................................................... 4
1.3. Batasan Masalah ...................................................................................... 4
1.4. Tujuan dan Manfaat Penelitian ................................................................. 4
1.5. Metode Penelitian .................................................................................... 4
1.6. Sistematika Penyusunan ........................................................................... 6
BAB II KAJIAN PUSTAKA ........................................................................ 8
2.1. Penjadwalan ............................................................................................. 8
2.1.1. Waktu Shalat .................................................................................. 8
2.1.2. Penjadwalan Kuliah ........................................................................ 10
2.2. Optimasi .................................................................................................. 12
2.3. Algoritma Genetika (Genetic Algorithms) ............................................... 15
2.3.1. Komponen Utama Algoritma Genetika .......................................... 21
2.3.2. Parameter Algoritma Genetika ....................................................... 30
2.4. Penerapan Algoritma Genetika pada Penjadwalan Perkuliahan ................ 31
x
BAB III PERANCANGAN SISTEM .......................................................... 35
3.1. Penjadwalan Kuliah di Jurusan Teknik Informatika ................................. 35
3.2. Komponen Penjadwalan Perkuliahan ...................................................... 35
3.3. Rancangan Sistem .................................................................................... 37
3.3.1. Faktor-faktor yang Mempengaruhi Penjadwalan ............................ 37
3.3.2. Aturan Penjadwalan ...................................................................... 38
3.3.3. Model Genetika ............................................................................. 39
3.3.4. Skema Database ............................................................................ 40
3.3.5. Inisialisasi Kromosom ................................................................... 41
3.3.6. Fungsi Fitness ............................................................................... 41
3.3.7. Seleksi ........................................................................................... 42
3.3.8. Perkawinan Silang ......................................................................... 42
3.3.9. Mutasi ........................................................................................... 43
3.4. Pemodelan UML ..................................................................................... 43
3.4.1. Use Case Diagram ........................................................................ 43
3.4.2. Activity Diagram ............................................................................ 45
3.4.3. Class Diagram ............................................................................... 52
3.4.4. Sequence Diagram ......................................................................... 53
3.5. Optimasi Penjadwalan Perkuliahan ......................................................... 61
BAB IV IMPLEMENTASI DAN UJI COBA ............................................. 62
4.1. Deskripsi Program .................................................................................. 62
4.1.1. Input Data .................................................................................... 62
4.1.2. Konfigurasi .................................................................................. 66
4.2. Penerapan Program pada Penjadwalan Perkuliahan ................................. 66
4.3. Penjelasan Program .................................................................................. 68
4.3.1. Inisialisasi Kromosom ................................................................. 69
4.3.2. Aturan Penjadwalan ..................................................................... 69
4.3.3. Parameter Algoritma Genetika ..................................................... 73
4.4. Uji Coba ................................................................................................. 77
xi
BAB V PENUTUP ........................................................................................ 81
5.1. Kesimpulan .............................................................................................. 81
5.2. Saran ........................................................................................................ 81
DAFTAR PUSTAKA
LAMPIRAN A
LAMPIRAN B
xii
DAFTAR TABEL
Tabel 2.1 Contoh populasi dengan 5 kromosom .......................................... 23
Tabel 3.1 Daftar Jam Kuliah Reguler .......................................................... 37
Tabel 3.2 Aturan dan nilai pinalti ................................................................. 42
Tabel 4.1 Kombinasi default parameter genetika ......................................... 66
Tabel 4.2 Kombinasi parameter genetika yang diuji coba ............................ 78
Tabel 4.3 Hasil uji coba dan perhitungan tingkat kesalahan ......................... 79
xiii
DAFTAR GAMBAR
Gambar 2.1 Taksonomi Algoritma Optimasi ............................................... 14
Gambar 2.2 Ilustrasi Representasi Penyelesaian Permasalahan dalam
Algoritma Genetika ................................................................. 20
Gambar 2.3 Siklus Sederhana Algoritma Genetika ...................................... 21
Gambar 2.4 Probabilitas suatu kromosom dalam roda roulette .................... 23
Gambar 2.5 Crossover satu titik ................................................................. 27
Gambar 2.6 Crossover dua titik .................................................................. 27
Gambar 2.7 Order Crossover ...................................................................... 28
Gambar 2.8 Mutasi tingkat kromosom ................................................................... 29
Gambar 2.9 Mutasi tingkat gen .............................................................................. 29
Gambar 2.10 Mutasi tingkat bit ............................................................................... 29
Gambar 3.1 Skema Database ..................................................................... 41
Gambar 3.2 Ilustrasi perkawinan silang ....................................................... 43
Gambar 3.3 Use case Diagram .................................................................... 43
Gambar 3.4 Activity Diagram secara umum alur Algoritma Genetika ......... 46
Gambar 3.5 Activity Diagram memasukkan data mata kuliah ...................... 47
Gambar 3.6 Activity Diagram memasukkan data dosen ............................... 48
Gambar 3.7 Activity Diagram memasukkan data penugasan ........................ 49
Gambar 3.8 Activity Diagram memasukkan data kesediaan waktu dosen .... 50
Gambar 3.9 Activity Diagram memasukkan data ruang ............................... 51
Gambar 3.10 Activity Diagram memasukkan data hari dan jam .................... 52
Gambar 3.11 Class Diagram ........................................................................ 53
Gambar 3.12 Sequence Diagram Proses Genetika Penjadwalan Perkuliahan 54
Gambar 3.13 Sequence Diagram memasukkan data mata kuliah .................. 55
Gambar 3.14 Sequence Diagram memasukkan data dosen ............................ 56
Gambar 3.15 Sequence Diagram memasukkan data penugasan .................... 57
Gambar 3.16 Sequence Diagram memasukkan data kesediaan waktu dosen . 58
Gambar 3.17 Sequence Diagram memasukkan data ruang ............................ 59
Gambar 3.18 Sequence Diagram memasukkan data hari dan jam .................. 60
xiv
Gambar 4.1 Interface utama ........................................................................ 62
Gambar 4.2 Form input data dosen ............................................................... 63
Gambar 4.3 Form input data mata kuliah ...................................................... 63
Gambar 4.4 Form input data ruang .................................................................... 64
Gambar 4.5 Form input data hari dan jam kuliah .............................................. 64
Gambar 4.6 Form input data ketersediaan waktu dosen .................................... 65
Gambar 4.7 Form input data penugasan ............................................................ 65
Gambar 4.8 Form proses genetika ..................................................................... 66
Gambar 4.9 Hasil penjadwalan .......................................................................... 68
xv
ABSTRAK
Lina Maria Ulfa. 2011. 06550003. Optimasi Penjadwalan Perkuliahan
Menggunakan Algoritma Genetika (Studi Kasus: Jurusan Teknik
Informatika UIN Malang). Jurusan Teknik Informatika Fakultas Sains
dan Teknologi Universitas Islam Negeri Maulana Malik Ibrahim Malang.
Pembimbing: (I) Ririen Kusumawati, M.Kom (II) Dr. Ahmad Barizi, M.A
Kata Kunci: penjadwalan kuliah, Algoritma Genetika
Penyusunan jadwal perkuliahan setiap semester adalah suatu pekerjaan yang
rumit karena harus mengkombinasikan antara mata kuliah yang ditawarkan, waktu
kesediaan dosen, ruangan, dan dilengkapi dengan sejumlah aturan yang harus
dilaksanakan. Selama ini di Jurusan Teknik Informatika UIN Maliki Malang
penjadwalan perkuliahan dilakukan secara manual dengan kondisi memiliki banyak
mahasiswa, ruang perkuliahan terbatas, waktu yang dibatasi, dan jumlah dosen yang
masih sedikit, sehingga perlu adanya aplikasi penjadwalan perkuliahan secara
otomatis. Pada skripsi ini, peneliti mencoba menyelesaikan masalah penjadwalan
perkuliahan menggunakan Algoritma Genetika sebagai metode optimasinya.
Algoritma Genetika merupakan algoritma pendekatan komputasional untuk
menyelesaikan masalah yang dimodelkan dengan proses biologi dari evolusi.
Keuntungan penggunaan Algoritma Genetika adalah dari kemudahan implementasi
dan kemampuannya untuk menemukan solusi yang bagus dan cepat untuk masalah-
masalah berdimensi tinggi. Penggunaan Algoritma Genetika untuk menyelesaikan
seputar masalah penjadwalan telah banyak dipergunakan oleh para peneliti bidang ini.
Berdasarkan uji coba yang dilakukan menggunakan data sebanyak 217 kelas
perkuliahan, dengan probabilitas crossover 60% dan probabilitas mutasi 1%,
menghasilkan jadwal kuliah dengan fitness rata-rata 0,03656 dan tingkat kesalahan
sebesar 27,79%. Aplikasi ini sudah dapat digunakan untuk membuat jadwal
perkuliahan dengan melakukan perubahan secara manual pada jadwal-jadwal yang
bentrok.
xvi
ABSTRACT
Lina Maria Ulfa. 2011. 06550003. Scheduling Optimation Using Genetic
Algorithm (Case Studies: Department of Informatics Engineering,
State Islamic University of Maulana Malik Ibrahim Malang). .
Department of Informatics Engineering, Faculty of Science and
Technology, State Islamic University of Maulana Malik Ibrahim Malang.
Guide : (I) Ririen Kusumawati, M.Kom (II) Dr. Ahmad Barizi, M.A
Keywords: scheduling courses, Genetic Algorithm
Scheduling classes each semester is a complicated job because it must
combine courses that are offered, the ability of lecturer, space, and is equipped
with a number of rules that must be implemented. During this time at Department
of Informatics Engineering, State Islamic University of Maulana Malik Ibrahim
Malang scheduling is done manually with the condition have a lot of students,
lecture space is limited, time is limited, and few number of lecturers, so it needs a
lecture scheduling applications automatically. In this thesis, the researcher tried to
resolve the problem of scheduling lectures as a method using genetic algorithm
optimization.
Genetic Algorithm is an algorithm approach to solve computational
problems that are modeled with the biological processes of evolution. The
advantage of using genetic algorithms is the ease of implementation and ability to
find a good and quick solutions to the problems of high dimension. The use of
genetic algorithms to solve around issues of scheduling has been widely used by
researchers of this field.
Based on experiments performed using the data as much as 217 classroom
courses, with 60% crossover probability and 1% mutation probability, resulting in
a fitness class schedule with an average of 0.03656 and an error rate of 27.79%.
This application can already used to schedule courses with some manual changes
at the error schedules.