JURNAL TEKNIK POMITS Vol. 1, No. 1, (2012) 1-5 1

JURNAL TEKNIK POMITS Vol. 1, No. 1, (2012) 1-5

1

Perancangan dan Pembuatan Aplikasi Penjadwalan Perkuliahan Menggunakan Algoritma Genetik dan Teknologi Java API for XML Web Service pada Platform Android Nanda Bagus Pradnyana, Dwi Sunaryono, dan Abdul Munif Jurusan Teknik Informatika, Fakultas Teknologi Informasi, Institut Teknologi Sepuluh Nopember (ITS) Jl. Arief Rahman Hakim, Surabaya 60111 E-mail: [email protected]

Abstrak—Aplikasi yang dibuat pada artikel ini merupakan aplikasi penyusunan jadwal kuliah secara otomotis berdasarkan dengan jadwal kuliah kampus Teknik Informatika ITS. Jadwal akan disusun berdasarkan sumber daya kampus dengan data batasan yang telah dimasukkan sebelumnya. Sumber daya yang dimaksud seperti ruang kelas, pengajar, dan peserta kuliah. Metode yang digunakan untuk penyusunan jadwal adalah algoritma Genetika. Algoritma ini merupakan salah satu algortima pencarian untuk mencari optimasi dari suatu masalah yang diberikan dengan cara membentuk sebuah populasi kasus dan menerapkan hukum teori alam sehingga algoritma ini dapat menghasilkan individu terbaik pada generasi terakhir. Aplikasi penjadwalan ini berbasis web dan dibangun menggunakan kerangka kerja Vaadin. Selain itu dibuat pula sebuah aplikasi pada platform Android untuk melihat jadwal yang tersimpan. RaspinDroid mengambil data dari server menggunakan Web Service yang dibuat menggunakan JAX-WS. JAX-WS terhubung langsung ke dalam basis data server untuk mengolah data langsung ke bentuk XML dan siap dikirimkan ke aplikasi RaspinDroid. Fitur-fitur yang ada pada aplikasi RaspinWeb selain penyusunan jadwal, terdapat fitur pemesanan kelas, dan fitur pengaturan jam permohonan mengajar dari pengajar. Evaluasi yang akan dilakukan terhadap aplikasi ini akan dilakukan apakah Algoritma Genetik yang digunakan dapat mencapai hasil optimum sesuai dengan jadwal yang telah dibangun secara manual. Hasil evaluasi yang didapatkan bahwa sesuai data daftar kelas tahun ajaran genap 2011/2012, Algoritma Genetik dapat menempatkan kelas pada jadwal dengan nilai fitness sesuai dengan yang diharapkan. Kata Kunci— Algoritma Genetik, Android, Jadwal, JAX-WS.

I. PENDAHULUAN ekerjaan menyusun suatu penjadwalan, terutama penjadwalan kuliah mungkin terlihat mudah, akan tetapi ketika sumber daya yang ada semakin terbatas, tentunya membuat sebuah jadwal mata kuliah akan menjadi pekerjaan yang cukup memakan waktu yang lama. Beberapa sumber daya yang biasanya dibutuhkan seperti ketersediaan ruangan, apakah ruangan tersebut memiliki kriteria yang cukup untuk mengadakan sebuah kelas, jumlah kursi, dan kebutuhan penunjang lainnya, seperti ruangan laboratorium atau ruangan aula. Lalu pengajar, apakah pengajar mampu mengajar pada

P

