skripsi sistem penjadwalan mata kuliah …eprints.mercubuana-yogya.ac.id/852/1/bab i.pdf ·...

SKRIPSI

SISTEM PENJADWALAN MATA KULIAH

MENGGUNAKAN ALGORITMA GENETIKA

(STUDI KASUS PENJADWALAN MATA KULIAH

KELAS R1 PROGRAM STUDI TEKNIK

INFORMATIKAUMBY)

Disusun Oleh :

Nama : Martina Lova

Nim : 13111092

PROGRAM STUDI TEKNIK INFORMATIKA

FAKULTAS TEKNOLOGI INFORMASI

UNIVERSITAS MERCU BUANA YOGYAKARTA

TAHUN 2017

ii


MENGGUNAKANALGORITMA GENETIKA

(STUDI KASUS: PENJADWALAN MATA KULIAH

KELAS R1 PROGRAM STUDI TEKNIK INFORMATIKA UMBY)

Oleh:

Disusun Oleh :

Nama : Martina Lova

Nim : 13111092

Skripsi ini diajukan untuk memenuhi persyaratan akademik sarjana pada

Program Studi Teknik Informatika,

Fakultas Teknologi Informasi, Universitas Mercu BuanaYogyakarta.

Yogyakarta, Agustus 2017

Menyetujui Pembimbing

Ozzi Suria,S.T.,M.T.

NIDN. 0503019201

iii

HALAMAN PENGESAHAN


MENGGUNAKANALGORITMA GENETIKA

(STUDI KASUS: PENJADWALAN MATA KULIAH

KELAS R1 PROGRAM STUDI TEKNIK INFORMATIKA UMBY)

Oleh:

Martina Lova

13111092

Telah Dipertanggung-jawabkan dan diterima

oleh Tim Penguji pada tanggal 18- Agustus 2017

Mengetahui

Dekan, Dosen Pembimbing

(Supatman, S.T,. M.T) (Ozzi Suria, S.T,. M.T)

NIDN. 050905720 NIDN.0503019201

Dosen Penguji,

1.Supatman, S.T., M.T

NIDN. 0509057202

2.Imam Suharjo, S.T., M.Eng.

NIDN. 05099047901

3. Agus Sidiq Purnomo, S.Kom., M.Eng.

NIDN. 0511078701

iv

HALAMAN PERNYATAAN PERSETUJUAN PUBLIKASI

SKRIPSI UNTUK KEPENTINGAN AKADEMIS

Sebagai mahasiswi Universitas Mercu Buana Yogyakarta, saya yang

bertanda tangan dibawah ini :

Nama : Martina Lova

Nim : 13111092

Program Studi : Teknik Informatika

Fakultas : Teknologi Informasi

Jenis Karya : Skripsi

Demi pengembangan ilmu pengetahuan, menyetujui untuk memberikan

kepada Universitas Mercu Buaba Yogyakarta Hak Bebas Royalti Non-eksklusif

(None-exsclusive Royalty Free Right) atas kerja ilmiah saya yg berjudul :

SISTEM PENJADAWAL MATA KULIAH MENGGUNAKAN

ALGORITMA GENETIKA

(STUDI KASUS PENJADWALAN MATA KULIAH KELAS R1

PROGRAM STUDI TEKNIK INFORMATKA UMBY)

Beserta perangkat yang ada (jika diperlukan). Dengan Hak Bebas Royalti

Royalti non-ekslusive ini Universitas Mercu Buana Yogyakarta berhak

menyimpan, mengalih-media-kan mengelola dalam bentuk pangkalan data

(database), merawat dan mempublikasikan skripsi saya selama tetap

mencantumkan nama saya sebagai penulis dan sebagai pemilik hak cipta.

Demikian pernyataan ini saya buat dengan sebenarnya.

Dibuat di : Yogyakarta

Pada Tanggal :

Martina Lova

v

HALAMAN PERNYATAAN ORISINALITAS KARYA

Skripsi ini adalah hasil karya saya sendiri,

