PENJADWALAN KELAS MATAKULIAH MENGGUNAKAN VERTEX GRAPH COLORING DAN SIMULATED ANNEALING

Jurnal Ilmu komputer dan Sistem Informasi

PENJADWALAN KELAS MATAKULIAH MENGGUNAKAN VERTEX GRAPH COLORING DAN SIMULATED ANNEALING Mariana 1) Lely Hiryanto 2) 1)2)

Teknik Informatika Universitas Tarumanagara Jl. Letjen S. Parman No.1, Jakarta Barat 12020 Indonesia email : [email protected], 2) [email protected]

agar tidak terjadi bentrok dalam suatu penyusunan jadwal. Graph Coloring merupakan metode sederhana dengan mendefinisikan masalah penjadwalan yang dibahas dengan menggunakan graph dan mendefinisikan constraints melalui hubungan antar vertex. Metode ini sudah dipastikan tidak akan melanggar hard constraints. Pada pewarnaan graf dapat menghasilkan lebih dari satu solusi selama solusi tersebut memenuhi dan tidak melanggar syarat dan aturan jumlah minimum warna yang dapat digunakan pada graf tersebut. Hasil penjadwalan terbaik ditentukan dengan jumlah minimum warna yang ada pada pewarnaan graf. Semakin sedikit warna yang dipergunakan maka hasil yang diperoleh akan semakin optimal. Kendala dalam penjadwalan mata kuliah dengan metode ini adalah masih ada kecendrungan terjadinya pelanggaran soft constraints, yaitu pewarnaan mata kuliah dapat melebihi jumlah ruangan yang tersedia, sehingga seharusnya mata kuliah tersebut tidak dapat dijadwalkan, namun dapat dijadwalkan dengan melanggar soft constraints. SA adalah teknik optimalisasi numerik dengan prinsip thermo-dynamic. Algoritma SA diperkenalkan oleh Metropolis et al pada tahun 1953, dan aplikasi algoritma SA mulai dikembangkan dalam masalah optimasi pada tahun 1983 oleh Kirkpatrick et al. Dalam sistem termodinamika, SA menggunakan persamaan Boltzman. Persamaan ini merepresentasikan probabilitas suatu new state yang lebih buruk dari current state yang masih mungkin terpilih sebagai next state. Kelebihan SA adalah dapat menjelajahi seluruh domain, dan SA mampu menghindari jebakan optimum local. Penjadwalan mata kuliah pada umumnya bersifat renggang, artinya banyak mata kuliah yang tidak saling berhubungan. VGC mempunyai kemampuan untuk bekerja dengan baik di atas kerenggangan hubungan antara mata kuliah tersebut [1]. Akan tetapi, mengingat faktor banyaknya mata kuliah yang akan dijadwalkan dengan jumlah ruangan yang terbatas dan kapasitas ruangan yang terbatas sehingga tidak memungkinkan untuk mengalokasikan sejumlah mata kuliah dengan beban sks tertentu di timeslot yang sama. Oleh karena itu diperlukan penggabungan metode VGC dengan salah satu algoritma metaheuristik yang dimana metaheuristik dapat dilihat sebagai kerangka algoritma umum yang diterapkan untuk masalah

ABSTRACT Makalah ini membahas tentang penggabungan metode vertex graph coloring dan simulated annealing dalam menyusun jadwal matakuliah. Penggabungan ini ditujukan untuk mengetahui seberapa layak dan optimal penjadwalan yang dibuat dari gabungan kedua metode ini. Vertex Graph Coloring adalah metode pemberian warna pada simpul dengan mencari vertex tetangga dan tidak bertetangga, sehingga vertex yang bertetangga akan diberi warna yang sama dan vertex yang tidak bertetangga akan diberi warna baru yang berbeda. Simulated Annealing (SA) adalah teknik optimalisasi numerik dengan prinsip thermo-dynamic. Kinerja SA sangat bergantung pada solusi awal, lingkungan pencarian dan proses pendinginan. Vertex Graph Coloring (VGC) bekerja untuk memenuhi seluruh hard constraints dan Simulated annealing bekerja untuk meneruskan proses penjadwalan dengan mengoptimalkan penjadwalan tersebut. Hasil penjadwalan yang diperoleh dari penggabungan kedua metode ini adalah menghasilkan penjadwalan yang visible dan optimal meskipun beberapa ketentuan soft constraints masih terlanggar.

Key words Course Scheduling, Vertex Graph Coloring, Simulated Annealing, Optimization

