PERANCANGAN SISTEM PENJADWALAN UJIAN PADA SUATU FAKULTAS DENGAN BEBERAPA JURUSAN DENGAN MENGGUNAKAN ALGORITMA GENETIKA

TELCOMATICS Journal, Vol.I No.I, Dec 2016

PERANCANGAN SISTEM PENJADWALAN UJIAN PADA SUATU FAKULTAS DENGAN BEBERAPA JURUSAN DENGAN MENGGUNAKAN ALGORITMA GENETIKA Suwarno Universitas Internasional Batam Jl. Gajah Mada, Baloi-Sei Ladi, Batam 29422, (0778) 7437111, Fax. (0778)7437112 e-mail: [email protected]

Abstrak This research provides an insight into heuristic scheduling by using Genetic Algorithm. The background is to make students will not have difficulties in learning to prepare their exams and they can perform well. Scheduling is a complex process because it must comply with several constraints at once, within a reasonable process. The research uses sample of exam schedule at University of Surabaya, Engineering faculty, with some majors for school year 1997-1998, even semester. In accordance with the purpose of this research is to implement heuristic concept, that the program scheduling with genetic algorithm could produce a quality schedule in a relatively not too long when compared to the manual method. This research results shows that number of chromosome will determine value of objective function obtained greater but longer time taken, and determine the saddle point obtained vanishingly small, it means faster experiencing a stable condition or a condition where the rate of change of small value does not even exist. In addition, this research provides evidence that crossover-probability parameter is greater then the value of the objective function obtained greater too, and average of consuming time is same. It means more of the crossover process too.

Keywords: Heuristic, Genetic algorithm, objective function

1.

Pendahuluan

Sistem belajar pada sebuah perguruan tinggi sudah berbeda dengan sistem belajar pada SMU. Meskipun menggunakan istilah yang sama, yaitu SKS atau Sistem Kredit Semester, namun memiliki perbedaan utama yaitu setiap siswa SMU pada tingkat kelas tertentu memiliki mata pelajaran yang telah ditentukan oleh pihak sekolah, sedangkan pada perguruan tinggi, setiap mahasiswa boleh mengambil mata kuliah apapun sesuai dengan mata kuliah yang dibuka. Sistem ini akan menguntungkan pihak mahasiswa, dimana memberi kemungkinan lebih luas kepada mahasiswa untuk memilih program menuju suatu jenjang akademik profesi tertentu. Hal ini juga berpengaruh dengan masa studi mahasiswa, dimana masa studi

setiap mahasiswa dapat berbeda, semakin cakap, dan giat belajar mahasiswa tersebut semakin dapat menyelesaikan studi dalam waktu yang singkat, dan sebaliknya semakin malas, maka mahasiswa tersebut akan semakin lama masa studinya. Mahasiswa yang memiliki masa studi normal berarti ia mengambil mata kuliah sesuai dengan mata kuliah wajib pada tiap semester. Pihak fakultas dituntut untuk membuat jadwal ujian yang sesuai dengan kebutuhan mahasiswa. Kebutuhan tiap mahasiswa berbeda, sehingga mata kuliah yang dibuka harus disesuaikan dengan kebutuhan mahasiswa. Setelah mahasiswa melakukan perwalian, maka fakultas akan membuat jadwal ujian yang tidak membuat beban belajar mahasiswa semakin berat, waktu belajar lebih lama, tidak ada mahasiswa yang


memiliki jadwal ujian yang bentrok, tidak melebihi kapasitas yang disediakan, dan dosen pengajar dapat menjaga ujian untuk mata kuliah yang diasuhnya. Jadwal ujian diatur berdasar slot yaitu hari dan jam ujian. Pembuatan jadwal secara umum terbagi atas dua cara, yaitu: pembuatan jadwal secara manual dan terkomputerisasi. Pembuatan jadwal secara manual mempunyai kelemahan pada kecepatan dan ketelitian. Oleh karena itu dipilih cara terkomputerisasi. Pembuatan jadwal secara terkomputerisasi terbagi lagi menjadi dua cara, yaitu: secara exhaustic search yaitu menelusuri semua kemungkinan jadwal yang ada untuk mencari jadwal yang diinginkan dan heuristic yaitu pencarian jadwal namun dengan dipandu oleh sebuah aturan. Exhaustic search walaupun dilakukan dengan komputer yang sangat cepat tetap tidak layak dilakukan karena kemungkinan jadwal yang ada sangat besar sehingga butuh waktu yang lama untuk menemukan jadwal yang diinginkan. Oleh karena itu cara yang dipilih adalah heuristic. Heuristic memiliki banyak metode yang bisa digunakan untuk menyusun jadwal, dan metode yang dipilih adalah Algoritma Genetika. Berdasarkan pertimbanganpertimbangan yang telah diuraikan di atas, maka penulis tertarik untuk melakukan penelitian dengan judul “Program Penjadwalan Ujian Pada Suatu Fakultas Dengan Beberapa Jurusan Dengan Menggunakan Algoritma Genetika”. Penelitian ini menggunakan kasus pada Fakultas Teknik, Universitas Surabaya, dengan beberapa jurusan yaitu: Teknik Elektro, Teknik Kimia, Teknik Industri, Teknik Informatika dan Teknik Manufaktur. Dari latar belakang tersebut, dapat dirumuskan masalah bagaimana membuat program untuk melakukan penjadwalan ujian tanpa melanggar batasan yang diberikan dengan menggunakan metode heuristic yaitu algoritma genetika. Berikut ini constraint atau batasan permasalahan dalam penjadwalan ujian di U: 1. Mahasiswa boleh mengambil mata kuliah apa pun tanpa perlu harus disesuaikan dengan jadwal ujian yang ada, hal ini diimplementasikan

dengan matriks mata kuliah yang boleh atau tidak boleh tabrakan (gambar 1.1.). Matriks ini merupakan matriks yang simetris terhadap diagonal utama.. MK

A

B

C

D

MK

A B

boleh tabrakan tidak boleh tabrakan

C D

gambar 1.1.: Matriks Tabrakan 2. Pengajar yang sama untuk mata kuliah yang berbeda tidak boleh diujikan pada slot yang sama. Gambar 1.2. menunjukkan salah satu kemungkinan dimana mata. kuliah A dan C tidak boleh diujikan pada slot yang sama karena diajar oleh dosen yang sama. MK

Dosen

A

I

B

II

C

I

D

III

gambar 1.2.: Tabel Pengajar Mata Kuliah 3. Jumlah total mahasiswa pada sebuah slot tidak boleh melebihi kapasitas kursi yang disediakan. 4. Jadwal ujian tidak boleh diadakan pada slot dimana dosen pengajar berhalangan. Berikut ini preference atau kondisi yang diinginkan namun boleh tidak dipenuhi, meliputi: 1.

2.

Jadwal untuk tiap jurusan seimbang, tidak boleh ada jurusan tertentu yang memonopoli jadwal ujian. Mata kuliah pada semester yang sama untuk satu jurusan tidak boleh diletakkan pada hari yang sama


3.

4.

A

Libur

Mata kuliah pada semester yang selisih dua untuk satu jurusan tidak boleh diletakkan pada hari yang sama Ujian untuk tiap mata kuliah pada semester yang sama diharapkan untuk diadakan dengan jadwal yang dipisahkan dengan libur (gambar 1.3.). B

Libur

C

Libur

D

gambar 1.3.: Tabel Hari Ujian Mata Kuliah dengan Jurusan dan Semester Sama

