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





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





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





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)


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.


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.

06550003 lina maria ulfa.ps

Documents