## PEMODELAN SISTEM OPTIMASI PENJADWALAN MATAKULIAH DENGAN ALGORITMA GENETIKA

## (COURSE SCHEDULING OPTIMIZATION SYSTEM MODELING WITH GENETIC ALGORITHMS)
Eka Yulia Sari 1) , Dina Yulina Heriyani 2) , dan Titik Rahmawati 3)
1, 2,3) Program Studi Informatika, Fakultas Teknik Universitas Sarjanawiyata Tamansiswa e-mail: eka.sari@ustjogja.ac.id 1) , dina.heriyanj@ustjogja.ac.id 2) , titik.rahmawati@ustjogja.ac.id 3 )

## ABSTRAK
Bertambahnya jumlah mahasiswa yang ditampung serta jumlah kelas yang disediakan oleh Fakultas Teknik UST setiap tahunnya akan mengakibatkan proses penyusunan jadwal perkuliahan akan semakin kompleks dan rumit. Saat  ini  Penyusunan  jadwal  perkuliahan  di  Fakultas  Teknik  UST  masih  dilakukan  secara  manual  dengan menggunakan excel sehingga proses penyusunan jadwal tersebut membutuhkan waktu yang lama sehingga kurang efektif.  Tujuan dari penelitian ini adalah untuk mengatasi permasalahan penjadwalan dengan merancang sebuah model  sistem  optimasi  penjadwalan  mata  kuliah  pada  Fakultas  Teknik  UST. Metode  Optimasi  yang digunakan untuk penjadwalan adalah algoritma genetika. Pada penelitian ini pemodelan dilakukan pada pemodelan sistem dan  pemodelan  penyimpanan  datanya.  Pemodelan  proses  dari  sistem  optomasi penjadwalan  dengan  algoritma genetika dilakukan dengan UML (Unified Modeling Language) yang terdiri dari 3 diagram yaitu Use Case Dia- gram,  Activity  Diagram,  dan  Class  Diagram  sedangkan  pemodelanan  analisis  penyimpanan  datanya menggunakan ERD (Entity Relation Diagram). Hasil akhir dari penelitian ini adalah sebuah pemodelan sebagai roadmap dalam  pembangunan  sistem  perangkat lunak  optimasi penjadwalan  matakuliah  dengan  algoritma  ge- netika yaitu berupa Use Case Diagram, Activity Diagram, Class Diagram dan ERD (Entity Relation Diagram). Pada penelitian ini menggunakan 4 hard constraint dan 3 soft constraint yang menjadi batasan dalam memproses penjadwalan dengan algortima genetika.
Kata Kunci: Penjadwalan Matakuliah, Algoritma Genetika, UML (Unified Modeling Language), Hard Constraint, Soft Constraint.

## ABSTRACT
The increasing number of students accommodated and the number of classes provided by the UST Faculty of Engineering each year will result in the process of preparing lecture schedules becoming more complex and com- plicated. At present, the preparation of class schedules at the UST Faculty of Engineering is still done manually using Excel, so the process of preparing the schedule takes a long time, making it less effective. The purpose of this research  is  to  overcome  scheduling  problems  by  designing  a  model  of  the  optimization  system  for  scheduling courses at the UST Faculty of Engineering. The optimization method used for scheduling is a genetic algorithm. In this  study,  modeling  was  carried  out  on  system  modeling  and  data  storage  modeling.  Process  modeling  of  the scheduling optimization system with genetic algorithms is carried out using UML (Unified Modeling Language) which consists of 3 diagrams namely Use Case Diagrams, Activity Diagrams, and Class Diagrams while modeling the analysis of data storage using ERD (Entity Relation Diagrams). The result of this research is modeling as a roadmap in the development of a software system for optimizing course scheduling with genetic algorithms, namely Use Case Diagrams, Activity Diagrams, Class Diagrams, and ERD (Entity Relation Diagrams). In this study, 4 hard constraints and 3 soft constraints are used which are the limitations in processing scheduling with genetic algorithms.
Keywords: Course Scheduling, Genetic Algorithm, UML (Unified Modeling Language), Hard Contraint, Soft Con- straint.

