SKRIPSI KADAR ERATOSTHENES SITEPU

SISTEM PENDUKUNG KEPUTUSAN PENJADWALAN MATA KULIAH DENGAN MODEL PEMROGRAMAN HEURISTIC MENGGUNAKAN ALGORITMA A* (STUDI KASUS: S1 ILMU KOMPUTER FMIPA USU)

SKRIPSI

KADAR ERATOSTHENES SITEPU 061401091

PROGRAM STUDI S1 ILMU KOMPUTER DEPARTEMEN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2010

Universitas Sumatera Utara


SKRIPSI

Diajukan untuk melengkapi tugas akhir dan memenuhi syarat mencapai gelar Sarjana Komputer


PROGRAM STUDI S1 ILMU KOMPUTER DEPARTEMEN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2010


PERSETUJUAN

Judul

Kategori Nama Nomor Induk Mahasiswa Program Studi Departemen Fakultas

: SISTEM PENDUKUNG KEPUTUSAN PENJADWALAN MATA KULIAH DENGAN MODEL PEMROGRAMAN HEURISTIC MENGGUNAKAN ALGORITMA A* (STUDI KASUS: S1 ILMU KOMPUTER FMIPA USU) : SKRIPSI : KADAR ERATOSTHENES SITEPU : 061401091 : SARJANA (S1) ILMU KOMPUTER : ILMU KOMPUTER : MATEMATIKA DAN ILMU PENGETAHUAN ALAM (FMIPA) UNIVERSITAS SUMATERA UTARA Diluluskan di Medan, 21 Desember 2010

Komisi Pembimbing

:

Pembimbing 2

Pembimbing 1

Drs. Agus Salim Harahap, M.Si NIP 195408281981031004

Drs. Suyanto, M.Kom NIP 195908131986011002

Diketahui/Disetujui oleh Departemen Ilmu Komputer FMIPA USU Ketua,

Prof. Dr. Muhammad Zarlis NIP 195707011986011003


PERNYATAAN


SKRIPSI

Saya mengakui bahwa skripsi ini adalah hasil kerja saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing disebutkan sumbernya.

Medan, 21 Desember 2010



PENGHARGAAN

Segala puji dan syukur penulis panjatkan kepada Tuhan Yesus Kristus, dengan limpah karunia-Nya penulisan skripsi ini berhasil diselesaikan dalam waktu yang telah ditetapkan. Ucapan terima kasih saya sampaikan kepada Bapak Drs. Suyanto, M.Kom dan Bapak Drs. Agus Salim Harahap, M.Si selaku pembimbing pada penyelesaian skripsi ini yang telah memberikan panduan dan penuh kepercayaan kepada saya untuk menyempurnakan kajian ini. Serta kepada Bapak Syahril Efendi, S.Si, M.I.T. dan Bapak M. Andri Budiman, S.T., MCompSc., M.E.M. selaku pembanding yang telah memberikan saran dan kritiknya yang banyak membantu dalam proses penyelesaian skripsi ini. Ucapan terima kasih juga ditujukan kepada Ketua dan Sekretaris Departemen Ilmu Komputer, Bapak Prof. Dr. Muhammad Zarlis dan Bapak Syahriol Sitorus, S.Si., M.I.T., Dekan dan Pembantu Dekan Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sumatera Utara, semua dosen dan staf/pegawai pada Departemen Ilmu Komputer FMIPA USU, serta rekan-rekan mahasiswa angkatan 2006 terutama untuk sahabat saya Friendly, Pangeran, Handy, Ferry, Evin, Rain, dan Ferdinandus. Akhirnya, tidak terlupakan saya ucapkan terima kasih yang sebanyakbanyaknya kepada Ayahanda Dalin Mehuli Sitepu, Ibunda Sedia br. Ginting, dan saudari saya serta semua sanak-keluarga dan teman-teman yang telah memberikan bantuan materil dan spiritual dalam masa kuliah dan dalam penyelesaian skripsi ini. Semoga Tuhan akan membalasnya. Akhirnya penulis berharap semoga skripsi ini bermanfaat bagi pribadi, keluarga, masyarakat, organisasi, dan negara.


