PENJADWALAN KULIAH DENGAN MENGGUNAKAN ALGORITMA GENETIKA STUDI KASUS FAKULTAS TEKNIK UNIVERSITAS SUMATERA UTARA TESIS

PENJADWALAN KULIAH DENGAN MENGGUNAKAN ALGORITMA GENETIKA STUDI KASUS FAKULTAS TEKNIK UNIVERSITAS SUMATERA UTARA

TESIS

Oleh: PURWANTO SIMAMORA 097034013/MTE

FAKULTAS TEKNIK UNIVERSITAS SUMATERA UTARA MEDAN 2013

Universitas Sumatera Utara

2


TESIS

Tugas Akhir ini diajukan untuk melengkapi salah satu syarat untuk memperoleh gelar Magister Teknik (MT)

Oleh PURWANTO SIMAMORA 097034013/MTE

FAKULTAS TEKNIK UNIVERSITAS SUMATERA UTARA MEDAN 2013


3

Judul Tesis

: PENJADWALAN KULIAH DENGAN MENGGUNAKAN ALGORITMA GENETIKA STUDI KASUS FAKULTAS TEKNIK UNIVERSITAS SUMATERA UTARA

Nama Mahasiswa : Purwanto Simamora Nomor Induk : 097034013 Program Studi : Magister Teknik Elektro

Menyetujui Komisi Pembimbing,

(Prof. Drs. Tulus, M.Si., Ph.D.) Ketua

(Fakhruddin R. Batubara, S.T., M.TI.) Anggota

Sekretaris Program Studi,

Dekan,

(Drs. Hasdari Helmi, M.T.)

(Prof. Dr. Ir. Bustami Syam, MSME)

Tanggal Lulus : 10 Oktober 2013


4


Oleh:

PURWANTO SIMAMORA NIM: 097034013

Tugas Akhir ini diajukan untuk melengkapi salah satu syarat untuk memperoleh gelar Magister Teknik PROGRAM STUDI MAGISTER TEKNIK ELEKTRO FAKULTAS TEKNIK UNIVERSITAS SUMATERA UTARA MEDAN Sidang meja hijau tanggal 10 bulan Oktober tahun 2013 di depan komisi penguji: 1. Prof. Drs. Tulus, M.Si., Ph.D.

: Ketua Penguji

2. Fakhruddin R. Batubara, S.T., M.TI.

: __________

: Anggota Penguji I : __________

3. Dr. Benny B. Nasution., Dipl.Ing., M.Eng. : Anggota Penguji II : __________ 4. Fahmi, S.T., M.Sc.

: Anggota Penguji III : __________

5. Dr. Poltak Sihombing, M.Kom.

:

Anggota Penguji IV : __________

Diketahui Oleh: Sekretaris, Program Studi Magister Teknik Elektro FT. USU

(Drs. Hasdari Helmi, M.T.) NIP. 195911301987011001


5

Telah Diuji pada Tanggal : 10 Oktober 2013

PANITIA PENGUJI TESIS Ketua : Prof. Drs. Tulus, M.Si., Ph.D Anggota : 1. Fakhruddin R. Batubara, S.T., M.TI. 2. Dr. Benny B. Nasution., Dipl.Ing., M.Eng 3. Fahmi, S.T., M.Sc. 4. Dr. Poltak Sihombing, M.Kom


6

