IMPLEMENTASI ALGORITMA WELCH-POWELL DALAM

Download Penelitian ini bertujuan untuk mendapatkan sebuah teknik agar pembuatan jadwal ujian akhir semester dapat dilakukan secara cepat dan akurat...
1 downloads 662 Views 350KB Size
Download PDF
Love PNG Images
IMPLEMENTASI ALGORITMA WELCH-POWELL DALAM PEMBUATAN JADWAL UJIAN AKHIR SEMESTER Pasnur Jurusan Sistem Informasi, STMIK AKBA, Makassar Email : [email protected] Abstrak Pembuatan jadwal ujian akhir semester merupakan salah satu kegiatan rutin yang memerlukan konsentrasi tinggi agar tidak terjadi jadwal bersamaan untuk dua atau lebih mata kuliah yang diikuti oleh seorang mahasiswa. Penelitian ini bertujuan untuk mendapatkan sebuah teknik agar pembuatan jadwal ujian akhir semester dapat dilakukan secara cepat dan akurat. Teknik yang diterapkan adalah menggunakan algoritma Welch-Powell yang merupakan salah satu algoritma dalam metode pewarnaan graf dan diimplementasikan dengan menggunakan pemrograman PHP Hypertext Preprocessor. Algoritma ini akan mencari sebuah bilangan kromatik yang menunjukkan jumlah jadwal ujian minimal yang harus diselenggarakan serta daftar mata kuliah yang boleh memiliki jadwal ujian yang bersamaan. Hasil penelitian menunjukkan bahwa algoritma Welch-Powell yang diimplementasikan dengan pemrograman PHP Hypertext Preprocessor mampu memberikan solusi pembuatan jadwal ujian akhir semester secara cepat dan akurat. Kata kunci : algoritma welch-powell, penjadwalan, pewarnaan graf 1. Pendahuluan 1.1 Latar Belakang Masalah Setiap hari manusia memiliki berbagai aktivitas yang harus diselesaikan dalam alokasi waktu tertentu. Kegiatankegiatan tersebut memerlukan penjadwalan yang efektif agar mampu memanfaatkan semua sumber daya yang dimiliki secara optimal dan memberikan hasil yang maksimal. Pembuatan jadwal ujian akhir semester merupakan contoh sebuah penjadwalan yang harus dilakukan oleh sebuah perguruan tinggi menjelang berakhirnya masa satu semester. Jadwal tersebut memetakan berbagai komponen penjadwalan ke dalam matriks ruang dan waktu. Hasil akhir dari penjadwalan tersebut adalah sebuah informasi kepada

seluruh sivitas akademika terkait tentang pelaksanaan ujian akhir semester setiap mata kuliah. Dalam pelaksanaan akademik perguruan tinggi yang menerapkan sistem kredit semester, setiap mahasiswa memiliki kebebesan tertentu untuk menentukan sendri mata kuliah yang akan diikutinya pada masa semester tertentu. Kebebasan memilihi ini menimbulkan ketidakseragaman perkuliahan antar mahasiswa, walaupun mereka memiliki masa studi yang sama. Hal tersebut akan berdampak pada pembuatan jadwal perkuliahan dan jadwal ujian akhir semester. Pembuatan kedua jenis jadwal tersebut sering kali terasa sangat rumit dan kompleks bahkan harus diulang beberapa kali karena adanya jadwal yang bersamaan.

35