ABSTRAK

Penjadwalan mata kuliah merupakan kegiatan administratif yang paling utama di universitas. Melakukan penjadwalan mata kuliah bukanlah pekerjaan yang mudah. Banyak aspek yang mempengaruhi dan dapat menjadi kendala sehingga menimbulkan masalah dan konflik dalam menyusun jadwal mata kuliah. Untuk mengatasinya, dibangunlah sebuah sistem pendukung keputusan yang dapat membantu pegawai administratif untuk membuat jadwal mata kuliah. Sistem pendukung keputusan dibuat dengan menggunakan model pemrograman heuristic yang merupakan model pendekatan yang melibatkan cara heuristic yang dapat menghasilkan solusi layak dan cukup baik. Heuristic yang dimaksud adalah aturan keputusan yang diadopsi dari batasan-batasan dalam melakukan penjadwalan mata kuliah sehingga masalah penjadwalan dapat dipecahkan. Setiap slot waktu akan diperiksa menggunakan heuristic ini untuk menemukan waktu kuliah yang tepat untuk mata kuliah yang dijadwalkan. Dalam mencari slot waktu, sistem menggunakan algoritma A* yang akan mencari waktu kuliah dalam sebuah tree yang berisikan simpul slot waktu. Algoritma A* merupakan algoritma yang optimal dalam menghasilkan jalur atau lintasan terpendek dalam menemukan solusi dari masalah. Sistem pendukung keputusan ini akan memberikan solusi jadwal mata kuliah disertai dengan penilaian kualitas dan efektivitas dari solusi yang diberikan.


DECISION SUPPORT SYSTEM FOR COURSE SCHEDULING WITH HEURISTIC PROGRAMMING MODEL BY USING A* ALGORITHM (CASE STUDY: S1 ILMU KOMPUTER FMIPA USU)

ABSTRACT

The course scheduling is the main administrative activity in university. Doing of course scheduling is not an easy thing. Many aspects affect it and can be a problem in arranging it. To solve it, a decision support system was build to help the administrator to make the course schedule. The decision support system was made by using heuristic programming model which is an approaching model that involve heuristic way and can give a good solution. The heuristic means decision rules that adopted from constraints in scheduling subject so that the problem in making schedule can be solved. Every slot time will be checked by this heuristic to find the right time for course in schedule. In finding the slot time, this system uses A* algorithm that will find the time for a class in a tree that contain of node time slot. A* algorithm is an optimum algorithm that can produce the shortest way in finding solution of a problem. This decision support system can give course schedule solution with quality and the effectiveness grade from the solution that given.


DAFTAR ISI

Halaman Persetujuan Pernyataan Penghargaan Abstrak Abstract Daftar Isi Daftar Tabel Daftar Gambar

ii iii iv v vi vii ix x

Bab 1 Pendahuluan 1.1. Latar Belakang 1.2. Perumusan Masalah 1.3. Batasan Masalah 1.4. Tujuan 1.5. Manfaat 1.6. Metodologi Penelitian 1.7. Sistematika Penulisan

1 1 2 3 3 3 4 5

Bab 2 Landasan Teori 2.1. Penjadwalan 2.1.1. Definisi Penjadwalan 2.1.2. Penjadwalan Mata Kuliah 2.1.3. Masalah Jadwal Mata Kuliah 2.2. Sistem Pendukung Keputusan 2.2.1. Definisi SPK 2.2.2. Konfigurasi SPK 2.2.3. Karakteristik dan Kemampuan SPK 2.2.4. Komponen-Komponen SPK 2.2.4.1. Subsistem Manajemen Data 2.2.4.2. Subsistem Manajemen Model 2.2.4.3. Subsistem Antarmuka Pengguna 2.2.4.4. Subsistem Manajemen Berbasis Pengetahuan 2.2.5. Model 2.2.5.1. Manfaat Model 2.2.5.2. Kategori Model 2.2.6. Pemrograman Heuristic 2.3. Algoritma A* 2.4. Delphi 7.0 2.5. MySQL

6 6 6 7 8 10 13 13 14 15 16 18 19 19 20 20 21 22 24 27 27

