ANALISIS PENYELESAIAN MASALAH PENJADWALAN KULIAH MENGGUNAKAN TEKNIK PEWARNAAN GRAPH DENGAN ALGORITMA KOLONI LEBAH Heni Rachmawati 1,2 I Ketut Edy Purnama 1 Mauridhi Hery Purnomo1 Bidang Keahlian Telematika, Jurusan Teknik Elektro, Institut Teknologi Sepuluh Nopember Surabaya 1 Program Studi Sistem Informasi, Jurusan Komputer, Politeknik Caltex Riau 2
Abstrak--- Pewarnaan graph sudah menjadi teknik yang umum digunakan dalam penyelesaian masalah penjadwalan. Umumnya dalam penjadwalan kuliah proses pemasangan ruangan dilakukan setelah graph selesai diwarnai (dengan artian telah diperoleh periode waktu setiap kuliah). Makalah ini membahas teknik pewarnaan graph alternatif penjadwalan kuliah. Pada teknik ini proses pemasangan ruangan dilakukan bersamaan dengan proses konstruksi dan pewarnaan graph itu sendiri. Algoritma pewarnaan graph yang kompleks seringkali membutuhkan biaya yang besar. Metaheuristik untuk optimisasi menawarkan solusi cukup baik untuk menyelesaikan masalah ini. Salah satu algoritma metahuristik yaitu koloni lebah digunakan dalam makalah ini untuk fungsi pewarnaan graph. Hasil menunjukkan lebah mampu menyelesaikan pewarnaan graph dengan baik. Kata kunci--- Penjadwalan kuliah, pewarnaan graph, koloni lebah
I. PENDAHULUAN
P
embuatan
jadwal
adalah
sebuah
masalah
periodik yang selalu dihadapi oleh sekolah dan universitas. Dengan banyaknya faktor yang mempengaruhi penyusunan suatu jadwal seperti jumlah ruangan, daya tampung ruangan, dan slot waktu yang sedikit menjadikan penyusunan jadwal perkuliahan lebih rumit. Dasar permasalahan penyusunan jadwal kuliah di universitas adalah bagaimana menempatkan perkuliahan pada slot waktu terbatas pada ruangan kuliah yang sesuai untuk pertemuan tersebut dan mahasiswa bisa menghadiri semua perkuliahan yang diikutinya. Namun umumnya sebuah jadwal muncul lebih dahulu sebelum mahasiswa memilih perkuliahan yang akan diikutinya, sehingga kecendrungan bahwa mahasiswa-lah yang menyesuaikan diri dengan jadwal. Meski demikian ada beberapa ketentuan penjadwalan yang mendasar dalam membangun sebuah jadwal yang layak, ketentuan
ini bersifat harus dipenuhi agar penjadwalan bisa diterima. Ketentuan yang harus dipenuhi itu adalah Dua atau lebih perkuliahan yang diampu oleh dosen yang sama tidak bisa dijadwalkan pada slot waktu yang sama [1, diantaranya] Dua atau lebih perkuliahan yang membutuhkan ruangan yang sama tidak bisa dijadwalkan pada slot waktu yang sama [1,diantaranya] Ketentuan lain yang bersifat tambahan merupakan ketentuan yang tidak wajib dipenuhi untuk membangun sebuah jadwal yang layak namun akan lebih diterima oleh mahasiswa dan anggota akademik jika dapat dipenuhi. Ketentuan tambahan seringnya sangat beralasan Beberapa contoh dari ketentuan tambahan adalah : Beberapa dosen mungkin ingin memilih jadwal mangajar pada waktu-waktu tertentu saja Beberapa dosen mungkin ingin memilih ruangan tertentu untuk perkuliahannya Beberapa perkuliahan semestinya hanya diselenggarakan pada pagi dan siang saja (tidak waktu malam) [2] Beberapa perkuliahan yang diselenggarakan lebih dari sekali dalam seminggu mungkin ingin dalam jarak hari tertentu Meminimalisasi penggunaan ruangan dalam pembangunan jadwal [2] Permasalahan penjadwalan dapat dimodelkan dan diselesaikan dengan teknik pewarnaan graph [3],[4]. Masalah pewarnaan graph dikenal dengan Optimasi Kombinatorial. Selain untuk penjadwalan, pewarnaan graph juga digunakan dalam aplikasi pemasangan frekuensi pada jaringan selular [5], pemasangan kru karyawan [6]. Model konvensional pewarnaan graph untuk penjadwalan, vertex merepresentasikan kuliah yang akan dijadwalkan, edge merepresentasikan pasangan kuliah yang bisa menimbulkan konflik (tidak bisa dijadwalkan pada waktu yang sama), dan warna pada vertex merepresentasikan periode waktu kapan kuliah tersebut dijadwalkan [7]. Jika terdapat dua vertex dan yang terhubung oleh sebuah edge , maka kedua vertex harus diwarnai dengan warna yang berbeda. Jumlah minimum warna yang dibutuhkan untuk mewarnai sebuah graph disebut angka
kromatik dari atau dinotasikan dengan ( ). Untuk memecahkan pewarnaan graph ada dua kelas algoritma yaitu eksak dan perkiraan. Algoritma eksak digunakan untuk memecahkan masalah dalam ukuran kecil, sementara algoritma perkiraan sering digunakan untuk mencari solusi mendekati optimal dengan biaya komputasi yang lebih rendah. Kebanyakan algoritma perkiraan untuk menyelesaikan pewarnaan graph menggunakan implementasi metaheuristik seperti Simulated Annealing, Pencarian Tabu, Algoritma Genetika dan Optimasi Koloni Semut[8], dan lain-lain Dalam makalah ini digunakan algoritma berdasarkan prilaku lebah (Bee Colony) seperti pada [9] . Hasil komputasi menunjukkan bahwa dalam penyelesaian contoh test dari DIMACS, algoritma lebah memberikan hasil yang lebih baik dari MMGC [6].
II. TEKNIK PEWARNAAN GRAPH KONFLIK Pada penjadwalan universitas dengan model pewarnaan graph konvensional, pemasangan ruangan untuk perkuliahan dilakukan setelah graph konflik dibangun dan diwarnai. Pertanyannya adalah, apakah mungkin jika pemasangan ruangan dilakukan selama pembangun graph konflik dan proses mewarnai berlangsung daripada setelah kedua proses tersebut. [10] mengembangkan sebuah model matematika dan komputasi dengan pendekatan konvensional untuk memecahkan masalah penjadwalan universitas mengunakan teknik pewarnaan graph alternatif. Model yang ditawarkan membangun sebuah graph konflik dari data inputan perkuliahan tetapi jika pada pendekatan konvensioanl satu matakuliah direpesentasikan dengan satu vertex, pada model yang ditawarkan satu matakuliah direpresentasikan dengan sekumpulan vertex sekaligus untuk mewakilkan proses pemasangan ruangan. Metode [10] mengkonstruksi graph konflik alternatif, kemudian mewarnainya dengan algoritma greedy untuk kemudian ditransformasikan menjadi jadwal bebas konflik. Faraji [2] menggunakan pendekatan algortima lebah untuk memecahkan np-problem pada pewarnaan graph, hasilnya terlihat bahwa koloni lebah memberikan hasil lebih baik pada sisi kecepatan komputasi dari pada koloni semut. Setelah graph diwarnai ditransformasikan menjadi sebuah jadwal kuliah yang bebas konflik.
A. Konstruksi Graph Konflik Perkulihan Cara alternatif yang digunakan disini adalah merepresentasikan sebuah matakuliah dengan sekumpulan vertex, dimana setiap vertex pada sebuah kumpulan merepresentasikan ruangan yang mungkin untuk perkuliahan matakuliah tersebut. Misalkan terdapat sebuah himpunan terdiri dari
matakuliah { , , … , } yang akan dijadwalkan, dan terdapat sebuah himpunan yang terdiri dari m ruang { , , … , } tempat perkuliahan dapat dipasangkan. Misalkan dari ruangan tersebut terdapat subset { , , , , } sebagai contoh, tempat dimana perkuliahan matakuliah bisa dipasangkan, berdasarkan beberapa faktor (misalnya kapasitas ruangan, tipe ruangan yang diminta dosen pengampu). Sekarang dapat digambarkan matakuliah dalam graph konflik perkuliahan dengan lima vertex { , , , , }, dimana satu vertex merepresentasikan satu kemungkinan pemasangan ruangan untuk perkulihaan matakuliah . Pada peristiwa sesungguhnya nanti hanya satu ruangan misal yang akan digunakan untuk perkulihaan matakuliah , dimana akan direpresentasikan oleh vertex . Kemudian dapat ditambahkan edge dengan cara berikut : Misalkan terdapat dua kuliah yang bisa menimbulkan konflik yaitu dan . Edge yang harus ditambahkan antara vertex dan pada graph altenatif akan menjadi sebuah subgraph bipartie lengkap terdiri dari sekumpulan vertex yang berhubungan dengan kuliah dan . Sebagai contoh, jika kuliah dan terdiri dari kumpulan vertex { , , , , } dan { , , , }, maka vertex , , , dan menjadi himpunan bagian pertama sedangkan vertex , , , menjadi himpuan bagian kedua.
Gambar 2. Kuliah
dan dijadwalkan pada slot waktu yang berbeda
Dengan kata lain jika kuliah dan tidak menimbulkan konflik (sehingga mereka bisa atau tidak mesti dipasangkan dalam slot waktu yang sama), maka dalam pewarnaan graph penjadwalan konvensional mungkin tidak perlu menambahkan edge diantara vertex dan . Pada graph konflik alternatif tetap ditambahkan edge diantara dua kumpulan vertex yang memiliki ruangan yang sama dan . Jika kuliah dan memiliki kemungkinan pemasangan ruangan yang sama, maka ditambahkan edge antara kumpulan vertek milik kuliah dan kumpulan vertek milik kuliah . Sebagai contoh, jika kuliah dan terdiri dari kumpulan vertex { , , , , } dan
{ , , , }, maka akan ditambahkan edge diantara dan , dan , dan . Maka jika kuliah dan dijadwalkan pada slot waktu yang sama mereka tidak dapat menggunakan ruangan yang sama, seperti gambar 3.
Gambar 5. Kuliah dan dipasang pada ruangan yang sama dan slot waktu yang berbeda
Gambar 3. Kuliah
dan mungkin dipasang pada slot waktu yang sama
B. Mewarnai Graph Konflik Perkuliahan Sebuah graph dengan pewarnaan vertex yang tepat akan mewarnai sepasang vertex yang terhubung oleh edge dengan warna yang berbeda. Pasangan vertex yang tidak terhubung oleh edge bisa menggunakan dua warna yang sama atau berbeda. Dalam proses pewarnaan, graph alternatif menggunakan prosedur yang sama dengan graph konvensional, tetapi dengan satu pengecualian bahwa hanya satu vertex dalam sebuah kumpulan yang akan diwarnai, dengan kata lain setiap kuliah yang dipasang dalam salah satu ruang saja yang diberikan warna. Seperti dalam graph konvensional setiap warna dalam graph konflik yang telah melewati proses pewarnaan melambangkan slot waktu yang berbeda. Dalam graph konflik alternatif, sebuah vertex yang telah diwarnai mengimplikasikan bahwa kuliah telah dipasang pada ruangan dan dijadwalkan pada sebuah slot waktu tertentu. Seperti yang diperlihatkan oleh gambar berikut :
Gambar 5 memperlihatkan bahwa kuliah dan harus dijadwalkan pada slot waktu yang berbeda. Vertex diwarnai dengan warna 1 dan vertex diwarnai dengan warna 2, mengimplikasikan bahwa kuliah dan dijadwalkan pada slot waktu yang berbeda dan ruangan yang sama yaitu
Gambar 6. Kuliah dan tidak berpotensi menimbulkan konflik, dipasang pada ruangan yang berbeda dan slot waktu yang berbeda
Gambar 6 memperlihatkan bahwa kuliah c dan c tidak menimbulkan konflik, sehingga bisa dijadwalkan pada slot waktu yang sama atau berbeda. Vertex diwarnai dengan 1 dan vertex diwarnai dengan 2, mengimplikasikan bahwa kuliah dan dijadwalkan pada slot waktu yang berbeda menggunakan ruangan yang berbeda
Gambar 4. Kuliah dan dipasang pada ruangan yang berbeda dan slot waktu yang berbeda
Gambar 4 memperlihatkan bahwa kuliah dan harus dijadwalkan pada slot waktu yang berbeda. Vertex diwarnai dengan warna 1 dan vertex diwarnai dengan warna 2, mengimplikasikan bahwa kuliah dan dijadwalkan pada slot waktu yang berbeda dan ruangan yang berbeda.
Gambar 7. Kuliah dan tidak berpotensi menimbulkan konflik, dipasang pada ruangan yang berbeda dan slot waktu yang sama
Gambar 7 memperlihatkan bahwa kuliah c dan c tidak menimbulkan konflik, sehingga bisa dijadwalkan pada slot waktu yang sama atau
berbeda. Vertex diwarnai dengan 1 dan vertex diwarnai dengan 2, mengimplikasikan bahwa kuliah dan dijadwalkan pada slot waktu yang sama menggunakan ruangan yang berbeda
3.
4. 5.
Gambar 8. Kuliah dan tidak berpotensi menimbulkan konflik, dipasang pada ruangan yang sama dan slot waktu yang berbeda
Gambar 8 memperlihatkan bahwa kuliah c dan c tidak menimbulkan konflik, sehingga bisa dijadwalkan pada slot waktu yang sama atau berbeda. Vertex diwarnai dengan 1 dan vertex diwarnai dengan 2, mengimplikasikan bahwa kuliah dan dijadwalkan pada slot waktu yang sama menggunakan ruangan yang sama.
C. Algoritma Koloni Lebah Ada dua jenis lebah yang digunakan dalam algoritma ini yaitu, lebah pramuka dal lebah pekerja. Lebah pramuka : lebah yang melakukan pencarian awal dalam wilayah pencarian, menggunakan deduksi mereka sendiri. Lebah pekerja : lebah yang menemukan hasil yang lebih baik dibandingkan dengan temanya disebut lebah pekerja. Hanya lebah-lebah ini yang akan melakukan tarian kibasan, sehingga jumlah lebah pekerja sesuai dengan kapasitas area tarian. Selain memberikan informasi jalur pencarian mereka pada saat menari, mereka juga berusaha mencari jalur yang lebih baik disekitar jalur mereka sendiri. Awalnya lebah pramuka disebar untuk melakukan pencarian solusi primer, lalu kualitas dari solusi yang mereka bawa akan dievaluasi. Beberapa lebah pramuka yang memberikan solusi yang lebih baik akan dikonversi menjadi lebah pekerja (disesuaikan dengan kapasitas ruang tarian). Para lebah pekerja tersebut lalu melakukan tarian kibasan untuk membagi informasi tentang jalur solusi yang mereka bawa dengan lebah pekerja yang lain. Setiap lebah akan mengingat informasi lebah-lebah yang lain. Berikut pseudocode dari algoritma yang digunakan : 1. Sebar lebah pramuka untuk membuat solusi primer 2. Evaluasi bobot solusi setiap lebah pramuka, kemudian pilih lebah pramuka yang
memberikan solusi lebih baik untuk dikonversi menjadi lebah pekerja While (kriteria berhenti belum ditemukan) : Para lebah pekerja terpilih akan melakukan tarian kibasan dan berbagi informasi dan saling mengingat informasi setiap lebah pekerja yang lain. Pencarian lingkungan Update informasi
Berikut fungsi pewarnaan yang digunakan untuk solusi primer : Jika derajat vertex adalah deg ( ) = dan vertex yang terhubung dengan vertex adalah { , , … , } dan himpunan warna dari vertex yang terhubung dengan vertex adalah = { ( ), ( ), … , ( )} maka : ( ) = 1 ∄ ℎ ( )= ;
III.
RANCANGAN SISTEM
Perancangan struktur penyelesaian masalah dilakukan dengan pendeskripsian masalah dan batasanbatasan dalam formula teknik pewarnaan graph untuk penjadwalan dan merancang teknik pencarian solusi dengan algoritma koloni lebah.. Berikut tahap-tahap pengerjaan dari penelitian ini Data Perkuliahan
Pengkodean Graph Kuliah Konflik dari besaran-besaran masalah penjadwalan kuliah
Pewarnaan Graph Kuliah Konflik dengan Algoritma Koloni Lebah menjadi Graph Kuliah Bebas Konflik
Transformasi Graph Kuliah Bebas Konflik menjadi Jadwal
Jadwal Kuliah
Gambar 9.Tahap-tahap pengerjaan sistem penjadwalan
IMPLEMENTASI DAN ANALISIS HASIL Sistem dibangun dengan bahasa pemrograman java menggunakan platform Netbeans 8.9 dan database MySQL 5.5. Sistem akan diujicobakan dengan pembangunan jadwal untuk Jurusan Teknik Elektro Institut Teknologi Sepuluh Nopember, Surabaya. Pada jurusan Teknik Elektro terdapat lebih dari seratus kuliah yang diselenggarakan dalam satu semester, dengan jumlah ruangan perkuliahan... IV. KESIMPULAN DAFTAR PUSTAKA [1] M. Trick. Network resources for coloring a graph.http://mat.gsia.cmu.edu/COLOR/color.ht ml [2] E.K. Burke, D.G. Elliman, and R. Weare. A genetic algorithm based university timetabling system. In Proceedings of the 2nd East-West International Conference on Computer Technologies in Educa-tion, volumeI, pages 3540, 1995. [3] K.A. Dowsland dan J.M.Thompson, Ant Colony Optimization for the Examination Schedulling Problem, Journal of the Operational Research Society, 56(2005), 426-438 [4] F.T.Leighton, A Graph Coloring Algorithm for Large Schedulling Problems, Journal of Research of The National Bureau of Standards, 84(1979),489-506 [5] A. Gamst, Some Lower Bounds for a Class of Frequency Assignment Problem, IEEE Transaction of Vehicular Technology, 35 (1999), 8-14 [6] A. Lim dan F. Wang, Metaheuristic for Robust Graph Coloring Problem, Proc. Of the 16th IEEE International Conference on Tools with Artificial Intelligence (ICTAI 2004), 2004 [7] D. de Werra. An introduction to timetabling. European Journal of Operational Research, 19(2):151–162, February 1985. [8] E.Salari dan K.Eshagi, An ACO Algorithm for the Graph Coloring Problem. International Journal of Contempory Mathematical Science, 3 (2008) [9] Faraji Majid dan Seyyed Javadi Haj, Proposing a New Algorithm Based on Bees Behaviour for Solving Graph Coloring. International Journal Contemp.Math.Sciences, Vol 6, 2011, no.1,4149 [10] T.A. Redl. A Study of University Timetabling that Blends Graph Coloring with the Satisfaction of Various Essential and Preferential Conditions, Ph.D. Thesis, Department of Computational and Applied
Mathematics, Rice University, May 2004, 159 pages.
