BAB I

PENDAHULUAN

1.1 latar belakang

Jadwal mata kuliah merupakan hal yang sangat penting bagi kelancaran proses belajar mengajar di Jurusan Teknik Informatika Universitas Yudharta Pasuruan. Sering terjadinya tumbukan, baik tumbukan yang terjadi pada mata kuliah yang diambil oleh mahasiswa maupun tumbukan yang terjadi pada dosen mengakibatkan tidak efektifnya proses belajar mengajar di Jurusan Teknik Informatika Universitas Yudharta Pasuruan. Ditambah lagi terjadinya pergantian jadwal yang mengakibatkan bertambahnya tumbukan yang terjadi pada mahasiswa. Oleh karena itu di Jurusan Teknik Informatika Universitas Yudharta Pasuruan di butuhkan penjadwalan mata kuliah yang baik.Untuk membuat jadwal mata kuliah yang baik kita harus memperhatikan berbagai aspek yang mempengaruhi penjadwalan mata kuliah ini. Dari aspek mahasiswa, kita perlu perhatikan ada atau tidaknya tumbukan pada mata kuliah yang diambil oleh mahasiswa, selain dilihat dari aspek mahasiswa, kita juga harus melihat dari aspek dosen, yaitu kemungkinan kemungkinan dosen akan mengampu lebih dari satu mata kuliah yang ada, sebab ada kemungkinan jumlah mata kuliah dan jumlah dosen tidak sebanding, sehingga harus dipikirkan juga solusi agar dosen tidak mengampu dua mata kuliah berbeda pada hari dan jam yang sama. Selain itu, harus dipertimbangkan juga ketersediaan kelas sehingga kegiatan belajar dapat dilaksanakan. Di samping aspek-aspek di atas, dalam penyusunan jadwal mata kuliah ini pun terdapat sangat banyak kemungkinan yang selayaknya dicoba untuk menemukan penjadwalan yang terbaik. Karena itu dibutuhkan metode optimasi yang dapat diterapkan untuk mengerjakan penjadwalan mata kuliah ini. Masalah optimasi dapat diselesaikan menggunakan algoritma pencarian heuristik, tapi algoritma pencarian heuristik yang biasa seperti best first search digunakan untuk kasus yang sederhana (Salwani,2009). Untuk input dan persyaratan yang lebih rumit seperti pada kasus penjadwalan mata kuliah, algoritma pencarian heuristic sudah tidak dapat lagi digunakan dengan baik untuk mendapatkan solusi yang diinginkan. Dalam kasus penjadwalan mata kuliah ini diperlukan algoritma yang lebih baik yaitu algoritma yang dapat menyelesaikan masalah optimasi kompleks (kompleks optimization problems), yaitu suatu persoalan yang menuntut pencarian solusi optimum, Berharap bahwa dengan memilih optimum lokal pada setiap langkah akan berakhir dengan optimum global (Wikipedia, optimasi 2007) . Salah satu algoritma yang dapat digunakan adalah algoritma Greedy. Algoritma Greedy adalah merupakan algoritma yang membentuk solusi langkah per langkah (step by step). Pada setiap langkah tersebut akan dipilih keputusan yang paling optimal. Keputusan tersebut tidak perlu memperhatikan keputusan selanjutnya yang akan diambil, dan keputusan tersebut tidak dapat diubah lagi pada langkah selanjutnya.

Banyak permasalahan optimalisasi yang telah diselesaikan dengan menggunakan algoritma Greedy diantaranya adalah permasalahan pemilihan beberapa jenis investasi(penanaman modal), mencari jalur tersingkat dari bandung ke Surabaya, memilih jurusan di perguruan tinggi, bermain kartu remi (Wikipedia,2008).Dari latar belakang yang telah disebutkan di atas, maka dalam tugas akhir ini akan dicoba mengaplikasikan algoritma Greedy untuk mengoptimalkan jadwal mata kuliah. Diharapkan dengan digunakannya algoritma Greedy akan diperoleh optimasi penjadwalan yaitu terjadinya kombinasi terbaik untuk pasangan mata kuliah dan dosen pengajar secara keseluruhan, tidak ada permasalahan tumbukan jadwal pada sisi mahasiswa, serta ketersediaan ruang yang cukup dan sesuai secara fasilitas untuk seluruh mata kuliah yang ada.Penjadwalan yang dijadikan studi kasus dalam Skripsi ini adalah merupakan penjadwalan kuliah di Jurusan Teknik Informatika Universitas Yudharta Pasuruan. Data-data yang dibutuhkan dalam kasus penjadwalan tersebut adalah:

1. Data Penugasan yang memuat data kelas, matakuliah, dosen pengajar

2. Data kelas dari tingkat awal sampai tingkat akhir untuk jenjang S13. Data ruang yang dapat dipergunakan untuk perkuliahan

4. Data dosen yang mengajar.

Proses penjadwalan memiliki kompleksitas waktu proses yang sangat tinggi dan meningkat terhadap jumlah komponen yang dijadwalkan. Untuk mengoptimasikan waktu proses penjadwalan, maka setiap hasil proses iterasi akan disimpan di memori bukan dalam database ( hardisk ).

1.2 Rumusan masalah

Berdasarkan latar belakang masalah, maka yang menjadi permasalahan adalah bagaimana mengaplikasikan algoritma Greedy agar dapat digunakan untuk melakukan penjadwalan mata kuliah sehingga diperoleh jadwal mata kuliah dengan kombinasi terbaik untuk pasangan mata kuliah dan dosen pengajar secara keseluruhan, tidak ada permasalahan tumbukan jadwal pada sisi mahasiswa, serta ketersediaan ruang yang cukup untuk seluruh mata kuliah yang ada.

1.3 Batasan Masalah

Permasalahan yang akan dipecahkan dapat terus meluas seiring dengan berjalannya penelitian ini. Dikarenakan masih ada sejumlah batasan dan syarat (constraints) yang belum diketahui. Dalam penelitian ini, penulis membatasi penjadwalan kuliah dengan studi kasus di jurusan teknik informatika Universitas Yudharta Pasuruan sebagai berikut :

1. Komponen yang dijadikan parameter penjadwalan berupa Subject ( kelas, matakuliah, dosen ), timeslot, ruang.

2. Penelitian hanya menjadwalkan perkuliahan dari semester satu sampai dengan semester tujuh (ganjil).

3.Penelitian hanya memecahkan masalah jadwal kelas regular ( nonkaryawan ).

4.Waktu kegiatan belajar mengajar adalah dari hari Senin sampai dengan Sabtu dimulai dari jam 07.00 sampai jam 17.30 dengan lama perkuliahan adalah 45 menit.

5.Batasan kasus hanya untuk mata kuliah di semester ganjil untuk jenjang S1.1.4 Tujuan Maksud dari Skripsi ini adalah membuat sebuah perangkat lunak untuk menyelesaikan permasalahan penjadwalan kuliah dengan menggunakan algoritma Greedy sehingga didapatkan hasil penjadwalan yang baik dan tidak terjadi kontra-produktif antar komponen-komponen yang dijadwalkan serta jadwal yang relatif nyaman untuk setiap mahasiswa dan dosen sehingga aktivitas perkuliahan dapat terlaksana dengan baik. Tujuan dari penulisan Skripsi ini adalah :

1. Membuktikan hasil penjadwalan dengan algoritma Greedy, tidak terjadi bentrok antar komponen yang dijadwalkan yaitu kelas, matakuliah, dosen, waktu, dan ruang.

2. Mengefisiensikan waktu proses pemecahan masalah penjadwalan kuliah dengan memproses dan menyimpan hasil setiap iterasi ke dalam memori sedangkan solusi global akan disimpan dalam database/hardisk.1.5 Manfaat PenelitianAdanya tugas akhir yang dibuat ini, diharapkan dapat memberikan manfaat antara lain :

1. Bagi mahasiswa :

a. Dapat menerapkan disiplin ilmu dan memanfaatkannya.

b. Meningkatkan pemahaman tentang penggunaan algoritma Greedy.

2. Bagi program studi Informatika : a. Dapat digunakan untuk membantu proses penjadwalan mata kuliah agar lebih optimal.

