PENERAPAN PEWARNAAN GRAF MENGGUNAKAN ALGORITMA WELCH POWELL UNTUK PENYUSUNAN JADWAL MATA PELAJARAN DI SMP KANISIUS PAKEM

Abstract

Penjadwalan merupakan kegiatan untuk mengalokasikan sejumlah sumber daya yang tersediauntukmemastikanbahwaperencanaandapatberjalandenganbaikdenganwaktudantenaga yang digunakan secara efisien. Dalam penelitian ini dipilih SMP Kanisius Pakem yang juga melakukan penyusunan jadwal pelajaran setiap tahun ajaran baru. SMP Kanisius Pakem memiliki 6 gurudan12matapelajaran.Selainitu,penyusunanjadwalpelajarandiSMPKanisiusPakemmasih menggunakan Microsoft Excel secara manual, sehingga masih sering terjadi tumpang tindih antar jadwal meskipun jadwal telah selesai disusun. Akibatnya, jadwal yang telah tersusun perlu disusun ulang. Untuk mengatasi masalah penjadwalan tersebut peneliti memilih untuk menerapkan pewarnaan simpul pada graf menggunakan Algoritma Welch Powell, dimana simpul yang berelasi (mata pelajaran yang diampu oleh guru yang sama) diberi warna yang berbeda satu sama lain, sehingga jadwal pelajaran yang disusun dapat optimal. Metode penelitian yang digunakan meliputi studiliteratur,pengumpulandata,pengolahandata,danpenarikankesimpulan.Hasilpenelitianyang diperoleh yaitu pewarnaan simpul graf menggunakan Algoritma Welch Powell dapat diterapkan dalam penyusunanjadwal pelajaran di SMP Kanisius Pakem. Dalam penerapannya, pewarnaan simpul pada graf dilakukan disetiap kelas sehingga terdapat 3 bentuk graf, yaitu graf kelas VII,VIII, danIX.Darimasing-masinggrafdiperoleh3warna,dimanawarnatersebutuntukmengelompokkan mata pelajaran. Mata pelajaran yang berada pada warna yang sama dapat dijadwalkan pada jam atauhariyangsama,sedangkanyangberadapadawarnayangberbedaharusdijadwalkanpadajam atau hari yang berbeda. Melalui pengelompokkan mata pelajaran tersebut akan memudahkan penyusunan jadwal pelajaran dan menghindari terjadinya jadwal tumpangtindih.