Jadi dengan 4 buah constraint dan 4 buah preference di atas maka kapasitas kursi dihitung berdasar jumlah total kursi yang disediakan pada tiap slot, mata kuliah yang diujikan merupakan mata kuliah yang telah diatur berdasar jurusan dan semester sehingga penjadwalan ini tidak mencakup mata kuliah yang diujikan pada beberapa fakultas dan mata kuliah pilihan, dan penjadwalan yang dilakukan hanya mencakup jadwal ujian yaitu hari dan jam ujian, tidak mencakup ruang dan dosen pengawas.

Tujuan yang ingin dicapai dari penelitian ini adalah: 1. Membuat program dengan metode heuristic yaitu algoritma genetika. 2. Menentukan parameter optimal sesuai dengan algoritma genetika berdasarkan beberapa contoh data set. Bagi pengguna program penjadwalan akan memberikan manfaat sebagai berikut: 1.

Penjadwalan ujian dapat dilakukan dalam waktu yang relatif lebih cepat, dan lebih teliti daripada dengan cara manual. 2. Program penjadwalan ujian akan menghasilkan sebuah jadwal yang optimal sesuai dengan algoritma genetika Di samping itu juga akan memberikan manfaat bagi mahasiswa yaitu: 1. 2. 3.

Beban belajar mahasiswa lebih ringan. Waktu belajar mahasiswa lebih panjang. Ujian mata kuliah yang diambil mahasiswa tidak bentrok.

4.

Dosen dapat mendampingi mahasiswa pada saat mata kuliah yang diasuhnya diujikan.

2. Dasar Teori 2.1.

Heuristic

Masalah penjadwalan merupakan masalah Non linear Programming-complete (NP-complete), sebab pembuatan jadwal bersifat sangat kompleks. Banyak ilmuwan ilmu komputer yakin bahwa permasalahan NP-complete sulit dipecahkan karena jika sebuah permasalahan NP-complete dapat dipecahkan dalam waktu polynomial, maka setiap permasalahan NP-complete akan dapat diselesaikan dalam waktu polynomial juga, karena semua permasalah NP-complete memiliki kompleksitas waktu yang sama. Sampai saat ini, belum ada algoritma waktu polynomial yang ditemukan untuk menyelesaikan permasalahan NP-complete. Namun bukan berarti tidak bisa memecahkan permasalahan ini. Untuk membantu memecahkan permasalah NP-complete, metode heuristic dapat digunakan untuk memecahkan permasalahan ini. Heuristic adalah bagian dari metode kecerdasan buatan yang dapat digunakan untuk menemukan solusi dalam waktu yang layak untuk dilakukan tetapi tidak menjamin ditemukannya solusi optimal. Sehingga perbedaan utama dari algoritma dan heuristic adalah jaminan ditemukannya solusi optimal. Perbedaan lainnya adalah heuristic bergantung pada rules of thumb yaitu aturanaturan yang diperoleh dari intuisi, pertimbangan, pengalaman dan sebagainya selain metode yang menggunakan analisis. Walaupun heuristic tidak memberikan jaminan pada ditemukannya solusi optimal, metode ini tetap banyak digunakan. Heuristic dipilih karena lebih baik memperoleh solusi yang kualitasnya cukup baik dalam waktu yang wajar daripada memperoleh solusi terbaik dalam waktu berabad-abad. Untuk memberikan gambaran betapa pentingnya heuristic pada penjadwalan, berikut akan diberikan ilustrasi penyusunan program penjadwalan dengan cara exhaustic search. Program ilustrasi ini menyusun jadwal dengan cara langsung membuat suatu jadwal


2.

secara acak lalu menguji jadwal tersebut apakah melanggar constraint dan menghitung nilai total dari semua preference. Istilah slot yang digunakan berikut ini berarti jam ujian tertentu pada hari tertentu. Misalkan terdapat 184 mata kuliah dan 48 slot maka banyak jadwal yang bisa disusun adalah 184! / (184 48)! + 136! / (136 - 48)! + 88! / (88 – 48)! + 40! 105 = 6.09  10 jadwal. Program ini mampu menghasilkan sebuah jadwal sekaligus menguji constraint dan menghitung nilai -12 preference dalam 10 detik. Berarti total waktu yang diperlukan oleh program ini untuk menghasilkan jadwal yang diinginkan adalah 105 -12 93 6.09  10  10 detik atau 6.09  10 84 detik atau 1.93  10 abad. Dari ilustrasi secara sekilas di atas terlihat pembuatan jadwal dengan cara exhaustic search tidak memadai untuk diterapkan, untuk itu dipilih cara heuristic dengan algoritma genetika.

3.

4.

5.

6.

N

2.2. Algoritma Genetika Seperti yang diungkapkan oleh 2 David E. Goldberg bahwa algoritma genetika merupakan algoritma pencarian yang berdasar pada mekanisme natural selection dan natural genetic. Dari natural selection diambil informasi berupa bit string secara random dan dihasilkan bit string baru yang merupakan hasil dari natural genetic. Terdapat 4 langkah yang ditempuh dalam algoritma genetika antara lain: pengkodean berupa binary representation atau non binary representation, membuat populasi awal dengan n kromosom, menggunakan objective function sebagai tujuan yang ingin dicapai, dan menggunakan probabilistic transition rules bukan deterministic rules. Secara umum terdapat 3 (tiga) operator penting dalam algoritma genetika antara lain: reproduction, crossover, dan mutation. Berikut ini adalah contoh penggunaan algoritma genetika, misalkan mencari nilai maksimum dari fungsi kuadrat, f(x)=x², dengan nilai x terletak pada interval [0,31]. Langkah-langkah pencarian nilai maksimum dari fungsi di atas sebagai berikut: 1.

Menentukan nilai probabilitas crossover dan probabilitas mutation. Misalkan probabilitas crossover  0.2 dan probabilitas mutation > 0.2.

Menentukan batas iterasi maksimum. Batas iterasi maksimum adalah jumlah iterasi yang dilakukan tidak boleh melebihi batas yang telah ditentukan oleh user. Misal batas iterasi maksimum = 20. Berarti jumlah maksimum iterasi yang akan dilakukan adalah 20 kali. Merepresentasikan nilai x menjadi kode bit. Kode bit terdiri atas 2 (dua) macam digit yaitu 0 dan 1, sehingga nilai x dapat digantikan dengan kode bit 00000 sampai 11111. Membuat populasi awal dengan jumlah 4 (empat) kromosom secara acak, yaitu 01101, 11000, 01000, 10011 Menentukan objective function, yaitu f(x)= x². Maka tujuan yang ingin dicapai adalah mencari nilai x hingga f(x) menghasilkan nilai yang tertinggi. Melalui proses reproduction dihasilkan sejumlah nilai f(x) dengan memberikan nilai x sesuai populasi x. Popul

x

f(x)

fi

f

o asi

fi f

. Awal

Actual

Count

1

01101

13

169

0.14

0.58

1

2

11000

24

576

0.49

1.97

2

3

01000

8

64

0.06

0.22

0

4

10011

19

361

0.31

1.23

1

1.00

4.00

4.0

Total

117 0

Rata-rata

293

0.25

1.00

1.0

Maksimum

576

0.49

1.97

2.0

7.

8.

Setelah proses reproduction, dilanjutkan dengan pengambilan nilai probabilitas secara acak. Jika nilai probabilitas yang didapatkan berada pada interval probabilitas crossover maka proses crossover yang akan dilakukan yaitu menukar nilai bit pada string yang satu dan yang lain dengan menentukan lebih dulu titik potong atau posisi penukaran (k), nilai k diperoleh dari hasil random antara 1 hingga panjang


