PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI

PENJADWALAN MATA KULIAH MENGGUNAKAN ALGORITMA PARTICLE SWARM OPTIMIZATION (Studi Kasus Program Studi Pendidikan Guru Sekolah Dasar,

Universitas Sanata Dharma, Yogyakarta)

SKRIPSI Diajukan untuk Memenuhi Salah Satu Syarat Memperoleh Gelar Sarjana Komputer Program Studi Teknik Informatika

oleh Antonius Rianditya Putra

10 5314 044

PROGRAM STUDI TEKNIK INFORMATIKA JURUSAN TEKNIK INFORMATIKA FAKULTAS SAINS DAN TEKNOLOGI UNIVERSITAS SANATA DHARMA YOGYAKARTA 2015 i


COURSE SCHEDULING USING PARTICLE SWARM OPTMIZATION ALGORITHM (Case Study at Primary School Teacher Education Study Program,

Sanata Dharma University, Yogyakarta)

Thesis Presented as Partial Fullfillment of the Requirements To Obtain Sarjana Komputer Degree In Department of Informatics Engineering

By : Antonius Rianditya Putra

10 5314 044

INFORMATICS ENGINEERING STUDY PROGRAM DEPARTMENT OF INFORMATICS ENGINEERING FACULTY OF SCIENCE AND TECHNOLOGY SANATA DHARMA UNIVERSITY YOGYAKARTA 2015

ii


iii


iv


.

HALAMAN PERSEMBAHAN

“Ketika dirimu tidak merasa lelah, berarti kamu sedang tidak

memperjuangkan sesuatu”

“To accomplish great things, we must not only act, but also dream, not only plan, but also believe” -Anatole France-

Knowledge is Power

Skripsi ini ku persembahkan untuk : Yesus Kristus Papa, Mama, kakak dan adikku Sahabat dan Teman-teman

Terima Kasih Semua ....

v


PERNYATAAN KEASLIAN KARYA

Saya menyatakan dengan sesungguhnya bahwa skripsi yang saya tulis ini tidak memuat karya orang lain, kecuali yang telah disebutkan dalam kutipan daftar pustaka , sebagaimana layaknya karya ilmiah.

Yogyakarta , 27 Januari 2015 Penulis

Antonius Rianditya Putra

vi


LEMBAR PERNYATAAN PERSETUJUAN PUBLIKASI KARYA ILMIAH UNTUK KEPENTINGAN AKADEMIS

Yang bertanda tangan di bawah ini , saya mahasiswa Universitas Sanata Dharma: Nama

: Antonius Rianditya Putra

Nomor mahasiswa

: 105314044

Demi pengembangan ilmu pengetahuan, saya memberikan kepada Perpustakaan Universitas Sanata Dharma karya ilmiah saya yang berjudul : “PENJADWALAN MATA KULIAH MENGGUNAKAN ALGORITMA PARTICLE SWARM OPTIMIZATION (Studi Kasus Program Studi Pendidikan Guru Sekolah Dasar Universitas Sanata Dharma, Yogyakarta)” beserta perangkat yang diperlukan (bila ada). Dengan demikian saya memberikan kepada Perpustakaan Universitas Sanata Dharma hak untuk menyimpan, mengalihkan dalam bentuk media lain, mengelolanya dalam bentuk pangkalan data, mendistribusikan secara terbatas, dan mempublikasikannya di Internet atau media lain untuk kepentingan akademis tanpa perlu meminta ijin dari saya maupun memberikan royalti kepada saya selama tetap mencantumkan nama saya sebagai penulis.

Demikian pernyataan ini saya buat dengan sebenarnya. Yogyakarta,

29 Januari 2015

Yang menyatakan

Antonius Rianditya Putra

vii


ABSTRAK Banyak faktor yang berpengaruh dalam pembuatan jadwal mata kuliah seperti dosen, mahasiswa, mata kuliah, permintaan ruang dan waktu serta jumlah ruang dan waktu yang tersedia. Namun dalam pembuatan jadwal mata kuliah, masih dilakukan secara manual. Hal ini mengakibatkan proses pembuatan jadwal membutuhkan ketelitian dan membutuhkan waktu yang sangat lama dalam pembuatan jadwal setiap semesternya. Dalam penelitian ini, dikembangkan sebuah Sistem Penjadwalan Mata Kuliah yang berfungsi membantu pihak Sekretariat PGSD dalam pembuatan jadwal menggunakan algoritma Particle Swarm Optimization (PSO). Metode PSO merupakan metode dengan membangkitkan populasi partikel di awal iterasi dan pada setiap iterasi, partikel-partikel tersebut memperbaiki posisinya menuju posisi terbaik, yaitu posisi mata kuliah yang memenuhi semua batasan hard constraint. Hasil akhir yang diperoleh adalah sebuah Sistem Penjadwalan Mata Kuliah Menggunakan Algoritma Particle Swarm Optimization (PSO) pada Program Studi Pendidikan Guru Sekolah Dasar di Universitas Sanata Dharma Yogyakarta yang menghasilkan jadwal dengan memenuhi hard constraint dan meminimalkan waktu pembuatan jadwal mata kuliah.

Kata kunci : Particle Swarm Optimization, matakuliah, jadwal, partikel.

viii


ABSTRACT There are several influential factors in the forming of scheduling, such as lecturers, students, subjects, room and time request and the availability of those rooms and time. However, in the forming of lecturing time-table, everything is done manually. As a result, the scheduling process requires extra precision and consumes extra time for each semester. This study is developing a System of Course Scheduling which is expected to help the secretariat of Elementary School Study Program (PGSD) in creating the course schedule using Particle Swarm Optimization algorithm. PSO method is a method which evokes the population of particles in the beginning of iteration, the particles repair its position to the best position, which is position of the courses are meets all hard constraint limitation. The final result is a Course Scheduling System Using The Particle Swarm Optimization (PSO) has been made for the Study Program of Primary School Teacher Education in Sanata Dharma University in Yogyakarta, which generates schedules that fulfill the hard constraint and minimize the time of making.

Keyword : Particle Swarm Optimization, Courses, Schedule, Particle.

ix


KATA PENGANTAR

Puji dan syukur senantiasa penulis haturkan kepada Tuhan Yesus Kristus karena hanya dengan anugerah, berkat, kasih, dan pertolongan-Nya penulis dapat menyelesaikan penelitian dan penyusunan skripsi yang berjudul “Penjadwalan matakuliah menggunakan algoritma Particle Swarm Optimization (Studi Kasus Program Studi Pendidikan Guru Sekolah Dasar Universitas Sanata Dharma Yogyakarta)”. Skripsi ini disusun guna memenuhi salah satu syarat untuk memperoleh gelar Sarjana Strata Satu Program Studi Teknik Informatika (S.Kom). Terselesaikannya penulisan laporan akhir ini tidak lepas dari bantuan berbagai pihak yang telah membantu penulis. Oleh karena itu, penulis mengucapkan terima kasih kepada : 1.

Tuhan Yesus Kristus dan Bunda Maria yang selalu memberikan anugerah, rahmat, dan kekuatan sehingga penulis dapat menyelesaikan penelitian dan penyusunan skripsi ini hingga selesai.

2.

Kedua orang tua saya, Agustinus Supriyadi, S.Pd., dan Marcella Ety Widajanti, S.Pd., kakak ku Laurensius Widi Andhika Putra, S.Farm., Apt., dan adik ku Irene Melani Putri yang selalu memberikan curahan kasih sayang tak terhingga, doa, dukungan baik moral maupun moril kepada penulis.

3.

Ibu P.H. Prima Rosa, S.Si., M.Sc., selaku Dekan Fakultas Sains dan Teknologi Universitas Sanata Dharma.

4.

Ibu Ridowati Gunawan, S.Kom., M.T., selaku Ketua Jurusan Teknik Informatika, Universitas Sanata Dharma.

x


5.

Bapak Alb. Agung Hadhiatma, S.T., M.T. selaku dosen pembimbing saya yang selalu memberikan bimbingan, dukungan, waktu dan saran.

6.

