## PENERAPAN METODE ALGORITMA GENETIKA UNTUK PENJADWALAN MENGAJAR
I Gusti Ayu Desi Saryanti STIKOM Bali Email: desi@stikom-bali.ac.id
I Kadek Wijanegara STIKOM Bali Email: juan_tole@yahoo.com

## ABSTRAK
Penjadwalan merupakan kegiatan prioritas terhadap pengajar atau pun guru yang berdasarkan tingkat keahlian masing-masing dan untuk membagi tugas kita perlu perhatikan ada atau tidaknya tumpukan dan penambahan waktu pada pengajar yang mengajarkan mata pelajaran kepada siswa/i. Dalam aspek kegiatan mengajar sangat penting untuk kelancaran proses belajar mengajar di sekolah, dan terkadang waktu sering bertumpukan untuk para pengajar. Oleh karena itu perlu penjadwalan khusus para pengajar ataupun guru untuk menghindari terjadinya tumpukan dan bertambahnya waktu serta mendukung suatu pelaksanaan kegiatan yang berkaitan dengan belajar mengajar. Dalam kasus penjadwalan mengajar, diperlukan algoritma yang lebih baik yaitu algoritma genetika yang merupakan salah satu algoritma yang sangat tepat digunakan untuk menyelesaikan masalah optimasi kompleks yang sulit dilakukan oleh metode konvensional.
Kata kunci : penjadwalan, algoritma genetika.

## ABSTRACT
Scheduling is a priority activity of the teacher or teachers based on the level of expertise of each and to divide the tasks we need to look at whether or not the pile and adding time to the teachers who teach subjects to students. In the aspect of teaching is very important for the smooth process of teaching and learning in schools, and sometimes is often schedule piling on teachers. Therefore require special scheduling teachers to avoid the pile and increasing time and support an implementation of activities related to teaching and learning. In the case of scheduling teaching, needed a better algorithm is a genetic algorithm which is one of the very precise algorithms used to solve complex optimization problems that are difficult to do by conventional methods.
Keywords : scheduling algorita genetics.

## 1. PENDAHULUAN
Penjadwalan adalah suatu bentuk kegiatan termasuk dalam proses belajar mengajar di semua sekolah untuk para pengajar ataupun guru khususnya di Sekolah Menegah Kejuruan (SMK Giri Pandawa) . Dalam aspek kegiatan mengajar sangat penting untuk kelancaran proses belajar mengajar di sekolah, dan terkadang waktu sering bertumpukan untuk para pengajar. Oleh karena itu perlu penjadwalan khusus para pengajar ataupun guru untuk menghindari terjadinya tumpukan dan bertambahnya waktu serta mendukung suatu pelaksanaan kegiatan yang berkaitan dengan belajar mengajar. Untuk membuat jadwal pengajar harus memperhatikan dari berbagai aspek yang mempengaruhi penjadwalan tersebut. Penjadwalan merupakan kegiatan prioritas terhadap pengajar atau pun guru yang berdasarkan tingkat keahlian masing-masing dan untuk membagi tugas kita perlu perhatikan ada atau tidaknya tumpukan dan penambahan waktu pada pengajar yang mengajarkan mata pelajaran kepada siswa/i. Selain itu harus dipertimbangkan juga ruangan pengajar biar dapat dilaksanakannya dalam penyusunan jadwal mengajar yang selayaknya dicoba untuk menemukan penjadwalan yang terbaik. Salah satu solusi untuk meningkatkan kualitas mengajar adalah dengan merancang menggunakan metode-metode yang dapat diterapkan untuk mengerjakan penjadwalan mengajar yang ada di SMK Giri Pandawa. Dalam kasus penjadwalan mengajar, diperlukan algoritma yang lebih baik yaitu algoritma genetika yang merupakan salah satu algoritma yang sangat tepat digunakan untuk menyelesaikan masalah optimasi kompleks yang sulit dilakukan oleh metode
konvensional. Banyak permasalahan optimalisasi yang telah diselesaikan dengan menggunakan Algoritma Genetika di antaranya adalah permasalahan task assignment pada sistem terdistribusi, travelling salesmen problem, timetabling , transportasi, knapsack [1] . Dengan latar belakang yang disebutkan di atas, maka penulis mencoba mengaplikasikan Algoritma Genetika untuk mengoptimalkan penjadwalan mengajar yang ada SMK Giri Pandawa. Berharap menggunakan Algoritma Genetika akan memperoleh optimasi penjadwalan mengajar yaitu dengan terjadinya kombinasi terbaik untuk mata pelajaran dan pengajar secara keseluruhan.