1. Pendahuluan Penjadwalan kelas mata kuliah adalah suatu sistem penempatan waktu dan ruang dalam proses kegiatan belajar mengajar. Dalam hal ini, penjadwalan erat kaitannya dengan kapasitas dan keterbatasan jumlah ruang, waktu yang dibutuhkan, dan ketersediaan dosen. Penjadwalan mata kuliah di universitas dikenal dengan istilah University Course Timetabling Problem. (UCTP). University Course Timetabling Problem (UCTP) adalah perencanaan pengalokasian sejumlah mata kuliah ke dalam sebuah kumpulan waktu dan ruang selama tidak melanggar syarat atau ketentuan penjadwalan (constraints). Dalam penyusunan jadwal kelas mata kuliah terdapat istilah constraints yang berarti syarat atau ketentuan. Fungsi dari constraints dalam masalah penjadwalan adalah sebagai aturan atau syarat ketentuan

125

Jurnal Ilmu komputer dan Sistem Informasi optimasi yang berbeda dengan sedikit modifikasi agar dapat beradaptasi dengan masalah tersebut. Berdasarkan karakteristik ini dan mengingat sifat istimewa dari masalah penjadwalan kelas mata kuliah membuat metaheuristik sangat cocok dalam problem domain yang akan diselesaikan [2]. Maka dari itu, metode VGC akan digabungkan dengan metode SA yang mempunyai keunikan yang berbeda dalam mencari solusi baru sehingga dapat mengoptimalkan suatu proses penyusunan penjadwalan [3]. Dengan memanfaatkan cooling schedule pada algoritma SA pengalokasian mata kuliah ke time slot akan diulang secara bertahap sehingga menghasilkan penjadwalan yang optimal dengan pengalokasian mata kuliah yang merata. Metode vertex Graph Colouring (VGC) akan bekerja untuk memenuhi seluruh hard constraints, sehingga penjadwalan dapat dikatakan layak. Setelah itu proses pengerjaan selanjutnya akan diteruskan dengan metode Simulated Annealing (SA). Metode SA akan menjelajahi seluruh domain penjadwalan secara acak sehingga sistem akan memeriksa ulang apakah mata kuliah tersebut sudah menemukan posisi yang baik ataukah belum, hal ini dipertimbangkan melalui besar kecilnya nilai fitness dari penjadwalan tersebut, kemudian SA juga bertugas mempertimbangkan hard constraints dari penjadwalan yang dihasilkan VGC dan mempertimbangkan soft constraints yang ada, karena sebelumnya metode VGC bekerja dengan hanya melihat hard constraints dengan tidak mempertimbangkan soft constraints. Sistem yang dibuat adalah Perancangan dan Pembuatan Program Aplikasi Penjadwalan Kelas Mata Kuliah di suatu lembaga pendidikan atau universitas dengan Metode Graph Colouring dan Simulated Annealing, yang dimana sistem tersebut akan menyusun jadwal perkuliahan pada semester reguler beserta jadwal kuliah pengganti, dengan permasalahan jumlah sks dalam 1 matakuliah yang terbilang cukup besar. Makalah ini akan membahas mengenai permodelan UCTP yang dimana penjadwalan akan dibuat terlebih dahulu sehingga mahasiswa dapat mengetahui seluruh informasi yang berkaitan dengan jadwal yang akan mereka registrasikan. Oleh karena itu, dalam tugas akhir ini mahasiswa tidak mempunyai peranan dalam penyusunan jadwal, sehingga penjadwalan ini hanya memperhitungkan faktor ketersediaan dosen, jumlah pemakaian ruangan beserta kapasitasnya, dan slot waktu. Permasalahan UCTP sampai sekarang ini masih dijadikan bahan penelitian karena mengingat banyaknya universitas yang menggunakan sistem penjadwalan secara manual. Dalam proses penyusunan jadwal, penjadwalan mempunyai banyak kendala, dan semua kendala ini sebisa mungkin harus dipenuhi dan tidak boleh di langgar, apabila kendala ini dilanggar, tentu saja akan membuat penjadwalan itu menjadi tidak layak dan optimal. Kendala tersebut berupa permasalahan seperti waktu penjadwalan, bagaimana membuat penjadwalan tersebut dapat tersusun dengan baik mengingat

banyaknya kegiatan dan adanya keterbatasan ruang yang waktu pelaksanaan singkat.

2. Penjadwalan Matakuliah 2.1 Vertex Graph Coloring Graf adalah pasangan himpunan (, ) dengan adalah kumpulan simpul (vertex atau node) dan merupakan himpunan sisi (edges atau arcs) yang menghubungkan sepasang simpul pada graf tersebut, sehingga dengan kata lain graf dapat diartikan sebagai suatu kumpulan vertex yang menjelaskan hubungan antar vertex melalui edges yang terkait. Notasi vertex dan edges akan dituliskan pada persamaan (1) dan persamaan (2) yang akan membentuk graf sebagai berikut [4]:

