MODEL SISTEM PENJADWALAN DEPENDENCY PADA BASIS DATA DEDUKTIF

MODEL SISTEM PENJADWALAN DEPENDENCY PADA BASIS DATA DEDUKTIF STUDI KASUS: SISTEM PENJADWALAN MATA KULIAH

LAPORAN TUGAS AKHIR Disusun sebagai syarat kelulusan tingkat sarjana

oleh Yosep Kurniawan NIM : 13503059

PROGRAM STUDI TEKNIK INFORMATIKA SEKOLAH TEKNIK ELEKTRO DAN INFORMATIKA INSTITUT TEKNOLOGI BANDUNG 2007

LEMBAR PENGESAHAN PROGRAM STUDI SARJANA TEKNIK INFORMATIKA

Model Sistem Penjadwalan Dependency Pada Basis Data Deduktif Studi Kasus: Sistem Penjadwalan Mata Kuliah

Tugas Akhir Program Studi Sarjana Teknik Informatika ITB

oleh Yosep Kurniawan NIM: 13503059

Telah disetujui dan disahkan sebagai laporan Tugas Akhir di Bandung, pada tanggal 27 September 2007

Pembimbing,

Tricya E. Widagdo, S.T., M.Sc. NIP: 132164563

ii

RINGKASAN Penjadwalan yang dilakukan dengan baik akan membuat penggunaan resource menjadi lebih efektif. Oleh karena itu, suatu proses kegiatan harus dialokasikan dengan baik dan memenuhi batasan-batasan yang ada. Permasalahan utama yang menjadi kendala dalam melakukan proses penjadwalan adalah data (resource dan batasan) yang banyak dan frekuensi perubahan yang tinggi pada data. Dengan permasalahan seperti ini, proses komputasi dibutuhkan untuk memudahkan proses penjadwalan. Agar batasan dalam bahasa manusia dapat dikomputasi dan memberikan hasil sesuai dengan yang diinginkan, batasan perlu dikonversi menjadi aturan-aturan yang dimengerti oleh komputer. Pada tugas akhir ini, dibangun sebuah model sistem penjadwalan dengan memanfaatkan sistem basis data deduktif untuk menangani sistem penjadwalan dengan data yang banyak dan frekuensi perubahan yang tinggi pada data. Selain itu, dibangun pula langkah-langkah untuk melakukan konversi dari batasan dalam bahasa manusia menjadi aturan dalam basis data deduktif. Sebagai studi kasus, dipilih penjadwalan mata kuliah karena data yang digunakan memiliki karakteristik yang serupa dengan permasalahan penjadwalan umumnya, yaitu data yang banyak dan berubah-ubah. Pada tahap awal, dilakukan analisis terhadap model data, lalu dilanjutkan dengan analisis model proses. Selain itu, dilakukan pula analisis untuk mengkonversi batasan sistem penjadwalan menjadi aturan dalam basis data deduktif. Selanjutnya, analisis pembangunan perangkat lunak dilakukan untuk mendapatkan gambaran mengenai perangkat lunak yang dibangun. Berdasarkan analisis yang dilakukan, perangkat lunak dibangun dengan memanfaatkan basis data deduktif. Basis data deduktif yang digunakan dikembangkan dengan menggunakan basis data relasional dan mesin inferensi. Perangkat lunak yang dibangun merupakan aplikasi berbasis web yang menggunakan sebuah web server dan basis data deduktif. Perangkat lunak dikembangkan dalam bahasa pemrograman PHP dan PSP. Fitur utama yang dimiliki perangkat lunak ini adalah manipulasi resource, manipulasi batasan, proses penjadwalan, pengaturan ulang jadwal solusi, dan menampilkan jadwal solusi dalam bentuk tabel waktu. Kesimpulan yang dapat diambil dari tugas akhir ini adalah model sistem penjadwalan terbagi menjadi dua, yaitu model data dan model proses. Model data dan model proses yang dibangun dapat menyelesaikan permasalahan penjadwalan yang sejenis, yaitu berupa timetabling.