semua jam, apakah pada waktu tersebut pengajar tertentu juga mengajar di kelas lainnya. Setelah itu tentu peserta kelas, apakah mereka juga dapat menghadiri kelas tersebut, atau mereka bisa saja memiliki jadwal lain pada waktu yang sama. Maka dari itu dibutuhkannya sebuah perangkat lunak yang mampu untuk menyusun sebuah jadwal, dimana jadwal tersebut sudah dioptimalisasi sehingga sumber daya yang terbatas tidak lagi menjadi suatu permasalahan dalam penyusunan jadwal kuliah. Selain itu pengembangan perangkat telepon pintar kini mampu membantu penerimaan dan pengiriman jalur informasi digital ketika kita tidak sedang menggunakan komputer. Telepon pintar mampu untuk bertukar informasi dengan perangkat digital lainnya pada jaringan dengan menggunakan internet. Teknologi ini sangat membantu untuk mendapatkan informasi yang lebih aktual dan dapat meningkatkan efisiensi tempat dan waktu. Salah satu pengaplikasian dalam kasus penyusunan jadwal kuliah ketika pengajar membutuhkan adanya kelas diluar jadwal tetap, atau kelas pengganti, hal ini tentunya perlu adanya komunikasi antara pengajar, penjaga ruangan, dan peserta kelas. Mungkin jika pengajar sebelumnya sudah membicarakannya kepada peserta kuliah dan meminjam ruangan jauh hari, hal ini tidak akan menjadi masalah. Akan tetapi jika hal ini tidak terencanakan, maka dibutuhkan sebuah alat yang dapat menyampaikan permintaan dan informasi secara cepat. Dengan dibuatnya sebuah aplikasi penyusunan jadwal kampus ini, diharapkan memudahkan para pengguna dalam mengatur penyusunan jadwal kuliah sesuai dengan sumber daya dan batasan yang ada. Dengan aplikasi ini pula diharapkan memudahkan komunikasi antara pengajar dan peserta kelas dalam mengatur jadwal kelas. II. URAIAN PENELITIAN A. Algoritma Genetik Algoritma Genetik merupakan salah satu algoritma optimasi yang kuat dan bisa digunakan pada berbagai macam studi kasus karena menggunakan prinsip teori evolusi. Algoritma ini sering digunakan untuk mencari solusi optimal baik pada

JURNAL TEKNIK POMITS Vol. 1, No. 1, (2012) 1-5 kasus yang sederhana sampai kasus yang rumit. Algoritma genetik bekerja pada suatu populasi yang dibentuk oleh sebuah kasus yang direpresentasikan sebagai kromosom dan akan dievaluasi untuk memperoleh seberapa nilai optimalnya [1]. Apabila pada generasi tersebut belum ditemukan kasus yang memiliki nilai paling optimal, maka akan dibentuk populasi baru dengan cara melakukan seleksi kepada individu yang nilai optimalnya kecil dan digantikan dengan individu baru melalui proses reproduksi. Berikut akan dijelaskan beberapa aspek yang digunakan pada Algoritma Genetik. Inisialisasi Inisialisasi kromosom ini dilakukan hanya sekali pada populasi pertama dibentuk. Setiap gen dari kromosom merupakan nilai real yang dihasilkan secara acak. Jarak nilai acak tersebut merepresentasikan waktu dan ruangan dari sebuah jadwal kelas. Crossover Crossover merupakan salah satu operator Algoritma Genetik yang digunakan untuk menghasilkan solusi baru dari dua buah solusi pada generasi sebelumnya. Operator ini bekerja pada dua buah kasus yang dianggap mampu menghasilkan kasus baru yang memiliki nilai kemampuan yang baik. Nantinya, solusi ini akan digabungkan untuk menghasilkan sebuah solusi baru yang memiliki kemiripan bentuk dari kedua kasus yang digabungkan. Solusi yang dihasilkan nantinya memiliki nilai kemampuan yang tidak berbeda jauh dengan nilai kemampuan induknya [2]. Mutasi Mutasi dilakukan dengan memberikan gaussian noise kepada satu gen atau lebih yang merupakan bilangan real [2]. Pada awalnya dipilih gen dari suatu kasus secara acak, selanjutnya nilai tersebut diberi nilai yang berbeda dengan nilai sebelumnya. Mutasi dilakukan untuk memperluas area pencarian kasus agar dapat mencapai nilai kemampuan yang lebih optimal.