Kegagalan-kegagalan dalam pembuatan jadwal ujian akhir semester tentunya akan memakai sumber daya yang lebih besar, sehingga diperlukan sebuah solusi untuk melakukan penjadwalan secara cepat dan akurat. Solusi tersebut dapat dilakukan dengan menerapkan algoritma Welch-Powell dan diimplementasikan dalam salah satu pemrograman web yaitu PHP Hypertext Preprocessor. Algoritma Welch-Powell efektif digunakan dalam persoalan pewarnaan graf, seperti penjadwalan, serta memiliki tingkat kerumitan algoritma yang rendah. Sedangkan penggunaan pemrograman PHP Hypertext Preprocessor dalam mengimplementasikan algoritma tersebut karena pada umumnya sistem informasi akademik yang merupakan sistem terintegrasi dalam hal administrasi akademik pada sebuah perguruan tinggi dikembangkan secara berbasis web. Penggunaan pemrograman PHP Hypertext Preprocessor memudahkan aplikasi untuk mengambil data terkait dalam proses pembuatan jadwal ujian akhir semester, seperti data mahasiswa, data mata kuliah, dan data pengambilan mata kuliah. 1.2 Perumusan Masalah Perumusan masalah dalam penelitian ini adalah : a. Menentukan nilai bilangan kromatik yang menunjukkan jumlah jadwal ujian akhir semester minimal yang harus dilaksanakan tanpa menimbulkan munculnya jadwal bersamaan dua atau lebih mata kuliah yang diikuti oleh seorang mahasiswa. b. Menentukan nama-nama mata kuliah yang boleh memiliki jadwal ujian akhir semester yang bersamaan.

c.

Mengimplementasikan algoritma Welch-Powell ke dalam bahasa pemrograman PHP Hypertext Preprocessor untuk pembuatan jadwal ujian akhir semester secara cepat.

1.3 Tujuan Penelitian Tujuan dari penelitian ini adalah untuk menghasilkan sebuah fitur pembuatan jadwal ujian akhir semester yang dilakukan dengan mengimplementasikan algoritma WelchPowell dalam bahasa pemrograman PHP Hypertext Preprocessor. Fitur tersebut nantinya dapat diintegrasikan ke dalam sistem informasi manajemen akademik perguruan tinggi yang telah ada dan diharapkan mampu menghasilkan jadwal ujian akhir semester secara cepat dan akurat. 1.4 Metode Penelitian Penelitian ini dilakukan dengan menggabungkan metode kepustakaan dari berbagai sumber rujukan terkait, serta metode perancangan dan implementasi sistem pembuatan jadwal ujian akhir semester. Metode kepustakaan dilakukan dengan mengumpulkan berbagai teori terkait dengan algoritma Welch-Powell serta persoalan penjadwalan secara umum. Perancangan sistem dilakukan dengan membuat diagram alir implementasi algoritma Welch-Powell dalam pembuatan jadwal ujian akhir semester, dan implementasinya dengan menerjemahkan diagram alir tersebut ke dalam bahasa pemrograman PHP Hypertext Preprocessor.

36

2. Tinjauan Pustaka 2.1 Teori Graf Teori graf merupakan sebuah topik dasar dalam dalam matematika diskrit dan ilmu komputer. Teori ini sudah berusia tua namun memiliki banyak terapan sampai saat ini. Graf digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antar objek-objek tersebut. Representase visual dari sebuah graf adalah dengan menyatakan objek dengan sebuah noktah, bulatan, atau titik, sedangkan hubungan antar objek dinyatakan dengan garis. Sebuah graf G didefenisikan sebagai pasangan himpunan (V,E), ditulis dengan notasi G=(V,E), yang dalam hal ini V adalah himpunan tidak kosong dari simpul-simpul (vertices atau node) dan E adalah himpunan sisi (edges atau arcs) yang menghubungkan sepasang simpul.Setiap simpul v dalam sebuah graf memiliki derajat (degree) yang disimbolkan dengan d(v). Derajat tersebut menunjukkan jumlah garis yang berhubungan dengan simpul v, di mana sebuah loop dihitung dua kali. Gambar 1 berikut memperlihatkan sebuah contoh skema jaringan komputer, sedangkan gambar 2 di bawahnya merupakan representase gambar 1 dalam bentuk graf.

Gambar 1 : Contoh sebuah skema jaringan komputer