Dan semua sumber baik yang dikutip maupun yang dirujuk,

Telah saya nyatakan dengan benar.

Nama : Martina Lova

Nim : 13111092

Judul Skripsi : SISTEM PENJADWALAN MATA KULIAH



KELAS R1 PROGRAM STUDI TEKNIK

INFORMATIKA UMBY)

Program Studi : Teknik Informatika

Tanggal : Agustus 2017

Tanda Tangan :

vi

HALAMAN PERSEMBAHAN

Dengan mengucap syukur Alhamdulilah, kupersembahkan karya kecilku ini

untuk orang-orang yang kusayangi:

Bapakku Zaenuddin dan Ibuku Tursinah yang amat sangat aku sayangi,

motivator terbesar dalam hidupku yang tak pernah henti mendo’akan dan

menyayangiku, atas semua pengorbanan dan kesabaran mengantarkanku

sampai kini. Sampai aku dapat menyelesaikan pendidikan sarjanaku dengan

sangat memuaskan. Tak pernah cukup ku membalas cinta bapak dan ibu

padaku.

Nenekku tersayang yang sudah bahagia bersama kakekku disyurga yang juga

ikut merawatku memberikan kasih sayangnya kepadaku, do’akan aku mbah

semoga aku dapat menjadi wanita yang kuat dan hebat.

Kekasihku Sakti Tua Petrus Davici Banjarahhor yang sudah menemaniku sejak

oktober 2013 tepatnya tanggal 22 yang sabar membimbingku, mengajariku,

yang selalu memberikan semangat untuk menyelessaikan pendidikan

sarjanaku, dan memberikan kenangan indah dibangku kuliahku.

vii

HALAMAN MOTTO

“ Menjadi baik itu tidak mudah, menjadi tidak baik itu sangat mudah, maka

terciptalah pilihan, kita hanya memilih untuk menjadi baik atau tidak baik karna

semuanya akan ada hasilnya masing-masing dan hasil itu tidak akan berkhianat

pada pilihan yang dipilih”

viii

KATA PENGANTAR

Puji syukur kepada Tuhan Yang Maha Esa, atas segala nikmat hidup dan

kesempatan untuk menggenggam ilmu, sehingga penulis dapat menyelesaikan

skripsi yang berjudul SISTEM PENJADWALAN MATA KULIAH

MENGGUNAKAN METODE ALGORITMA GENETIKA (STUDI KASUS

PENJADWALAN MATA KULIAH KELAS R1 PROGRAM STUDI

TEKNIK INFORMATIKA UMBY). Skripsi ini disusun untuk sebagai salah

satu persyaratan untuk mencapai derajat strata satu difakultas Teknologi Informasi

di Universitas Mercu Buana Yogyakarta.

Dalam penelitian dan penyusunan skripsi ini, peneliti banyak dibantu,

dibimbing, dan didukung oleh berbagai pihak. Oleh karena itu, pada kesempatan

ini dengan peneliti sangat ingin mengucapkan terima kasih yang sebesar-besarnya

kepada:

1. Dr. Alimatus Sahrah, M.Si., MM., selaku rektor Universitas Mercu Buana

Yogyakrta.

2. Supatman, S.T.,M.T., selaku dekan Fakultas Teknologi Informasi

Universitas Mercu Buana Yogyakarta.

3. Ozzi Suria, S.T,. M.T selaku dosen pembimbing skripsi yang super

sabar dalam penyelesaian penulisan skripsi ini.

4. Seluruh dosen Fakultas Teknologi yang telah membina dan mengajar

peneliti dengan wawasan dan penuh kesabaran.

5. Tim Penguji yang membantu peneliti dalam kelancaran ujian skripsi

ini.

6. Orang tua yang selalu memberikan motovasi dalam bentuk dorongan

agar tidak mudah putus asa dalam mengerjakan skripsi dan selalu

mendoakan untuk kelancaran penelitian ini.

7. Sakti Tua Pertus Davici Banjarnahor yang menjadi penyemangat