BAB IITINJAUAN PUSTAKA2.1 Penelitian Terkait Penelitian ini merujuk pada penelitian sebelumnya sebagai bahan kajian, antara lain:1. Aplikasi Algoritma Greedy Untuk Mengatasi Konflik Penjadwalan Mata Kuliah Di UNY Oleh Husna 'Arifah.[1]

Data yang digunakan di ambil dari data yang telah ada di jurusan. Komponen utama yang digunakan yaitu:

1. Dosen

2. Ruang

3. Mata Kuliah

4. Waktu Dengan aturan penjadwalan:

a. Tidak boleh ada dosen yang mengajar lebih dari satu kelas mata kuliah berbeda diwaktu yang bersamaan.

b. Lebih dari satu kelas mata kuliah yang berbeda tidak dapat berada pada ruang dan waktu yang sama.

c. Satu mata kuliah dapat diampu lebuh dari seorang dosen.

d. Waktu kuliah dalam sehari dimulai dari jam 07.30 17.30. Lama setiap satu jam pelajaran adalah 45 menit, dalam jangka waktu satu hari terdapat 12 slot waktu, maka dalam 6 hari terdapat 72 slot waktu. Dari penelitian yang telah dilakukan, dapat disimpulkan bahwa Algoritma Greedy dapat digunakan sebagai alternatif solusi untuk menyelesaikan masalah penjadwalan perkuliahan.2. Implementasi Jadwal Kuliah Dengan Menggunakan Algoritma Semut Berbasis Web Ferawati, Evi.[2] Dalam skripsi tersebut disebutkan bagaimana membuat jadwal kuliah menggunakan Algoritma Semut yang mampu memberikan solusi optimal untuk penjadwalan. Algoritma Semut bisa memberikan solusi optimal meskipun terdapat syarat tertentu pada komponen dibawah ini:

1. Mata kuliah: merupakan satuan pelajaran, berbeda tiap semester, dibedakan berdasarkan semester ganjil dan genap.

2. Dosen: pengajar mata kuliah yang ditawarkan, biasanya mengajar lebih satu mata kuliah, namun sering terjadi dalam penyusunan jadwal kuliah jam mengajar dosen bersamaan untuk mata kuliah yang berbeda.

3. Jam kuliah: waktu yang dibutuhkan untuk menyampaikan materi pelajaran.

4. Ruangan: tempat kuliah dimana kegiatan perkuliahan tidak akan berjalan maksimum jika ruangan yang tersedia tidak memenuhi kapasitas.

5. Jumlah sks dalam penjadwalan digunakan sebagai tolok ukur lamanya kuliah dilaksanakan. 2.2 Landasan Teori2.2.1 Algoritma GreedyAlgoritma Greedy adalah salah satu algoritma yang dapat digunakan untuk mendapatkan solusi terbaik dan merupakan algoritma yang paling populer dalam hal optimasi. Persoalan optimasi adalah persoalan yang tidak hanya mencari sekedar solusi, tetapi mencari solusi terbaik. Solusi terbaik adalah solusi yang memiliki nilai minimum atau maksimum dari sekumpulan alternatif solusi yang mungkin[16].

Secara harfiah Greedy artinya rakus atau tamak, sifat yang berkonotasi negatif. Orang yang memiliki sifat ini akan mengambil sebanyak mungkin atau mengambil yang paling bagus atau yang paling mahal. Sesuai dengan arti tersebut, prinsip Greedy adalah take what you can get now. Dalam kehidupan sehari-hari Greedy dapat digunakan dalam masalah seperti :

1. Memilih beberapa jenis investasi

2. Mencari jalur tersingkat

Algoritma Greedy membentuk solusi langkah per langkah (step by step). Terdapat banyak pilihan yang perlu di eksplorasi pada setiap langkah solusi, karenanya pada setiap langkah harus dibuat keputusan yang terbaik dalam menentukan pilihan. Keputusan yang telah diambil pada suatu langkah tidak dapat diubah lagi pada langkah selanjutnya. Sebagai contoh, jika kita menggunakan algoritma Greedy untuk menempatkan komponen diatas papan sirkuit, sekali komponen telah diletakkan dan dipasang maka tidak dapat dipindahkan lagi.

