MODEL PENJADWALAN GURU MENGGUNAKAN GRAPH COLORING DENGAN ALGORITMA BEE COLONY
TESIS
Oleh SETIAWAN TANADI 117021027/MT
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2013
MODELPENJADWALAN GURU MENGGUNAKAN GRAPH COLORING DENGAN ALGORITMA BEE COLONY
TESIS
Diajukan Sebagai Salah Satu Syarat untuk Memperoleh Gelar Magister Sains dalam Program Studi Magister Matematika pada Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sumatera Utara
Oleh SETIAWAN TANADI 117021027/MT
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2013
Judul Tesis
: MODELPENJADWALAN GURU MENGGUNAKAN GRAPH COLORING DENGAN ALGORITMA BEE COLONY Nama Mahasiswa : Setiawan Tanadi Nomor Pokok : 117021027 Program Studi : Magister Matematika
Menyetujui, Komisi Pembimbing
(Prof. Dr. Opim Salim S, M.Sc ) Ketua
Ketua Program Studi
(Prof. Dr. Herman Mawengkang )
Tanggal lulus : 3 Juni 2013
(Dr. Marwan Ramli, M.Si ) Anggota
Dekan
(Dr. Sutarman, M.Sc )
Telah diuji pada Tanggal : 3 Juni 2013
PANITIA PENGUJI TESIS Ketua Anggota
: Prof. Dr. Opim Salim S, M.Sc : 1. Dr. Marwan Ramli, M.Si 2. Prof. Dr. Herman Mawengkang 3. Dr. Erna Budhiarti
PERNYATAAN
MODEL PENJADWALAN GURU MENGGUNAKAN GRAPH COLORING DENGAN ALGORITMA BEE COLONY
TESIS
Saya mengakui bahwa tesis ini adalah hasil karya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing dituliskan sumbernya
Medan, 3 Juni 2014 Penulis, Setiawan Tanadi
i
ABSTRAK
Penjadwalan merupakan salah satu masalah periodik yang rumit dan sering mengalami kesulitan khususnya disetiap sekolah dan universitas yang terdapat diseluruh dunia. Banyak faktor yang mempengaruhi penyusunan penjadwalan. Salah satu diantaranya adalah pengalokasian mata pelajaran dengan guru dan ruangan kelas sering mengalami benturan dengan jadwal mata pelajaran, guru dan ruangan kelas yang lain dalam satu periode jadwal sekolah. Oleh karena itu, penelitian ini akan memfokuskan pada masalah bagaimana memodelkan penjadwalan menggunakan teknik pewarnaan graph dengan algoritma bee colonydimana vertex merepresentasikanmata pelajaran yang akan dijadwalkan, edge merepresentasikan pasangan jam mengajaryang bisa menimbulkan konflik dan warna pada vertex merepresentasikan periode waktu kapan pelajaran tersebut dijadwalkan. Jika terdapat dua vertexvdanwyang terhubung oleh sebuah edge vw maka kedua vertex harus diwarnai dengan warna yang berbeda. Jumlah minimum warna yang dibutuhkan untuk mewarnai sebuah graph disebut angkakromatik dari G atau dinotasikan dengan X(G). Sebuah graph dengan pewarnaan vertex yang tepat akan mewarnai sepasang vertex yang terhubung oleh edge dengan warna yang berbeda. Pasangan vertex yang tidak terhubung oleh edge bisa menggunakan dua warna yang sama atau berbeda. Salah satu algoritma metaheuristik yaitu bee colony digunakan dalam tesis ini untuk fungsi pewarnaan graph sehingga menghasilkan suatu model penjadwalan guru yang dapat digunakan untuk mengatur jadwal secara optimal agar proses belajar mengajar dapat berlangsung dengan lancar. Kata kunci : Penjadwalan mata pelajaran, Pewarnaan graph, Algoritma bee colony.
ii
ABSTRACT
Scheduling is a one of the most complicated periodically problem that often meet difficulties especially at schools and universitiesall around the world. Many factors may influence the scheduling management. One of them is allocation among the teachers, lessons and classrooms with other teachers, lessons and classrooms in one periodic of time. Therefore, this research will focus on how to create a schedulings model by usingcoloring graph technique and algorithm of bee colony, which the vertex represents lesson that is needed to be scheduled, edge represents a pairing in teachings time which may have aconflict and color in the vertex represents aperiodic of time, whenever the lessons are scheduled. If there are 2 vertex v and w which is connected by an edge vw, so these two vertexs must be colored with different color. The sum of the minimum color which is needed for coloring a graph named cromatic number of G or notated as X(G). A graph with the exact coloring vertex will colora pair of vertex which is connected by an edge with different color. Pairing vertex which is not connected by the edge can use two same colors or different ones. One of the metaheuristic algorithm is bee colony which used to have the function of coloring graph so that the model can create an optimum result of teachers scheduling in order to proceed a better process in teaching. Keyword : Scheduling lesson, Graph coloring, Bee colony algorithm
iii
KATA PENGANTAR
Puji syukur penulis mengucapkan kepada Tuhan Yang Maha Esa yang telah melimpahkan rahmat, hidayah, dan karunia-Nya, sehingga penulis dapatmenyelesaikan tesis dengan judul: MODEL PENJADWALAN GURU MENGGUNAKAN GRAPH COLORING DENGAN ALGORITMA BEE COLONY. Tesis ini merupakan salah satu syarat untuk menyelesaikan studi pada Program Studi Magister Matematika FMIPA Universitas Sumatera Utara.Pada kesempatan ini, penulis menyampaikan ucapan terima kasih dan penghargaan yang sebesar-besarnya kepada: Prof. Dr. dr. Syahril Pasaribu, DTMH, M.Sc(CTM), Sp.A(K) selaku Rektor Universitas Sumatera Utara. Dr. Sutarman, M.Sc selaku Dekan FMIPA Universitas Sumatera Utara yang telah memberikan kesempatan kepada penulis untuk mengikuti Program Studi Magister Matematika di Sekolah Pascasarjana Universitas Sumatera Utara. Prof. Dr. HermanMawengkang selaku Ketua Program Studi Magister Matematika FMIPA Universitas Sumatera Utara dan selaku pembanding tesis. Prof. Dr. Saib Suwilo, M.Sc selaku Sekretaris Program Studi Magister Matematika FMIPA Universitas Sumatera Utara. Prof. Dr. Opim Salim S, M.Sc selaku pembimbing utama yang dengan sabar memberikan bimbingan dan arahan yang telah banyak memberikan bantuan dalam penulisan tesis ini. Dr. Marwan Ramli, M.Si selaku pembimbing kedua yang telah banyak memberikan bimbingan dan motivasi dalam menyelesaikan penulisan tesis ini. Dr. Erna Budhiarti selaku Tim Pembanding Tesis. Seluruh Staf Pengajar pada Program Studi Magister Matematika Universitas Sumatera Utara yang telah banyak memberikan ilmu pengetahuan selama masaperkuliahan. iv
Saudari Misiani, S.Si selaku Staf Administrasi Program Studi Magister Matematika Universitas Sumatera Utara yang telah banyak memberikan pelayanan yang baik kepada penulis selama mengikuti perkuliahan. Seluruh rekan-rekan Mahasiswa angkatan 2011-2013 pada Program Studi Magister Matematika Universitas Sumatera Utara yang telah memberikan bantuan moril dan dorongan kepada penulis. Secara khusus penulis menyampaikan terimakasih dan sayang yang mendalam kepada orang tua penulis, Ayah Ng Tiam Meng dan ibu Lie Sioe Hing, serta kepada seluruh keluarga yang senantiasa memberikan dukungan dan mendoakan keberhasilan penulis dalam menyelesaikan pendidikan ini. Kepada seluruh pihak yang tidak dapat penulis sebutkan satu persatu, penulis berterima kasih atas semua bantuan yang diberikan, semoga Tuhan membalaskan segala kebaikan yang telah diberikan, amin. Penulis menyadari bahwa tesis ini masih jauh dari sempurna, untuk itu penulis mengharapkan kritik saran untuk penyempurnaan tesis ini. Semoga tesis ini dapat bermanfaat bagi pembaca dan pihak-pihak lain yang memerlukannya baik perkembangan ilmu pengetahuan.
Medan, Penulis, Setiawan Tanadi
v
RIWAYAT HIDUP Setiawan Tanadi dilahirkan di Medan, pada tanggal 06 September 1982 dari pasangan Bapak Ng Tiam Meng dan Ibu Lie Sioe Hing., dan merupakan anak ke dua dari tiga bersaudara. Pada tahun 1989 penulis masuk SD Sutomo 1 Medan dan lulus pada tahun 1995. Pada tahun 1995 penulis melanjutkan sekolah di SMP Sutomo 1 Medan dan lulus pada tahun 1998. Pada tahun 1998 penulis melanjutkan studi di SMA Sutomo 1 Medan dan lulus pada tahun 2001. Pada tahun 2001 penulis diterima di Institut Sains dan Teknologi TD. Pardede jurusan Tehnik Industri dan mendapatkan gelar Sarjana Teknik pada tahun 2011. Kemudian penulis melanjutkan studi pada Program Magister Matematika di Universitas Sumatera Utara pada tahun 2011. Pada tahun 2003 penulis dipercaya sebagai guru matematika pada sekolah SMP Sutomo 1 Medan sampai sekarang.
vi
DAFTAR ISI Halaman PERNYATAAN
i
ABSTRAK
ii
ABSTRACT
iii
KATA PENGANTAR
iv
RIWAYAT HIDUP
vi
DAFTAR ISI
vii
DAFTAR GAMBAR
ix
BAB 1 PENDAHULUAN
1
1.1 Latar Belakang
1
1.2 Rumusan Masalah
2
1.3 Tujuan Penelitian
2
1.4 Manfaat Penelitian
3
BAB 2 TINJAUAN PUSTAKA
4
2.1 Model Penjadwalan
5
2.2 Graph
5
2.2.1 Teori Graph
5
2.2.2 Graph berbobot
8
2.2.3 Representasi Graph
8
2.2.4 Lintasan terpendek (shortest path)
10
2.2.5 Pewarnaan graph
11
2.2.6 Bilangan kromatik
12
2.3 Graph Konflik (Shift Ganda)
12
vii
2.3.1 Penjadwalan dengan metode graph
14
2.4 Masalah Pewarnaan Graph dalam Penjadwalan
14
2.4.1 Multicoloring
14
2.4.2 Precoloring extension
15
2.4.3 List coloring
15
2.4.4 Minimum sum coloring
15
2.5 Algoritma Bee Colony
15
BAB 3 METODOLOGI PENELITIAN
19
3.1 Teknik Pewarnaan Graph
19
3.2 Pengumpulan Data
20
3.3 Konstruksi Graph Konflik Pelajaran
20
3.4 Pewarnaan Graph Konflik Pelajaran
22
BAB 4 MODEL PENJADWALAN GURU
25
BAB 5 KESIMPULAN
31
5.1 Kesimpulan
31
DAFTAR PUSTAKA
32
viii
DAFTAR GAMBAR
Nomor
Judul
Halaman
2.1
Graph tak berarah
7
2.2
Graph berarah
7
2.3
Graph berbobot
8
2.4
Graph matriks ketetanggaan
9
2.5
Graph Matriks Bersisian
9
3.1
Mata pelajaran mi dan mj dijadwalkan pada slot waktu yang berbeda
3.2
21
Mata pelajaran mi dan mj di pasangkan pada slot waktu yang sama
3.3
22
Mata pelajaran mi dan mj di pasang pada ruangan kelas yang berbeda dan slot waktu yang berbeda
3.4
Mata pelajaran mi dan mj di pasang pada ruangan kelas yang sama dan slot waktu yang berbeda
3.5
22
23
Mata pelajaran mi dan mj tidak berpotensi menimbulkan konflik, di pasang pada ruangan kelas yang berbeda dan slot waktu yang berbeda
3.6
23
Mata pelajaran mi dan mj tidak berpotensi menimbulkan konflik, di pasang pada ruangan kelas yang berbeda dan slot waktu yang sama
3.7
24
Mata pelajaran mi dan mj tidak berpotensi menimbulkan konflik, di pasang pada ruangan kelas yang sama dan slot waktu yang berbeda
24
ix
