Slamet Datang di era kebodohan: SPK

SPK

BAB I

PENDAHULUAN

1 .1 Latar Belakang

Penjadwalan perkuliahan merupakan suatu hal yang sangat kompleks dan rumit untuk dipecahkan. Kompleksitasnya dapat dilihat dari sisi mahasiswa, dosen yang mengajar, mata kuliah yang diajarkan, waktu perkuliahan, dan juga ruangan untuk melaksanakan perkuliahan tersebut. Kemungkinan-kemungkinan tersebut sangat mempengaruhi kinerja keseluruhan aktifitas akademis dalam suatu kampus yang akhirnya berdampak pada kompetensi kampus tersebut.

Kampus STMIK STIKOM Indonesia memiliki banyak mata kuliah yang ditawarkan setiap semesternya. Pada setiap mata kuliah tersebut terdapat juga banyak jadwal yang ditawarkan kepada mahasiswa. Mahasiswa dan dosen yang terlibat pun cukup banyak. Apalagi adanya kemungkinan satu dosen dapat mengajar lebih dari satu mata kuliah, sebab jumlah kelas dan jumlah dosen tidak seimbang. Sistem penjadwalan yang dilakukan selama ini masih manual sehingga memungkinkan terjadinya tabrakan jadwal antara mata kuliah yang satu dengan mata kuliah lainnya dan untuk dosen yang mengajar di beberapa mata kuliah pun harus diperhatikan jadwalnya agar tidak mengajar dua mata kuliah berbeda di jam dan hari yang sama. Selain itu, harus dipertimbangkan juga ketersediaan kelas sehingga kegiatan belajar dan mengajar dapat dilaksanakan.

Metode Algoritma Genetika dipadukan dengan metode Constraint Satisfaction Problem, dengan kromosom yang dihasilkan metode Algoritma Genetika diproses dengan metode Constraint Satisfaction Problem. Dengan cara ini akan didapat batasan-batasan pada penjadwalan yang harus dipenuhi dapat dijamin tidak terlanggar. Hal ini akan membuat proses heuristic pada Algoritma Genetika menjadi terarah dan membuat keseluruhan proses menjadi lebih efisien.

Untuk mengatasi masalah di atas, dibutuhkan sebuah sistem pendukung keputusan untuk mendukung proses penjadwalan mata kuliah agar jadwal dapat tersusun tanpa adanya kelas atau jadwal mengajar dosen yang bertabrakan satu sama lain. Berdasarkan uraian di atas untuk mengatasi masalah tersebut maka penulis mencoba melakukan penelitian tentang “Sistem Penjadwalan Mata Kuliah dengan Metode Algoritma Genetika dan Metode Constraint Satisfaction Problem di Kampus STIMK STIKOM Indonesia”.

1.2 Rumusan Masalah

Berdasarkan uraian latar belakang di atas maka rumusan masalah dalam penelitian ini adalah “Bagaimana membuat sistem penjadwalan mata kuliah dengan metode Algoritma Genetik dan Metode Constraint Satisfaction Problem di Kampus STIMK STIKOM Indonesia?”

1.3 Batasan Masalah

Melihat luasnya cakupan yang ditemukan dalam tulisan ini serta keterbatasan waktu dan pengetahuan penulis maka agar pembahasan tidak menyimpang dari tujuan, dilakukan pembatasan masalah sebagai berikut:

1. Sistem ini menggunakan metode Algoritma Genetik dan Constraint Satisfaction Problem

2. Lokasi yang digunakan dalam penelitian ini adalah Kampus STIMK STIKOM Indonesia.

3. Sistem tidak memperhatikan proses pergantian semester dan tidak memperhatikan mata kuliah yang ditawarkan.

Batasan masalah yang digunakan dalam sistem ini adalah sebagai berikut:

1. Satu dosen dapat mengajar di dua kelas atau lebih namun pada jam yang berlainan.

2. Satu dosen dapat mengajar banyak mata kuliah, dan satu mata kuliah dapat diampu banyak dosen.

3. Satu mata kuliah memiliki banyak kelas, dan satu kelas diampu satu dosen.

4. Satu ruang diisi dengan satu kelas pada satu waktu.

5. Perkuliahan berlangsung dari pukul 07.30 – 22.00 WITA dari hari Senin – Sabtu.

1.4 Manfaat dan Tujuan