ABSTRAK Penjadwalan kuliah merupakan suatu kegiatan untuk mengalokasikan sejumlah aktivitas perkuliahan ke dalam slot ruang dan waktu yang telah tersedia. Untuk menghasilkan suatu penjadwalan kuliah yang baik, maka diperlukan komponen penjadwalan antara lain dosen, mata kuliah, mahasiswa, kurikulum, ruang dan waktu. Keterbatasan ruang dan waktu kuliah sering menjadi permasalahan dalam penyusunan jadwal kuliah. Penambahan jumlah mahasiswa, penambahan mata kuliah akibat penerapan kurikulum baru, dan penambahan kegiatan lain di universitas mempengaruhi penggunaan jumlah ruang dan waktu. Sistem penjadwalan kuliah yang diinginkan adalah sistem penjadwalan yang optimal dan cepat untuk mengatasi tiap perubahan yang terjadi. Sistem penjadwalan yang dihasilkan nantinya harus tetap mengatasi keterbatasan pada komponen penjadwalan yaitu jumlah dosen, ruang dan waktu yang tersedia. Penelitian ini menggunakan dua metode dalam menyusun sistem penjadwalan kuliah, yaitu dengan menggunakan algoritma penjadwalan dan tanpa menggunakan algoritma penjadwalan. Kedua metode ini akan digabungkan ke dalam algoritma genetika sehingga diharapkan diperoleh suatu sistem penjadwalan kuliah yang dapat mengurangi jumlah pelanggaran ruang dan waktu. Dari hasil penelitian diperoleh bahwa tanpa menggunakan algoritma penjadwalan, terjadi 2 pelanggaran waktu dan jumlah ruang minimal yang digunakan ada sebanyak 9 ruangan serta konvergen pada generasi ke-127. Tetapi dengan menggunakan algoritma penjadwalan, jumlah pelanggaran yang terjadi tidak terjadi lagi dan penggunaan jumlah ruangan minimal menjadi 8 ruangan serta konvergen pada generasi ke-85. Dengan demikian penjadwalan mata kuliah dengan menggabungkan algoritma penjadwalan dan algoritma genetika merupakan metode yang lebih tepat untuk mengurangi jumlah pelanggaran waktu dan dapat lebih memanfaatkan penggunaan jumlah ruangan seminimal mungkin. Katakunci : Penjadwalan Kuliah, Algoritma genetika, Konvergen, Pelanggaran Ruang, Pelanggaran Waktu


7

ABSTRACT Scheduling courses is an activity of allocating a number of activities of giving lectures in an available slot of space and time. To yield good course scheduling, we need scheduling components such as instructors, subjects, students, curriculum, place, and time. The limited place and time for courses often become a problem in organizing course schedule. The addition of the number of students, the addition of subjects because of a new curriculum, and the addition of other activities at the university influence the use of place and time. The intended system of scheduling courses is an optimal and fast scheduling system to cope with every change. The outcome of the scheduling system should be able to cope with the limitation of scheduling components such as the available number of instructors, place, and time. This research used two methods in organizing the scheduling of courses, by using scheduling algorithm and without using scheduling algorithm. These two methods would be combined into genetic algorithm so that it was expected to obtain a system of course scheduling which could reduce a number of violations against place and time. The result of the research showed that scheduling algorithm was not used, two violations would occur and the number of minimal use of rooms would be nine rooms and the convergence at the 127th generation. On the other hand, scheduling logarithm was used, the number of violations would not occur and the use of minimal rooms became eight rooms at the 85th generation. Therefore, the scheduling of courses by combining scheduling algorithm with genetic algorithm was a correct method to reduce the number of violations of place and time and could be more beneficial for the use of the number of rooms as minimal as possible. Keywords: Course Scheduling, Genetic Algorithm, Convergence, Violation of Place, Violation of Time


8

KATA PENGANTAR

Puji dan syukur kehadirat Tuhan Yang Maha Esa, atas berkat, rahmat dan karuniaNya sehingga penulis dapat menyelesaikan tesis dengan judul: Sistem Penjadwalan Kuliah dengan Menggunakan Algoritma Genetika Studi Kasus Fakultas Teknik Universitas Sumatera Utara. Tesis ini merupakan salah satu syarat yang harus dipenuhi oleh mahasiswa untuk mendapatkan gelar Magister Teknik pada Program Studi Teknik Elektro Universitas Sumatera Utara. Penulis banyak mendapat bantuan dan dukungan dari berbagai pihak dalam menyelesaikan tesis ini. Pada kesempatan ini, penulis mengucapkan terima kasih kepada Bapak Prof. Drs. Tulus, M.Si., Ph.D., selaku Ketua Komisi Pembimbing, Bapak Fakhruddin R. Batubara, S.T., M.TI., selaku Pembimbing yang dengan penuh sabar, arif dan bijaksana memberikan bimbingan, dorongan, petunjuk serta arahan kepada penulis. Bapak Dr. Benny B. Nasution, Dipl. Ing., M.Eng., Bapak Fahmi, S.T., M.Sc., dan Bapak Dr. Poltak Sihombing, M.Kom., selaku Pembanding Utama yang telah memberikan kritik dan masukan terhadap tesis. Penulis juga mengucapkan terima kasih kepada orang tua penulis, Bapak Drs. Djamiandar Simamora, DFM., M.Pd. dan Ibu Alida Nurbetty Siregar atas doa dan dukungannya. Keluarga dan teman penulis yang telah banyak memberikan semangat dan perhatian serta toleransi sehingga tesis ini selesai. Terselesaikannya penelitian tesis ini juga melibatkan berbagai pihak yaitu: Ketua dan Sekretaris Program Studi