## I. P ENDAHULUAN
enjadwalan  mata  kuliah  disetiap  universitas merupakan  pekerjaan  yang  rumit  dan  kom- pleks  karena  banyak  kendala  dan  aturan- aturan  yang  harus  diperhatikan.  Kendala  tersebut bisa  berupa  jumlah  mata  kuliah,  jumlah  ruangan yang tersedia, jumlah mahasiswa , preferensi dosen
dan  slot  waktu  sehingga  permasalahan  penjad- walan  ini  akan  sulit  dilakukan  jika  menggunakan metode optimasi konvensional[1].Kesulitan dalam menerapkan  metode  optimasi  tradisional  dalam proses penjadwalan dikarenakan masalah penyusu- nan jadwal termasuk kedalam golongan NP-Hard roblem  (nondeterministic  polynomial  time) yang
P
jika  semua  kombinasi  alternatif  diuji  untuk  men- gujinya, waktu yang diperlukan untuk mencari so- lusi akan meningkat tajam [2] .
Penjadwalan  merupakan  hal  yang  sangat penting  dalam  proses  belajar  mengajarkarena kegiatan  Dosen  pengajar  dan  mahasiswa  bergan- tung pada jadwal perkuliahan. Penyusunan jadwal perkuliahan perlu persiapan yang matang dan men- dalam  sehingga  dikemudian  hari  tidak  meng- ganggu  aktifitas  perkuliahan.Penyusunan  jadwal perkuliahan memerlukan waktu yang tidak sedikit untuk  menyusunnya  agar  jadwal  yang  dihasilkan baik dan adil yang memperhatikan batasan-batasan yang ada sehingga proses belajar mengajar berjalan dengan baik, khususnya bagi dosen dan mahasiswa yang mengikuti mata kuliah tersebut.
Apek-aspek yang perlu diperhatikan dalam penjadwalan seperti :1) tidak diperbolehkan terjadi bentrok  jadwal,  2)  ketersediaan  waktu  mengajar dosen,3)  keterbatasan  ruangan  dan  4.)  distribusi mata  kuliah  harus  merata  setiap  minggunya[3]. Permasalahan umum yang perlu diperhatikan pada saat  penjadwalan  yaitu  kemungkinan  dosen mengajar lebih dari satu mata kuliah dan kemung- kinan  jumlah  mata  kuliah  dan  dosen  tidak  seim- bang.
Fakultas Teknik Universitas Sarjanawiyata Tamansiswa( UST)  merupakan salah satu fakultas di  universitas  swasta  di  Yogyakarta.    FT  UST memiliki  3  program  studi  yang  meliputi  Teknik Sipil, Teknik Industri, dan Informatika. Setiap awal semester,  Tim  dari  Fakultas  Teknik  UST  akan memetakan matakuliah, dosen, mahasiswa , waktu dan ruangan yang digunakan untuk membuat jad- wal  perkuliahan.  Penyusunan  jadwal  perkuliahan di  Fakultas  Teknik  UST  masih  dilakukan  secara manual  dengan  menggunakan  excel  sehingga proses  penyusunan  jadwal  tersebut  membutuhkan waktu  yang lama sehingga kurang efektif. Sistem optimasi  penjadwalan  matakuliah  menjadi  solusi dengan  memanfaatkan  optimasi  penjadwalan menggunakan algoritma. Berbagai algoritma opti- masi telah digunakan oleh berbagai peneliti, salah satunya  Algortima  Genetika[4][5].  Algoritma  ge- netika merupakan algoritma optimasi yang bekerja meniru  proses  seleksi  alam  yang  dapat  me- nyelesaikan permasalahan optimasi kompleks dan memiliki model pencarian yang luas.
Berdasarkan  latar  belakang  masalah  terse- but,  peneliti  tertarik  untuk  merancang  sebuah pemodelan sistem optimasi penjadwalan matakuliah di  Fakultas  Teknik  UST  dengan algo-
ritma  Genetika  untuk  mempermudah  pengem- bangan  sistem  penjadwalan  sehingga  mengopti- malisasikan waktu penyusunan jadwal matakuliah. Data  yang  diperoleh  merupakan  data  sekunder berupa  data  penjadwalan  pada  Fakultas  Teknik UST semester genap tahun ajar 2022/2023 .