string - 1 [1, l-1]. Penukaran dimulai dari posisi bit ke-k+1 hingga panjang string terakhir (l). Contoh :

Repro ductio n

Urutan kode bit

Titik Potong (k)

Populasi baru

x

f(x )

01101

1

2

00101

5

25

11000

2

5

11001

2 5

62 5

A2 = 1100|0

01000

3

4

01010

Hasil crossover 2 string menghasilkan:

1 0

10 0

10011

4

3

10111

2 3

52 9

A1 = 01100

Total

12 79

Ratarata

32 0

Maksi mum

62 5

k=4 A1 = 0110|1

A2 = 11001 k=2 A3 = 01|000 A4 = 10|011 Hasil crossover 2 string menghasilkan: A3 = 01011 A4 = 10000 Reprodu ction

Pasang an (rando m)

Titik Poto ng (k)

Popula si baru

x

f(x)

0110|1

1

4

01100

1 2

144

1100|0

2

4

11001

2 5

625

01|000

3

2

01011

1 1

121

10|011

4

2

10000

1 6

256

Total

1146

Rata-rata

287

Maksim um

625

9.

Jika nilai probabilitas yang didapatkan berada pada interval probabilitas mutation maka proses mutation yang akan dilakukan, yaitu mengubah nilai bit dari 0 ke 1 maupun dari 1 ke 0 pada posisi k. Nilai k diperoleh secara acak dengan nilai antara 1 sampai panjang string (l). Contoh: k=2 A1 = 01101  A1 = 00101 k=5 A2 = 11000  A2 = 11001 k=4 A3 = 01000  A3 = 01010 k=3 A4 = 10011  A4 = 10111

10. Mengambil ½ n kromosom yang dapat menghasilkan nilai objective function tertinggi, misalkan proses crossover yang telah dilakukan maka 2 (dua) kode bit yang diambil adalah 11001 dan 10000. 2 (dua) buah nilai x ini disimpan sebagai kromosom unggul lama, dan dilakukan penyalinan 2 (dua) buah kode bit yang sama, yaitu 11001 dan 10000 sehingga jumlah kromosom dalam sebuah populasi menjadi 2 (dua), n=2. 11. Ulangi langkah 5 (lima) sampai dengan 8 (delapan). Lakukan proses crossover atau mutation sesuai nilai probabilitas terhadap populasi tersebut. 12. Ambil ½ n kromosom yang memiliki nilai objective function tertinggi dari populasi dan 2 kode bit yang tersimpan sebagai kromosom unggul lama. Pengambilan ½ n kromosom ini menghasilkan 2 (dua) buah kromosom unggul yang baru. 13. Karena jumlah kromosom dalam populasi tersebut masih ½ n maka harus diciptakan kromosom baru lagi sebanyak ½ n secara acak. Sekarang populasi baru berjumlah n kromosom. 14. Ulangi langkah 5 (lima) sampai dengan 8 (delapan) hingga mencapai kondisi terakhir yaitu nilai objective function maksimum yang dihasilkan mencapai nilai tertinggi sebanyak m kali iterasi, atau jumlah iterasi mencapai batas iterasi maksimum. m adalah jumlah iterasi yang menunjukkan nilai objective function yang sama untuk sekian iterasi.


Penerapan algoritma genetika dalam bidang penjadwalan ujian ini, allele yang dilakukan berupa non pengkodean binary representation, tepatnya table representation yaitu pengkodean berupa tabel. Jadi kromosom tersebut berupa jadwal ujian seperti yang digambarkan pada gambar 2.1. di bawah ini:

5.

JADWAL UJIAN KodeMK

Semester

Jumlah Mhs

Hari

Jam

IF0001

2

55

1

1

IF1001

1

50

2

2

IF4002

1

60

1

2

TM0003

2

50

1

2

TM1040

2

40

1

1

TM2240

1

40

2

1

6.

kuliah, semester, jumlah mahasiswa, hari dan jam ujian. Reproduction: mengambil sejumlah jadwal yang memiliki nilai objective function terbaik dari populasii dan populasii-1 sebanyak ½ n, dan simpan sebagai populasii-1. Lakukan penyalinan populasii-1 sebagai populasii dan lakukan proses crossover atau mutation terhadap populasii berdasar nilai probabilitas yang dibangkitkan secara random. Karena populasii masih berjumlah setengah kali jumlah populasi awal maka harus dibuat sejumlah jadwal yang baru sebanyak ½ n secara acak sehingga populasii berjumlah n jadwal. Lakukan proses ke-2 sampai proses ke-5 hingga mencapai kondisi berakhir. Kondisi berakhir ditentukan berdasar jika memenuhi batas iterasi atau sudah tidak memiliki perubahan nilai selama beberapa kali iterasi. Dari tiap iterasi diambil sebuah jadwal dengan nilai objective function terbaik dari satu generasi.

3. Analisis, Desain dan Implementasi Gambar 2.1.: Kromosom Terdiri Atas 6 Allele Langkah-langkah yang dilakukan dalam algoritma genetika sebagai berikut: 1.

2.

3.

4.

Inisialisasi awal adalah menciptakan sebuah populasi yang terdiri atas n kromosom. Kromosom berupa jadwal ujian. Tiap jadwal diurutkan berdasar kode mata kuliah. Cari sebuah jadwal yang masih melanggar constraint atau belum memenuhi ketentuan preference dan tentukan mata kuliah mana yang akan diubah hari dan jam ujiannya. Posisi mata kuliah ini disebut sebagai titik potong. Pengambilan nilai probabilitas secara acak untuk menentukan apakah jadwal tersebut akan dilakukan proses crossover atau mutation. Jika proses crossover yang dilakukan maka cari pasangan jadwal lain dengan titik potong sama. Record yang ditunjuk oleh titik potong tersebut pada kedua jadwal yang terpilih disebut sebagai pasangan allele pada dua buah jadwal. Jika proses mutation yang dilakukan maka tentukan pasangan allele dalam sebuah jadwal dan lakukan penukaran slot. Allele merupakan sebuah record pada suatu jadwal yang berisi kode mata

Sistem 3.1. Analisis Sistem Jadwal ujian dikategorikan sebagai jadwal yang baik apabila dapat menguntungkan mahasiswa sebanyak mungkin. Sangat banyak faktor yang mempengaruhi suatu jadwal yang menguntungkan mahasiswa peserta ujian. Berikut ini beberapa faktor-faktor yang dapat menguntungkan mahasiswa: 1. Dosen pengajar hadir pada saat mata kuliah yang diasuhnya diujikan. Alasan dari hal ini adalah jika terdapat permasalahan dengan soal ujian dapat langsung ditangani oleh dosen yang bersangkutan. Hal lainnya adalah kehadiran dosen pengasuh dapat membantu siswa secara psikologis dalam menghadapi ujian. 2. Dosen pengajar yang hadir saat ujian tidak boleh terpecah konsentrasinya dengan menjaga lebih dari satu mata kuliah pada suatu slot. 3. Dapat diatur mata kuliah apa saja yang tidak boleh terletak dalam satu slot. Hal ini menyebabkan jadwal menjadi fleksibel atau dapat diatur sesuai dengan keinginan mahasiswa. 4. Mata kuliah yang berada pada suatu slot tidak boleh melebihi kapasitasnya. Hal ini mutlak harus