Seluruh Dosen Universitas Sanata Dharma, Dosen yang mengajar jurusan Teknik Informatika khususnya yang telah mengajarkan banyak ilmu kepada penulis.

7.

Team Penjadwalan, H.Roy Wiranata, Aweng dan Damai yang telah berjuang bersama-sama dan membantu penulisan skripsi ini.

8. Mafia Tangerang, Erick, Bella, Andy, Diky, dan Shela yang selalu memberikan semangat dengan kata-kata “Kapan maju Sidang? Tenang masih sampai 14 semester, gak usah buru-buru”. 9.

Semua teman-teman TI angkatan 2010, khususnya Tomi, Kristopel, Krisma, Radikstya, serta teman-teman Heavenly Shin dan teman-teman Josefic yang selalu memberikan dukungan dalam penulisan skripsi ini.

10. Serta semua pihak yang telah banyak membantu penyusunan skripsi ini yang tidak dapat disebutkan satu per satu. Penulis menyadari bahwa penulisan skripsi ini masih banyak kekurangan dan kelemahan karena keterbatasan pikiran, tenaga, dan waktu penulis. Untuk itu penulis mengharapkan saran dan kritik yang membangun dari semua pihak. Akhir kata semoga skripsi ini dapat berguna dan bermanfaat bagi pembaca semua.

Yogyakarta,

Penulis

xi


DAFTAR ISI

HALAMAN JUDUL................................................................................................ i HALAMAN PERSETUJUAN ............................................................................... iii HALAMAN PENGESAHAN .............................................................................. iv HALAMAN PERSEMBAHAN ............................................................................. v PERNYATAAN KEASLIAN KARYA ................................................................ vi LEMBAR PERNYATAAN PERSETUJUAN PUBLIKASI ILMIAH UNTUK KEPENTINGAN AKADEMIS ............................................................................ vii ABSTRAK ........................................................................................................... viii ABSTRACT ........................................................................................................... ix KATA PENGANTAR ............................................................................................ x DAFTAR ISI ......................................................................................................... xii DAFTAR GAMBAR ............................................................................................ xv DAFTAR TABEL ............................................................................................... xvii BAB I PENDAHULUAN ....................................................................................... 1 1.1.

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

1.2.

Rumusan Masalah .................................................................................... 3

1.3.

Batasan Masalah ....................................................................................... 3

1.4.

Tujuan Penelitian ...................................................................................... 4

1.5.

Metodologi Penelitian .............................................................................. 4

1.6.

Sistematika Penulisan ............................................................................... 5

BAB II LANDASAN TEORI ................................................................................. 7 2.1.

Penjadwalan .............................................................................................. 7

2.2.

Particle Swarm Optimization ................................................................... 9

2.2.1.

Penjelasan algoritma Particle Swarm Optimization .......................... 9

2.2.2.

Proses Algoritma Particle Swarm Optmization .............................. 12

2.2.3.

Cara Kerja Algoritma Particle Swarm Optimization ...................... 14

BAB III ANALISA DAN PERANCANGAN SISTEM ....................................... 18 3.1.

Analisis Sistem ....................................................................................... 18

xii


3.1.1.

Analisis Masalah ............................................................................. 18

3.1.2.

Aturan Penjadwalan ........................................................................ 19

3.2.

Pemodelan Algoritma Particle Swarm Optimization untuk penjadwalan 20

3.2.1. Memploting matakuliah secara random (Pembangkitan posisi dan kecepatan awal) ............................................................................................. 22 3.2.2.

Menentukan nilai fitness masing-masing partikel ........................... 38

3.2.3.

Proses Update Velocity dan Posisi .................................................. 44

3.2.4.

Stopping Condition ......................................................................... 49

3.3.

Analisa Kebutuhan Sistem ..................................................................... 50

3.3.1.

Spesifikasi Perangkat Keras ............................................................ 50

3.3.2.

Spesifikasi Perangkat Lunak ........................................................... 50

3.4.

Sumber Data ........................................................................................... 50

3.5.

Perancangan Sistem ................................................................................ 61

3.5.1 Diagram Use Case ................................................................................ 62 3.5.2

Narasi Use Case .............................................................................. 64

3.5.3 Diagram Activity untuk setiap use case ................................................ 73 3.5.4 Model Kelas Analisis ........................................................................... 86 3.5.5 Diagram Kelas ...................................................................................... 87 3.6 Perancangan Basis Data .............................................................................. 94 3.6.1 ER Diagram .......................................................................................... 94 3.6.2 Hubungan Relasi Antar Tabel .............................................................. 95 3.6.3 Model Fisikal (Struktur Tabel dalam DBMS) ..................................... 96 3.6.4 Desain Model Interaksi Antar Kelas .................................................. 100 3.7 Desain Antar Muka ................................................................................... 110 1.

Tampilan Halaman Utama ................................................................ 110

2.

Tampilan Mata Kuliah ...................................................................... 111

3.

Tampilan Dosen ................................................................................ 112

4.

Tampilan Ruang ................................................................................ 112

5.

Tampilan Lihat Jadwal...................................................................... 113

6.

Tampilan Kelas Matakuliah .............................................................. 115

xiii


7.

Tampilan Permintaan Kelas .............................................................. 116

8.

Tampilan Buat Jadwal ...................................................................... 117

BAB IV IMPLEMENTASI DAN ANALISIS SISTEM .................................... 118 4.1 Implementasi Sistem ................................................................................. 118 4.1.1

Home ............................................................................................. 118

4.1.2

Data Mata Kuliah ......................................................................... 119

4.1.3

Data Dosen .................................................................................... 124

4.1.4

Data Ruang .................................................................................... 130

4.1.5

Data Kelas Matakuliah .................................................................. 134

4.1.6

Pilih Permintaan ............................................................................ 140

4.1.7

Buat Jadwal ................................................................................... 148

4.18

Jadwal............................................................................................ 165

4.2 Analisis Sistem .......................................................................................... 169 4.2.1 Uji Coba ........................................................................................... 169 BAB V KESIMPULAN DAN SARAN .............................................................. 192 5.1 Kesimpulan ............................................................................................... 192 5.2 Saran .......................................................................................................... 193 DAFTAR PUSTAKA ......................................................................................... 194 LAMPIRAN ........................................................................................................ 196

xiv


DAFTAR GAMBAR Gambar 3. 1 Algoritma PSO dalam pembuatan jadwal ....................................... 21 Gambar 3. 2 Konfigurasi Sistem ........................................................................... 61 Gambar 3. 3 Use Case Diagram ............................................................................ 62 Gambar 3. 4 Model Kelas Analisis ....................................................................... 86 Gambar 3. 5 ER Diagram ...................................................................................... 94 Gambar 3. 6 Hubungan relasi antar table .............................................................. 95 Gambar 3. 7 Tampilan Menu Utama................................................................... 110 Gambar 3. 8 Menu Matakuliah ........................................................................... 111 Gambar 3. 9 isi Tabel Matakuliah ....................................................................... 111 Gambar 3. 10 Menu Tampilan Dosen ................................................................. 112 Gambar 3. 11 Menu Tampilan Ruang ................................................................. 112 Gambar 3. 12 Tampilan Lihat Jadwal Mahasiswa .............................................. 113 Gambar 3. 13 Tampilan Lihat Jadwal Dosen ...................................................... 114 Gambar 3. 14 Tampilan Kelas Matakuliah ......................................................... 115 Gambar 3. 15 Tampilan Permintaan Kelas ......................................................... 116 Gambar 3. 16 Tampilan Buat Jadwal .................................................................. 117 Gambar 4. 1 Home .............................................................................................. 118 Gambar 4. 2 Data Matakuliah ............................................................................. 119 Gambar 4. 3 Tabel Data Matakuliah ................................................................... 120 Gambar 4. 4 Pesan cek data belum terisi ............................................................ 124 Gambar 4. 5 Data Dosen ..................................................................................... 125 Gambar 4. 6 Data Ruang ..................................................................................... 130 Gambar 4. 7 Pesan cek data belum terisi ............................................................ 133 Gambar 4. 8 Data Kelas Matakuliah ................................................................... 135 Gambar 4. 9 Data Dosen ..................................................................................... 136 Gambar 4. 10 Data Permintaan ........................................................................... 142 Gambar 4. 11 Tabel Matakuliah direncanakan ................................................... 142 Gambar 4. 12 Pesan cek belum terpilih jumlah kelas ......................................... 144 Gambar 4. 13 Buat Jadwal .................................................................................. 148 Gambar 4. 14 Jadwal Pilihan Dosen ................................................................... 166 Gambar 4. 15 Jadwal Pilihan Mahasiswa ........................................................... 167 Gambar 4. 16 Tabel Pelanggaran ........................................................................ 167 Gambar 4. 17 Buat Jadwal .................................................................................. 169 Gambar 4. 18 Grafik Fitness parameter 1 ........................................................... 172 Gambar 4. 19 Grafik Fitness parameter 2 ........................................................... 173 Gambar 4. 20 Grafik fitness parameter 3 ............................................................ 175 Gambar 4. 21 Grafik fitness parameter 4 ............................................................ 176 Gambar 4. 22 Grafik fitness parameter 5 ............................................................ 178 Gambar 4. 23 Grafik Fitness perbandingan ........................................................ 178 Gambar 4. 24 Grafik fitness 10 partikel .............................................................. 180 xv