Bab 3 Analisis dan Perancangan Sistem

30


3.1. Analisis Masalah Penjadwalan Mata Kuliah 30 3.2. Analisis dan Perancangan Komponen Sistem 33 3.2.1. Subsistem Manajemen Berbasis Pengetahuan 33 3.2.1.1. Hard Constraints 34 3.2.1.2. Soft Constraints 35 3.2.1.3. Tree 36 3.2.1.4. Nilai Konflik Mata Kuliah 37 3.2.1.5. Nilai Kualitas Solusi Jadwal Mata Kuliah 45 3.2.1.6. Nilai Efektivitas Penjadwalan Mata Kuliah 50 3.2.2. Subsistem Manajemen Model 51 3.2.2.1. Model Pemrograman Heuristic 51 3.2.2.2. Algoritma Penjadwalan Mata Kuliah Menggunakan A* 59 3.2.2.3. Sistem Pendukung Keputusan Penjadwalan Mata Kuliah 62 3.2.3. Subsistem Manajemen Data 63 3.2.3.1. Analisis Data Sistem 63 3.2.3.1.1. Data Internal 63 3.2.3.1.2. Data Eksternal 64 3.2.3.2. Data Flow Diagram (DFD) 65 3.2.3.2.1. Diagram Konteks 65 3.2.3.2.2. DFD Level 1 66 3.2.3.2.3. DFD Level 2 68 3.2.3.3. Kamus Data 68 3.2.3.4. Entity Relationship Diagram (ERD) 68 3.2.4. Subsistem Antarmuka Pengguna 69 Bab 4 Implementasi dan Pengujian Sistem 4.1. Implementasi Sistem 4.1.1. Lingkungan Implementasi 4.1.2. Implementasi Antarmuka Sistem 4.1.2.1. Form Utama 4.1.2.2. Form New 4.1.2.3. Form Open/Delete 4.1.2.4. Form Jadwal 4.2. Pengujian Sistem 4.2.1. Data Pengujian 4.2.2. Hasil Pengujian Sistem

72 72 72 73 73 73 74 74 75 76 79

Bab 5 Kesimpulan dan Saran 5.1. Kesimpulan 5.2. Saran

89 89 89

Daftar Pustaka

91

Lampiran A: DFD Level 2 Lampiran B: Kamus Data Lampiran C: Implementasi Antarmuka Sistem Lampiran D: Data Pengujian

93 99 103 109


DAFTAR TABEL

Halaman Tabel 2.1 Contoh sebuah tabel Tabel 2.2 Kategori-Kategori Model Tabel 2.3 Contoh-contoh heuristic Tabel 3.1 Heuristic dari Kriteria Penjadwalan Tabel 3.2 Spesifikasi Proses DFD Level 1 Tabel 4.1a Konflik Mata Kuliah Tabel 4.1b Konflik Mata Kuliah Tabel 4.2 Konflik Mata Kuliah KTB 103 Kelas 10 Kom A Tabel 4.3 Konflik Mata Kuliah KTB 304 Kelas 08 Kom A Tabel 4.4 Konflik Mata Kuliah KTC 302 Kelas 08 Kom A Tabel 4.5 Konflik Mata Kuliah UNI 106 Kelas 09 Kom A Tabel A.1 Spesifikasi Proses DFD Level 2 P1 Tabel A.2 Spesifikasi Proses DFD Level 2 P2 Tabel A.3 Spesifikasi Proses DFD Level 2 P3 Tabel A.4 Spesifikasi Proses DFD Level 2 P4 Tabel A.5 Spesifikasi Proses DFD Level 2 P5 Tabel B.1 Kamus Data Tabel D.1 Data Dosen Tabel D.2 Data Ruangan Tabel D.3 Data Mahasiswa Tabel D.4 Data Mata Kuliah Tingkat I Tabel D.5 Data Mata Kuliah Tingkat II Tabel D.6 Data Mata Kuliah Tingkat III Tabel D.7 Data Mata Kuliah Tingkat IV Tabel D.8 Data Waktu Ketersediaan Dosen