Manfaat dari penelitian ini adalah untuk membantu bagian akademik dalam membuat penjadwalan mata kuliah yang sesuai dengan aturan-aturan yang tersedia. Tujuan dari penelitian ini adalah agar jadwal mata kuliah dapat tersusun tanpa adanya tabrakan antara jadwal mata kuliah yang satu dengan mata kuliah yang lain dan jadwal dosen tidak ada yang bertabrakan satu sama lain.

1.5 Analisa Kebutuhan

1.5.1 Analisis Sistem

Sistem Penjadwalan Mata Kuliah dapat membantu bagian akademik dalam proses pembuatan jadwal mata kuliah. Pengguna memberikan data berupa aturan-aturan, jumlah mata kuliah, jam dari mata kuliah, jadwal dosen, dan jumlah ruangan yang tersedia. Setelah itu, sistem akan memberikan alternatif susunan jadwal mata kuliah.

1.5.2 Data yang Dibutuhkan

Dalam pembuatan sistem ini, adapun data yang dibutuhkan adalah:

a. Data Dosen : nama dosen, tempat tgl lahir, alamat, telp.

b. Data Waktu : hari, jam

c. Data Ruang : nama ruang, daya tampung.

d. Data Mata Kuliah : mata kuliah, sks,

e. Data Penjadwalan: mata kuliah, kelas, nama dosen, ruang, hari, jam.

1.5.3 Kebutuhan Fungsional

Fungsi dari sistem ini adalah:

a. Proses login untuk bagian akademik.

b. Proses pengelolaan data dosen, meliputi input, update, dan delete.

c. Proses pengelolaan data kelas, meliputi input, update, dan delete.

d. Proses pengelolaan data mata kuliah, meliputi input, update, dan delete.

e. Proses pengelolaan data penjadwalan, meliputi input dan update.

BAB II

LANDASAN TEORI

2.1. Sistem Pendukung Keputusan

2.1.1. Sistem

Sistem adalah kumpulan objek seperti orang, sumber daya, konsep, dan prosedur yang dimaksudkan untuk melakukan suatu fungsi yang dapat diidentifikasi atau untuk melayani suatu tujuan. Menurut Kamus Besar Bahasa Indonesia, sistem adalah perangkat unsur yg secara teratur saling berkaitan sehingga membentuk suatu totalitas, susunan yg teratur dr pandangan, teori, asas, metode. Abdul Kadir mendefinisikan sistem sebagai “sekumpulan elemen yang saling terkait atau terpadu yang dimaksudkan untuk mencapai suatu tujuan”. Sementara Jogiyanto membagi pendekatan dalam pendefinisian sistem menjadi 2 kelompok. Kelompok pertama melakukan pendekatan sistem yang lebih menekankan pada prosedur, sementara kelompok kedua melakukan pendekatan sistem yang lebih menekankan pada elemen atau komponennya. Kelompok pertama mendefinisikan sistem sebagai suatu jaringan kerja dari prosedur-prosedur yang saling berhubungan, berkumpul bersama-bersama untuk melakukan suatu kegiatan atau untuk menyelesaikan suatu sasaran tertentu. Kelompok kedua mendefinisikan sistem sebagai kumpulan dari elemen-elemen yang berinteraksi untuk mencapai suatu tujuan tertentu.

Definisi dari kelompok kedua lebih banyak diterima, karena kenyataannya suatu sistem dapat terdiri dari beberapa subsistem atau sistem-sistem bagian. Selain itu, pendekatan sistem yang menekankan pada komponen akan lebih mudah di dalam mempelajari suatu sistem untuk tujuan analisis dan perancangan suatu sistem. Jadi, dapat disimpulkan bahwa sistem adalah sekumpulan objek yang terdiri dari elemen-elemen yang secara teratur saling berkaitan dan yang berinteraksi untuk mencapai suatu tujuan tertentu.

Sistem dibagi menjadi tiga bagian berbeda: input, proses, output. Bagian-bagian tersebut dikelilingi oleh sebuah lingkungan dan sering melibatkan sebuah mekanisme umpan balik.

1. Input

Input adalah elemen yang masuk ke dalam sistem. Contoh input adalah bahan mentah yang dimasukkan seperti pabrik kimia, mahasiswa yang diterima pada sebuah universitas, dan input data ke dalam halaman web untuk query database.

2. Proses

