Josselyn Sinthia Thio 1) Lely Hiryanto 2)

Jurnal Ilmu Komputer dan Sistem Informasi

IMPLEMENTASI VERTEX GRAPH COLOURING, PARTICLE SWARM OPTIMIZATION, DAN CONSTRAINT BASED REASONING UNTUK UNIVERSITY TIMETABLING PROBLEM (STUDI KASUS: FTI UNTAR) Josselyn Sinthia Thio 1) Lely Hiryanto 2) 1) 2)

Teknik Informatika Fakultas Teknologi Informasi Universitas Tarumanagara Jl. Letjen. S. Parman No. 1, Jakarta 11440 Indonesia email :1) [email protected], 2), [email protected]

yang dibutuhkan untuk suatu ujian. Masalah penjadwalan perkuliahan dan ujian pada universitas disebut University Timetabling Problem.[2] Sebagai contoh kasus dalam rancangan ini digunakan permasalahan penjadwalan perkuliahan dan ujian pada Fakultas Teknologi Informasi Universitas Tarumanagara (FTI Untar). Telah dilakukan beberapa perancangan penjadwalan komputatif untuk menggantikan penjadwalan manual FTI Untar namun perancanganperancangan tersebut masih belum dapat menghasilkan jadwal yang sesuai dengan constraints yang ada. Pada perancangan penjadwalan perkuliahan yang dibuat oleh Jacklin Sinthia Thio dengan menggunakan metode Graph Colouring[3], Sri Whisnu Andokowimbo dengan menggunakan metode Vertex Coloring Heuristic[4], dan Ayu Windy Astuti dengan menggunakan metode Hybrid Particle Swarm Optimization dan Constraint Based Reasoning[5] masih terdapat beberapa pelanggaran soft-constraints pada hasil pengujian yang dilakukan. Selain itu penjadwalan ujian yang dilakukan oleh Benny Yohanes dengan menggunakan algoritma Particle Swarm Optimization[6] masih menghasilkan pelanggaran hard-constraints pada beberapa pengujian yang dilakukan. Pelanggaran constraints yang masih terjadi pada perancangan-perancangan tersebut diatasi melalui perancangan penjadwalan perkuliahan dan ujian yang dibuat menggunakan metode Vertex Graph Colouring, Particle Swarm Optimization, dan Constraint Based Reasoning.

ABSTRACT An application of exams and courses scheduling is made using Vertex Graph Colouring, Particle Swarm Optimization, and Constraint Based Reasoning method to produce a valid and optimal exam and course schedule which can also fulfill the demands of special schedule and room needs. FTI Untar is used as a study case in this development. The results of the tests done for the courses scheduling of even semester of 2010 / 2011 till odd semester of 2012 / 2013, without collision of special preferences, show that on average there’s no hard-constraints (constraints that must be satisfied) violation, only 13% of soft-constraints (constaints that are attempted to be satisfied) violations between each course and 6% soft-constraints violation due to the poor preference score of the room or time used. Whilst, the results of the tests done for the exams scheduling of odd semester of 2011 / 2012 and 2012 / 2013 show that on average there’s no hard-constraint and soft-constraint violation between each course although there is still 1% soft-constraints violation due to the poor preference score of the room used. The development was tested to the Secretariat of Informatics Department in FTI Untar and obtain a positive response because of the userfriendly user interfaces and can help to accelerate the process of course, practicum, and exam schedule’s report making.

Key words Constraint Based Reasoning, Great Deluge Algorithm, Particle Swarm Optimization, University Timetabling Problem, Vertex Graph Colouring

2. University Timetabling Problem University Timetabling Problem (UTP) adalah perencanaan pengalokasian sejumlah matakuliah ke dalam sekumpulan waktu dan ruang selama tidak melanggar batasan (constraints) yang ditetapkan [7]. UTP secara umum dapat dimodelkan sebagai Constraint Satisfaction Problem (CSP), yaitu sebuah himpunan

1. Pendahuluan Penjadwalan perkuliahan merupakan sebuah masalah yang sulit karena kompleksitas constraints yang harus dipenuhi untuk memenuhi tuntutan mahasiswa dan dosen[1]. Demikian pula dengan penjadwalan ujian yang harus menyesuaikan kapasitas ruang dengan kapasitas

97


