ANALISA DAN IMPLEMENTASI ALGORITMA PRIORITY DISPATCHING DALAM PENJADWALAN PEMBAGIAN RUANGAN UJIAN

Volume : II, Nomor : 1, Pebruari 2014

Majalah Ilmiah

Informasi dan Teknologi Ilmiah (INTI) ISSN : 2339-210X

ANALISA DAN IMPLEMENTASI ALGORITMA PRIORITY DISPATCHING DALAM PENJADWALAN PEMBAGIAN RUANGAN UJIAN DEDI MASYOYO (1111976) Mahasiswa Program Studi Teknik Informatika, STMIK Budidarma Medan Jl. Sisingamangaraja No.338 Simpang Limun Medan www.stmik-budidarma.ac.id // [email protected] ABSTRAK Di dalam teori graph, graph adalah kumpulan titik yang mungkin terhubung maupun tidak terhubung dengan titik lainnya dengan garis. Tidak penting seberapa besar titik itu, atau seberapa panjang garisnya, atau apakah garis itu lurus atau melengkung dan titik itupun tidak harus bulat. Intinya adalah bahwa titik-titik itu terhubung oleh garis. Masalah pertama dalam mempelajari teori graph yaitu terdapat begitu banyak definisi. Semuanya sesuai untuk gagasan intuitif, tetapi dapat disarikan dengan seketika. Algoritma Algoritma Priority Dispatching dapat digunakan untuk mewarnai sebuah graph G secara efisien. Algoritma ini tidak selalu memberikan jumlah warna minimum yang diperlukan untuk mewarnai G, namun algoritma ini cukup praktis untuk digunakan dalam pewarnaan simpul sebuah graph. Algoritma Algoritma Priority Dispatching hanya cocok digunakan untuk graph dengan orde yang kecil. Oleh karena itu algoritma Kata Kunci : Graph, Priority Dispatching

1. PENDAHULUAN 1.1 Latar Belakang Masalah Penjadwalan ruang ujian merupakan pekerjaan rutin dalam sistem Akademik Sekolah Menengah Atas yang dilakukan setiap akhir semester. Seringkali jadwal yang telah dikeluarkan belum benar sehingga membutuhkan adanya penjadwalan ruang ujian ulang. Sesuai dengan penelitian pada suatu Sekolah, Pelaksanaan jadwal ruangan ujian masih menggunakan cara yang kurang optimal, dimana setiap siswa yang akan mengikuti ujian harus meminta atau pun melihat setiap jadwal yang dibuat oleh pihak sekolah. Hal ini mengakibatkan ujian bisa berjalan tidak efektif karena harus melakukan penyesuaian jadwal dengan keadaan real setelah jadwal dikeluarkan. Dalam melakukan penjadwalan ujian ini, diperlukan pemikiran yang cukup rumit untuk dapat memetakan sejumlah komponen penjadwalan (Mata Pelajaran, Pengawas, Siswa, ruang, dan waktu) ke dalam timeslot (matriks ruangan dan waktu) dengan mempertimbangkan semua batasan yang ada. Proses manual memerlukan waktu yang cukup lama untuk dapat melakukan hal ini dan memungkinkan terjadinya pelanggaran constraint akibat human error Penjadwalan merupakan alokasi dari sumber daya terhadap waktu untuk menghasilkan sebuah kumpulan pekerjaan. Penjadwalan ini dibutuhkan untuk mendapatkan hasil yang lebih teratur dengan pengalokasian sumber daya yang tepat, seperti jumlah peserta yang akan mengikuti ujian. Dengan pengaturan penjadwalan yang efektif dan efisien, Sekolah akan dapat memenuhi penjadwalan yang