Kata kunci : sistem penjadwalan, basis data deduktif, model data, model proses, timetabling

iii

KATA PENGANTAR Puji syukur kepada Tuhan YME atas bimbingan-Nya sehingga penulis dapat menyelesaikan Tugas Akhir ini. Ucapan terima kasih yang mendalam dihaturkan pada Ibu Tricya E. Widagdo, S.T.,M.Sc. selaku pembimbing Tugas Akhir ini. Terima kasih atas bimbingan, kritik, saran, dan waktu yang telah Ibu luangkan. Terima kasih pula atas motivasi, semangat dan kesabaran dalam setiap bimbingan yang Ibu berikan. Tidak lupa terima kasih juga diucapkan pada pihak-pihak yang telah membantu pelaksanaan Tugas Akhir ini: 1. Ibu Ir. Hira Laksmiwati Zoro, M.Sc., Bapak Adi Mulyanto, S.T., M.T. dan Ibu Yani Widyani, S.T., M.T. selaku dosen penguji, terima kasih atas masukan-masukan dan sarannya. 2. Ibu Henny Yusnita Zubir, B.Sc., M.T. sebagai wali akademik yang telah memberikan bimbingan selama masa perkuliahan. 3. Seluruh dosen Teknik Informatika ITB dan staf pengajar lainnya. Terima kasih diucapkan atas pengajaran dan ilmu yang telah diberikan. 4. Bapak Rasidi, Bapak Ade, dan Mba Nur dan petugas Tata Usaha Akademik lainnya yang telah memberikan bantuan administrasi selama masa perkuliahan dan pengerjaan Tugas Akhir. 5. Mama dan Papa, atas segala doa dan dukungan yang telah diberikan hingga Tugas Akhir ini dapat diselesaikan. 6. Saudara-saudaraku

yang

tidak

lelah-lelahnya

memberi

semangat

untuk

menyelesaikan Tugas Akhir ini. 7. Metta, Allentine, Dian, CK, Arie, Ong, Davis, Jeffrey dan rekan-rekan Teknik Informatika angkatan 2003 atas bantuan, baik dalam hal akademik, maupun lainnya selama masa perkuliahan dan pengerjaan Tugas Akhir. 8. Eko, Cuco, Teguh, Amudi, dan rekan-rekan di laboratorium Basis Data atas dukungan dan kebersamaan yang diberikan selama pengerjaan Tugas Akhir. 9. Seluruh pihak lain yang tidak dapat disebutkan satu-persatu.

iv

Akhir kata, tidak ada kesempurnaan dalam diri manusia dan hasil karyanya, begitu pula dengan Tugas Akhir ini. Semoga Tugas Akhir ini dapat bermanfaat seluas-luasnya bagi siapa saja yang berminat dalam bidang sistem penjadwalan dan basis data deduktif. Saran dan kritik yang membangun selalu diharapkan sebagai perbaikan di masa datang.

Bandung, September 2007

Penulis

v

DAFTAR ISI

LEMBAR PENGESAHAN ....................................................................................................... ii RINGKASAN .......................................................................................................................... iii  KATA PENGANTAR .............................................................................................................. iv  DAFTAR ISI ............................................................................................................................ vi  DAFTAR GAMBAR................................................................................................................ ix  DAFTAR TABEL ..................................................................................................................... x  DAFTAR ALGORITMA ........................................................................................................ xii  Bab I PENDAHULUAN ......................................................................................................... I-1  I.1 

Latar Belakang......................................................................................................... I-1 

I.2 

Rumusan Masalah ................................................................................................... I-2 

I.3 

Tujuan ...................................................................................................................... I-3 

I.4 

Batasan Masalah ...................................................................................................... I-4 

I.5 

Metodologi .............................................................................................................. I-4 

I.6 

Sistematika Pembahasan.......................................................................................... I-5 

Bab II DASAR TEORI .......................................................................................................... II-1  II.1 

Sistem Penjadwalan ............................................................................................... II-1 

II.1.1 

Resource ........................................................................................................ II-1 

II.1.2 