Gambar 4. 25 Grafik fitness 8 partikel ................................................................ 181 Gambar 4. 26 Grafik fitness 5 partikel ................................................................ 183 Gambar 4. 27 Grafik fitness perbandingan antar partikel ................................... 183 Gambar 4. 28 Grafik fitness dengan 13 ruang .................................................... 185 Gambar 4. 29 Grafik fitness dengan 8 ruang ...................................................... 186 Gambar 4. 30 Grafik fitness perbandingan 13 dan 8 ruang ................................ 187

xvi


DAFTAR TABEL Tabel 3. 1 Tabel Data hari ..................................................................................... 23 Tabel 3. 2 Tabel data waktu .................................................................................. 23 Tabel 3. 3 Tabel data struktur time slot................................................................. 24 Tabel 3. 4 Tabel data Struktur Matriks time slot dengan Ruang .......................... 25 Tabel 3. 5 Tabel Dosen ......................................................................................... 26 Tabel 3. 6 Tabel Kelas Matakuliah ....................................................................... 26 Tabel 3. 7 Tabel Slot Matakuliah .......................................................................... 27 Tabel 3. 8 Nilai Posisi awal................................................................................... 28 Tabel 3. 9 Tabel pembangkitan posisi dan velocity jadwal matakuliah ............... 29 Tabel 3. 10 Posisi baru jadwal matakuliah ........................................................... 49 Tabel 3. 11 Tabel Data NIP dan Nama Dosen ...................................................... 51 Tabel 3. 12 Tabel Data Matakuliah, Nama Matakuliah, SKS dan JP Semester 1 53 Tabel 3. 13 Tabel Data Matakuliah, Nama Matakuliah, SKS dan JP Semester 2 54 Tabel 3. 14 Tabel Data Matakuliah, Nama Matakuliah, SKS dan JP Semester 3 55 Tabel 3. 15 Tabel Data Matakuliah, Nama Matakuliah, SKS dan JP Semester 4 56 Tabel 3. 16 Tabel Data Matakuliah, Nama Matakuliah, SKS dan JP Semester 5 57 Tabel 3. 17 Tabel Data Matakuliah, Nama Matakuliah, SKS dan JP Semester 6 58 Tabel 3. 18 Tabel Data Matakuliah, Nama Matakuliah, SKS dan JP Semester 7 58 Tabel 3. 19 Tabel Data Matakuliah, Nama Matakuliah, SKS dan JP Semester 8 59 Tabel 3. 20 Tabel Ruang Kelas ............................................................................. 60 Tabel 4. 1 Parameter 1 w=0.4 ............................................................................. 171 Tabel 4. 2 Hasil Uji coba parameter 1................................................................. 171 Tabel 4. 3 Tabel parameter 2, w=0.5 .................................................................. 172 Tabel 4. 4 Hasil Ujicoba parameter 2.................................................................. 173 Tabel 4. 5 Tabel parameter 3, w=0.6 .................................................................. 174 Tabel 4. 6 Hasil Ujicoba parameter 3.................................................................. 174 Tabel 4. 7 Tabel parameter 4, w=1 ..................................................................... 175 Tabel 4. 8 Hasil Ujicoba parameter 4.................................................................. 176 Tabel 4. 9 Tabel parameter 5, w = 1.4 ................................................................ 177 Tabel 4. 10 Hasil Ujicoba parameter 5................................................................ 177 Tabel 4. 11 Tabel parameter 1 , 10 partikel ........................................................ 179 Tabel 4. 12 Hasil Ujicoba parameter 1................................................................ 179 Tabel 4. 13 Tabel parameter 2 , 8 partikel .......................................................... 180 Tabel 4. 14 Hasil Ujicoba parameter 2................................................................ 181 Tabel 4. 15 Tabel parameter 3, 5 partikel ........................................................... 182 Tabel 4. 16 Hasil Ujicoba parameter 3................................................................ 182 Tabel 4. 17 Tabel parameter 1, 13 ruang ............................................................ 184 Tabel 4. 18 Hasil Ujicoba parameter 1, 13 ruang ............................................... 184 Tabel 4. 19 Tabel parameter 2, 8 ruang .............................................................. 185

xvii


Tabel 4. 20 Hasil Ujicoba parameter 2, 8 ruang ................................................. 186

xviii


BAB I PENDAHULUAN

1.1.

Latar Belakang Penjadwalan adalah suatu proses membuat suatu urutan aktivitas yang berfungsi untuk menyelesaikan sekumpulan pekerjaan dengan waktu yang optimal (Morton,1993). Jadwal mata kuliah menjadi salah satu bagian terpenting dalam proses belajar mengajar suatu lembaga pendidikan, termasuk di dalam Program Studi Pendidikan Guru Sekolah Dasar di Universitas Sanata Dharma Yogyakarta. Pada pelaksaanaannya, seringkali jadwal yang telah dikeluarkan belum fix sehingga membutuhkan adanya penjadwalan ulang. Hal ini mengakibatkan perkuliahan di awal semester berjalan tidak efektif karena harus melakukan penyesuaian jadwal dengan keadaan real setelah jadwal dikeluarkan. Selain itu, kesulitan dalam hal pencarian slot yang masih kosong juga menjadi suatu kendala terutama pada saat mencari jadwal kuliah pengganti atau kuliah tambahan. Ada beberapa faktor yang berpengaruh dalam pembuatan jadwal mata kuliah seperti dosen, mahasiswa, mata kuliah serta jumlah ruang dan waktu yang tersedia. Banyaknya jumlah mata kuliah dan dosen yang terlibat mengakibatkan munculnya persoalan seperti terbatasnya ruang yang digunakan untuk menyelenggarakan perkuliahan tidak terjadi secara bersamaan, terbatasnya jam mengajar dosen yang hanya bisa mempunyai kuota tidak lebih dari 20 sks dan terjadinya dosen yang mengajar secara bersamaan. Selain dilihat

1


2

dari sisi mahasiswa, juga harus dilihat dari sisi dosen, yaitu kemungkinankemungkinan dosen akan mengampu lebih dari satu matakuliah 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. Faktor lain yang menjadi kesulitan adalah dibutuhkan waktu yang lama untuk membuat satu jadwal dalam satu semester, karena banyaknya data dosen, mata kuliah, ruang, yang diperlukan ketelitian karena masih dibuat secara manual. Permasalahan

penjadwalan

kuliah

terkait

erat

dengan

masalah