dalam mengerjakan skripsi ini.

ix

8. Seluruh Pemimpin dan staff Direktorat Marketing Universitas Mercu

Buana Yogyakarta yang memberikan semangat untuk tetap tekun

dalam pengerjaan skripsi ini.

9. Megawati Rahayu, Sholahuddin Al-ayubbi, Gita Angeline Mutiara

Zam zam sebagai sahabat yang selalu memberi semangat dan

memberikan dorongan moral dalam pengerjaan skripsi ini.

10. Seluruh teman mahasiswa Fakultas Teknologi Informasi Mercu Buana

Yogyakarta yang memberikan semangat dalam pengerjaan skripsi ini.

11. Semua pihak yang tidak dapat penulis sebutkan satu persatu.

Terima kasih atas semua bantuan dan dukungannya, akhir kata penulis

berharap hasil penelitian berupa skripsi ini dapat memberikan manfaat bagi

perkembangan ilmu pengetahuan, dan memberikan inspirasi untuk kemajuan

teknologi Indonesia. Amin.

Yogyakarta, 18 Agustus 2017

Peneliti

x




KELAS R1 PROGRAM STUDI TEKNIK INFORMATIKAUMBY)

1. Peneliti 1 (Martina Lova, 13111092, [email protected])

2. Peneliti 2(Ozzi Suria, S.T,. M.T, 0503019201, [email protected])

ABSTRAK

Masalah penjadwalan dalam dunia pendidikan dapat dibagi menjadi dua

kategori, yaitu penjadwalan matakuliah dan ujian. Penyelesaian masalah

penjadwalan perkuliahan dalam jumlah yang sangat besar hingga saat ini masih

menjadi permasalahan yang rumit untuk diselesaikan secara manual.

Algoritma genetik adalah algoritma yang berusaha menerapkan pemahaman

mengenai evolusi alamiah pada tugas-tugas pemecahan-masalah (problem

solving). Pendekatan yang diambil oleh algoritma ini adalah dengan

menggabungkan secara acak berbagai pilihan solusi terbaik di dalam suatu

kumpulan untuk mendapatkan generasi solusi terbaik berikutnya yaitu pada suatu

kondisi yang memaksimalkan kecocokannya atau lazim disebut fitness. Generasi

ini akan merepresentasikan perbaikan-perbaikan pada populasi awalnya. Dengan

melakukan proses ini secara berulang, algoritma ini diharapkan dapat

mensimulasikan proses evolusioner.

Penelitian penjadwalan matakuliah menggunakan algoritma genetika (studi

kasus progran studi Teknik Informatika Universitas Mercu Buana Yogyakara)

adalah dengan memasukan jumlah nilai kromosom, jumlah generasi, jumlah

crossover rate, dan mutation rate. Dari hasil uji coba dalam penelitian ini dengan

menggunakan jumlah kromosom dari yang terkecil 4 dan yang terbesar 15, jumlah

generasi dari yang terkecil 10 dan yang terbesar 50, nilai crossover rate 0.3 dan

0.5, nilai mutation rate 0.25 dan banyak generasi yang bervariasi. Diperoleh hasil

terbaik yaitu pada uji coba ke-3 dengan nilai kromosom 15, nilai generasi 10,

nilai crossover rate 0.5 dan nilai mutation rate 0.25 dngan hasil 70%. Dari hasil

yang diperoleh dalam penelitian ini di harapakan dapat menyelesaikan

permasalahan penjadwalan mata kuliah.

Kata Kunci :Penjadwalan, Matakuliah, Algoritma Genetika

mailto:[email protected]

mailto:[email protected]

xi

DAFTAR ISTILAH

No ISTILAH KETERANGAN

1 Crossover Operator algoritma genetika yang membutuhkan

parameter dua kromosom.

2 Fitness Fungsi yang digunakan untuk mengukur nilai kecocokan

suatu kromosom.

3 Gen nilai yang terdapat pada kromosom

4 Individu Kromosom yang terdiri dari unit-unit yang dinamakan

