OPTIMASI JADWAL PERKULIAHAN DOSEN DENGAN NEIGHBORHOOD SEARCH METHODS
TESIS
ORIS KRIANTO SULAIMAN 127038041
PROGRAM STUDI MAGISTER (S2) TEKNIK INFORMATIKA FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2015
OPTIMASI JADWAL PERKULIAHAN DOSEN DENGAN NEIGHBORHOOD SEARCH METHODS TESIS Diajukan untuk melengkapi tugas dan memenuhi syarat memperoleh ijazah Magister Teknik Informatika ORIS KRIANTO SULAIMAN 127038041
PROGRAM STUDI MAGISTER (S2) TEKNIK INFORMATIKA FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2015
ii
PERSETUJUAN
Judul
: OPTIMASI JADWAL PERKULIAHAN DOSEN DENGAN
NEIGHBORHOOD
SEARCH
METHODS Nama
: ORIS KRIANTO SULAIMAN
Nomor Induk Mahasiswa
: 127038041
Program Studi
: MAGISTER (S2) TEKNIK INFORMATIKA
Fakultas
: ILMU
KOMPUTER
DAN
TEKNOLOGI
INFORMASI (FASILKOM-TI) UNIVERSITAS SUMATERA UTARA Komisi Pembimbing
:
Pembimbing 2
Pembimbing 1
Dr.Mahyuddin, M.IT
Prof.Dr.Opim Salim Sitompul, M.Sc
Diketahui/Disetujui Oleh Program Studi Magister Teknik Informatika Ketua,
Prof. Dr. Muhammad Zarlis 19570701 198601 1 003
iii
PERNYATAAN
OPTIMASI JADWAL PERKULIAHAN DOSEN DENGAN NEIGHBORHOOD SEARCH METHODS
TESIS
Saya mengakui bahwa tesis ini adalah hasil karya saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing telah disebutkan sumbernya.
Medan, 9 Maret 2015
Oris Krianto Sulaiman 127038041
iv
PERNYATAAN PERSETUJUAN PUBLIKASI KARYA ILMIAH UNTUK KEPENTINGAN AKADEMIS
Sebagai sivitas akademika Universitas Sumatera Utara, saya yang bertanda tangan di bawah ini : Nama Mahasiswa
: ORIS KRIANTO SULAIMAN
Nomor Induk Mahasiwa
: 127038041
Program Studi
: Magister Teknik Informatika
Jenis Karya Ilmiah
: Tesis
Demi pengembangan ilmu pengetahuan, menyetujui untuk memberikan kepada Universitas Sumatera Utara Hak Bebas Royalti Non-Eksklusif (Non Exclusive Royalti Free Right) atas tesis saya yang berjudul: OPTIMASI JADWAL PERKULIAHAN DOSEN DENGAN NEIGHBORHOOD SEARCH METHODS Berserta perangkat yang ada (jika diperlukan). Dengan hak bebas royalty NonEksklusive ini, Universitas Sumatera Utara berhak menyimpan, mengalih media, memformat, mengelola dalam bentuk database, merawat dan mempublikasikan tesis saya tanpa meminta izin dari saya, selama tetap mencantumkan nama saya sebagai penulis dan sebagai pemegang dan/atau sebagai hak cipta. Demikianlah pernyataan ini dibuat dengan sebenarnya. Medan, 9 Maret 2015
Oris krianto Sulaiman 127038041
v
Telah diuji pada : Tanggal : 9 Maret 2015
PANITIA PENGUJI TESIS Ketua
: Prof. Dr. Opim Salim Sitompul
Anggota
: 1. Dr. Mahyuddin, M.IT 2. Prof. Dr. Muhammad Zarlis 3. Prof. Dr. Drs. Iryanto, M.Si 4. Prof. Dr. Herman Mawengkang
vi
RIWAYAT HIDUP
DATA PRIBADI Nama Lengkap
: Oris Krianto Sulaiman
Tempat dan Tanggal Lahir
: Kp.Paya, 16 Maret 1990
Alamat Rumah
: Jl. Eka rasmi komplek perumahan Bumi Johor Sentosa (BJS) No. B5
HP
: 082369783801
E-mail
:
[email protected]
Instansi Tempat Bekerja
: UNIMED / UISU
Alamat Kantor
: Jalan Willem Iskandar, Pasar V Medan Estate, Sumatera Utara 20221, Indonesia. Jalan Sisingamangaraja Teladan, Kelurahan Teladan
Barat,
Kecamatan
Medan
Kota,
Medan – Sumatera Utara.
DATA PENDIDIKAN SD
: SD Negeri 9 Tapaktuan Aceh Selatan
Tamat : 2002
SLTP : SMP Negeri 1 Tapaktuan Aceh Selatan
Tamat : 2005
SLTA : SMA Negeri 1 Tapaktuan Aceh Selatan
Tamat : 2008
S1
: Universitas Islam Sumatera Utara (UISU)
Tamat : 2012
S2
: Universitas Sumatera Utara (USU)
Tamat : 2015
vii
KATA PENGANTAR
Puji syukur kepada Tuhan Yang Maha Esa, atas segala limpahan berkat dan penyertaan-Nya sehingga tesis ini dapat diselesaikan tepat pada waktunya. Dengan selesainya tesis ini, perkenankanlah penulis mengucapkan terima kasih yang sebesarbesarnya kepada : 1. Rektor Universitas Sumatera Utara, Prof. Dr. dr. Syahril Pasaribu, DTM&H, M.Sc (CTM), Sp. A(K) atas kesempatan yang diberikan kepada penulis untuk mengikuti dan menyelesaikan pendidikan Program Magister. 2. Dekan Fasilkom-TI (Fakultas Ilmu Komputer dan Teknologi Informasi) Universitas Sumatera Utara Prof. Dr. Muhammad Zarlis, atas kesempatan yang diberikan kepada penulis menjadi mahasiswa Program Magister pada Program Pascasarjana Fasilkom-TI Universitas Sumatera Utara. 3. Ketua
Program
Studi
Magister
(S2)
Teknik
Informatika,
Prof. Dr. Muhammad Zarlis dan Sekretaris Program Studi Magister (S2) Teknik Informatika M. Andri Budiman, S.T, M.Comp, M.E.M beserta seluruh staff pengajar pada Program Studi Magister (S2) Teknik Informatika Program Pascasarjana Fasilkom-TI Universitas Sumatera Utara, yang telah bersedia membimbing penulis sehingga dapat menyelesaikan pendidikan tepat pada waktunya. 4. Terima kasih yang tak terhingga dan penghargaan setinggi-tingginya saya ucapkan kepada Prof.Dr. Opim Salim Sitompul, selaku pembimbing utama dan kepada Dr. Mahyuddin, M.IT selaku dengan
penuh
kesabaran
pembimbing
lapangan
yang
menuntun, memberikan nasehat baik
serta
membimbing penulis hingga selesainya tesis ini dengan baik. 5. Prof.Dr. Muhammad Zarlis, Prof.Dr. Drs. Iryanto, M.Si, dan Prof. Dr. Herman Mawengkang sebagai pembanding yang telah memberikan banyak masukkan dan motivasi serta arahan yang baik demi penyelesaian tesis ini. 6. Yang tersayang dan tercinta kedua orang tua penulis, ayahanda Sulaiman.SE dan ibunda Nuriha yang selalu memberikan motivasi dalam penyusunan tesis ini, serta adik tercinta Asih Annisa Sulaiman yang selalu memberikan semangat dalam mengerjakan tesis ini.
viii
7. Saudaraku bg Mohamad Ihwani dan bg Muhammad Basri tak terbalas jasa kalian, kalian membuka gerbang untuk terus berusaha belajar dan belajar, memberikan pengalaman berharga yang tak terlupa, cepat nyusulnya ya bg. 8. Seluruh tim IT UNIMED, khusunya my team networking , Bayu, Rusdi, Wanda, Emil, Anto, Wanda dan eli. Divisi data center Bg Angga dan Bg adi. Divisi maintenance, bg Zuhari, Rahdiansyah, Muflih, Uje, Sopi, Herman. Divisi research and development Bg Wais, Irfan, Andre dan Kak Ria. Serta semua civitas UNIMED yang mempercayakan tugas-tugas negara kepada tim IT. 9. Universitas Islam Sumatera Utara, Seluruf staf pegawai dan administrasi pada program studi teknik khususnya teknik informatika yang banyak memberikan masukan ilmu-ilmu baru di bidangnya. 10. Universitas Sumatera Utara, Staf Pegawai dan Administrasi pada Program Studi Magister (S2) Teknik Informatika Program Pascasarjana Fasilkom-TI Universitas Sumatera Utara yang telah memberikan bantuan dan pelayanan terbaik kepada penulis selama mengikuti perkuliahan.
Medan, 9 Maret 2015 Penulis
Oris Krianto Sulaiman 127038041
ix
ABSTRAK
Penjadwalan kegiatan kuliah dalam suatu Perguruan tinggi/kampus adalah suatu hal yang rumit dan sering mengalami kesulitan, yang menyebabkan pengalokasian mata kuliah dengan dosen dan ruangan yang sering bentrok dengan jadwal mata kuliah, dosen dan ruang yang lain dalam satu periode jadwal kuliah. Oleh karena itu dibutuhkan suatu sistem dan metode optimasi yang dapat diterapkan untuk menyusun penjadwalan mata kuliah. Optimasi penjadwalan kuliah dalam Tesis ini dibuat untuk membantu pihak pembuat jadwal dalam melakukan penjadwalan kuliah pada periode yang diselenggarakan. Metode yang dipakai adalah Neighborhood Search. Dimana terdiri dari algoritma genetika, simulated annealing dan tabu search. Kata Kunci : Neighborhood Search Methods, Algoritma Genetika, Algoritma Tabu Search dan Algoritma Simulated Annealing.
x
OPTIMIZATION OF LECTUER SCHEDULING WITH NEIGHBORHOOD SEARCH METHODS ABSTRACT Scheduling activities in a college lecture / campus is a complex and often experience difficulties, which led to the allocation of courses with professors and room often clashed with the schedule of courses, lecturers and other space in the class schedule period. Therefore, it needs a system and method of optimization that can be applied to develop scheduling courses. Scheduling optimization study in this thesis is made to assist the scheduler in scheduling courses in the period held. The method used is the Neighborhood Search. Where is composed of genetic algorithms, simulated annealing and tabu search. Keywords: Neighborhood Search methods, Genetic Algorithms, Tabu search algorithm and simulated annealing algorithm.
xi
DAFTAR ISI Halaman HALAMAN JUDUL KATA PENGANTAR ABSTRAK ABSTRACT DAFTAR ISI DAFTAR TABEL DAFTAR GAMBAR BAB 1
BAB 2
BAB 3
BAB 4
vii ix x xi xiii xiv
PENDAHULUAN 1.1 Latar Belakang 1.2 Rumusan Masalah 1.3 Batasan Masalah 1.4 Tujuan Penelitian 1.5 Manfaat Penelitian
1 2 2 3 3
TINJAUAN PUSTAKA 2.1 Permasalah Optimasi 2.2 Penjadwalan (Scheduling) 2.3 Neighborhood Search Methods 2.3.1 Genetic Algorithm 2.3.2 Simulated Annealing 2.3.3 Tabu Search Algorithm 2.4 Masalah Jadwal Mata Kuliah 2.5 Riset Terkait
4 5 7 8 12 13 16 17
METODOLOGI PENELITIAN 3.1 Model Neighborhood Search Methods 3.2 Analisis Proses Penjadwalan 3.3 Desain Sistem Genetic Algorithm 3.4 Desain Sistem Simulated Annealing 3.5 Desain Sistem Tabu Search 3.6 Teknik Pengumpulan Data 3.7 Teknik Mengembangkan Model 3.8 Pembahasan
18 19 20 23 24 25 26 26
HASIL DAN PEMBAHASAN 4.1 Hasil 4.1.1 Pengujian Sistem 4.1.2 Pengujian Algoritma 4.1.3 Evaluasi Kromosom 4.1.4 Seleksi Kromosom 4.1.5 Mutasi 4.1.6 Pengujian Secara Tabu Search 4.1.7 Input Ruangan dengan Simulated Anneling 4.2 Percobaan
28 28 29 32 33 36 40 47 49
xii
BAB 5
KESIMPULAN DAN SARAN 5.1 Kesimpulan 5.2 Saran DAFTAR PUSTAKA LAMPIRAN
60 60 61 62
xiii
DAFTAR TABEL
No. Tabel
Judul
Halaman
2.1
Riset Terkait
17
3.1
Algoritma Genetika pada Penjadwalan Mata Kuliah
21
4.1
Route Wheel
35
xiv
DAFTAR GAMBAR
No. Gambar
Judul
Halaman
2.1
Ilustrasi Tahapan Proses Genetic Algorithm
8
2.2
Dimensi Tabu Search
14
3.1
Struktur Pengembangan Neighborhood Search Methods
18
3.2
Struktur Penjadwalan-Model Neighborhood Search Methods
19
3.3
Struktur Jadwal dengan Genetik
20
3.4
Struktur Jadwal dengan metode Simulated Annelaing
23
3.5
Desain Sistem Tabusearch
24
4.1
Format Roster
29
4.2
Form 1 Pengaturan jam masuk dosen
30
4.3
Proses Inisialisasi kormosom peletakan jadwal dosen hari senin
31
4.4
Proses Inisialisasi kromosom pada jadwal dosen hari rabu
32
4.5
Kromosom Bermutasi hari senin
36
4.6
Kromosom Bermutasi hari rabu
38
4.7
Proses Susunan Tabulist
41
4.8
Mutasi kromosom Hari Senin
43
4.9
Mutasi kromosom hari Rabu
43
4.10
Kombinasi Ruangan
47
4.11
Kombinasi Ruangan dengan Metode Simulated Annealing
48
4.12
Jadwal salah satu dosen N. Manurung
49
4.13
Tabulist[1] digunakan
51
4.14
Proses tabulist[1] telah gagal
52
4.15
Tabulist[2] digunakan
52
4.16
Proses tabulist[2] telah gagal
53
4.17
Tabulist[3] digunakan
53
4.18
Tabulist[4] digunakan
54
4.19
Algoritma Simulated Anneling
55
4.20
Jarak Antara Ruangan dengan metode Simulated Annealing
56
xv
4.21
Proses Simulated Annealing
57
4.22
Jadwal Pada Hari Senin
57
4.23
Jadwal Pada Hari Selasa
58
4.24
Jadwal Pada Hari Rabu
58
4.25
Jadwal Pada Hari Kamis
58
4.26
Jadwal Pada Hari Jumat
59
