sistem penjadwalan mata kuliah berdasarkan … · program studi teknik informatika, fakultas ilmu...

Scientific Work Documents | Final Project | Teknik Informatika - S1 | Fakultas Ilmu Komputer | Universitas Dian Nuswantoro Semarang | 2015

SISTEM PENJADWALAN MATA KULIAH BERDASARKANPEMINATAN MAHASISWA MENGGUNAKAN METODE ASOSIASI

YANG DISEMPURNAKAN DENGAN ALGORITMA GENETIKA

Wahyu SetiawatiProgram Studi Teknik Informatika, Fakultas Ilmu Komputer,Universitas Dian Nuswantoro

E-mail: [email protected]

Abstrak— Secara umum, sebuah jadwal mata kuliah harus dapat memenuhi kebutuhan dari pihakuniversitas dan pihak dosen. Sedangkan kebutuhan dari pihak mahasiswa seperti minat dan pengambilanmata kuliah di semester sebelumnya tidak dipertimbangkan. Karena itu perlu adanya suatu sistempenjadwalah yang tidak hanya dapat memenuhi kebutuhan universitas dan dosen, tapi juga dapatmemenuhi kebutuhan mahasiswa. Proses penelitian ini menggunakan metode asosiasi untuk mencariketerhubungan data input yang berupa histori pengambilan mata kuliah mahasiswa sehingga mampumemprediksi mata kuliah yang akan diambil di semester berikutnya dan perkiraan jumlah kelas yangharus dibuka untuk mata kuliah tersebut. Proses penelitian kemudian dilanjutkan dengan menggunakanalgoritma genetika yang dapat digunakan dalam memecahkan masalah optimasi kombinasi jadwal matakuliah berdasarkan hasil asosiasi dan input data berupa nama mata kuliah, jumlah sks, nama dosen, namakelas dan kapasitas kelas.

Kata Kunci— asosiasi, algoritma genetika, penjadwalan, mata kuliah, peminatan mahasiswa

Abstrak— Generally, a course schedule must be satisfy the university’s and lecturer’s requirements. Whereasthe student’s requirement like their learning interest and the courses that have been taken in the previoussemester never be considered. So then we need the scheduling system than satisfy not just the university’s andlecturer’s requirements, but also student’s requirement as well. This study using association mining to find theassociation in the history of courses that have been taken by the student, so the system can predict the numberof classes that have to be open for that courses. The next stage of this study is using genetic algorithm that canbe used to solve course scheduling optimization problem based on association result and data input like coursesname, credits, lecturer’s name, class’s name and class quantity.

Keywords— association, genetic algorithm, scheduling, courses, student’s learning interest

I. PENDAHULUAN

enjadwalan mata kuliah pada sebuah universitas atauperguruan tinggi merupakan hal yang sangat penting

untuk menjaga keberlangsungan perkuliahan di setiapsemesternya. Sebuah jadwal perkuliahan yang efisien dapatdikatakan sebagain indicator of service quality dariuniversitas atau perguruan tinggi tersebut [1]. Dalampenyususan jadwal mata kuliah, ada beberapa hal yang harusdipenuhi.

Pada sebuah universitas, sistem penjadwalan, terutamapenjadwalan mata kuliah, merupakan hal yang kritis danperlu diperhitungkan dengan baik karena harusmempertimbangkan berbagai keterbatasan dan syarat yangbiasanya terbagi dalam hard constraints dan soft constraints.Sebuah jadwal mata kuliah dari sebuah universitas harusdibuat di setiap semester, dan jadwal tersebut tikan akandapat digunakan kembali pada semester yang sama di tahunberikutnya. Karena itulah, permasalah penjadwalan matakuliah merupakan permasalahan yang kompleks danmerupakan permasalahan yang disebut sebagai NP-Complete

Problem [2].Penjadwalan dilakukan dengan cara mencari slot waktu

yang dapat memenuhi semua constraints. Proses inidilakukan secara berulang-ulang, hingga kemudianditemukan slot waktu yang paling tepat untuk dialokasikanbagi salah satu mata kuliah.

Banyak metode yang telah dikembangkan untuk mengatasipermasalahan penjadwalan mata kuliah. Wood mengusulkanteknik pewarnaan graph untuk memecahkan masalahpenjadwalan [3]. Mulvey menggunakan metode 0-1 integerprogramming untuk menganalisis masalah penjadwalan matakuliah, dengan tujuan untuk mengoptimalkan pemanfaatankelas atau ruangan yang ada [4]. Yu dan Sung menggunakanalgoritma genetika berbasis sektor untuk memecahkanpenjadwalan mata kuliah dengan tujuan untuk membentukjadwal mata kuliah dengan efektifitas biaya yang lebih baik[5].

Akan tetapi, pada umumnya penyusunan jadwal matakuliah hanya memperhatikan pemenuhan kebutuhanuniversitas dan dosen saja, tanpa memperhatikan pemenuhankebutuhan mahasiswa, seperti jumlah ketersediaan kelas pada