= , , , … , (1) = , , , … , (2) Pada gambar 2 di bawah ini, dapat diketahui hubungan antar vertex melalui edge – edge yang terhubung. Berdasarkan edges yang terbentuk, maka terhubung dengan dan karena itu dan disebut sebagai tetangga dari , sedangkan tidak bertetangga dengan .

Gambar 2 Graf sederhana

2.1.1. Pewarnaan Graf Pewarnaan graf adalah metode pemberian warna pada suatu vertex, edges, maupun wilayah dalam suatu graf. Pemberian warna yang dimaksudkan bertujuan untuk mencari wilayah tetangga yang ada pada graf. Pewarnaan graf terbagi menjadi 3 macam, yaitu Pewarnaan sisi (edge colouring) [5], Pewarnaan wilayah (region colouring), pewarnaan simpul (vertex coloring). Pewarnaan sisi (edge colouring) merupakan pemberian warna pada setiap sisi pada graf sampai sisi – sisi yang saling berhubungan tidak memilih warna yang sama. Pewarnaan wilayah (region colouring) adalah pemberian warna pada setiap wilayah di graf sehingga

126

Jurnal Ilmu komputer dan Sistem Informasi tidak ada wilayah yang bersebelahan memiliki warna yang sama. Pewarnaan simpul (vertex vertex coloring) coloring adalah pemberian warna pada setiap simpul (vertex vertex) dimana warna yang sama akan diberikan pada vertex yang saling bertetangga, sedangkan ngkan yang tidak bertetangga akan diberi warna lain.

2.1.2. Pewarnaan Vertex Seperti yang dijelaskan sebelumnya, pewarnaan vertex (Vertex graph coloring)) adalah metode pemberian warna pada simpul (vertex)) dengan mencari vertex tetangga dan tidak bertetangga, sehingga vertex yang bertetangga akan diberi warna yang sama dan vertex yang tidak bertetangga akan diberi warna baru yang berbeda. Pewarnaan vertex berfungsi untuk mencari nilai maximum warna yang boleh digunakan dalam suatu sua graf. Jumlah warna paling minimum yang diterapkan dinamakan angka kromatik dinotasikan dengan χ(G). Semakin minim jumlah warna yang digunakan maka penjadwalan tersebut akan semakin efisien. Teknik pewarnaan ini menggunakan derajat tertinggi ( ) sebagai penentu maksimum warna yang digunakan. Derajat tertinggi ini didapatkan dari jumlah edge yang berhubungan dengan vertex tersebut. Batasan jumlah maksimum warna dapat dirumuskan sebagai berikut [6]:

( ) ( )

(3) (4)

2.2.

Simulated Annealing

Simulated Annealing (SA) adalah teknik optimalisasi numerik dengan prinsip thermo-dynamic dynamic. Kinerja SA sangat bergantung pada solusi awal, lingkungan pencarian dan proses pendinginan. Algoritma SA diperkenalkan oleh Metropolis olis et al pada tahun 1953, dan aplikasi algoritma SA mulai dikembangkan dalam masalah optimasi pada tahun 1983 oleh Kirkpatrick et al [7]. Dalam sistem termodinamika, simulated annealing (SA) menggunakan persamaan Boltzman. Persamaan ini merepresentasikan probabilitas suatu new state yang lebih buruk dari current state yang masih mungkin terpilih sebagai next state.. SA dikembangkan berdasarkan ide dari mekanisme perilaku pendinginan dan proses kristalisasi (annealing)) material panas. Algoritma SA melakukan peningkatan iteratif untuk memperbaiki solusi yang dihasilkan teknik teknik-teknik penjadwalan heuristic [8], dalam hal ini adalah sebuah solusi awal yang dibuat dengan teknik heuristik ataupun random diiterasi secara berulang dengan metode annealing dengan menggunakan perturbasi lokal hingga tidak ada peningkatan lagi atau hingga jumlah iterasi yang diinginkan sudah dicapai. Algoritma (Simulated Annealing)) SA khas menerima solusi baru jika biaya ya baru lebih rendah daripada biaya dari solusi saat ini di setiap iterasi. Dengan kriteria tersebut, SA memungkinkan terhindar dari jebakan minimum lokal, hal ini menjadi salah satu kelebihan SA dibandingkan dengan metode penjadwalan lain.

Keterangan :

( ) : angka kromatik, jumlah warna minimum yang

:

dapat digunakan untuk mewarnai sebuah graf. derajat tertinggi dari setiap vertex.