## II. STUDI PUSTAKA
Ferdinandus  (2021)  mendefinisikan  pen- jadwalan  mata  kuliah  sebagai  aktivitas  pengisian kegiatan  perkuliahan  yang  dilaksanakan  selama seminggu dalam satu hari. Perkuliahan yang terdiri dari dosen, mata kuliah,  mahasiswa, ruang kuliah dan  rencana  pelaksanaannya  diatur  sedemikian rupa sehingga tidak terjadi bentrok selama perkuli- ahan maka jadwal  perkuliahan ini menjadi  sangat penting  sehingga  rutin  dilakukan  setiap  semester. Membuat  rencana  perkuliahan  dalam  sebuah susunan jadwal yang baik pasti akan meningkatkan kualitas dan pelayanan pendidikan [6].
Telah  banyak  penelitian  tentang  optimasi penjadwalan dengan menggunakan algoritma yang berbeda-beda,  seperti  yang  dilakukan  oleh  Agus Rudianto  dkk  (2022)  dalam  penelitiannya  yang berjudul  “Rancang  Bangun  System  Penyusunan Jadwal  Pelajaran  Menggunakan  Algoritma  Ge- netika Berbasis Web”[7]. Pada penelitian ini men- erapkan algoritma genetika untuk mengoptimalkan pembuatan  jadwal  pelajaran  dalam  kegiatan  ad- ministrasi  sekolah  dengan  memanfaatkan  sistem berbasis  web.Penelitian  ini  menemukan  kes- impulan  bahwa  penggunaan  algoritma  genetika memberikan  penjadwalan  pelajaran  yang  cukup baik dan dapat mengoptimalkan penugasan belajar mengajar kepada guru bersertifikat atau tidak ber- sertifikat.
Anggi Andriyadi dkk (2022) juga melakukakan  penelitian  dengan  judul  “Penerapan Algortima Genetika untuk Penjadwalan Sidang dan Seminar  IIB  Darmajaya”[8].  Penelitian  ini  ber- tujuan  untuk  membuktikan  penerapan  algoritma genetika  pada  sistem  penjadwalan  seminar  pro- posal  dan  sidang  skripsi  secara  otomatis  apakah lebih optimal. Hasil dari penelitian ini yaitu dapat disimpulkan  bahwa  sistem  penjadwalan  yang dibangun  menggunakan  algoritma  genetika  dapat mempercepat  proses  kegiatan  penjadwalan  dan mempermudah  mahasiswa  dan  dosen  untuk mengetahui  jadwal  seminar  proposal  dan  sidang skripsi. Penerapan algoritma genetika pada sistem yang  dibangun  pada  penelitian  ini  yaitu  memini- malisir  kesalahan  dan  keterlambatan  proses  pen- jadwalan.
Pada  penelitian  yang  berjudul  “Optimal- isasi Sistem Penjadwalan Mata Kuliah Jurusan Ba- hasa  Inggris  Menggunakan  Algoritma  Genetika (Studi  kasus  Politeknik  Negeri  Surabaya)”  yang dilakukan oleh rasmalia dkk(2022)[9]. Hasil akhir dari penelitian ini yaitu dengan menggunakan sis- tem berbasis web, proses penjadwalan matakuliah semakin optimal dan tidak ada bentrok antar mata kuliah , antar dosen dengan yang lain, serta  antar jam dan waktu perkuliahan.
Penelitian lain yang berjudul “ Membangun Sistem Informasi Penjadwalan dengan Metode Al- goritma  Genetika  pada  Laboratorium  Teknik  In- formatika  Universitas  Muhammadiyah  Maluku Utara”  yang  dilakukan  oleh  Agil  Assagaf  dkk (2018)[10].  Pada  penelitian  ini  menggunakan metode  algoritma  genetika  untuk  optimasi  dalam pembuatan  jadwal  praktikum.  Menurut  penelitian ini,  Parameter-parameter  yang  mempengaruhi proses penjadwalan perkuliahan adalah jumlah in- dividu,  probabiltas  crossover,  probabilitas  mutase serta metode seleksi.

## III. METODE PENELITIAN
Pada penelitian ini, tahapan yang digunakan terlihat pada gambar 1 berikut ini.

## Gambar 1 Tahap Penelitian

## A. Pengumpulan data
Tahap  ini  dilakukan  untuk  menggali  data  apa saja yang digunakan untuk pembuatan sistem dan analisis  algoritma  GA  dalam  pembuatan  sistem penjadwalan  perkuliahan.  Pengumpulan  data  dil- akukan  dengan  metode  observasi  dan  wawancara dengan tim penyusun jadwal perkuliahan Fakultas Teknik UST. Tim penyusun jadwal tersebut mem- butuhkan  waktu  yang  lama  dalam  menyusun  jad- wal perkuliahan sehingga tidak efektif dan efisien. Terkadang  ada  tabrakan  jadwal  antar  matakuliah lain  ataupun  tabrakan  jadwal  dosen  dalam mengajar.  Hasil  obeservasi  dan  wawancara didapatkan  data  sekunder  yang  bentuknya  berupa data  penjadwalan  perkuliahan  Fakultas  Teknik
UST  semester  Genap  2022/2023  yang  terdiri  dari data  mahasiswa, matakuliah, dosen, ruangan, dan sesi perkuliahan serta aturan-aturan dalam penjad- walan.  Data dosen yang diperoleh adalah 45 data, data  ruang  sebanyak  9  ruang,  data  mata  kuliah sebanyak  66  mata  kuliah,  hari  aktif  perkuliahan sebanyak 5 hari, dan ada 5 sesi setiap harinya.

## B. Analisis Kebutuhan
Kendala  yang  dipertimbangkan  pada  penilitian ini  merujuk  pada  [11]  yaitu  mengatur  jadwal dengan memastikan bahwa mata kuliah, dosen, ma- hasiswa,  kelas,  ruang,  hari,  dan  sesi  tidak  terjadi bentrok satu  sama lainnya disetiap periode kuliah dan  memastikan  bahwa  telah  memenuhi  batasan yang  ditetapkan  oleh  administrator  sebelumnya. Pada paper ini, mempertimbangkan aturan sebagai berikut :
a) Tidak  boleh  ada  tabrakan  jadwal  antar matakuliah
b) Tidak boleh ada tabrakan jadwal antar dosen.
c) Tidak  boleh  ada  tabrakan  jadwal  antar  kelas yang diambil mahasiswa
d) Hanya 1 dosen yang mengampu  1 matakuliah dalam 1 kelas yang dapat mengisi ruangan da- lam 1 sesi.
e) Tidak  boleh  tabrakan  jadwal  antar  kelas  teori dan praktik.
f) Jadwal kelas praktikum sudah di tetapkan sebe- lumnya.
Peneliti  juga  memetakan  analisis  kebutuhan fungsional  sistem  yang  mengacu  pada  kebutuhan sistem  yang  diusulkan.  Pada  sistem  penjadwalan dengan  algoritma  genetika  ini  memiliki  1  user utama  yaitu  administrator.  Kebutuhan  fungsional telah dipetakan dalam tabel 1 berikut ini :
Tabel 1. Kebutuhan Fungsional User No Kebutuhan Utama Tujuan 1 Mengelola data matakuliah, ru- angan, sesi, maha- siswa dan dosen Melakukan proses CRUD data sehingga data yang diinputkan ke sistem dipastikan sudah benar. 2 Mengelola data pengampu matakuliah Melakukan proses setting pengampu matakuliah 3. Mengelola hasil penjadwalan dise- tiap semester Melakukan download jadwal yang sudah ber- hasil di susun oleh sistem 4. Mengelola data matakuliah prak- tikum Melakukan setting data matakuliah praktikum yang sudah didapatkan