Gambar 2 : Representase gambar 1 dalam bentuk graf 2.2 Pewarnaan Graf Pewarnaan graf (graph coloring) merupakan salah satu topik menarik yang ada dalam teori graf. Pewarnaan graf dapat berupa pewarnaan simpul, pewarnaan sisi, dan pewarnaan wilayah.Pewarnaan graf bukan sekedar memberikan warna yang berbeda, tetapi juga untuk meminimalkan jumlah warna yang digunakan. 2.2.1 Pewarnaan Simpul Pewarnaan simpul pada sebuah graf adalah memberi warna pada setiap simpul graf sedemikian, sehingga setiap dua simpul bertetangga mempunyai warna yang berbeda. Sebuah pewarnaan yang menggunakan beberapa buah warna biasanya disebut dengan n-coloring. Ukuran terkecil banyaknya warna yang dapat diberikan kepada sebuah grag G disebut dengan bilangan kromatik dan dilambangkan dengan χ(G). Beberapa graf tertentu dapat langsung diketahui jumlah bilangan kromatiknya. Graf kosong memiliki χ(G) sebanyak 1 karena semua simpul tidak terhubung, sehingga untuk mewarnai semua simpul graf tersebut cukup dengan 37

satu warna saja. Graf lengkap memiliki χ(G) = n, karena semua simpul saling terhubung satu sama lai, sehingga untuk mewarnai semua simpul graf tersebut diperlukan n buah warna. 2.2.2 Pewarnaan Sisi Pewarnaan sisi sebuah graf berarti cara pemberian warna pada garis sedemikian sehingga setiap garis yang bertumpuan pada titik yang sama memiliki warna yang berbeda. 2.2.3 Pewarnaan Wilayah Pewarnaan wilayah adalah pemberian warna pada setiap wilayah pada graf, sehingga tidak ada wilayah bersebelahan yang memiliki warna yang sama. Teknik pewarnaan wilayah sangat cocok diterapkan pada kasus pemberian warna pada sebuah peta wilayah. Pada kasus tersebut, peta wilayah harus diberikan warna sedemikian, sehingga wilayah yang berbatasan langsung tidak memiliki warna yang sama. 2.3 Algoritma Welch-Powell Pada graf-graf tertentu, proses pewarnaan dapat dilakukan secara cepat dan mudah, misalnya untuk kasus graf lengkap dan graf lingkaran. Namun pada kenyataannya graf seringkali dijumpai dalam bentuk yang tidak teratur. Pada kondisi tersebut sangat dibutuhkan algoritma tertentu untuk menyelesaikan masalah pewarnaannya. Algoritma WelchPowell merupakan salah satu algoritma yang dapat dimanfaatkan untuk menyelesaikan kasus pewarnaan graf secara mangkus.

Algoritma Welch-Powell dapat digunakan dengan mengikuti langkahlangkah berikut : a. Urutkan simpul-simpul dari G dalam derajat yang menurun. Urutan yang didapatkan mungkin saja tidak bersifat unik karena adanya beberapa simpul yang memiliki derajat yang sama. b. Gunakan sebuah warna untuk mewarnai simpul pertama yang memiliki derajat paling tinggi, dan simpul-simpul lain (dalam urutan yang terurut) yang tidak bertetangga dengan simpul pertama tersebut. c. Mulai lagi dengan memberikan warna kedua pada simpul dengan derajat tertinggi berikutnya di dalam daftar terurut dan belum diwarnai. d. Ulangi pemberian warna berbeda pada simpul-simpul berikutnya hingga semua simpul telah diwarnai. Sebuah graf diperlihatkan seperti pada gambar 3 berikut in, terdiri atas 6 simpul yang diberi nama simpul A, B, C, D, E, dan F. Graf tersebut akan diberikan pewarnaan mengikuti algoritma WelchPowell.

Gambar 3 : Contoh sebuah graf Langkah pertama : mengurutkan simpul dalam derajat yang menurun, didapatkan hasil dengan urutan B (derajat 4), E

38