optimasi.Oleh karena itu, pengembangan sistem penjadwalan kuliah dilakukan dengan melalui beberapa iterasi perbaikan.Untuk mengatasi penjadwalan kuliah di Program Studi Guru Sekolah Dasar, dapat dilakukan penelitian dengan membuat desain sebuah model penjadwalan menggunakan algoritma Particle Swarm Optimization (PSO). Contoh kasus yang digunakan untuk penelitian adalah Model Penjadwalan Matakuliah Secara Otomatis Berbasis Algoritma Particle Swarm Optimization (PSO) yang dilakukan di Universitas Islam Indonesia yang menyimpulkan bahwa algoritma PSO dapat digunakan untuk membantu pembuatan table jadwal yang sesuai dengan semua kriteria mata kuliah yang bersifat wajib ,memenuhi permintaan dosen dalam memilih waktu mengajar dan dapat membantu tugas penjadwalan yang cukup rumit. Algoritma PSO merupakan sebuah teknik optimasi stokastik berdasarkan populasi yang teriinspirasikan oleh perilaku sekumpulan burung atau sekelompok ikan (Haupt,R.I.,2004). Fungsi dan tujuan dari penelitian ini adalah untuk


3

memperoleh penjadwalan mata kuliah dengan menggunakan Particle Swarm Optimiztion (PSO) sehingga dapat diperoleh kombinasi terbaik untuk pasangan mata kuliah dan dosen secara keseluruhan dan mengoptimalkan jumlah hari mengajar dosen serta menganalisa parameter-parameter terbaik pada algoritma Particle Swarm Optimiztion (PSO) untuk melakukan penjadwalan mata kuliah.

1.2.

Rumusan Masalah 1. Bagaimana penerapan algoritma Particle Swarm Optimiztion dalam menjadwalkan mata kuliah di Program Studi Pendidikan Guru Sekolah Dasar Universitas Sanata Dharma? 2. Bagaimana menyelesaikan masalah penjadwalan mata kuliah di prodi PGSD Universitas Sanata Dharma dengan mencari jadwal yang tidak terdapat bentrokan ruang, dosen dan kelompok kelas ?

1.3.

Batasan Masalah 1. Penelitian Ini hanya di lakukan di Prodi PGSD Sanata Dharma 2. Penjadwalan ini hanya untuk mata kuliah satu semester, tanpa memperhitungkan adanya mahasiswa yang mengambil ulang mata kuliah tertentu. 3. Hanya melakukan pemetaan penjadwalan mata kuliah tanpa memperhatikan status dosen. 4. Ruangan yang diprioritaskan dipakai adalah ruangan yang hanya milik PGSD Sanata Dharma yang berjumlah 13 kelas.


4

5. Hanya menangani matakuliah teori yang berjumlah 34 dengan jumlah sks sebanyak 79.

1.4.

Tujuan Penelitian 1. Mempelajari dan mendesain algoritma Particle Swarm Optimiztion sehingga dapat di gunakan untuk sistem penjadwalan kuliah. 2. Membuat sistem penjadwalan kuliah di Prodi PGSD Sanata Dharma

1.5.

Metodologi Penelitian Metode yang digunakan dalam menyusun jadwal mata kuliah PGSD adalah metode System Development Life Cycle (Paradigma Waterfall).Metode ini terdiri dari berbagai tahap :

1. Analisis Kebutuhan Pada tahap ini, akan dilakukan Identifikasi tentang kebutuhan system serta

pengumpulan

data–data

yang

diperlukan

dalam

proses

penjadwalan. 2. PerancanganSistem Pada tahap ini, akan dilakukan penerjemahan rancangan system kedalam perangkat lunak. Proses perancangan meliputi Perancangan Sistem, desain Basis Data, user interface dan rancangan implementasi program.


5

3. PenulisanProgam Pada tahap ini, akan dilakukan penerjemahan dari perancangan system ke dalam bahasa pemrograman. 4. Pengujian Pada tahap ini akan dilakukan pengujian program. Pengujian bertujuan untuk menemukan kesalahan – kesalahan hingga program dapat sesuai dengan yang diharapkan.

1.6.

Sistematika Penulisan

BAB I

: PENDAHULUAN

Bab ini berisi penjelasan tentang latar belakang masalah, rumusan masalah, tujuan, batasan masalah, metodologi penelitian, dan sistematika penulisan.

BAB II

: LANDASAN TEORI

Bab ini berisi tentang teori metode Particle Swarm Optimization yang menjadi dasar dalam pembuatan system penjadwalan perkuliahan di PGSD.

BAB III

: ANALISA DAN PERANCANGAN SISTEM

Bab ini berisi tentang analisis dan perancangan sistem yang akan di bangun, serta meliputi analisis data penjadwalan, aturan dalam


6

proses penjadwalan, dan penjelasan algoritma metode Particle Swarm

Optimization

dalam

menyelesaikan

permasalahan

penjadwalan perkuliahan.

BAB IV

: IMPLEMENTASI DAN ANALISA HASIL

Bab ini berisi tentang implementasi dari perancangan pada Bab III. Implementasi tersebut meliputi tampilan progam (input dan output) dan analisa dari progam yang dibuat.

BAB V

: KESIMPULAN DAN SARAN

Bab ini berisi tentang kesimpulan dan saran dari sistem yang akan di buat berdasarkan pada bab-bab sebelumnya.


BAB II LANDASAN TEORI 2.1. Penjadwalan Menurut Kenneth R. Baker (2009) Penjadwalan (Scheduling) merupakan proses pengalokasian sekumpulan tugas yang dimasukan ke dalam rentetan waktu tertentu. Penjadwalan merupakan sebuah fungsi pengambilan keputusan dari sekumpulan tugas untuk menentukan jadwal yang paling tepat. [6] Menurut Thomas Morton (1993) Penjadwalan adalah pengambilan suatu keputusan dalam penyesuaian aktivitas dan sumber daya untuk menyelesaikan sekumpulan pekerjaan agar mempunyai kualitas yang diinginkan.[7] Keputusan yang dibuat didalam Penjadwalan adalah pengurutan pengerjaan, waktu mulai dan waktu selesai, serta urutan operasi suatu pekerjaan. Permasalahan penjadwalan merupakan permasalahan kombinatorial yang rumit karena memiliki daerah alternative solusi yang luas dan banyak dijumpai lokal optimal (Yu, 2006) [8].Penjadwalan mata kuliah menjadi salah satu bagian terpenting dan selalu menjadi masalah yang selalu dihadapi oleh setiap universitas. Penjadwalan mata kuliah adalah proses penyusunan daftar perkuliahaan atau daftar kegiatan belajar yang dimasukkan pada slot waktu tertentu yang tersedia selama satu minggu beserta pembagian ruang kelasnya.

7


8

Dalam penjadwalan mata kuliah, terdapat dua kategori batasan yaitu batasan yang bersifat wajib atau disebut batasan mutlak (hard constraint) dan batasan yang bersifat preferensi atau disebut batasan lunak (soft constraint) (Oner,A., 2011). Batasan yang bersifat multak yang harus dipenuhi yaitu : 1. Dosen yang sama tidak dapat mengajarkan matakuliah yang berbeda dalam waktu yang bersamaan. 2. Setiap satu mata kuliah diselenggarakan di suatu ruang kuliah pada slot waktu yang tertentu. 3. Jam pelajaran per mata kuliah harus sesuai dengan beban SKSnya. 4. Kapasistas ruang kuliah harus mampu menampung sejumlah mahasiswa yang akan mengambil suatu mata kuliah tertentu. 5. Matakuliah yang lebih dari 3 sks diadakan sebanyak 2 kali dan diusahakan tidak diadakan dalam satu hari sekaligus. sedangkan batasan lunak, yaitu: 1. Mata kuliah yang diadakan secara paralel dengan dosen yang sama, sebaiknya tidak dijadwalkan dalam waktu yang bersamaan dan/atau berurutan. 2. Matakuliah yang dimungkinkan diambil oleh beberapa angkatan yang berbeda, tidak boleh dilaksanakan dalam waktu yang bersamaan.


9

3. Beberapa matakuliah dengan kelas yang hanya satu (tidak paralel) yang diambil oleh angkatan yang sama, sebaiknya tidak dilaksanakan dalam waktu yang bersamaan. [9]