P


mata kuliah yang akan diambil. Sehingga perlu adanya sistempenjadwalan alternative yang dapat mengatasi permasalahantersebut.

Sistem penjadwalan alternative yang ditawarkan dalampenelitian ini akan menggunakan metode asosiasi danalgoritma genetika dengan objek Program Studi TeknikInformatika S1 Universitas Dian Nuswantoro (UDINUS).

II. METODE YANG DIUSULKAN

Dalam penelitian ini, penulis mengusulkan pembuatan sistemmenggunakan dua metode yang dilakukan dalam dua tahap.Tahap pertama, menggunakan metode asosiasi untuk mencariketerhubungan atara mata kuliah yang sudah diambil danyang akan diambil untuk memprediksi jumlah kelas yangakan dibuka. Tahap kedua dilanjutkan dengan menggunakanalgoritma genetika untuk membentuk jadwal alternatif yangoptimal.

A. Metode Asosiasi

Metode Asosiasi dibagi menjadi 2 tahap, yaitu analisafrekuensi tinggi dengan rumus

Support (A) = ℎDan kemudian dilanjutkan dengan tahap pembentukan

aturan asosiatif dengan rumus

Confidence = ( | ) = ℎ ℎB. Algoritma Genetika

Berdasarkan [6] , setiap masalah yang berbentuk adaptasi,baik itu alami maupun buatan dapat diformulasikan ke dalamterminologi genetika.

Algoritma genetika merupakan salah satu algoritma yangsangat tepat untuk digunakan dalam menyelesaikan masalahoptimasi kompleks, yang cukup sulit jika dilakukan dengancara konvensional [7].

Terdapat 6 komponen utama dalam penyelesaian denganalgoritma genetika [6] yaitu teknik pengkodean, prosespembangkitan populasi awal, evaluasi kromosom, seleksi,pindah silang, dan mutasi.

Dalam proses evaluasi kromosom, nilai fitness untuk setiapgen dilakukan dapat dihitung dengan rumus:= ( ) +

A = sembarang bilangan real sebagai konstantax = individu (kromosom)ɛ=bilangan kecil yang ditentukan untuk menghindari

pembagi 0 atau f(x)=0

C. Perancangan Sistem Penjadwalan

Dalam penelitian ini, metode pengembangan sistem yangdigunakan adalah Waterfall dengan perancangan berbasisobjek. Proses development dilakukan dengan menggunakanbahasa pemrograman C# dengan tools Visual Studio Express2013 for Windows Desktop.

III. IMPLEMENTASI

Sistem yang akan dibangun adalah sebuah aplikasipenjadwalan mata kuliah yang mengimplementasikanmetode asosiasi dan algoritma genetika dengan menggunakanProgram studi Teknik Informatika S1 Fakultas IlmuKomputer UDINUS sebagai objek penelitian. Perangkatlunak ini bertujuan sebagai sistem alternatif untukmendapatkan tabel mata kuliah yang lebih optimal denganmemperhitungkan faktor histori pengambilan mata kuliahmahasiswa.

Histori mata kuliah yang diterima oleh sistem adalah dataset yang berupa file csv. File tersebut akan dibaca oleh sistem,di kalkulasi untuk mencari keterhubungan antar mata kuliahdatam setiap transaksi. Kemudian mengembalikan outputberupa file configurasi yang dapat digunakan untukmembangkitkan populasi awal.

Pada implementasi optimasi jadwal, objek yang digunakanadalah Mata_Kuliah, Ruang, Kelompok_Kelas, dan Kelas.

Representasi kromosom pada tabel jadwal digambarkanmenggunakan vector hash map, seperti digambarkan dalamgambar berikut:

Gambar 1 Hash map jadwalBanyaknya slot kelas yang dijadwalkan di semua ruangan

dalam satu hari merupakan satu kromosom. Setiap kromosommemiliki parameter genetika, yaitu crossover dan mutasi.

Nilai fitness ditentukan dengan menggunakan rumus:= ℎ × 5Setiap kelas memiliki skor antara 2 sampai dengan 5.

Initial score tiap kelas adalah 2. Jika kelas ditempatkan padaslot waktu yang kosong, maka skor + 1. Jika kapasitas ruangkelas mampu menampung jumlah mahasiswa dalam satukelompok kelas, maka skor + 1. Jika satu kelompok kelastidak dijadwalkan di kelas lain pada hari dan jam yang sama,maka skor + 1.

a. CrossoverProses crossover menggabungkan hash map dua

kromosom induk yang kemudian di-split berdasarkanjumlah crossover point yang ditentukan secara randommenggunakan iterasi dengan parameter sembaranginteger.

b. MutasiKonsep mutasi lebih sederhana karena hanya perlu

mengambil beberapa slot kelas secara random danmemindahkannya.

Secara umum algoritma genetika yang diterapkan dalamsistem ini hanya menerapkan 2 macam operasi dasar. Yangpertama adalah memilih secara acak sejumlah n pasang