(derajat 4), A (derajat 3), C (derajat 3), D (derajat 2), dan F (derajat 2). Langkah kedua : berikan warna (misalnya merah) untuk simpul dengan derajat tertinggi, dalam hal ini adalah simpul B (gambar 4).

Selanjutnya berikan warna yang sama (warna kuning) kepada simpul-simpul lain yang tidak bertetangga dengan simpul A, dalam hal ini simpul D dan F (gambar 7).

Gambar 4 : Pewarnaan simpul pertama dengan derajat tertinggi.

Gambar 7 : Pewarnaan simpul lain yang tidak bertetangga dengan simpul A

Selanjutnya berikan warna yang sama kepada simpul-simpul lain yang tidak bertetangga dengan simpul B, dalam hal ini simpul E (gambar 5).

Langkah keempat : mulai lagi pewarnaan dengan warna yang berbeda (misalnya hijau) pada simpul yang belum diwarnai dengan derajat tertinggi, dalam hal ini adalah simpul C dan merupakan simpul terakhir yang belum diwarnai (gambar 8).

Gambar 5 : Pewarnaan simpul lain yang tidak bertetangga dengan simpul B Gambar 8 : Pewarnaan simpul terakhir Langkah ketiga : mulai lagi pewarnaan dengan warna yang berbeda (misalnya kuning) pada simpul yang belum diwarnai dengan derajat tertinggi, dalam hal ini adalah simpul A (gambar 6).

Gambar 6 : Pewarnaan simpul selanjutnya dengan derajat tertinggi

Berdasarkan proses pewarnaan sebelumnya, dapat diketahui bahwa untuk melakukan pewarnaan graf seperti yang ditunjukkan pada gambar 3, diperlukan minimal 3 warna. Jumlah tersebut disebut juga sebagai bilangan kromatik. 2.4 Penjadwalan Ujian Akhir Semester Kegiatan penjadwalan ujian akhir semester yang didlakukan setiap kali menjelang berakhirnya masa satu semester merupakan sebuah proses pemetaan

39

komponen penjadawalan ke dalam matriks ruang dan waktu. Komponen penjadwalan yang utama akan meliputi mahasiswa, mata kuliah, ruangan, dan data pengambilan mata kuliah oleh mahasiswa. Pada penelitian ini, proses penjadwalan akan akan melibatkan database akademik yang biasanya terdapat pada sistem informasi manajemen akademik di perguruan tinggi. Proses penjadwalan membutuhkan data dari tiga buah tabel, yaitu tabel mahasiswa, tabel mata kuliah, dan tabel perkuliahan, seperti ditunjukkan pada gambar relasi berikut ini.

3. Perancangan Sistem Dalam perancangan sistem, digunakan sebuah flowchart yang memperlihatkan alur pembuatan jadwal yang disesuaikan dengan algoritma WelchPowell (gambar 10). Tahap pertama yang akan dilakukan oleh sistem adalah membuka

Gambar 9 : Tabel dan relasinya yang dibutuhkan dalam penjadwalan ujian akhir semester Banyak sistem informasi manajemen akademik yang dipergunakan di perguruan tinggi dibangun secara berbasis web. Hal tersebut biasanya dilakukan dengan alasan berbagai kelebihan aplikasi berbasis web dibandingkan dengan aplikasi berbasis desktop. Salah satu bahasa pemrograman yang populer penggunaannya dalam pengembangan aplikasi berbasis web adalah PHP Hypertext Preprocessor atau biasa disingkat saja menjadi PHP. Pada penelitian ini, sistem penjadwalan ujian akhir semester yang akan dibangun juga menggunakan PHP.

40