Untuk mengatasi masalah penjadwalan, terdapat beberapa algoritma yang dapat memberikan solusinya, contohnya algoritma Particle Swarm Optimization. 2.2. Particle Swarm Optimization 2.2.1. Penjelasan algoritma Particle Swarm Optimization Algoritma particle swarm optimization pertama kali dikenalkan oleh Dr. Eberhart dan Dr. Kennedy ditahun 1995 dalam sebuah konferensi jaringan syaraf di Perth, Australia . Algoritma particle swarm optimization merupakan teknik optimasi berbasis stochastic yang diinspirasi oleh tingkah laku sosial sekawanan burung atau sekumpulan ikan (swarm) dalam bertahan hidup. Tiap-tiap makhluk hidup (selanjutnya disebut particle) akan disebar di ruang solusi secara acak yang uniform. Kemudian setiap particle akan berusaha berpindah posisi untuk mencari posisi lain yang dapat menghasilkan fungsi tujuan yang lebih baik. Setiap pergerakan particle akan dipandu oleh dua hal, posisi terbaik yang pernah ditempati particle tsb dan posisi terbaik yang pernah ditemui oleh seluruh particle. Sehingga, particle-particle tersebut akan bekerja sama dalam mencari solusi optimal.[10]


10

Kata partikel menunjukkan, misalnya, seekor burung dalam kawanan burung. Setiap individu atau partikel berperilaku secara terdistribusi dengan cara menggunakan kecerdasannya (intelligence) sendiri dan juga dipengaruhi perilaku kelompok kolektifnya. Dengan demikian, jika satu partikel atau seekor burung menemukan jalan yang tepat atau pendek menuju ke sumber makanan, sisa kelompok yang lain juga akan dapat segera mengikuti jalan tersebut meskipun lokasi mereka jauh di kelompok tersebut.

Metode optimasi yang didasarkan pada swarm intelligence ini disebut algoritma behaviorallyinspired sebagai alternatif dari algoritma genetika, yang sering disebut evolution-based procedures. Algoritma PSO ini awalnya diusulkan oleh Eberhart R. Dalam konteks optimasi multivariabel, kawanan diasumsikan mempunyai ukuran tertentu atau tetap dengan setiap partikel posisi awalnya terletak di suatu lokasi yang acak dalam ruang multidimensi. Setiap partikel diasumsikan memiliki dua karakteristik: posisi dan kecepatan. Setiap partikel bergerak dalam ruang/space tertentu dan mengingat posisi terbaik yang pernah dilalui atau ditemukan terhadap sumber makanan atau nilai fungsi objektif. Setiap partikel menyampaikan informasi atau posisi bagusnya kepada partikel yang lain dan menyesuaikan posisi dan kecepatan masingmasing berdasarkan informasi yang diterima mengenai posisi yang bagus tersebut. Sebagai contoh, misalnya perilaku burung-burung dalam


11

dalam kawanan burung. Meskipun setiap burung mempunyai keterbatasan dalam hal kecerdasan, biasanya ia akan mengikuti kebiasaan (rule) seperti berikut :

1. Seekor burung tidak berada terlalu dekat dengan burung yang lain 2.

Burung tersebut akan mengarahkan terbangnya ke arah ratarata keseluruhan burung

3. Akan memposisikan diri dengan rata-rata posisi burung yang lain dengan menjaga sehingga jarak antar burung dalam kawanan itu tidak terlalu jauh

Dengan demikian perilaku kawanan burung akan didasarkan pada kombinasi dari 3 faktor simpel berikut: 1. Kohesi - terbang bersama 2. Separasi - jangan terlalu dekat 3. Penyesuaian(alignment) - mengikuti arah bersama Jadi PSO dikembangkan dengan berdasarkan pada model berikut: 1. Ketika seekor burung mendekati target atau makanan (atau bisa minimum atau maximum suatu fungsi tujuan) secara cepat mengirim informasi kepada burung-burung yang lain dalam kawanan tertentu


12

2. Burung yang lain akan mengikuti arah menuju ke makanan tetapi tidak secara langsung 3. Ada komponen yang tergantung pada pikiran setiap burung, yaitu memorinya tentang apa yang sudah dilewati pada waktu sebelumnya.

Model ini akan disimulasikan dalam ruang dengan dimensi tertentu dengan sejumlah iterasi sehingga di setiap iterasi, posisi partikel akan semakin mengarah ke target yang dituju (minimasi atau maksimasi fungsi). Ini dilakukan hingga maksimum iterasi dicapai atau bisa juga digunakan kriteria penghentian yang lain.

2.2.2. Proses Algoritma Particle Swarm Optmization Proses algoritma particle swarm optimization yaitu sebagai berikut : 1)Inisialisasi sekumpulan particle secara random (setiap particlemerepresentasikan solusi yang mungkin untuk masalah optimasi). 2)Inisialisasi posisi dari setiap particle (𝑋𝑖 ) dan kecepatan dari setiapparticle (𝑉𝑖 ). 3)Hitung nilai fitness dari setiap particle𝐹𝑖 berdasarkan formula dan model yang telah ditentukan sesuai dengan masalah optimasinya.


13

4)Untuk setiap particle, bandingkan nilai fitness𝐹𝑖 dengan nilaiterbaiknya yang telah dicapai 𝑃𝑖𝑑 (local best) .jika𝐹𝑖 <𝑃𝑖𝑑 , maka 𝑃𝑖𝑑 diganti dengan 𝐹𝑖 . 5)Untuk setiap particle, bandingkan nilai fitness 𝐹𝑖 dengan Nilai terbaik yang dicapai dalam populasi 𝑃𝑔𝑑 (global best), jika𝐹𝑖 <𝑃𝑔𝑑 , maka 𝑃𝑔𝑑 diganti dengan 𝐹𝑖 . 6)Berdasarkan persamaaan 4 dan 5 , kecepatan (𝑉𝑖 )dan posisi dari particle(𝑋𝑖 ) diubah.

Rumus perubahan kecepatan (𝑉𝑖 ) : 𝑖 𝑉𝑘+1 = 𝑤 ∗ 𝑉𝑘𝑖 + 𝑐1 ∗ 𝑅𝑎𝑛𝑑 ∗ (𝑋𝑖𝑑 − 𝑋𝑘𝑖 ) + 𝑐2 ∗ 𝑅𝑎𝑛𝑑

∗ (𝑋𝑔𝑑 − 𝑋𝑘𝑖 ) Rumus perubahan posisi (𝑋𝑖 ) : 𝑖 𝑖 𝑋𝑘+1 = 𝑋𝑘𝑖 + 𝑉𝑘+1

7) Jika telah mencapai kondisi akhir (mencapai nilai iterasi maksimum atau perulangan telah mencapai nilai optimum) maka perulangan berhenti dan nilai optimumnya didapatkan namun jika belum maka diulangi pada nomor 3.


14

Berikut Pseudo code dari algoritma PSO [5] : For setiap partikel Inisialisasi partikel End Repeat For setiap partikel Hitung nilai fitness If nilai fitness baru lebih baik daripada nilai fitness lama Update nilai fitness dari partikel tersebut End End Pilih partikel dengan nilai fitness terbaik diantara semua partikel tetangganya dan simpan nilai fitness terbaik tersebut. For setiap partikel Hitung velocity partikel menggunakan rumus pertama di atas Update posisi partikel menggunakan rumus ke dua diatas End Until (Kriteria Berhenti = true)

2.2.3. Cara Kerja Algoritma Particle Swarm Optimization Misalkan kita mempunyai fungsi berikut : min 𝑓(𝑥) 𝑑𝑖𝑚𝑎𝑛𝑎 𝑋 (𝐵) ≤ 𝑋 ≤ 𝑋 (𝐴) dimana𝑋 (𝐵) adalah batas bawah dan 𝑋 (𝐴) adalah batas atas dari X. Prosedur PSO dapat dijabarkan dengan langkah-langkah sebagai berikut [13]:


15