## dari jadwal penggunaan Laboratorium UST
Setelah  dipetakan  kebutuhan  fungsional  user,  se- lanjutnya ke tahap perancangan sistem.

## C. Perancangan Sistem.
Pada  tahap  perancangan  ini  dilakukan  dengan membuat  rancangan  sistem  dengan  sebuah  UML ( Unified Modeling Language ). UML sebagai alat untuk memodelkan sistem yang berorientasi objek yang menjadikan proses analisis dan design dalam tahap  iteratif.  Tahap iterative tersebut  meliputi  : identifikasi kelas dan objek, identifikasi hubungan antar objek dan kelas serta perincian interface dan implementasinya[12].  Pada  penelitian  ini  akan menggunakan 3 diagram yaitu Use Case Diagram, Activity  Diagram, dan Class  Diagram sedangkan p emodelan basis datanya menggunakan ERD ( En- tity Relation Diagram ).
D. Perancangan Proses Algoritma Genetika.
Penelitian ini menggunakan algoritma genetika untuk proses optimasi penjadwalan. Algoritma ge- netika  merupakan  algoritma  pencarian  numerik yang didasarkan pada cara kerja dari seleksi alam dan  genetik  makhluk  hidup.  Algoritma  ini  biasa digunakan  untuk  menyelesaikan  permasalahan yang  berhubungan  dengan  masalah  pencarian  so- lusi  optimal[13].  Mencari  solusi  optimal  melalui proses iteratif untuk membentuk individu dari pop- ulasi yang merupakan individu bernilai tinggi. So- lusi optimal dihasilkan dengan mencari di antara ti- tik-titik optimal alternatif berdasarkan fungsi prob- abilitas.  Salah  satu  kelebihan  dari  algoritma  ge- netika yaitu sifatnya yang mencari solusi global se- hingga  tidak  mudah  terjebak  dalam  optimasi  lo- kal[14].Prosedur  algoritma  genetik  mengikuti langkah-langkah yang mirip dengan proses evolusi yang terdiri dari proses seleksi, crossover dan mu- tasi.
Awalnya gen dikodekan dalam bentuk kromosom sehingga  dapat  diproses  oleh  algoritma  genetika. Perlu  digaris  bawahi  bahwa  setiap  kromosom mengandung beberapa gen yang mengkodekan in- formasi yang disimpan dalam individu atau kromo- som.  Kemudian  menginisialisasi  populasi  awal dengan  membangkitkannya  secara  acak  untuk mendapatkan  solusi  awal.  Suatu  populasi  terdiri dari  individu-individu  dengan  kromosom  yang terdiri dari sekumpulan gen. Selanjutnya dilakukan evaluasi  populasi  untuk  menentukan  nilai  fitness
dari  setiap  kromosom  sampai  terpenuhi  kriteria berhenti menggunakan persamaan (1) berikut :
𝑓𝑖𝑡𝑛𝑒𝑠𝑠 = ∑ 𝐺 𝑖 𝑃 𝑖 𝑛 𝑖=1 (1)
Keterangan : Fitness  : Nilai fitness dari setiap kromosom 𝐺 𝑖 : Nilai gen ke-i pada kromosom yang die- valuasi.
𝑃 𝑖 : Nilai prioritas perangkat ke-i Selanjutnya, kumpulan kromosom dalam populasi dilakukan seleksi dengan memilih kandidat kromo- som  berdasarkan  nilai  fitness  terbaik.  Kandidat kromosom  yang  terpilih  akan  digunakan  untuk proses  perkawinan  atau  persilangan.Proses  selan- jutnya  adalah crossover atau  persilangan,  dimana informasi  dipertukarkan  antara  dua  kromosom yang  berbeda  untuk  menciptakan  kromosom  baru yang memiliki karakteristik dari kedua kromosom tersebut.  Penelitian  ini  menggunakan single-point crossover , dimana setiap gen pada satu kromosom dipertukarkan dengan gen pada kromosom lain un- tuk  membuat  kromosom  baru  melalui  satu  titik potong.
[15]. Titik potong tersebut dibangkitkan menggunakan sebuah random number dengan ba- tasan 1 sampai n (panjang kromosom). Contohnya pada kasus 2 koromosom yang memeiliki panjang 5 serta random number yang didapatkan adalah 3 , maka gen 1 sampai 3 akan dipotong dengan gen 4 sampai 5. Kemudian gen 1 sampai 3 pada kromo- som pertama akan dilakukan crossover dengan gen 4 dan 5 pada kromosom dua, dan sebaliknya. Ilus- trasi proses crossover menggunakan crossover one point crossover terlihat pada gambar 3 berikut ini.
Gambar 2 Ilustrasi One Point Crossover
Setelah  dilakukan  persilangan,  kromosom  akan melalui  proses  mutasi  untuk  mengubah  nilai  dari suatu gen pada kromosom tersebut. Perubahan nilai dari  satu  atau  lebih  gen  pada  kromosom  tersebut dilakukan secara random dengan interval area pen- carian.  Tujuan  proses  mutasi  adalah  membentuk individu-individu  dengan  kualitas  terbaik  diatas rata-rata  serta  untuk  memperbaiki  kerusakan  gen akibat  proses  crossover[16].  Pada  gambar  3 dibawah merupakan  tahap-tahap optimasi penjad- walan dengan algoritma genetika :