variabel yang telah terkait dengan domain dan himpunan constraint, sebagai berikut [7]: 1. Himpunan matakuliah (subjects), X = {x1 , x 2 ,......... , x N } . Umumnya tiap matakuliah memiliki atribut dosen, ruang kuliah, slot waktu kuliah, bobot (sks), kapasitas, semester distribusi, dan lain-lain sesuai kurikulum operasional universitas terkait. 2. Himpunan domain dua dimensi, yaitu dimensi ruang dan waktu (rooms and timeslots), D = {d 1 , d 2 ,......... , d M } . Domain dari UTP berdimensi dua, yaitu dilihat dari dimensi ruang kuliah dan slot waktu kuliah. Setiap elemen dari matriks selanjutnya disebut slot posisi. 3. Himpunan ketentuan (constraints), C = {c1 , c2 ,........., cL } . Constraints adalah suatu kondisi yang harus dipenuhi sebisa mungkin tetapi tidak sepenuhnya penting untuk penjadwalan yang optimal.

4. Ulangi langkah ke-2 dan ke-3 hingga daftar simpul kosong. 5. Kemudian ulangi langkah ke-1 hingga ke-4 di atas hingga semua simpul pada graf terwarnai.

3.2. Particle Swarm Optimization Algoritma Particle Swarm Optimization (PSO) pertama kali diperkenalkan oleh Dr. Eberhart dan Dr. Kennedy pada tahun 1995.[11] Kelebihan utama algoritma PSO adalah mempunyai konsep sederhana, mudah diimplementasikan, dan efisien dalam perhitungan jika dibandingkan dengan algoritma matematika dan teknik optimisasi heuristik lainnya [12]. Algoritma PSO meniru perilaku dari sekelompok burung di mana setiap individu akan selalu terbang mencari tempat terbaik.[12] Dalam PSO sejumlah entitas sederhana (partikel) diasumsikan mempunyai posisi awal pada suatu lokasi yang acak dalam ruang pencarian multidimensi di mana setiap partikel diasumsikan mempunyai dua karakteristik yaitu posisi dan kecepatan.[13] Masing-masing partikel mengevaluasi fungsi tujuannya di posisi saat ini dan bergerak berdasarkan penggabungan beberapa aspek historisnya, yaitu posisi saat ini dan posisi terbaik yang pernah dilalui (best-fitness), dengan informasi dari satu atau lebih anggota dalam kelompok.[13] Akhirnya partikel-partikel tersebut secara keseluruhan, akan berpindah ke lokasi yang dekat dengan fungsi fitness yang optimal.[11] Beberapa istilah umum yang digunakan dalam Particle Swarm Optimization adalah[14]: 1. Swarm: populasi dari suatu algoritma. 2. Particle: anggota (individu) pada suatu swarm. Setiap particle merepresentasikan suatu solusi yang potensial pada permasalahan yang diselesaikan. 3. Pbest (Personal best): posisi Pbest suatu particle yang menunjukkan posisi terbaik dari suatu particle. 4. Gbest (Global best): posisi terbaik dari seluruh particle yang ada pada swarm. 5. Velocity (vektor): vektor yang menggerakkan proses optimisasi, menentukan arah perpindahan suatu particle untuk memperbaiki posisi semula. 6. c1 dan c2: c1 merupakan konstanta pembelajaran kognitif dan c2 merupakan konstanta pembelajaran sosial.

Constraints yang dipakai dalam perancangan ini dibagi menjadi dua jenis, yaitu hard-constraint dan softconstraint. Hard-constraint adalah batasan yang harus dipenuhi dan tidak boleh dilanggar dalam melakukan penjadwalan[8], misalnya tidak ada dosen yang dapat dijadwalkan pada lebih dari satu kelas matakuliah pada waktu yang sama. Sedangkan soft-constraint adalah batasan yang masih boleh dilanggar tetapi diusahakan untuk dipenuhi untuk mendapatkan penjadwalan yang optimal [8], misalnya jadwal mengajar dari seorang dosen yang hanya dapat mengajar pada hari tertentu saja.

