BAB III ANALISIS Analisis yang dilakukan pada tugas akhir ini mencakup:
1. Analisis terhadap sistem penjadwalan. 2. Analisis terhadap penyelesaian masalah sistem penjadwalan. 3. Analisis terhadap perancangan aturan pada sistem penjadwalan. Analisis terhadap sistem penjadwalan dilakukan pertama kali dengan tujuan untuk mendapatkan definisi mengenai model data yang dibangun pada sistem penjadwalan, mencakup pendefinisian fakta dan batasan. Selanjutnya, tujuan dari analisis berikutnya adalah untuk mengetahui solusi yang ingin dicapai, algoritma umum yang digunakan untuk menyelesaikan permasalahan yang ada dan bagaimana mekanisme independensi data terhadap aplikasi. Hasil analisis penyelesaian masalah berupa alur proses seperti yang tergambar pada Gambar III-1 merupakan model proses sistem penjadwalan. Kemudian analisis terhadap perancangan aturan pada sistem penjadwalan dilakukan untuk memperoleh penjelasan mengenai proses konversi batasan dalam bahasa manusia menjadi aturan-aturan yang dimengerti oleh komputer.
III.1 Analisis Sistem Penjadwalan Pada subbab ini dibahas mengenai bagaimana fakta, batasan, dan prioritas didefinisikan dalam sistem penjadwalan. Pendefinisian fakta dan batasan yang dibahas pada subbab ini merupakan model data sistem penjadwalan yang generik.
III.1.1 Pendefinisian Fakta Fakta adalah suatu informasi yang ada pada dunia nyata. Dalam sistem penjadwalan, fakta dapat berupa data mengenai resource pada sistem penjadwalan atau dapat pula berupa informasi mengenai hubungan antara satu resource dengan resource yang lain. Fakta dapat merupakan fakta elementer atau merupakan fakta turunan. Fakta turunan yaitu fakta yang diturunkan dari fakta (fakta elementer dan fakta turunan) yang ada. Fakta turunan diperoleh melalui mekanisme deduksi fakta-fakta yang ada dengan menggunakan aturan-aturan. Beberapa contoh fakta (fakta elementer) yang terdapat pada sistem penjadwalan mata kuliah yaitu fakta kelas mata kuliah, mata kuliah, dosen, ruangan kelas, waktu, mahasiswa, dan jadwal perkuliahan. Setiap fakta elementer ini memiliki beberapa atribut. Sebagai contoh,
III-1
III-2 fakta kelas mata kuliah memiliki beberapa atribut, yaitu kode mata kuliah, nomor kelas (K1, K2, K3, dst.), NIP dosen, jumlah perkiraan peserta, dan program studi penyelenggara. Untuk mendapatkan fakta mengenai ruangan kelas yang tersedia pada slot waktu X, dibutuhkan dua buah fakta, yaitu fakta mengenai ruangan kelas yang ada dan fakta mengenai ruangan kelas yang telah dialokasikan untuk jadwal perkuliahan pada slot waktu X. Fakta mengenai ruangan kelas dan jadwal perkuliahan merupakan contoh fakta yang berupa fakta elementer. Fakta jadwal perkuliahan memiliki atribut, antara lain kode mata kuliah, nomor kelas, slot waktu, ruangan kelas, dan grup mahasiswa. Fakta mengenai ruangan kelas yang telah dialokasikan untuk jadwal perkuliahan pada slot waktu X dapat diperoleh dengan cara melakukan proyeksi ruangan kelas terhadap fakta jadwal perkuliahan pada slot waktu X. Fakta jadwal perkuliahan pada slot waktu X diperoleh dengan menerapkan seleksi fakta jadwal perkuliahan untuk slot waktu X. Selanjutnya, untuk mendapatkan fakta mengenai ruangan kelas yang tersedia pada slot waktu X, fakta mengenai ruangan kelas yang ada dikenakan operasi SET DIFFERENCE dengan fakta mengenai ruangan kelas yang telah dialokasikan untuk jadwal perkuliahan pada slot waktu X. Berikut adalah penjabarannya dalam operasi aljabar relasional: Relasi: r1 = jadwal(Kode_mk, Nomor_Kelas, Waktu, Kode_Ruang, Mahasiswa) r2 = ruangan(Kode_Ruang, Kapasitas)
Fakta mengenai ruangan kelas yang telah dialokasikan untuk jadwal perkuliahan pada slot waktu X: f1 Å ΠKode_Ruang ( σWaktu=’X’ ( r1 ) ) (Melakukan
proyeksi
Kode
ruang
dari
hasil
seleksi
terhadap
tabel jadwal
untuk mendapatkan Kode ruang mana saja yang telah digunakan untuk jadwal perkuliahan)
Fakta mengenai ruangan kelas yang tersedia pada slot waktu X: f2 Å ΠKode_Ruang ( r2 ) - f1 (Mencari ruangan yang belum digunakan untuk jadwal perkuliahan, yaitu dengan cara mengurangkan semua ruangan yang ada dengan semua ruangan yang telah digunakan)
Fakta di atas diperoleh dengan menggunakan pendekatan relasional. Pada basis data deduktif, untuk mendapatkan fakta mengenai ruangan kelas yang tersedia pada slot waktu X, dapat dilakukan dengan cara mendeduksi fakta turunan allocated_class dan avail_class dari fakta yang ada. Berikut adalah representasinya: Fakta dasar yang terdapat pada basis data adalah sebagai berikut a. jadwal(Kode_mk, Nomor_Kelas, Waktu, Kode_Ruang, Mahasiswa). b. ruangan(Kode_Ruang, Kapasitas).
III-3 Aturan: a. Fakta mengenai ruangan kelas yang telah dialokasikan untuk jadwal perkuliahan pada slot waktu X dapat dilihat pada Algoritma III-1. allocated_class(Kode_Ruang) Å jadwal(_, _, X, Kode_Ruang, _).
Algoritma III-1 Aturan allocated_class
b. Fakta mengenai ruangan kelas yang tersedia pada slot waktu X dapat dilihat pada Algoritma III-2. avail_class(Kode_Ruang) Å ruangan(Kode_Ruang, _) ∧ ~(allocated_class(Kode_Ruang)).
Algoritma III-2 Aturan avail_class
Fakta mengenai ruangan kelas yang tersedia pada slot waktu X merupakan contoh dari fakta turunan pada sistem penjadwalan mata kuliah karena untuk mendapatkannya tidak dapat diperoleh secara langsung melainkan membutuhkan proses penurunan dari fakta-fakta yang ada.
III.1.2 Pendefinisian Batasan Batasan pada sistem penjadwalan adalah definisi atau informasi yang membatasi pencarian solusi pada proses penjadwalan. Umumnya permasalahan dalam dunia nyata berkaitan dengan batasan-batasan tertentu. Oleh karena itu, pemrograman dengan menggunakan batasan lebih banyak digunakan karena pendekatan ini mendekati keadaan dunia nyata yang sulit didefinisikan. Selain itu, batasan didefinisikan dengan bahasa yang deklaratif sehingga lebih mudah bagi manusia untuk mendefinisikannya. Berikut adalah beberapa contoh batasan yang terdapat pada sistem penjadwalan mata kuliah. 1. Jumlah peserta suatu mata kuliah harus lebih kecil daripada kapasitas ruangan yang akan ditempatinya. 2. Sebuah ruangan hanya dapat digunakan oleh sebuah mata kuliah pada satu waktu. Sebuah batasan dapat membatasi satu atau lebih resource. Sebagai contohnya dapat dilihat pada Tabel III-1. Untuk memudahkan pendefinisian batasan pada sistem penjadwalan, batasan dapat dimasukkan ke dalam kelompok tertentu sesuai dengan resource yang dibatasinya. Apabila sebuah batasan membatasi dua atau lebih resource, maka sebaiknya dibuat sebuah kelompok baru yang dapat merepresentasikan batasan tersebut. Salah satu contoh pengelompokan yang dilakukan pada sistem penjadwalan mata kuliah dapat dilihat pada Tabel III-2. Pada sistem penjadwalan terdapat dua jenis batasan utama, yaitu: 1. Batasan terhadap urutan (batasan prioritas)
III-4 Batasan terhadap urutan mengatur prioritas dari resource yang akan dijadwalkan, sehingga resource dengan prioritas tertinggi akan dijadwalkan terlebih dahulu. Contoh: mata kuliah dengan jumlah peserta yang banyak dijadwalkan terlebih dahulu. 2. Batasan terhadap penjadwalan. Batasan terhadap penjadwalan dibagi menjadi dua jenis, yaitu: 2.1 Batasan tipe I Batasan tipe I adalah batasan yang harus dipenuhi, sering juga disebut sebagai hard constraint. Contoh: jumlah peserta suatu kelas mata kuliah harus lebih kecil atau sama dengan kapasitas ruangan yang akan ditempatinya 2.2 Batasan tipe II Batasan tipe II adalah batasan yang sebaiknya dipenuhi karena akan meningkatkan efisiensi dari penggunaan resource pada sistem penjadwalan (menambah nilai dari solusi yang dihasilkan), dikenal juga sebagai soft constraint. Contoh: dosen X lebih menyukai mengajar di ruangan yang berada pada lantai 3 di gedung Labtek V. Tabel III-1 Contoh hubungan antara batasan dan resource
No
Batasan
1
Jumlah peserta suatu kelas mata kuliah harus lebih kecil
Resource Ruangan Kelas
Waktu
9
daripada kapasitas ruangan yang akan ditempatinya 2
Sebuah ruangan hanya dapat digunakan oleh sebuah
9
9
9
9
kelas mata kuliah pada satu waktu 3
Seorang dosen hanya dapat mengajar sebuah kelas mata kuliah dalam satu waktu
4
Mata kuliah wajib pada tingkat yang sama tidak
9
dijadwalkan pada waktu yang sama Tabel III-2 Contoh Pengelompokan pada Sistem Penjadwalan Mata Kuliah
No.
Kelompok Batasan
Batasan
1.
Kelas mata kuliah
i. Mata kuliah memiliki jadwal sejumlah sks yang dimilikinya.
dan jadwal mata kuliah 2.
Dosen dan slot waktu
3.
Mata kuliah dan ruangan kelas
1. Dosen hanya dapat mengajar sebuah kelas mata kuliah pada satu slot waktu. i. Mata kuliah yang memiliki jumlah perkiraan peserta yang besar dialokasikan terlebih dahulu agar dapat menempati ruangan kelas dengan kapasitas yang cukup.
III-5 No.
Kelompok Batasan
Batasan
4.
Mata kuliah, slot
i. Sebuah ruangan kelas hanya dapat digunakan oleh sebuah
waktu dan ruangan
kelas mata kuliah pada satu waktu.
kelas
Contoh penggunaan batasan prioritas dan tipe II dijelaskan pada bagian berikut ini, sedangkan untuk batasan tipe I dijelaskan lebih detail pada Subbab III.3. Pada basis data deduktif, batasan prioritas dikenakan pada semua resource yang akan dijadwalkan dan batasan tipe I harus dipenuhi oleh semua kumpulan fakta yang akan menjadi kandidat solusi, sedangkan batasan tipe II diterapkan pada semua kumpulan fakta yang memenuhi batasan tipe I. Untuk semua resource akan diberikan bobot yang sesuai dengan batasan prioritas yang ada. Fakta yang memiliki prioritas tertinggi (misal: bobot tertinggi, terendah) akan diambil oleh sistem pertama kali untuk dicarikan pasangan slot jadwalnya. Lain halnya dengan penggunaan bobot pada batasan tipe II, setiap kumpulan fakta yang dapat memenuhi batasan ini diberikan sejumlah bobot tertentu sesuai dengan bobot yang dimiliki batasan tersebut. Contoh penggunaan batasan prioritas dalam menentukan resource yang akan dijadwalkan terlebih dahulu dalam sistem penjadwalan mata kuliah: terdapat batasan bahwa mata kuliah dengan jumlah peserta yang banyak dijadwalkan terlebih dahulu. Dalam bentuk aturan dalam basis data deduktif, transformasi batasan ini dapat dilihat pada Algoritma III-3. appropriate_class(Kode_mk, Kelas_mk, Jml_bobot) Å mata_kuliah(Kode_mk, _, Kelas_mk, _, _, Jml_peserta, _) ∧ Jml_bobot = Jml_peserta.
Algoritma III-3 Aturan appropriate_class
Setiap kelas mata kuliah akan diberikan bobot sesuai dengan perkiraan jumlah pesertanya. Misalkan terdapat tiga buah kelas mata kuliah yang akan dijadwalkan: a. IF3211 K1 dengan jumlah perkiraan peserta 90. b. IF3211 K2 dengan jumlah perkiraan peserta 80. c. IF5011 K1 dengan jumlah perkiraan peserta 85. Dengan mekanisme deduksi dan aturan yang ada dihasilkan tiga fakta turunan, yaitu a. appropriate_class(‘IF3211’, ‘01’, 90), b. appropriate_class(‘IF3211’, ‘02’, 80), dan c. appropriate_class(‘IF5011’, ‘01’, 85). Selanjutnya, fakta turunan yang memiliki bobot terbesar akan digunakan oleh sistem untuk dicarikan pasangan slot jadwalnya terlebih dahulu. Fakta lainnya tetap disimpan sebagai fakta yang akan digunakan dalam proses backtrack.
III-6 Seandainya pada sistem penjadwalan, jumlah peserta tidak begitu penting dibandingkan dengan tingkat kelas mata kuliah tersebut, maka aturan appropriate_class dapat disesuaikan menjadi Algoritma III-4. appropriate_class2(Kode_mk, Kelas_mk, Jml_bobot) Å mata_kuliah(Kode_mk, getLevel(Kode_mk,
_,
Level)
Kelas_mk, ∧
Jml_bobot
_, is
_,
Jml_peserta,
(1/2
*
_)
Jml_peserta)
∧ +
(Level*100).
Algoritma III-4 Aturan appropriate_class2
Predikat getLevel adalah suatu aturan yang mengembalikan tingkat dari kelas mata kuliah dan menyimpannya di variabel Level. Dengan mekanisme deduksi dan aturan yang ada dihasilkan tiga fakta turunan, yaitu: a. appropriate_class2(‘IF3211’, ‘01’, 350). b. appropriate_class2(‘IF3211’, ‘02’, 340). c. appropriate_class2(‘IF5011’, ‘01’, 542.5). Hal ini akan menyebabkan bobot kelas mata kuliah IF5011 K1 menjadi lebih tinggi daripada kelas mata kuliah lainnya dan mendapat prioritas untuk dicarikan pasangan slot jadwalnya terlebih dahulu. Sama halnya pada penggunaan batasan prioritas, batasan tipe II juga menerapkan bobot pada pemilihan solusi jadwal. Perbedaannya hanya terletak pada objek yang dikenai batasan dan besarnya bobot yang diperoleh setiap fakta. Pada batasan tipe II hanya kumpulan fakta yang memenuhi batasan tipe I saja yang dikenai batasan ini dan mendapatkan bobot sesuai dengan batasan tipe II yang dapat dipenuhi. Contoh penggunaan batasan tipe II dalam sistem penjadwalan mata kuliah: terdapat batasan bahwa dosen tertentu (misal: dosen X) ingin mengajar di ruangan yang berada di lantai 3 di gedung Labtek V. Untuk memenuhi batasan tipe II ini, basis data deduktif memerlukan beberapa fakta utama antara lain: a. ruangan(kode ruangan, kapasitas, lokasi, lantai). b. kelas_mk(kode mk, nomor kelas, nip dosen, jml peserta). Misalkan bobot untuk batasan ini adalah 50, dengan memanfaatkan kedua fakta utama, dapat dibangun sebuah aturan untuk mendapatkan bobot setiap kumpulan fakta yang memenuhi batasan tipe I dan batasan tipe II ini. Contoh definisi aturan batasan tipe II dapat dilihat pada Algoritma III-5. weightOnClass(Kode_mk, Kode_ruang, BobotOld, BobotNew) Å (ruangan (Kode_ruang, _, ‘labtekV’, 3) ∧ kelas_mk(Kode_mk, _, ‘X’, _)) Æ BobotNew is BobotOld + 50; BobotNew is BobotOld + 0.
Algoritma III-5 Aturan weightOnClass
Sebagai catatan, masukan untuk predikat ini adalah kumpulan fakta yang memenuhi batasan tipe I yaitu fakta berupa jadwal sementara yang berisi kode mata kuliah, nomor kelas,
III-7 slot waktu, kode ruangan dan grup mahasiswa. Ketika kumpulan fakta ini dikenakan terhadap batasan tipe II, maka jadwal sementara yang telah dihasilkan akan ditambahkan dengan atribut bobot di mana nilai awalnya dapat berjumlah lebih dari atau sama dengan 0.
III.1.3 Pendefinisian Prioritas Resource Selain fakta dan batasan, terdapat komponen lainnya yang juga perlu didefinisikan, yaitu prioritas dari setiap resource yang ada. Sebagai contoh dalam sistem penjadwalan mata kuliah, resource dapat diberi bobot berdasarkan jumlah perkiraan peserta yang mengikuti kelas mata kuliah, jumlah kelas yang dimiliki mata kuliah (misal: K1, K2, K3), atau tingkat mata kuliah. Dalam dunia nyata, prioritas setiap sistem penjadwalan mungkin berbeda. Hal ini bergantung pada beberapa faktor seperti pengguna sistem penjadwalan dan jenis sistem penjadwalan. Sebagai contoh pada sistem penjadwalan mata kuliah: setiap universitas memiliki peraturan dan kebijakan masing-masing. Hal ini akan mempengaruhi pendefinisian prioritas dalam sistem
penjadwalan
pada
masing-masing
universitas
tersebut,
sehingga
besar
kemungkinannya bahwa prioritas dari sistem penjadwalan yang didefinisikan juga akan berbeda. Selain itu, dalam proses pencarian solusi, faktor prioritas sangat mempengaruhi solusi yang akan ditemukan. Secara umum, setiap resource dikenakan batasan prioritas yang ada dan mendapatkan bobot tertentu. Kemudian, prioritas dari setiap resource dalam proses penjadwalan ditentukan dengan memanfaatkan bobot ini.
III.2 Analisis Penyelesaian Masalah Sistem Penjadwalan Pada bagian ini akan dibahas mengenai bagaimana solusi yang dihasillkan dari sistem penjadwalan, komponen pemroses dan peranannya masing-masing dalam proses pencarian solusi, langkah-langkah untuk mendapatkan jadwal sesuai dengan batasan yang ada, dan efek dari perubahan terhadap batasan dan fakta yang ada terhadap sistem penjadwalan.
III.2.1 Solusi dari Sistem Penjadwalan Solusi yang akan dicapai pada sistem penjadwalan ini adalah sebuah jadwal yang merupakan hasil dari pengalokasian resource yang ada ke dalam slot-slot waktu yang tersedia. Solusi ini memiliki beberapa karakteristik sebagai berikut. 1. Solusi memuat semua jadwal resource yang terdaftar pada sistem penjadwalan. 2. Proses pencarian solusi mengikuti batasan prioritas yang ada. Solusi harus memenuhi semua batasan tipe I dan memenuhi sebanyak-banyaknya batasan tipe II.
III-8 3. Solusi bersifat unik untuk satu kumpulan batasan. III.2.2 Algoritma Pencarian Solusi Untuk mendapatkan solusi untuk sistem penjadwalan seperti yang telah dijelaskan pada Subbab III.2.1 diperlukan sebuah proses pencapaian solusi penjadwalan sebagai berikut. Proses ini digambarkan pada Gambar III-1. 1. Mendefinisikan fakta dan batasan. Fakta-fakta mengenai resource dan aturan untuk mendapatkan fakta turunan perlu didefinisikan terlebih dahulu. Aturan untuk mendapatkan fakta turunan juga berkaitan dengan pendefinisian batasan. Dalam mendefinisikan batasan, batasan yang ada dibagi ke dalam kategorinya masing-masing. Kategori batasan, seperti telah dijelaskan sebelumnya, terdiri dari batasan yang bersifat wajib dan mutlak harus dipenuhi (batasan tipe I) dan batasan yang sifatnya akan meningkatkan efisiensi dari penggunaan resource (batasan tipe II). Selain itu, terdapat juga batasan prioritas yang diterapkan pada semua resource untuk mendapatkan prioritasnya masing-masing. Batasan tipe II bersifat opsional relatif terhadap kebutuhan sistem penjadwalan. Batasan tipe II dapat pula menjadi batasan yang wajib dipenuhi oleh sistem penjadwalan tergantung kebutuhan dari sistem penjadwalan yang akan dibangun. Pada tahap pendefinisian fakta dan batasan juga didefinisikan besarnya bobot setiap batasan prioritas dan batasan tipe II. Besarnya bobot dapat bergantung pada beberapa contoh faktor berikut: a. Jenis dan jumlah resource yang terkait. Semakin banyak resource yang terkait maka bobotnya akan semakin tinggi. b. Besarnya pengaruh terhadap solusi apabila batasan tidak dipenuhi.
2. Pembobotan resource dan penentuan prioritas Pada tahap ini, prinsip kerja pada algoritma greedy digunakan untuk menentukan resource yang akan dijadwalkan pertama kali. 2.1. Basis data deduktif akan memberikan bobot pada setiap resource yang belum dan akan dijadwalkan. Sebagai contoh pada sistem penjadwalan mata kuliah: perhitungan bobot resource dapat dilakukan berdasarkan jumlah perkiraan peserta yang mengikuti kelas mata kuliah, jumlah kelas yang dimiliki mata kuliah (misal: K1, K2, K3), tingkat mata kuliah, atau ketiganya. 2.2. Setelah semua resource dibobotkan, aplikasi akan memberikan prioritas berdasarkan bobot setiap resource. 2.3. Aplikasi memilih sebuah resource yang memiliki prioritas tertinggi dari kumpulan resource yang ada untuk dijadwalkan.
III-9
3. Pencarian pasangan slot jadwal untuk resource yang dipilih. Proses dilanjutkan oleh basis data deduktif, yaitu melakukan proses pencarian fakta mengenai pasangan slot jadwal yang tersedia untuk resource yang dipilih. Kemudian, basis data deduktif juga memberikan bobot setiap pasangan slot jadwal sesuai dengan batasan tipe II yang dapat dipenuhi oleh pasangan slot jadwal. Sejumlah pasangan slot jadwal beserta bobotnya ini kemudian dikirimkan kembali ke aplikasi untuk diproses lebih lanjut.
4. Penentuan solusi pasangan slot jadwal. Pada tahap ini, prinsip kerja pada algoritma greedy digunakan untuk menentukan pasangan slot jadwal yang dipilih, yaitu pemilihan pasangan slot jadwal dengan bobot tertinggi. Dari sejumlah pasangan slot jadwal dan bobot yang diberikan, aplikasi akan memilih sebuah pasangan slot jadwal yang memiliki bobot tertinggi terlebih dahulu untuk dijadikan solusi. Seandainya aplikasi tidak dapat menemukan solusi, maka akan dilakukan backtrack. Pada saat terjadi backtrack, solusi yang telah dipilih tidak akan menjadi kandidat solusi pada proses pencarian solusi. Selanjutnya, solusi fakta jadwal yang telah persisten akan dibatalkan dan diganti dengan solusi lainnya yang memiliki bobot tertinggi berikutnya (bobot kedua tertinggi, bobot ketiga tertinggi, dst).
5. Penyimpanan solusi pasangan jadwal pada basis data deduktif. Setelah solusi ditemukan, maka aplikasi akan mengirimkan query kepada basis data deduktif untuk menyimpan solusi fakta jadwal untuk resource yang dipilih.
Proses 2 hingga proses 5 diulang hingga semua resource dijadwalkan.
6. Pengaturan ulang solusi jadwal. Setelah semua resource dijadwalkan, aplikasi dapat melakukan pengecekan terhadap solusi jadwal yang dihasilkan. Pada tahap ini, hasil yang terbentuk dapat diatur ulang oleh pengguna apabila memungkinkan. Pengaturan ulang dilakukan secara manual oleh pengguna dengan langkah-langkah sebagai berikut: a. Pengguna memilih jadwal solusi yang ingin diatur ulang. Aplikasi menampilkan pasangan slot jadwal lain yang dapat digunakan. b. Pengguna memilih salah satu dari pasangan slot jadwal lain untuk digunakan. Aplikasi menyimpan jadwal solusi hasil pengaturan ulang. c. Pengguna melakukan pengecekan terhadap jadwal solusi yang diatur ulang.
III-10
I. Pendefinisian Fakta dan Batasan II. Komputasi
APLIKASI 2.2 Menentukan prioritas semua resource yang akan dijadwalkan 2.3 Menentukan sebuah resource untuk dijadwalkan 4. Menentukan solusi dan melakukan backtrack apabila tidak ditemukan solusi 5. Menyimpan solusi pada basis data deduktif 6. Melakukan pengecekan dan pengaturan ulang jadwal solusi
** Basis Data Deduktif (DDB) 2.1 Memberikan bobot untuk semua resource yang akan dijadwalkan dengan menerapkan batasan prioritas * 3. Menghasilkan pasangan slot jadwal yang memenuhi batasan tipe I * beserta bobot yang diperoleh dari batasan tipe II * yang berhasil dipenuhi
III. Pembangunan Tabel Waktu Solusi Jadwal Oleh Aplikasi Keterangan: * Batasan prioritas adalah batasan yang menentukan urutan penjadwalan dari resource secara tidak langsung Batasan tipe I adalah batasan yang harus dipenuhi. Batasan tipe II adalah batasan yang sebaiknya dipenuhi untuk meningkatkan efisiensi resource. ** Proses diulang sampai semua resource telah terjadwalkan. Gambar III-1 Proses pencapaian solusi penjadwalan
7. Penyusunan solusi jadwal. Selanjutnya fakta-fakta pada basis data deduktif disusun oleh aplikasi sehingga membentuk tabel waktu yang berisi penjadwalan resource.
III-11
III.2.3 Analisis Independensi Data Independensi data perlu dijaga dengan tujuan agar aplikasi tetap dapat digunakan untuk data yang berbeda. Pengertian dari data yang berbeda adalah data memiliki model yang sama dengan model yang dapat diselesaikan oleh aplikasi, tetapi isi dari data tersebut berbeda. Contoh: model data untuk penjadwalan mata kuliah di universitas dan model data untuk penjadwalan mata pelajaran sekolah adalah sama, tetapi data yang terdapat di dalamnya adalah berbeda. Seperti yang telah digambarkan pada Gambar III-1, sistem ini memiliki dua buah komponen pemroses, yaitu aplikasi dan basis data deduktif. Hubungan komunikasi di antara kedua komponen ini menggambarkan bagaimana data, dalam basis data deduktif, dapat bersifat independen terhadap aplikasi. Basis data deduktif mengatur bagaimana fakta turunan diperoleh dari mekanisme deduksi dan mekanisme penyimpanan data (fakta dan aturan), sedangkan aplikasi mengatur bagaimana proses penjadwalan dimulai, dilakukan dan diakhiri. Selain data yang berbeda, aplikasi dengan data yang independen tetap dapat memberikan hasil meskipun terjadi perubahan terhadap fakta dan batasan. Secara umum, perubahan terhadap fakta dan batasan akan mempengaruhi solusi yang dihasilkan. Perubahan yang terjadi dapat mencapai tahapan hingga tidak ditemukannya solusi yang memenuhi semua batasan yang ada. Hal ini dapat terjadi apabila tidak ditemukan sebuah solusi (fakta mengenai resource) yang dapat memenuhi semua batasan yang ada. Model dari sistem penjadwalan yang telah dibangun akan menjaga definisi dari batasan dan fakta yang dapat diterima oleh sistem. Oleh karena itu, perubahan terhadap batasan dan fakta hanya akan mempengaruhi solusi yang dihasilkan, tapi tetap menggunakan model yang telah dibangun.
III.3 Analisis Perancangan Aturan Sistem Penjadwalan Basis data deduktif mampu mendeduksi fakta yang ada menjadi fakta-fakta turunan. Kemampuan ini menjadi alasan utama penggunaan basis data deduktif dalam proses penyelesaian masalah sistem penjadwalan. Basis data deduktif menggunakan aturan untuk melakukan mekanisme inferensi untuk mendapatkan solusi hasil yang merupakan fakta turunan dari fakta-fakta yang ada. Aturan yang digunakan merupakan hasil konversi dari batasan dalam bahasa manusia yang terdapat pada sistem penjadwalan. Pada subbab ini dibahas mengenai bagaimana konversi dari batasan-batasan yang telah didefinisikan menjadi aturan-aturan dalam basis data deduktif. Pemroses hanya mengenali aturan-aturan yang ditulis dalam sintaks suatu bahasa tertentu. Agar sebuah batasan dapat dikenali oleh pemroses (komputer) maka diperlukan suatu
III-12 metode untuk melakukan konversi dari batasan yang telah didefnisikan menjadi aturan-aturan yang dikenal oleh pemroses. Berikut adalah beberapa hal yang perlu diperhatikan dalam melakukan konversi batasan menjadi aturan. 1. Sebuah batasan dapat terkait dengan satu atau banyak resource. 2. Satu batasan dapat dikonversi menjadi beberapa aturan, tapi tidak sebaliknya. Satu aturan hanya akan merupakan hasil konversi dari sebuah batasan. Metode untuk mengkonversi batasan menjadi aturan adalah sebagai berikut: 1. Jika batasan terkait dengan fakta-fakta yang telah ada, maka batasan dapat langsung dikonversi menjadi aturan seperti pada Algoritma III-6. ([<parameter1>[,<parameter2>, ...]) Å ∧ .
Algoritma III-6 Sintaks konversi batasan menjadi aturan
Contoh pada sistem penjadwalan mata kuliah: Batasan yang akan dikonversi menjadi aturan adalah jumlah peserta suatu mata kuliah harus lebih kecil daripada kapasitas ruangan yang akan ditempatinya. Untuk membuat aturan dari batasan ini, perlu dikaji resource apa saja yang terlibat di dalamnya. Batasan pada contoh ini terkait dengan kapasitas ruangan kelas yang terdapat pada fakta ruangan dan perkiraan jumlah peserta mata kuliah yang akan dijadwalkan yang terdapat pada fakta mata kuliah. Definisi fakta yang terkait adalah sebagai berikut. a. mata_kuliah
(Kode_mk,
Nama_mk,
Kelas_mk,
Jml_SKS,
NIP_dosen,
Jml_peserta, Sifat) b. ruangan (Kode_ruang, Kapasitas_ruang)
Oleh karena itu, aturan yang dibangun harus menggunakan kedua fakta ini untuk menurunkan aturan mengenai kode ruangan kelas yang dapat digunakan untuk menjadwalkan mata kuliah dengan kode tertentu. Bentuk konversi yang dapat dilakukan dapat dilihat pada Algoritma III-7. (1) avail_class_capacity (Kode_mk, Kelas_mk, Kode_ruang) Å (2)
mata_kuliah(Kode_mk, Nama_mk, Kelas_mk, SKS, NIP, Jml_peserta,
(3)
Sifat) ∧ ruangan(Kode_ruang, Kapasitas) ∧ Jml_peserta =<
(4)
Kapasitas.
Algoritma III-7 Aturan avail_class_capacity
Baris (1) pada aturan utama adalah head dari aturan, sedangkan (2), (3), dan (4) adalah body dari aturan. Aturan ini akan menghasilkan fakta turunan tentang semua ruangan yang dapat digunakan untuk kelas mata kuliah Kode_mk – Kelas_mk dengan batasan jumlah peserta lebih kecil atau sama dengan kapasitas ruangan kelas. Aturan
III-13 yang dibangun ini dapat digunakan untuk melakukan pengecekan maupun pencarian. Seperti pada contoh di atas, aturan dapat mengecek apakah kelas mata kuliah Kode_mk – Kelas mk dapat menempati ruangan Kode_ruang terkait dengan batasan jumlah peserta lebih kecil atau sama dengan kapasitas ruangan. 2. Jika batasan membutuhkan fakta-fakta turunan dari fakta-fakta yang telah ada, maka batasan dapat dikonversi menjadi aturan seperti pada Algoritma III-8. ([<parameter1>[,<parameter2>, ...]) Å ∧ . ([<parameter1>[,<parameter2>, ...]) Å ∧ . ([<parameter1>[,<parameter2>, ...]) Å ∧
∧
.
Algoritma III-8 Sintaks konversi batasan menjadi aturan (2)
Contoh pada sistem penjadwalan mata kuliah: Mata kuliah wajib pada tingkat yang sama tidak dijadwalkan pada waktu yang sama. Definisi fakta yang terkait adalah sebagai berikut. a. mata_kuliah(Kode_mk,
Nama_mk,
Kelas_mk,
Jml_SKS,
NIP_dosen,
Jml_peserta, Sifat) b. waktu(Kode_waktu) c. jadwal(Kode_mk, Kelas_mk, Kode_waktu, Kode_ruang, Grup_mahasiswa)
Fakta (a) digunakan untuk membangun fakta turunan kode mata kuliah yang setingkat dengan kode mata kuliah masukan. Catatan: karakter ketiga pada kode mata kuliah menunjukkan tingkatan tahun ajaran mata kuliah. Fakta (b) dan (c) digunakan untuk mencari slot waktu-slot waktu yang digunakan oleh mata kuliah yang setingkat dengan mata kuliah masukan. Batasan ini memerlukan fakta mengenai mata kuliahmata kuliah (Kode_mk_out) yang setingkat dengan kode mata kuliah Kode_mk_in. Kemudian, fakta lainnya yang diperlukan adalah slot waktu-slot waktu yang digunakan oleh mata kuliah yang setingkat tersebut (Kode_mk_out). Contoh implementasi aturan yang membutuhkan fakta-fakta turunan dapat dilihat pada Algoritma III-9. one_level_matkul(Kode_mk_in, Kode_mk_out) Å sub_string(Kode_mk_in, 2, 1, _, Y) ∧ mata_kuliah(Kode_mk_out, _, _, _, _, _, wajib) ∧
III-14 Kode_mk_in \= Kode_mk_out ∧ sub_string(Kode_mk_out, 2, 1, _, Z) ∧ Y = Z. not_one_level(Kode_mk, Kode_waktu) Å one_level_matkul(Kode_mk, Kode_mk_out) ∧ waktu(Kode_waktu) ∧ not(jadwal(Kode_mk_out, _, Kode_waktu, Kode_ruang, _)).
Algoritma III-9 Contoh aturan dengan fakta-fakta turunan
Konversi batasan jenis ini bersifat rekursif, seandainya mekanisme deduksi faktafakta yang ada perlu dilakukan berulang-ulang. Potongan aturan berikut adalah pendefinisian batasan yang dijelaskan pada Subbab III.2.2 dalam bentuk aturan.
Berikut adalah contoh konversi batasan tipe I menjadi aturan pada sistem penjadwalan mata kuliah. Untuk batasan prioritas dan tipe II, dapat dilihat pada Subbab III.I.2.
Batasan: Jumlah peserta suatu mata kuliah harus lebih kecil daripada kapasitas ruangan yang akan ditempatinya. Ruangan yang memenuhi batasan adalah semua ruangan yang kapasitasnya lebih besar dari jumlah peserta. Aturan hasil konversi batasan ini dapat dilihat pada Algoritma III-7. Batasan: Sebuah ruangan hanya dapat digunakan oleh sebuah kelas mata kuliah pada satu waktu. Batasan ini dapat dipenuhi dengan mencari semua slot waktu yang tersedia untuk ruangan tertentu. Slot waktu yang memenuhi batasan adalah semua slot waktu yang belum terdapat pada fakta jadwal dengan slot waktu dan kode ruang tertentu. Aturan hasil konversi batasan ini dapat dilihat pada Algoritma III-10. avail_slot_on_class(Kode_waktu, Kode_ruang) Å waktu(Kode_waktu) ∧ not(jadwal(_,_,Kode_waktu, Kode_ruang, _)).
Algoritma III-10 Aturan avail_slot_on_class
Batasan: Seorang dosen hanya dapat mengajar sebuah kelas mata kuliah dalam satu waktu. Batasan ini dapat dipenuhi dengan cara mencari slot yang tidak dapat digunakan oleh dosen untuk mengajar. Suatu slot waktu tidak dapat digunakan oleh dosen jika sudah terdapat fakta jadwal dari kelas mata kuliah yang diajar oleh dosen tersebut. Aturan hasil konversi batasan ini dapat dilihat pada Algoritma III-11. avail_slot_on_dosen(NIP_dsn, Kode_waktu) Å mata_kuliah(Kode_mk, _, Kelas_mk, _, NIP_dsn, _, _) ∧
III-15 not(jadwal(Kode_mk, Kelas_mk, Kode_waktu, Kode_ruang, _)).
Algoritma III-11Aturan not_avail_slot_on_dosen
Batasan: Mata kuliah wajib pada tingkat yang sama tidak dijadwalkan pada waktu yang sama. Batasan ini dapat dipenuhi dengan cara menurunkan fakta mengenai mata kuliah (Kode_mk_out) mana saja yang setingkat dengan kode mata kuliah Kode_mk_in, lalu mencari slot waktu kapan saja yang digunakan oleh mata kuliah yang setingkat tersebut (Kode_mk_out). Aturan hasil konversi batasan ini dapat dilihat pada Algoritma III-9.
Fakta turunan slot waktu dan ruangan kelas yang tersedia untuk suatu kelas mata kuliah tertentu dapat diperoleh dengan cara menggabungkan semua batasan yang telah didefinisikan. Slot waktu dan ruangan kelas yang memenuhi batasan adalah semua ruangan yang kapasitasnya lebih besar dari jumlah pesertanya, dan semua slot waktu yang tersedia untuk ruangan tersebut. Selain itu, slot waktu tersebut juga harus merupakan slot waktu yang dapat digunakan oleh dosen dan tidak digunakan oleh mata kuliah lain yang bersifat wajib dan setingkat. Aturan akhir yang menggabungkan seluruh batasan untuk mencari solusi jadwal dapat dilihat pada Algoritma III-12. slot_avail(Kode_mk, Kelas_mk, Kode_waktu, Kode_ruang) Å mata_kuliah(Kode_mk, _, Kelas_mk, _, NIP_dsn, Jml_peserta) ∧ avail_class(Jml_peserta, Kode_ruang) ∧ avail_slot_on_class(Kode_waktu, Kode_ruang) ∧ not_avail_slot_on_dosen(NIP_dsn, Kode_waktu) ∧ not_one_level(Kode_mk, Kode_waktu).
Algoritma III-12 Aturan slot_avail
III.4 Kesimpulan Analisis Berdasarkan analisis yang dilakukan, terdapat beberapa kesimpulan antara lain: 1. Model data penjadwalan terdiri dari definisi fakta dan batasan. Fakta mendefinisikan semua resource yang terkait dengan penjadwalan, sedangkan batasan mendefinisikan semua batasan pada penjadwalan. Fakta terbagi menjadi dua, yaitu fakta elementer dan fakta turunan. Fakta turunan merupakan hasil mekanisme deduksi dari fakta elementer dan aturan-aturan yang ada. Batasan pada sistem penjadwalan terbagi menjadi dua bagian utama, yaitu batasan terhadap urutan dan batasan terhadap penjadwalan. Batasan terhadap urutan merupakan batasan untuk menentukan prioritas dari setiap resource yang dijadwalkan. Batasan terhadap urutan disebut juga batasan prioritas. Batasan terhadap penjadwalan merupakan batasan yang digunakan untuk menentukan pasangan slot
III-16 jadwal mana saja yang dapat menjadi solusi bagi sistem penjadwalan. Batasan terhadap penjadwalan dibagi menjadi dua, yaitu batasan tipe I (hard-constraint) dan batasan tipe II (soft-constraint). Batasan tipe I adalah batasan yang harus dipenuhi, sedangkan batasan tipe II adalah batasan yang sebaiknya dipenuhi karena apabila dipenuhi dapat meningkatkan performansi dari hasil yang diberikan. 2. Fakta mengenai resource dan batasan harus mengikuti model data yang dibangun. Fakta mengenai resource menjadi fakta, sedangkan batasan dikonversi menjadi aturan-aturan dalam basis data deduktif. 3. Model proses penjadwalan terbagi menjadi tiga proses utama, yaitu: Pendefinisian fakta dan batasan, Komputasi, dan Pembangunan tabel waktu solusi jadwal. Tiga proses utama ini dilakukan dengan menggunakan dua pemroses, yaitu: basis data deduktif dan aplikasi. Proses penjadwalan diawali dengan mendefinisikan fakta dan batasan dalam model data yang dibangun. Selanjutnya, setiap resource yang terdefinisi mendapatkan bobot sesuai dengan batasan prioritas yang dapat dipenuhinya. Tahap ini dilakukan oleh basis data deduktif. Kemudian, bobot tersebut digunakan oleh aplikasi untuk menentukan prioritas dari setiap resource. Resource dengan prioritas tertinggi dipilih, lalu pasangan slot jadwal untuk resource ini dicari dengan menerapkan batasan tipe I dan setiap pasangan slot jadwal diberi bobot sesuai dengan batasan tipe II yang dapat dipenuhinya. Pencarian pasangan slot jadwal dan pembobotan batasan tipe II dilakukan oleh basis data deduktif Selanjutnya, sebuah pasangan slot jadwal akan ditentukan oleh aplikasi menjadi solusi untuk resource yang dipilih. Namun, jika tidak ditemukan solusi yang dapat memenuhi batasan yang ada, maka aplikasi melakukan backtrack untuk mencari alternatif solusi lain yang memungkinkan. Solusi yang telah ditentukan disimpan dan proses penjadwalan dilanjutkan untuk resource dengan prioritas tertinggi berikutnya. Setelah semua resource terjadwalkan, jadwal solusi yang telah terbentuk dapat diatur ulang oleh pengguna sebelum ditampilkan dalam bentuk tabel waktu solusi jadwal. 4. Prinsip kerja algoritma greedy digunakan untuk menentukan resource yang dijadwalkan terlebih dahulu, yaitu memilih resource dengan prioritas tertinggi. Selain itu, prinsip kerja algoritma greedy juga digunakan untuk menentukan pasangan slot jadwal yang dipilih sebagai solusi, yaitu memilih pasangan slot jadwal dengan bobot tertinggi.
