BAB 1
PENDAHULUAN
1.1 Latar Belakang
Perkembangan teknologi yang pesat memberikan banyak kemudahan dalam penyelesaian masalah dan pencapaian hasil kerja yang memuaskan bagi kehidupan manusia. Salah satu teknologi itu adalah teknologi komputer. Keberadaan komputer sampai saat ini telah mengalami berbagai kemajuan. Kemampuan komputer untuk melakukan suatu pekerjaan atau tugas pun semakin baik. Jika dahulu komputer digunakan untuk memproses data secara sederhana, maka saat ini penggunaan komputer sudah sangat luas pengaruh dan manfaatnya meliputi segala aspek kehidupan manusia.
Salah satu aspek kehidupan itu sendiri dimana penggunaan komputer saat ini digunakan untuk membuat aplikasi komputasi untuk dalam masalah penjadwalan, yang dalam hal ini yaitu dalam penjadwalan kuliah. Melaksanakan pekerjaan secara efektif dan efisien agar tujuan tercapai merupakan hal yang penting dalam masalah penjadwalan. Oleh karena itu pemahaman mengenai konsep penjadwalan sangat penting, sehingga para pelaksana mengetahui kapan waktu harus memulai suatu pekerjaan dan kapan waktu mengakhirinya.
Penjadwalan kegiatan belajar mengajar dalam suatu kampus adalah hal yang rumit. Permasalahan yang sering disebut dengan University Timetabling Problems (UTP) ini. Selain dilihat dari sisi mahasiswa, juga harus dilihat dari sisi dosen, yaitu kemungkinan-kemungkinan dosen akan mengampu lebih dari satu mata kuliah yang ada, sebab ada kemungkinan jumlah mata kuliah dan jumlah dosen tidak sebanding, sehingga harus dipikirkan juga solusi agar dosen
Universitas Sumatera Utara
2
tidak mengajar dua mata kuliah berbeda pada hari dan jam yang sama. Selain itu, harus dipertimbangkan juga ketersediaan kelas sehingga kegiatan perkuliahan dapat dilaksanakan.
Salah satu metode simulasi yang dapat digunakan untuk menyelesaikan permasalahan tersebut adalah dengan menggunakan pendekatan algoritma genetik. Algoritma genetik merupakan pendekatan komputasional untuk menyelesaikan masalah yang dimodelkan dengan proses evolusi biologis. Diharapkan dengan digunakannya algoritma genetik akan diperoleh optimasi penjadwalan yaitu kondisi dimana terjadi kombinasi terbaik untuk pasangan mata kuliah dan dosen pengajar secara keseluruhan, tidak ada permasalahan bentrokan jadwal pada sisi mahasiswa, serta ketersediaan ruang yang cukup dan sesuai secara fasilitas untuk seluruh mata kuliah yang ada.
Pada penelitian ini, sistem simulasi penjadwalan dibuat dengan melibatkan parameter-paramenter terdiri atas mata kuliah, slot waktu dengan sejumlah batasan (hari dan jam), mahasiswa, dosen, ruangan dan kapasitasnya, dan syarat (constraint) tertentu. Memasukkan parameter mahasiswa, dan mengaturnya supaya bentrokan pada mahasiswa seminimal mungkin. Juga menghidari mahasiswa kuliah lebih dari 3 mata kuliah dalam sehari. Maka melalui penelitian ini penulis mencoba mengusulkan beberapa alternatif pilihan dari jadwal yang dihasilkan dan mengusulkan perubahan (seminimal mungkin) jika masih terjadi bentrokan jadwal. Terdapat berbagai aspek yang berkaitan dalam penjadwalan tersebut yang harus dilibatkan dalam pertimbangan di antaranya : 1. Terdapat jadwal-jadwal di mana dosen yang bersangkutan tidak bisa mengajar. 2. Tidak boleh adanya jadwal kuliah yang beririsan dengan jadwal kuliah angkatan sebelumnya maupun sesudahnya, sehingga mahasiswa dapat mengambil mata kuliah angkatan sebelumnya maupun sesudahnya. 3. Distribusi jadwal perkuliahan diharapkan dapat merata tiap harinya untuk setiap kelas.
Universitas Sumatera Utara
3
4. Pekerjaan penjadwalan mata kuliah ini akan semakin berat jika melibatkan semakin banyak kelas per-angkatannya.
Di samping aspek-aspek di atas, dalam penyusunan sistem simulasi jadwal kuliah ini pun terdapat sangat banyak kemungkinan yang selayaknya dicoba untuk menemukan penjadwalan yang terbaik. Karena itu dibutuhkan metode optimasi dengan menggunakan algoritma genetik yang dapat diterapkan untuk mengerjakan sistem simulasi penjadwalan kuliah ini.
1.2 Perumusan Masalah
Permasalahan yang terdapat dalam penelitian ini adalah sebagai berikut: 1. Bagaimana membangun sistem simulasi penjadwalan kuliah yang dapat meminimalkan bentrokan sehingga diperoleh suatu sistem simulasi penjawalan kuliah. 2. Bagaimana kinerja algoritma genetik dalam penjadwalan kuliah sehingga diperoleh suatu sistem simulasi penjadwalan kuliah yang baik dan optimal.
1.3 Pembatasan Masalah
Agar pembahasan penelitian ini lebih terarah maka diberikan batasan-batasan masalah yang akan dibahas. Yang menjadi batasan masalah pada penelitian ini adalah : 1. Semua parameter dan restriction yang telah ditentukan dapat di input. 2. Pemecahan permasalahan dengan metode algoritma genetik. 3. Perancangan aplikasi panjadwalan berbasis desktop. 4. Berbasis Client Server dan tetap memperhatikan sistem keamanan database.
Universitas Sumatera Utara
4
1.4 Tujuan Penelitian
Tujuan dari penelitian ini adalah penerapan algoritma genetik untuk menghasilkan sistem simulasi penjadwalan kuliah. Jadwal yang dihasilkan dapat meminimalkan
bentrokan
seminimal
mungkin,
sehingga
dapat
lebih
memudahkan penggunanya dalam mendapatkan solusi untuk penanganan penjadwalan kuliah.
1.5 Tinjauan Pustaka
Sebagai pendukung teori dalam penulisan studi ini, penulis menggunakan beberapa buku dan jurnal, antara lain :
Michael Negnevitsky (2005). Secara umum, proses dari algoritma genetik ini berisi step-step procedural sekuensial yang memproses sebuah populasi kromosom buatan (artificial) menjadi populasi baru lainnya. Algoritma ini menggunakan proses seleksi natural dan teknik-teknik yang terinspirasi dari teori genetik, yaitu: crossover dan mutasi.
William B. Langdon (2000). Kekuatan algoritma genetik dalam menemukan solusi optimal telah direkomendasikan dalam berbagai bidang aplikasi seperti finansial, pengolahan citra, pengontrol pipa gas dan penjadwalan produksi. Dan belakangan ini pemanfaatan algoritma genetik semakin meluas di banyak program aplikasi lain seperti game programming dan text mining.
Rimcharoen (2006). Algoritma genetik menggambarkan populasi seperti sebuah probabilitas distribusi dari kumpulan solusi, oleh karena itu tidak semua populasi perlu untuk disimpan. Dalam setiap generasi, algoritma genetik menghasilkan
individu-individu
berdasarkan
pada
probabilitas
yang
dispesifikasikan dalam probability vector. Individu-individu tersebut akan dievaluasikan dan probability vector akan berubah berdasarkan individu yang terbaik. Algoritma genetik mempunyai keuntungan dalam menggunakan
Universitas Sumatera Utara
5
memori yang sedikit dan mencapai kualitas yang sebanding dan mempunyai hasil dengan jumlah yang hampir sama dengan yang dihasilkan oleh Basic Genetik Algorithm.
1.6 Manfaat Penelitian
Manfaat yang dapat diambil dari penelitian ini adalah: 1. Memperkaya literatur dalam bidang sistem simulasi penjadwalan kuliah khususnya dengan menggunakan algoritma genetik. 2. Dapat dijadikan sebagai dasar atau pedoman untuk pengembangan sistem simulasi penjadwalan kuliah tingkat lanjut.
1.7 Diagram Konsepsi
Disini penulis menggambarkan diagram konsepsi dari tahapan algoritma genetik terhadap sistem simulasi penjadwalan kuliah:
Analisa Algoritma Genetik
Implementasi J2SE
Proses Input Data
Generate dengan Program
Analisa Hasil Generate
Gambar 1.1 Diagram Konsepsi
Universitas Sumatera Utara
6
Penjelasan Diagram Konsepsi 1. Analisa Algoritma Genetik. Pada tahapan ini akan dianalisa bagaimana alur proses dari algoritma Genetik, dimana mendefenisikan gen, kromosom, individu dan populasi untuk setiap parameter untuk membuat simulasi penjadwalan kuliah. 2. Implementasi J2SE Pada tahap ini adalah implementasi pada program J2SE. Sesuai dengan tahap analisa diawal yang pertama kali dibuat dengan membuat defenisi dari
masing-masing
parameter
dari
genetik.
Sehingga
dapat
diimplementasikan dalam bentuk program penjadwalan kuliah. 3. Proses Input Data Pada tahapan ini merupakan proses input data dari semua parameterparameter penjadwalan sehingga bisa diolah dalam program yang telah diimplementasikan. 4. Generate dengan Program Pada tahap ini merupakan proses pembentukan jadwal kuliah dengan Generate semua data input yang telah dimasukkan, sehingga dapat dihasilkan jadwal kuliah. 5. Analisa Hasil Generate Dalam tahapan ini merupakan analisa hasil Generate program yang telah dijalankan, dimana akan dilihat hasilnya telah optimal atau belum. Sehingga akan meng-generate ulang apabila hasil dari jadwal yang sebelumnya belum optimal.
1.8 Metodologi Penelitian
Dalam melakukan penelitian ini, penulis menggunakan beberapa metode penelitian, antara lain: 1. Studi Literatur dan Pemahaman Sistem.
Universitas Sumatera Utara
7
Penulisan ini dimulai dengan studi kepustakaan yaitu dengan membaca buku-buku, jurnal-jurnal dan bahan-bahan referensi dari internet untuk memperoleh pengertian dan pengetahuan mengenai algoritma genetik, artificial intelligence, analisis dan perancangan sistem, penjadwalan, perancangan, dan pemrograman Java 2 Standard Edition. 2. Analisis Pada tahap ini dilakukan pengumpulan fakta-fakta yang mendukung perancangan sistem simulasi penjadwalan kuliah dengan mengadakan konsultasi
dengan
dosen
pembimbing
maupun
dosen
yang
berkemampuan di bidang ini dan membandingkan dengan yang ada pada buku penuntun, mendaftarkan semua ruangan yang bisa dipakai, membuat slot waktu untuk masing-masing ruangan, mendefinisikan gen atau kromosom atau individu dan populasi, membuat algoritma dan flowchart,
merancang sistem database dan proses jadwal kuliah,
meliputi: a. Membuat
ERD
(Entity
Relationship
Diagram)
untuk
menggambarkan hubungan entitas. b. Membuat skema diagram. c. Membuat Context Diagram. d. Membuat DFD (Data Flow Diagram) level 0 dan level 1 untuk menggambarkan
proses-proses
yang
terjadi
dalam
sistem
penjadwalan kuliah. 3. Perancangan dan Implementasi Perancangan dan implementasi sistem simulasi penjadwalan kuliah berdasarkan metode yang digunakan dalam algoritma genetik dengan menggunakan bahasa pemrograman Java 2 Standard Edition (J2SE) dan MySQL 5.1.30 untuk sistem databasenya. 4. Pengujian Pada tahap ini sistem simulasi yang sudah dirancang diuji oleh pemakai dan membandingkan solusi pada sistem dengan pemikiran dosen pembimbing maupun dosen yang berkemampuan di bidang ini.
Universitas Sumatera Utara
8
5. Penyusunan laporan dan kesimpulan akhir. Menyusun laporan hasil analisa simulasi ke dalam format penulisan tugas akhir dengan disertai kesimpulan akhir.
Universitas Sumatera Utara