dilakukan karena jika peserta ujian melebihi kapasitas kursi akan menyebabkan kekacauan pada saat ujian dilaksanakan. Kekacauan ini pada akhirnya akan merusak konsentrasi peserta ujian. 5. Mata kuliah dengan jurusan dan semester sama tidak terletak pada satu hari karena kebanyakan mahasiswa mengambil mata kuliah dengan jurusan dan semester yang sama. Mahasiswa mengalami ujian sekali dalam sehari tidak terlalu berat beban belajarnya. 6. Mata kuliah dengan jurusan dan semester sama mendapat selang libur. Hal ini dimaksudkan agar mahasiswa bisa belajar lebih optimal. 7. Mata kuliah dengan jurusan sama dan semester selisih dua tidak sehari supaya mahasiswa yang terlambat dan terlalu cepat mengambil mata kuliah tidak mengalami ujian lebih dari sekali dalam sehari. 8. Jumlah mahasiswa suatu jurusan yang ujian pada suatu hari tidak melebihi porsinya. Hal ini dilakukan agar tidak timbul kecemburuan terhadap suatu jurusan yang dominan pada hari tertentu. Sebagai perbandingan berikut ini analisis jadwal ujian semester genap 1997-1998 jurusan Teknik Informatika. Ujian ini diselenggarakan selama sebelas hari. Untuk faktor semester dan jurusan sama tidak boleh sehari ditemukan dua kasus yaitu: 1. Mata kuliah semester empat berjumlah tujuh mata kuliah, tiga diantaranya diujikan pada hari Jumat minggu I. Padahal tujuh mata kuliah ini bisa diujikan pada tujuh hari yang berbeda. 2. Mata kuliah semester dua berjumlah tujuh mata kuliah, dua diantaranya diujikan pada hari Kamis minggu I. Padahal tujuh mata kuliah ini bisa diujikan pada tujuh hari yang berbeda. Dua kasus ini menyebabkan mahasiswa semester empat dan dua mendapatkan beban belajar lebih berat pada saat mendapat ujian lebih dari sekali dalam sehari. Untuk faktor semester dan jurusan sama diberi selang libur ditemukan dua kasus: 1. Mata kuliah semester satu berjumlah lima mata kuliah, empat diantaranya diujikan pada hari yang berurutan dari Senin minggu II sampai Kamis

minggu II. Padahal lima mata kuliah ini bisa diujikan tanpa ada mata kuliah yang diujikan secara berurutan. 2. Mata kuliah semester lima berjumlah tiga mata kuliah, dua diantaranya diujikan pada hari yang berurutan dari Rabu minggu II sampai Kamis minggu II. Padahal tiga mata kuliah ini bisa diujikan tanpa ada mata kuliah yang diujikan secara berurutan. Dua kasus ini menyebabkan mahasiswa semester satu dan lima tidak mendapatkan keuntungan dari libur antara dua ujian pada hari yang berurutan. Pada faktor mata kuliah dengan jurusan sama dan selisih dua semester ditemukan satu mata kuliah semester empat sehari dengan satu mata kuliah semester enam pada Selasa minggu II. Hal ini menyebabkan mahasiswa semester enam harus mengalami ujian dua kali jika mengambil mata kuliah semester empat di atas.

3.2. Desain dan Implementasi Sistem 3.2.1.

Perancangan Basis Data

Untuk program pembuatan jadwal ini diperlukan data untuk diolah, untuk itu diperlukan sebuah basis data untuk ditulis, dibaca dan diubah. Dengan adanya basis data ini pemakai dapat dengan mudah memanipulasi data yang akan dipergunakan. Oleh karena itu progam ini tidak statis karena bisa memperoleh input data yang berbedabeda sesuai keinginan pemakai.

DOSEN Tabel ini digunakan untuk menyimpan data semua dosen sebuah fakultas.

NAMA

TYPE

PANJANG

KODE_DSN (PK)

char

4

NAMA_DSN

char

35

MATA KULIAH Tabel ini digunakan untuk menyimpan data semua mata kuliah yang dimiliki oleh sebuah fakultas. NAMA

TYPE

PANJANG

KODE_MK (PK)

char

6

NAMA_MK

char

35


SEMESTER

numeric

2

KAPASITAS Tabel ini digunakan untuk menyimpan data banyak kursi mahasiswa yang bisa ditampung untuk tiap hari pada jam ujian tertentu.

MATA KULIAH BERTABRAKAN

YANG

Tabel ini digunakan untuk menyimpan data dua mata kuliah yang bertabrakan dengan jumlah mahasiswa terkait dengan kedua mata kuliah tersebut.

NAMA

TYPE

PANJANG

KODE_MK1 (PK)

Char

6

NAMA

TYPE

PANJANG

HARI_KE (PK)

numeric

2 6

numeric

1

KODE_MK2 (PK)

char

JAM_KE (PK) KAPASITAS

numeric

4

JUM_MHS

numeric

3

PENGAJAR MATA KULIAH

Model Penjadwalan Algoritma Genetika Pemeriksaan Constraint

3.2.2.

Tabel ini digunakan untuk menyimpan data pengajar mata kuliah pada kelas paralel tertentu. Tiap kelas paralel dapat diajar oleh satu atau beberapa dosen.

NAMA

TYPE

PANJANG

KODE_MK (PK)

char

6

KP

char

2

KODE_DSN (PK)

char

4

DOSEN ABSEN Tabel ini digunakan untuk menyimpan data pada hari dan jam ke berapa dosen pengajar berhalangan untuk menjaga ujian.

NAMA

TYPE

PANJANG

KODE_DSN (PK)

char

4

HARI_KE (PK)

numeric

2

JAM_KE (PK)

numeric

1

JUMLAH PESERTA MATA KULIAH Tabel ini digunakan untuk menyimpan data jumlah mahasiswa untuk kode mata kuliah tertentu.

NAMA

TYPE

PANJANG

KODE_MK (PK)

char

6

JUM_MHS

numeric

3

Dengan

Constraint adalah syarat yang tidak boleh dilanggar dalam pembuatan jadwal. Masingmasing constraint memiliki cara pengecekan yang berbeda. Pemeriksaan constraint dilakukan guna mengetahui apakah perubahan jadwal untuk mata kuliah tertentu boleh dilakukan atau tidak, dan juga untuk mengetahui apakah ada mata kuliah yang melanggar constraint, yaitu: CONSTRAINT 1 : Bertabrakan Pemeriksaan constraint I adalah constraint tabrakan, yaitu untuk memeriksa apakah ada mata kuliah terletak pada slot yang sama dengan pasangannya dalam list tabrakan. CONSTRAINT 2 : Melebihi Kapasitas Pemeriksaan constraint II adalah constraint kapasitas pada slot yang disediakan, yaitu untuk memeriksa apakah ada sebuah slot yang digunakan oleh mata kuliah yang terletak pada slot itu hingga melebihi kapasitasnya. CONSTRAINT 3 : Diujikan Pada Slot Yang Dilarang Pemeriksaan constraint III adalah constraint mata kuliah diujikan pada hari dan jam yang tidak diperbolehkan karena dosen berhalangan menjaga pada hari dan jam tersebut.

Preference Preference sebagai syarat yang boleh dilanggar harus mempunyai mekanisme untuk menunjukkan berapa banyak syarat ini dipenuhi atau dilanggar. Untuk itu tiap


preference harus mempunyai fungsi untuk mengembalikan nilai preference itu pada suatu jadwal. Gabungan dari semua nilai preference merupakan objective function.

