PENYUSUNAN JADWALUJIANMATAKULIAH DENGANALGORITMAPEWARNAANGRAFWELCH POWELL SetiaAstuti Fakultasllmu KomputerUniversitasDianNuswantoroSemarang Abstract: ln makinga schedulein our dailylife, it oftencausesa clashor trouble.Personallyit will be not a big problemsincethereis time toleranceand differentscheduleof each person.lf thereare many personson a scheduleit will be a big problemwhichcausesa big trouble.A scheduleof a universityincludesvarietysubl'ecfsandmany studenfs.GraphcoloringWelchPowellalgorithm offers a good solutionto know the minimumamount of days which are availablefor an examination,as the resulttherewill be no scheduleclashanymorefor students. Keyttords : graph,node,coloring,examschedule
PENDAHULUAN Penjadwalan ujianmerupakan suatupekerjaanrutindalamsistemakademikdi Perguruan Tinggiyangdilakukan setiapsemester. Padapelaksaanaannya, seringkalijadwal ujianyangtelah belumfx sehinggamembutuhkan dikefuarkan adanyapenjadwalan ulang.Hal ini disebabkan jenismatakuliahyangbanyakdanvariasipengambilan matakuliahdarimahasiswa yangbanyak juga . Padadasarnyadalammenentukan jadwalujianharusdiatursedemikian rupasehingga semuamahasiswa dapatmengikuti ujianmatakuliahyangdiambilnya tanpabertabrakan waktunya denganjadwalujiankuliahlainyangjugadiambilnya. Dengankatalainjikaadamahasiswa yang mengambil duabuahmatakuliahataulebih,jadwalujianmatakuliahtersebut haruspadawaktu yangtidakbersamaan. Ujianduabuahmatakuliahdapatdijadwalkan padawaktuyangbersamaan jikatidakadamahasiswa yangsamayangmengikuti ujianduamatakuliahtersebut. penjadwalan Dalammelakukan pemikiran ujian, diperlukan yangcukuprumituntukdapat (matakuliah,mahasiswa, memetakan sejumlahkomponenpenjadwalan ruang,dan waktu)ke dalamtimeslot(matriksruangdanwaktu)denganmempertimbangkan semuabatasanyangada. Masalahtersebutantaralainsetiap.mahasiswa yangmengontrak matakuliahharusdijadwalkan ujiandalamwaktuyangberbedadanketersediaan ruangyangsesuaiuntukpesertaujiandalam jumlahtertentu. Prosesmanualmemerlukan waktuyangcukuplamauntukdapatmelakukan hal ini dan pelanggaran memungkinkan terjadinya constraint akibalhumaneffor.Pelanggaran constraint dalam jadwaltidakvaliddan harusdirekonstruksi penjadwalan ujianmenjadikan ulang.Jika kejadian berulang tiapkalimenghadapiujian sepertiiniselalu semester,makasepatutnya permasalahan prioritas inimendapat untukdicarisolusinya demipeningkatan mutusistemakademik di Perguruan Tinggi. penjadwalan Permasalahan ujianterkaiterat denganmasalahoptimasl.Oleh karenaitu, pengembangan sistempenjadwalan ujiandilakukan denganmelaluibeberapa iterasiperbalkan. Fungsitujuannya adalahmemenuhisejumlah penjadwalan, constraint sepertimenghindariterjadinya bentrokjadwalujian.Dalamkajianilmudi Matematika Diskrit,teorigrafmemberisolusiuntuk permasalahan inimelaluibahasannya tentangpewarnaan graf,Pembuatan sistempenjadwalan ujianyangmenerapkan teoriinidiharapkan mampumenjawab permasalahan ini. Beberapa constraint di atasmenunjukkan bahwapermasalahan penjadwalan ujianditimbulkan yangbersifat olehsuatuvariabel dinamisyaitupolakontrakmatakuliahyangdilakukan mahasiswa. padaumumnya Variabellainnya sepertiruang tidakmengalamiperubahan yangbegitu.signifikan
68
tunuf Dian ilot. 11 Np. 1lawnri 207t
sehinggamasihmungkindiadaptasidengan keadaanreal.Sedangkanpola kontrakmata kuliah yang berbedapada tiap semestersangat menjadikendalauntuk penjadwalanujian sehingga prediksimengenaihal ini sangatdiperlukan.
LANDASANTEORI 1. Permutasidan Kombinasi Sepertitelah disebutkansebelumnyabahwa permasalahanpenjadwalanujian disebabkan oleh pola kontrak mata kuliahyang dilakukanmahasiswa.Hal ini merupakanpermasalahan kombinatorialsehinggadibutuhkanpenulusuranmasalah secara matematisagar hasil yang didapatkanlebihoptimal.Pemahamandimulaidariteoritentangpermutasidankombinasi. Permutasiadalahjumlah urutanberbedadari pengaturanobjek-objek.Permutasimerupakan bentukkhususaplikasiaturanperkalian.Misalkanjumlahobjekadalahn, maka urutanpertama i b j e k , u r u t a n k e t i g a d i p i l i h d anr-i 2 o b j e k , dipilihdan r io b j e k , u r u t a n k e d u a d i p i l i h dna- rl o begituseterusnya, dan urutanterakhirdipilihdari 1 objekyang tersisa.Menurutkaidahperkalian, permutasidann objek adalah n(n - 1)(n-2) ... (2)(1)= nt Adapunjumlah susunanberbedadari pemilihanr objek yang diambildan n objek disebut permutasi-r, dilambangkandenganP(n,r),yaitu fln, rl = n (n - 1)(n- 2) ... (n - (r - 1)) = nt (n - rl! Kombinasimerupakanbentuk khusus dari permutasi.Kombinasimengabaikanurutan kemunculan.Dalam kasuspenjadwalanujian,kombinasimerupakanvariasiyangmungkinterjadi ketika mahasiswamemilihuntuk mengontrakmata kuliahpada semestertertentu.Jumlah mata kuliahyang ditawarkanProgramStudi sebanyakn objek dan jumlah mata kuliahyang dikontrak dengan batasanSKS tertertuadalahr objek. Rumus kombinasi-radalah
C (n,rl=
nl il(n-r)l
2. Graf Teori Graf merupakansalah satu bahasan dalam MatematikaDiskrit yang menarik untuk dibahas karena berkaitandengan permasalahanyang banyak ditemui di dunia nyata Graf G didefinsikan sebagaipasanganhimpunan(VE), ditulisdengannotasiG = (VE ) ,dimanV adalah himpunantidak kososngdari simpul- simpul( verteks) dan E adalahhimpunansisi ( Edges ) yang meghubungkan sepasangsimpul. BerdasarkanarahnyaGraf dibedakanmenjadi2 yaitu : a. Graf Tak Berarah : Graf yang sisinyatidak mempunyaiorientasiarah b. Graf Berarah: Graf yang sisinya mempunyaiorientasiarah Pada tulisanini hanya dibahasGraf Tak Berarahsaja.
2.1.DerajatGraf padagraftakberarah jumlah Derajat suatusimpul adalah sisiyangbersisian dengan simpul tersebut. 2.1. PewarnaanGraf Dalam teori graf, pewarnaangraf merupakansuatu bentuk pelabelangraf, yaitu dengan memberikanwarna pada elemengraf yang akan dijadikansubjekdalam memahamiconstraint
Qenyusunnn J adwa[.....(SetioAstuti)
69
permasafahan. Ada tiga macampersoalanpewarnaangraf(graphcolouring), yaitupewarnaan simpul,pewarnaan sisi,danpewarnaan wilayah(region). Padatulisaninihanyaakanmembahas pewarnaan untukelemengrafyangpalingsederhana yaitupewarnaan simpulgraf. 2.2.Pewarnaan Simpul Graf Pewarnaan simpuladalahmemberiwarnapadasimpul-simpul di dalamgraf sedemikian sehingga setiapduasimpulbertetangga mempunyaiwarna yangberbeda [1].Contohkasusyang permasalahan merepresentasikan inidiantaranya adalahpenjadwalan ujianmatakuliah. 2.3.Bilangan Kromatik padahakikatnya Penyelesaian kasuspenjadwalan adalahberupaya untukmengalokasikan sejumfahaktifitasyangmengandung constraint ataubatasanke dalamtimeslot(matriksruang dan waktu).Jumlahtimeslotyangtersediajuga memilikibatasan,baikberupajumlahruang, maupunwaktupenggunaannya. Oleh karenaitu, penjadwalan yang baik haruslahdapat menyesuaikan sejumlahketerbatasan resourceatausumberdayayangadaagarseluruhaktifitas dapattetapterlaksanatanpamelanggarconstraint-nya. Pewarnaangraf mengakomodasi hal tersebut denganbilangan kromatik. Bilangan Kromatik GrafG (*(G))adalahjumlahwarnaminimum yangdapatdigunakan untuk (verteks/ mewarnai simpul V). 2.4.Algoritma Welch-Powell
Flowchaft Algoritma Welch-Powelladalah sebagaiberikut:
Algoritma Welch-Powell merupakan salahsatu a l g o r i t m ap e w a r n a a ng r a f y a n g m e l a k u k a n pewarnaanberdasarkanderajattertinggidari simpul-simpulnya atau disebutLargesfDegree Ordering(LDO).AlgoritmaWelch-Powell Carisatusimpul berderajat dapat tertinggi atausimpulutama digunakan untukmewarnai sebuahgrafG secara warna(SUW) jumlah Algoritma efisien. initidakselalumemberikan warnaminimumyangdiperlukan untukmewarnai G, namuncukuppraktisuntukdigunakandalam pewarnaan simpulsebuahgraf.Algoritma WelchPowellhanyacocokdigunakan untukgrafdengan ordeyangkecil[3]. Berikutalgoritmanya: 1) Urutkansimpul-simpul dari G dalamderajat yangmenurun (urutan sepertiinimungkin tidak yangtldak Carisatu simpul unikkarenabeberapa simpulmungkinberderajat bertetangga dengan sUW sama). danberderajat tertinggi 2) Gunakansatuwarnauntukmewarnai slmpul pertama(yangmempunyai derajattertinggi) Tidakada dan simpul-simpul lain (dalamurutanyang berurut)yang tidakbertetanga dengansimpul pertamaini. Beriwarnayangsama 3) Mulailagidengansimpulberderajat tertinggi dengan SUW berikutnya di dalamdaftarterurutyangbelum diwarnai danulangiprosespewarnaan simpul denganmenggunakan warnakedua. Gambar1. 4) Ulangipenggunaan warna-warna sampaisemua Flowchart Algoritma Welch-Powell simpultelah diwarnai.
70
Iurnnf Dinn,/o[. 11 M. 1 Jarunri2017
ANALISADAN PEMBAHASAN Pada pembahasandimisalkan terdapat10 mahasiswadan 6 matakuliahyang berbeda. Masing- masingmahasiswamengontrakmata kuliahdengankombinasiberbeda,sepertipada tabel di berikutini:
Tabel 1. Tabel relasi mahasiswayang mengambilmatakuliah Variasimata kuliahyang dikontrakoleh mahasiswadimodelkansecara matematisdalam bentuk graf. Mata kufiah disimbolkandi dalam graf berupa simpul yang merupakansubl'ectdari constraint yang akan dipenuhi.Adapun constraintyang dimaksudadalah syarat bahwajadwal ujian mata kuliahyang diselenggarakantidak boleh berbentrokanagar mahasiswadapat mengikutiseluruh ujiandari mata kuliahyang dikontraknya.Berikutini adalahrepresentasigraf yang terbentukdari tabel di atas.
V4o
V6 Gambar 2. GambarGraf hasildari tabel 1
lPenynsunan 1adua[..,. (SetiaAStuti)
71
Kemudiandisusundaftarsimpulgraf dan ketetanggaannya sebagaiberikut Vertoks(simpul)
SimpdlTetangga
vl
v2, v3, v5, v6
v2
vl, v4,v6
V3
vl , v5
v4
v2, v5
V5
vl, v3, v4, v6
v6
v1, v2, v5
Tabel2. Tabelsimpul dan ketetanggaannya DenganalgoritmaWelch-Powell, hasilyang didapatkanadalah:
Verteks
V1
V5
V6
v2
v4
V3
Derajat
4
4
4
3
3
2
Warna
a
b
c
r
a
c
Tabel 3. Tabel pewarnaan graf dengan algoritmaWelch-Powel
Alur kerjanyasebagaiberikut: 1.
PilihVerteksVl denganderajat4 kemudian diberiwarnaa ( dalamgambarmisaldipilih warnabiru)
2.
PilihVerteksyangtidakbertetangga denganVl yaituV4 kemudian diberiwarnaa juga.
3.
PilihVerteksV5 denganderajat4 kemudian diberiwarnab ( dalamgambarmisaldipilih warnahijau)
4.
PilihVerteksyangtidakbertetangga denganV5 yaituV2 kemudian diberiwarnab juga.
5.
PilihVerteksVGdenganderajat4 kemudian diberiwarnac ( dalamgambarmisaldipilih warnamerah)
6.
PilihVerteksyangtidakbertetangga denganV6 yaituV3 kemudian diberiwarnac juga,
72
turno[ Dinn,l/o[. 11 M. 1 larunri %)11
Gambar graf yang didapatsebagaiberikut:
'ot V6 Gambar 3. GambarHasilPewarnaanGraf
gambargraf tersebutterdapat3 warnaberbedauntuk6 simpulmatakuliah Berdasarkan yaitua,bdanc ataubiru,hijau danmerah.Ataudikatakan Grafmempunyaibilangankromatis3. Sehingga dapatdianalisabahwadari6 matakuliahtersebutbisadijadwalkan ujianselama3 hari yaitu: 1. Harike 1: ujianuntukmatakuliahv1 danv4 2. Harike 2: ujianuntukmatakuliahv2 danv5 3. Harike 3: ujianuntukmatakuliahv3 dan v6
KESIMPULAN Berdasarkananalisadan pembahasandiatasdapat diambilkesimpulansebagaiberikut: 1.
AlgoritmaPewarnaanGraph Welch Powell bisa digunakanuntuk menentukanjadwal ujian semesterpada sisteminformasiakademikPerguruanTinggisehinggatidakterjadibentrokan jadwal ujian untuk semua mahasiswa.
2.
AlgoritmaPewarnaanGraphWelch Powellbisadigunakanuntukmenentukanminimaljumlah hari ujian yang dibutuhkandalam mengadakanujian tersebut sehingga bisa menghemat waktu.
lknyasunnnladua[..... (Setk Astutil
73
DAFTARPUSTAKA 1.
(2005).Matematika Informatika. Munir,Rinaldi. Diskrit edisiKetiga,lBandung:
2.
Al-Omari,Hussein& KhairEddinSabri.(2006).New Graf ColoringAlgorithms[Online]. Tersedia:www.scipub.org/fulltext/jms2ljms224739-741.pdf, Diakses tanggal12Mei2010.
3.
Budiman,Hengky.Penerapan GraphColouring untukMerencanakan JadwallOnlinel. Tersedia: http://www.informatika.org/-rinaldi/Matdisl2007l2O08/Makalah/MakalahlF2153-0708-025.pdf, tanggal14 Mei2010. Diakses
4.
Setiadi,Robert.(2001).PemecahanMasalahPenjadwalan KuliahdenganMenggunakan Teknik IntelligentSearch[Online].Tersed ia: http://www.robertsetiadi.neUartlcles/snkk.htm, Diakses5 Juni2010. As'ad,Nabifa.AplikasiPewarnaan GrafPadaPemecahanMasalahPenyusunan Jadwal htto://www.scribd.com/doc/38875880/Aplikasi-Pewarnaan-Graf-Pada-Pemecahan-MasalahPenyusunan Jadwal, Diakses 6 Juni2010.
74
Iurnaf Dian'/o[, ll ib. I ]arunri 2011