tepat pada due date serta kualitas yang telah ditentukan. Supaya Siswa-siswi yang akan mengikuti Ujian tersebut dapat mengambil setiap jadwal ujiannya sesuai dengan jadwal yang telah ditentukan oleh pihak sekolah. Maka setiap Siswa yang akan mengikuti Ujian tersebut lebih mudah di tentukan setiap ruangan ujiannya dengan adanya metode ini. Algoritma yang digunakan dalam menentukan warna pada penjadwalan ruang ujian, yaitu algoritma Priority Dispatching . keuntungan dari algoritma Priority Dispatching adalah efisien. Algoritma Priority Dispatching adalah merupakan salah satu algoritma pewarnaan graph yang melakukan pewarnaan berdasarkan derajat tertinggi dari simpul-simpulnya atau disebut Largest Degree Ordering (LDO). Metode yang digunakan algoritma ini adalah dengan pewarnaan langsung pada sebuah graph dengan warna yang sedikit mungkin. Namun Algoritma Priority Dispatching ini tidak selalu memberikan jumlah warna minimum yang diperlukan untuk mewarnai. 1.2 Perumusan Masalah Memperhatikan latar belakang diatas maka penulis menetapkan rumusan masalah sebagai berikut : 1. Bagaimana cara mengimplementasikan Algoritma Priority Dispatching dalam mempermudah pembuatan penjadwalan ruangan Ujian Siswa? 2. Bagaimana merancang sistem penjadwalan ruangan ujian nasional ?

Analisa Dan Implementasi Algoritma Priority Dispatching Dalam Penjadwalan Pembagian Ruangan Ujian. Oleh : Dedi Masyoyo

16


Majalah Ilmiah

Informasi dan Teknologi Ilmiah (INTI) ISSN : 2339-210X 1.3

Batasan Masalah Agar pembahasan lebih terarah, maka penulis memberikan batasan-batasan pembahasan masalah yaitu : 1. Graph Colouring yang akan diimplementasikan yaitu hanya pada bagian verteks colouring. 2. Jumlah warna yang dipakai dalam graph sebaiknya digunakan sedikit mungkin. Dan banyak verteks yang digunakan adalah 6 verteks. 3. Data yang dipakai adalah penjadwalan ruangan Ujian . Perancangan sistem yang dilakukan tidak sampai kepada perancangan sistem online.

dekat dalam teori graph, dahulu merupakan masalah yang cukup rumit hingga pada akhirnya dipecahkan oleh Leonhard Euler, Matematikawan dari Swiss (1707-1783) tahun 1736.[Narsingh Deo,1980] Kőnigsberg adalah sebuah kota di sebelah timur Prussia (Jerman sekarang) dimana terdapat Sungai Pregel (Pregolya sekarang) dan merupakan tempat tinggal duke of Prussia pada abad ke-16 (tahun 1736). Kota tersebut saat ini bernama Kaliningrad dan merupakan pusat ekonomi dan industri utama di Rusia Barat. Sungai Pregel membagi kota menjadi empat daratan dengan mengalir mengitari pulau Kneiphof lalu bercabang menjadi dua buah anak sungai, seperti tampak pada gambar 3.1 berikut ini :

1.4 Tujuan dan Manfaat Penelitian 1.4.1 Adapun tujuan dari penelitian ini adalah : 1. Mengimplementasikan graph colouring dalam mempermudah pembuatan penjadwalan ruangan Ujian Siswa. 2. Merancang sistem penjadwalan Ujian Nasional dengan metode Algorithma priority dispatching . 1.4.2 Adapun manfaat penelitian ini adalah : 1. Memudahkan proses pembuatan jadwal ruangan ujian pada SMA YAPIM . 2. Menghemat waktu dan biaya yang biasanya diperlukan untuk menyelesaikan permasalahan penjadwalan ujian . 2. Landasan Teori 2.1. Teori Dasar Graph Rinaldi Munir Edisi Ketiga (2005:353) Teori dasar Graph merupakan pokok bahasan yang sudah tua usianya namun memiliki banyak terapan dalam kehidupan sehari-hari sampai saat ini. Graph adalah suatu diagram yang memuat informasi tertentu jika diinterpretasikan secara tepat. Dalam kehidupan sehari-hari, graph digunakan untuk menggambarkan berbagai macam struktur yang ada. Tujuannya adalah sebagai visualisasi objek-objek agar lebih mudah dimengerti. Teori Graph merupakan cabang ilmu matematika diskrit yang banyak penerapannya dalam berbagai bidang ilmu seperti engineering, fisika, biologi, kimia, arsitektur, transportasi, teknologi komputer, ekonomi, sosial dan bidang lainnya. Teori Graph juga dapat diaplikasikan untuk menyelesaikan persoalan-persoalan, seperti Travelling Salesperson Problem, Chinese Postman Problem, Shorest Path, Electrical Network Problems, Seating Problem serta Graph Coloring. 2.2. Sejarah Teori Graph Masalah jembatan Kőnigsberg (Kőnigsberg Bridge Problem) bisa menjadi contoh yang paling