Penggunaan rumus (3) untuk kasus yang merupakan simple graph dan untuk rumus (4) digunakan untuk kasus unsimple graph. Pada pewarnaan vertex,, berbagai macam algoritma banyak digunakan oleh peneliti, namun algoritma yang akan digunakan dalam tugas akhir ini adalah Recursive Largest First Algorithm. Langkah – langkah pewarnaan dalam algoritma ini adalah: t 1. Buat daftar semua simpul dengan derajat tetangga. Dalam derajat tetangga akan diurutkan susunan derajat tetangga dari vertex yang memiliki derajat tertinggi sampai yang terendah. 2. Ambil vertex yang memiliki derajat tetangga tertinggi dan warnai dengan sebuah warna. ai pada langkah 3. Buang vertex yang telah diwarnai sebelumnya dan semua simpul yang bertetangga tersebut dari daftar vertex. 4. Warnai semua vertex yang belum mempunyai warna dengan warna yang sama pada vertex tadi. Kemudian ulangi langkah-langkah langkah diatas hingga semua simpul pada graf terwarnai semua.

Gambar 2 Algoritma Simulated Annealing Sumber: Aycan T.Ayav, Solving the Course Scheduling Problem Using Simulated Annealing, Annealing http://web.iyte.edu.tr/~tolgaayav/papers/Aycan_CourseSch.pdf 4 http://web.iyte.edu.tr/~tolgaayav/papers/Aycan_CourseSch.pdf, Agustus 2012.

Berdasarkan algoritma tersebut, maka di dalam SA terdapat 3 faktor utama dalam cara kerja algoritma SA, yaitu pencarian lingkungan (neighborhood neighborhood searching), searching perhitungan biaya (cost calculation)), dan pendinginan jadwal(cooling schedule). Proses oses dari algoritma SA di atas adalah: 1. Cari inisialisasi awal secara random. 2. Inisialisasi temperatur awal serta temperatur final dengan kondisi , jumlah iterasi ( ),


3. 4. 5.

6.

dan nilai tetap yang mempengaruhi durasi penurunan suhu (!"#$ ). Hitung nilai parameter reduksi suhu dengan persamaan (6). Cari tetangga secara random dengan menggunakan algoritma Simple Searching Neighboorhood (SSN). Hitung nilai cost dari penjadwalan yang dibentuk oleh initialisasi awal di langkah a dengan cara menghitung bobot constraints dari seluruh mata kuliah yang berada dalam seluruh pos domain. Kemudian hitung nilai cost penjadwalan yang telah terbentuk oleh langkah d di atas. Setelah itu bandingkan kedua nilai cost tersebut dengan menggunakan persamaan (4). Ulangi langkah tersebut sebanyak . Setelah iteration count = , update nilai suhu () dengan menggunakan persamaan (5). Ulangi langkah b sampai suhu () mencapai nilai , .

2.2.1.

dipindahkan ke pos lain atau tidak, apabila nilai cost saat ini lebih kecil dari nilai cost sebelumnya maka jadwal tersebut akan dipindahkan dengan persamaan:

%& = ' ' ⋯ ' (5)

Keterangan: %& : jumlah dari perhitungan hard constraints dan soft constraints. ' : bobot constraints. Persamaan (5) digunakan untuk menghitung cost, yang apabila slot tersebut melanggar hard constraints dan soft constraints akan menghasilkan cost yang tinggi dan sebaliknya. Pada proses perpindahan state dari state awal menuju state yang diujikan akan menunjukan perbedaan cost sesuai dengan penjelasan sebelumnya. Proses ini akan diperhitungkan oleh persamaan (6). Perbedaan SA dengan metaheuristik lain adalah SA mempunyai keunikan dalam menentukan solusi baru. Pada persamaan (7), SA akan menerima solusi yang buruk walaupun cost yang dihasilkan mempunya nilai yang tinggi, namun dengan diterimanya solusi buruk ini SA dapat terhindar dari jebakan minimum lokal, yaitu:

Pencarian tetangga

Pencarian lingkungan (Neighborhood Searching) dalam algoritma SA digunakan untuk mengambil satu atau lebih kegiatan yang kemudian akan dibandingkan dengan slot sebelumnya yang hasilnya dihitung melalui persamaan (4) Penjelasan lingkup tetangga dalam algoritma SA ini berarti slot domain selama 1 hari, misalnya hari senin dengan pos1 sampai pos36. Anggota pos dari pos1 sampai dengan pos36 saling bertetangga. Pencarian lingkungan dalam setiap iterasi dari algoritma akan dilakukan satu kali untuk mengetahui set solusi berikutnya yang mungkin. Algoritma yang akan digunakan untuk pencarian lingkungan adalah Simple Searching Neighboorhood (SSN). Algoritma ini merupakan algoritma sederhana yang bekerja dengan memilih secara acak dari 1 kegiatan dan 1 timeslot. SSN() {

) = % (*+ ) − % (* ) exp ( () 0 ) 12 [,]

(6) (7)

Keterangan: ) = Delta, hasil perbandingan fungsi biaya lama dengan fungsi biaya baru % = fungsi biaya (cost) * = inisialisasi solusi, *+ = tetangga dari * . Exp = fungsi exponen. Rand= fungsi rand, memilih nilai dari bilangan 0 sampai dengan 1. Dalam rancangan aplikasi ini, nilai rand yang digunakan adalah 0,9.