9

Magister Teknik Elektro, serta seluruh staf pengajar dan karyawan Program Studi Magister Teknik Elektro, untuk itu penulis mengucapkan terimakasih atas kontribusi dan bantuannya. Penulis menyadari masih ada kekurangan dalam tulisan ini, namun penulis mengharapkan tulisan ini dapat memenuhi persyaratan yang diperlukan untuk suatu tesis dalam Program Studi Magister Teknik Elektro Fakultas Teknik Universitas Sumatera Utara. Akhir kata penulis mengucapkan terima kasih dan semoga tesis ini dapat berguna bagi semua kita. Medan,

Oktober 2013

Hormat Saya,

Purwanto Simamora


10

DAFTAR ISI

Halaman

ABSTRAK ..................................................................................................... i-ii KATA PENGANTAR .................................................................................... iii DAFTAR ISI ..................................................................................................... v DAFTAR TABEL ........................................................................................... ix DAFTAR GAMBAR ....................................................................................... xi DAFTAR LAMPIRAN ...................................................................................xii BAB I PENDAHULUAN ............................................................................... 1 1.1. Latar Belakang Masalah ................................................................. 1 1.2. Rumusan Masalah ......................................................................... 6 1.3. Batasan Masalah ............................................................................ 6 1.4. Tujuan Penelitian .......................................................................... 7 1.5. Manfaat Penelitian ........................................................................ 7 1.6. Sistematika Penulisan ................................................................... 8

BAB II TINJAUAN PUSTAKA ................................................................... 10 2.1. Penelitian Terkait ........................................................................ 10 2.2. Penjadwalan Kuliah ..................................................................... 12 2.3. Masalah Penjadwalan Kuliah ...................................................... 14 2.4. Persyaratan Penjadwalan ............................................................. 15 2.5. Kesulitan dalam Menyusun Penjadwalan .................................... 16 2.6. Algoritma Genetika ...................................................................... 17 2.6.1. Tahapan Algoritma Genetika ........................................... 18 2.6.2. Komponen Utama Algoritma Genetika ........................... 19 2.7. Pengkodean ................................................................................. 19 2.7.1. Pengkodean Biner ............................................................. 19


11

2.7.2. Pengkodean Nilai .............................................................. 20 2.7.3. Pengkodean Pohon ........................................................... 21 2.7.4. Pengkodean Permutasi ....................................................... 21 2.8. Inisialisasi Populasi ................................................................... 22 2.9. Operator dalam Algoritma Genetika .......................................... 23 2.9.1. Seleksi ............................................................................ 23 2.9.1.1.Seleksi Roda Roulette ....................................... 23 2.9.1.2.Seleksi Ranking.................................................. 25 2.9.1.3.Seleksi Turnamen ........................................................ 26 2.9.2. Kawin Silang ................................................................. 27 2.9.2.1.Kawin Silang 1 Titik ......................................... 27 2.9.2.2.Kawin Silang 2 Titik ......................................... 28 2.9.2.3.Kawin Silang Seragam ...................................... 29 2.9.2.4.Kawin Silang Rekombinasi .............................. 30 2.9.3. Mutasi ............................................................................ 31 2.9.3.1.Mutasi Biner ..................................................... 32 2.9.3.2.Mutasi Permutasi .............................................. 32 2.9.3.3.Mutasi Nilai ...................................................... 32 2.10. Elitisme ..................................................................................... 33 2.11. Precedence Presservative Crossover (PPX) .............................. 33 2.12. Konvergen ................................................................................. 34

BAB III METODE PENELITIAN .............................................................. 36 3.1. Sumber Data ............................................................................. 36 3.1.1. Daftar Nama Dosen ......................................................... 37 3.1.2. Daftar Mata Kuliah ......................................................... 37 3.1.3. Daftar Jumlah Mahasiswa ............................................... 38 3.1.4. Daftar Waktu Kuliah ....................................................... 38 3.1.5. Daftar Ruang Kuliah ....................................................... 39


12