gen .

5 Kromosom Merupakan suatu solusi yang mempunyai nilai atau gen .

6 Mutasi Operator yang membutuhkan satu parameter

7 Populasi Kumpulan individu yang sejenis

xii

DAFTAR ISI

HALAMAN PENGESAHAN ............................................................................ iii

HALAMAN PERNYATAAN PERSETUJUAN PUBLIKASI SKRIPSI UNTUK

KEPENTINGAN AKADEMIS ......................................................................... iv

HALAMAN PERNYATAAN ORISINALITAS KARYA ................................ v

HALAMAN PERSEMBAHAN ........................................................................ vi

HALAMAN MOTTO ....................................................................................... vii

KATA PENGANTAR ..................................................................................... viii

ABSTRAK .......................................................................................................... x

DAFTAR ISTILAH ........................................................................................... xi

DAFTAR ISI ..................................................................................................... xii

DAFTAR TABEL ............................................................................................ xiv

DAFTAR GAMBAR ....................................................................................... xvi

DAFTAR LAMPIRAN ................................................................................... xvii

BAB I PENDAHULUAN .................................................................................. 1

1.1 Latar Belakang. .................................................................................................. 1

1.2 Perumusan Masalah. ......................................................................................... 2

1.3 Tujuan Penelitian. .............................................................................................. ..2

1.4 Manfaat Penelitian. ........................................................................................... ..2

BAB II TINJAUAN PUSTAKA DAN LANDASAN TEORI ............................

2.1 Tinjauan Pustaka. ....................................................................................................... ...

2.2 Landasan Teori. .................................................................................................... ...

2.2.1 Sistem ..............................................................................................................

2.2.2 Jadwal .............................................................................................................

2.2.3 Algoritma Genetika. ........................................................................................

2.2.4 Hal yang harus dilakukan dalam Algoritma Genetika ...................................

2.2.5 Penyilangan (Crossover) ................................................................................

2.2.6 Mutasi ............................................................................................................

BAB III METODOLOGI .....................................................................................

3.1 Data Penelitian ...........................................................................................................

3.2 Alat Penelitian ............................................................................................................

xiii

3.3 Jalan Penelitian ..........................................................................................................

3.3.1 Input Data.......................................................................................................

3.3.2 Menentukan Nilai Krormoson, Nilai Generasi, Crossover Rate dan Mutation

Rate. 17

3.3.3 Fitness .............................................................................................................

3.3.4 Seleksi .............................................................................................................

3.3.5 Crossover ........................................................................................................

3.3.6 Mutasi .............................................................................................................

3.4 Rancangan Tabel ..................................................................................................

3.5 Relasi Database ...................................................................................................

3.6 Data Flow Diagram (DFD) ..................................................................................

3.7 Sistem Antarmuka Perangkat Lunak ....................................................................

BAB IV ANALISIS DAN PEMBAHASAN .......................................................

4.1 Hasil Penelitiaan ........................................................................................................

4.1.1 Data Matakuliah .............................................................................................

4.1.2 Data Ruang.....................................................................................................

4.1.3 Data Dosen ......................................................................................................

4.1.4 Data Jam Perkuliahan ....................................................................................

4.1.5 Hasil Pengujian ..............................................................................................

4.2 Tabel Hasil Kesimpulan .............................................................................................

BAB V PENUTUP ...............................................................................................

5.1 Kesimpulan ..........................................................................................................

5.2 Saran ....................................................................................................................

DAFTAR PUSTAKA ...........................................................................................

LAMPIRAN ..........................................................................................................

Lampiran A Biodata Peneliti ...........................................................................................

Lampiran B Scan Dokumen Bimbingan Skripsi ..............................................................

Lampiran C Jadwal Kuliah .............................................................................................

Lampiran D Source Code .................................................................................................

xiv

DAFTAR TABEL

Tabel 3.1 Spesifikasi Alat Penelitian.....................................................................15

Tabel 3.1 Contoh Jadwal.......................................................................................17

