PENERAPAN ALGORITMA GENETIKA UNTUK OPTIMASI JADWAL MATA KULIAH PADA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA
SKRIPSI
RURY HANDAYANI 061401018
PROGRAM STUDI S1 ILMU KOMPUTER DEPARTEMEN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2010
Universitas Sumatera Utara
PENERAPAN ALGORITMA GENETIKA UNTUK OPTIMASI JADWAL MATA KULIAH PADA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA
SKRIPSI
Diajukan untuk melengkapi tugas dan memenuhi syarat mencapai gelar Sarjana Komputer
RURY HANDAYANI 061401018
PROGRAM STUDI S1 ILMU KOMPUTER DEPARTEMEN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2010
Universitas Sumatera Utara
PERSETUJUAN
Judul
Kategori Nama Nomor Induk Mahasiswa Program Studi Departemen Fakultas
: PENERAPAN ALGORITMA GENETIKA UNTUK OPTIMASI JADWAL MATA KULIAH PADA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA : SKRIPSI : RURY HANDAYANI : 061401018 : SARJANA (S1) ILMU KOMPUTER : ILMU KOMPUTER : MATEMATIKA DAN ILMU PENGETAHUAN ALAM (FMIPA) UNIVERSITAS SUMATERA UTARA Diluluskan di Medan,
Komisi Pembimbing
:
Pembimbing 2
Ade Chandra, ST, M. Kom NIP. 197909042009121002
Pembimbing 1
Drs. James P. Marbun, M. Kom NIP. 195806111986031002
Diketahui/Disetujui oleh Program Studi S1 Ilmu Komputer Ketua,
Prof. Dr. Muhammad Zarlis NIP 195707011986011003
Universitas Sumatera Utara
PERNYATAAN
PENERAPAN ALGORITMA GENETIKA UNTUK OPTIMASI JADWAL MATA KULIAH PADA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA SKRIPSI
Saya mengakui bahwa skripsi ini adalah hasil karya saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing disebutkan sumbernya.
Medan, 9 Nopember 2010
Rury Handayani 061401018
Universitas Sumatera Utara
PENGHARGAAN Pertama-tama penulis ingin mengucapkan puji syukur ke hadirat Allah SWT, karena atas limpahan rahmat-Nya penulis dapat menyelesaikan skripsi ini, sebagai syarat untuk memperoleh gelar Sarjana Komputer, Program Studi S1 Ilmu Komputer. Ucapan terima kasih penulis sampaikan kepada Drs. James P. Marbun, M. Kom selaku pembimbing pertama dan Ade Chandra, ST, M. Kom selaku pembimbing kedua yang telah meluangkan waktunya dan membagi ilmunya dalam memberikan masukan kepada penulis dalam penyelesaian skripsi ini. Ucapan terima kasih juga penulis ucapkan kepada Prof. Dr. Muhammad Zarlis selaku Ketua Departemen Ilmu Komputer dan dosen penguji, dan kepada M. Andri B, ST, M.Comp. Sc, MEM selaku dosen penguji kedua. Ucapan terima kasih juga penulis ucapkan kepada Syahriol Sitorus, S.Si selaku Sekretaris Departemen Ilmu Komputer, kepada Dekan dan Pembantu Dekan Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sumatera Utara, dosen-dosen, dan pegawai di Departemen Ilmu Komputer Sumatera Utara. Skripsi ini terutama penulis persembahkan untuk kedua orang tua penulis yang telah memberikan semangat dan doa, ayahanda Irwan Djamaluddin dan ibunda Muliyani yang selalu sabar dalam mendidik dan mendengar keluh kesah penulis, kepada kakak dan adik Tia Irmayani dan Mentari Irdayani atas keceriaan dan perhatian yang telah diberikan kepada penulis. Terima kasih penulis ucapkan kepada teman-teman yang tak henti memberikan dukungan dan persahabatan selama kuliah, Surya Wijaya, Habrul Leini Lubis, Anggarani Novitasari, Agus Salim, Fadly Fauzi, Aidil Akbar, dan Nurindah Sari. Semoga Allah SWT membalas semua kebaikan yang telah kalian berikan. Sekali lagi penulis mengucapkan terima kasih kepada semua pihak yang telah membantu dalam penyelesaian skripsi ini yang tidak dapat disebutkan satu persatu.
Universitas Sumatera Utara
ABSTRAK
Penjadwalan mata kuliah merupakan salah satu kegiatan dalam universitas yang membutuhkan banyak waktu untuk menyelesaikannya. Jadwal mata kuliah yang baik adalah jadwal yang memperhatikan semua komponen dasar penyusunnya. Komponen dasar terdiri atas dosen, mata kuliah, ruangan, dan jam kuliah. Untuk mencari alternatif dari penjadwalan digunakan algoritma genetika, yaitu algoritma yang menyelesaikan masalah dengan melakukan pemodelan mekanisme evolusi biologis. Kombinasi parameter genetika yang digunakan adalah seleksi turnamen, kawin silang satu titik, dan mutasi. Aplikasi ini menghasilkan tawaran jadwal mengajar untuk setiap dosen yang terdaftar. Program ditulis dengan menggunakan bahasa pemrograman VB6, dan analisis dilakukan dengan menggunakan flowchart dan DFD. Dari penggunaan algoritma genetika dalam penyelesaian masalah ini, diharapkan dapat menjadi alternatif untuk penjadwalan, dan menginspirasi untuk diadakan penelitian mengenai algoritma genetika lebih lanjut.
Universitas Sumatera Utara
APPLICATION OF GENETIC ALGORITHM TO OPTIMIZE LECTURER TIMETABLING
ABSTRACT
Lecturer timetabling is one of task in university that takes too much time to complete. A good lecturer timetabling is timetabling that includes all basic components. Those components are: lecturer, lecture, class, and time. To seek alternative of timetabling is by implemented genetic algorithm, ie algorithm that solve problem using mechanism of biological evolution. Combination of genetic parameters used are tournament selection, crossover one point, and mutation.This application generate offer lecturer timetabling for each lecturer listed. This program written in VB6, and analysis is done by using data flow diagram and flowchart. Using genetic algorithm in solving this problem is expected to be an alternative in lecturer timetabling and inspiring for the research on genetic algorithm further.
Universitas Sumatera Utara
DAFTAR ISI
Halaman Persetujuan Pernyataan Penghargaan Abstrak Abstract Daftar Isi Daftar Tabel Daftar Gambar
ii iii iv v vi vii ix x
Bab 1 Pendahuluan 1.1 Latar Belakang 1.2 Rumusan Masalah 1.3 Batasan Masalah 1.4 Tujuan Penelitian 1.5 Manfaat Penelitian 1.6 Metodologi Penelitian 1.7 Sistematika Penulisan
1 2 3 3 4 4 5
Bab 2 Landasan Teori 2.1 Penjadwalan 2.1.1 Batasan-Batasan pada Penjadwalan 2.1.1.1 Batasan Pokok Penjadwalan 2.1.1.2 Batasan Tambahan Penjadwalan 2.2 Algoritma Genetika 2.3 Teknik Pengodean 2.3.1 Pengodean Biner 2.3.2 Pengodean Nilai 2.3.3 Pengodean Pohon 2.3.4 Pengodean Permutasi 2.4 Operator dalam Algoritma Genetika 2.4.1 Seleksi 2.4.1.1 Seleksi Roda Roulette 2.4.1.2 Seleksi Ranking 2.4.1.3 Seleksi Turnamen 2.4.2 Penyilangan 2.4.2.1 Penyilangan Satu Titik
7 8 8 8 9 11 12 12 13 14 14 14 15 15 15 15 16
Universitas Sumatera Utara
2.4.2.2 Penyilangan Banyak Titik 2.4.2.3 Penyilangan Seragam 2.4.3 Mutasi 2.4.3.1 Mutasi Biner 2.4.3.2 Mutasi Nilai 2.5 Parameter dalam Algoritma Genetika
16 17 17 18 18 19
Bab 3 Analisis dan Perancangan Sistem 3.1 Analisis Kebutuhan Perangkat Lunak 3.1.1 Metode Analisis 3.1.2 Hasil Analisis 3.1.2.1 Sistem Penjadwalan Mata Kuliah di Fakultas MIPA 3.1.2.2 Komponen Utama Penjadwalan 3.2 Perancangan Perangkat Lunak 3.2.1 Hasil Perancangan 3.2.1.1 Pemodelan Proses 3.2.1.1.1 Data Flow Diagram Level 0 3.2.1.1.2 Data Flow Diagram Level 1 3.2.1.2 Pemodelan Data 3.2.1.3 Pemodelan Antarmuka
21 21 22 24 24 27 28 28 28 29 30 35
Bab 4 Implementasi dan Pengujian 4.1 Implementasi 4.1.1 Kebutuhan Perangkat Keras 4.1.2 Kebutuhan Perangkat Lunak 4.2 Penggunaan Aplikasi 4.2.1 Halaman Utama 4.2.2 Halaman Data Dosen 4.2.3 Halaman Data Mata Kuliah 4.2.4 Halaman Data Ampu Mata Kuliah 4.2.5 Halaman Data Ruang 4.2.6 Halaman Data Ketersediaan Dosen 4.2.7 Halaman Data Waktu Kuliah 4.2.8 Halaman Penjadwalan 4.3 Pengujian Aplikasi
42 42 43 43 43 46 48 50 52 53 54 55 58
Bab 5 Kesimpulan dan Saran 5.1 Kesimpulan 5.2 Saran
60 61
Daftar Pustaka
62
Lampiran A: Listing Program
63
Universitas Sumatera Utara
DAFTAR TABEL
Halaman Tabel 2.1 Tabel 2.2 Tabel 2.3 Tabel 2.4 Tabel 2.5 Tabel 2.6 Tabel 2.7 Tabel 2.8 Tabel 2.9 Tabel 3.1 Tabel 3.2 Tabel 3.3 Tabel 3.4 Tabel 3.5 Tabel 3.6 Tabel 3.7 Tabel 3.8 Tabel 3.9 Tabel 3.10 Tabel 3.11 Tabel 3.12 Tabel 3.13 Tabel 3.14 Tabel 3.15 Tabel 3.16 Tabel 3.16
Contoh Kromosom dalam Pengodean Biner Contoh Kromosom dalam Pengodean Nilai Contoh Kromosom dalam Pengodean Pohon Contoh Kromosom dalam Pengodean Permutasi Contoh Penyilangan Satu Titik Contoh Penyilangan Banyak Titik Contoh Penyilangan Seragam Contoh Mutasi Biner Contoh Mutasi Nilai Contoh Dosen dan Mata Kuliah yang Diampunya Contoh Paket Mata Kuliah Daftar Jam Kuliah Ruangan dan Kapasitasnya Contoh Penjadwalan Mata Kuliah tDosen tMtKuliah tRuang tJamKuliah tSedia Dosen tPenalti tAmpu tProses tFitness tJadwal tGenetika Pembagian Waktu pada Penjadwalan
12 12 13 14 16 17 17 18 18 25 25 26 27 27 30 30 31 31 32 32 32 33 33 34 34 41
Universitas Sumatera Utara
DAFTAR GAMBAR
Halaman Gambar 3.1 Diagram Proses Aplikasi Penjadwalan Mata Kuliah dengan Algoritma Genetika Gambar 3.2 DFD Level 0 Gambar 3.3 DFD Level 1 Gambar 3.4 Relationship Database pada Penjadwalan Mata Kuliah Gambar 3.5 Halaman Menu Utama Sebelum Proses Login Gambar 3.6 Halaman Menu Utama Setelah Proses Login Gambar 3.7 Halaman Form Dosen Gambar 3.8 Halaman Form Mata Kuliah Gambar 3.9 Halaman Form Ruang Gambar 3.10 Halaman Form Ketidaktersediaan Dosen Gambar 3.11 Halaman Form Jam Kuliah Gambar 4.1 Halaman Awal Gambar 4.2 Halaman Login Gambar 4.3 Halaman Utama Setelah Login Gambar 4.4 Halaman Data Dosen Gambar 4.5 Kotak Dialog Ketika Data Dosen Tidak Lengkap Gambar 4.6 Kotak Dialog Ketika Nama Dosen Tidak Ada Gambar 4.7 Kotak Dialog Pengubahan Data Gambar 4.8 Kotak Dialog Yakin Hapus Gambar 4.9 Halaman Data Mata Kuliah Gambar 4.10 Kotak Dialog Ketika Data Mata Kuliah Tidak Ada Gambar 4.11 Halaman Data Ampu Mata Kuliah Gambar 4.12 Halaman Data Ruangan Gambar 4.13 Halaman Data Ketersediaan Dosen Mengajar Gambar 4.14 Halaman Data Waktu Kuliah Gambar 4.15 Halaman Penjadwalan dengan Algoritma Genetika Gambar 4.16 Kotak Dialog ketika Salah Satu Data Tidak Lengkap untuk Menjalankan Algoritma Genetika Gambar 4.17 Halaman Cetak Penjadwalan Mata Kuliah
23 29 29 35 36 36 37 38 38 39 40 44 45 45 46 47 47 48 48 49 50 51 52 53 54 56 57 58
Universitas Sumatera Utara