## Gambar 3 Tahap-tahap Proses Penjadwalan dengan
Algoritma Genetika

## IV. HASIL DAN PEMBAHASAN

## A. Perancangan Sistem
Penulis  merancang  use  case  diagram  yang digunakan  untuk  memodelkan  perilaku  sistem dengan mendefinisikan fitur apa saja yang dimiliki sistem  dan  siapa  yang  berhak  menggunakan  fitur tersebut[17].  Berikut  ini  rancangan  use  case  dia- gram  dari  sistem  penjadwalan  matakuliah  dengan algoritma genetika pada Fakultas Teknik UST.

## Gambar 4 Use Case Diagram Sistem Penjadwalan Matakuliah dengan GA
Setelah Use  Case  Diagram dibuat,  Kemudian buat skenario dengan Activity diagram untuk setiap use case diagram. Activity Diagram digunakan un- tuk menggambarkan sistem kerja atau sistem suatu objek  secara  terstruktur.  Pada  artikel  ini,  penulis menambahkan activity diagram pada saat pemben- tukan  jadwal  perkuliahan  setiap  semester  seperti yang ditunjukkan pada Gambar 5 di bawah ini

## Gambar 5 Activity Diagram pada Proses Mengelola Penjadwalan
Selanjutnya,  penulis  membuat  sebuah  logical model dari sistem dengan Class Diagram. Class di- agram berfungsi  untuk memudahkan  dalam menunjukan  bagaimana  skema  dari  arsitektur  sis- tem  yang  dirancang[18].  Class  diagram  sendiri merupakan  alat untuk menggambarkan sistem da- lam  bentuk  kelas  yang  mencakup  status  dan  per- ilaku  dalam  hubungan  antar  kelas.  Berikut  ini rancangan class diagram dari sistem optimasi pen- jadwalan  matakuliah  dengan  algoritm  genetika yang diusulkan oleh penulis :

## Gambar 6 Class Diagram Sistem Penjadwalan Matakuliah dengan GA

## B. Perancangan ERD  (Entity Relation Diagram)
Entity  Relation  Diagram atau  ERD  digunakan penulis untuk merancang database yang digunakan dalam  sistem  optimasi  penjadwalan  matakuliah dengan  algoritma  genetika.  Pada  ERD  akan  di
deskripsikan  data  yang  akan  disimpan  dalam  sis- tem  maupun  batasannya.  Komponen  utama  pada diagram ERD pada umumnya adalah entity set, re- lationship  set,  dan constraints [19].  Berikut rancangan  ERD  yang  digunakan  pada  penelitian ini, terlihat pada gamabr 7 berikut :
Gambar 7 Entity Relation Diagram Sistem Optimasi Penjadwalan dengan GA

## C. Perancangan Penjadwalan dengan Algoritma Genetika
Penjadwalan dilakukan untuk mengalokasikan rangkaian kejadian terbatas sumber daya yang dia- tur untuk memenuhi kendala tertentu. Batasan ter- sebut  dapat  diklasifikasikan  menjadi Hard  Con- straint (harus dipenuhi) dan Soft Constraint (harus dipenuhi). Hard Constraint berarti bahwa kendala ini harus diterapkan dan dipenuhi saat mencari so- lusi penjadwalan yang optimal. Pencarian solusi di- anggap  valid  jika  tidak  ada  hard  constraint  pen- carian solusi pada jadwal yang dilanggar.
Pada penelitian ini, terdapat beberapa bata- san dalam proses pencarian jadwal optimal dengan algoritma genetika yaitu :
1. Hard Constrain
a) Tidak boleh ada bentrok dosen terhadap sesi waktu mengajar.
b) Tidak boleh ada bentrok antar dosen pada ru- ang kuliah tertentu.
c) Tidak boleh ada bentrok antar mahasiswa ter- hadap sesi waktu kuliah dan ruangan kuliah.
d) Tidak boleh ada bentrok matakuliah teori dan praktikum
2. Soft Constrain
a) Diupayakan  untuk  memberi  jeda  1  sesi  jika dalam sehari ada kelas teori dan praktikum.
b) Diupayakan  untuk  mengkosongkan  sesi pukul 11.00-13.00  hari jumat kosong.
c) Diupayakan untuk setiap kelasnya maksimal 4 sesi perkuliahan
Langkah-langkah  pada  algoritma  genetika  yang digunakan pada perancangan sistem optimasi pen- jadwalan matakuliah ini adalah sebagai beikut :