3.2. Perancangan Penjadwalan Kuliah ............................................. 39 3.3. Optimasi Penjadwalan dengan Algoritma Genetika .................. 40 3.3.1. Pemilihan Representasi Masalah .................................... 40 3.3.2. Pembentukan Gen ........................................................... 41 3.3.3. Pembentukan Kromosom ................................................ 41 3.4. Pembentukan Populasi Awal (Inisialisasi) ................................ 42 3.5. Pemilihan Operator Genetika .................................................... 43 3.5.1. Seleksi dan Penetapan Fungsi Fitness ............................ 43 3.5.2. Crossover dan Mutasi ..................................................... 45 3.6. Perancangan Algoritma Genetika .............................................. 46 3.7. Perbandingan dan Analisa Hasil Penjadwalan .......................... 48 3.8. Diagram Alir Penelitian ............................................................. 49

BAB IV HASIL DAN ANALISA ................................................................. 51 4.1. Pengumpulan Data ..................................................................... 51 4.2. Komponen Penjadwalan ............................................................ 52 4.2.1. Daftar Mata Kuliah ......................................................... 53 4.2.2. Daftar Waktu Kuliah ....................................................... 54 4.2.3. Daftar Ruang Kuliah ...................................................... 55 4.3. Perancangan Sistem Penjadwalan Kuliah .................................. 56 4.3.1. Pengkodean Data ............................................................. 57 4.3.2. Pembentukan Kromosom ................................................ 60 4.3.3. Pengembalian Kode (Decoding) .................................... 69 4.4. Fungsi fitness ............................................................................. 77 4.5. Proses Optimasi dengan Algoritma Genetika ............................ 81 4.5.1. Penentuan Hard Constraint dan Soft Constraint ............ 81 4.5.2. Pencarian Kromosom Dominated & Non-Dominated .... 83 4.5.3. Proses Seleksi dan Mutasi ............................................... 85


13

4.5.4. Hasil Pengujian pada Metode Tanpa Algoritma Penjadwalan .................................................................... 87 4.6. Proses Optimasi dengan Algoritma Penjadwalan dan Algoritma Genetika ............................................................ 89 4.6.1. Pembentukan Gen pada Metode dengan Algoritma Penjadwalan ................................................. 89 4.6.2 Perbaikan Kromosom dengan Algoritma Genetika .......................................................................... 99 4.6.3 Hasil Pengujian pada Metode Tanpa Algoritma Penjadwalan .................................................................. 100 4.7. Perbandingan Hasil Penjadwalan .......................................... 103 4.8. Perbandingan Grafik Hasil Penjadwalan ............................... 105

BAB V KESIMPULAN DAN SARAN ........................................................ 107 5.1. Kesimpulan ............................................................................ 107 5.2. Saran ...................................................................................... 108

DAFTAR PUSTAKA .................................................................................... 109 LAMPIRAN ................................................................................................ A – J


14

DAFTAR TABEL

Halaman Tabel 2.1. Kromosom dengan Pengkodean Biner ................................................20 Tabel 2.2. Kromosom dengan Pengkodean Nilai..................................................21 Tabel 2.3. Kromosom dengan Pengkodean Permutasi..........................................22 Tabel 2.4. Contoh proses seleksi ...........................................................................23 Tabel 2.5. Seleksi Ranking sebelum di-ranking....................................................25 Tabel 2.6. Seleksi Ranking setelah di-ranking ......................................................25 Tabel 2.7. Kawin Silang Rekombinasi..................................................................30 Tabel 2.8. Mutasi pada Pengkodean Biner............................................................32 Tabel 2.9. Mutasi pada Pengkodean Permutasi ....................................................32 Tabel 2.10 Contoh mutasi pada pengkodean nilai riil............................................33 Tabel 3.1 Contoh Pengkodean Waktu Kuliah dengan Kode Biner ........................40 Tabel 3.2 Contoh Pengkodean Ruang Kuliah dengan Kode Biner ........................41 Tabel 3.3 Jadwal Hasil Penerjemahan Kromosom ................................................42 Tabel 4.1 Daftar Mata Kuliah dan Dosen ..............................................................53 Tabel 4.2 Daftar Waktu Kawin untuk Daftar Hari .................................................55 Tabel 4.3 Daftar Waktu Kawin untuk Daftar Jam .................................................55 Tabel 4.4 Daftar Ruang Kuliah ..............................................................................56 Tabel 4.5 Kode Biner untuk Waktu Kuliah ...........................................................57 Tabel 4.6. Kode Biner untuk Ruang Kuliah ...........................................................60 Tabel 4.7 Pembentukan Gen dari Kode Waktu dan Kode Ruang Kuliah ..............63 Tabel 4.8 Urutan Mata Kulih dalam Kromosom ...................................................60 Tabel 4.9 Tabel Jadwal Kuliah Hasil Decoding dari Kromosom 1 .......................70 Tabel 4.10 Jadwal Penggunaan Waktu dan Ruang Kuliah ....................................79 Tabel 4.11 Pengurutan Kromosom berdasarkan Fitness f1 ....................................82 Tabel 4.12 Pemberian Nilai Fitness pada Kromosom dalam Populasi ..................84 Tabel 4.13 Kromosom Terpilih untuk k = 3 ..........................................................85 Tabel 4.14 Populasi Akhir dari Hasil Proses Optimasi ..........................................87 Tabel 4.15 Pengkodean Prioritas Mata Kuliah ......................................................90 Tabel 4.16 Urutan Penjadwalan Kuliah berdasarkan Penerjemahan Kromosom I .........................................................................................94 Tabel 4.17 Hasil Penjadwalan dengan Algoritma Penjadwalan ............................97 Tabel 4.18 Populasi Akhir sebagai Solusi Optimal dari Hasil Proses Optimasi dengan Metode Algoritma Genetika ..................................101