## 2. METODOLOGI PENELITIAN

## 2.1 Data
Pada bab ini berisikan penjelasan mengenai jenis data yang akan digunakan, teknik pengumpulannya, dan penjelasan lain yang di pandang perlu.

## 2.2 Jenis Data
Jenis data terbagi menjadi dua yaitu data primer dan data sekunder.
1) Data primer adalah data yang diperoleh peneliti secara langsung.
2) Data sekunder adalah data yang diperoleh peneliti dari sumber yang sudah ada, seperti dokumentasi atau catatan

## 2.3 Teknik Pengumpulan Data
Teknik pengumpulan data merupakan metode atau cara yang dilakukan untuk mengumpulkan data. Adapun teknik pengumpulan data yang digunakan dalam penelitian ini adalah sebagai berikut :
1) Studi Pustaka
Studi pustaka merupakan suatu metode pengumpulan data berupa laporan-laporan studi terdahulu, paper atau makalah, dan artikel-artikel dari internet serta data sekunder yang dibutuhkan dalam mendesain penelitian, serta menganalisis hasil studi. Studi pustaka terkait dengan berbagai sumber informasi tentang penerapan Aloritma Genetika.
2) Observasi
Pengumpulan data dengan observasi merupakan teknik pengumpulan data melalui proses pengamatan secara langsung dan mencatat secara sistematis terhadap kegiatan yang diteliti . 3) Wawancara Wawancara adalah proses memperoleh keterangan untuk tujuan penelitian dengan cara tanya jawab dan bertatap muka antara penanya atau pewawancara dengan penjawab atau responden dari pihak terkait.

## Gambar 1. Alur Analisis
Penelitian ini diawali dengan pengumpulan data dan dilanjutkan dengan penerapan dari metode yang digunakan. Tahapan kegiatan secara rinci dari penelitian yang dilakukan adalah sebagai berikut:
1) Pendefinisian permasalahan berkaitan dengan perancangan sistem
2) Studi Pustaka, pengumpulan data berupa buku-buku, paper atau dokumentasi yang berkaitan dengan penelitian yang dilakukan.
3) Wawancara, dilakukan proses tanya jawab antara peneliti dengan responden.
4) Observasi, yaitu pengamatan secara langsung pada proses-proses yang sedang berjalan.
5) Analisa, melakukan proses penganalisaan terhadap permasalahan yang dibahas pada penelitian.
6) Penerapan metode, dilakukan dengan melakukan perhitungan terhadap algoritma genetika.
7) Pengambilan kesimpulan.

## 3. HASIL DAN PEMBAHASAN

## 3.1 Analisa Permasalahan
Sistem penjadwalan mengajar yang ada di Sekolah Menengah Kejuruan  (SMK) Giri Pandawa dapat dikatakan baik, karena sudah terkomputerisasi. Namun aplikasi dalam bentuk penjadwalan mengajar belum begitu efektif dan efisien karena setiap mata pelajaran dan guru belum mempunyai database. Terdapat beberapa kekurangan dan kemungkinan terjadinya human error dalam pelaksanaannya seperti input data oleh bagian Kurikulum. Hal ini dikarenakan banyaknya kesediaan mengajar data guru yang perlu dimasukkan ke dalam aplikasi Microsoft Excel guna diproses secara manual. Untuk melihat jadwal, guru diberi selebaran kertas jadwal mengajar dan juga jadwal ditempel di madding sekolah biar tidak lupa dalam proses kegiatan belajar mengajar yang telah ditentukan. Analisis permasalahan yang dihadapi adalah dalam dokumentasi data kesediaan mengajar sudah tersimpan secara lengkap, karena kesediaan mengajar dibuat di atas kertas dan pembuatan jadwal sudah menggunakan komputer, hanya saja penggunaan komputer tersebut sebatas penyimpanan data dan pencetakan data. Oleh karena itu diperlukan pengembangan suatu sistem penjadwalan mengajar yang dapat meminimalisasi beberapa kekurangan dan kemungkinan terjadinya human error seperti input data , sehingga dapat memudahkan bagian Kurikulum dalam proses pembuatan jadwal mengajar.