koneksi ke server database MySQL. Apabila koneksi berhasil dilakukan, maka sistem akan membersihkan tabel temporary 1 yang berisi data daftar mata kuliah secara berpasangan yang memiliki keterhubungan (terdapat minimal seorang mahasiswa yang memprogramkan secara bersamaan kedua mata kuliah tersebut), serta tabel temporary 2 yang berisi data daftar simpul mata kuliah beserta derajat dan status pewarnaannya. Pada tahap selanjutnya program akan membuat dua buah array, masing-masing berisi daftar mahasiswa aktif (mahasiswa yang mengikuti perkuliahan minimal satu mata kuliah) dan daftar mata kuliah aktif (mata kuliah yang memiliki minimal satu peserta). Mata kuliah akan dianggap sebagai simpul dan akan diatur derajatnya masing-masing dengan angka 0. Selanjutnya program akan melakukan perhitungan derajat setiap simpul mata kuliah dilanjutkan dengan pengisian data pada tabel temporary 1 dan temporary 2. Untuk mulai proses pewarnaan graf, program akan memulai pengurutan simpul mata kuliah berdasarkan derajat tertinggi. Simpul mata kuliah dengan derajat tertinggi akan diberikan warna, dan dilanjutkan dengan pewarnaan simpul mata kuliah lain yang tidak bertetangga dengan simpul mata kuliah sebelumnya. Proses ini akan dilakukan secara berulang hingga semua simpul mata kuliah telah diwarnai. Pada tahap terakhir, program akan menampilkan daftar mata kuliah yang boleh memiliki jadwal ujian bersamaan dan program akan berakhir dengan penutupan koneksi database.

4. Hasil dan Pembahasan Pada pengujian program, digunakan database percobaan yang terdiri atas tiga buah tabel, yaitu tabel mahasiswa, tabel mata kuliah, dan tabel pengujian. Data yang terdapat pada masing-masing tabel disederhanakan seperti pada tabeltabel berikut ini. Tabel 1 : Data mahasiswa NIM Nama Mahasiswa 20112205001 Andi 20112205002 Budi 20112205003 Wati 20112205004 Fadil 20112205005 Fatma Tabel 2 : Data mata kuliah Kode Nama Mata Kuliah MK-1 Kecerdasan Buatan MK-2 Sistem Basis Data MK-3 Matematika Diskrit MK-4 Pemrograman Web MK-5 Statistika MK-6 Pemodelan dan Simulasi MK-7 Keamanan Komputer Tabel 3 : Data perkuliahan Nama Nama Mata Kuliah Mahasiswa Andi Kecerdasan Buatan Andi Sistem Basis Data Budi Matematika Diskrit Budi Pemrograman Web Wati Kecerdasan Buatan Wati Sistem Basis Data Wati Pemodelan dan Simulasi Fadil Kecerdasan Buatan Fadil Pemrograman Web Fatma Pemrograman Web Pada saat maka program

program akan

dijalankan, melakukan

41

serangkaian proses seperti yang telah digambarkan pada gambar 10 tentang flowchart sistem. Setelah program menyelesaikan proses persiapan, maka program akan membuat daftar mata kuliah aktif sebagai simpul dan diurutkan berdasarkan derajat tertinggi. Gambar 11 berikut memperlihatkan graf simpul mata kuliah sebelum proses iterasi dimulai.

Gambar 12 : Pewarnaan simpul MK-1 sebagai simpul berderajat tertinggi. Selanjutnya program juga akan memberikan warna yang sama kepada simpul mata kuliah yang tidak bertetangga (tidak berhubungan langsung) dengan simpul MK-1, dalam hal ini adalah simpul MK-3 (gambar 13).

Gambar 11 : Kondisi graf sebelum proses iterasi dimulai Pada gambar 11 diketahui daftar simpul mata kuliah yang diurutkan berdasarkan derajat tertinggi, seperti pada tabel 4 berikut ini. Tabel 4 : Daftar simpul mata kuliah sebelum proses iterasi yang diurutkan berdasarkan derajat tertinggi Simpul Derajat MK-1 3 MK-2 2 MK-3 1 MK-4 2 MK-6 2 Pada proses iterasi pertama, program akan memberikan warna kepada simpul MK-1 sebagai simpul berderajat tertinggi (gambar 12).