3. Model Solusi untuk University Timetabling Problem 3.1. Vertex Graph Colouring Pewarnaan vertex (Vertex Colouring) adalah pemberian warna-warna pada titik-titik dalam suatu graf sedemikian rupa sehingga tidak ada dua titik yang bertetangga berwarna sama [9]. Untuk menyelesaikan masalah penjadwalan perkuliahan dan ujian pada FTI Untar, pada perancangan yang dibuat digunakan algoritma Recursive Largest First denga langkah kerja sebagai berikut [10]: 1. Buat daftar semua simpul pada graf yang belum diwarnai beserta derajat tetangga (jumlah simpul tetangga yang belum diwarnai) terurut secara descending yang disebut degree list dan tetapkan sebuah warna baru. 2. Ambil simpul pertama pada degree list (simpul dengan derajat tetangga tertinggi) dan warnai. 3. Buang simpul yang telah diwarnai pada langkah sebelumnya dan semua simpul yang bertetangga dengan simpul tersebut dari daftar simpul.

Proses dari algoritma PSO untuk memperbaharui velocity dapat dirumuskan seperti pada persamaan (1) [14]. Pada perancangan ini, persamaan untuk update velocity yang dipakai mengalami perubahan dari rumus standar PSO yaitu adanya penambahan constriction factor χ yang berguna untuk mengontrol besarnya kecepatan partikel seperti yang dapat dilihat pada persamaan (2) [15]. = + ∗ ∗ − + ∗ ∗ − ....(1)

98


= χ ∗ ∗ + ∗ ∗ − + ∗ ∗ − ……………………………………………….………(2)

$

Secara garis besar, cara kerja algoritma PSO dapat dilihat pada gambar 1.

Sedangkan untuk update posisi digunakan rumus pada persamaan (3)[13]: Xi=Xi-1+Vi……

...………………………………………(3)

3.3. Fungsi Fitness

Keterangan: = velocity terkini = velocity sebelumnya = posisi partikel terkini = Particle Best = Global Best = beban inersia, di mana nilai ditentukan sebagai berikut: [7] = 1/2 ∗ log 2 , = 2 konstanta percepatan positif. Ditentukan nilai = 2.8 dan = 1.3 . [7]

, = 2 nilai acak antara 0 sampai 1 = Faktor penyempitan untuk mengontrol besarnya χ kecepatan, persamaannya sebagai berikut: [7]

χ

= c1 + c2, φ > 4. Biasanya φ ditetapkan 4.1, sehingga χ menjadi 0.7298. [7]

Fungsi fitness yang dipilih digunakan untuk mengoptimalisasi nilai preferensi untuk memanfaatkan timeslot dan ruang yang baik [16]. Dengan menggunakan nilai yang diperoleh dari fungsi fitness tersebut, matakuliah akan dialokasikan pada ruang dan timeslot terbaik selama tidak ada constraint yang dilanggar [7]. Persamaan fungsi fitness yang dipakai adalah: [7] &' = ()*. +,-./0, + /,-./0, ……..... (4) Keterangan : +,-./0,

nilai preferensi timeslot untuk matakuliah , , i = 1,2,...n /,-./0, = nilai preferensi ruang untuk matakuliah , i = 1,2,...n ,

= 2 / |2 − φ − #$ − 4$|

=

Gambar 1 Flow Chart Algoritma PSO

untuk mencari penyelesaian yang diinginkan yaitu backtracking dan local search [7]. Local search merupakan sebuah metode yang berusaha memperbaiki solusi saat ini dengan perubahan lokal, yang dilakukan dengan mencari kemungkinan solusi pada tetangga (neighborhoods) dari solusi saat ini [18]. Untuk kasus timetabling, tetangga dapat berupa sebuah timetable yang sama dengan sebuah atau beberapa matakuliah yang diletakkan pada posisi berbeda [17]. Local search dapat dilakukan dengan berbagai cara. Pada rancangan ini digunakan local

3.4. Constraint Based Reasoning Constraint Based Reasoning (CBR) adalah teknik penyelesaian masalah (constraint propagation) yang digunakan untuk menyelesaikan CSP [7]. Teknik penyelesaian tersebut biasanya tidak langsung dapat memberikan penyelesaian yang diinginkan sehingga biasanya ditambahkan teknik pencarian (search) ke dalamnya[17]. Terdapat dua jenis teknik atau algoritma pencarian (search) yang banyak digunakan dalam CBR

99