## 3.2 Analisa Sistem
Sekolah Menengah Kejuruan  (SMK) Giri Pandawa merupakan salah satu sekolah yang cukup favorit di daerah setempat. Kegiatan belajar mengajar dilaksanakan pada hari senin sampai sabtu, pada hari senin dimulai pukul 07.20 sampai dengan 13.00. sedangkan hari selasa sampai sabtu dimulai pukul 07.30 sampai dengan pukul 12.40.  Dalam sehari di SMK Giri Pandawa ini mendapatkan 2x istirahat pada hari Senin 10.00 s/d 10.10 dan pukul 11.30 s/d 11.40. Sedangkan di hari selasa sampai hari Sabtu pada pukul  Dalam seminggu jumlah jam mengajar di SMK GIri Pandawa 24 jam. Jam mengajar guru juga mencakup pekerjaan administrasi yang dikonversi ke jam mengajar. Guru mengampu mata pelajaran yang ditentukan. Penerapan Algoritma ini merujuk pada pengumpulan data yang diperlukan sebagai bahan masukan ( input ) untuk membuat aplikasi penjadwalan dengan menggunakan metode algoritma genetika yaitu data MP Guru, Guru, Mata Pelajaran, Kelas, Ruang dan Waktu. Proses untuk mengolah data input adalah dengan algoritma genetika. Output yang dihasilkan adalah jadwal mengajar yang optimal dan sesuai dengan apa yang diharapkan.
Berdasarkan uraian di atas, maka dapat dijabarkan data sistem penjadwalan seperti yang dapat dilihat pada Gambar berikut ini :
Gambar 2. Data Sistem Penjadwalan

## 3.3 Analisa Kebutuhan Non Fungsional
Analisa kebutuhan non fungsional menggambarkan faktor-faktor yang ada dalam pengembangan sistem penjadwalan mengajar, diantaranya analisa user, data mengajar yang nantinya akan digunakan sebagai acuan utuk perhitungan menggunakan algoritma genetika.

## 3.4 Desain Sistem

## 3.4.1 Desain Umum Sistem

## Gambar 3. Desain Umum Sistem
Gambar 3 menjelaskan gambaran umum dari desain sistem penjadwalan mengajar menggunakan algoritma genetika, tahap pertama dimulai dari inputan sistem yang terdiri dari Data MP Guru, Guru, MP, Kelas, Ruang, dan Waktu kemudian data tersebut akan memproses menggunakan metode algoritma genetika sehingga nantinya akan menghasilkan output penjadwalan.