## A. Inisialisasi Kromosom
Pada langkah ini, data yang ada dibentuk men- jadi variabel  yang diperlukan untuk  pembentukan kromosom.  Variabel  ini  berupa:  kode  pengampu mk, kode ruang,  kode hari, dan kode sesi. Variabel kode pengampu terdiri dari kode dosen, kode MK dan kelas. Variabel dosen, kode_mk dan kelas dise- but  gen  dan  gabungan  variabel  kode_mk,  kelas, hari dan kode sesi disebut kromosom. Setiap kro- mosom memiliki solusi, sehingga semakin banyak kromosom  yang  dibuat,  semakin  banyak  solusi yang mungkin.
Pada tabel berikut merupakan ilustrasi gen dan kro- mosom.
Tabel 2. Ilustrasi Gen pada Optimasi Penjadwalan Al-
goritma Genetika kode_pengampu kd_hari kd_sesi kd_ru- ang kd_dosen  kd_mk kls D1 M1 K1 1  S1 R1 D2 M2 K2 2  S2 R2 D3 M3 K3 3  S3 R3 D4 M4 K4 4  S4 R4 D5 M5 K5 5  S5 R5 D6 M6 K6 S6 R6 D n …. M n …. K n … R7
𝑘𝑟𝑜𝑚𝑜𝑠𝑜𝑚 = [𝑃 𝑘𝑝 , 𝐻 𝑘ℎ , 𝑆 𝑘𝑠 , 𝑅 𝑘𝑟 ] (2) Pada  persamaan  2  diatas  menggambarkan  bahwa pada  setiap  kromosom  terdapat  pengampu mengajar pada hari ke- kh , sesi ke- ks , dan ruang ke- kr .

## a. Inisialisasi populasi awal
Pada langkah ini, populasi dibangkitkan secara acak  hingga  membentuk  populasi  awal.   Berikut pseudocode pembangkitan populasi awal yang ter- lihat pada Gambar 8 berikut ini :
Gambar  8  diatas  merepresentasikan  tahapan bagaimana proses pembangkitan popuasi awal dil- akukan. Inisialisasikan dahulu variabel jumlah se- luruh  pengampu,  jam,  hari  dan  ruang  yang  akan digunakan  pada  proses  pejadwalan.  Kemudian acak individu secara random berdasarkan banyak- nya sesi, hari dan ruang sehingga terbentuk sebuah array.
b. Menghitung Fitness
Tahap ini merupakan tahap menghitung nilai fit- ness  dengan  mempertimbangkan  sebuah  batasan- batasan  yang  sudah  ditentukan  (hard  constraint). Nilai fitness yang diharapkan adalah yang memiliki nilai yang paling besar yaitu yang memiliki jumlah pelanggaran  paling  minimum  diantara  yang  lain. Pada gambar 9 berikut ini merupakan pseudocode proses cek nilai fitness.
Gambar 9 Pseudocode Cek Fitness Batasan-batasan yang digunakan untuk menghi- tung nilai fitness yaitu :
a) Tidak boleh ada bentrok dosen terhadap sesi waktu mengajar
b) Tidak boleh ada bentrok antar dosen pada ru- ang kuliah tertentu.
c) Tidak boleh ada bentrok antar mahasiswa ter- hadap sesi waktu kuliah dan ruangan kuliah.
d) Tidak boleh ada bentrok matakuliah teori dan praktikum
Jika batasan-batasan tersebut dilanggar, maka akan menambah variabel pinalti. Dimana variabel pinalti ini digunakan untuk menghitung nilai fitness mas- ing-masing individu. c. Seleksi Pada  tahap  ini,  dilakukan  proses  seleksi  dengan metode  seleksi  rangking.  Pada  metode  seleksi rangking  ini,  nilai  fitness  terkecil  diberi  1,  yang terkecil  kedua  bernilai  2  dan  begitu  seterusnya sampai  yang  terbesar,  dengan  demikian  semakin besar nilai fitness maka rangkinya semakin besar. Nilai tersebut akan diambil sebagai prosentase te- pat yang tersedia. Pada gambar 10 berikut ini meru- pakan pseudocode proses seleksi.
Gambar 10 Pseudocode Proses Seleksi
Nilai fitness dari suatu kromosom menunjukan kualitas  dari  kromosom  dalam  populasi  tersebut. Kromosom  yang  memiliki  nilai  fitness  terkecil akan  menjadi  kromosom  terbaik  dan  mempunyai peluang  yang  besar  untuk  dipilih  menjadi  induk (parent).