search dengan Great Deluge Algorithm untuk memvalidasi solusi awal yang telah dioptimalisasi dengan metode PSO untuk mencari solusi terbaik dengan mencari lokasi timeslot potensial terbaik ketika terjadi bentrokan dalam penjadwalan. Great Deluge Algorithm, pertama kali diperkenalkan oleh Dueck pada tahun 1993, merupakan sebuah algoritma yang digunakan untuk menyelesaikan masalah .

optimisasi [19]. Algoritma ini menggantikan solusi awal dengan solusi terbaik yang ditemukan [19]. Pada perancangan ini, digunakan prinsip dasar Great Deluge Algorithm yang mengacu pada [20] dengan sedikit perubahan untuk mempersingkat waktu proses. Algoritma Great Deluge Algorithm yang telah diubah dan digunakan dalam program aplikasi yang dirancang dapat dilihat pada gambar 3

Gambar 3 Flowchart Cara Kerja Great Deluge Algorithm yang Telah Diubah

menggunakan solusi awal yang diperoleh dari metode Vertex Graph Colouring. Hal ini dikarenakan sifat Vertex Graph Colouring yang menggunakan jumlah warna minimum dalam menyelesaikan masalah sangat sesuai untuk masalah yang memerlukan optimasi penggunaan sumber daya seperti University Timetabling Problem (UTP).[21] Pengoptimalisasian jadwal yang dihasilkan dengan menggunakan metode PSO masih belum cukup karena sifat PSO yang mencari solusi potensial sesuai dengan fitness function tetapi tidak memenuhi constraints yang ada sehingga diperlukan sebuah teknik penanganan constraints untuk mencapai solusi optimal yaitu Constraint Based Reasoning [7]. Sedangkan kelemahan dari metode Constraint Based Reasoning yang membutuhkan solusi awal dapat diatasi dengan menggunakan solusi yang diperoleh dari metode PSO. Model solusi penjadwalan yang dirancang mengadopsi model solusi UTP yang diusulkan oleh [7] dengan memberikan sejumlah perubahan pada setiap langkah pendekatan yang diajukan. Alur kerja penggabungan Vertex Graph Coloring (VGC), Particle

3.5. Penggabungan Vertex Graph Colouring, Particle Swarm Optimization, dan Constraint Based Reasoning Penggabungan metode Vertex Graph Colouring, Particle Swarm Optimization, dan Constraint Based Reasoning dalam rancangan yang dibuat diharapkan dapat saling mengatasi kelemahan masing-masing. Kelemahan dari Vertex Graph Colouring berupa adanya kemungkinan pemakaian ruang dan waktu yang berlebihan pada jadwal yang dihasilkan[4] diatasi dengan pengoptimalisasian yang dilakukan oleh metode Particle Swarm Optimization. Demikian pula dengan preferensi ruang serta waktu yang akan diatasi dalam metode Particle Swarm Optimization. Sementara kelemahan dari algoritma PSO yaitu banyaknya iterasi yang dibutuhkan untuk mencapai solusi yang sesuai dengan fitness function yang ditetapkan[6] menyebabkan lamanya waktu proses. Oleh karena itu untuk mempercepat pencapaian solusi optimal, maka pada perancangan ini inisialisasi posisi matakuliah tidak dilakukan secara random tetapi

100


Swarm Optimization, dan Constraint Based Reasoning dapat dilihat pada gambar 2.

4. Hasil Percobaan 4.1. Implementasi Penjadwalan perkuliahan dan ujian yang dirancang diimplementasikan dalam bentuk program aplikasi dengan menggunakan bahasa pemrograman PHP. Sedangkan perangkat lunak yang digunakan adalah : 1. Sistem operasi Windows XP Professional SP 3 2. Basis data MySQL 3. Adobe Dreamweaver CS 5.5 sebagai perancang desain dan coding PHP 4. XAMPP 1.7.2 sebagai web-server 5. Microsoft Word 2007 sebagai pengolah teks 6. Microsoft Visio 2007 sebagai pengolah tabel, graf, dan chart 7. Adobe Reader 9 sebagai pengolah file berekstensi .PDF Modul-modul yang terdapat pada aplikasi yang dirancang adalah sebagai berikut: 1. Modul Generate Schedule Modul Generate Schedule merupakan modul yang hanya dapat diakses oleh hak akses operator untuk menghapus, mengubah, atau menambahkan data kelas matakuliah maupun ujian yang akan dijadwalkan. a. Submodul Kelas Matakuliah Submodul untuk memasukkan, mengubah, atau menghapus data kelas matakuliah yang akan dibuka.