Batasan .......................................................................................................... II-2 

II.1.3 

Penjadwalan ................................................................................................... II-4 

II.1.4 

Timetabling .................................................................................................... II-6 

II.2 

Basis Data Deduktif ............................................................................................... II-7 

II.2.1 

Latar Belakang dan Definisi .......................................................................... II-7 

II.2.2 

Model Datalog ............................................................................................... II-8 

II.2.3 

Mekanisme Inferensi ....................................................................................II-12 

II.2.4 

Aturan Non-Rekursif ....................................................................................II-12 

II.2.5 

Aturan Rekursif ............................................................................................II-12 

II.2.6 

Negasi ...........................................................................................................II-13 

II.3 

Algoritma Greedy [MUN05] ................................................................................II-13 

Bab III ANALISIS ............................................................................................................... III-1  III.1 

Analisis Sistem Penjadwalan ............................................................................ III-1 

III.1.1 

Pendefinisian Fakta ...................................................................................... III-1 

III.1.2 

Pendefinisian Batasan ................................................................................... III-3 

III.1.3 

Pendefinisian Prioritas Resource .................................................................. III-7 

vi

III.2 

Analisis Penyelesaian Masalah Sistem Penjadwalan ....................................... III-7 

III.2.1 

Solusi dari Sistem Penjadwalan .................................................................... III-7 

III.2.2 

Algoritma Pencarian Solusi .......................................................................... III-8 

III.2.3 

Analisis Independensi Data ........................................................................ III-11 

III.3 

Analisis Perancangan Aturan Sistem Penjadwalan ........................................ III-11 

III.4 

Kesimpulan Analisis ....................................................................................... III-15 

Bab IV PEMBANGUNAN PERANGKAT LUNAK .......................................................... IV-1  IV.1 

Deskripsi Umum Perangkat Lunak................................................................... IV-1 

IV.2 

Perancangan Basis Data Deduktif .................................................................... IV-1 

IV.3 

Spesifikasi Kebutuhan Perangkat Lunak .......................................................... IV-3 

IV.3.1 

Kebutuhan Fungsional .................................................................................. IV-3 

IV.3.2 

Kebutuhan Non Fungsional .......................................................................... IV-4 

IV.4 

Model Use Case ............................................................................................... IV-4 

IV.4.1 

Diagram Use Case ........................................................................................ IV-4 

IV.4.2 

Definisi Aktor ............................................................................................... IV-4 

IV.4.3 

Definisi Use Case ......................................................................................... IV-5 

IV.4.4 

Skenario Use Case ........................................................................................ IV-5 

IV.5 

Model Interaksi dengan Diagram Sequence ..................................................... IV-7 

IV.6 

Diagram Kelas Perangkat Lunak .................................................................... IV-12 

IV.7 

Rancangan Antarmuka Perangkat Lunak ....................................................... IV-13 

Bab V IMPLEMENTASI DAN PENGUJIAN ..................................................................... V-1  V.1 

Implementasi Perangkat Lunak ............................................................................. V-1 

V.1.1 

Batasan Perangkat Lunak .............................................................................. V-1 

V.1.2 

Lingkungan Implementasi ............................................................................. V-1 

V.1.3 

Implementasi Kelas ....................................................................................... V-2 

V.1.4 

Implementasi Penggunaan Batasan ............................................................... V-2 

V.2 

Pengujian Perangkat Lunak ................................................................................... V-3 

V.2.1 

Tujuan Pengujian ........................................................................................... V-3 

V.2.2 

Lingkungan Pengujian ................................................................................... V-3 

V.2.3 

Data Pengujian............................................................................................... V-4 

V.2.4 

Skenario Pengujian ........................................................................................ V-5 

V.2.5 

Hasil Pengujian .............................................................................................. V-6 

V.2.5.1 

Pengujian I ................................................................................................. V-6 

V.2.5.2 

Pengujian II ............................................................................................... V-8 

V.2.5.3 

Pengujian III .............................................................................................. V-8 

V.2.5.4 

Pengujian IV .............................................................................................. V-9 