## d. Crossover
Pada proses seleksi sebelumnya, akan didapat- kan  parents  yang  akan  digunakan  untuk  proses crossover. Pada penelitian ini menggunakan cross- over one point crossover . Proses crossover sendiri tidak  akan  terlepas  dari  parameter  algoritma  ge- netika yaitu probabilitas crossover.Parameter prob- abilitas ini digunakan untuk mengontrol setiap op- erator  crossover.  Gen-gen  dalam  populasi  men- galami  persilangan  yang  mana  semakin  tinggi probabilitas  persilangan,  semakin  cepat  terbentuk struktur  tunggal  baru  dalam  populasi.  Jika  proba- bilitas  silang  terlalu  tinggi,  satu  kandidat  solusi yang paling mungkin akan menghilang lebih cepat dalam proses pembangkitan ulang.Pada gambar 11 terlihat pseudocode proses crossover.

## Gambar 11 Pseudocode Proses Crossover
Pada  proses crossover ini  dilakukan  perulan- gan dan apabila nilai acak crossover pada populasi kurang dari nilai probabilitas crossover maka akan terjadi  pertukaran  jadwal.  Perulangan  terus  dil- akukan sampai nilai acak bisa melebihi probabilitas crossover.
e. Mutasi
Pada  tahap  mutasi,  hal  ini  dilakukan  dengan mengacak  ulang  komponen  penjadwalan.  Ketika proses mutasi  selesai,  skor fitness  masing-masing individu  dihitung.  Jika  tidak  ada  yang  cocok dengan  batasan-batasan  yang  ditentukan,  proses mutasi diulang.Proses mutasi tergambar pada pseu- docode yang terlihat pada gambar 12 berikut :
Gambar 12 Pseudocode Proses Mutasi
Gambar 12 menjelaskan pseudocode proses mu- tase  pada  algoritma  genetika.  Proses  mutasi  dil- akukan  dengan  mengacak  kembali  penjadwalan untuk jadwal baru yang terbentuk.  Kemudian dil- akukan perulangan untuk populasi. Jika nilai acak kurang dari nilai probabilitas mutase maka kompo- nen  penjadwalan  akan  diganti.  Langakah  terakhir
yaitu  mengecek  kembali  nilai fitness setiap  indi- vidu dengan probabilitas mutase.

## V. K ESIMPULAN
Berdasarkan hasil pembahasandiatas maka pada  penelitian  ini  dapat  diambil  kesimpulan  se- bagai berikut :
1. Masalah penjadwalan matakuliah pada Fakultas Teknik  Universitas  Sarjanawiyata  Tamansiswa dapat dimodelkan sebagai pemodelan sistem opti- masi  penjadwalan  matakuliah  dengan  algoritma genetika.
2. Menghasilkan pemodelan sistem optimasi  pen- jadwalan  matakuliah  yang  dapat  ditindak  lanjuti dengan mengimplementasikan model pada penelitian  ini  sebagai  roadmap  dalam  pem- bangunan sistem perangkat lunak optimasi penjad- walan matakuliah dengan algoritma genetika. 3.  Pada  pemodelan  sistem  optimasi  penjadwalan ini menghasilkan 4 hard constraint dan 3 soft con- straint.
4.  Penelitian  ini  menghasilkan  pemodelan  aliran dan proses sistem dengan UML ( Unified Modeling Language )  yang  terdiri  dari  diagram  yaitu Use Case Diagram, Activity Diagram, dan Class Dia- gram. S edangkan pemodelan basis data untuk sis- tem  optimasi  penjadwalan  dengan  Genetika menggunakan ERD ( Entity Relation Diagram ).