Proses adalah semua elemen yang diperlukan untuk mengkonversi atau mentransformasi input ke dalam output. Proses juga dapat didefinisikan sebagai urutan langkah-langkah yang baik untuk penciptaan artefak perangkat lunak tertentu, akan melibatkan analisis dan pemodelan formal maupun informal dari proses-proses perangkat lunak, dan proses yang terakhir untuk memenuhi kebutuhan bisnis spesifik, seperti penjadwalan cepat dari pengembangan aplikasi web. Pada sebuah komputer, termasuk komputer berbasis web, sebuah proses dapat meliputi perintah-perintah pengaktifan, eksekusi komputasi, dan penyimpanan informasi.

3. Output

Output adalah produk finis atau konsekuensi yang ada pada sistem. Sebagai contoh, fertilizer adalah output dari sebuah pabrik kimia, orang yang berpendidikan adalah output dari sebuah universitas, dan laporan adalah output dari sebuah sistem komputer. Server web dapat menghasilkan sebuah halaman web dinamis berdasarkan input dan prosesnya.

4. Umpan Balik

Ada aliran informasi dari komponen output ke pengambil keputusan berkenaan dengan output atau performa sistem. Berdasarkan output, pengambil keputusan, yang bertindak sebagai kontrol, dapat memutuskan untuk memodifikasi input, proses, atau keduanya. Aliran informasi ini, muncul sebagai closed loop disebut umpan balik. Inilah bagaimana monitoring sistem riil terjadi. Pengambil keputusan membandingkan output dengan output yang diharapkan dan menyesuaikan input dan mungkin proses untuk makin mendekati output target.Menurut Ludwig Von Bartalanfy, Sistem merupakan seperangkat unsur yang saling terikat dalam suatu antar relasi diantara unsur-unsur tersebut dengan lingkungan. Sementara menurut Anatol Raporot, Sistem adalah suatu kumpulan kesatuan dan perangkat hubungan satu sama lain. Menurut L. Ackof, Sistem adalah setiap kesatuan secara konseptual atau fisik yang terdiri dari bagian-bagian dalam keadaan saling tergantung satu sama lainnya.

Mengacu pada beberapa definisi di atas, sistem juga dapat diartikan, sekumpulan unsur / elemen yang saling berkaitan dan saling mempengaruhi dalam melakukan kegiatan bersama untuk mencapai suatu tujuan. Sebagai contoh, dalam sistem komputer terdapat software (perangkat lunak), hardware (perangkat keras), dan brainware (sumber daya manusia).

2.1.2. Keputusan

Beberapa definisi keputusan yang dikemukakan para ahli dijelaskan sebagai berikut (Hasan, 2004):

1. Menurut Ralph C. Davis

Keputusan adalah hasil pemecahan masalah yang dihadapinya dengan tegas. Suatu keputusan merupakan jawaban yang pasti terhadap suatu pertanyaan. Keputusan harus dapat menjawab pertanyaan tentang apa yang dibicarakan dalam hubungannya dengan perencanaan. Keputusan dapat pula berupa tindakan terhadap pelaksanaan yang sangat menyimpang dari rencana semula.

2. Menurut Mary Follet

Keputusan adalah suatu atau sebagai hukum situasi. Apabila semua fakta dari situasi itu dapat diperolehnya dan semua yang terlibat, baik pengawas maupun pelaksana mau mentaati hukumnya atau ketentuannya, maka tidak sama dengan mentaati perintah. Wewenang tinggal dijalankan, tetapi itu merupakan wewenang dari hukum situasi.

3. Menurut James A.F.Stoner

Keputusan adalah pemilihan diantara alternatif-alternatif. Definisi ini mengandung tiga pengertian, yaitu:

a. Ada pilihan atas dasar logika atau pertimbangan.

b. Ada beberapa alternatif yang harus dan dipilih salah satu yang terbaik.

c. Ada tujuan yang ingin dicapai, dan keputusan itu makin mendekatkan pada tujuan tertentu.

4. Menurut Prof. Dr. Prajudi Atmosudirjo, SH

Keputusan adalah suatu pengakhiran daripada proses pemikiran tentang suatu masalah atau problema untuk menjawab pertanyaan apa yang harus diperbuat guna mengatasi masalah tersebut, dengan menjatuhkan pilihan pada suatu alternatif.