15

Tabel 4.19 Perbandingan Hasil Akhir Proses Optimasi dari Metode dengan Algoritma Penjadwalan dan Tanpa Algoritma Penjadwalan .............103


16

DAFTAR GAMBAR

Halaman Gambar 2.1. Flowchart Algoritma Genetika ........................................................18 Gambar 2.2. Seleksi Roda Roulette ......................................................................24 Gambar 2.3. Kawin Silang 1 Titik ........................................................................28 Gambar 2.4. Kawin Silang 2 Titik .........................................................................29 Gambar 2.5. Kawin Silang seragam .......................................................................30 Gambar 2.6. Operasi Mutasi Genetika ...................................................................31 Gambar 2.7. Precedence Presservative Crossover (PPX) .....................................34 Gambar 2.8. Nilai fitness dalam algoritma genetika ..............................................35 Gambar 3.1. Pembentukan Gen untuk Kode Waktu dan Kode Ruangan ..............41 Gambar 3.2. Kromosom yang Terbentuk dari Susunan Gen .................................42 Gambar 3.3 Proses Seleksi untuk Pencarian Pareto Optimal .................................45 Gambar 3.4 Proses Crossover ................................................................................46 Gambar 3.5 Diagram Alir Penelitian .....................................................................50 Gambar 4.1. Kromosom 1 yang terdiri dari 1050 Bit Biner ..................................69 Gambar 4.2. Proses Reproduksi dengan Mutasi Banyak Titik ..............................86 Gambar 4.3. Proses Perubahan Kode Biner ke Bentuk Gray Code .......................90 Gambar 4.4. Pembentukan Kromosom berdasarkan Urutan Penjadwalan Mata Kuliah .......................................................................................94 Gambar 4.5. Tabel Jadwal sebagai Matriks Waktu dan Ruangan..........................95 Gambar 4.6. Grafik Hasil Penjadwalan Kuliah tanpa Menggunakan Algoritma Penjadwalan ...................................................................105 Gambar 4.7. Grafik Hasil Penjadwalan Kuliah dengan Menggunakan Algoritma Penjadwalan ...................................................................106


17

DAFTAR LAMPIRAN

Halaman Daftar Dosen ................................................................................ A – 1 Daftar Mata Kuliah ...................................................................... B – 1 Daftar Gabungan Dosen dan Mata Kuliah .................................. C – 1 Daftar Jumlah Mahasiswa ........................................................... D – 1 Daftar Waktu Kuliah ................................................................... E – 1 Daftar Hari Kuliah ....................................................................... F – 1 Daftar Ruang Kuliah .................................................................... G – 1 List Program Penjadwalan Kuliah tanpa Algoritma Penjadwalan ................................................................................ H – 1 Lampiran 9. List Program Penjadwalan Kuliah dengan Algoritma Penjadwalan ................................................................ I – 1 Lampiran 10 Jadwal Kuliah Semester Ganjil..................................................... J – 1 Lampiran 1. Lampiran 2. Lampiran 3. Lampiran 4. Lampiran 5. Lampiran 6. Lampiran 7. Lampiran 8.


PENJADWALAN KULIAH DENGAN MENGGUNAKAN ALGORITMA GENETIKA STUDI KASUS FAKULTAS TEKNIK UNIVERSITAS SUMATERA UTARA TESIS

Recommend Documents