PREFERENCE 1 : Jurusan Berimbang Nilai preference jurusan seimbang ditentukan berdasar jumlah peserta mata kuliah jurusan tertentu pada hari tertentu dibandingkan dengan jumlah mahasiswa ideal pada hari tertentu sesuai dengan jurusannya. Jumlah mahasiswa ideal diperoleh berdasar rasio. Jika melebihi jumlah mahasiswa ideal berarti dianggap belum memenuhi preference jurusan seimbang, dan akan diberikan nilai semakin banyak yang melebihi jumlah ideal maka semakin kecil nilai preference yang dihasilkan.

PREFERENCE 2 : Ujian Jurusan Dan Semester Sama, Sekali Dalam Sehari Nilai preference ujian jurusan dan semester sama, sekali dalam sehari dihitung berdasar pada hari tertentu, untuk suatu jurusan ujian berapa kali. Jika setiap hari satu ujian maka nilai preference yang diperoleh semakin tinggi, sebaliknya jika dalam satu hari terdapat beberapa ujian maka nilai semakin rendah.

PREFERENCE 3 : Ujian Jurusan Dan Semester Sama, Mendapatkan Selang Libur Nilai preference selang libur ditentukan banyaknya pasangan mata kuliah dengan jurusan dan semester sama yang memiliki selisih hari sama lebih besar satu. Jika semakin banyak maka nilai semakin tinggi.

PREFERENCE 4 : Ujian Jurusan Sama Dan Semester Selisih Dua, Tidak Sehari Penilaian preference ini akan memberikan nilai yang lebih baik jika menemukan pasangan mata kuliah dengan jurusan sama dan semester selisih dua dan tidak terletak pada satu hari.

POPULASI AWAL Populasi awal berupa sekumpulan jadwal dengan 2 sifat apakah sudah tidak

melanggar constraint atau melanggar constraint.

MENGUMPULKAN MATA KULIAH YANG MELANGGAR CONSTRAINT Untuk populasi awal yang melanggar constraint maka untuk menentukan kromosom mana yang hendak dilakukan crossover atau mutation, akan dilakukan pengecekan dari setiap kromosom apakah ada yang melanggar constraint, yang dikumpulkan menjadi sebuah list.

MENGUMPULKAN MATA KULIAH YANG TIDAK MEMENUHI PREFERENCE Jika populasi awal sudah tidak melanggar constraint, maka yang harus dilakukan adalah mencari kromosom atau jadwal yang akan diproses berdasar ketentuan preference yang ada. Terdapat 4 (empat) macam preference, masingmasing akan diproses secara acak, sehingga tiap preference pasti pernah dilakukan.

CEK PREFERENCE UJIAN SEMESTER DAN JURUSAN SAMA, SEKALI DALAM SEHARI Pengecekan preference ini akan menghasilkan daftar mata kuliah semua jurusan pada sebuah jadwal berupa list Prefs, yang hari ujiannya sama dengan mata kuliah lainnya yang satu semester dan jurusan.

CEK PREFERENCE UJIAN JURUSAN DAN SEMESTER SAMA, MENDAPATKAN SELANG LIBUR Pengecekan preference ini akan menghasilkan daftar mata kuliah yang ujiannya tidak memiliki selang libur dari mata kuliah yang lainnya dengan syarat pada semester dan jurusan sama.

CEK PREFERENCE UJIAN JURUSAN SAMA DAN SEMESTER SELISIH DUA, TIDAK SEHARI Pengecekan preference ini dilakukan dengan cara mengumpulkan mata kuliah yang hari ujiannya sama, namun memiliki selisih semester sama dengan 2 (dua) pada jurusan yang sama.


CEK PREFERENCE BERIMBANG

JURUSAN

Pengecekan preference jurusan seimbang akan menghasilkan kumpulan mata kuliah yang menyebabkan jadwal ujian untuk tiap jurusan tidak seimbang. Jurusan seimbang berarti tidak ada jurusan yang memonopoli dalam satu hari. Penilaian ini berdasar jumlah mahasiswa tiap jurusan dibanding dengan jumlah kursi yang disediakan.

Proses mutation akan melakukan penukaran dua buah slot pada sebuah jadwal, maka perubahan nilai objective function hanya terjadi pada jadwal tersebut.

NATURAL GENETIC Dalam satu generasi atau iterasi, semua kromosom atau jadwal akan mengalami satu kali crossover atau satu kali mutation.

MENUKAR HARI DAN JAM UJIAN

NATURAL SELECTION

Dalam proses crossover dan mutation, yang dilakukan adalah penukaran hari dan jam ujian pasangan allele.

Natural selection atau seleksi alam, merupakan proses pengambilan jadwal yang memiliki nilai objective function tertinggi sebanyak setengah kali jumlah populasi awal. Pengambilan nilai objective function tertinggi dilakukan berdasar populasi yang aktif, dan populasi lama terbaik yang berjumlah setengah kali jumlah populasi awal. Populasi lama ini sudah mewakili populasi-populasi sebelumnya yang memiliki nilai objective function tertinggi. Sehingga akan berpengaruh terhadap proses natural selection, yaitu yang terbaik yang akan bertahan.

PROBABILITAS RANDOM Bilangan random diambil sebanyak 4 digit, guna menentukan proses crossover atau mutation.

TITIK POTONG Titik potong pada sebuah jadwal dapat dicari berdasar list Prefs yang telah diperoleh. List Prefs merupakan kumpulan mata kuliah pada sebuah jadwal. Berdasar kode mata kuliah dapat ditentukan titik potong pada kromosom pertama.

KONDISI BERAKHIR Algoritma genetika akan berhenti jika memenuhi salah satu dari beberapa kondisi, antara lain: mencapai batas maksimum iterasi, selisih nilai objective function antar kromosom dalam sebuah populasi sama, atau tidak adanya peningkatan nilai sebanyak n kali iterasi.

CROSSOVER Proses crossover merupakan proses penukaran dua buah slot pada dua buah jadwal. Penukaran melibatkan dua buah jadwal, sehingga memberikan pengaruh perubahan nilai terhadap kedua jadwal tersebut.

MUTATION

PROSES GENETIKA Proses genetika merupakan proses utama yang dilakukan dalam mengolah sejumlah jadwal dalam sebuah populasi hingga mencapai kondisi akhir. Algoritma Genetika 1. repeat 2. generasi  generasi+1 3. natural genetic 4. if generasi  BatasGen then 5. natural selection 6. natural genetic 7. if populasi awal memenuhi constraint then 8. Populasi  tambahkan Jadwal baru yang tidak melanggar constraint sebanyak n/2 ke dalam Populasi 9. else


10. Populasi  tambahkan Jadwal baru yang melanggar constraint sebanyak n/2 ke dalam Populasi 11. natural selection 12. if populasi awal memenuhi constraint then 13. Populasi  tambahkan Jadwal baru yang tidak melanggar constraint sebanyak n/2 ke dalam Populasi 14. else 15. Populasi  tambahkan Jadwal baru yang melanggar constraint sebanyak n/2 ke dalam Populasi 16. KeteranganPopulasi  isikan kembali KeteranganPopulasi berdasar Populasi yang baru 17.until kondisi berakhir

4. Analisis dan Evaluasi Hasil 4.1. Analisis Parameter Program

Optimal