Dari pengertian-pengertian keputusan diatas, dapat ditarik suatu kesimpulan bahwa keputusan merupakan suatu pemecahan masalah sebagai suatu hukum situasi yang dilakukan melalui pemilihan satu alternatif dari beberapa alternatif.

2.1.3. Pengambilan Keputusan

Beberapa definisi pengambilan keputusan yang dikemukakan para ahli dijelaskan sebagai berikut (Hasan, 2004):

1. Menurut George R. Terry

Pengambilan keputusan adalah pemilihan alternatif perilaku (kelakuan) tertentu dari dua atau lebih alternatif yang ada.

2. Menurut S.P. Siagian

Pengambilan keputusan adalah suatu pendekatan yang sistematis terhadap hakikat alternatif yang dihadapi dan mengambil tindakan yang menurut perhitungan merupakan tindakan yang paling tepat.

3. Menurut James A.F. Stoner

Pengambilan keputusan adalah proses yang digunakan untuk memilih suatu tindakan sebagai cara pemecahan masalah.

Dari pengertian-pengertian pengambilan keputusan diatas, dapat disimpulkan bahwa pengambilan keputusan merupakan suatu proses pemilihan alternatif terbaik dari beberapa alternatif secara sistematis untuk ditindaklanjuti (digunakan) sebagai suatu cara pemecahan masalah

2.1.4. Sistem Pendukung Keputusan

Decision Support System atau Sistem Pendukung Keputusan, secara umum didefinisikan sebagai sebuah sistem yang mampu memberikan kemampuan baik kemampuan pemecahan masalah maupun kemampuan pemgkomunikasian untuk masalah semi-terstruktur. Secara khusus, SPK didefinisikan sebagai sebuah sistem yang mendukung kerja seorang manajer maupun sekelompok manajer dalam memecahkan masalah semi-terstruktur dengan cara memberikan informasi ataupun usulan menuju pada keputusan tertentu.

Pembuatan keputusan merupakan fungsi utama seorang manajer atau administrator. Kegiatan pembuatan keputusan meliputi pengidentifikasian masalah, pencarian alternatif penyelesaian masalah, evaluasi dari alternatif-alternatif tersebut dan pemilihan alternatif keputusan yang terbaik. Kemampuan seorang manajer dalam membuat keputusan dapat ditingkatkan apabila ia mengetahui dan menguasai teori dan teknik pembuatan keputusan. Dengan peningkatan kemampuan manajer dalam pembuatan keputusan diharapkan dapat ditingkatkan kualitas keputusan yang dibuatnya, dan hal ini tentu akan meningkatkan efisiensi kerja manajer yang bersangkutan.

2.2. Penjadwalan

Menurut Ross permasalahan jadwal mata kuliah (lecture timetable) adalah permasalahan pengalokasian waktu dan tempat untuk suatu kegiatan perkuliahan, seminar, dan lain-lain untuk memenuhi beberapa kendala yang berhubungan dengan kapasitas dan lokasi dari ruang, waktu, dan hal lain yang berhubungan dengan perkuliahan.

Permasalahan penjadwalan mata kuliah didefinisikan secara formal dan matematis oleh Ross sebagai berikut :

· Diberikan suatu himpunan E = {e1,e2…ev} merupakan kegiatan, T = {t1,t2…ts} merupakan waktu, P = {p1,p2…pm} merupakan tempat dan A = {a1,a2…an} merupakan ‘agents’ ( orang yang kehadiranya diperlukan untuk kelangsungan kegiatan, dalam hal ini sebagai contoh adalah mahasiswa dan perkuliahan sebagai ‘agents’ ).

· Diimplementasikan dalam 4 tuple (e,t,p,a).

· Permasalahan penjadwalan mata kuliah sekarang didefinisikan sebagai permasalahan untuk mengalokasikan sekumpulan kegiatan pada suatu tempat dan waktu yang terbatas yang meminimalkan kendala-kendala yang ada.

Dalam proses penyelesaian masalah penjadwalan mata kuliah terdapat kendala-kendala yang harus dipenuhi atau tidak boleh dilanggar. Kendala tersebut merupakan ukuran kualitas dari penjadwalan mata kuliah, sehingga suatu jadwal mata kuliah yang optimal dapat terbentuk. Kendala-kendala yang harus dipenuhi pada penjadwalan mata kuliah pada umumnya adalah kendala yang terjadi pada suatu kampus atau universitas tertentu. Kendala-kendala tersebut adalah :