Nilai Kemampuan Setiap individu yang dibuat akan dievaluasi untuk dicari nilai kemampuannya. Nilai ini digunakan untuk melakukan seleksi terhadap individu dalam populasi dimana individu yang nilai kemampuannya tidak memenuhi persyaratan akan dihapus dari populasi [3]. B. Android Android merupakan sebuah sistem operasi, perangkat perantara, dan beberapa aplikasi kunci. Sistem operasi Android khusus dikembangkan oleh Open Handset Alliance untuk perangkat tablet maupun ponsel pintar. Sumber kode pada sistem operasi Android bersifat terbuka. Android menggunakan kernel yang berbasis kernel Linux dan memiliki perangkat perantara dan pustaka yang ditulis dalam bahasa C. Perangkat lunak aplikasi yang berjalan pada kerangka aplikasi mencakup pustaka Java-Compatible yang berbasis pada Apache Harmony [4].

2 Android telah melakukan sejumlah perubahan sejak rilis aslinya, masing-masing memperbaiki bug dan menambah berbagai fitur baru [4]. C. JAX-WS Web service adalah aplikasi berbasis web yang menggunakan basis XML (Ekstensible Markup Language) standar dan transportasi protokol untuk saling bertukar data dengan klien [5]. JAX-WS (Java API for XML Web Service) adalah ekstensi standar dari Java yang digunakan untuk membangun sebuah web service berbasis Java menggunakan pendekatan interface POJO (Plain Old Java Object) dan WSDL (Web Service Definition Language) [6]. III. PENERAPAN TEORI A. Algoritma Genetik Representasi Kromosom Bentuk kromosom yang digunakan adalah sebuah Vector yang menyimpan daftar jadwal kelas. Kromosom yang dibuat sebenarnya merupakan tabel jadwal yang disusun secara satu baris. Baris ini disusun dengan urutan jumlah hari, yang didalamnya berisi urutan kelas yang ada, lalu berisi jumlah jam pada satu hari. Maka ukuran dari Vector ini adalah jumlah hari dikalikan dengan jumlah ruangan dikali dengan jumlah jam yang ada. Gambar 1 akan menggambarkan bagaimana bentuk kromosom yang akan dibuat. Jadwal Senin

0

1

... Kelas 1

13

14

...

26

27

...

82

83

...

418

419

Kelas 2

Gambar 1. Bentuk Kromosom Jadwal Kuliah. Gambar ini menunjukan suatu kromosom yang memiliki lima hari waktu mengajar, enam ruangan kelas, dan 14 jam waktu mengajar tiap harinya.

Flowchart Program Flowchart yang dapat dilihat pada Gambar 2 ini terdiri dari tiga proses utama, satu input data, dan dua percabangan. Untuk proses pertama, Inisialisasi Populasi Awal merupakan proses dimana populasi generasi pertama dibentuk untuk memulai pencarian kasus terbaik. Proses selanjutnya adalah Evaluasi Nilai Kemampuan, proses ini menghitung kemampuan suatu kasus dalam mengatasi batasan-batasan yang diberikan. Setiap batasan memiliki nilai bobot yang berbeda, sesuai dengan seberapa pentingnya batasan tersebut untuk dipenuhi. Proses ketiga adalah proses Reproduksi Kromosom Baru, proses ini melakukan seleksi berdasarkan nilai kemampuan yang sudah diberikan pada setiap individu. Setiap individu akan diurutkan berdasarkan nilai kemampuannya. Individu yang berada pada kelompok urutan bawah akan dihilangkan dan diganti dengan individu baru dengan cara membuat kromosom baru yang berbeda dengan induknya. Proses terakhir adalah proses Mutasi, proses ini mengambil suatu kelas dari jadwal secara acak dan ditempatkan ke jadwal yang berbeda. Mutasi dilakukan untuk memperluas area pencarian dan mendapatkan nilai

JURNAL TEKNIK POMITS Vol. 1, No. 1, (2012) 1-5

3