Gambar 2 Alur Kerja Penjadwalan dengan Vertex Graph Colouring, Particle Swarm Optimization, dan Constraint Based Reasoning

Setelah mengadakan pengujian pada rancangan yang dibuat, ternyata masih terdapat pelanggaran hardconstraint. Oleh karena itu setelah seluruh proses dari ketiga metode selesai, ditambahkan suatu tahap validasi akhir yang mengacu pada algoritma Great Deluge Algorithm yang dipakai, seperti yang dapat dilihat pada gambar 3, untuk memindahkan kelas matakuliah yang masih melanggar hard-constraint ke posisi yang baru. Pada tahap ini pelanggaran soft-constraints yang terjadi sudah tidak dipertimbangkan lagi dan jumlah iterasi yang dilakukan adalah sebanyak slot kosong yang tersedia. Tahap validasi akhir hanya dilakukan apabila terdapat pelanggaran hard-constraint pada solusi yang dihasilkan. Validasi ini hanya dilakukan satu kali saja. Flowchart dari tahap validasi akhir dapat dilihat pada gambar 4.

Gambar 5 Tampilan Submodul Kelas Matakuliah

b. Submodul Praktikum Submodul untuk mengisi, mengubah, atau menghapus data kelas praktikum yang akan dibuka.

Gambar 4 Flowchart Cara Kerja Tahap Validasi Akhir

Gambar 6 Tampilan Submodul Praktikum

101


c. Submodul Ujian Submodul untuk mengisi, mengubah, atau menghapus data ujian yang akan dilaksanakan.

rata-rata pelanggaran yang diperoleh dari penjadwalan ujian yang dilakukan adalah: Tabel 1 Rata-rata Pelanggaran Constraints pada Pengujian Penjadwalan Ujian Tengah Semester

Semester Gambar 7 Tampilan Submodul Ujian

Hardconstraint

Softconstraint (antar partikel)

Soft-constraint (ruang atau slot)

0

0

1

0

0

1

Ganjil 2012/2013 (101 Kelas Matakuliah) Ganjil 2011/2012 (82 Kelas Matakuliah)

2. Modul View Schedule Modul yang dapat diakses oleh pengguna yang memiliki hak akses untuk melihat hasil penyusunan jadwal perkuliahan dan ujian.

Tabel 2 Rata-rata Pelanggaran Constraints pada Pengujian Penjadwalan Ujian Akhir Semester

Semester

Hardconstraint

Softconstraint (antar partikel)

Soft-constraint (ruang atau slot)

0

0

1

0

0

1

Ganjil 2012/2013 (101 Kelas Matakuliah) Ganjil 2011/2012 (82 Kelas Matakuliah) Gambar 8 Tampilan Modul View Schedule (Jadwal Perkuliahan)

Sedangkan hasil pengujian untuk jadwal perkuliahan yang ditambahkan dengan tahap validasi akhir dan tidak ada preferensi slot khusus yang saling berbentrokan sebanyak 10 kali untuk tiap semester, tidak terdapat matakuliah yang melanggar Hard-constraint meskipun ada beberapa kelas matakuliah yang melanggar SoftConstraints. Tabel 3 Rata-rata Pelanggaran Constraints pada Pengujian Penjadwalan Perkuliahan dengan Preferensi Khusus Ruang dan Slot dengan Tahap Validasi Akhir Kelas Matakuliah Semester

Ganjil 2012 / 2013 (105 Kelas Matakuliah)

Gambar 8 Tampilan Modul View Schedule (Jadwal Ujian)

Ganjil 2011 / 2012 (84 Kelas Matakuliah)

4.2. Pengujian

Genap 2011 / 2012

Hasil pengujian untuk penjadwalan ujian sebanyak 10 kali untuk tiap semester, tidak terdapat matakuliah yang melanggar hard-constraint, namun masih terdapat kemungkinan terlanggarnya soft-constraints. Tabulasi

(89 Kelas Matakuliah)

Genap 2010 / 2011 (97 Kelas Matakuliah)

102