1. Dosen dapat mengajar lebih dari satu mata kuliah dan tidak boleh terjadi tumbukan pada dosen.

2. Satu mata kuliah dapat diampu oleh 2 orang dosen atau lebih. Terdapat mata kuliah tertentu yang menggunakan ruang laboratorium yang harus dijadwalakan pada ruang laboratorium.

3. Mahasiswa dapat mengambil mata kuliah angkatan sebelumnya maupun sesudahnya dan tidak boleh terjadi tumbukan pada mata kuliah yang sudah diambil.

4. Tersedianya ruang yang cukup untuk seluruh mata kuliah yang ada.

2.3. Algoritma Genetik

Algoritma ini ditemukan di Universitas Michigan, Amerika Serikat oleh John Holland (1975) melalui sebuah penelitian dan dipopulerkan oleh salah satu muridnya, David Goldberg (1989). Dimana mendefenisikan algoritma genetic ini sebagai metode algoritma pencarian berdasarkan pada mekanisme seleksi alam dan genetik alam. Sedikit menengok ke belakang, sebenarnya cikal bakal perkembangan Algoritma Genetika ini berawal dari prakarsa beberapa ahli Biologi. Para ahli Biologi tersebut menggunakan komputer digital untuk mengerjakan simulasi dari sistem genetika. Para ahli tersebut diantaranya adalah Baricelli, N.A yang pada tahun 1957 melakukan penelitian evolusi simbiogenetik dan pada tahun 1962 mengajukan teori evolusi beserta analisis numeriknya. Selain Baricelli, satu lagi nama yang menjadi pemrakarsa Algoritma Genetika adalah Fraser, A.S. yang pada tahun 1960 mensimulasikan sistem genetika dengan komputer. Penelitian yang dilakukan para ahli Biologi tersebut memberikan ide bagi Jhon Hollad dan muridnya David Goldberg untuk mengaplikasikan proses genetika ini pada sistem buatan.

Algoritma genetik adalah algoritma yang berusaha menerapkan pemahaman mengenai evolusi alamiah pada tugas-tugas pemecahan-masalah (problem solving). Pendekatan yang diambil oleh algoritma ini adalah dengan menggabungkan secara acak berbagai pilihan solusi terbaik di dalam suatu kumpulan untuk mendapatkan generasi solusi terbaik berikutnya yaitu pada suatu kondisi yang memaksimalkan kecocokannya atau lazim disebut fitness. Generasi ini akan merepresentasikan perbaikan-perbaikan pada populasi awalnya. Dengan melakukan proses ini secara berulang, algoritma ini diharapkan dapat mensimulasikan proses evolusioner.

Algoritma Genetika memiliki prosedur sebagai berikut :

1. [Start] Generate populasi pertama secara random sebanyak n individu

2. [Fitness] Evaluasi nilai fitness f(x) dari setiap individu x di dalam populasi

3. [New Populasi] Bentuk populasi baru dengan melakukan pengulangan langkah-langkah di bawah ini sehingga didapatkan populasi baru

a. [Selection] Pilih 2 individu sebagai orangtua dari sebuah populasi sesuai dengan fitness mereka (semakin besar nilai fitness, maka semakin besar pula peluang untuk terpilih)

b. [Crossover] Lakukan persilangan antara kedua orangtua seseuai dengan probabilitas crossover untuk menghasilkan keturunan yang baru. Jika tidak terjadi persilangan maka keturunan yang dihasilkan akan sama persis dengan orangtuanya

c. [Mutation] Mutasi setiap keturunaan yang baru sesuai dengan probabilitas mutasi di setiap gen

d. [Accepting] Tempatkan keturunan yang baru sesuai populasi yang baru

4. [Replace] Gunakan populasi yang baru dibentuk untuk menjalankan algoritma

5. [Test] Jika kondisi akhir dipenuhi maka berhenti dan tampilkan solusi dari populasi

6. [Loop] Kembali ke langkah 2

Algoritma Genetika ini meniru mekanisme dari genetika alam. Dari siklus di atas dapat dijabarkan sebagai berikut :

1. Membuat Populasi Awal

Langkah pertama dalam algoritma ini adalah membentuk sejumlah populasi awal yang digunakan untuk mencari penyelesaian optimal. Populasi ini merupakan kumpulan dari alternatif solusi. Dengan adanya populasi ini, maka Algortima Genetika melakukan proses pencarian dari berbagai titik uji. Pembuatan populasi awal ini dilakukan secara random.