kemampuan yang lebih baik. Untuk input data, ada tiga masukan yang dibutuhkan yaitu, Tabel Dosen, Tabel Mata Kuliah, dan Tabel Kelas. Tabel Kelas dibentuk berdasarkan data pada Tabel Mata Kuliah dan Tabel Dosen. Tabel Kelas berisi daftar kelas yang akan dijadwalkan dengan Algoritma Genetik. Informasi yang disimpan seperti nama mata kuliah, identitas dosen pengajar, sampai kuota kelas. Untuk percabangan, terdapat percabangan apabila nilai kemampuan sudah mencapai batas maksimal atau jumlah generasi yang sudah melampui batas generasi, maka proses pencarian kasus dianggap selesai dan individu terbaik akan diambil sebagai solusi dari kasus yang diberikan. Input Data Terdapat tiga input data yang dibutuhkan untuk menjalankan algoritma ini, yaitu: 1. Tabel Mata Kuliah 2. Tabel Dosen 3. Tabel Kelas Tabel Mata Kuliah berisikan semua data yang berhubungan dengan kurikulum mata kuliah yang bersangkutan seperti semester, jumlah SKS, sampai jenis mata kuliah. Tabel Dosen menyimpan data identitas dosen yang mengajar pada kampus. Identitas yang disimpan seperti NIP, nama, bidang minat, sampai alamat e-mail dosen tersebut. Sedangkan Tabel Kelas berisi daftar kelas yang akan dibuat jadwalnya. Tabel ini berisikan nama, dosen, mata kuliah, sampai durasi kelas yang didaftarkan. Inisialisasi Populasi Awal Pada proses inisialiasi awal ini akan dibuat sepuluh kromosom berdasarkan bilangan acak. Bilangan yang diacak adalah indeks hari dan indeks ruangan yang akan ditempati oleh kelas. Untuk nilai waktu, akan di set pada indeks nol dimana dilakukan perulangan sejumlah jam perkuliahan apakah kelas tersebut dapat diletakan sesuai pada kolom jadwal yang tersedia. Evaluasi Nilai Kemampuan Evaluasi ini dilakukan setiap adanya individu baru yang berhasil terbentuk. Perhitungan nilai kemampuan berdasarkan dengan batasan penyusunan jadwal yang sudah ditentukan pada awal pembuatan aplikasi ini. Tabel 1 menjelaskan batasan yang ada beserta bobot yang diberikan. Dengan data ini semua daftar kelas yang digunakan dalam pembuatan jadwal akan dievaluasi apakah kelas tersebut melanggar batasan yang diberikan apa tidak. Jika kelas tersebut memenuhi suatu batasan, maka nilai kemampuan individu tersebut akan ditambahkan. Semakin tinggi nilai kemampuan suatu individu akan menandakan bahwa kelas-kelas pada jadwal tersebut sudah dialokasikan ke dalam jadwal yang baik. Setelah didapatkan semua nilai dari semua kelas, maka dapat dihitung nilai kemampuan kromosom dengan rumusan: NilaiKemampuan =

K 1 xB1 + K 2 xB2 + K 3 xB3 + K 4 xB4 + K 5 xB5 B1 + B2 + B3 + B4 + B5

(1)

Start

Input Data

Inisialisasi Populasi Awal

Evaluasi Nilai Kemampuan

Nilai Kemampuan Optimal Terpenuhi

Tidak

Jumlah Generasi Melewati Batas Generasi

Tidak

Reproduksi Kromosom Baru

Ya

Mutasi

Kromosom Terbaik pada Populasi

Finish

Gambar 2. Flowchart dari Algoritma Genetik. Terdapat satu proses masukan, empat proses utama, dua percabangan, dan satu hasil keluaran yang digunakan pada aplikasi ini.