Tabel 3.2 Tabel Admin ......................................................................................... 22

Tabel 3.3 Tabel Dosen .......................................................................................... 22

Tabel 3.4 Tabel Hari ............................................................................................. 22

Tabel 3.5 Tabel Jadwal ......................................................................................... 23

Tabel 3.6 Tabel Jam .............................................................................................. 23

Tabel 3.7 Tabel Kelas ........................................................................................... 23

Tabel 3.8 Tabel Kuliah .......................................................................................... 23

Tabel 3.9 Tabel Matkul ......................................................................................... 23

Tabel 3.10 Tabel Ruang ........................................................................................ 24

Tabel 3.11 Tabel Temp ......................................................................................... 24

Tabel 3.12 Tabel Waktu ........................................................................................ 24

Tabel 4.1 Matakuliah semester 1...........................................................................25








Tabel 4.9 Matakuliah Pilihan................................................................................30

Tabel 4.10 Tabel Keterangan Nilai Kriteria .........................................................33

Tabel 4.11 Tabel Keterangan Masing-masing kriteria..........................................34

Tabel 4.12 Tabel Hasil Pengujian Kromosom sedikit dan Generasi sedikit.........35

Tabel 4.13 Tabel Keterangan Kriteria Masing- Masing kriteria...........................35

Tabel 4.14 Tabel Hasil Pengujian Kromosom sedikit ..........................................36

Tabel 4.15 Tabel Keterangan Kriteria Masing- Masing kriteria............................37

Tabel 4.16 Tabel Hasil Pengujian Kromoson Sedikit Generasi Banyak...............37

xv


Tabel 4.18 Tabel Hasil Pengujian Kromoson Sedikit Generasi Banyak...............38


Tabel 4.20 Tabel Hasil Pengujian Kromoson Banyak Generasi Sedikit...............39


Tabel 4.22 Tabel Hasil Pengujian Kromoson Banyak Generasi Sedikit...............40


Tabel 4.24 Tabel Hasil Pengujian Kromoson Banyak Generasi Banyak...............41


Tabel 4.26 Tabel Hasil Pengujian Kromoson Banyak Generasi Banyak...............43

Tabel 4.27 Tabel Hasil Pengujian .........................................................................43

xvi

DAFTAR GAMBAR

Gambar 2.1 Diagram Alur Algoritma Genetika ............................................... 7

Gambar 2.2 Diagram Alur Proses Crossover ................................................... 12

Gambar 2.3 Diagram Proses Mutasi ................................................................ 13

Gambar 2.4 Diagram Alur Penjadwalan Mata Kuliah .................................... 16

Gambar 3.2 Rancangan Tabel .......................................................................... 22

Gambar 3.3 Relasi Database............................................................................ 23

Gambar 3.4 Data Flow Diagram ...................................................................... 23

Gambar 3.5 Sistem Antar Muka....................................................................... 24

Gambar 3.6 Sistem Antar Muka Penjadwalan ................................................. 24

Gambar 4.1 Ruang Kelas ................................................................................. 31

Gambar 4.2 Data Dosen ................................................................................... 32

Gambar 4.3 Data Hari ...................................................................................... 32

Gambar 4.4 Data Jam Kuliah ........................................................................... 33

Gambar d.1 Kode Fitur Data Matakuliah ......................................................... 7

Gambar d.2 Kode Fitur Data Dosen ................................................................. 7

Gambar d.3 Kode Fitur Perhitungan AG ......................................................... 8

Gambar d.4 Kode Fitur Penyimpanan Ke ....................................................... 8

Gambar d.5 Kode Fitur Jam ............................................................................. 9

Gambar d.6 Kode Fitur Kelas .......................................................................... 9

xvii

DAFTAR LAMPIRAN

Lampiran A Biodata Peneliti ................................................................................. 1

Lampiran B Scan Dokumen Bimbingan .............................................................. 2

Lampiran C jadwal Kuliah .................................................................................... 3

Lampiran D Source Kode...................................................................................... 7