## 3.4.2 Bentuk Output
Penjadwalan mengajar pada Sekolah Menengah Pertama Kejuruan (SMK) Giri Pandawa sangat ditentukan oleh jumlah jam pelajaran setiap minggu, jumlah mata pelajaran yang sesuai dengan kurikulum, jumlah ruang kelas yang ada dan jumlah guru yang mengajar suatu mata pelajaran. Kurikulum
Data Masukan Data MP Guru Data Guru Data MP Pros es Algor itma Gene tika Outp ut Penj adwa lan Parameter Algoritma Genetika Constraint Data Ruang Data Waktu Data Kelas
yang berlaku di SMK Giri Pandawa, menunjukkan bahwa jumlah jam yang diberlakukan dalam proses pembelajaran dalam seminggu adalah 24 jam tidak termasuk extrakurikuler.
Mata pelajaran ini akan didistribusikan pada jadwal yang dimulai pada hari Senin hingga hari Sabtu dengan bobot untuk 1 jam pelajaran adalah 40 menit. Proses pembelajaran dimulai pada pukul 07.00 dan berakhir pukul 12.50. Rentang waktu pembelajaran ini hanya berlaku untuk hari Senin hingga hari Selasa. Pada hari Rabu, Kamis dan Sabtu, proses waktu pembelajaran sama dimulai pada pukul 07.00, tapi berakhir pukul 11.15. Sedangkan pada hari Jum’at proses waktu pembelajaran sama pada pukul 07.00 dan berakhir pukul 09.55. Untuk lebih jelasnya penjadwalan mengajar terlihat pada gambar 4.
Aph ‐ 1 Aph ‐ 2 Aph ‐ 3 Aph ‐ 4 Aph ‐ 5 TKJ Aph ‐ 1 Aph ‐ 2 Aph ‐ 3 Aph ‐ 4 Aph ‐ 5 TKJ Aph ‐ 1 Aph ‐ 2 Aph ‐ 3 Aph ‐ 4 Aph ‐ 5 TKJ 07.3 0- 08.1
0 Ngakan
Putu Murtika Putu
Agus Narendr a, ST I Nym Pande
Setiaw an Dew a Putu Suaba I GN Sandi Putra Ni
Waya n Parw ati Ni Kadek Pebi Apsari I Komang Sumarta I Ketut Mertaya sa
I Wayan Gede
Suamat a Md Sri Yuli Astuti Ni Made Kencan a Dew i Ni Nengah
Puspaw ati I Made
Agus Suciarta I Wayan Suw iji I Komang Wedana I Gst Ngr. Eka Ni Luh GD
Septiari yastini 08.1
0- 08.5 0 Ngakan Made
Ariaw a n I Wayan Desi
Baw anta ra Ni Luh GD
Septiari yastini IGN Mataram I Komang Juliani Waya n Andik a Ngakan Putu Murtika Ni Wayan Parw ati I Komang Sumarta Md Sri Yuli Astuti Ni Luy Eka Sumardi ni I Ketut Mertaya sa I Nym Pande Setiaw a n I Gst Ngr. Eka I GN
Sandi Putra Ni Luh Sri
Parw ati Ni Made Sumami I Wayan Gede
Suamat a 09.4 5- 10.2
5 Dew a Putu Suaba Ni Wayan
Parw ati I Nym Pande
Setiaw an Ngakan Putu
Murtika Putu
Agus Narendr a, ST I GN Sandi Putra Md Sri Yuli
Astuti Ni
Kadek Pebi Apsari
Ni Made Kencan a Dew i I Ketut Mertaya sa I Komang Sumarta I Wayan Gede Suamat a Ni Luh GD Septiari yastini I Gst Ngr. Eka I Komang Wedana I Wayan Suw iji I Made Agus Suciarta Ni Nengah
Puspaw ati 10.2 5- 11.0
5 Wayan Andika
Wiraw an Ngakan
Made Ariaw an I
Koman g Juliani I Wayan Desi
Baw anta ra Ni Luh GD
Septiari yastini IGN Matar am Md Sri
Yuli Astuti
Ni Luy
Eka Sumardi ni I Ketut Mertaya sa I Komang Sumarta Ni Wayan Parw ati Ngakan Putu Murtika
I Wayan Gede Suamat a Ni Made Sumami Ni Luh Sri Parw ati I Nym
Pande Setiaw a n I Gst Ngr. Eka I GN Sandi Putra Kelas X Kelas XI Kelas XII Selasa Jam Istirahat
Gambar 4. Contoh Output Jadwal Mengajar
Kendala terbesar yang dihadapi adalah ketersediaan tenaga guru masing-masing mata pelajaran untuk mengajar sejumlah kelas. Bagaimana menyusun jadwal pelajaran untuk sejumlah kelas dengan sejumlah mata pelajaran yang ada diampu oleh sejumlah guru yang tersedia. Masalah inilah yang akan dicari solusinya dengan menggunakan metode Algortima Genetika.

## 3.4.3 Constraint
Terdapat batasan/persyaratan ( constraint ) dalam penyusunan penjadwalan mengajar. Constraint sendiri merupakan suatu syarat yang harus dipenuhi dalam menghasilkan susunan penjadwalan yang baik. Beberapa constraint tersebut, yaitu:
a) Tidak ada guru mengajar di jam yang sama kecuali mata pelajaran olah raga.
b) Guru sudah di assign mengajar di mata pelajaran tertentu.
c) Maksimal jam mengajar adalah 8 jam per hari.
d) Satu jam pelajaran adalah 40 menit.