ac := select_random_activity(); sl := select_random_time_slot(); slot(ac) := sl;

}

2.2.3. Pendinginan jadwal (cooling schedule) Dalam setiap iterasi ditentukan dengan rumus:

2.2. 2. Perhitungan biaya Dalam penjadwalan mata kuliah, perhitungan biaya (cost calculation) yang dimaksudkan bertujuan untuk memeriksa pengalokasian mata kuliah dalam suatu susunan ruang dan timeslot berdasarkan pertimbangan bobot constraints (hard constraints dan soft constraints) yang terkandung dalam penyusunan jadwal tersebut sehingga akan menunjukan skor penalti dari kedua constraints yang terhubung dalam kegiatan tersebut. Cost calculation dapat diartikan sebagai fungsi fitness yang biasanya digunakan dalam bidang penjadwalan mata kuliah. Perhitungan nilai cost berperan dalam menentukan apakah mata kuliah tersebut boleh

=∝

, suhu berikutnya (8)

∝ = − 6ln( ) − ln ( )9 / !"#$ (9) Keterangan: = parameter reduksi suhu, = suhu saat ini, !"#$ = nilai tetap yang mempengaruhi durasi penurunan suhu. !"#$ yang akan digunakan adalah 4.

128

Jurnal Ilmu komputer dan Sistem Informasi Persamaan (8) digunakan untuk perhitungan suhu, dengan mengalikan parameter reduksi suhu dengan suhu saat ini yang dimana nilai parameter reduksi suhu yang terbentuk itu didapatkan dari persamaan (9). merupakan jumlah iterasi yang ditetapkan untuk mendapatkan hasil yang diinginkan. Dalam perancangan yang dibuat, ditetapkan sebanyak 3 kali, dengan

suhu awal ( ) adalah 1140, suhu ini cukup panas untuk melakukan perpindahan aktivitas ke setiap state tetangga akan tetapi temperatur tersebut akan selalu di-update secara iteratif oleh algoritma SA dengan menggunakan persamaan (6) di atas.

2.3. Penggabungan Vertex graph coloring dengan

Simulated Annealing untuk penjadwalan mata kuliah regular Metode vertex graph coloring telah banyak diujicobakan oleh para peneliti dan menghasilkan penjadwalan UCTP yang optimal. Seluruh hard constraints tidak ada yang terlanggar dan pengoptimalan soft constraints juga terlaksana, namun kendala dalam metode Vertex graph coloring adalah kemungkinan terjadinya pengalokasian pewarnaan vertex yang melebihi batas slot waktu yang tersedia, sehingga diambil jalan alternatif lain yaitu dengan melanggar soft constraints untuk beberapa kelas. Oleh karena itu, dalam tugas akhir ini metode vertex graph coloring akan digabungkan dengan metode simulated annealing. Tahap awal yang dilakukan adalah tahap pemenuhan hard constraints, untuk memuaskan semua kendala yang menjadi kategori hard constraints akan digunakan metode vertex graph coloring. Vertex graph coloring akan menyusun penjadwalan dan mengalokasikan penjadwalan tersebut dengan hanya melihat bagian hard constraints saja. Kemudian algoritma simulated annealing (SA) akan memeriksa pengalokasian jadwal tersebut dengan menelusuri seluruh ruang solusi satu per satu secara acak (random). SA akan bekerja dengan menukar posisi berulang kali dan melihat apakah mata kuliah tersebut melanggar hard constraints dan soft constraints. Selain itu, akan dipertimbangkan juga perhitungan nilai cost agar didapat hasil solusi yang terbaik.

2.4.

Matakuliah pengganti dengan Simulated Annealing

