OPTIMASI PENJADWALAN PELAJARAN MENGGUNAKAN PARTICLE SWARM OPTIMIZATION
TUGAS AKHIR
Sebagai Persyaratan Guna Meraih Gelar Sarjana Strata Satu Teknik Informatika Universitas Muhammadiyah Malang
Oleh : Dadang Romadhon Alim Putra 08560144
JURUSAN TEKNIK INFORMATIKA FAKULTAS TEKNIK UNIVERSITAS MUHAMMADIYAH MALANG 2014
i
LEMBAR PERSETUJUAN
OPTIMASI PENJADWALAN PELAJARAN MENGGUNAKAN PARTICLE SWARM OPTIMIZATION
TUGAS AKHIR
Oleh : Dadang Romadhon Alim Putra 08560144
Telah Direkomendasikan Untuk Diajukan Sebagai Judul Tugas Akhir Di Teknik Informatika Universitas Muhammadiyah Malang
Menyetujui, Pembimbing I
Pembimbing II
Yuda Munarko. S.Kom, MSc NIP : 108.0611.0443
Ali Sofyan Kholimi. S.Kom
ii
LEMBAR PENGESAHAN
OPTIMASI PENJADWALAN PELAJARAN MENGGUNAKAN PARTICLE SWARM OPTIMIZATION
TUGAS AKHIR
Diajukan Untuk Memenuhi Persyaratan Guna Meraih Gelar Sarjana Strata Satu Teknik Informatika Universitas Muhammadiyah Malang
Disusun Oleh : DADANG ROMADHON ALIM PUTRA 08560144
Tugas Akhir ini telah diuji dan dinyatakan lulus oleh tim penguji pada tanggal 2 Juli 2014
Mengetahui/Menyetujui, Penguji I
Penguji II
Gita Indah Marthasari, ST. NIP : 108.0611.0442
Yufis Azhar, S.Kom.
Mengetahui Ketua Jurusan Teknik Informatika
Yuda Munarko. S.Kom, MSc NIP : 108.0611.0443 iii
LEMBAR PERNYATAAN
Yang bertanda tangan di bawah ini: Nama
: Dadang Romadhon Alim Putra
Tempat / Tgl Lahir
: Malang, 02 April 1990
NIM
:08560144
Fakultas / Jurusan
: Teknik / Teknik Informatika
Dengan ini saya menyatakan bahwa Tugas Akhir dengan judul “OPTIMASI
PENJADWALAN PELAJARAN MENGGUNAKAN PARTICLE SWARM OPTIMIZATION” beserta seluruh isinya adalah karya saya sendiri dan bukan merupakan karya tulis orang lain, baik sebagian maupun keseluruhan, kecuali dalam bentuk kutipan yang telah disebutkan sumbernya. Demikian surat pernyataan ini saya buat dengan sebenar-benarnya. Apabila kemudian ditemukan adanya pelanggaran terhadap etika keilmuan dalam karya saya ini, atau ada klaim dari pihak lain terhadap keaslian karya saya ini maka saya siap menanggung segala bentuk resiko/sanksi yang berlaku.
Malang, 10 Juni 2014 Yang Membuat Pernyataan
Dadang Romadhon A.P Mengetahui, Dosen Pembimbing I
Dosen Pembimbing II
Yuda Munarko. S.Kom, MSc NIP : 108.0611.0443
Ali Sofyan Kholimi. S.Kom
iv
ABSTRAK
Penjadwalan merupakan salah satu hal terpenting dalam suatu lembaga pendidikan, begitu juga untuk lingkup Sekolah Menengah Kejuruan (SMK). Penjadwalan pelajaran pada SMK tersebut meliputi jadwal mata pelajaran, pembagian guru di kelas, dan pembagian waktu praktikum di laboratorium berdasarkan kelas dan jurusan masing-masing. Untuk itu, penjadwalan pelajaran tersebut harus disusun dengan benar dan teliti. Sehingga tidak terjadi bentrok baik antar mata pelajaran, guru, kelas dan lab. Untuk menyelesaikan masalah tersebut dalam tugas akhir ini digunakan algoritma Particle SwarmOptimized (PSO) utnuk melakukan optimasi pada jadwal kuliah. Karena algoritma PSO memiliki tool-tool yang cukup handal dengan penggunaan yang cukup mudah. Tugas Akhir ini ini bertujuan untuk membuat suatu sistem komputasi untuk menggantikan penjadwalan secara manual, dan hasil akhirnya diharapkan dapat mengatur jam mengajar dosen dan juga jadwal perkuliahan mahasiswa, sehingga menghindari adanya bentrokan jadwal
Kata Kunci : Particle Swarm Optimizaton, PSO, penjadwalan
v
ABSTRACT
Scheduling is one of the most important things in an educational institution, as well as to the scope of the Vocational School (VS). Scheduling lessons on vocational subjects include schedules, division of teachers in the classroom, and the division of time in the laboratory practicum based classes and majors, respectively. To that end, the lesson scheduling must be arranged properly and carefully. So there is no clash between both subjects, teacher, classroom and lab. To resolve the issue in this thesis is used SwarmOptimized Particle algorithm (PSO) for optimizing the class schedule. Because the PSO algorithm has the tools that are reliable enough to use fairly easily. This final project aims to create a computing system to replace manual scheduling, and the end result is expected to set the hours of teaching faculty and student lecture schedule, so as to avoid any clashes schedule.
Keywords: Particle Swarm Optimizaton, PSO, scheduling
vi
LEMBAR PERSEMBAHAN
Dengan rahmat dan hidayah Allah SWT, saya persembahkan kesuksesan pengerjaan skripsi ini kepada :
1.
Ayah, ibu, adik tercinta, yang telah memberikan dukungan baik berupa materiil maupun spiritual, sampai dapat terselesaikannya penulisan skripsi ini.
2.
Rofiatul Anifah tercinta yang selama ini selalu memberikan semangat positif dalam keseharian penulis.
3.
Bapak Yuda Munarko. S.Kom, MSc, dan Ali Sofyan Kholimi. S.Kom selaku dosen pembimbing, yang dengan penuh perhatian dan kesabaran beliau telah membimbing penulis sejak awal sampai selesai.
4.
Bapak Yuda Munarko. S.Kom, MSc, selaku Ketua Jurusan Teknik Informatika Universitas Muhammadiyah Malang.
5.
Bapak dan Ibu Dosen Universitas Muhammadiyah Malang, yang telah membantu penulis dalam mendapatkan ilmu pengetahuan.
6.
Bapak Drs. Tri Harijoto, M.Pd, selaku Kepala SMK Muhammadiyah 1 Kepanjen, yang telah mengizinkan penulis melakukan penelitian di sekolah beliau serta telah meluangkan waktu untuk membantu selama penelitian.
7.
M. Nanang Nukman Amir selaku Staf WAKA Kurikulum SMK Muhammadiyah 1 Kepanjen yang telah membantu dan memberi kesempatan untuk mengadakan penelitian.
vii
8.
Semua sahabat-sahabat penulis, terutama Bismoko Widiyatno, Agung Kristiyanto, Bambang Eko Wahyudi. S.Kom, Khoirul anwar, Arista Pribadi dan Krisna Ramadhan yang telah memberi dukungan dan selalu membantu di saat penulis senang maupun susah. Semoga dalam pertemanan ini penulis mendapatkan hubungan tali silaturahmi yang lebih baik.
9.
Semua pihak yang tidak dapat penulis sebutkan satu persatu, baik secara langsung maupun tidak langsung telah memberikan bantuan sehingga terselesaikanya penulisan skripsi ini.
Akhir kata, semoga Allah SWT berkenan membalassegala kebaikan semua pihak yang membantu. Semoga skripsi ini bermanfaat bagi pengembangan ilmu.
Malang, 12 Juli 2014 Penulis
Dadang Romadhon A.P
viii
KATA PENGANTAR
Dengan mengucap puji syukur ke hadirat Allah SWT yang telah melimpahkan rahmat, taufik, dan hidayah-Nya, sehingga skripsi yang berjudul ”Optimasi Penjadwalan Pelajaran Menggunakan Particle Swarm Optimization” dapat diselesaikan dengan baik. Terwujudnya skripsi ini merupakan usaha maksimal yang telah penulis lakukan dan penulis menyadari dalam penyelesaian skripsi ini banyak mengalami kendala, namun demikian dapat diatasi berkat bantuan dan pertolongan Allah SWT lewat orang-orang yang diketuk hatinya untuk mengulurkan tangan membagi sebagian ilmu yang dimilikinya. Penulis telah berusaha sebaik mungkin agar penelitian ini dapat berjalan dengan sempurna, namun karena keterbatasan penulis maka penulis menyadari bahwa penulisan skripsi ini masih memiliki banyak kekurangan. Oleh karena itu kritik dan saran yang membangun sangat diharapkan penulis demi perbaikan dan penyempurnaan skripsi ini. Semoga skripsi ini dapat memberikan manfaat bagi semua pihak. Amiiin
Malang, 12 Juli 2014
Penulis ix
DAFTAR ISI
HALAMAN JUDUL ........................................................................
i
LEMBAR PERSETUJUAN............................................................
ii
LEMBAR PENGESAHAN .............................................................
iii
LEMBAR PERNYATAAN .............................................................
iv
ABSTRAK ........................................................................................
v
ABSTRACT……………………………………………………….
vi
LEMBAR PERSEMBAHAN..........................................................
vii
KATA PENGANTAR .....................................................................
ix
DAFTAR ISI ....................................................................................
x
DAFTAR TABEL ............................................................................
xiii
DAFTAR PERSAMAAN ...............................................................
xiv
DAFTAR GAMBAR .......................................................................
xv
BAB I
PENDAHULUAN
1.1. Latar Belakang ....................................................................
1
1.2. Rumusan Masalah ..............................................................
2
1.3. Tujuan .................................................................................
3
1.4. Batasan Masalah .................................................................
3
1.5. Metodologi Penyelesaian Masalah .......................................
4
1.6. Sistematika Penulisan ……………………………………..
6
BAB II
DASAR TEORI
2.1. Penjadwalan ........................................................................
x
8
2.2. Optimasi ...............................................................................
9
2.3. Particle Swarm Optimization ...............................................
12
2.3.1. Konsep Dasar Algoritma Particle Swarm Optimization
13
2.3.2. Kontrol Parameter ……………………………………
20
BAB III
PERANCANGAN SISTEM
3.1. Penjadwalan Pelajaran Di SMK Muhammadiyah 1 Kepanjen ……………………………………………………….… . .
22
3.2. Komponen Penjadwalan Pelajaran ......................................
23
3.3. Rancangan Sistem ...............................................................
24
3.3.1. Faktor – faktor Yang Mempengaruhi Penjadwalan ...
25
3.3.2. Aturan Penjadwalan ………………………………...
26
3.3.3. Metode Particle Swarm Optimization………………
27
3.3.4. Skema Database …………………………………….
28
3.3.5. Pembangkitan Posisi dan Velocity Awal Particle … .
31
3.3.6. Nilai Fitness ……………………………………….. .
32
3.3.7. Local Best dan Global Best ……………………….. .
33
3.3.8. Update Velocity dan Posisi …………………………
33
3.4. Optimasi Penjadwalan Mata Pelajaran .................................
34
BAB IV
IMPLEMENTASI DAN UJI COBA
4.1. Deskripsi Program ...............................................................
35
4.1.1. Input Data …………………………………………..
35
4.1.2. Konfigurasi …………………………………………
39
4.2. Penerapan Program Pada Penjadwalan Pelajaran .................
39
4.3. Penjelasan Program ..............................................................
41
xi
4.3.1 Inisialisasi Partikel.......................................................
42
4.3.2 Aturan Penjadwalan.....................................................
43
4.3.3 Parameter Algoritma Particle Swarm Optimization ....
45
4.4. Uji Coba................................................................................
55
BAB V
PENUTUP
5.1. Kesimpulan ...........................................................................
57
5.2. Saran .....................................................................................
57
DAFTAR PUSTAKA
xii
DAFTAR TABEL
Tabel 3.1Daftar Jam PelajaranPagi…………………………..
23
Tabel 3.1.1 Daftar Jam Pelajaran Siang……………………….
24
Tabel 3.2Daftar Slot yang Digunakan Untuk Tiap Partikel......
31
Tabel 4.1 Kombinasi default parameter proses PSO.................
40
Tabel 4.2 Kombinasi Variabel yang di Uji Coba......................
55
Tabel 4.3 Hasil Uji Coba dan Perhitungan Tingkat Kesalahan..
56
xiii
DAFTAR PERSAMAAN
Persamaan 2.1 Pembangkitan Partikel Posisi...................
17
Persamaan 2.2 Pembangkitan Partikel Kecepatan............
17
Persamaan 2.3 Vektor Posisi............................................
17
Persamaan 2.4 Vektor Kecepatan.....................................
17
Persamaan 2.5 Update Velocity........................................
18
Persamaan 2.6 Update Posisi.............................................
18
xiv
DAFTAR GAMBAR
Gambar 2.1 Taksonomi Algoritma Optimasi (Weise, 2009).........
11
Gambar 2.2 Topologi PSO : ring topology....................................
15
Gambar 2.3 Topologi PSO : star topology.....................................
15
Gambar 2.4 Pseudo code Algoritma PSO......................................
19
Gambar 3.1 Proses Penyusunan Jadwal.........................................
24
Gambar 3.2 Konfigurasi Sistem Secara Keseluruhan....................
25
Gambar 3.3 Flowchart Sistem Penjadwalan..................................
28
Gambar 3.4 Skema Database.........................................................
30
Gambar 4.1 Interface Utama..........................................................
35
Gambar 4.2 Form Input Data Jurusan............................................
36
Gambar 4.3 Form Input Data Kelas / Rombel...............................
36
Gambar 4.4 Form Input Data Ruang.............................................
36
Gambar 4.5 Form Input Data Guru...............................................
37
Gambar 4.6 Form Input Data Kesediaan Waktu Guru..................
37
Gambar 4.7 Form Input Data Pelajaran.........................................
38
Gambar 4.8 Form Input Data Hari dan Jam Pelajaran...................
38
Gambar 4.9 Form Input Data Pengampu Pelajaran........................
39
Gambar 4.10 Form Proses Algoritma Particle Swarm Optimization
39
Gambar 4.11 Hasil Penjadwalan......................................................
41
xv
DAFTAR PUSTAKA
[1] Agustina, Ira Lia. 2006. “Penjadwalan Pelajaran SMU Negeri Mojoagung dengan Algoritma”.Jurusan Teknologi Informasi, Politeknik Negeri Surabaya. [2] Ariani, Dian. 2010. “Optimasi Penjadwalan Mata Kuliah Dengan Menggunakan Algoritma Particle Swarm Optimization (PSO)”. Politeknik Elektronika Negeri Surabaya-Institut Teknologi Sepuluh Nopember. Surabaya. [3] C. Eberhat, Russell. Shi, Yuhui. “Particle Swarm Optimization : Developments, Applications and Resources”. Purdue School of engineering and Technology, Indianapolis USA [4] Chu. Shu-Chuan, Chen.Yi-Tin and Ho. Jiun-Huei. 2006. “ Timetable Scheduling Using Particle Swarm Optimization”, Cheng-Shiu University, Kaohsiung County 833, Taiwan [5] Particle Swarm Optimization, (Online), (http://en.wikipedia.org/wiki/Particle_swarm_optimization, diakses pada 15Januari 2013). [6] Pongchairerks, Pisut. 2009. “Particle Swarm Optimization Algorithm Applied to Schedulling Problems”. Industrial Engineering Programme, School of Manufacturing Systems and Mechanical Engineering, Sirindhorn International Institute of Technology, hammasat University, Pathum Thani 12121, Thailand. [7] S.G. Ponnambalam, N. Jawahar, S. Chandrasekaran. “Discrete Particle Swarm Optimization Algorithm for Flowshop Scheduling”.Monash University, Thiagarajar College of Engineering, S R M V Polytechnic College, Malaysia, India.
xvi
[8] Suyanto. 2010. Algotitma Optimasi Deterministik atau Probabilitik, Yogyakarta:Graha Ilmu. [9] Weise, Thomas. Global Optimization Algorithm (Theori and Application). 2009.
http://www.it-weise.de/
xvii