1. Asumsikan bahwa ukuran kelompok atau kawanan (jumlah partikel) adalah N. Untuk mengurangi jumlah evaluasi fungsi yang diperlukan untuk menemukan solusi, sebaiknya ukuran N tidak terlalu besar, tetapi juga tidak terlalu kecil,agar ada banyak kemungkinan posisi menuju solusi terbaik atau optimal. Jika terlalu kecil, sedikit kemungkinan menemukan posisi partikel yang baik. Terlalu besar juga akan membuat perhitungan jadi panjang. Biasanya digunakan ukuran kawanan adalah 20 sampai 30 partikel.

2. Bangkitkan populasi awal X dengan rentang𝑋 (𝐵) 𝑑𝑎𝑛𝑋 (𝐴) secara random sehingga didapat 𝑋1 , 𝑋2 , … , 𝑋𝑁. Setelah itu, untuk mudahnya,partikelj dan kecepatannya pada iterasi i dinotasikan (𝑖)

(𝑖)

sebagai 𝑋𝑗 𝑑𝑎𝑛 𝑉𝑗 Sehingga partikel-partikel awal ini akan menjadidisebut𝑋1 (0), 𝑋2 (0), … , 𝑋𝑁 (0). Vektor 𝑋𝑗 (0), 𝑗(1,2, … , 𝑁) partikel atau vektor koordinat dari partikel. (seperti kromosom dalam algoritma genetika). Evaluasi nilai fungsi tujuan untuk setiap partikel dan nyatakan dengan 𝑓[𝑋1(0)], 𝑓[𝑋2 (0)], … , 𝑓[𝑋𝑁 (0)]

3. Hitung kecepatan dari semua partikel. Semua partikel bergerak menujutitik optimal dengan suatu kecepatan. Awalnya semua


16

kecepatan daripartikel diasumsikan sama dengan nol. Set iterasi i =1.

4. Pada iterasi ke-i, temukan 2 parameter penting untuk setiap partikel j yaitu: (a) Nilai terbaik sejauh ini dari 𝑋𝑗 (𝑖)(koordinat partikel jpada iterasi i) dan nyatakan sebagai𝑃𝑏𝑒𝑠𝑡,𝑗 ,dengan nilai fungsi obyektif paling rendah (kasus minimasi) ,𝑓[𝑋𝑗 (𝑖)] , yang ditemui sebuah partikel jpada semua iterasi sebelumnya. Nilai terbaik untuk semua partikel 𝑋𝑗 (𝑖) yang ditemukan sampai iterasi ke-i, 𝐺𝑏𝑒𝑠𝑡 , dengan nilai fungsi tujuan paling kecil/minimum diantara semua partikel untuk semua iterasi sebelumnya,𝑓[𝑋𝑗 (𝑖)].

(b) Hitung kecepatan partikel j pada iterasi ke i dengan rumus sebagai berikut: 𝑉𝑗 (𝑖) = 𝑉𝑗 (𝑖 − 1) + 𝑐1 𝑟1 [𝑃𝑏𝑒𝑠𝑡,𝑗 − 𝑥𝑗 (𝑖 − 1)] +𝑐2 𝑟2 [𝐺𝑏𝑒𝑠𝑡 − 𝑥𝑗 (𝑖 − 1)], 𝑗 = 1,2, … , 𝑁 dimana𝑐1 𝑑𝑎𝑛 𝑐2 masing-masing adalah learning rates untuk kemampuan individu (cognitive) dan pengaruh sosial

(group),

dan𝑟1 𝑑𝑎𝑛 𝑟2 bilangan

random

yang

berdistribusi uniforml dalam interval 0 dan 1. Jadi


17

parameters𝑐1 𝑑𝑎𝑛 𝑐2 menunjukkan bobot dari memory (position) sebuah partikel terhadap memory (posisi) darikelompok(swarm). Nilai dari 𝑐1 𝑑𝑎𝑛 𝑐2 adalah 2 sehingga perkalian 𝑐1 𝑟1 𝑑𝑎𝑛 𝑐2 𝑟2memastikan bahwa partikel-partikel akanmendekati target sekitar setengah selisihnya.

(c) Hitung posisi atau koordinat partikel j pada iterasi ke-i dengan cara 𝑋𝑗 (𝑖) = 𝑋𝑗 (𝑖 − 1) + 𝑉𝑗 (𝑖); 𝑗 = 1,2 … , 𝑁(3) Evaluasi nilai fungsi tujuan untuk setiap partikel dan nyatakan sebagai 𝑓[𝑋1 (𝑖)], 𝑓[𝑋2 (𝑖)], 𝑓 … , 𝑓[𝑋𝑁 (𝑖)]

5. Cek apakah solusi yang sekarang sudah konvergen. Jika posisi semua partikel menuju ke satu nilai yang sama, maka ini disebut konvergen. Jika belum konvergen maka langkah 4 diulang dengan memperbarui iterasi i = i + 1, dengan cara menghitung nilai baru dari 𝑃𝑏𝑒𝑠𝑡,𝑗 𝑑𝑎𝑛 𝐺𝑏𝑒𝑠𝑡 .Proses iterasi ini dilanjutkan sampai semua partikel menuju ke satu titik solusi yang sama. Biasanya akan ditentukan dengan kriteria penghentian (stopping criteria), misalnya jumlah selisih solusi sekarang dengan solusi sebelumnya sudah sangat kecil.


BAB III ANALISA DAN PERANCANGAN SISTEM

3.1.

Analisis Sistem Sistem yang akan dibangun pada tugas akhir ini adalah sistem optimasi penjadwalan MataKuliah menggunakan algoritma Particle Swarm Optimization. Aplikasi ini merupakan alat bantu untuk proses perataan jam mengajar mata kuliah di PGSD Univesitas Sanata Dharma. Sistem ini akan diimplementasikan ke sebuah aplikasi dengan bahasa pemrograman Java dan MySQL sebagai database

3.1.1.

Analisis Masalah Kegiatan belajar mengajar di PGSD dilaksanakan pada hari senin

sampai jumat, dimulai pukul 07.00 sampai jam 19.00. Proses penyusunan penjadwalan mata kuliah di PGSD diawali dengan pemaketan mata kuliah pada tiap semester. Kemudian masing-masing mata kuliah ditugaskan kepada

dosen

yang

kompeten

mengajar

pada

mata

kuliah

tersebut.Selanjutnya, mata kuliah dijadwalkan pada hari, jam, dan ruang yang tersedia dengan mempertimbangkan kesedian waktu dan kuota dosen mengajar.Ketika terdapat dosen luar yang mengajar di PGSD maka,dosen luar akan diprioritaskan untuk mendapatkan jam dan hari mengajar yang diinginkan.

18


19

Hasil akhir dari penyusunan mata kuliah ini adalah jadwal mata kuliah selama satu semester yang disusun berdasarkan jam, ruang, kelas dan mata kuliah. 3.1.2.

Aturan Penjadwalan Dalam penjadwalan mata kuliah, terdapat batasan yang tidak boleh dilanggar oleh sistem.Terdapat 2 batasan, yang bersifat wajib atau disebut batasan mutlak (hard constraint) dan batasan yang bersifat preferensi atau disebut batasan lunak (soft constraint).Hard constraint merupakan batasan yang wajib terpenuhi oleh sistem, Sedangkan soft constraint merupakan batasan yang tidak wajib di penuhi oleh sistem. Batasan yang bersifat multak yang harus dipenuhi yaitu : 1. Dosen yang sama tidak boleh mengajar mata kuliah yang berbeda di waktu yang bersamaan. 2. Setiap matakuliah, diselenggarakan di satu ruang yang berbeda dengan matakuliah 3. Satu mata kuliah dapat diampu lebih dari satu dosen. 4. Setiap dosen memiliki batasan maksimal mengajar sebanyak 20 sks pada semester di tahun bersangkutan. 5. 1 kelas hanya mampu menampung maksimal 50 mahasiswa pada kelas teori, dan 30 pada kelas praktikum. 6. Waktu kuliah dalam sehari dimulai dari jam 07.00 wib sampai pukul 19.00 wib.


20

sedangkan batasan lunaknya, yaitu: 1.