V.2.6 

Evaluasi Hasil Pengujian ............................................................................. V-10 

vii

Bab VI PENUTUP ............................................................................................................... VI-1  VI.1 

Kesimpulan ....................................................................................................... VI-1 

VI.2 

Saran ................................................................................................................. VI-2 

Lampiran A 

Konfigurasi IIS untuk PSP ........................................................................ A-1 

Lampiran B 

Skenario Use Case ..................................................................................... B-1 

Lampiran C 

Diagram Sequence ..................................................................................... C-1 

Lampiran D 

Rancangan Antarmuka Perangkat Lunak .................................................. D-1 

Lampiran E 

Data Pengujian............................................................................................ E-1 

DAFTAR PUSTAKA............................................................................................................. xiii 

viii

DAFTAR GAMBAR Gambar II-1 Kategori-kategori batasan dalam Gantt chart [BAR99] ................................... II-4  Gambar II-2 Hubungan ketiga bagian utama basis data deduktif.......................................... II-8  Gambar II-3 Dependency Graph ..........................................................................................II-11  Gambar III-1 Proses pencapaian solusi penjadwalan ......................................................... III-10  Gambar IV-1 Arsitektur perangkat lunak ............................................................................. IV-1  Gambar IV-2 Mekanisme Aliran Data Aplikasi DedSched - DDBMS ................................ IV-3  Gambar IV-3 Diagram Use Case .......................................................................................... IV-4  Gambar IV-4 Diagram Sequence Manipulasi Resource ....................................................... IV-8  Gambar IV-5 Diagram Sequence Manipulasi Batasan ......................................................... IV-9  Gambar IV-6 Diagram Sequence Proses Penjadwalan Resource ....................................... IV-10  Gambar IV-7 Diagram Sequence Pengaturan Ulang Jadwal Solusi ................................... IV-11  Gambar IV-8 Diagram Sequence Menampilkan Jadwal Solusi ......................................... IV-12  Gambar IV-9 Diagram kelas perangkat lunak .................................................................... IV-13  Gambar IV-10 Rancangan Antarmuka Layar Utama ......................................................... IV-13  Gambar V-1 Data Uji Pengujian Pengaturan Ulang Solusi Jadwal ..................................... V-10  Gambar D-1 Rancangan Antarmuka Manipulasi Resource................................................... D-1 Gambar D-2 Rancangan Antarmuka Manipulasi Batasan ..................................................... D-2 Gambar D-3 Rancangan Antarmuka Menjadwalkan Resource ............................................. D-3 Gambar D-4 Rancangan Antarmuka Pengaturan Ulang Jadwal Solusi................................. D-4 Gambar D-5 Rancangan Antarmuka Menampilkan Jadwal Solusi ....................................... D-5

ix

DAFTAR TABEL