Gambar1 Jembatan Kőnigsberg Sumber : (Rinaldi Munir, Matematika Diskrit Edisi Ketiga, 2000) 2.3. Definisi Graph Rinaldi Munir Edisi Ketiga (2005:356) Suatu linier graph atau sederhana G = (V,E) terdiri atas himpunan benda V = {v1, v2, . . .} disebut vertex, dan himpunan E = {e1, e2, . . . }, yang elemen-elemennya disebut edge sehingga setiap edge ek diidentifikasikan dengan pasangan tak berurut vertex (vi, vj). Di dalam teori graph, graph adalah kumpulan titik yang mungkin terhubung maupun tidak terhubung dengan titik lainnya dengan garis. Tidak penting seberapa besar titik itu, atau seberapa panjang garisnya, atau apakah garis itu lurus atau melengkung dan titik itupun tidak harus bulat. Intinya adalah bahwa titik-titik itu terhubung oleh garis. Masalah pertama dalam mempelajari teori graph yaitu terdapat begitu banyak definisi. Semuanya sesuai untuk gagasan intuitif, tetapi dapat disarikan dengan seketika. Beberapa pendapat tentang graph memiliki nama jamak. Sebagai contoh, graph terkadang disebut networks, vertex terkadang disebut simpul atau nodes atau titik, dan edge terkadang disebut sisi atau arcs atau garis. Dalam


17


Majalah Ilmiah

Informasi dan Teknologi Ilmiah (INTI) ISSN : 2339-210X tulisan ini yang digunakan untuk menjelaskan simpul dan sisi yaitu vertex dan edge. Peristiwa terburuk, tidak ada yang setuju pada arti yang terdapat dalam terminologi. Sebagai contoh, dalam definisi setiap graph harus memiliki paling sedikit satu vertex. Karena itu pengarang yang lain mengizinkan graph dengan nol vertex. (Graph dengan nol vertex hanya ada satu, contoh yang tidak baik jika menjadi sebuah teorema). Secara teori, setiap penulis yang setuju sedikit banyaknya maksud dari masing-masing teorema, tetapi tidak setuju dengan kasus graph dengan nol vertex tersebut. Jadi, tidak perlu diingat jika definisi ini berbeda dengan definisi yang dilihat dimanapun. Pada umumnya perbedaan ini tidak menjadi masalah. 2.4. Terminologi dan Konsep Dasar Teori Graph Sebuah graph dibentuk dari kumpulan titik yang dihubungkan dengan garis-garis. Secara informal, graph adalah cabang dari titik, yang dihubungkan oleh garis. Contoh sebuah graph pada gambar 2:

Gambar 2 : Contoh sebuah graph Sumber : (Rinaldi Munir, Matematika Diskrit Edisi Ketiga, 2007) 2.5. Graph Planar Rinaldi Munir Edisi Ketiga (20055:392) Suatu graph G yang dapat digambarkan tanpa adanya edge-edge yang saling memotong disebut sebagai graph planar jika tidak demikian graph G disebut takplanar.

Gambar 3. Graph berarah dan tak berarah K4 Sumber : (Rinaldi Munir, Matematika Diskrit Edisi Ketiga, 2005) 2.6. Pewarnaan Graph Rinaldi Munir Edisi Ketiga (2005:425) Definisi pewarnaan graph adalah pemberian warna, yang biasanya direpresentasikan sebagai bilangan terurut mulai dari 1 atau juga dapat direpresentasikan langsung dengan menggunakan warna merah, biru, hijau, dan lain-lain pada objek tertentu pada suatu