Untuk Kelompok Kelas yang sama, tidak lebih dari 3 matakuliah yang di selenggarakan dalam sehari.

2.

Dosen tidak mengajar secara berurutan lebih dari 3 matakuliah per hari.

3.2.Pemodelan Algoritma Particle Swarm Optimization untuk penjadwalan

Algoritma particle swarm optimization merupakan teknik komputasi evolusioner, yang mana populasi pada PSO didasarkan pada penelusuran algoritma dan diawali dengan suatu populasi yang random yang disebut dengan particle. Algoritma particle swarm optimization memodelkan pencarian solusi terbaik dalam suatu ruang solusi sebagai aktivitas bergeraknya kelompok partikel dalam suatu ruang solusi tersebut. Setiap posisi pada partikel dalam ruang solusi merupakan kandidat solusi yang berisi variabel – variabel dari optimasi. Algoritma dasar PSO terdiri dari tiga tahap, yaitu pembangkitan posisi serta kecepatan partikel, updatevelocity (update kecepatan), updateposition (update posisi).Partikel berubah posisinya dari suatu perpindahan (iterasi) ke posisi lainnya berdasarkan pada update velocity.


Start

Ploting matakuliah (random) Inialisasi nilai w,c1,c2,jumlah partikel, max iterasi Iterasi < jumlah iterasi ya Hitung nilai fitness tiap partikel Iterasi =0

tidak

ya Simpan nilai fitness ke dalam arraylist simpanlocal

Simpan nilai fitness ke dalam arraylist simpanlocal dan simpan global

Fitness baru < Fitness lama ya

Buat String tampungglobal = simpanglobal.get(0)

Simpan nilai fitness ke dalam arraylist simpanglobal

j = 0; j < simpanglobal.size(); j++

ya

Buat String tampunglocal = simpanlocal.get(0)

Int pel=simpanglobal.get(j), Int pel2 =tampungglobal

j = 0; j < simpanlocal.size(); j++

tidak Pel < pel2

ya

tidak ya

Int pel=simpanlocal.get(j), Int pel2 =tampunglocal tidak tidak

tampungglobal=simpanglobal.get(j)

Pel < pel2

globalbest = tampungglobal tidak

ya Tampunglocal=simpanlocal.get(j)

Localbest = tampunglocal

Memenuhi stopping condition?

tidak

ya Simpan Jadwal End

Gambar 3. 1 Algoritma PSO dalam pembuatan jadwal

Inisialisasi posisi

21


Proses

penjadwalan

kuliah

menggunakan

Particle

22

Swarm

Optimization (PSO) dapat dilihat pada flowchart Gambar 3.1 diatas. Proses awal yang dilakukan adalah dengan memploting matakuliah secara random kedalam matriks 2 dimensi. Proses penjadwalan mata kuliah menggunakan algoritma Particle Swarm Optimization sebagai berikut: 3.2.1. Memploting matakuliah secara random (Pembangkitan posisi dan kecepatan awal) Untuk memploting matakuliah secara random, maka di gunakan matriks 2 dimensi. Matriks tersebut merupakan persilangan antara kelas “timeslot” dengan kelas “Ruang” untuk mendapatkan kelas matakuliah. Dalam studi kasus di PGSD, terdapat 5 hari waktu perkuliahan yaitu dari hari Senin – Jumat. Waktu perkuliahan dalam satu hari di bagi menjadi 4 sesi (waktu), 1 sesi memiliki 3 jam dan memiliki 13 ruang teori. Untuk mendapatkan timeslot , maka kita harus mensilangkan hari dan waktu yang sudah ditentkan, sehingga di dapatkan timeslot = 5 hari * 4 waktu = 20 timeslot.


Tabel 3. 1 Tabel Data hari

Id Hari

Nama Hari

H1

Senin

H2

Selasa

H3

Rabu

H4

Kamis

H5

Jumat

Tabel 3. 2 Tabel data waktu

Id Waktu

Jam

W1

07.00-10.00 WIB

W2

10.00-13.00 WIB

W3

13.00-16.00 WIB

W4

16.00-19.00 WIB

23


24

Tabel 3. 3 Tabel data struktur time slot

Time slot Kode

Kode

Kode

TS

Hari

Jam

TS1

H1

W1

TS2

H1

W2

TS3

H1

W3

TS4

H1

W4

TS5

H2

W1

…

…

…

TS20

H5

W4

Setelah mendapatkan timeslot, maka akan di tentukan timeslot kelas matakuliah yang didapatkan antara persilangan timeslot hari dan waktu * ruang teori, sehingga didapatkan 20 * 13 ruang = 260 timeslot kelas matakuliah.


25

Tabel 3. 4 Tabel data Struktur Matriks time slot dengan Ruang

" Time Slot "

"Ruang" R1

R2

R3

R4

R5

…

R13

ts1

KM1

KM50

?

?

?

…

?

ts2

?

?

?

?

?

…

?

ts3

?

?

?

?

?

…

?

ts4

?

?

?

?

?

…

?

ts5

?

?

?

?

?

…

?

ts6

?

?

?

?

?

…

?

ts7

?

?

?

?

?

…

?

ts8

?

?

?

?

?

…

?

ts9

?

?

?

?

?

…

?

…

…

…

…

…

…

…

…

ts20

?

?

?

?

?

…

?

Ket : ? = Kode "Kelas MataKuliah" hasil random Proses memploting matakuliah dengan sample 3 matakuliah dengan 4 dosen yang mempunyai 15 kelas matakuliah dengan menggunakan 1 partikel sebagai berikut :


Tabel 3. 5 Tabel Dosen

ID D1 D2 D3 D4

Nama Dosen Apri Damai S., S.S., M.Pd. Galih Kusumo, M.Pd. AG. Sujatmiko BS., M.Hum. Rusmawan, S.Pd., M.Pd.

Tabel 3. 6 Tabel Kelas Matakuliah

No 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Mata kuliah Bahasa dan Sastra Indo (1A) Bahasa dan Sastra Indo (1B) Bahasa dan Sastra Indo (1C) Bahasa dan Sastra Indo (1D) Bahasa dan Sastra Indo (1E) Bahasa Inggris 1 (i) (1A) Bahasa Inggris 1 (i) (1B) Bahasa Inggris 1 (i) (1C) Bahasa Inggris 1 (i) (1D) Bahasa Inggris 1 (i) (1E) IPS (3A) IPS (3B) IPS (3C) IPS (3D) IPS (3E)

Dosen D1 D1 D1 D2 D2 D3 D3 D3 D3 D3 D4 D4 D4 D4 D4

Sks 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3

26


27

Buat slot yang akan menampung posisi dan velocity. Gambaran dari slot awal yang akan di gunakan untuk tiap partikel adalah sebagai berikut : Tabel 3. 7 Tabel Slot Matakuliah

TS1 TS2 TS3 TS4

TS5 TS6 TS7 TS8

TS9 TS10 TS11 TS12

TS13 TS14 TS15 TS16

TS17 TS18 TS19 TS20

R1 0 13 26 39

R2 1 14 27 40

R3 2 15 28 41

R4 3 16 29 42

R5 4 17 30 43

Senin R6 R7 5 6 18 19 31 32 44 45

R8 7 20 33 46

R9 8 21 34 47

R10 9 22 35 48

R9 60

R10 R11 R12 R13 61 62 63 64

72 85 98

73 86 99

74 87 100

R8

R9

R10 R11 R12 R13

111 124 137 150

112 125 138 151

113 126 139 152

R8

R9

R10 R11 R12 R13

163 176 189 202

164 177 190 203

165 178 191 204

R8

R9

R10 R11 R12 R13

215 228 241 254

216 229 242 255

217 230 243 256

R1 52

R2 53

R3 54

R4 55

R5 56

Selasa R6 R7 R8 57 58 59

65 78 91

66 79 92

67 80 93

68 81 94

69 82 95

70 83 96

R1

R2

R3

R4

R5

R6

104 117 130 143

105 118 131 144

106 119 132 145

107 120 133 146

108 121 134 147

109 122 135 148