Tabel III-1 Contoh hubungan antara batasan dan resource .................................................. III-4  Tabel III-2 Contoh Pengelompokan pada Sistem Penjadwalan Mata Kuliah ...................... III-4  Tabel IV-1 Tabel kebutuhan Fungsional .............................................................................. IV-4  Tabel IV-2 Tabel kebutuhan Non-Fungsional ...................................................................... IV-4  Tabel IV-3 Tabel Definisi Aktor .......................................................................................... IV-5  Tabel IV-4 Tabel Definisi Use Case .................................................................................... IV-5  Tabel IV-5 Tabel Skenario Use Case Manipulasi Resource ................................................ IV-5  Tabel IV-6 Tabel Skenario Use Case Manipulasi Batasan .................................................. IV-6  Tabel IV-7 Tabel Skenario Use Case Penjadwalan.............................................................. IV-6  Tabel IV-8 Tabel Skenario Use Case Mengatur Ulang Jadwal Solusi ................................. IV-7  Tabel IV-9 Tabel Skenario Use Case Menampilkan Jadwal Solusi ..................................... IV-7  Tabel IV-10 Keterangan Antarmuka Layar Utama ............................................................ IV-14  Tabel V-1 Daftar nama file fisik perangkat lunak ................................................................. V-2  Tabel V-2 Data pengujian: Fakta resource ............................................................................ V-4  Tabel V-3 Pengujian I: Fakta kelas mata kuliah.................................................................... V-6  Tabel V-4 Pengujian I: Fakta ruangan ................................................................................... V-6  Tabel V-5 Pengujian II: Fakta kelas mata kuliah .................................................................. V-8  Tabel V-6 Pengujian III: Fakta kelas mata kuliah ................................................................. V-8  Tabel B-1 Skenario Alternatif Use Case Manipulasi Resource ............................................ B-1 Tabel B-2 Skenario Alternatif Use Case Manipulasi Batasan............................................... B-2 Tabel B-3 Skenario Alternatif Use Case Penjadwalan .......................................................... B-4 Tabel B-4 Skenario Alternatif Use Case Mengatur Ulang Jadwal Solusi ............................. B-4 Tabel B-5 Skenario Alternatif Use Case Menampilkan Jadwal Solusi ................................. B-5 Tabel C-1 Aksi Diagram Sequence Manipulasi Resource ..................................................... C-1 Tabel C-2 Aksi Diagram Sequence Manipulasi Batasan ....................................................... C-1 Tabel C-3 Aksi Diagram Sequence Proses Penjadwalan Resource ....................................... C-2 Tabel C-4 Aksi Diagram Sequence Mengatur Ulang Jadwal Solusi ..................................... C-3 Tabel C-5 Aksi Diagram Sequence Menampilkan Jadwal Solusi ......................................... C-4 Tabel D-1 Keterangan Antarmuka Manipulasi Resource...................................................... D-1 Tabel D-2 Keterangan Antarmuka Manipulasi Batasan ........................................................ D-2 Tabel D-3 Keterangan Antarmuka Menjadwalkan Resource ................................................ D-4 Tabel D-4 Keterangan Antarmuka Mengatur Ulang Jadwal Solusi ...................................... D-4 Tabel D-5 Keterangan Antarmuka Menampilkan Jadwal Solusi .......................................... D-5

x

Tabel E-1 Data Pengujian: Fakta Mata Kuliah ....................................................................... E-1 Tabel E-2 Data Pengujian: Fakta Kelas Mata Kuliah ............................................................. E-2 Tabel E-3 Data Pengujian: Fakta Dosen................................................................................. E-4 Tabel E-4 Data Pengujian: Fakta Waktu ................................................................................ E-5 Tabel E-5 Data Pengujian: Fakta Ruangan............................................................................. E-6 Tabel E-6 Data Pengujian Batasan Prioritas........................................................................... E-7 Tabel E-7 Data Pengujian Batasan Tipe I dan Tipe II ............................................................ E-7 Tabel E-8 Data Pengujian Aturan Hasil Konversi Batasan Tipe I dan Tipe II ....................... E-9

xi

DAFTAR ALGORITMA Algoritma III-1 Aturan allocated_class ................................................................................ III-3  Algoritma III-2 Aturan avail_class ....................................................................................... III-3  Algoritma III-3 Aturan appropriate_class ............................................................................ III-5  Algoritma III-4 Aturan appropriate_class2 .......................................................................... III-6  Algoritma III-5 Aturan weightOnClass ................................................................................ III-6  Algoritma III-6 Sintaks konversi batasan menjadi aturan .................................................. III-12  Algoritma III-7 Aturan avail_class_capacity ..................................................................... III-12  Algoritma III-8 Sintaks konversi batasan menjadi aturan (2) ............................................ III-13  Algoritma III-9 Contoh aturan dengan fakta-fakta turunan................................................ III-14  Algoritma III-10 Aturan avail_slot_on_class ..................................................................... III-14  Algoritma III-11Aturan not_avail_slot_on_dosen ............................................................. III-15  Algoritma III-12 Aturan slot_avail ..................................................................................... III-15  Algoritma E-1 Aturan prioritas_mk ....................................................................................... E-7 Algoritma E-2 Aturan prioritas_mk2 ..................................................................................... E-7

xii