B1 = Batasan kelas tidak menempati jadwal yang sudah ditempati kelas lain. B2 = Batasan ruangan yang ditempati sudah sesuai dengan ruangan kebutuhan kelas. B3 = Batasan pengajar dapat mengajar pada waktu tersebut B4 = Batasan kelas tidak beririsan dangan kelas lain yang memiliki semester yang sama. B5 = Batasan kelas tidak beririsan dengan kelas lain yang memiliki semester yang berbeda satu tahun ajaran. K1 = Jumlah kelas yang memenuhi batasan B1 K2 = Jumlah kelas yang memenuhi batasan B2 K3 = Jumlah kelas yang memenuhi batasan B3 K4 = Jumlah kelas yang memenuhi batasan B4

JURNAL TEKNIK POMITS Vol. 1, No. 1, (2012) 1-5 K5 = Jumlah kelas yang memenuhi batasan B5 Tabel 1. Tabel ini berisi batasan yang diberikan pada penyusunan jadwal kuliah menggunakan Algoritma Genetik.

No . 1

Batasan

Bobot

Kelas tidak menempati jadwal yang sudah 30 ditempati kelas lain. 2 Ruangan yang ditempati sudah sesuai 20 dengan ruangan kebutuhan kelas. 3 Pengajar dapat mengajar pada waktu 20 tersebut. 4 Kelas tidak beririsan dangan kelas lain 15 yang memiliki semester yang sama. 5 Kelas tidak beririsan dengan kelas lain 5 yang memiliki semester yang berbeda satu h j Dapat dilihat pada Tabel 1 urutan bobot disusun berdasarkan kemungkinannya diadakan kelas pada ruangan dan jadwal yang sudah ditentukan. Apabila suatu ruangan terdapat dua kelas yang berbeda tentu tidak memungkinan kedua kelas tersebut dapat diadakan, untuk itu bobot terbesar diberikan kepada batasan ini. Selanjutnya apakah ruangan tersebut memiliki kebutuhan yang dibutuhkan oleh kelas, seperti jumlah kursi dan fasilitas yang diberikan. Batasan ketiga diberikan untuk mengatasi jadwal pribadi yang dimiliki oleh dosen. Bisa saja dosen sudah memiliki jadwal lain seperti tugas belajar, atau sedang mengajar pada kelas yang lain. Untuk dua batasan selanjutnya diberi bobot yang relatif kecil dari bobot yang lainnya. Hal ini dikarenakan batasan ini dapat diatasi dengan menambah kelas baru dengan mata kuliah yang sama. Reproduksi Kromosom Baru Proses ini merupakan pembuatan kromosom baru sama seperti proses Inisialiasi Populasi Awal. Pembuatan kromosom baru ini dimaksudkan untuk mencari kasus dengan nilai kemampuan yang lebih baik dan menjaga jumlah individu populasi pada jumlah yang tetap. Mutasi Proses Mutasi dilakukan dengan memindahkan suatu jadwal kelas yang dipilih secara acak ke jadwal kelas yang lain. Jadwal kelas akan dipindahkan dengan mengacak indeks hari dan indeks ruangan yang baru. Dilakukan perulangan sampai kelas mendapatkan jadwal baru sesuai dengan bentuk kromosom. Apabila secara kebetulan kelas diletakan kembali ke dalam jadwal yang sama, pengacakan ruangan dan hari akan dilakukan kembali. B. Android dan JAX-WS Aplikasi RaspinDroid merupakan aplikasi untuk melihat jadwal secara mobile. RaspinDroid terhubung langsung dengan jaringan internet untuk mengambil data jadwal kuliah yang terlah disimpan pada basis data server. Pada RaspinDroid dibuat beberapa fitur untuk dosen seperti fitur peminjaman ruangan kelas untuk kelas pengganti. Selain itu

4 juga dosen juga dapat memasukkan jadwal pribadi sebagai masukan untuk penyusunan jadwal berikutnya. Platform Android tidak bisa terhubung langsung dengan basis data server. Diperlukan sebuah aplikasi web service untuk menjembatani hubungan antara basis data server dan klien Android. Gambar 3 menunjukan penggalan sumber kode dari endpoint interface pada JAX-WS. import javax.jws.WebMethod; import javax.jws.WebService; @WebService public interface WebService { @WebMethod String getRuangan(); @WebMethod String reqJadwal(String tipe, String id, String nip, String tanggal, String ruangan, String jam); @WebMethod String login(String username, String password); } Gambar 3. Endpoint Interface pada JAX-WS. Terdapat beberapa web method yang akan melakukan query pada basis data dan mengirimkan hasilnya ke klien RaspinDroid.