7 21 22 51 67 77 78 81 82 83 84 93 94 95 96 97 99 109 110 111 111 112 113 114 115


DAFTAR GAMBAR

Halaman Gambar 2.1 SPK Dalam Sudut Pandang Konotasional 11 Gambar 2.2 Skematik SPK 16 Gambar 3.1 Tree dari slot waktu 36 Gambar 3.2 Flowchart Untuk Mencari Konflik Dosen 39 Gambar 3.3 Flowchart Untuk Mencari Konflik Kelas 41 Gambar 3.4 Flowchart Untuk Mencari Konflik Tingkat 43 Gambar 3.5 Flowchart Untuk Mencari Nilai Konflik Mata Kuliah 44 Gambar 3.6a Flowchart Untuk Mencari Kualitas Mata Kuliah 46 Gambar 3.6b Flowchart Untuk Mencari Kualitas Mata Kuliah 47 Gambar 3.6c Flowchart Untuk Mencari Kualitas Mata Kuliah 48 Gambar 3.7 Flowchart Untuk Mencari Nilai Kualitas Solusi Jadwal Mata Kuliah 49 Gambar 3.8 Flowchart Untuk Mencari Nilai Efektivitas Penjadwalan Mata Kuliah 50 Gambar 3.9 Flowchart Heuristic Untuk Mata Kuliah Berstatus ‘Biasa’ 57 Gambar 3.10 Flowchart Heuristic Untuk Mata Kuliah Berstatus ‘Bersama’ 58 Gambar 3.11 Flowchart Penjadwalan Mata Kuliah Menggunakan Algoritma A* 61 Gambar 3.12 Flowchart Proses-Proses Dalam Sistem 62 Gambar 3.13 Diagram Konteks (DFD Level 0) 66 Gambar 3.14 DFD Level 1 67 Gambar 3.15 Diagram Entity Relationship 69 Gambar 3.16 Struktur Menu dan Form Antarmuka Sistem 71 Gambar 4.1 Pemberitahuan bahwa Mata Kuliah KTB 103 kelas 10 Kom A tidak dapat dijadwalkan 79 Gambar 4.2 Pemberitahuan bahwa Mata Kuliah KTB 304 kelas 08 Kom A tidak dapat dijadwalkan 80 Gambar 4.3 Pemberitahuan bahwa Mata Kuliah KTC 302 kelas 08 Kom A tidak dapat dijadwalkan 80 Gambar 4.4 Pemberitahuan bahwa Mata Kuliah UNI 106 kelas 09 Kom A tidak dapat dijadwalkan 80 Gambar 4.5 Pemberitahuan Nilai Kualitas Solusi Jadwal Mata Kuliah 85 Gambar 4.6 Pemberitahuan Nilai Efektivitas Penjadwalan Mata Kuliah 85 Gambar 4.7 Jadwal Mata Kuliah Untuk Ruang Java 86 Gambar 4.8 Jadwal Mata Kuliah Untuk Ruang Basic 87 Gambar 4.9 Jadwal Mata Kuliah Untuk Ruang Pascal 87 Gambar 4.10 Jadwal Mata Kuliah Untuk Ruang Fortran 88 Gambar A.1 DFD Level 2 P1 93 Gambar A.2 DFD Level 2 P2 94 Gambar A.3 DFD Level 2 P3 94 Gambar A.4 DFD Level 2 P4 95 Gambar A.5 DFD Level 2 P5 97 Gambar C.1 Tampilan Implementasi Antarmuka Form Utama 103 Gambar C.2 Tampilan Implementasi Antarmuka Form New 103


Gambar C.3 Tampilan Implementasi Antarmuka Form Open/Delete Gambar C.4 Tampilan Implementasi Antarmuka Tab Dosen Gambar C.5 Tampilan Implementasi Antarmuka Tab Mahasiswa Gambar C.6 Tampilan Implementasi Antarmuka Tab Ruangan Gambar C.7 Tampilan Implementasi Antarmuka Tab Mata Kuliah Gambar C.8 Tampilan Implementasi Antarmuka Tab Jadwal

104 104 105 106 107 108


SKRIPSI KADAR ERATOSTHENES SITEPU

Recommend Documents