Penjadwalan kuliah pengganti akan dirancang dengan metode SA. Seperti yang telah dijelaskan pada subbab 2.2, gambar 2, tahap awal dalam proses Simulated Annealing adalah mencari inisialisasi solusi awal secara acak. Inisialisasi solusi awal telah dilakukan dengan VGC. Untuk kasus jadwal matakuliah pengganti, jadwal matakuliah reguler merupakan inisialisasi solusi awal, sehingga tidak perlu menggunakan metode VGC lagi. Metode SA dalam penjadwalan matakuliah pengganti diperlukan untuk mencari solusi tempat untuk 1 matakuliah pengganti dengan tidak melanggar hard constraints dan meminimalkan pelanggaran soft constraints yang tidak boleh mengubah susunan jadwal matakuliah reguler yang telah terbentuk sebelumnya. Constraints yang digunakan untuk penjadwalan kuliah pengganti ini sama dengan constraints padaa penjadwalan umum lainnya. Perbedaan penjadwalan kuliah pengganti dengan kuliah umum terletak di cara kerja sistem tersebut dalam menghitung nilai cost pada tabel domain penjadwalan. Dalam penjelasan algoritma SA, nilai cost dihitung dengan cara menjumlahkan nilai pelanggaran constraints dari seluruh mata kuliah, sedangkan pada kuliah pengganti, nilai cost akan dihitung dengan cara hanya memfokuskan mata kuliah pengganti tersebut dengan mata kuliah umum lainnya yang berada pada 1 timeslot yang sama.

Gambar 4 Flowchart proses penjadwalan kuliah pengganti

3.

Gambar 3 Flowchart penggabungan metode VGC dan SA

Pembuatan

Pembuatan program aplikasi ini menggunakan data matakuliah semester ganjil di suatu fakultas dari sebuah universitas sebagai acuan untuk pembuatan program aplikasi penjadwalan matakuliah. Fakultas tersebut memiliki pembagian gedung dan ruangan berdasarkan jenis matakuliah praktikum dan teori. Kemudian fakultas

Jurnal Ilmu komputer dan Sistem Informasi Menu ini berisi input data kurikulum di fakultas dan akan menampilkan hasil data yang telah diinput. c) Sub menu input kelompok matakuliah Menu ini berisi input data nama kelompok matakuliah di fakultas sesuai dengan departemen pendidikan. Menu ini akan menampilkan hasil data kelompok matakuliah yang telah diinput. d) Sub menu input ruang kelas Menu ini berisi input data ruang kelas yang digunakan fakultas dan akan menampilkan hasil data ruang yang telah diinput. e) Sub menu input dosen Menu ini berisi input data dosen fakultas dan akan menampilkan hasil data seluruh dosen tetap dan tidak tetap yang telah diinput. f) Sub menu input matakuliah Menu ini berisi input data matakuliah fakultasdan akan menampilkan hasil data seluruh matakuliah yang telah diinput. g) Sub menu input kelas matakuliah Menu ini berisi input data kelas matakuliah fakultas dan akan menampilkan hasil data seluruh kelas matakuliah yang telah diinput. h) Sub menu input waktu Menu ini berisi input waktu perkuliahan yang diinginkan fakultas dan akan menampilkan hasil data waktu secara otomatis sesuai dengan waktu 1 sks yang telah diinput dan di generate. i) Sub menu edit dosen tidak tetap Menu ini berisi untuk mengedit inputan waktu ketersediaan mengajar dari dosen tidak tetap fakultas dan akan menampilkan hasil data seluruh waktu dosen tidak tetap. 3. Menu view Menu view berisi data hasil generate jadwal matakuliah berdasarkan semester yang diinginkan (report). Menu ini sama fungsinya dengan menu view yang ada pada modul user 4. Menu generate jadwal Menu ini berfungsi untuk mengenarate jadwal matakuliah berdasarkan tahun semester yang dipilih. 5. Menu matakuliah pengganti Menu ini digunakan untuk generate matakuliah pengganti berdasarkan matakuliah yang telah tersusun sebelumnya.