Gambar 13 : Pewarnaan simpul MK-3 dengan warna yang sama dengan simpul MK-1. Pada iterasi kedua, program akan mengurutkan kembali simpul mata kuliah yang belum diwarnai berdasarkan derajat tertinggi. Pada iterasi ini, didapatkan bahwa simpul MK-2 merupakan simpul berderajat tertinggi. Program akan memberikan warna yang kedua terhadap simpul MK-2 (gambar 14).

42

berderajat tertinggi pada proses iterasi yang ketiga.

Gambar 14 : Pewarnaan simpul MK-2 dengan warna yang kedua sebagai simpul berderajat tertinggi pada proses iterasi yang kedua. Program juga akan memberikan warna yang sama dengan simpul mata kuliah lain yang tidak bertetangga dengan simpul MK2, dalam hal ini adalah simpul MK-4 (gambar 15).

Proses pewarnaan graf akan selesai jika semua simpul mata kuliah telah diberikan warna. Simpul-simpul yang memiliki warna yang sama merupakan mata kuliah yang boleh memiliki jadwal ujian akhir semester yang bersamaan. Mata kuliah yang boleh memiliki jadwal ujian akhir bersamaan, yaitu MK-1 dengan MK3, serta MK-2 dengan MK-4. Mata kuliah MK-6 memiliki jadwal tersendiri. Jumlah warna yang dipakai menunjukkan jumlah jadwal minimum yang harsu dilaksanakan, dalam hal ini berjumlah 3 (tiga). Pada saat program diakses melalui web browser, maka akan tampil informasi jadwal ujian akhir semester seperti pada gambar 17 berikut ini.

Gambar 15 : Pewarnaan simpul MK-4 dengan warna yang sama dengan simpul MK-2. Pada iterasi yang ketiga, ternyata masih terdapat satu simpul mata kuliah yang belum diwarnai, dalam hal ini adalah simpul MK-6. Simpul tersebut akan diberikan warna yang ketiga (gambar 16).

Gambar 16 : Pewarnaan simpul MK-6 dengan warna yang ketiga sebagai simpul

Gambar 17 : Tampilkan hasil eksekusi program melalui web browser.

43

Pada gambar 17 di atas terlihat informasi mengenai jadwal ujian akhir semester untuk kasus data yang diteliti. Jadwal tersebut terdiri atas jadwal pertama yang menyelenggarakan ujian untuk mata kuliah MK-1 dan MK-3, jadwal kedua yang menyelenggarakan ujian MK-2 dan MK-4, serta jadwal ketiga yang menyelengarakan ujian MK-6. Hasil tersebut sejalan dengan proses pewarnaan graf secara konvensional. 5. Kesimpulan Berdasarkan hasil penelitian yang telah dilakukan, didapatkan kesimpulan sebagai berikut : a. Algoritma Welch-Powell mampu menentukan bilangan kromatik yang menunjukkan jumlah jadwal ujian akhir semester yang harus dilaksanakan tanpa terjadi jadwal yang bersamaan pada dua atau lebih mata kuliah yang diikuti oleh seorang mahasiswa. b. Algoritma Welch-Powell mampu menampilkan informasi namanama mata kuliah yang boleh memiliki jadwal ujian akhir semester yang bersamaan. c. Pemrograman PHP Hypertext Preprocessor memiliki kemampuan untuk mengimplementasikan algoritma Welch-Powell dalam pembuatan jadwal ujian akhir semester.

Daftar Pustaka [1] Babin, Lee, PHP-5 Recipes : A Problem Solution Approach, Apress, 2005 [2] Munir, Rinaldi, Matematika Diskrit, Penerbit Informatika, Bandung, 2010 [3] Siang, Jong Jek, Matematika Diskrit dan Aplikasinya Dalam Ilmu Komputer, Penerbit Andi, Yogyakarta, 2009 [4] Stein, Clifford, Discrete Mathemathics for Computer Scientists, Addison-Wesley, 2011 [5] Wibisono, Samuel, Matematika Diskrit, Graha Ilmu, Yogyakarta, 2008

44