OPTIMASI PENJADWALAN PERKULIAHAN MENGGUNAKAN METODE SIMULATED ANNEALING (STUDI KASUS: PROGRAM STUDI TEKNIK INFORMATIKA UNIVERSITAS YUDHARTA PASURUAN) ABDUL AZIZ Fakultas Teknik, Program Studi Teknik Informatika Universitas Yudharta Pasuruan
ABSTRAK Penjadwalan berkaitan dengan mengalokasikan sumber daya yang terbatas untuk mengoptimalkan fungsi tujuan tertentu. Dan yang sering terjadi pada kegiatan penjadwalan perkuliahan dimungkinkan karena masalah dari segi mahasiswa, keterbatasan dosen, dan waktu ketersediaan dosen untuk mengajar kuliah. Selain itu, harus dipertimbangkan juga ketersediaan kelas sehingga kegiatan belajar dapat dilaksanakan. Permasalahan diatas biasanya yang sering disebut dengan University Timetabling Problems (UTP). Agar dalam proses pembuatan jadwal tidak terlalu banyak/meminimalkan constraint, maka dalam permasalahan ini diperlukan sebuah optimasi yang dapat diterapkan dalam membuat penjadwalan mata kuliah. Optimasi ini tidak bisa sepenuhnya menghasilkan hasil yang optimal tapi mendekati optimal. Simulated Annealing adalah algoritma metaheuristik pencarian lokal yang digunakan untuk mengatasi masalah diskrit. Masalah yang membutuhkan pendekatan Simulated Annealing adalah masalah-masalah optimasi kombinatorial, dimana ruang pencarian yang ada terlalu besar, sehingga hampir tidak mungkin ditemukan solusi eksak terhadap permasalahan ini. Kata Kunci: Penjadwalan Perkuliahan, Optimasi, Simulated Annealing
1. PENDAHULUAN Penjadwalan berkaitan dengan mengalokasikan sumber daya yang terbatas untuk mengoptimalkan fungsi tujuan tertentu [1]. Kendala yang terjadi pada kegiatan penjadwalan perkuliahan dimungkinkan karena masalah dari segi mahasiswa, keterbatasan dosen, dan waktu ketersediaan dosen untuk mengajar kuliah. Selain itu, harus dipertimbangkan juga ketersediaan kelas sehingga kegiatan belajar dapat dilaksanakan. Permasalahan diatas biasanya yang sering disebut dengan University Timetabling Problems (UTP)[2]. Bila menggunakan sistem manual maka masalah ini membutuhkan waktu proses yang cukup lama untuk pencarian solusinya, terlebih lagi bila ukuran 1
permasalahan semakin besar, seperti bertambahnya jumlah komponen dan tetapan atau syarat yang ditentukan oleh institusi tempat jadwal tersebut digunakan. Di Universitas Yudharta Pasuruan khususnya di Jurusan Teknik Informatika juga mengalami kendala seperti di atas. Untuk memecahkan masalah penjadwalan ada dua pendekatan yang dapat diambil yaitu dengan menggunakan metode solusi yang tepat dan pendekatan dengan menggunakan heuristik atau metode pendekatan [3]. Berdasarkan aspek-aspek di atas, agar dalam proses pembuatan jadwal tidak terlalu banyak/meminimalkan constraint, maka dalam permasalahan ini diperlukan sebuah optimasi
yang dapat diterapkan dalam membuat penjadwalan mata kuliah. Optimasi ini tidak bisa sepenuhnya menghasilkan hasil yang optimal tapi mendekati optimal. Ada beberapa metode optimasi yang sering digunakan untuk menyelesaikan penjadwalan yang masing-masing memiliki keunggulan sendiri [4]. Metode tersebut antara lain, Ant Colony, Simulated Annealing, dan Genetic Algorithm. Kelebihan Ant Colony adalah dapat diterapkan secara sempurna dengan perubahan minimal ke permasalahan optimasi kombinasi, Simulated Annealing memiliki keunggulan lebih cepat dalam menyelesaikan iterasinya, sedangkan Genetic Algorithm dapat digunakan untuk mencari berbagai solusi persoalan yang ada di dunia nyata. Pada penelitian ini akan menggunakan metode Simulated Annealing sebagai metode optimasi dalam penjadwalan. Simulated Annnealing adalah algoritma penjadwalan probabilistik yang dimodelkan dari proses metalurgi dalam ilmu fisika [5]. Karena kepopularitasannya dan fleksibilitas dalam yang berjudul “Schedullig: Theory, Algorithms, and Systems”, penjadwalan merupakan proses pembuatan keputusan yang yang digunakan secara teratur yang berhubungan dengan sumber daya alokasi tugas selama periode waktu tertentu dan tujuannya adalah untuk mengoptimalkan satu atau lebih tujuan [8]. Dalam buku “School Timetable Construction: Algorithms Complexity” karya Robertus J. Willemen, jadwal adalah tabel peristiwa yang diatur sesuai dengan waktu. Sebuah jadwal harus memenuhi sejumlah persyaratan dan harus memuaskan keinginan semua orang yang terlibat secara bersamaan dengan sebaik-baiknya. Waktu kejadian harus sedemikian rupa bahwa tidak ada yang memiliki lebih dari satu acara di waktu yang sama [9]. Jadi, 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. 2
permasalahan metaheuristik ini yang membuat penulis menggunakan metode Simulated Annealing [6]. Diharapkan dengan algoritma Simulated Annealing ini penjadwalan yang dibuat bisa lebih optimal. 2. LANDASAN TEORI 2.1. Penjadwalan Definisi jadwal pada sebuah kutipan kamus bahasa Indonesia, jadwal adalah pembagian waktu berdasarkan rencana pengaturan urutan kerja, daftar (tabel kegiatan) atau rencana kegiatan dengan pembagian waktu pelaksanaan yang terinci.Adapun pengertian penjadwalan menurut beberapa ahli: Dalam kutipan buku “Multicriteria Schedulling: Theory, Models and Algorithms” karya Vincent T’kindt and Jean-Charles Billaut, penjadwalan adalah proses pengolahan karya dengan memanfaatkan sumber daya untuk melakukan tugas dan memperbaiki waktu mulai mereka [7]. Menurut Michael L. Pinedo dalam bukunya 2.2. Penjadwalan Perkuliahan 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 aturanaturan dan batasan penjadwalan yang telah ditentukan. Dalam kutipan buku “School Timetable Contruction”, ada beberapa survey mengenai masalah penjadwalan. Schaerf memberikan gambaran literatur tentang masalah penjadwalan [9].
Dosen
untuk menemukan fungsi biaya minimum yang mungkin diproses [10]. Mahasisw a
Mata Kuliah
Waktu
Ruang
Gambar 1 Konsep penjadwalan 2.3. Optimasi Optimasi merupakan aktivitas untuk mendapatkan hasil yang terbaik dari pilihan yang tersedia, yang disebut optimal. Optimasi juga merupakan bidang interdisipliner matematika dan ilmu komputer yang membicarakan jumlah untuk memilih elemen terbaik dari beberapa set alternatif yang tersedia dan mempelajari sifat-sifatnya. Optimasi telah dipakai di mana-mana seperti ke berbagai arah penelitian teoritis dan terapan matematika modern. Optimasi dalam arti luas merupakan suatu disiplin yang mencakup berbagai bidang, termasuk nonsmooth dan analisis cembung, analisis numerik, teori kompleksitas komputasi, dan teori algoritma. Misalnya, terutama dalam pengaturan dimensi tak terbatas, hanya mampu menjamin adanya solusi. Optimasi modern memiliki asal-usul dalam pemrograman linier, dikembangkan pada tahun 1930 dan 1940-an oleh Leonid Kantorovich, John von Neumann dan George Dantzig, yang berkaitan dengan masalah meminimalkan fungsional linear. 2.4. Simulated Annealing Simulated Annealing adalah algoritma metaheuristik pencarian lokal yang digunakan untuk mengatasi masalah diskrit. Masalah yang membutuhakan pendekatan Simulated Annealing adalah masalah-masalah optimasi kombinatorial, dimana ruang pencarian yang ada terlalu besar, sehingga hampir tidak mungkin ditemukan solusi eksak terhadap permasalahan ini. Publikasi tentang pendekatan ini pertama kali dilakukan oleh Kirkpatrick, Gelett dan Vecchi pada tahun 1983 yang diaplikasikan pada desain optimal hardware komputer, dan juga pada masalah Traveling Salesman Problem. Dan Cerny pada tahun 1985 3
global
Menurut Kirkpatrick (Kirkpatrick, 1983), ada tiga hal utama yang perlu diperhatikan dalam penggunaan Simulated Annealing untuk memodelkan suatu permasalahan [5]: 1. Representasi yang akurat dari konfigurasi dalam suatu permasalahan. 2. Proses modifikasi, langkah acak atau perubahan apa yang harus dilakukan terhadap elemen-elemen konfigurasi untuk menghasilkan konfigurasi berikutnya. 3. Fungsi evaluasi atau fungsi objektif yang dapat menyatakan baik-buruknya suatu solusi terhadap permasalahan. Optimasi dengan metode simulated annealing ini membutuhkan: a. Spesifikasi sebuah fungsi objektif nilai tunggal dengan baik. b. Deskripsi ruang variabel independen dan daerah di mana solusi akan dicari. c. Definisi lingkungan dari suatu titik dalam ruang variabel independen. d. Prosedur yang menghasilkan pseudo acak melalui lingkungan yang berdampingan. e. Kriteria untuk penghentian random walk. Pada Gambar 2 disajikan flowchart Simulated Annealing secara umum menurut Dr. Ayman Hammadeh [11]. Struktur Algoritma Simulated Annealing secara umum adalah sebagai berikut [12]: 1. Cari solusi awal S menggunakan parameter awal dan metode heuristik awal yang dapat ditentukan sendiri. 2. Tetapkan suatu nilai temperatur awal T yang cukup tinggi, dimana T>0 3. Pada keadaan titik frozen, lakukan: a. Lakukan L kali: i. Cari solusi neighbourhoodS’ dari S menggunakan metode yang dapat ditetapkan sendiri. ii. Ä = Nilai objektif (S’) – Nilai objektif (S). iii. Jika Ä<0, maka tetapkan S=S’, jika tidak maka tetapkan S=S’ dengan probabilitas exp(-Ä/T).
b. Turunkan T, T = 0.9*T c. Dapatkan solusi optimal.
Tabel 3 Physical Annealing Fisika (Termodinamika) Keadaan Sistem
Start
Energi Perubahan Keadaan Temperatur
Masukan dan Bentuk State Awal dari
Keadaan Beku
Tetapkan Suhu Awal
3. METODOLOGI 3.1. Tahapan Penelitian
Hasilkan Solusi Baru
Apakah Solusi Baru Lebih Baik Dari Solusi Sekarang ?
Simulated Annealing Solusi Yang Mungkin Biaya Solusi Tenaga Parameter Kontrol Solusi Heuristik
Ganti Solusi Lama Dengan
Apakah Percobaan Sudah Maksimal Untuk Suhu Saat Ini ?
Turunkan Suhu Dengan Tingkatan Yang Ditentukan
Mencapai Suhu Terendah Dibolehkan
Penelitian ini dilakukan untuk merancang dan membuat aplikasi penjadwalan mata kuliah yang fungsinya untuk membantu proses dalam hal pembuatan jadwal mata kuliah. Hal ini dikarenakan karena dalam pembuatan jadwal masih terdapat bentrokan (constraint) serta penyusunannya masih manual dan membutuhkan waktu yang lama sehingga menjadi tidak efektif dan efisien. 3.2. Analisa Data Dari analisa proses pembuatan penjadwalan ada beberapa hal yang harus dioptimasi menggunakan menggunakan algoritma penjadwalan sehingga aplikasi penjadwalan yang dibuat dapat bekerja optimal. Hasil analisa terdapat beberapa permasalahan yang perlu dilakukan pengoptimasian, yaitu: 1. Tidak ada bentrok jam mengajar dosen. 2. Tidak ada bentrok ruang perkuliahan.
Stop
Gambar 2 SA secara umum Berikut ini adalah pemetaan dari Physical Annealing ke Simulated Annealing [11]:
3. Dosen mengajar pada jam-jam dimana dosen tersebut tidak berhalangan untuk mengajar. 4. Ruang perkuliahan terisi dengan maksimal dan merata. 3.3. Penulisan Kode Program Penulisan aplikasi penjadwalan ini menggunakan bahasa pemrograman Visual Basic .Net, sedangkan untuk penyimpanan datanya menggunakan database MySql. Dengan menggunakan algoritma penjadwalan maka dimulailah teknik pengoptimasian dalam
4
tahapan ini. Selain itu teknik komputerisasi lebih lanjut juga dilakukan sehingga aplikasi penjadwalan yang diinginkan sesuai dengan harapan. 3.4. Uji Coba
Dalam sebuah program aplikasi yang digunakan untuk membantu pengguna dalam melakukan penjadwalan mata kuliah. Berikut ini adalah tampilan utama program dapa dilihat pada gambar 4.1 berikut ini:
Pada tahap ini diuji cobakan dengan data-data penjadwalan dan constraint yang ada menggunakan metode Simulated Annealing untuk proses pengoptimasian. Sedangkan untuk uji coba aplikasi menggunakan teknik Blackbox untuk mengujinya. 3.5. Perancangan Perangkat Lunak (Software) Pada penelitian ini kami berikan sebuah desain awal aplikasi yang akan digunakan sebagai interface di komputer. Data penjadwalan yang terdiri dari gabungan dari data mata kuliah, data dosen, data ruang, data waktu dan kelas. Selanjutnya data tersebut dilakukan proses generate jadwal. Saat proses generate pertama menghasilkan jadwal awal, bila jadwal awal kondisinya masih buruk maka dilakukan generate ulang yang menghasilkan jadwal baru yang merupakan jadwal awal yang di generate ulang untuk menghasilkan jadwal yang lebih baik lagi. Bila nilai bentrok yang baru lebih baik daripada nilai bentrok jadwal awal maka jadwal baru yang dipakai, begitu sebaliknya. Pengontrol ditetapkan sebanyak mungkin untuk membatasi proses iterasi. Nilai alpha digunakan untuk menurunkan nilai pengontrol secara bertahap untuk mencapai kondisi maksimal.
Gambar 5Interface Menu Utama 1. Input Data Program memerlukan beberapa interface untuk melalukan input data komponen penjadwalan yang meliputi beberapa interface, antara lain:
Gambar 6 Interface Dosen
. Ouput dari aplikasi berupa sebuah jadwal yang dapat dilihat berdasarkan angkatan kuliah. Output ini merupakan jadwal final dari proses Simulated Annealing. Jadwal final dapat diambil dengan menghentikan iterasi dengan syarat nilai bentrokan bernilai 0. Constraint adalah aturan penjadwalan yang digunakan untuk menghitung nilai bentrokan. Ada dua yaitu hard constraint (tidak boleh dilanggar) dan soft constraint (boleh dilanggar). 4. HASIL DAN PEMBAHASAN 4.1. Deskripsi Program 5
Gambar 7 Interface Kelas
Annealing. Pada tabel 11 dijelaskan pengontrol jadwal 100 untuk memberikan gerak bebas pada komponen penjadwalan. Pereduksi sebesar 1. Apabila parameter tersebut sudah disimpan, maka proses selanjutnya adalah pembuatan jadwal melalui tombol proses.
Gambar 8 Interface Hari
Gambar 12 Form Proses Jadwal
Gambar 9 Interface Jam 2. Konfigurasi Hal-hal yang perlu untuk dikonfigurasi adalah kombinasi parameter Simulated Annealing, pengontrol jadwal dan pereduksi pengontrol jadwal. Gambar 10 berikut adalah form konfigurasi parameter Simulated Annealing:
Gambar 10 Form Parameter Simulated Annealing 4.2. Penerapan Program Pada Penjadwalan Kuliah Tabel 11 Kombinasi Default Parameter
5. PENUTUP 5.1. Kesimpulan Dari penelitian ini, dapat disimpulkan bahwa penggunaan metode optimasi menggunakan Simulated Annealing pada penjadwalan dapat diimplementasikan dengan baik. Selain itu, masih terdapat beberapa kendala yang belum tertangani dalam aplikasi ini. Kendala tersebut antara lain pada penanganan masalah jam mengajar dengan sks. Sedangkan untuk masalah ruang dan hari sudah tertangani dengan baik tanpa adanya bentrokan. Dalam proses iterasinya, Simulated Annealing lebih cepat dalam memproses penjadwalan karena Simulated Annealing memiliki iterasi sedikit pada prosesnya sehingga proses pembuatan jadwal menjadi lebih cepat dibandingkan dengan algoritma lain yang proses iterasinya lebih banyak. 5.2. Saran Bagi Peneliti
Parameter Pengontrol Jadwal Pereduksi Pengontrol
Nilai 100 1
Program akan dapat digunakan untuk menyelesaikan masalah penjadwalan dengan berbagai kombinasi parameter Simulated 6
Setelah membuat aplikasi ini, diharapkan peniliti bisa lebih mengembangkan aplikasi yang sudah ada agar lebih baik lagi sehingga mampu memberikan kontribusi pada perkembangan algoritma tersebut. Bagi Instansi
Konstrain dapat ditambah dan disesuaikan dengan kebutuhan dan persyaratan pembuatan jadwal yang berlaku.
Michael L. Pinedo, Schedullig: Theory, Algorithms, and Systems, Fourth Edition ed. New York, USA: Springer.
Bagi Pembaca Ruang lingkup aplikasi ini masih sangat kecil yaitu di lingkup Jurusan. Peneliti berharap untuk penelitian selanjutnya dapat dikembangkan lagi untuk ruang lingkup yang lebih besar.
Robertus J. Willemen, School Timetable Construction: Algorithms Complexity. Eindhoven, Netherlands, 2002.
DAFTAR PUSTAKA V. Selladurai P. V. Senthiil, "Optimal Job Shop Scheduling Performance Enhancement Through Computer Based Simulated Annealing Technique," 2007. Ivan Nugraha, "Aplikasi Algoritma Genetik Untuk Optimasi Penjadwalan Kegiatan Belajar Mengajar," Institut Teknologi, Bandung, 2008. L.J.M Cluitmans, Using Genetic Algorithms for Scheduling Data Flow Graphs.: Eindhoven Univerisity of Technology Research Reports. Komang Setemen, "Implementasi Algoritma Genetika Dalam Pengembangan Sistem Aplikasi Penjadwalan Kuliah," Manajemen Informasi Universitas Diponegoro, Semarang, Skripsi ISSN 1829-5282,. Sugeng Sad Harjono, "Optimasi Penjadwalan Perkuliahan Jurusan Teknik Informatika Universitas Islam Negeri Maulana Malik Ibrahim Malang Menggunakan Metode Simulated Annealing," Teknik Informatika Universitas Negeri Maulana Malik Ibrahim, Malang, Skripsi 2012. Sheldon H. Jacobson Alexander G. Nikolaev, Handbook of Metaheuristics, Second Edition ed., Jean-Yves Potvin Michel Gendreau, Ed. New York: Springer. Jean-Charles Billaut Vincent T’kindt, Multicriteria Schedulling: Theory, Models and Algorithms, Second Edition ed. France: Springer.
7
C. D. Gelatt, M. P. Vecchi S. Kirkpatrick, "Optimization by Simulated Annealing," JSTOR, vol. 220, pp. 671-680, May 1983. Dr. Ayman Hammadeh, "Intelence Algorithms Simulated Annealing Algorithn," Aleppo University, 2011-2012. N. Jawahar, P. Aravindan, S.G. Ponnambalam, "A Simulated Annealing Algorithm for Job Shop Scheduling," vol. 10, no. 8, pp. 767-777. Lina Maria Ulfa, "Optimasi Penjadwalan Perkuliahan Menggunakan Algoritma Genetika," Universitas Negeri Maulana Malik Ibrahim, Malang, Skripsi 2011. Ruey-Maw Chen and Hsiao-Fang Shih, "Solving University Course Timetabling Problems Using Constriction Particle Swarm Optimization with Local Search," MDPI, no. 6, pp. 227-244, April 2013. Phuc Nguyen and Noung Tran Khang Nguyen, "A hybrid algorithm of Harmony Search and Bees Algorithm for a University Course Timetabling Problem," IJCSI, vol. IX, no. 1, January 2012. Kirill
Fakhroutdinov. Unified Modeling Language. [Online]. http://www.umldiagrams.org/use-case-diagrams.html
(2013)
Smart Draw. [Online]. http://www.smartdraw.com/resources/tut orials/uml-activity-diagram/
Tripod. [Online]. http://myyee.tripod.com/cs457/dfd.htm Thomas Weise. Global Optimation Algorithms: Theory and Aplication. [Online]. http://www.it-weise.de/
8