Kelas Praktikum / Kelas di Lab SoftConst SoftHardConstrai raint Const nt (ruang (antar raint atau slot) partik el)

HardConst raint

SoftConst raint (antar partik el)

SoftConst raint (ruang atau slot)

0

6

7

0

2

1

0

6

5

0

5

1

0

11

3

0

8

1

0

7

4

0

3

1


Pelanggaran soft-constraints yang terjadi pada jadwal yang dihasilkan dapat diatasi melalui pengubahan edit manual yang tersedia pada aplikasi. Edti manual tersebut dapat dilakukan baik untuk jadwal perkuliahan, ujian, maupun praktikum yang dihasilkan oleh aplikasi yang dirancang.

REFERENSI [1] Murray, Keith and Muller, Tomas., 2008, “Automated System for University Timetabling”, University of Nottingham, Nottingham. [2] Abdullah, Salwani., 2006, “Heuristic Approaches For University Timetabling Problems”, University of Nottingham, Nottingham. [3] Thio, Jacklin Sinthia., 2011, “Perancangan Program Aplikasi Penjadwalan Matakuliah pada Fakultas Teknologi Informasi Universitas Tarumanagara dengan menggunakan Metode Graph Colouring”, Program Studi Teknik Informatika Fakultas Teknologi Informasi Universitas Tarumanagara (Skripsi tidak dipublikasikan). [4] Andokowimbo, Sri Whisnu., 2012, “Perancangan Aplikasi Penjadwalan Matakuliah untuk Fakultas Teknologi Informasi Universitas Tarumanagara dengan Metode Vertex Colouring Heuristic”, Program Studi Teknik Informatika Fakultas Teknologi Informasi Universitas Tarumanagara (Skripsi tidak dipublikasikan). [5] Astuti, Ayu Windy., 2012, “Perancangan Aplikasi Penjadwalan Mata Kuliah pada Fakultas Teknologi Infomasi Universitas Tarumanagara dengan Metode Hybrid Particle Swarm Optimization dan Constraint Based Reasoning”, Program Studi Teknik Informatika Fakultas Teknologi Informasi Universitas Tarumanagara (Skripsi tidak dipublikasikan). [6] Yohanes, Benny., 2012, “Perancangan Aplikasi Penjadwalan Ujian pada Fakultas Teknologi Informasi Universitas Tarumangara dengan Menggunakan Algoritma Particle Swarm Optimization”, Program Studi Teknik Informatika Fakultas Teknologi Informasi Universitas Tarumanagara (Skripsi tidak dipublikasikan). [7] Irene, Ho Sheau Fen., Deris, Safaai., and Hasiml, Siti Zaiton Mohd., June 2009, “Incorporating Of ConstraintBased Reasoning Into Particle Swarm Optimization For University Timetabling Problem”. International Journal of Computer Science Letters, Vol. 1, Johor-Malaysia. [8] Kazarlis, Spyros., 2005, “Solving University Timetabling Problems Using Advanced Genetic Algorithms”, SerresGreece. [9] Bondy, J.A. and Murty, U.S.R., 1982, “Graph Theory with Applications”, Elsevier Science Publishing Co., Inc., Cambridge City. [10] Leighton, Frank Thomson., November-December 1979, “A Graph Coloring Algorithm for Large Scheduling Problems”, JOURNAL OF RESEARCH of the National Bureau of Standards, Vol. 84, No. 6, Washington DC. [11] P., Engelbrecht A., 2005, “Fundamentals of Computational Swarm Intelligence”, Wiley, West Susex. [12] Tuegeh, Maickel., Soeprijanto., dan Purnomo, Mauridhi H., Juni 2009, “Modified Improved Particle Swarm Optimization for Optimal Generator Scheduling”, Seminar Nasional Aplikasi Teknologi Informasi 2009 (SNATI 2009), Yogyakarta. [13] Santoso, Budi., 2009, “Tutorial Particle Swarm Optimization”, Surabaya. [14] Wati, Dwi Ana Ratna., 2011, “Sistem Kendali Cerdas”, Bandung. [15] M., Clerc., J., Kennedy., 2011, “The Particle Swarm Explosion, Stability, and Convergence in a Multidimensional Complex Space”, IEEE Transaction on Evolutionary Computation, New Jersey. [16] Deris, Safaai., Omatu, Sigeru., and Ohta, Hiroshi., Agustus 2000, “Timetable Planning using the Constraintbased Reasoning”, Computer & Operations Research, Vol. 27, No. 9, Johor-Malaysia.