2. Representasi Kromosom

Agar dapat diproses melalui Algoritma Genetika, maka alternatif solusi tersebut harus direpresentasikan terlebih dahulu ke dalam bentuk kromosom. Representasi kromosom merupakan proses pengkodean dari penyelesaian asli suatu masalah. Pengkodean tersebut meliputi penyandian gen, dengan satu gen mewakili satu variabel.

3. Fungsi Fitness

Suatu kromosom dievaluasi berdasarkan suatu fungsi tertentu sebagai ukuran performansinya. Fungsi tersebut disebut fungsi fitness, (Hermanto 2003) yaitu Fungsi yang membedakan kualitas dari kromosom yang diinginkan. Kromosom yang memiliki fungsi fitness yang tinggi akan dipertahankansedangkan kromosom dengan harga fungsi fitness yang rendah akan diganti.

4. Seleksi

Sejumlah kromosom akan diseleksi untuk menjadi orangtua. Kromosom yang baik (orangtua) yang memiliki nilai fitness yang tinggi akan dipertahankan dan akan menghasilkan keturunan baru untuk populasinya.

5. Persilangan

Merupakan bagian dari operator genetika yang digunakan untuk memodifikasi individu dalam aliran populasi guna mencetak individu selanjutnya. Operator persilangan bekerja untuk menggabungkan dua kromosom orangtua (parent) menjadi kromosom baru (offspring).

6. Mutasi

Setelah persilangan dilakukan, operator genetika pun melakukan mutasi. Hal ini dilakukan untuk menghindari solusi-solusi dalam populasi mempunyai nilai lokal optimum. Mutasi adalah proses mengubah gen dari keturunan secara random.

7. Kondisi Berhenti

Kondisi berhenti tercapai ketika solusi optimum terpenuhi dan Algoritma Genetika akan menghentikan proses pencariannya.

Operator genetika dipergunakan untuk mengkombinasi (modifikasi) individu dalam aliran populasi guna mencetak individu pada generasi berikutnya. Ada dua operator genetika yaitu crossover dan mutation (Juniawati, 2003).

1. Persilangan (Crossover )

Operator persilangan merupakan operasi yang bekerja untuk menggabungan dua kromosom orangtua (parent) menjadi kromosom baru (offspring). Tidak semua kromosom mengalami persilangan. Jumlah kromosom dalam populasi yang mengalami persilangan ditentukan oleh paramater yang disebut dengan crossover rate (probabilitas persilangan) . Jenis operator persilangan yaitu:

a. One point crossover

Sebuah titik crossover dipilih, selanjutnya string biner mulai dari awal kromosom sampai dengan titik tersebut disalin dari salah satu orangtua ke keturunannya, kemudian sisa bit keturunan disalin dari orangtua yang kedua. Contoh : 11001011 + 11011111 = 11001111.

b. Two point crossover

Dua titik crossover dipilih, selanjutnya string biner mulai dari awal kromosom sampai dengan titik crossover pertama disalin dari salah satu orangtua ke keturunannya kemudian mulai dari titik crossover pertama sampai dengan titik kedua disalin dari orangtua kedua. Sisanya disalin dari orangtua pertama. Contoh : 11001011 + 11011111 = 11011111

2. Mutasi

Setelah crossover dilakukan, proses reproduksi dilanjutkan dengan mutasi. Hal ini dilakukan untuk menghindari solusi-solusi dalam populasi mempunyai nilai lokal optimum. Mutasi adalah proses mengubah gen dari keturunan secara random. Untuk pengkodean biner maka mutasi mengubah bit 0 menjadi bit 1 dan bit 1 menjadi bit 0. Contoh : 11001001 ? 10001001

Tidak setiap gen selalu dimutasi tetapi mutasi dikontrol dengan probabilitas tertentu yang disebut dengan mutation rate (probabilitas mutasi) dengan notasi Pm. Jenis operator mutasi antara lain:

a. Mutasi Terarah