graph. Objek tersebut dapat berupa simpul, sisi, wilayah, ataupun kombinasi ketiganya. Seperti pada gambar 2.1, setiap simpul yang berdekatan atau bertetangga tidak mempunyai warna yang sama. Dalam pewarnaan graph jumlah warna minimum yang dapat digunakan untuk mewarnai graph dinyatakan dengan bilangan kromatik, yang disimbolkan dengan χ(G), (χ adlah huruf Yunani Chi). (Graph yang memiliki bilangan kromatik 1 adalah graph kosong, yaitu graph yang hanya terdiri dari sebuah simpul. Sementara suatu graph dikatakan planar jika tidak ada dua buah titik yang saling berpotongan yaitu graph yang dapat digambarkan pada bidang datar tanpa ada sisi yang menyilang diatas sisi lainnya dimana jumlah warna yang digunakan hanya 4 warna. Masalah pewarnaan seperti itu dapat berubah menjadi sangat berguna, karena wilayah tersebut dapat dengan mudah diubah bentuknya menjadi sebuah graph. Masing-masing daerah dari wilayah itu menjadi sebuah simpul dan jika dua buah daerah berdampingan maka ke dua buah simpulnya berhubungan, kemudian hubungkan dengan sebuah sisi

Gambar 4. Pewarnaan Graph Sumber: ( Rinaldi Munir, Matematika Diskrit Edisi Ketiga,2005) Ada tiga macam persoalan pewarnaan graph (graph colouring), yaitu pewarnaan simpul, pewarnaan sisi dan pewarnaan wilayah (region). Pembahasan kali ini hanya dibatasi pada pewarnaan simpul saja. 2.7. Algoritma-Algoritma Pewarnaan Graph Dalam metode pewarnaan graph, terdapat beberapa algortma-algoritma yang telah diterapkan. Algoritma-algoritma ini telah banyak digunakan dalam pengembangan berbagai macam software penyusunan jadwal. Karena banyaknya persoalan penyusunan jadwal yang kompleks, tidak memungkinkan untuk melakukan pewarnaan graph secara manual. Semakin banyak jumlah komponenkomponen yang harus diperhitungkan dalam penyusunan sebuah jadwal, maka semakin sulit penyusunan sebuah jadwal tesebut. Berikut ini merupakan beberapa algoritma yang dapat digunakan dalam metode pewarnaan graph. 3.7.1. Algoritma Algoritma Priority Dispatching Algoritma Algoritma Priority Dispatching dapat digunakan untuk mewarnai sebuah graph G secara efisien. Algoritma ini tidak selalu memberikan jumlah warna minimum yang diperlukan untuk


18


Majalah Ilmiah

Informasi dan Teknologi Ilmiah (INTI) ISSN : 2339-210X mewarnai G, namun algoritma ini cukup praktis untuk digunakan dalam pewarnaan simpul sebuah graph. Algoritma Algoritma Priority Dispatching hanya cocok digunakan untuk graph dengan orde yang kecil. Oleh karena itu algoritma Algoritma Priority Dispatching hanya dapat menentukan batas atas warna. Langkah-langkahnya adalah sebagai berikut: Langkah 1 (melabel titik dengan derajatnya). Label titik V1, V2, ..., Vn sedemikian hingga derajat (V1) > derajat (V2) > ... > derajat (Vn). Langkah 2 (warnai titik belum berwarna pertama dari titik-titik belum berwarna yang berdekatan dengan titik itu). Berikan warna yang belum digunakan pada titik belum berwarna yang pertama pada daftar titik itu. Lakukan hal itu pada semua titik dalam daftar secara terurut, berikan warna baru ini pada setiap titik yang tidak berdekatan dengan setiap titik lain yang telah diwarnai ini. Langkah 3 (graphnya telah diwarnai?). Jika beberapa titiknya belum berwarna, maka kembalilah ke langkah 2. Langkah 4 (selesai). Pewarnaan graph telah dilakukan. Contohnya:Misalkan kita ingin mewarnai simpul graph pada gambar 5.

4.

5.

6.

7.

sama pada simpul A dan G dengan warna simpul E yaitu merah karena Simpul A dan G tidak berdampingan dengan simpul E. sehingga diperolah urutan simpul yang belum diberi warna adalah C, B, D, F, dan H. Ambil warna kedua, misalnya Biru, warnai simpul C ( karena simpul C sekarang ada diurutan pertama). Kemudian cari simpul yang tidak berdampingan dengan simpul C, beri warna yang sama (Biru). Diberikan warna yang sama pada simpul D dan H dengan warna simpul C yaitu biru karena Simpul D dan H tidak berdampingan dengan simpul C. Sehingga diperoleh urutan simpul yang belum diberi warna adalah B dan F. Mengambil warna ketiga, misalnya warna hijau. Lalu warna tersebut ditambahkan pada simpul B dan F (simpul B dan F tidak bertetangga).

Dan pada gambar 6 merupakan hasil pewarnaan graph tersebut adalah:

Gambar 6 : Graph yang telah diwarnai simpulnya dengan algoritma Algoritma Priority Dispatching Sumber : http://www.google.co.id/search?hl=id&client=firefo x-a&hs=Shj&rls=org.mozilla (07 April 2012)

2.8.

Gambar 5 : Graph yang akan diwarnai simpulnya dengan algoritma Algoritma Priority Dispatching Sumber : http://www.google.co.id/search?hl=id&client=firefo x-a&hs=Shj&rls=org.mozilla (21 April 2012) Langkah-langkah yang akan dilakukan adalah: 1. Urutkan simpul berdasarkan derajatnya dari besar ke kecil : Simpul berderajat terbesar adalah E, yaitu 5 (mempunyai 5 ruas) kemudian simpul C berderajat 4, B,D,F masing-masing berderajat 3 dan A,H,G masing-masing berderajat 2. Jadi Urutannya adalah : E,C,B,D,F,A,H,G 2. Ambil warna pertama, misalnya Merah. Beri warna Merah simpul E (karena E adalah simpul urutan pertama). 3. Kemudian cari simpul yang tidak berdampingan dengan simpul E, beri warna yang sama (merah). Diberikan warna yang

Penjadwalan Jong Jek Siang (2002:22) menyatakan bahwa jadwal didefinisikan sebagai sesuatu yang menjelaskan di mana dan kapan orang-orang dan sumber daya berada pada suatu waktu. Berdasarkan Kamus Besar Bahasa Indonesia, jadwal merupakan pembagian waktu berdasarkan rencana pengaturan urutan kerja. Jadwal juga didefinisikan sebagai daftar atau tabel kegiatan atau rencana kegiatan dengan pembagian waktu pelaksanaan yang terperinci. Sedangkan penjadwalan merupakan proses, cara, perbuatan menjadwalkan atau memasukkan dalam jadwal (Departemen Pendidikan dan Kebudayaan, 1995). Kebanyakan orang terbiasa dengan jadwal sekolah yang disajikan sebagai tabel hari dalam seminggu dan slot waktu. Dapat dilihat bahwa setiap hari dibagi ke dalam slot waktu. Setiap slot waktu memiliki daftar mata pelajaran yang sedang diajarkan, oleh siapa dan di mana. Jadwal dapat dinyatakan dalam sejumlah cara yang berbeda, masing-masing siswa harus memiliki jadwal sendiri tergantung pada mata pelajaran, begitu juga masing-


19


Majalah Ilmiah

Informasi dan Teknologi Ilmiah (INTI) ISSN : 2339-210X masing guru dan ruang, semua ini adalah perspektif yang berbeda pada jadwal yang sama. Situasi lain di mana jadwal diperlukan yaitu: 1. Manufacturing - jalur produksi, perencanaan proyek. 2. Travel- kereta api, bus, dll. 3. Ujian universitas/sekolah. 4. Mata kuliah universitas. 5. Jadwal sekolah. 6. Jadwal televisi/radio/media. 7. Pertemuan/Rapat. Situasi di atas membutuhkan jadwal dengan berbagai kerumitan tergantung pada jumlah sumber daya yang dijadwalkan, jumlah slot waktu dan lokasi. 3. ANALISA 3.1. Analisa Kebutuhan Sistem Analisa berguna untuk mengetahui kebutuhan perangkat lunak dan bagaimana aplikasi yang akan dibangun. Dalam penelitian diperlukan pengumpulan-pengumpulan sumber pengetahuan dan data yang dapat menganalisis hasil perangkat yang baik. Salah satu aplikasi penerapan pewarnaan graph dalam kehidupan sehari-hari adalah dalam penyusunan sebuah jadwal. Sebuah jadwal yang ada mula-mula dipetakan menjadi bentuk graph terlebih dahulu. Proses pewarnaan graph ini nantinya akan dilakukan pada graph yang terbentuk. Pemetaan dilakukan dengan mengasumsikan bahwa setiap jadwal adalah sebuah verteks (simpul) dan urutan jadwal atau dua jadwal yang tidak bisa diadakan bersamaan dipetakan dengan membuat edge (sisi) antara dua titik tersebut. Adapun hasil penelitian yang didapat dari sekolah yaitu: 1. Peserta Ujian Adapun jumlah peserta yang sedang mengikuti ujian nasional tersebut adalah sebanyak 160 orang, dalam setiap ruangan ada 20 orang siswa. 2. Ruangan Ujian Ruangan yang ada disekolah tersebut ada 30 ruangan, yang terdiri dari ruangan kelas 1 sampai kelas 3. 3. Materi Ujian Nasional Adapun jenis mata pelajaran yang akan diujiankan ada 6 mata pelajaran, yaitu : Bahasa Indonesia, Bahasa Inggris, Fisika, Matematika, Biologi, Kimia. 4. Waktu Waktu ujian yang dipakai setiap mata pelajaran adalah sebanyak 120 menit (2jam permata pelajaran). 5. Hari Banyaknya hari yang dipakai dalam ujian tersebut adalah selama 4 hari. yaitu: hari senin (Bahasa Indonesia), hari selasa (Bahasa Inggris dan Fisika), hari rabu (Matematika), hari kamis (Biologi dan Kimia).

3.2. Representasi Penjadwalan Kedalam Suatu Graph Perancangan merupakan penggambaran, perancangan dan pembuatan sketsa atau pengaturan yang bertujuan untuk melakukan tahap awal untuk merancang suatu sistem. Disamping itu tahap ini bertujuan untuk memenuhi kebutuhan pemakai sistem, dan juga memberikan gambaran yang jelas dan rancang bangun yang lengkap kepada pemakai pemograman komputer dan ahli teknik lainnya yang terlibat. Algoritma Priority Dispatching dapat digunakan untuk mewarnai sebuah graf G secara mangkus. Algoritma ini hanya memberikan batas atas untuk χ(G), yaitu bahwa algoritma tidak selalu memberikan jumlah warna minimum yang diperlukan untuk mewarnai. Pada Graph yang akan digambarkan dibawah ini akan ditentukan simpul-simpul tujuan sebagai berikut: 1. Pada Level yang Pertama yaitu dinyatakan sebagai hari yang diteruskan kelevel keDua. 2. Pada level keDua yaitu dinyatakan sebagai Matapelajaran yang diteruskan kelevel terakhir. 3. Pada Level keTiga yaitu dinyatakan sebagai Ruangan, dan ini merupakan Simpul Tujuan yang terakhir dari hasil semua simpul-simpulnya.

Gambar: 7 Graph yang akan diwarnai simpulnya dengan Algoritma Priority Dispatching . Gambar Graph diatas menunjukkan gambaran graph yang berbeda dengan graph-graph sebelumnya, karena pada gambar tersebut kita menggunakan lintasan yang berarah, sehingga graph yang terbentuk disebut sebagai graph berarah (directed graph). Dalam Graph berarah, kita hanya dapat bergerak dalam lintasan ke salah satu arah, tidak ke arah sebaliknya. Dalam program Graph perbedaan antara graph tidak berarah (non-direct graph) dan graph berarah adalah bahwa lintasanlintasan dalam graph berarah hanya memiliki 1 entry dalam adjancency matrix. Setiap lintasan (edge) direpresentasikan dalam adjancency matrix menggunakan nilai 1 (ada lintasan) atau 0 (tidak ada


20


Majalah Ilmiah

Informasi dan Teknologi Ilmiah (INTI) ISSN : 2339-210X lintasan). Label-label baris menunjukkan dari arah mana lintasan berawal, sedangkan label-label kolom memperlihatkan dimana mereka berakhir. Dengan demikian jika dalam graph tidak berarah separuh bagian adjancency matrix merupakan cerminan dari separuh bagian adjancency matrix lainnya, maka dalam Graph berarah, setiap sel dalam adjancency matrix memuat informasi-informasi yang unik. Dengan demikian, untuk graph berarah, metoda penambahan lintasa (edge) hanya memiliki pernyataan tunggal

pewarnaan berdasarkan derajat tertinggi dari simpulsimpulnya. Berikut Algoritmanya:

Keterangan dari Graph diatas adalah: 1. X menyatakan Siswa. 2. H menyatakan Hari (H1-H4). Dimana ada 1-4 hari melaksanakan ujian (Senin, Selasa, Rabu, Kamis) Tabel 1 : Tabel Kode Hari Ujian Nasional Kode 1 2 3 4

Nama Hari Senin Selasa Rabu Kamis

3. MP menyatakan Mata pelajaran (MP1-MP6). Dimana ada MP1-MP6 sebagai jenis Ujian (Bahasa Indonesia, Bahasa Inggris, Fisika, Matematika, Biologi, Kimia) Tabel 2 : Tabel Kode Mata Pelajaran Ujian Nasional Kode A B C D E F

Mata Pelajaran Bahasa Indonesia Bahasa Inggris Fisika Matematika Biologi Kimia

4. R menyatakan Ruangan Ujian Nasional (R1-R8). Dimana ada 8 Ruangan yang dipakai pada saat melaksanakan Ujian Nasional tersebut. 3. 3 Penerapan Algoritma PRIORITY DISPATCHING Cara yang digunakan dalam pewarnaan vertex dengan menggunakan Algoritma pewarnaan vertex, adalah: 1. Nyatakan jenis ujian sebagai vertex, dan Siswa sebagai edge. 2. Setiap vertex bertetangga harus mempunyai warna berbeda (warna setiap vertex harus berbeda). Algoritma Priority Dispatching merupakan salah satu algoritma pewarnaan graph yang melakukan

Gambar 8 : Flowchart Algoritma Priority Dispatching Persoalan yang mempunyai karakteristik seperti pewarnaan graf adalah persoalan menentukan ruangan ujian, ada 6 mata pelajaran yang akan diujian nasionalkan, (A,B,C,D,E,F) dan ujian tersebut berlangsung selama 4 hari (1,2,3,4). Maka tabel berikut akan memperlihatkan matriks 4 hari ujian pada 6 mata pelajaran. Angka 1 pada elemen(i,j) berarti hari i ujian j, sedangkan angka 0 menyatakan hari i tidak ujian j. Tabel 3 : Tabel Jadwal Ujian Nasional yang akan dilaksanakan MP

A

B

C

D

E

F

H 1 2 3 4

1 0 0 0

0 1 0 0

0 1 0 0

0 0 1 0

0 0 0 1

0 0 0 1

Ketentuan: 1. [1,1] menyatakan: Hari Senin mengadakan ujian Bahasa Indonesia. 2. [2,2];[2,3] menyatakan: Hari Selasa mengadakan Ujian Bahasa Inggris dengan Fisika. 3. [3,4] menyatakan: Hari Rabu mengadakan Ujian Matematika. 4. [4,5];[4,6] menyatakan: Hari Kamis mengadakan Ujian Biologi degan Kimia. Dari Graph gambar 4.1 teknik pewarnaannya dengan Algoritma PRIORITY DISPATCHING 21 Analisa Dan Implementasi Algoritma Priority Dispatching Dalam Penjadwalan Pembagian Ruangan Ujian. Oleh : Dedi Masyoyo


Majalah Ilmiah

Informasi dan Teknologi Ilmiah (INTI) ISSN : 2339-210X 1. Urutkan simpul-simpul dari G dalam derajat yang menurun (urutan seperti ini mungkin tidak unik karena beberapa simpul mungkin berderajat sama) 2. Gunakan satu warna untuk mewarnai simpul pertama dan simpul-simpul lain (dalam urutan yang berurut) yang tidak bertetangga dengan simpul pertama ini. 3. Mulai lagi dengan simpul derajat tertinggi berikutnya didalam daftar terurut yang belum diwarnai dan ulangi proses pewrnaan simpul dengan menggunakan warna kedua. 4. Ulangi penambahan warna-warna sampai semua simpul telah diwarnai.

oleh satu titik graf dan satu sisi merupakan bahwa pada satu hari tersebut hanya mengadakan ujian pada satu mata pelajaran, sehingga dikatakan graf tidak terhubung. 4. Implementasi Pada bab ini berisikan tentang semua proses yang terdapat di dalam system, dimana semua proses tersebut diimplementasikan ke dalam system sehingga system dapat berjalan dengan baik dan benar. Implementasi system program ini mencakup spesifikasi kebutuhan perangkat keras (hardware) dan spesifikasi perangkat lunak (software). Berikut Form-Form yang akan diimplementasikan: a. Form Menu Login

Gambar 10 : Tampilan Login Admin b. Tampilan Menu Utama

Gambar 9 : Hasil pewarnaan graph dengan menggunakan Algoritma Welch powell. Di dalam persoalan pewarnaan graf, tidak hanya sekedar mewarnai simpul-simpul dengan warna yang berbeda dari warna simpul tetangganya saja, namun juga menginginkan jumlah macam warna yang digunakan sedikit mungkin. Warna yang digunakan dalam mewarnai graf diatas hanya 4 warna saja untuk mewarnai graf tersebut. Ketentuannya adalah: 1. Pada hari pertama siswa mengikuti Ujian Nasional hanya 1 mata pelajaran. 2. Pada hari kedua siswa mengikuti Ujian Nasional 2 mata pelajaran. 3. Pada hari ketiga siswa mengikuti Ujian Nasional 1 mata pelajaran. 4. Pada hari keempat siswa mengikuti Ujian Nasional 2 mata pelajaran. Persoalan menentukan ruangan ujian semua mata pelajaran sama dengan menentukan bilangan kromatis graf. Dapat menggambarkan graf yang menyatakan penjadwalan ruangan ujian. Simpulsimpul pada graf menyatakan Mata Pelajaran. Sisi yang menghubungkan dua buah simpul menyatakan pada hari yang sama ada mata pelajaran yang diujiankan, lalu pada graf yang hanya ditentukan

c.

Gambar 11 : Tampilan Menu Utama Form Time

Gambar 12 Tampilan Menu Time d. Form Faculty


22


Majalah Ilmiah


i. e.

Gambar 17 : Tampilan Section Form Print Room Schedule

Gambar 13 : Tampilan Menu Faculty Form Room

Gambar 18 : Tampilan Menu Print Room Schedule f.

Gambar 14 : Tampilan Menu Room Form Subject

j.

Form Day

k.

Gambar 19: Tampilan Menu Day Form Faculty Schedule

Gambar 15: Tampilan Menu Subject g.

Form Year Level

Gambar 20 : Tampilan Faculty Schedule Gambar 16 : Tampilan Menu Year Level h.

l.

Form Schedule

Form Section


23


Majalah Ilmiah


3.

graph dengan jumlah simpul yang banyak, disini diperlukan sebuah software komputer. Algoritma ini tidak selalu memberikan jumlah warna minimum yang diperlukan untuk mewarnai graph.

DAFTAR PUSTAKA

Gambar 21: Tampilan Schedule

m.

Form Print Schedule

Gambar 22 : tampilan Print Schedule

[1] Roger S.Pressman,2012:5. Software Engineering 6th Edition [2] Munir, Rinaldi (2005:353).Matematika Diskrit Edisi Ketiga [3] Munir, Rinaldi 2000. Matematika Diskrit Edisi Ketiga [4] Munir, Rinaldi 2007. Matematika Diskrit Edisi Ketiga [5] Siang, Jok Jek (2002:175. Penjadwalan ujian. [6] http://www.google.co.id/search? hl=id&client= firefox-a&hs=shj&rls =org.mozila (7 April 2012) [7] http://www.google.co.id/search?hl=id& client=firefox-a&hs= shj&rls=org. mozila (21 April 2012) [8] http://id.wikipedia.org/wiki/Teks_biasa [9] Mesran,1999. Seri Panduan Pemrograman Visual Basic 6.0, [10] http://fahmibaharun.wordpress.com/2010/ 04/02/apa-itu-algoritma

5. KESIMPULAN DAN SARAN 5.1 Kesimpulan Setelah dilakukan pembahasan pada babbab sebelumnya, maka dapat disimpulkan sebagai berikut : 1. Algoritma Priority Dispatching dapat diimplementasikan untuk penjadwalan Ruangan ujian. 2. Langkah awal penyelesaian adalah dengan memetakan suatu jadwal ke dalam graph lalu menentukan bilangan kromatik graph tersebut 3. Dengan penerapan Algoritma Priority Dispatching dapat membantu dalam penyusunan jadwal Ruangan ujian sehingga tidak terjadi bentrokan jadwal saat pelaksanaan ujian. 4. Algoritma ini cukup praktis untuk digunakan dalam pewarnaan simpul sebuah graph.

5.2

Saran Berikut adalah saran-saran untuk pengembangan lebih lanjut terhadap aplikasi ini : 1. Algoritma Priority Dispatching ini tidak dapat digunakan dengan skala yang besar 2. Untuk graph dengan jumlah simpul yang sedikit, dapat ditentukan bilangan kromatik suatu graph dengan mudah. Namun untuk


24

ANALISA DAN IMPLEMENTASI ALGORITMA PRIORITY DISPATCHING DALAM PENJADWALAN PEMBAGIAN RUANGAN UJIAN

Recommend Documents