Analisis parameter ini didasarkan pada nilai objective function yang diperoleh pada lampiran Tabel Nilai Objective Function. Parameter program dengan algoritma genetika meliputi jumlah kromosom, dan probabilitas crossover. Analisis parameter jumlah kromosom dilakukan dengan n mengambil jumlah kromosom = 2 , n = 2,3,4 atau jumlah kromosom = 4,8,16. Sedangkan analisis parameter probabilitas crossover dengan mengambil nilai probabilitas crossover mulai dari 0.1, 0.2, 0.3, .. 0.9. Nilai objective function pada Lampiran Tabel Nilai Objective Function merupakan nilai rata-rata dari 30 nilai objective function untuk tiap iterasi. Jumlah iterasi adalah 80. Berikut ini gambar 4.1. adalah tabel rata-rata nilai objective function dengan mengambil nilai awal (nilai pada iterasi ke-0) dan akhir (nilai pada iterasi ke-80).

Jumlah 4

8

16

Kromosom Probabilita s Crossover

Nilai Awal

Nilai Akhir

Nilai Awal

Nilai Akhir

Nilai Awal

Nilai Akhir

0.1

260 5

2717

261 5

2738

2632

2751

0.2

260 5

2728

261 5

2748

2632

2756

0.3

260 5

2733

261 5

2756

2632

2763

0.4

260 5

2738

261 5

2754

2632

2768

0.5

260 5

2742

261 5

2760

2632

2774

0.6

260 5

2740

261 5

2766

2632

2774

0.7

260 5

2747

261 5

2769

2632

2777

0.8

260 5

2754

261 5

2772

2632

2777

0.9

260 5

2756

261 5

2770

2632

2778

TOTAL

234 45

24655

235 35

24833

23688

24918

RATARATA

260 5

2739

261 5

2759

2632

2769

MAKSIMA L

260 5

2756

261 5

2772

2632

2778

gambar 4.1.: Tabel Nilai Objective Function Tertinggi

Dari tabel di atas dapat diketahui bahwa semakin banyak jumlah kromosom, nilai rata-rata dan nilai maksimal yang dicapai semakin meningkat. Peningkatan nilai objective function maksimal awal yaitu dari 2605 menjadi 2615 adalah 10 point, dan dari 2615 menjadi 2632 adalah 17 point. Peningkatan nilai objective function maksimal akhir yaitu dari 2756 menjadi 2772 adalah 16 point, dan dari 2772 menjadi 2778 adalah 6 point. Semakin banyak jumlah kromosom nilai awal semakin meningkat, dan semakin banyak jumlah kromosom nilai akhir juga mengalami peningkatan, namun peningkatan nilai akhir akan semakin rendah yaitu dari 16 point menjadi 6 point. Jumlah kromosom juga berpengaruh terhadap waktu yang ditempuh, semakin banyak jumlah kromosom waktu yang ditempuh semakin banyak. Untuk kasus ini, penambahan waktu yang ditempuh adalah dua kali. Jadi jumlah kromosom makin banyak maka nilai objective function maksimal akhir yang diperoleh semakin tinggi, namun waktu yang ditempuh makin lama. Dari tabel di atas juga dapat diketahui bahwa semakin tinggi nilai probabilitas crossover


menunjukkan semakin meningkat nilai akhir yang diperoleh. Berdasarkan lampiran grafik contoh kasus dapat juga dibuat tabel rata-rata saddle point (gambar 4.2.) yaitu tabel titik dimana grafik tidak mengalami penambahan nilai yang begitu besar atau penambahan nilai stabil.

Jumlah Kromosom

populasi dengan jumlah kromosom 8 akan mencapai nilai akhir dengan waktu setengah kali dari populasi dengan jumlah kromosom 16 meskipun populasi dengan 16 kromosom ini memiliki nilai akhir yang lebih tinggi, sebab kenaikan waktu sebanding dengan kenaikan jumlah kromosom, yaitu jumlah kromosom berjumlah 2 kali dari sebelumnya maka didapat waktu yang ditempuh juga 2 kali dari sebelumnya.

4.2. Evaluasi Hasil Probabilitas Crossover 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9

TOTAL RATA-RATA MAKSIMAL

4

8

16

38 29 54 39 48 46 61 67 47

29 29 29 44 51 37 40 41 60

24 25 40 32 31 44 44 51 35

42 9 48 67

36 0 40 60

32 6 36 51

gambar 4.2.: Tabel Saddle Point

Tabel rata-rata saddle point di atas diperoleh dengan menggunakan populasi awal tanpa melanggar constraint. Dari tabel saddle point di atas dapat diketahui perkiraan pada iterasi ke berapa sebuah grafik akan kurang mengalami perubahan. Perkiraan ini diperoleh dari nilai rata-rata saddle point pada tiap jumlah kromosom dengan nilai probabilitas dari 0.1 hingga 0.9. Populasi dengan jumlah kromosom=4 akan mencapai saddle point pada iterasi ke-48, populasi dengan jumlah kromosom=8 akan mencapai saddle point pada iterasi ke-40, populasi dengan jumlah kromosom=16 akan mencapai saddle point pada iterasi ke-36. Populasi dengan jumlah kromosom=16 memiliki nilai rata-rata saddle point paling kecil, maka dapat disimpulkan semakin banyak jumlah kromosom maka saddle point semakin kecil, berarti grafik semakin cepat mencapai kondisi mendatar atau tingkat perubahan nilai objective function kecil bahkan tidak ada. Dari hasil analisis kedua tabel di atas maka dapat disimpulkan parameter optimal adalah jumlah kromosom=8, dan probabilitas crossover=0.9, karena dilihat dari segi waktu,

Jadwal yang dihasilkan dievaluasi dari dua segi yaitu: contraint dan preference.

Evaluasi pada Constraint Pada pembuatan jadwal ini jadwal tidak pernah melanggar constraint kecuali populasi awal sudah melanggar constraint, namun jadwal dengan nilai objective function tertinggi bisa tidak melanggar constraint dengan syarat telah diulang sebanyak x kali generasi. Adanya hasil jadwal yang masih melanggar constraint dapat disebabkan pula oleh banyaknya batasan yang harus dipatuhi.

Evaluasi pada Preference Di bawah ini akan diberikan evaluasi hasil dari algoritma genetika melakukan optimasi meningkatkan nilai dari tiap preference. Untuk evaluasi di bawah akan menggunakan 2 jenis populasi yaitu populasi dengan 16 kromosom dan probabilitas crossover =0.9, dan populasi dengan 32 kromosom dan probabilitas crossover=0.4. Pengambilan contoh dengan dua populasi di atas berdasarkan hasil Tabel Nilai Objective Function Tertinggi dimana diambil dua jadwal tertinggi, yang masingmasing merupakan anggota 2 populasi yang berbeda seperti yang telah ditulis di atas. Kedua jadwal ini dibandingkan dengan jadwal yang dihasilkan pada saat populasi awal. Berikut daftar nilai preference untuk jadwal dengan nilai objective function tertinggi pada populasi 16 kromosom, dan probabilitas crossover=0.9:

Jenis Preference

Populasi Awal

Populasi ke-1024

Jurusan Berimbang Jurusan dan Semester Sama diujikan pada hari yang berbeda Jurusan dan Semester Sama diujikan dengan selang libur Jurusan Sama dan Semester Selisih Dua diujikan pada hari yang berbeda

769 805

774 905

389

440

679

696

TOTAL

2642

2815

Berikut daftar nilai preference untuk jadwal dengan nilai objective function tertinggi pada


populasi 32 kromosom, dan probabilitas crossover=0.4: Populasi Populasi Jenis Preference Awal ke-1024 Jurusan Berimbang 769 771 Jurusan dan Semester 805 905 Sama diujikan pada hari yang berbeda Jurusan dan Semester 389 440 Sama diujikan dengan selang libur Jurusan Sama dan 679 700 Semester Selisih Dua diujikan pada hari yang berbeda