R1

R2

R3

R4

R5

110 123 136 149 Kamis R6 R7

156 169 182 195

157 170 183 196

158 171 184 197

159 172 185 198

160 173 186 199

161 174 187 200

R1

R2

R3

R4

R5

162 175 188 201 Jumat R6 R7

208 221 234 247

209 222 235 248

210 223 236 249

211 224 237 250

212 225 238 251

213 226 239 252

71 84 97 Rabu R7

214 227 240 253

R11 10 23 36 49

75 88 101

114 127 140 153

166 179 192 205

218 231 244 257

R12 11 24 37 50

76 89 102

115 128 141 154

167 180 193 206

219 232 245 258

R13 12 25 38 51

77 90 103

116 129 142 155

168 181 194 207

220 233 246 259


28

Berdasarkan table di atas, di dapat nilai posisi awal (x) adalah sebagai berikut : Tabel 3. 8 Nilai Posisi awal R1

R2

R3

R4

R5

R6

Senin R7

R8

R9

R10

R11

R12

R13

x0=0

x1=1

x2=2

x3=3

x4=4

x5=5

x6=6

x7=7

x8=8

x9=9

x10=10

x11=11

x12=12

x13=13

x14=14

x15=15

x16=16

x17=17

x18=18

x19=19

x20=20

x21=21

x22=22

x23=23

x24=24

x25=25

x26=26

x27=27

x28=28

x29=29

x30=30

x31=31

x32=32

x33=33

x34=34

x35=35

x36=36

x37=37

x38=38

x39=39

x40=40

x41=41

x42=42

x43=43

x44=44

x45=45

x46=46

x47=47

x48=48

x49=49

x50=50

x51=51

R10

R11

R12

R13

R1

R2

R3

R4

R5

R6

Selasa R7

R8

R9

x52=52

x53=53

x54=54

x55=55

x56=56

x57=57

x59=58

x59=59

x60=60

x61=61

x62=62

x63=63

x64=64

x65=65

x66=66

x67=67

x68=68

x69=69

x70=70

x71=71

x72=72

x73=73

x74=74

x75=75

x76=76

x77=77

x78=78

x79=79

x80=80

x81=81

x82=82

x83=83

x84=84

x85=85

x86=86

x87=87

x88=88

x89=89

x90=90

x91=91

x92=92

x93=93

x94=94

x95=95

x96=96

x97=97

x98=98

x99=99

x100=100

x101=101

x102=102

x103=103

R1

R2

R3

R4

R5

R6

Rabu R7

R8

R9

R10

R11

R12

R13

x104=104

x105=105

x106=106

x107=107

x108=108

x109=109

x110=110

x111=111

x112=112

x113=113

x114=114

x115=115

x116=116

x117=117

x118=118

x119=119

x120=120

x121=121

x122=122

x123=123

x124=124

x125=125

x126=126

x127=127

x128=128

x129=129

x130=130

x131=131

x132=132

x133=133

x134=134

x135=135

x136=136

x137=137

x138=138

x139=139

x140=140

x141=141

x142=142

x143=143

x144=144

x145=145

x146=146

x147=147

x148=148

x149=149

x150=150

x151=151

x152=152

x153=153

x154=154

x155=155

R1

R2

R3

R4

R5

R6

Kamis R7

R8

R9

R10

R11

R12

R13

x156=156

x157=157

x158=158

x159=159

x160=160

x161=161

x162=162

x163=163

x164=164

x165=165

x166=166

x167=167

x168=168

x169=169

x170=170

x171=171

x172=172

x173=173

x174=174

x175=175

x176=176

x177=177

x178=178

x179=179

x180=180

x181=181

x182=182

x183=183

x184=184

x185=185

x186=186

x187=187

x188=188

x189=189

x190=190

x191=191

x192=192

x193=193

x194=194

x195=195

x196=196

x197=197

x198=198

x199=199

x200=200

x201=201

x202=202

x203=203

x204=204

x205=205

x206=206

x207=207

R1

R2

R3

R4

R5

R6

Jumat R7

R8

R9

R10

R11

R12

R13

x208=208

x209=209

x210=210

x211=211

x212=212

x213=213

x214=214

x215=215

x216=216

x217=217

x218=218

x219=219

x220=220

x221=221

x222=222

x223=223

x224=224

x225=225

x226=226

x227=227

x228=228

x229=229

x230=230

x231=231

x232=232

x233=233

x234=234

x235=235

x236=236

x237=237

x238=238

x239=239

x240=240

x241=241

x242=242

x243=243

x244=244

x245=245

x246=246

x247=247

x248=248

x249=249

x250=250

x251=251

x252=252

x253=253

x254=254

x255=255

x256=256

x257=257

x258=258

x259=259


29

x0 menginialisasikan posisi ke 0 atau posisi awal di dalam slot. Kemudian masukkan jadwal perkuliahan secara acak ke dalam slot. Dimisalkan proses memasukkan jadwal perkuliahan dapat dilihat pada gambar di bawah ini Tabel 3. 9 Tabel pembangkitan posisi dan velocity jadwal matakuliah

TS

TS1

R1

R2 R3

0. Bahasa dan Sastra Indo (1AD1)

13

1

14

15

27

28

TS2

TS3

26. Bahasa dan Sastra Indo (1CD1)

39

16.Bahasa dan Sastra Indo(1D-D2)

29

40

41

17

5

30

R8

R9

6. Bahasa dan Sastra Indo (1BD1)

18.Bahasa Inggris 1 (i) (1D-D3)

R10 R11 R12 R13

7

9

10

11

12

21

22

23

24

25

34

35

36

37

38

47

48

49

50

51

8. IPS (3C-D4)

19

31

43

20

32

44

45

46

R1

Slot 1 R2

52.Bahasa dan Sastra Indo(1E-D2)

53

R3

R4

54. Bahasa Inggris 1 (i) (1A-D3)

55

65

66

67

68

78

79. IPS (3ED4)

80

81

91

92

93

94

TS6

TS7

TS8

R6

4

42. IPS (3BD4)

Nilai Posisi

TS5

R5 3

33. IPS (3A-D4)

TS4

TS

R4

2

Senin R7

Selasa R6 R7

R5 56

69.Bahasa Inggris 1 (i) (1B-D3)

57

R8

58.Bahasa Inggris 1 (i) (1C-D3)

R9

R10 R11 R12 R13 60

61

62

63

64

73

74

75

76

77

87

88

89

90

100

101

102

103

59. IPS (3C-D4)

70

71

72

82

83

84

85

95

96

97

98

86.Bahasa Inggris 1 (i) (1E-D3)

99


TS

R1

R2

R3

R4

R5

R6

Rabu R7 R8

R9

R10

30

R11

R12 R13

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

TS9

TS10

TS11

TS12

TS

R1

R2

R3

R4

R5

R6

Kamis R7 R8

R9

R10

R11

R12 R13

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

TS13

TS14

TS15

TS16


TS

R1

R2

R3

R4

208

209

210

211

221

222

223

224

234

235

236

237

247

258

249

250

R5

R6

Jumat R7 R8

R9

R10

31

R11

R12 R13

212

213

214

215

216

217

218

219

220

225

226

227

228

229

230

231

232

233

238

239

240

241

242

243

244

245

246

251

252

253

254

255

256

257

258

259

TS17

TS18

TS19

TS20


32

Lalu matakuliah yang di random akan di ploting ke dalam timeslot kelas matakuliah awal dan akan disimpan sebagai hasil ploting random matakuliah awal. Satu ploting matakuliah awal terdiri dari idSolusi = timeslot hari waktu, satu ruang kelas dan satu kelas matakuliah. 0 = satu kelas matakuliah + satu timeslot hari,waktu + satu ruang kelas Jadi,ploting matakuliah awal itu terdiri dari kumpulan idSolusi ke - 0 sampai ke - n. Sehingga di dapatkan batas minimal perpindahan partikel yaitu 0 dan batas maksimal perpindahan partikel yaitu 259. Berikut merupakan atribut-atribut yang digunakan : private static List

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Recommend Documents