## 3.4.4 Parameter
Parameter yang digunakan pada algoritma genetika adalah:
1) Fungsi fitness (fungsi tujuan) yang dimiliki oleh masing-masing kandidat penjadwalan untuk menentukan tingkat fitness individu tersebut dengan kriteria yang ingin dicapai.
2) Populasi jumlah individu yang dilibatkan pada setiap generasi melalui proses seleksi.
3) Probabilitas terjadinya persilangan ( crossover ) pada suatu generasi.
4) Probabilitas terjadinya mutasi pada setiap individu.
Adapun teori-teori yang diterapkan dalam sistem ini adalah:
a) Seleksi
Operasi seleksi dilakukan dengan memperhatikan fitness dari tiap individu, manakah yang dapat dipergunakan untuk generasi selanjutnya. Seleksi ini digunakan untuk mendapatkan calon induk yang baik, semakin kecil nilai fitness nya maka semakin kecil juga kemungkinan individu tersebut terpilih. diantaranya adalah seleksi roulette wheel . Proses seleksi yang biasa digunakan adalah mesin roulette ( roulette wheel ). Calon induk yang akan dipilih berdasarkan nilai fitness yang dimilikinya, semakin baik individu tersebut yang ditujukkan dengan semakin kecil nilai fitness nya akan mendapatkan kemungkinan yang lebih kecil untuk terpilih sebagai induk. Misalkan saja roulette wheel merupakan tempat untuk menampung seluruh kromosom dari tiap populasi, maka kecilnya tempat dari roulette wheel tersebut menunjukkan seberapa kecil nilai fitness yang dimiliki oleh suatu kromosom, semakin kecil nilai fitness tersebut, maka semakin kecil pula tempat yang tersedia. Ilustrasinya dapat digambarkan sebagai berikut:
Gambar 5. Ilustrasi Seleksi Dengan Roulette Wheel
b) Mutasi
Mutasi juga merupakan salah satu operator penting dalam algoritma genetika selain crossover . Metode dan tipe mutasi yang dilakukan juga tergantung pada encoding dan permasalahan yang diangkat. Berdasarkan encoding nya diantaranya adalah sebagai berikut: Permutation Encoding Memilih dua nilai dari gen dan menukarnya. Contoh: ( 1 2 3 4 5 8 9 7 ) => ( 1 8 3 4 5 6 2 9 7 ) Operator mutasi telah diciptakan untuk representasi permutasi, seperti metode insertion mutation . Insertion Mutation memilih sebuah gen dengan cara acak dan memasukkan ke dalam kromosom dengan cara acak pula.
c) Kawin Silang (Crossover)
Kawin silang ( crossover ) adalah salah satu operator penting dalam algoritma genetika, metode dan tipe crossover yang dilakukan tergantung dari encoding dan permasalahan yang diangkat. Cara yang bisa digunakan untuk melakukan crossover sesuai dengan encodingnya yang dijelaskan sebagai berikut:

## Permutation Encoding
Memilih satu titik tertentu, nilai permutasi sampai titik crossover pada induk pertama digunakan lalu sisanya dilakukan scan terlebih dahulu, jika nilai permutasi pada induk kedua belum ada pada offspring nilai tersebut ditambahkan. Contoh: ( 12345 6789) + (453 6897 21) = 123456897

## 3.4.5 Nilai Fitness
Setelah merancang kromosom (kandidat solusi/penjadwalan), langkah berikutnya adalah mendefinisikan fungsi fitness . Fungsi fitness berguna untuk menentukan nilai sebuah kromosom. Nilai inilah yang nantinya akan digunakan untuk menentukan apakah kromosom ini merupakan solusi terbaik atau solusi yang lebih baik dari kromosom lainnya. Beberapa ketentuan yang berkaitan dengan penghitungan nilai fitness adalah terlihat pada Tabel 1.