1

BAB I

PENDAHULUAN

1.1 Latar Belakang.

Pengaturan waktu terhadap suatu kegiatan merupakan hal yang penting

dilakukan agar kegiatan tersebut berlangsung secara lancar. Pengaturan waktu

tersebut biasa disebut penjadwalan. Penyusunan jadwal kegiatan berkaitan dengan

berbagai batasan/kendala yang harus dipenuhi sehingga memerlukan banyak

pertimbangan untuk mendukung kegiatan tersebut. Sebagian besar kasus

penentuan jadwal yang bisa diterapkan sangat sulit dicapai karena terkadang

sumber daya waktu, tempat, orang, tidak sesuai dengan kebutuhan. metode yang

digunakan untuk menyelesaikan masalah penjadwalan ini adalah menggunakan

pendekatan algoritma genetika. Beberapa Hal yang perlu dipertimbangkan untuk

menyusun jadwal (dalam hal ini mata kuliah) adalah dosen, ruang, mata kuliah,

jam, dan hari. Algoritma genetika merupakan pendekatan komputasional untuk

menyelesaikan masalah yang dimodelkan dengan proses biologi dari evolusi.

Algoritma ini biasa digunakan untuk proses optimasi dan pencarian hasil yang

terbaik (Soenandi, 2013).

Masalah penjadwalan mata kuliah dalam dunia pendidikan sering kali

terjadi. Dalam penilitian ini mencoba untuk menyelesaikan permasalahan

pembuatan jadwal perkuliahan. Penyelesaian masalah penjadwalan perkuliahan

dalam jumlah yang sangat besar hingga saat ini masih menjadi permasalahan yang

rumit untuk diselesaikan secara manual (Wiga dkk, 2013).

Penjadwalan pada umumnya diperlukan untuk mengantisipasi adanya

benturan jam kuliah dan juga waktu dosen dalam mengajar. Jadwal yang

dihasilkan juga harus memenuhi batasan dan syarat yang bertujuan agar jadwal

yang dihasilkan sesuai saat digunakan. Masalah penjadwalan merupakan

persoalan yang ditemukan pada situasi nyata. Masalah ini membutuhkan waktu

komputasi yang cukup tinggi untuk pencarian solusinya, terlebih lagi jika ukuran

permasalahan semakin besar dengan bertambahnya jumlah komponen dan tetapan

2

atau syarat yang ditentukan oleh institusi tempat jadwal tersebut digunakan

(Cahya, 2016).

1.2 Perumusan Masalah.

Rumusan masalah untuk penelitian sistem penjadwalan mata kuliah

menggunakan metode algortirma genetika adalah segabai berikut :

1. Bagaimana mendapatkan optimasi penjadwalan mata kuliah dengan

menggunakan algoritma genetika?

2. Bagaimana membuat sistem Penjadwalan mata kuliah dan kombinasi

terbaik antara pasangan antara mata kuliah, dosen pengajar, mahasiswa

yang mengambil mata kuliah, dan ruangan yang tersedia?

3. Bagaimana merancang gen, kromosom, individu dan populasi?

4. Bagaimana menentuka aturan-aturan yang tidak boleh dilanggar di

dalam pembuatan jadwal serta nilai pinaltinya untuk diterapkan dalam

fungsi nilai fitness?

5. Bagaimana menentukan calon parent individu yang mengalami mutasi

dan crossover pada kromosom individu?

1.3 Tujuan Penelitian.

Penelitian ini bertujuan untuk membangun sistem penjadwalan matakuliah

dengan mengimplementasikan Algoritma genetika.

1.4 Manfaat Penelitian.

Melalui hasil penelitian yang diperoleh maka adapun manfaat yang dapat

diperoleh dari penelitian ini adalah sistem ini dapat menghasilkan jadwal mata

kuliah dengan nilai error yang kecil.

skripsi sistem penjadwalan mata kuliah …eprints.mercubuana-yogya.ac.id/852/1/bab i.pdf ·...

Documents