SISTEM SIMULASI PENJADWALAN KULIAH DENGAN MENGGUNAKAN ALGORITMA GENETIK
SKRIPSI
REYNOLD LUMBAN TOBING 050803027
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2010
Universitas Sumatera Utara
SISTEM SIMULASI PENJADWALAN KULIAH DENGAN MENGGUNAKAN ALGORITMA GENETIKA
SKRIPSI
Diajukan untuk melengkapi tugas dan memenuhi syarat mencapai gelar Sarjana Sains
REYNOLD LUMBAN TOBING 050803027
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2010
Universitas Sumatera Utara
ii
PERSETUJUAN
Judul
Kategori Nomor Induk Mahasiswa Program Studi Departemen Fakultas
: SISTEM SIMULASI PENJADWALAN KULIAH DENGAN MENGGUNAKAN ALGORITMA GENETIK : SKRIPSI : 050803027 : SARJANA (S1) MATEMATIKA : MATEMATIKA : MATEMATIKA DAN ILMU PENGETAHUAN ALAM (FMIPA) UNIVERSITAS SUMATERA UTARA
Diluluskan di Medan, Januari 2010 Komisi Pembimbing
:
Pembimbing 2
Pembimbing 1
Syahriol Sitorus, S.Si, M.IT NIP. 19710310 199703 1 004
Drs. Sawaluddin, M.IT NIP. 19591231 199802 1 001
Diketahui/ Disetujui oleh Departemen Matematika FMIPA USU
Dr. Saib Suwilo, M.Sc. NIP. 19640109 198803 1 004
Universitas Sumatera Utara
iii
PERNYATAAN
SISTEM SIMULASI PENJADWALAN KULIAH DENGAN MENGGUNAKAN ALGORITMA GENETIK
SKRIPSI
Saya mengakui bahwa skripsi ini adalah hasil kerja saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing disebutkan sumbernya.
Medan,
Januari 2010
REYNOLD LUMBAN TOBING 050803027
Universitas Sumatera Utara
iv
PENGHARGAAN
Puji dan syukur kehadirat Tuhan Yesus Kristus atas semua yang telah diberikan sehingga penulis dapat menyelesaikan tulisan ini. Terpujilah Tuhan. Ucapan terimakasih saya sampaikan kepada Drs. Sawaluddin, M.IT dan Syahriol Sitorus, S.Si, M.IT selaku pembimbing pada penyelesaian skripsi ini yang telah memberikan panduan kepada penulis dalam menyelesaikan tulisan ini. Kepada prof. Dr. Herman Mawengkang dan Drs. James P. Marbun, M.Kom selaku dosen penguji. Ucapan terimakasih juga penulis tujukan kepada Ketua dan Sekretaris Departemen Matematika FMIPA USU Dr. Saib Suwilo, M.Sc dan Drs. Henry Rani Sitepu, M.Si, kepada Dra. Normalina Napitupulu, M.Sc selaku dosen pengajar Algoritma Genetik yang telah memberikan masukan untuk penyelesaian tulisan ini serta seluruh Dosen dan staf pengajar Departemen Matematika FMIPA USU. Terima kasih yang teristimewa buat orang tua penulis, Ayahanda D. Lumban Tobing dan Ibunda T. br Sinaga yang penuh kasih sayang dan merupakan kekuatan penulis dalam setiap langkah kecil penulis dan telah mendidik penulis selama ini, juga kepada Adinda Alberd Lumban Tobing dan Anggita Christiara Lumban Tobing yang selama ini menjadi motivasi penulis dalam menyelesaikan skripsi ini beserta segenap keluarga yang telah banyak memberikan motivasi dan nasehat kepada saya. Terima kasih juga kepada rekanrekan medanLinux Community Wardi, S.Si, Erwin Sitanggang, S.Kom, Muhfi Asbin Sagala, Irwan Daniel, Palti Pandiangan, S.Kom dkk, kawan-kawan Open Solaris User Grup Medan Ainul Hizriadi, Jogi Silalhi dkk, dan kawan-kawan di Webmedia Training Center Eko Purwanto, Speedy Learning Center Divi Handoko, teman-teman Cisco Networking Academy Masril, Ali Asman, Ichsan Hakim, semua Management dan semua ruang lingkup kerja PESADA Dina Lumbantobing, Berliana Purba, Vitri Siregar, Juni Ribka dkk, kawan-kawan di BPC dan PK GMKI FMIPA USU Medan, juga kepada teman-teman seperjuangan di Matematika (Golden Generation) stambuk 2005 terkhusus sahabat penulis Meilinda Siahaan di Matematika bidang Komputasi 2005, Wenny Helena Simamora dan Zivora Veronika Sihombing, tidak lupa temanteman kost Doli Sipahutar, Efraim Parapat, Vanal Simamora, dan Dedi Lumban Tobing dan semua yang tidak dapat disebutkan satu-persatu yang mau membantu penulis baik dalam waktu, tenaga dan pemikiran dalam pengerjaan skripsi ini. Akhirnya, terima kasih buat semua yang telah memberi dukungan kepada penulis. Tuhan memberkati.
Universitas Sumatera Utara
v
ABSTRAK
Penjadwalan kegiatan kuliah dalam suatu kampus adalah hal yang rumit. Permasalahan yang sering disebut dengan University Timetabling Problems (UTP) ini, selain dilihat dari sisi mahasiswa juga harus dilihat dari sisi dosen, yaitu kemungkinan-kemungkinan dosen akan mengajar lebih dari satu mata kuliah yang ada. Sebab ada kemungkinan jumlah mata kuliah dan jumlah dosen tidak sebanding, sehingga harus dipikirkan juga solusi agar dosen tidak mengampu dua mata kuliah berbeda pada hari dan jam yang sama. Selain itu, harus dipertimbangkan juga ketersediaan kelas sehingga kegiatan belajar dapat dilaksanakan. Tulisan ini membahas tentang salah satu metode simulasi yang dapat digunakan untuk menyelesaikan permasalahan tersebut, yaitu dengan menggunakan pendekatan Algoritma Genetik yang merupakan pendekatan komputasional untuk menyelesaikan masalah yang dimodelkan dengan proses evolusi biologis.
Universitas Sumatera Utara
vi
UNIVERSITY TIMETABLING SIMULATION SYSTEM WITH GENETIC ALGORITHM
ABSTRACT
Studying activity scheduling in a college is a very complicated thing. Problems which is commonly called University Timetabling Problems (UTP), not only seen from the student’s view but also from the lecturer that there are some possibilities the lecturers would teach more than one subject. Because the number of subjects and lecturers may be not comparable, so we have to think about the way out that the lecturer will not teach the different subject at the same time and the same day. Besides that, the avability of study rooms must be considered so the study activity can be done. This minithesis examines about one of the simulation methods which can be used to solve the problem by using Genetic Algorithm approach. This also means a computational approaching which can be used to solve the problem using a evolution biological process as a sample.
Universitas Sumatera Utara
vii
DAFTAR ISI
Halaman Persetujuan Pernyataan Penghargaan Abstrak Abstract Daftar Isi Daftar Tabel Daftar Gambar
ii iii iv v vi vii ix xi
Bab 1
PENDAHULUAN 1.1 Latar Belakang 1.2 Perumusan Masalah 1.3 Pembatasan Masalah 1.4 Tujuan Penelitian 1.5 Tinjauan Pustaka 1.6 Manfaat Penelitian 1.7 Diagram Konsepsi 1.8 Metodologi Penelitian
1 1 3 3 4 4 5 5 6
Bab 2
LANDASAN TEORI 2.1 Pengertian Algoritma Genetik 2.2 Struktur Umum Algoritma Genetik 2.3 Pengkodean 2.4 Operator Genetik 2.4.1 Seleksi 2.4.2 Crossover 2.4.3 Mutasi 2.4.4 Parameter Genetik 2.5 Uraian Singkat Java 2 Standard Edition 2.5.1 Mengenal Java 2 Standard Edition 2.5.1.1 Java 2 Software Development Kit 2.5.1.2 Pemrograman Berorientasi Objek 2.5.2 Java Class - Library 2.5.3 Komponen dan Tipe Data dalam J2SE 2.5.3.1 Keyword dalam Java 2.5.3.2 Tipe Data dalam Java
9 9 10 13 14 15 16 17 20 21 21 22 23 24 25 25 26
Bab 3
PEMBAHASAN 3.1 Analisis 3.1.1 Identifikasi Masalah 3.1.2 Analisis Algoritma Genetik Pada Penjadwalan 3.1.2.1 Membangun Populasi Awal
27 27 27 28 29
Universitas Sumatera Utara
viii
3.1.2.2 Evaluasi Penalty Kromosom 3.1.2.3 Proses Regenerasi 3.1.2.4 Pengujian 3.1.3 Mapping Algoritma Genetik 3.1.4 Aliran Informasi 3.1.4.1 Context Diagram 3.1.4.2 Data Flow Diagram (DFD) Level 0 3.1.4.3 Data Flow Diagram (DFD) Level 1 3.1.5 Pemodelan Data 3.2 Perancangan 3.2.1 Lingkungan Imlementasi 3.2.2 Perancangan Antarmuka 3.2.3 Perancangan Proses
31 32 33 33 39 39 39 40 44 47 47 47 49
Bab 4
PERANCANGAN SISTEM 4.1 Hasil Perancangan Sistem 4.2 Hasil Algoritma Genetik 4.3 Evaluasi Algoritma Genetik
59 59 64 65
Bab 5
KESIMPULAN DAN SARAN 5.1 Kesimpulan 5.2 Saran
66 66 67
DAFTAR PUSTAKA
68
LAMPIRAN A. LISTING PROGRAM FORM STARTUP LAMPIRAN B. LISTING PROGRAM FORM UTAMA
70 76
Universitas Sumatera Utara
ix
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 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.17 Tabel 3.18 Tabel 3.19 Tabel 3.20 Tabel 3.21 Tabel 3.22 Tabel 3.23 Tabel 3.24 Tabel 3.25 Tabel 3.26 Tabel 3.27 Tabel 3.28 Tabel 3.29 Tabel 3.30 Tabel 3.31 Tabel 3.32 Tabel 3.33 Tabel 3.34
Contoh Crossover 1-titik Contoh Crossover 2-titik Contoh Crossover seragam Contoh Mutasi pada pengkodean biner Contoh Mutasi pada pengkodean permutasi Tabel Package yang terdapat dalam J2SE Keyword dalam Java Tipe Data dalam Java Matriks Dosen Pengajar Available Matriks Kelas Mata Kuliah Matriks Ruang Available Bobot Penalty Setiap Golongan Penalty Bobot Penalty Setiap Prioritas Deskripsi Proses Pendataan Jurusan Deskripsi Proses Pendataan Kelas Deskripsi Proses Setting Tahun Jadwal Deskripsi Proses Penentuan Durasi Kuliah Deskripsi Proses Pendataan Mata Kuliah Deskripsi Proses Penempatan Mata Kuliah Deskripsi Proses Penentuan Hari Kuliah Deskripsi Proses Penentuan Jam Kuliah Deskripsi Proses Waktu Not Available Deskripsi Proses Pendataan Ruang Kuliah Deskripsi Proses Waktu Ruang Not Available Deskripsi Proses Pendataan Dosen Deskripsi Proses Penempatan Dosen Deskripsi Proses Waktu Dosen Not Available Deskripsi Proses Penyusunan Jadwal Deskripsi Data Jurusan Deskripsi Data Kelas Deskripsi Data Dosen Deskripsi Data Pengajar Deskripsi Data Not_Dosen Deskripsi Data Mata Kuliah Deskripsi Data dt_Matakuliah Deskripsi Data SKS Deskripsi Data Kuliah Deskripsi Data Hari Deskripsi Data Jam Deskripsi Data Not_Hari Deskripsi Data Ruang Deskripsi Data Not_Ruang
16 17 17 18 18 24 25 26 30 30 30 32 32 50 50 50 51 51 51 52 52 52 53 53 53 53 54 54 55 55 55 55 56 56 56 56 56 57 57 57 57 57
Universitas Sumatera Utara
x
Tabel 3.35 Deskripsi Data Jadwal GA Tabel 3.36 Deskripsi Data Tahun
58 58
Universitas Sumatera Utara
xi
DAFTAR GAMBAR
Halaman Gambar 1.1 Gambar 2.1 Gambar 2.2 Gambar 3.1 Gambar 3.2 Gambar 3.3 Gambar 3.4 Gambar 3.5 Gambar 3.6 Gambar 3.7 Gambar 3.8 Gambar 3.9 Gambar 3.10 Gambar 3.11 Gambar 3.12 Gambar 3.13 Gambar 3.14 Gambar 3.15 Gambar 3.16 Gambar 3.17 Gambar 4.1 Gambar 4.2 Gambar 4.3 Gambar 4.4 Gambar 4.5 Gambar 4.6 Gambar 4.7 Gambar 4.8
Diagram Konsepsi Diagram Alir Algoritma Genetik Tool-Tool Dasar JDK Algoritma Penyelesaian Jadwal Kuliah Algoritma Penjadwalan Kuliah Ilustrasi Pointer Penjadwalan Kuliah Persilangan Individu Mutasi Individu Context Diagram Data Flow Diagram (DFD) Level 0 DFD Level 1 Proses Pendataan Kelas dan Jurusan DFD Level 1 Proses 2 Pendataan Kurikulum DFD Level 1 Proses 3 Waktu Perkuliahan DFD Level 1 Proses 4 Pendataan Ruang Kuliah DFD Level 1 Proses 5 Pendataan Pengajar DFD Level 1 Proses 6 Penyusunan Jadwal Kuliah Entity Relationship Database (ERD) Skema Diagram Diagram Alir Program Simulasi Penjadwalan Kuliah Flowchart Program Simulasi Penjadwalan Kuliah Menjalankan Program dari Konsole Linux Halaman Startup dan Konfigurasi Form Utama Form Simulasi Jadwal berdasarkan Personal Form Simulasi Jadwal berdasarkan Mata Kuliah Form Simulasi Jadwal berdasarkan Ruangan Form Simulasi Jadwal dengan Algoritma Genetik Form Simulasi Jadwal dengan Algoritma Genetika untuk Hasil Capaian 100% Gambar 4.9 Form Result Simulasi Jadwal
5 11 23 31 34 36 38 38 39 40 41 41 42 42 43 43 45 46 48 49 59 60 60 61 62 62 63 63 64
Universitas Sumatera Utara
Terima Kasih Tuhan buat berkatMu yang selalu menyertai disetiap langkahku hingga pada saat ini, Tulisan ini adalah karunia besar dari TanganMu. Skripsi ini kupersembahkan teristimewa untuk Ayahanda dan Ibunda tercinta yang selalu ada di hati dan di setiap langkah kecilku dan Adek-adekku tersayang Alberd Lumban Tobing dan Anggita Christiara Lumban Tobing
Januari 2010 Reynold Lumban Tobing
Universitas Sumatera Utara