kromosom induk dan menghasilkan generasi baru denganmelakukan crossover dan mutasi. Yang kedua adalahmengganti kromosom yang memiliki nilai fitness yangrendah dengan kromosom generasi baru yang telah dihasilkandari proses sebelumnya.

Kedua operasi dasar ini kemudian diulang berkali-kaliuntuk mendapatkan kombinasi solusi yang lebih optimal danmendekati nilai fitness 1.

IV. HASIL DAN PEMBAHASAN

A. Proses Pembentukan Jadwal

Histori mata kuliah yang telah diinputkan akan diprosesmenjadi file konfigurasi dengan ekstensi cfg yang siapdigunakan untuk proses pembentukan jadwal. Timetabledibentuk menggunakan template hashmap vector sepertiyang terlihat pada gambar 1.

Setelah menu start solving dipilih, maka sistem secaraotomatis akan mulai menggenerate jadwal menggunakanalgoritma genetika, proses pembentukan jadwal, nilai fitness,dan generasi kromosom yang dibentuk dapat dilihat padagambar 2 dan gambar 3.

Gambar 2. Generasi 345 Dengan Nilai Fitnes 0.757778

Gambar 3. Generasi 6354 Dengan Nilai Fitnes 0.800000(max)

V. KESIMPULAN

Kesimpulan yang dapat didapat dari pembahasan atas hasilpenelitian ini yaitu sebagai berikut:

1. Sistem penjadwalan mata kuliah yang dibangun dapatmenghasilkan jadwal mata kuliah yang cukup optimalkarena mampu mengasosiasi antara mata kuliah yangtelah diambil dengan mata kuliah yang ditawarkan,sehingga jumlah pembukaan kelompok kelas dapatlebih efisien dan meminimalisir tabrakan jadwal.

2. Sistem penjadwalan mata kuliah yang dibangunmenerapkan metode Asosiasi dan algoritma Genetika.Penerapan metode Asosiasi dapat membantu sistemdalam melakukan proses pencarian asosiasi mata kuliahdan algoritma Genetika dapat membantu sistem untukmenghasilkan solusi jadwal yang lebih optimal..

3. Sistem penjadwalan mata kuliah dirancang dandibangun dengan tampilan yang sederhana agar mudahdigunakan oleh pengguna. Fitur-fitur yang disediakanpada sistem penjadwalan ini merupakan fitur utamayang diperlukan dalam melakukan penjadwalan matakuliah.

VI. PENELITIAN LANJUTAN

Penelitian dalam rancang bangun sistem penjadwalanmata kuliah ini masih memiliki beberapa kekurangan dankelemahan yang dapat dikembangkan dalam penelitianselanjutnya. Saran bagi penelitian selanjutnya yaitu sebagaiberikut:

1. Sistem penjadwalan mata kuliah ini hanya fokus padabagaimana menghasilkan jadwal mata kuliah yangefisien dengan membaca histori pengambilan matakuliah sebelumnya saja dan tidak memiliki fitur-fituruntuk menangani integrasi dengan sistem lain.

2. Sistem penjadwalan mata kuliah ini menerapkanalgoritma Apriori untuk mencari keterkaitan antaramata kuliah yang telah diambil dan mata kuliah yangakan diambil, namun performa algoritma ini masihdianggap kurang efisien karena terlalu banyakmelakukan perulangan. Sehingga perlu adanyaoptimasi untuk mengurangi runtime sistem yangkurang cepat.

3. Sistem masih belum sepenuhnya otomatis karenamasih perlu menambahkan file histori pengambilanmata kuliah dengan format csv secara manual danpengambilan file configuration hasil dari associationmining pun masih dilakukan secara manual. Sehinggasistem ini perlu lebih dikembangkan lagi dalam halotomatisasinya.

VII. REFERENCES

[1] Y.-T. Wang, "On the Application of Data MiningTechnique and Genetic Algorithm to an AutomaticCourse Scheduling System," IEEE, pp. 400-405, 2008.

[2] E. K. a. J. P. N. Burke, "A Multistage EvolutionaryAlgorithm for The Timetable Problem," IEEETransactions on Evolutionary Computation, vol. 3, pp.63-74, 1999.

[3] D. C. Wood, " A Technique for Colouring a GraphApplication to Large Scale Timetabling Problem," TheComputer Journal, vol. 12, pp. 317-319, 1969.

[4] J. M. Mulvey, "A Classroom/Time AssignmentModel," European Journal of Operational Research,vol. 9(2), pp. 151-162, 1982.

[5] E. a. S. K. S. Yu, "A Generic Algorithm for aUniversity Weekly Courses Timetabling Problem,"


International Transactions in Operational Research,vol. 9, pp. 703-717, 2002.

[6] S. Kusumadewi, Artificial Intelligence (Teknik danAplikasinya), Yogyakarta: Graha Ilmu, 2003.

[7] A. M. Desiani Anita, Konsep Kecerdasan Buatan,Yogyakarta: ANDI OFFSET, 2006.