## Tabel 1. Jumlah jam mengajar selama seminggu
No Nama Guru Mengajar Jam Perkelas Jumlah Jam X XI XII 1 Ngakan Putu Murtika Agama 14 24 BK 10 2 Putu Agus Narendra, ST KKPI 8 24 DKK-2, KK-5,KK 16 3 I Nym Pande Setiawan DKK 1, KKPI 14 24 KK 2,6 10 4 I Gst Ngr. Eka KKPI 18 24 DKK-3, KK-4, 7 6 5 Dewa Putu Suaba KK-3,KK-4 14 24 KK-5 10 6 I GN Sandi Putra DKK-4, KK-5 16 24 KK-7, 8 7 Ni Wayan Parwati DKK-1 12 24 KK-3 12 8 Ni Kadek Pebi Apsari DKK-3, KK-1 16 24 KK-6 8 9 Ni Luh Sri Parwati DKK-2 10 24 KK-4, KK-8 14 10 I Komang Sumarta PKn 16 24 IPS 8 11 I Ketut Mertayasa PKn 24 24 12 Ni Made Sumami Kewirausahaan 24 24 13 I Wayan Gede Suamata PKn 8 24 Seni Budaya 16 14 Putu Darma Suci Kewirausahaan 24 24 15 I Wayan Andika Wirawan Bhs. Inggris 24 24 16 Md Sri Yuli Astuti Matematika 24 24 17 Ni Made Kencana Dewi Matematika 24 24 18 Ni Luy Eka Sumardini Matematika 24 24 19 IGN Wirya Sudewa Bhs. Inggris 24 24 20 Ni Komang Juliani Bhs. Inggris 24 24 21 Ni Nengah Puspawati IPA 24 24 22 I Made Agus Suciarta IPA 12 24 Seni Budaya 12 23 Ni Wyn Melina Pebriani Bhs. Jepang 24 24 24 IGN Mataram Fisika 12 24 Kimia 12 25 I Wayan Suwiji IPS 24 24 26 I Wayan Desi Bawantara Agama 12 24 BK 12 27 I Komang Wedana Agama 10 24 Budi Pekerti 14 28 Ngakan Made Ariawan Bahasa Bali 16 24 Bhs. Indonesia 8 29 Ni Luh GD Septiariyastini Bhs. Bali 16 24 Bhs.Indonesia 8
Untuk menentukan nilai rata-rata, terlebih dahulu menjumlahkan jumlah jam guru dalam seminggu. berikut penjumlahan untuk menentukan rata-rata.
Berikut ini adalah contoh perhitungan fitness function pada kromosom sampel dengan menggunakan standar deviasi. Dimana X jumlah jam mengajar dalam seminggu dikurangi M rata-rata jam mengajar dibagi N dengan jumlah guru dan dikurangi nilai 1. Maka nilai fitness adalah.
(1)
Keterangan:
X
: Jumlah jam mengajar dalam seminggu
M
: Rata-rata jam mengajar
N : Jumlah guru
=
=
= = 0
Nilai fitness , berdasarkan nilai standar deviasi: 0

## 4. KESIMPULAN
Berdasarkan penelitian yang dilakukan, maka diperoleh kesimpulan sebagai berikut:
1) Penelitian ini telah menghasilkan suatu perhitungan menggunakan metode algoritma genetika untuk penjadwalan mengajar.
2) Penerapan metode ini dapat membantu Developer dalam melakukan pengembangan system dalam hal penjadwalan mengajar.
3) Algoritma genetika cukup efektif dan efisien digunakan untuk pembuatan jadwal mengajar dibandingkan dengan cara manual.

## UCAPAN TERIMA KASIH
Peneliti ucapkan terimakasih kepada pihak STIKOM Bali yang telah membiayai penelitian ini.

## DAFTAR PUSTAKA
[1] Anita Desiani. “ Konsep Kecerdasan Buatan ”. ANDI OFFSET. Yogyakarta. 2006
[2] Gary B. Shelly dan Harry J. Rosenblatt. Systems Analysis and Design. Cengage Learning. 2011.
[3] James A. O’Brien. Management Information Systems . McGraw-Hill. 2003.
[4] Suyanto. Algoritma Genetika dalam Matlab. Yogyakarta: Andi Offset. 2005
[5] Goldberg. D.E. Genetic Algorithm in Search , Optimiztion , and Machine Learning . Addison-Weasley Publishing Company, Inc. 1989.
[6] Zbigniew Michalewics, ‘Genetic Algorithms + Data Structure = Evolution Programs’, ed.
Revised and Extended Edition, Springer-verleg Berlin Heidelberg, 1996