tersebut juga memiliki jumlah sks yang terbilang cukup banyak dengan 2-6 per 1 sks. Program aplikasi penjadwalan mata kuliah ini menggunakan spesifikasi perangkat keras sebagai berikut: 1. Processor Intel(R) Core(TM) i3, 2.20 GHz. 2. Monitor 14” dengan resolusi 1366 x 768 piksel 3. Harddisk dengan kapasitas 600 GB. 4. NVIDIA GeForce 540GT 2Gb. Sedangkan spesifikasi perangkat lunak yang digunakan sebagai berikut : 1. Sistem operasi Windows XP 2. Basis data MYSQL. 3. PHP sebagai bahasa pemrograman. 4. Adobe Dreamweaver CS 3 sebagai perancangan desain dan koding PHP. 5. XAMPP 1.7.2 sebagai web-server. 6. Adobe Reader 9 sebagai pengolah file berekstensi .PDF. 7. Microsoft Word 2007 sebagai pengolah teks, tabel, dan alur proses. Program aplikasi penjadwalan ini dibuat dengan menggunakan pemrograman berbasis PHP dengan sistem basis data MYSQL. Tampilan antar muka aplikasi, dibuat berdasarkan data – data yang diperlukan oleh fakultas tersebut, sehingga dibuat beberapa modul yang terkait dengan penjadwalan, antara lain: 1. Modul user Modul user digunakan oleh mahasiswa dan dosen untuk melihat jadwal matakuliah yang dapat diakses langsung tanpa login. Pada modul user terdapat beberapa menu, yaitu : a. Menu Home User dapat mengakses menu home yang di dalamnya berisi menu login yang hanya dapat diakses oleh admin. b. Menu View Menu view berisikan informasi mengenai penjadwalan pada semester yang dipilih. 2. Modul admin Modul ini merupakan modul utama untuk penyusunan penjadwalan yang hanya dapat diakses oleh admin. Pada modul ini terdapat beberapa menu, yaitu: a. Menu home Menu home pada modul ini berisi register untuk membuat admin baru. b. Menu input Menu input mempunyai beberapa sub menu input untuk mengatur atau memanipulasi (mengubah, menambahkan, dan menghapus) data. Sub menu yang terdapat dalam menu input adalah: a) Sub menu input prodi Menu ini berisi input data program studi yang ada di fakultas dan akan menampilkan hasil dari seluruh data program studi yang telah diinput. b) Sub menu input kurikulum

4.

Pengujian dan Hasil Pengujian

4.1 Pengujian Aplikasi penjadwalan ini dibuat dengan 3 percobaan sekaligus untuk mengetahui cara kerja dari setiap metode dan seberapa efisien metode tersebut untuk meminimalkan pelanggaran pada setiap constraints, yaitu percobaan dengan memasukan data semester ganjil di fakultas tersebut dengan metode VGC saja, kemudian percobaan kedua menggabungkan metode VGC dengan

130

Jurnal Ilmu komputer dan Sistem Informasi SA yang menggunakan rumus exp ( () 0) 12 [,], dan terakhir menggabungkan metode VGC dengan metode SA tanpa menggunakan rumus exponen.

sehingga beberapa matakuliah yang melanggar hard constraints dan soft constraints belum tentu dapat terambil dan terpindahkan secara optimal. Tabel 2 Perbandingan penjadwalan secara manual dengan hasil pengujian

4.2 Hasil pengujian Berdasarkan hasil pengujian tersebut, hasil terbaik dicapai oleh penggabungan metode VGC dengan metode SA tanpa menggunakan rumus exp ( () 0) 12 [,] kemudian hasil tersebut akan dibandingkan dengan hasil penjadwalan yang telah dibuat sebelumnya oleh universitas tersebut secara manual. Penghapusan ) = %(*+ ) − %(* ) ;1 exp ( () 0) rumus 12 [,] dirasakan lebih efektif sehingga apabila salah satu kondisi memenuhi perumusan tersebut, maka SA akan memindahkan matakuliah ke slot yang baru meskipun slot baru tersebut mempunyai nilai cost yang lebih buruk dari nilai cost yang sebelumnya. Kemudian dari pengujian yang didapat, hasil yang terbaik akan dibandingkan dengan hasil penjadwalan secara manual yang dibuat oleh universitas tersebut yang dapat dilihat pada tabel 2.

No

Program Studi

Pelanggaran

Desain Komunikasi Visual (DKV) Manual Desain Interior (DI)

VGC+ SA (tanpa rumus)

Desain Komunikasi Visual (DKV) Desain Interior (DI)

Hard Constraints Soft Constraints Hard Constraints Soft Constraints Hard Constraints Soft Constraints Hard Constraints Soft Constraints

Jumlah Pelanggaran 0 27 kelas 0 20 kelas 0 kelas 9 kelas 0 kelas 11 kelas

Dari hasil pengujian terhadap data yang telah dilakukan, tidak ditemukan pelanggaan hard constraints. Kemudian dilakukan pengujian sebanyak 5 kali terhadap data kuliah pengganti dan didapatkan hasil sebagai berikut:

Tabel 1 Hasil pengujian

No VGC

VGC+ SA (dengan rumus)

VGC +SA (tanpa rumus)

Program Studi Desain Komunikasi Visual (DKV) Desain Interior (DI) Desain Komunikasi Visual (DKV) Desain Interior (DI) Desain Komunikasi Visual (DKV) Desain Interior (DI)