TOTAL

2642

2816

nilai preference ini menurun tetapi nilai preference yang lain meningkat.

UJIAN JURUSAN SEMESTER SELISIH SEHARI

SAMA DUA,

DAN TIDAK

Untuk mengevaluasi optimasi preference ini digunakan dua buah pasangan nilai awal dan nilai setelah optimasi yaitu: (679,696) dan (679,700). Dari selisih kedua pasangan terlihat peningkatan 17 dan 18 mata kuliah dengan jurusan sama dan semester selisih dua tidak sehari. Dari pengamatan pada decision cube ternyata angka 700 merupakan angka yang cukup baik karena hanya sedikit kegagalan yang terjadi merupakan kegagalan yang bisa dihindari.

JURUSAN BERIMBANG Untuk mengevaluasi optimasi preference ini digunakan dua buah pasangan nilai awal dan nilai setelah optimasi yaitu: (769,774) dan (769,771). Dari selisih kedua pasangan yaitu 5 (lima) dan 2 (dua), terlihat tidak ada peningkatan kualitas yang berarti. Hal ini bisa terjadi karena selama proses natural genetic terjadi penukaran dua buah slot yang menyebabkan penilaian terhadap preference jurusan seimbang berubah.

UJIAN JURUSAN DAN SEMESTER SAMA, SEKALI DALAM SEHARI Untuk mengevaluasi optimasi preference ini digunakan dua buah pasangan nilai awal dan nilai setelah optimasi yaitu: (805,905) dan (805,905). Selisih antara kedua pasangan nilai sama yaitu 100 (seratus), maka dapat disimpulkan nilai optimal untuk preference ini dicapai pada nilai 905, walaupun ada kemungkinan meningkat namun harus dilakukan hingga generasi berikutnya, tetapi tidak menutup kemungkinan nilai preference ini menurun tetapi nilai preference yang lain meningkat.

UJIAN JURUSAN DAN SEMESTER SAMA, MENDAPATKAN SELANG LIBUR Untuk mengevaluasi optimasi preference ini digunakan dua buah pasangan nilai awal dan nilai setelah optimasi yaitu: (389,440) dan (389,440). Selisih antara kedua pasangan nilai sama yaitu 51 (lima puluh satu), maka dapat disimpulkan nilai optimal untuk preference ini dicapai pada nilai 440, walaupun ada kemungkinan meningkat namun harus dilakukan hingga generasi berikutnya, tetapi tidak menutup kemungkinan

4.3. Evaluasi Perbandingan Jadwal Manual Dengan Jadwal Hasil Optimasi Menggunakan Algoritma Genetika Jadwal manual merupakan jadwal ujian yang dibuat tanpa menggunakan bantuan komputer seperti yang pada gambar 4.3. yaitu Jadwal UTS-UAS Genap 1997-1998 Jurusan Teknik Informatika. Sebelumnya diasumsikan mata kuliah pilihan pada jurusan Sistem Informasi diletakkan pada semester 9. Sebagai bahan perbandingan adalah jadwal hasil optimasi dengan algoritma genetika yang memiliki parameter jumlah kromosom=32, probabilitas crossover=0.4, dan dilakukan iterasi hingga 100 kali generasi. Populasi awal diciptakan tanpa melanggar constraint. Nilai objective function tertinggi = 477, dan berikut adalah rincian nilai preference yang dicapai:

Jenis Preference Jurusan Berimbang Jurusan dan Semester Sama diujikan pada hari yang berbeda Jurusan dan Semester Sama diujikan dengan selang libur Jurusan Sama dan Semester Selisih Dua diujikan pada hari yang berbeda

TOTAL Berdasarkan rincian nilai preference di atas diketahui preference jurusan seimbang=0 dikarenakan jurusan hanya ada satu.

Nilai 0 225 108 144 477


4.

hari ke-6,7,8,10,11,12. Hal ini dapat menyebabkan mahasiswa akan belajar setiap hari, dan tidak memiliki selang libur untuk mahasiswa yang mengambil mata kuliah semester ke-1,2,4,5,6, dan 9. Ujian Jurusan Sama dan Semester Selisih Dua, Tidak Boleh Sehari.

Hari 1 3 Untuk menganalisis jadwal manual digunakan decision cube seperti pada gambar 4.3. gambar 4.3.: Decision Cube Jadwal Manual Pada jadwal manual akan dianalisis berdasar tiap preference sebagai berikut: 1. Jurusan Berimbang Untuk preference tidak dilakukan sebab hanya ada satu jurusan. 2. Ujian Jurusan dan Semester Sama, Sekali Dalam Sehari

Semester 2 4 9 9

3.

Hari 4 5 7 11

Jumlah Mata Kuliah 2 2 2 2

Dapat disimpulkan masih ada mata kuliah dengan semester sama diujikan pada hari yang sama, yaitu 2 mata kuliah semester 2 diujikan pada hari ke-4, 2 mata kuliah semester 4 diujikan pada hari ke-5, 2 mata kuliah semester 9 diujikan pada hari ke-7, dan 2 mata kuliah semester 9 diujikan pada hari ke11. Seharusnya mata kuliah ini bisa dipindahkan ke hari yang berbeda sehingga tidak memberatkan mahasiswa pada semester 2, 4, dan 9, sebab ia harus belajar untuk dua mata kuliah sekaligus. Ujian Jurusan dan Semester Sama, Mendapatkan Selang Libur Pada jadwal manual nampak sekali ujian dilaksanakan tanpa selang libur, contoh pada mata kuliah semester ke-1 dilaksanakan ujian berturut-turut pada hari ke-7,8,9,10, pada mata kuliah semester ke-2 dilaksanakan ujian pada hari ke-3,4,10,11, pada mata kuliah semester ke-4 dilaksanakan ujian berturut-turut pada hari ke-3,4,5,8,9, pada mata kuliah semester ke-5 dilaksanakan ujian berturut-turut pada hari ke-3,4,9,10, pada mata kuliah semester ke-6 dilaksanakan ujian berturut-turut pada hari ke-3,4,6,7,8, pada mata kuliah semester ke-9 dilaksanakan ujian berturut-turut pada

4

11

Pasangan Semester 1&3 6&8 2&4 4&6 2&4 4&6 5&7 2&4

Pada hari ke-1 terdapat 2 pasangan mata kuliah yaitu mata kuliah semester 1 & 3, 6 & 8. Hari ke-3 terdapat 2 pasangan mata kuliah yaitu mata kuliah semester 2 & 4, 4 & 6. Hari ke-4 terdapat 3 pasang mata kuliah yaitu mata kuliah semester 2 & 4, 4 & 6, 5 & 7. Hari ke-11 terdapat 1 pasang mata kuliah yaitu mata kuliah semester 2 &4. Pasangan semester 2 & 4 sering muncul sehingga mahasiswa yang mengambil mata kuliah semester 2 dan 4 sekaligus akan mengalami beban belajar yang lebih banyak sebab terletak pada hari yang sama. Kasus ini sering dialami oleh mahasiswa yang mengambil terlalu cepat atau terlalu lambat. Oleh karenanya dengan adanya preference ini diusahakan keringanan belajar bagi mahasiswa tersebut. Total pasangan berjumlah 8 (delapan). Untuk menganalisis jadwal hasil optimasi algoritma genetika digunakan decision cube