Mutasi terarah tergantung dari informasi gen. Informasi gen tersebut berupa nilai pelanggaran gen (violation score). Ini berarti bahwa setiap gen mempunyai peluang yang berbeda untuk terjadi mutasi. Gen yang mempunyai nilai pelanggaran yang lebih besar maka gen tersebut mempunyai peluang untuk terjadi mutasi. Mutasi ini menghubungkan nilai pelanggaran relatif (nilai pelanggaran suatu gen dibagi dengan nilai pelanggaran total suatu kromosom) dengan probabilitas terjadinya mutasi dari suatu gen pada kromosom. Hubungan tersebut dinyatakan secara matematis sebagai berikut:

Keterangan persamaan:

nr(i) : nilai pelanggaran relative gen ke-i.

ntotal : nilai pelanggaran total kromosom.

pm(i) : probabilitas mutasi gen ke-i.

pm : probabilitas mutasi

b. Mutasi Biasa

Mutasi ini tidak tergantung dari informasi gen. Setiap gen mempunyai peluang yang sama untuk terjadi mutasi.

2.4. Constraint Satisfaction Problem

Constraint Satisfaction Problem merupakan sebuah pendekatan untuk menyelesaikan suatu masalah dengan tujuan menemukan keadaan atau objek yang memenuhi sejumlah persyaratan atau kriteria. Sebuah constraint diartikan sebagai sebuah batasan dari solusi yang memungkinkan dalam sebuah problem optimasi. Komponen-komponen yang terdapat pada CSP adalah Variabel yang merupakan penampung dapat diisi berbagai nilai, Constraint yang merupakan suatu aturan yang ditentukan untuk mengatur nilai boleh diisikan ke variabel, atau kombinasi variabel, Domain yang merupakan kumpulan nilai legal dapat diisi ke variable, Solusi yang merupakan assignment nilai-nilai dari domain ke setiap variabel tidak ada constraint yang dilanggar.

Prosedur pembatasan dalam CSP adalah sebagai berikut:

1. Pilihlah sebuah simpul yang belum dikembangkan dalam graph pencarian (search).

2. Terapkan aturan-aturan inferensi pembatas (constraint) untuk simpul yang dipilih untuk menghasilkan semua pembatasan baru yang dimungkinkan.

3. Jika himpunan pembatas berisi sebuah kontradiksi, maka laporkanlah bahwa lintasan ini terhenti.

4. Jika himpunan pembatas menggambarkan sebuah solusi yang lengkap, maka laporkanlah adanya kesuksesan.

5. Jika tidak ditemukan adanya kontradiksi atau solusi lengkap, maka solusi-solusi parsial baru yang konsisten dengan himpunan pembatas saat ini. Sisipkan solusi-solusi parsial ke dalam graph pencarian (search).

Constraint dari CSP penjadwalan matakuliah dapat dikategorikan menjadi dua yaitu hard constraint dan soft constraint. Hard constraint adalah batasan yang harus dipenuhi dalam pembuatan pemecah masalah (Solver). Sedangkan soft constraint adalah batasan tambahan, biasanya mewadahi permintaan pribadi (personal request).

2.5. Penelitian Terdahulu

Studi Algoritma Genetika Untuk Optimasi Penjadwalan Mata Kuliah oleh Kiki Firmansyah. Sistem ini untuk membantu proses penjadwalan perkuliahan dengan menggunakan Algoritma Genetika. Metode penelitian yang digunakan dalam jurnal ini adalah studi literatur. Dari hasil studi literatur dapat disimpulkan Algoritma Genetika dapat mengoptimalkan penjadwalan mata kuliah. Penjadwalan dapat memberikan solusi yang dapat digunakan oleh dosen, mahasiswa, kelas, ruangan, mata kuliah yang terlibat dalam kegiatan perkuliahan. Di samping itu, dapat meminimalkan tingginya frekuensi mengajar seorang dosen, frekuensi kuliah mahasiswa dan juga faktor lainnya. (Kiki Firmansyah, 2009)

Perbedaan penelitian tersebut dengan penelitian yang dilakukan oleh penulis adalah metode yang digunakan oleh penelitian tersebut hanyalah metode Algoritma Genetika, sementara metode yang digunakan oleh penulis adalah metode Algoritma Genetika yang dikombinasikan dengan metode Constraint Satisfaction Problem.