## DAFTAR PUSTAKA
[1]  H. Kanoh and Y. Sakamoto, “Knowledge-based genetic algorithm  for  university  course  timetabling  problems,” Int. J. Knowledge-Based Intell. Eng. Syst. , vol. 12, no. 4, pp. 283–294, 2008, doi: 10.3233/KES-2008-12403.
[2]  T. Birbas, S. Daskalaki, and E. Housos, “School timeta- bling  for  quality  student  and  teacher  schedules,” J. Sched. ,  vol.  12,  no.  2,  pp.  177–197,  2009,  doi: 10.1007/s10951-008-0088-2.
[3]  H. U. A. Hartadi Rudy and V. G, “Perancangan Aplikasi Penjadwalan Mata Kuliah,” J. Bianglala Inform. , vol. 4, no. 1, pp. 31–40, 2016, doi: 10.4324/9781003221296-10.
[4]  H. P. Hariyadi, T. Widiyaningtyas, M. Z. Arifin, and S.
Sendari, “Implementation of Genetic Algorithm to aca- demic  scheduling  system,” IEEE  Reg.  10  Annu.  Int. Conf. Proceedings/TENCON , pp. 2013–2016, 2017, doi: 10.1109/TENCON.2016.7848378.
[5]  X. Chen, R. Yi, and M. Li, “Design and Application of an  Improved  Genetic  Algorithm  to  a  Class  Scheduling System,” pp. 44–59.
[6]  F. Mone and J. E. Simarmata, “Aplikasi Algoritma Ge- netika  Dalam Penjadwalan Mata  Kuliah,” BAREKENG J.  Ilmu  Mat.  dan  Terap. ,  vol.  15,  no.  4,  pp.  615–628, 2021, doi: 10.30598/barekengvol15iss4pp615-628.
[7]  A. Rudianto and I. Muhandhis, “Rancang Bangun Sistem Penyusunan  Jadwal  Pelajaran  Menggunakan  Algoritma Genetika  Berbasis  Web  (study  Kasus  MI  Mahalul Ulum),” J. Syst. Eng. Technol. Innov. , vol. 1, no. 01, pp.
33–37, 2022, doi: 10.38156/jisti.v1i01.14.
[8]  H. Ardiansyah and M. B. S. Junianto, “Penerapan Algo- ritma  Genetika  untuk  Penjadwalan  Mata  Pelajaran,” J. Media  Inform.  Budidarma ,  vol.  6,  no.  1,  p.  329,  2022, doi: 10.30865/mib.v6i1.3418.
[9]  S.  D.  Kristanti,  P.  Studi,  T.  Informatika,  U.  B.  Darma, and  K.  Palembang,  “Optimalisasi  Sistem  Penjadwalan Mata Kuliah Jurusan Bahasa Inggris Menggunakan Al- goritma Genetika (Studi Kasus Politeknik Negeri Sriwi- jaya),” vol. 14, no. 2, pp. 22–31, 2022.
[10] C. Suranto, “Membangun Sistem Informasi Penjadwalan dengan Metode Algoritma Genetika pada Laboratorium
Teknik Informatika UMMU Ternate,” J. Ilm. Ilmu Kom- put. dan Inform. , vol. 1, no. 2, p. 65, 2018.
[11] T. Li, Q. Xie, and H. Zhang, “Design of College Sched- uling Algorithm Based on Improved Genetic Ant Colony Hybrid Optimization,” Secur.  Commun.  Networks ,  vol. 2022, 2022, doi: 10.1155/2022/2565639.
[12] A.  Voutama,  “Sistem  Antrian  Cucian  Mobil  Berbasis Website  Menggunakan  Konsep  CRM  dan  Penerapan UML,” Komputika  J. Sist. Komput. , vol. 11, no. 1, pp. 102–111, 2022, doi: 10.34010/komputika.v11i1.4677.
[13] R.  N.  Kurniawan et  al. ,  “Penjadwalan  Penggunaan Perangkat  Elektronik  Menggunakan  Algoritma  Ge- netika,” vol. 9, no. 5, pp. 2167–2174, 2022.
[14] J. Y. Setiawan, D. E. Herwindiati, and T. Sutrisno, “Al- goritma Genetika Dengan Roulette Wheel Selection dan Arithmetic  Crossover  Untuk  Pengelompokan,” J.  Ilmu
Komput.  dan  Sist.  Inf. ,  vol.  7,  no.  1,  pp.  58–64,  2019, [Online]. Available: https://journal.untar.ac.id/in-
dex.php/jiksi/article/view/5882
[15] J.  Suryaputra,  C.  Lubis,  and  T.  Sutrisno,  “Pemilihan Crossover pada Algoritma Genetika Untuk Program Ap- likasi  Pengenalan  Karakter  Tulisan  Tangan,” J.  Ilmu
Komput.  dan  Sist.  Inf. ,  vol.  6,  no.  1,  pp.  69–72,  2018, [Online]. Available: https://journal.untar.ac.id/in- dex.php/jiksi
[16] I. Hidayat, S. Revo, L. Inkiriwang, and P. A. K. Pratasis, “Optimasi  Penjadwalan  Menggunakan  Metode  Algo- ritma  Genetika  Pada  Proyek  Rehabilitasi  Puskesmas Minanga,” J. Sipil Statik , vol. 7, no. 12, pp. 1669–1680, 2019, [Online]. Available: https://ejour- nal.unsrat.ac.id/v3/index.php/jss/article/view/26145 [17] Ade Hendini,  “PEMODELAN  UML  SISTEM INFORMASI  MONITORING  PENJUALAN  DAN STOK BARANG (STUDI KASUS: DISTRO ZHEZHA PONTIANAK),” J.  KHATULISTIWA  Inform. ,  vol.  IV, no. 2, pp. 107–116, 2016, doi: 10.1145/358315.358387.

## [18] W. Aliman, “PERANCANGAN PERANGKAT LUNAK UNTUK MENGGAMBAR DIAGRAM
BERBASIS  ANDROID,” Syntax  Lit.  J.  Ilm.  Indones. , vol. 6, no. 6, pp. 3091–3098, 2021, [Online]. Available: https://jurnal.syntaxliterate.co.id/index.php/syntax-lit- erate/article/view/1404
[19] M. Larassati, A. Latukolan, A. Arwan, and M. T. Ananta,
“Pengembangan Sistem Pemetaan Otomatis Entity Rela- tionship Diagram Ke Dalam Database,” urnal Pengemb. Teknol.  Inf.  dan  Ilmu  Komput. ,  vol.  3,  no.  4,  p.  4059, 2019, [Online]. Available: http://j-ptiik.ub.ac.id