seperti pada gambar 4.4. gambar 4.4.: Decision Cube Jadwal Hasil Optimasi Algoritma Genetika Pada jadwal hasil optimasi menggunakan algoritma genetika akan dianalisis berdasar tiap preference sebagai berikut: 1. Jurusan Berimbang Untuk preference tidak dilakukan sebab hanya ada satu jurusan. 2. Ujian Jurusan dan Semester Sama, Sekali Dalam Sehari Dari gambar 4.4. dapat diketahui bahwa preference kedua ini terpenuhi dengan baik, dimana tiap mata kuliah pada tiap semester diujikan satu hari satu


kali, tidak ada yang sampai lebih dari satu mata kuliah dalam satu

hari. Jika dibandingkan dengan jadwal manual maka jadwal hasil optimasi lebih unggul dalam memenuhi preference kedua ini. Nilai preference yang telah dicapai yaitu nilai 225 merupakan nilai preference yang sudah optimal. 3. Ujian Jurusan dan Semester Sama, Mendapatkan Selang Libur Pada jadwal manual nampak sekali ujian dilaksanakan tanpa selang libur, contoh pada mata kuliah semester ke-2 dilaksanakan ujian berturut-turut pada hari ke4,5,9,10,11, pada mata kuliah semester ke-4 dilaksanakan ujian pada hari ke-3,4, pada mata kuliah semester ke-5 dilaksanakan ujian berturut-turut pada hari ke10,11,12, pada mata kuliah semester ke-6 dilaksanakan ujian berturut-turut pada hari ke5,6,7,8,9,11,12, pada mata kuliah semester ke-9 dilaksanakan ujian berturut-turut pada hari ke3,4,5,6,7,8,11,12. Hal ini dapat menyebabkan mahasiswa akan belajar setiap hari, dan tidak memiliki selang libur untuk mahasiswa yang mengambil mata kuliah semester ke-2,4,5,6, dan 9. Memang untuk preference ini belum bisa terpenuhi semua sebab ada semester yang memiliki jumlah mata kuliah lebih

besar dari separuh jumlah hari yang tersedia. Jika satu semester memiliki jumlah mata kuliah > 6 maka pasti terdapat mata kuliah yang diujikan pada hari yang berturut-turut. Contoh pada semester 2 memiliki 7 mata kuliah sehingga peletakan hari paling tidak ada satu mata kuliah yang terletak pada hari yang berturut-turut, namun nampak pada gambar 4.3. peletakan ujian semester 2 agak kurang baik, hal ini dapat disebabkan batasan yang diberikan. Semester 4 memiliki 7 mata kuliah, maka hal ini juga berakibat ada 1 ujian yang tidak berselang libur yaitu pada hari ke 3 & 4. Semester 5 yang hanya memiliki 4 mata kuliah namun masih terdapat pasangan mata kuliah yang diujikan pada hari yang berturut-turut yaitu pada hari

Hari 1 3 4 6 8 10 12

4.

Pasangan Semester 2&4 7&9 4&6 2&4 4&6 4&6 2&4 3&5 4&6

10,11,12. Seharusnya mata kuliah pada hari ke 11 tersebut dipindahkan ke hari yang masih tersisa, namun masih harus mempertimbangkan constraint. Semester 6 memiliki 8 mata kuliah maka dapat dipastikan ada ujian tanpa selang libur. Begitu pula pada semester 9 yang memiliki jumlah mata kuliah terbanyak yaitu 9, sehingga pelaksanaan ujian hampir berturut-turut. Pada jadwal manual terdapat 6 semester yang dirugikan yaitu 1,2,4,5,6,9, sedangkan jadwal hasil optimasi terdapat 5 semester yang dirugikan yaitu 2,4,5,6,9. Ujian Jurusan Sama dan Semester Selisih Dua, Tidak Sehari. Pada hari ke-1 terdapat 2 pasangan mata kuliah yaitu mata kuliah semester 2 & 4, 7 & 9. Hari ke-3 terdapat 1 pasangan mata kuliah yaitu mata kuliah semester 4 & 6. Hari ke-4 terdapat 1 pasang mata kuliah yaitu mata kuliah semester 2 & 4. Hari ke-6 terdapat 1 pasang mata kuliah yaitu mata kuliah semester 4 & 6. Hari ke-8 terdapat 1 pasang mata kuliah yaitu mata kuliah semester 4 & 6. Hari ke-10 terdapat 2


pasang mata kuliah yaitu mata kuliah semester 2 & 4, 2 & 5. Hari ke-12 terdapat 1 pasang mata kuliah yaitu mata kuliah semester 4 & 6. Pasangan semester 4 & 6 sering muncul sehingga mahasiswa yang mengambil mata kuliah semester 4 dan 6 sekaligus akan mengalami beban belajar yang lebih banyak sebab terletak pada hari yang sama. Kasus ini sering dialami oleh mahasiswa yang mengambil terlalu cepat atau terlalu lambat. Pada jadwal manual dapat diketahui ada 8 pasang semester yang dirugikan, sedangkan jadwal hasil optimasi terdapat 9 pasang semester, berarti dalam memenuhi preference keempat, jadwal hasil optimasi belum bisa mencapai target. Berdasarkan hasil evaluasi kedua jenis jadwal di atas dapat disimpulkan bahwa jadwal hasil optimasi lebih baik daripada jadwal manual, disamping dari segi waktu yang lebih cepat, juga dalam hal pencapaian target tiap preference.

5.

Kesimpulan

Dari penelitian ini, dapat diambil kesimpulan sebagai berikut: a. Sesuai dengan tujuan dari penelitian ini adalah untuk pengembangan ilmu heuristic, dimana program ini berusaha mengaplikasikan konsep-konsep yang ada pada heuristic, khususnya konsep pemanduan pencarian lokal dengan algoritma genetika. Dengan ini penulis menemukan bahwa program penjadwalan dengan algoritma genetika dapat menghasilkan jadwal yang berkualitas dalam waktu yang relatif tidak terlalu lama jika dibandingkan dengan cara manual. b. Algoritma genetika dapat digunakan untuk menghasilkan jadwal sesuai dengan batasan yang diberikan. c. Parameter jumlah kromosom yang semakin banyak maka nilai objective function yang diperoleh makin besar namun waktu yang ditempuh makin lama. d. Parameter jumlah kromosom juga menentukan saddle point, dimana semakin banyak jumlah kromosom maka saddle point yang diperoleh makin kecil, berarti semakin cepat mengalami kondisi yang stabil atau kondisi dimana tingkat perubahan nilai kecil bahkan tidak ada. e. Parameter probabilitas crossover yang semakin besar maka nilai objective function yang diperoleh makin besar, dan

waktu yang ditempuh rata-rata sama. Nilai probabilitas crossover semakin besar berarti semakin banyak terjadinya proses crossover.

6. Daftar Pustaka 1. Satyabudhi, B, The Contribution of Computer Science Theories to Deterministic Hard-Operational Research Theories, Kristal no. 17, Mei 1998, halaman 47-49 2. Goldberg, David E., Genetic Algorithm in Search, Optimization, and Machine Language, Addisson Wesley Publishing, 1989 3. Henderson, Ken, Database Developer’s Guide with Delphi 2, Sams Publishing (Borland Press), 1996

PERANCANGAN SISTEM PENJADWALAN UJIAN PADA SUATU FAKULTAS DENGAN BEBERAPA JURUSAN DENGAN MENGGUNAKAN ALGORITMA GENETIKA

Recommend Documents