Pendekatan yang digunakan dalam algoritma Greedy adalah membuat pilihan yang tampaknya memberikan perolehan yang terbaik, yaitu dengan membuat pilihan optimum lokal pada setiap langkah dengan harapan optimum lokal menjadi optimum global.2.2.2 Penjadwalan Jadwal menurut kamus besar bahasa Indonesia adalah pembagian waktu berdasarkan rencana pengaturan urutan kerja, daftar (tabel kegiatan) atau rencana kegiatan dengan pembagian waktu pelaksanaan yang terinci.

Penjadwalan merupakan proses penyusunan jadwal. Permasalahan penjadwalan biasanya berhubungan dengan penjadwalan kelas dalam sekolah atau perkuliahan dan juga dalam lingkup yang tidak jauh berbeda seperti penjadwalan pelajaran sekolah, penjadwalan ujian, atau dapat juga penjadwalan karyawan.

Penjadwalan mata kuliah merupakan proses pengaturan jadwal dengan memperhatikan dosen, ruang kelas, mata kuliah dan waktu yang disesuaikan dengan sejumlah batasan tertentu. Pada penjadwalan mata kuliah sejumlah mata kuliah harus dijadwalkan ke dalam ruang dan slot (pembagian) waktu tertentu dimana penjadwalan tersebut memperhatikan aturan-aturan dan batasan penjadwalan yang telah ditentukan.2.3 Kerangka Pemikiran Berdasarkan dukungan landasan teoritik yang diperoleh, maka dapat disusun kerangka pemikiran sebagai berikut:BAB IIIMETODE PENELITIAN3.1 Alat dan Bahan 3.1.1 Alat Sebagai alat yang digunakan pada penelitian ini menggunakan Compaq Presario CQ42, Intel Pentium T4500 2,30 GHz (2CPUs), RAM 1 GB, sistem operasi menggunakan Windows 7 Ultimate 32-bit. Untuk aplikasi algoritma Greedy dibangun dengan bahasa pemrograman VB.6 dan database MySQL.

3.1.2 Bahan Bahan utama dari penelitian ini antara lain sebagai berikut :

1) Objek Penelitian

Objek dalam penelitian ini menggunakan data-data yang berkaitan dengan sistem penjadwalan perkuliahan tahun akademik 2012/2013 pada jurusan Teknik Informatika Universitas Yudharta Pasuruan.

2) Metode Pengumpulan Data

a) Observasi

Observasi merupakan pengumpulan data yang dilakukan dengan mengamati sistem penjadwalan perkuliahan pada satu program studi perguruan tinggi. b) Wawancara Teknik pengumpulan data ini dilakukan dengan bertatap muka langsung kepada sumber dengan melakukan tanya jawab mengenai data yang akan diambil.

c) Tinjauan Pustaka

Tinjauan Pustaka merupakan teknik pengumpulan data yang dilakukan dengan media buku-buku pedoman yang berhubungan dengan pembuatan sistem ini diantaranya studi literatur algoritma Greedy untuk menyelesaikan permasalahan penjadwalan perkuliahan pada satu program studi perguruan tinggi.3.2 Metode Yang Diusulkan 1. Menganalisa Masalah

Mengumpulkan data yang diperlukan untuk data input dalam pembuatan aplikasi penjadwalan menggunakan Algoritma Greedy antara lain, data mata kuliah, data dosen, data kelas, data ruang, data timeslot, dan data kesediaan waktu dosen. Untuk output yang dihasilkan adalah sebuah jadwal kuliah yang optimal.

2. Perancangan Dalam hal ini akan dilakukan pembuatan diagram alir data, ERD (Entity Relationship Diagram), serta perancangan interface program input dan output sistem. 3. Implementasi

Mengimplementasikan hasil perancangan ke dalam modul program (coding program) dengan menggunakan algoritma Greedy.

4. Pengujian Menguji aplikasi apakah sudah tidak terjadi error dan sudah siap digunakan. Pengujian ini dilakukan terhadap data data yang diperlukan, diagram alir, perancangan ERD agar output yang dihasilkan optimal sesuai yang diharapkan. 3.2.1 Penjadwalan dengan Algoritma Greedy Algoritma Greedy secara umum dapat diilustrasikan pada flowchart di bawah ini :Mahasiswa dan DosenBagian Pengajaran