Perancangan Dan Pengembangan Perangkat Lunak Penjadwalan Matakuliah Dengan Metode Constraint Satisfaction oleh Dwi Anggraini P.R., S.Kom. Penelitian ini merupakan implementasi dan pengembangan dari penelitian yang telah dilakukan sebelumnya yang menghasilkan rumusan constraint satisfaction problem dan algoritma penyelesaiannya. Penelitian ini merancang dan mengembangkan prototipe perangkat lunak penjadwalan matakuliah dari rumusan algoritma tersebut. Perangkat lunak yang dikembangkan kali ini lebih difokuskan pada penyelesaian hard constraints dari constraint satisfaction problem yang telah didefinisikan. Prototipe perangkat lunak yang dihasilkan pada penelitian ini dapat mengotomatisasi dan mengoptimalisasi pembuatan jadwal akademik sehingga pembuatan jadwal akademik menjadi semakin terstruktur dan mudah.

Penelitian yang dilakukan penulis memiliki perbedaan yaitu dalam hal metode yang digunakan dalam penelitian. Penelitian di atas menggunakan metode Constraint Satisfaction Problem, sementara penulis menggunakan metode Algoritma Genetik dan metode Constraint Satisfaction Problem. Selain itu, bidang yang dikaji dalam penelitian di atas rekayasa perangkat lunak, sementara bidang yang dikaji dalam penelitian penulis adalah sistem pendukung keputusan. (Dwi Anggraini, 2008)

BAB III

METODE PENELITIAN

3.1. Uraian Permasalahan

Permasalahan pada penelitian ini adalah pembuatan jadwal mata kuliah di Kampus STIMK STIKOM Indonesia. Penjadwalan yang dibuat harus sesuai dengan aturan yang ada. Dalam melakukan penjadwalan pun harus memperhatikan ruang yang tersedia, agar semua kelas yang ada mendapatkan ruang. Banyaknya kemungkinan-kemungkinan yang dapat disusun untuk penjadwalan, ditambah adanya permintaan dosen untuk mengajar hanya di hari tertentu saja, membuat sistem ini semakin kompleks.

3.2. Analisis Permasalahan

Sistem Penjadwalan Mata Kuliah merupakan sistem pendukung keputusan yang dirancang dengan tujuan untuk mempermudah bagian akademik dalam melakukan proses penjadwalan setiap semesternya. Sistem ini dapat melakukan pengelolaan data dosen, data waktu, data ruang, data mata kuliah, dan data penjadwalan, sehingga melalui sistem ini PK I mendapatkan acuan dalam menentukan keputusan dan kebijakan untuk penjadwalan secara lebih cepat dan tepat.

3.3. Perancangan Sistem

3.3.1. Diagram Alir Sistem (System Flow)

Gambar 3.1 Diagram Alir Sistem (System Flow)

3.3.2. Bagan Alir Metode (Flowchart)

Gambar 3.2 Bagan Alir Metode (Flowchart)

3.3.3. Data Flow Diagram (DFD)

Context Diagram

Gambar 3.3 Diagram Konteks

DFD Level 0

Gambar 3.4 DFD Level 0

DFD Level 1

Gambar 3.5 DFD Level 1

3.3.4. Entity Relationship Diagram (ERD)

Gambar 3.6 Entity Relationship Diagram (ERD)

3.3.5. Struktur Database

Berdasarkan gambaran sistem yang telah dijelaskan diatas, struktur database secara keseluruhan dari sistem penjadwalan mata kuliah yang akan dibuat adalah sebagai berikut :

1. Tabel Dosen

Nama Field	Tipe Data	Ukuran	Keterangan
NIP	varchar	10	Primary key
Nama	varchar	50
Tempat_lhr	varchar	30
Tgl_lhr	date
Jk	byte	1
Alamat	varchar	100
No_Telp	varchar	12

2. Tabel Waktu

Nama Field	Tipe Data	Ukuran	Keterangan
Hari	varchar	10
Jam	time

3. Tabel Ruang

Nama Field	Tipe Data	Ukuran	Keterangan
Id_ruang	varchar	3	Primary Key
Daya_tampung	integer	2

4. Tabel Mata Kuliah

Nama Field	Tipe Data	Ukuran	Keterangan
Id_matkul	varchar	10	Primary Key
Matkul	varchar	50
Sks	integer	1
Kelas	char	1

5. Tabel Penjadwalan

Nama Field	Tipe Data	Ukuran	Keterangan
Id_matkul	varchar	10	Foreign Key
NIP	varchar	10	Foreign Key
Id_ruang	varchar	3	Foreign Key
Hari	varchar	10
Jam	time