IMPLEMENTASI MASALAH PEWARNAAN GRAPH DENGAN ALGORITMA TABU SEARCH PADA PENJADWALAN KULIAH Ida Suryani 1, Purwanto 2 , Mohamad Yasin 3 Universitas Negeri Malang E-mail:
[email protected];
[email protected];
[email protected] ABSTRAK: Pewarnaan titik adalah mewarnai semua titik pada graph 𝐺, sehingga setiap pasang titik yang terhubung langsung memiliki warna yang berbeda. Banyaknya warna minimum yang digunakan untuk mewarnai disebut dengan bilangan khromatik. Pewarnaan titik dapat digunakan untuk membantu menyelesaikan masalah penyusunan jadwal kuliah. Salah satu algoritma untuk menyelesaikan masalah pewarnaan graph pada penjadwalan kuliah adalah algoritma tabu search. Hasil pewarnaan graph dengan menggunakan algoritma tabu search digunakan untuk menyusun jadwal kuliah, sehingga tidak ada jadwal yang bentrok artinya tidak ada dua matakuliah yang diambil oleh seorang mahasiswa yang dilaksanakan pada waktu yang bersamaan. Dengan demikian dapat ditentukan waktu dan ruang untuk melaksanakan perkuliahan sehingga dapat dibuat jadwal kuliah. Untuk mempermudah menyelesaikan permasalahan tersebut maka dibuat program dengan Borland Delphi 7. Data yang diinputkan berupa mata kuliah, dosen dan kelas mahasiswa yang akan representasikan sebagai titik graph. Proses pewarnaan dimulai dari 𝑘 = 1 sehingga diperoleh warna yang lebih minimum. Output yang dihasilkan program berupa tabel jadwal kuliah yang telah ditentukan waktu dan ruang. Kata Kunci: pewarnaan titik graph, bilangan khromatik, algoritma tabu search, penjadwalan kuliah
Dalam kehidupan sehari-hari banyak permasalahan yang memerlukan penyelesaian. Sering dengan bantuan matematika permasalahan tersebut menjadi lebih mudah dipahami dan lebih mudah diselesaikan. Teori graph merupakan salah satu cabang matematika yang mempunyai banyak manfaat karena teoriteorinya dapat diterapkan dalam kehidupan sehari-hari. Salah satu sub bahasan dalam teori graph yang dapat diterapkan dalam kehidupan nyata adalah pewarnaan graph. Salah satu masalah yang dapat diselesaikan dengan pewarnaan graph adalah proses penjadwalan kuliah. Beker (1974) mengemukakan “penjadwalan merupakan kegiatan untuk mengalokasikan sejumlah sumber daya yang tersedia untuk memastikan bahwa perencanaan dapat berjalan dengan baik dengan waktu dan tenaga yang digunakan secara efisien”. Penjadwalan kuliah yang sederhana yaitu menjadwalkan beberapa komponen yang terdiri dari mata kuliah, dosen, dan kelas mahasiswa dengan memperhatikan sejumlah batasan dan syarat tertentu. Menurut Aladag dan Hocaoglu (2007: 56) salah satu algoritma untuk menyelesaikan masalah pewarnaan graph pada penjadwalan kuliah adalah algoritma tabu search. Algoritma tabu search merupakan suatu metode optimasi yang berbasis pada pencarian solusi tetangga dan memori lokal. Proses pencarian bergerak dari satu solusi ke solusi berikutnya berusaha mencari solusi tetangga yang lebih baik dari solusi saat ini. Selain itu, memori lokal digunakan untuk mencatat langkah-langkah pencarian yg pernah ditemui. Jika langkah pencarian tersebut pernah ditemui tidak lebih baik (tabu), maka algoritma tabu search akan mengabaikan langkah pencarian tersebut tetapi langkah itu akan digunakan untuk
1. Ida Suryani adalah mahasiswa jurusan Matematika FMIPA Universitas Negeri Malang 2. Purwanto adalah dosen jurusan Matematika FMIPA Universitas Negeri Malang 3. Mohamad Yasin adalah dosen jurusan Matematika FMIPA Universitas Negeri Malang
menuntun dalam pencarian selanjutnya (Berlianty dan Arifin, 2010: 199). Definisi mengenai graph dan pewarnaan graph merujuk pada Wilson dan Watkins (1990). PEMBAHASAN Algoritma Tabu Search untuk Penyelesaian Masalah Pewarnaan Graph Langkah-langkah penyelesaian metode pewarnaan graph dengan menggunakan algortima tabu search pada penjadwalan kuliah adalah sebagai berikut (Aladag dan Hocaoglu, 2007: 53): 1. Warnai titik secara acak. 2. Menentukan apakah solusi awal memenuhi kriteria solusi yang diharapkan. 3. Jika terjadi konflik (ada titik yang bertetangga) maka bangkitkan solusi baru dari solusi yang didapat dengan melakukan move (pemindahan warna). 4. Simpan solusi yang tidak tabu dalam tabu list dan abaikan solusi yang tabu. 5. Pilih solusi optimal dari tabu list. 6. Terapkan solusi optimal pada graph. 7. Jika masih ada konflik maka kembali ke langkah 3, tetapi jika tidak ada konflik maka selesai. Sebelum menyelesaikan menyelesaikan masalah pewarnaan graph pada penjadwalan kuliah dengan menggunakan algoritma tabu search yang harus dilakukan adalah identifikasi permasalahan dan konversi data ke bentuk graph. Setiap kombinasi mata kuliah, dosen, kelas (offering) mahasiswa dimodelkan dengan sebuah titik pada graph tersebut kemudian dua matakuliah yang diajar oleh dosen yang sama dan setiap matakuliah yang diikuti oleh setidaknya satu kelas yang sama akan memiliki hubungan yang direpresentasikan dalam bentuk sisi yang menghubungkan dua titik yang mewakili dua mata kuliah tersebut. Urutan dari proses pewarnaan graph dengan algoritma tabu search sebagai berikut: a. Warnai titik secara acak. Sebelum mewarnai titik secara acak terlebih dahulu ditentukan bilangan khromatik. Perwarnaan dimulai dari 𝑘 = 1 sampai batas atas bilangan kromatik 𝑘 = 4 warna yang berbeda sampai ditemukan solusi optimal. Dalam perhitungan manual dengan menggunakan Algoritma Tabu Search untuk mencari pewarnaan titik tidak dimulai dari 𝑘 = 1, misalkan diambil 𝑘 = 4 karena merupakan batas bawah dari bilangan khromatik. b. Menentukan apakah solusi awal memenuhi kriteria solusi yang diharapkan. Dari hasil pewarnaan graph dapat dihitung jumlah konflik pewarnaan dengan menghitung jumlah titik bertetangga yang mewakili warna yang sama. Dengan demikian dapat dilihat hasil pewarnaannya apakah menimbulkan konflik. c. Jika terjadi konflik (ada titik yang bertetangga) maka bangkitkan solusi baru dari solusi yang didapat dengan melakukan move (pemindahan warna). Jika hasil pewarnaannya apakah menimbulkan konflik.berarti harus dilakukan pembangkitan solusi baru untuk mengurangi jumlah konflik yang terjadi dengan melakukan move (pemindahan warna). Jika tidak terjadi konflik maka solusi tersebut merupakan solusi optimal.
d. Simpan solusi yang tidak tabu dalam tabu list dan abaikan solusi yang tabu. Solusi-solusi yang tidak tabu atau solusi tersebut belum pernah ditemui dan lebih baik, maka Algoritma tabu search akan mengabaikan langkah pencarian tersebut tetapi langkah itu akan digunakan untuk menuntun dalam pencarian selanjutnya. e. Pilih solusi optimal dari tabu list. Solusi optimal merupakan kondisi dimana konflik yang didapat sama dengan 0 (nol) atau solusi yang tidak mempunyai konflik. f. Terapkan solusi optimal pada graph. Setelah solusi optimal dipilih maka solusi tersebut akan diterapkan pada graph sehingga graph dapat diwarnai sesuai soilusi optimal yang telah ditremukan. g. Jika masih ada konflik maka kembali ke langkah 3, tetapi jika tidak ada konflik maka selesai. Jika masih ada konflik yaitu kondisi dimana titik pada graph yang mempunyai warna sama dihubungkan dengan sisi (bertetangga) maka lakukan pengulangan kembali ke Langkah c. Tetapi jika sudah tidak ada konflik artinya titik pada graph yang mempunyai warna sama tidak dihubungkan dengan sisi (bertetangga), maka langkah pewarnaan graph dengan algoritma tabu search selesai. Dari hasil pewarnaan graph dengan Algoritma Tabu Search titik-titik yang sama dikelompokkan berdasarkan warnanya. Bila dua titik memiliki warna yang sama, maka waktu kuliah dua mata kuliah yang diwakili oleh titik-titik tersebut dapat berlangsung secara bersamaan dan jika memiliki warna yang berbeda maka waktu kuliah dua mata kuliah tersebut tidak boleh bersamaan. Untuk menentukan ruang mana yang akan ditempati oleh kombinasi antara mata kuliah, kelas mahasiswa, dosen dan waktu kuliah adalah bila ada dua titik memiliki warna yang sama dari hasil pewarnaan titik, maka dua mata kuliah yang diwakili oleh titiktitik tersebut harus ditempatkan di ruang yang berbeda dan jika memiliki warna yang berbeda maka boleh ditempatkan di ruang yang sama karena waktu pelaksanaan kuliahnya berbeda tetapi harus memperhatikan ruangan yang sesuai dengan kebutuhan perkuliahan yang ada. Untuk mempermudah dalam menyelesaikan masalah pewarnaan graph pada penjadwalan kuliah dengan menggunakan algoritma tabu search maka dibuat program dengan menggunakan software Borland Delphi 7, berikut adalah gambar flowchart untuk setiap langkah-langkah yang akan dilakukan dalam proses konversi data ke dalam bentuk graph, proses pewarnaan graph dan proses pembuatan jadwal kuliah:
Mulai Mulai
Pemetaan dosen, mata kuliah, Pemetaan dosen, mata kuliah, dan kelasdan (offering) kelasmahasiswa (offering)secara mahasiswaberurutan secara berurutan
Buat titik Buat titik
Sudah Sudah dipetakan dipetakan semua semua
Tidak
Ya
Kombionasikan titiksecara secara Kombionasikan 22titik berurutan berurutan
Bertetangga Bertetangga
Tidak
Ya Ya
Buat sisi Buat sisi
Selesai Selesai
Flowchart Konversi Data ke Bentuk Graph
Mulai
Warnai titik secara acak
Ya
Memenuhi kriteria Tidak Bangkitkan solusi baru
Tabu Ya Tidak Tambahkan dalam Tabu List
Tidak
Solusi optimal tercapai Ya Terapkan solusi optimal pada graph
Ada konflik Ya Tidak Selesai
Flowchart Pewarnaan Graph
Mulai
Titik dikelompokkan berdasarkan warna
Ganti titik dengan matakuliah yang diwakili
Warna yang sama petakan ke
Tambahkan matakuliah ke waktu yang tidak terjadi konflik
waktu yang sama
Petakan ke ruang yang berbeda
Buat waktu baru Ya Ya
Sudah dipetakan semua
Tidak Terjadi konflik dengan matakuliah di waktu lain
Ya
Jadwal kuliah Selidiki matakuliah-matakuliah yang belum dipetakan Selesai
Flowchart Pembuatan Jadwal Kuliah
Tidak
Uji Coba Program Akan dilakukan uji terhadap program yang telah dibuat. Daftar kuliah pada tabel di bawah ini terdiri dari 8 mata kuliah, 6 orang dosen, 2 kelas dan 2 ruangan yang tersedia. Tiap mata kuliah diajarkan oleh 1 orang dosen pada sebuah ruangan tertentu yang direpresentasikan ke dalam titik graph. No
Mata Kuliah
Dosen
Kelas
Mata Kuliah (titik graph)
1 2 3 4 5 6 7 8
MK1 MK2 MK3 MK4 MK5 MK6 MK7 MK8
D1 D5 D2 D6 D3 D4 D4 D6
K1 K2 K1 K2 K1 K2 K1 K2
0 1 2 3 4 5 6 7
Maka dapat dibuat model graph sebagai berikut:
Diselesaikan menggunakan algoritma tabu search dengan bilangan kromatik 𝑘 = 4 karena merupakan batas bawah dari bilangan khromatik. Batas bawah bilangan khromatik adalah mencari graph bagian komplit terbesar di 𝐺. Sehingga diperoleh hasil pewarnaan seperti di bawah ini:
Dari gambar di atas terlihat bahwa graph dapat diwarnai minimun dengan 4 warna yaitu titik 7 dan 6 diberi warna 1, titik dan 4 diberi warna 2, titik 2 dan 3 diberi warna 3, titik 0 dan 5 diberi warna 4. Setelah itu membuat jadwal kuliah dengan ketentuan titik-titik yang warnanya sama dipetakan ke waktu kuliah yang sama dan titik-titik yang warnanya sama dipetakan ke ruang kuliah yang berbeda. Sehingga diperoleh jadwal kuliah senagai berikut:
No 1 2 3 4 5 6 7 8
Waktu hari Senin Senin Senin Senin Selasa Selasa Selasa Selasa
jam 1-3 1-3 4-6 4-6 1-3 1-3 4-6 4-6
Mata Kuliah MK7 MK8 MK2 MK5 MK3 MK4 MK1 MK6
Dosen
Kelas
Ruang
D4 D6 D5 D3 D2 D6 D1 D4
K1 K2 K2 K1 K1 K2 K1 K2
R1 R2 R1 R2 R1 R2 R1 R2
PENUTUP Kesimpulan 1. Sebelum menyelesaikan masalah graph yang harus dilakukan adalah konversi data ke bentunk graph. Setelah itu menentukan bilangan khromatik untuk mengetahui banyak warna pada solusi awal. Kemudian menyelesaikan masalah pewarnaan graph dengan algoritma tabu search. 2. Dari hasil pewarnan graph dengan algoritma tabu search titik-titik dikelompokkan berdasarkan warnanya dan akan dibuat jadwal kuliah dengan ketentuan titik-titik yang warnanya sama dipetakan ke waktu kuliah yang sama dan titik-titik yang warnanya sama dipetakan ke ruang kuliah yang berbeda. 3. Untuk mempermudah menyelesaikan masalah pewarnaan graph dengan algoritma tabu search pada penjadwalan kuliah maka dibuat program dengan memanfaatkan sofware Borland Delphi 7. Data yang diinputkan berupa mata kuliah, dosen dan kelas mahasiswa yang akan representasikan sebagai titik graph. Proses pewarnaan dimulai dari 𝑘 = 1 sehingga diperoleh warna yang lebih minimum. Output yang dihasilkan program berupa tabel jadwal kuliah yang telah ditentukan waktu dan ruang. Saran 1.
2.
3.
Untuk menyelesaikan masalah pewarnaan graph selain dengan menggunakan algoritma tabu search masih banyak algoritma lainnya yang dapat dikembangkan diantaranya adalah algoritma sequential color, algoritma genetika, algoritma mememtika dan algoritma koloni lebah. Contoh permasalahan lain yang dapat diselesaikan dengan pewarnaan titik graph adalah pemberian frekuensi radio pada setiap stasiun radio, penentuan jadwal operasi kereta api dan menyelesaikan permainan sudoku. Implementasi program yang telah dibuat selain menggunakan software Borland Delphi 7, program bisa dikembangakan menggunakan software Java dan Microsoft Visual Basic.
Daftar Rujukan Aladag, C.H and Hocaoglu, G. 2007. A Tabu Search Algoritm To Solve A Course Timetabling Problem. Hacettepe Journal of Mathematics and Satistics, Ankara, Turkey, (Online), 36(1): 53-64, (http://clonalg-monografia. googlecode.com/hg/ documentos/A%20Tabu%20Search%20algorithm %20to%20solve%20a%20course%20Timetabling%20problem.pdf), diakses tanggal 10 Januari 2013. Berlianty, I dan Arifin, M. 2010. Teknik-teknik Optimasi Heuristik. Yogyakarta: Graha Ilmu. Glover, F and Laguna, M. 1997. Tabu Search. Boston: Kluwer Academic Publishers. R. Baker, Kenneth. 1974. Introduction To Squencing and Scedulling. New York: John Wiley and Son’s Inc Wilson, R.J and Watkins, J.J. 1990. Graphs an Introductory Approach a First Discrete Mathematics. Canada: John Willy And Sons, Inc.