Hard Constraints Soft Constraints

Jumlah Pelanggaran 0 12 kelas


0 15 kelas


7 kelas 24 kelas


8 kelas 16 kelas


0 9 kelas


0 11 kelas

Pelanggaran

Tabel 3 Hasil penjadwalan matakuliah pengganti pada data semester ganjil 2012/2013

No 1

2

Program Studi Desain Komunikasi Visual (DKV) Desain Interior (DI)

Hard Constraints

Jumlah Pelanggaran 0

Soft Constraints

2 kelas

Hard Constraints

0

Soft Constraints

3 kelas

Pelanggaran

Berdasarkan Pengujian black box testing, program aplikasi ini telah berjalan sesuai dengan rancangan. Gambar 5 dan 6 merupakan tampilan output dari hasil penjadwalan.

Berdasarkan perbandingan data pada tabel 2 dapat disimpulkan bahwa penjadwalan yang dihasilkan oleh aplikasi lebih dapat mengoptimalkan penjadwalan dibandingkan dengan penjadwalan secara manual. Metode VGC dalam penjadwalan ini digunakan untuk mengatur penjadwalan agar tidak melanggar ketentuan hard constraint, karena metode ini sudah terpercaya dapat bekerja dengan baik dalam setiap kasus penjadwalan. Pengoptimalan penjadwalan menggunakan metode SA, namun metode SA dirasakan kurang bekerja dengan baik, karena cara kerjanya yang bersifat random,

Gambar 5 Hasil penjadwalan matakuliah reguler

131


REFERENSI [1] Aycan, E., Ayav, T., 1995, “Solving the Course Scheduling Problem Using Simulated Annealing”, Department of Computer Engineering. [2] Diestel, Reinhard., 2006, “Graph Theory : Third Edition”, Birkhauser, Heidelberg-Springer. [3] Hajnal, Peter., Szemeredi, Endre., 1990, “Brooks Coloring in Parallel”, Toronto. [4] Lewis, Rhydian., Mei 2007, “A Survey of Metaheuristic-based Techniques for University Timetabling Problems”, Cardiff Unversity, Wales. [5] Miner, Sara K., Elmohamed, Saleh., Yau, Hon W., “Optimizing Timetabling Solution Using Graph Coloring”, Syracuse University, New York State. Gambar 6 Hasil penjadwalan matakuliah pengganti

Penulis Pertama, saat ini sebagai mahasiswa di program studi Teknik Informatika, Fakultas Teknik Universitas Tarumanagara.

5. Kesimpulan dan Saran

Penulis Kedua, memperoleh gelar S.T tahun 2001 di program studi Teknik Informatika, Fakultas Teknik, Universitas Tarumanagara. Kemudian mendapat gelar M.Sc pada tahun 2006 di Department Of Computing Curtin University Of Technology, Australia. Saat ini sebagai Staf Pengajar program studi Teknik Informatika, Fakultas Teknik Universitas Tarumanagara.

5.1 Kesimpulan Berdasarkan hasil pengujian program aplikasi penjadwalan kelas matakuliah di suatu universitas, dapat diambil kesimpulan, bahwa: rumus exp ( () 0) 1. Penghapusan 12 [,]pada SA dirasakan lebih membantu hasil penjadwalan menjadi lebih optimal. 2. SA mempunyai sifat random sehingga dalam pengerjaannya SA akan mengambil matakuliah secara random, sehingga matakuliah tertentu bisa saja tidak terpilih dan terpindahkan, hal ini menyebabkan pelanggaran soft constraints masih dapat terjadi dan SA juga akan beresiko berada pada posisi infinite loop. 3. Penjadwalan kelas matakuliah reguler dan matakuliah pengganti sudah tidak melanggar hard constraints namun masih cenderung melanggar soft constraints. 5.2 Saran Saran-saran yang dapat diberikan bagi mereka yang ingin mengembangkan aplikasi penjadwalan matakuliah ini adalah sebagai berikut: 1. Untuk percobaan selanjutnya, disarankan mencoba penggabungan metode VGC dengan metode lain untuk lebih meminimalkan pelanggaan soft constraints, karena dengan random tidak menjamin terpilihnya matakuliah yang melanggar soft constraints dan tidak menjamin pelanggaran soft constraints matakuliah yang dipindahkan mencapai nilai 0. 2. Pemberian jedah waktu pada setiap matakuliah di satu jenis kelas sebagai bentuk kebijakan terhadap mahasiswa.

132

PENJADWALAN KELAS MATAKULIAH MENGGUNAKAN VERTEX GRAPH COLORING DAN SIMULATED ANNEALING

Recommend Documents