Gambar. Flowchart Penjadwalan 3.2.2 Strategi Greedy1. Greedy by profit.- Pada setiap langkah, pilih objek yang mempunyai keuntungan terbesar.-Mencoba memaksimumkan keuntungan dengan memilih objek yang paling menguntungkan terlebih dahulu.2. Greedy by weight. - Pada setiap langkah, pilih objek yang mempunyai berat teringan. - Mencoba memaksimumkan keuntungan dengan memasukkan sebanyak mungkin objek ke dalam knapsack. 3. Greedy by density.- Pada setiap langkah, knapsack diisi dengan objek yang mempunyai pi /wi terbesar.- Mencoba memaksimumkan keuntungan dengan memilih objek yang mempunyai keuntungan per unit berat terbesar. Pemilihan objek berdasarkan salah satu dari ketiga strategi di atas tidak menjamin akan memberikan solusi optimal. Contoh 4.w1 = 2; p1 = 12; w2 = 5; p1 = 15;

w3 = 10; p1 = 50; w4 = 5; p1 = 10 Kapasitas knapsack K = 16Solusi optimal: X = (0, 1, 1, 0) 3.3 Jadwal PenelitianNORencana Kegiatan

Bulan

April

2013Mei

2013Juni

2013Juli

2013

1Pengumpulan Data

2Analisis Data

3Pembuatan Sistem

4Penyelesaian Laporan

5evaluasi

Keterangan :

Pemeliharaan terhadap sistem yang dibangun akan dilakukan berkelanjutan.

Jadi, tidak hanya sebatas untuk skripsi ini.Daftar Pustaka

[1] Munir, R., Diktat Kuliah IF3051 Strategi Algoritma, Bandung, 2009.[2] Li Xiaofeng, Zhao Hai. Greedy Algorithm Solution of Flexible Flow Shop Scheduling Problem Changchun: College of Information Science and Engineering, 2010.

[3] Final Jadwal Perkuliahan Program S1Semester Genap 2010/2011, Fakultas Ilmu Komputer Universitas Indonesia. [4] M.M. Aldasht, M.H. Saheb, I. Najjar, M.H. Tamimi,& T.O. Takruri, University Course Scheduling Using Parallel Multi-Objective EvolutionaryAlgorithms,Journal of Theoretical and Applied Information Technology, vol.22, pp. 129-136, 2010.[5] Setiadi, Robert. (2001). Pemecahan Masalah Penjadwalan Kuliah dengan Menggunakan Teknik Intelligent Search [Online]. Tersedia: http://www.robertsetiadi.net/articles/snkk.htm [12 Oktober 2008].

[6] Munir, Rinaldi. (2005). Matematika Diskrit. Bandung: Informatika.[7] D. Mairiza & D.T.Soraya,Pendekatan Constraint Satisfaction dalam Perkuliahan di Fakultas Ilmu Komputer Universitas Indonesia,Jurnal Ilmu Komputer dan Informasi, vol.1, pp. 1-7, 2008.

1. Bentrok Ruang dan Waktu

3. Bentrok Dosen

4. Bentrok Kesediaan Waktu Dosen

5. Bentrok Lab

1. Data Pengampuan

2. Data Hari

3. Data Ruang

4. Data Jam

5. Data Kelas

1. Analisis

2. Desain Sistem

- Merancang DFD, ERD

3. Desain Aplikasi

- Membuat Antar Muka

Hasil:

Jadwal Perkuliahan

1. Mata Kuliah

2. Dosen

3. Ruang

4. Kelas

Jadwal Yang Efektif Menggunakan Algoritma Greedy

Perkuliahan dimulai

Petugas memberikan alternatif jaadwal yang baru

Petugas bagian penjadwalan mengecek apakah jadwal baru dapat dilaksanakan

Mengkonfirmasikan Pembatalan

Matakuliah

Mulai

Mahasiswa mengkonfirmasikan

Kepada dosen

Selesai

6