Setiap method diatas akan diimplementasikan pada kelas endpoint implementation. Setiap method yang mengembalikan hasil query dari basis data, akan diolah terlebih dahulu ke dalam bentuk XML dengan bantuan library JDOM2. Hasil query sengaja dirubah ke dalam XML untuk memudahkan pengiriman data berupa String dan ketika sampai pada klien dapat dirubah kembali menjadi bentuk objek. IV. HASIL PENGUJIAN Algoritma Genetik ini diuji dalam penjadwalan mata kuliah kampus Teknik Informatika ITS pada tahun ajaran semester genap 2011/2012. Uji coba ini melibatkan 83 kelas dengan rincian 3 kelas semester 1, 20 kelas semester 2, 1 kelas semester 3, 28 kelas semester 4, 2 kelas semester 5, 22 kelas semester 6, dan 7 kelas semester 8. Melibatkan juga 4 angkatan mahasiswa, 6 ruangan kelas biasa dan 1 ruangan laboratorium. Pada hasil akhir iterasi diperoleh hasil penjadwalan yang memiliki nilai kemampuan 0,888608 dimana semua kelas memiliki jadwal masing-masing tanpa adanya jadwal kelas yang menempati ruangan dan pada waktu yang sama. Hasil ini sudah cukup baik dan menunjukan bahwa Algoritma Genetik dapat digunakan untuk melakukan penyusunan jadwal mata kuliah kampus Teknik Informatika ITS. Gambar 4 menampilkan jadwal yang sudah tersusun dengan tampilan menggunakan kerangka kerja Vaadin.

JURNAL TEKNIK POMITS Vol. 1, No. 1, (2012) 1-5

Gambar 4. Hasil Penyusunan Jadwal Menggunakan Algoritma Genetik.

V. SIMPULAN Dengan bantuan Algoritma Genetik, penyusunan penjadwalan kuliah dapat dilakukan dan dioptimalkan. Aplikasi dapat mencari solusi dari populasi kasus yang diberikan berdasarkan sumber daya dan batasan yang diberikan. Selain itu, aplikasi mencegah adanya kelas ataupun jadwal dosen yang saling bertumpukan dan juga meminimalisir adanya irisan kelas yang memiliki semester yang sama atau selang satu tahun ajaran. Penggunaan Android sebagai media penerimaan data dapat membantu pengguna untuk mendapatkan informasi yang dibutuhkan secara aktual. Selain itu, fitur pada RaspinDroid memudahkan dosen untuk memesan kelas tambahan dengan mengirimkan informasi yang dibutuhkan server melalui web service JAX-WS. Untuk kedepannya diharapkan tidak hanya platform Android saja sebagai media penerimaan data pada aplikasi penjadwalan ini. Diharapkan pula dibuat pada platform lainnya seperti iOS ataupun Blackberry. DAFTAR PUSTAKA [1]

[2] [3] [4] [5] [6]

B. Edmund, E. David, W. Rupert, A Genetic Algorithm Based University Timetabling System. Department of Computer Science, University of Nottingham, University of Park, Nottingham, NG7 2RD. J. Holland, Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor, Michigan. 1975. M. Aria, Aplikasi Algoritma Genetik untuk Optimasi Penjadwalan Mata Kuliah. Universitas Komputer Indonesia, 2006. Android Developers. 2010. What is Android?, [Online]. Available: (http://developer.android.com/guide/basics/what-is-android.html Oracle WebPage. Metro Web Service Overview, [Online]. Available: http://www.oracle.com/technetwork/java/index-jsp-137004.html Eclipse Wiki WebPage. JAXWS – JAXWS Tools Component, [Online]. Available: http://wiki.eclipse.org/JAXWS

5