5. Kesimpulan Berdasarkan hasil pengujian yang telah dilakukan pada program aplikasi penjadwalan perkuliahan dan ujian yang dirancang, dapat ditarik kesimpulan: 1. Penggabungan metode Vertex Graph Colouring, Particle Swarm Optimization, dan Great Deluge Algorithm untuk penjadwalan perkuliahan dan ujian memerlukan waktu proses yang lama. 2. Dari hasil pengujian yang dilakukan, program aplikasi yang dirancang dapat menghasilkan jadwal perkuliahan yang tidak melanggar hard-constraint apabila tidak terdapat preferensi khusus yang berbentrokan tetapi masih terdapat rata-rata 13% kelas matakuliah yang melanggar soft-constraints antar kelas matakuliah dan 6% kelas matakuliah yang melanggar soft-constraints berupa nilai preferensi ruang dan slot yang buruk. Pelanggaran softconstraints tersebut dikarenakan adanya preferensi khusus yang harus dipenuhi. Hasil ini lebih baik dari rancangan penjadwalan perkuliahan yang sudah dibuat sebelumnya karena sudah dapat memenuhi preferensi waktu atau ruang khusus. 3. Dari hasil pengujian yang dilakukan, program aplikasi penjadwalan perkuliahan dan ujian ini dapat menghasilkan jadwal ujian yang layak dan optimal pada FTI Untar. Tidak terdapat jadwal ujian yang melanggar hard-constraint maupun soft-constraint antar matakuliah. Hanya terdapat rata-rata 1% ujian yang melanggar soft-constraint akibat nilai preferensi ruang yang kurang baik. Hasil ini lebih baik dari rancangan aplikasi penjadwalan ujian yang sudah dibuat sebelumnya. 4. Secara keseluruhan program telah berjalan dengan baik dan mudah pengunaannya. Hal ini disimpulkan melalui tahap pengujian. Selain itu praktikum dan perkuliahan yang dilaksanakan di laboratorium sudah dapat dijadwalkan. Saran-saran untuk pengembangan aplikasi penjadwalan perkuliahan dan ujian berikutnya adalah: 1. Kelemahan pada program yaitu waktu proses yang agak lama akibat jumlah iterasi yang banyak untuk penjadwalan perkuliahan dapat diatasi pada pengembangan aplikasi selanjutnya. 2. Constraint yang digunakan dalam penjadwalan dapat diubah sesuai kebutuhan, sehingga program aplikasi dapat digunakan di tempat lain tanpa perlu mengubah source code program.

103


[17] Legierski, Wojciech., 2002, “Constraint-Based Reasoning for Timetabling”, Gliwice. [18] St¨utzle, Thomas G., 1998, “Local Search Algorithms for Combinatorial Problems – Analysis, Improvements, and New Applications”, Darmstadt. [19] Dueck, G., 1993, “New Optimization Heuristics. The Great Deluge Algorithm and the Record-to-Record Travel”, Journal of Computational Physics, Vol. 104, Issue 1, Boston. [20] AL-Milli, Nabeel R., April 2010, “Hybrid Genetic Algorithms with Great Deluge For Course Timetabling”, IJCSNS International Journal of Computer Science and Network Security. Vol. 10, No. 4, Zarqa. Redhl, Timothy Anton., 2004, “A Study of University Timetabling that Blends Graph Coloring with the Satisfaction of Various Essential and Preferential Conditions”, Houston.

Josselyn Sinthia Thio, merupakan mahasiswi program sarjana S1, program studi Teknik Informatika, Fakultas Teknologi Informasi Universitas Tarumanagara. Lely Hiryanto, memperoleh gelar S.T. dari program studi Teknik Informatika, Fakultas Teknik Universitas Tarumanagara tahun 2001. Kemudian tahun 2006 memperoleh gelar M.Sc. dari Department of Computing, Curtin University of Technology, Australia. Saat ini sebagai Staf Pengajar program studi Teknik Informatika, Fakultas Teknologi Informasi Universitas Tarumanagara

104

Josselyn Sinthia Thio 1) Lely Hiryanto 2)

Recommend Documents