PEMODELAN OPTIMAL KONSTRUKSI JADWAL PERKULIAHAN DAN IMPLEMENTASINYA
KHAIRUNNISA
SEKOLAH PASCASARJANA INSTITUT PERTANIAN BOGOR BOGOR 2008
PERNYATAAN MENGENAI TESIS DAN SUMBER INFORMASI Dengan ini saya menyatakan bahwa tesis dengan judul Pemodelan Optimal Konstruksi Jadwal Perkuliahan dan Implementasinya adalah karya saya dengan arahan dari komisi pembimbing dan belum diajukan dalam bentuk apapun kepada perguruan tinggi manapun. Sumber informasi yang berasal atau dikutip dari karya yang diterbitkan maupun tidak diterbitkan dari penulis lain telah disebutkan dalam teks dan dicantumkan dalam Daftar Pustaka di bagian akhir tesis ini.
Bogor, Maret 2008
Khairunnisa NIM G551050101
ABSTRACT KHAIRUNNISA. An Optimal Modeling for Constructing University Timetabling and Its Implementation. Under direction of AMRIL AMAN and I GUSTI PUTU PURNABA. The construction of timetable that satisfies all operational rules and needs in an academic institution, while at the same time fulfills as many of the wishes and requirements of the teaching staff and the students is an important but extremely difficult task. Formally, timetable problem is defined as the process of assigning courses to specific time periods and to specific classrooms suitable for the number of the student and the needs of the each course. This paper presents an Integer Programming formulation of the timetable problem. A prototype of this model is implemented using LINGO software and produced timetable that satisfies all constraints. Keywords : timetabling, integer programming, university timetabling,
RINGKASAN KHAIRUNNISA. Pemodelan Optimal Konstruksi Jadwal Perkuliahan dan Implementasinya. Dibimbing oleh AMRIL AMAN dan I GUSTI PUTU PURNABA. Penjadwalan kuliah merupakan kegiatan yang mengawali pergantian semester di setiap perguruan tinggi. Proses ini harus memperhitungkan banyaknya mata kuliah, ketersediaan ruang, dan rentang waktu yang digunakan. Inti dari penjadwalan kuliah adalah menjadwalkan beberapa komponen yang terdiri dari mata kuliah, ruang, dan waktu dengan memperhatikan sejumlah batasan dan syarat tertentu Permasalahan yang dihadapi penjadwal terletak pada lebih banyaknya mata kuliah yang harus dijadwalkan daripada ruang yang tersedia, kesesuaian kebutuhan perkuliahan dengan fasilitas ruangnya, kapasitas ruang yang harus sesuai dengan jumlah mahasiswa, serta keinginan pengajar untuk mengajar pada suatu hari atau jam tertentu. Sejumlah algoritma dikembangkan untuk menyelesaikan masalah ini agar sesuai dengan kebutuhan instansi yang memerlukannya. Masalah penjadwalan kuliah menjadi topik yang dibahas dalam penelitian ini. Penyelesaian yang dicari berupa suatu model matematika yang merepresentasikan masalah penjadwalan kuliah yang sesuai dengan keadaan di Fakultas Ilmu Tarbiyah dan Keguruan (FITK) Universitas Islam Negeri (UIN) Syarif Hidayatullah Jakarta. Model tersebut kemudian diimplementasikan pada suatu kondisi. Untuk membuat penjadwalan kuliah perlu diketahui semua mata kuliah yang ditawarkan, dosen yang mengajar, peserta perkuliahan, bobot sks dan spesifikasi ruang yang diperlukan. Kemudian ditentukanlah hari dan jam perkuliahan. Pengalokasian hari dapat dirancang sesuai keinginan pengajarnya. Misalkan pengajar dapat meminta hari tertentu untuk mengajar mata kuliah atau untuk tidak mengajar mata kuliah. Setiap mata kuliah memerlukan jam untuk perkuliahan. Jam dibagi menjadi lima, yaitu: jam pertama (07.30–09.10), kedua (09.20–11.00), ketiga (11.10–12.50), keempat (13.30–15.10) dan kelima (15.30– 17.10). Sebagaimana hari, pengalokasian jam juga dapat dirancang sesuai keinginan pengajarnya. Perkuliahan memerlukan ruang yang fasilitasnya dapat menunjang pelaksanaan kuliah tersebut. Misal mata kuliah Pemprograman Komputer memerlukan ruang yang difasilitasi komputer agar perkuliahan efektif. Pada mata kuliah yang ditawarkan perlu diketahui pengajarnya, pesertanya, banyak sks serta spesifikasi ruang yang diperlukan. Jika pengajarnya telah ketahui maka dapat ditentukan hari dan waktu kesukaan pengajar tersebut atau penentuannya diserahkan pada penjadwal. Bila pengajar akan mengajarkan mata kuliah yang sama pada peserta yang berbeda biasanya pengajar meminta hari yang sama untuk mengajar mata kuliah tersebut dalam jam yang berurutan. Karena terbatasnya sumber daya pengajar maka ada beberapa mata kuliah yang berbeda diajarkan oleh pengajar yang sama. Sehingga diharapkan tidak ada kejadian berupa mata kuliah yang berbeda dengan pengajar yang sama dialokasikan pada hari dan jam yang sama.
Mata kuliah juga harus dibedakan dari pesertanya. Peserta perkuliahan terdiri dari jurusan, semester dan kelas yang berbeda. Penjadwalan dirancang agar tidak ada kuliah-kuliah wajib yang harus diikuti suatu peserta terjadwal pada hari dan jam yang sama. Jadi tiap peserta hanya mengambil tepat satu mata kuliah pada suatu hari dan jam tertentu. Masalah penjadwalan kuliah tersebut disajikan dalam model Integer Programming. Model tersebut mempunyai fungsi obyektif memenuhi semua batasan utama serta memaksimalkan nilai kepuasan penggunaan waktu yang disukai untuk perkuliahan. Model Integer Programming untuk masalah penjadwalan kuliah diselesaikan dengan menggunakan metode branch and bound yang tersedia pada software LINGO 8.0. Nilai kepuasan penggunaan waktu dilambangkan dengan koefisien nilai yang diberikan pada variabel hari dan jam. Waktu yang disukai untuk perkuliahan diberikan koefisien nilai yang tinggi sedangkan pada waktu yang kurang disukai diberikan koefisien nilai yang lebih rendah. Hal ini menyebabkan penjadwalan dengan menggunakan waktu yang disukai untuk perkuliahan memiliki fungsi obyektif yang lebih besar daripada penjadwalan dengan menggunakan waktu yang kurang disukai untuk perkuliahan. Model diimplementasikan pada beberapa skenario. Contoh suatu skenario mempunyai koefisien nilai nol pada jam tertentu di tiap harinya sedangkan skenario lain memiliki koefisien nilai nol pada jam tertentu di tiap harinya dan pada satu hari tertentu. Berdasarkan skenario tersebut dihasilkan dua jadwal yang nilai fungsi obyektifnya berbeda, yaitu skenario pertama lebih besar daripada skenario kedua. Kemudian melalui jadwal yang dihasilkan dapat dipastikan bahwa batasan utama tidak terlanggar walaupun ada perkuliahan yang terjadwal di waktu perkuliahan yang koefisiennya bernilai nol. Berdasarkan hal tersebut dapat disimpulkan bahwa model menghasilkan jadwal bernilai optimal dengan tetap mengakomodasi batasan-batasan serta mata kuliah yang terjadwal pada waktu yang kurang disukai terjadi agar tetap terpenuhi batasan yang ada. Kata kunci : penjadwalan, integer programming, penjadwalan kuliah
© Hak Cipta milik Institut Pertanian Bogor, tahun 2008 Hak cipta dilindungi Undang-undang 1. Dilarang mengutip sebagian atau seluruh karya tulis ini tanpa mencantumkan atau menyebutkan sumber. a. Pengutipan hanya untuk kepentingan pendidikan penelitian, penulisan karya ilmiah, penyusunan laporan, penulisan kritik atau tinjauan suatu masalah b. Pengutipan tidak merugikan kepentingan yang wajar Institut Pertanian Bogor 2. Dilarang mengumumkan dan memperbanyak sebagian atau seluruh karya tulis dalam bentuk apapun tanpa izin Institut Pertanian Bogor
PEMODELAN OPTIMAL KONSTRUKSI JADWAL PERKULIAHAN DAN IMPLEMENTASINYA
KHAIRUNNISA
Tesis sebagai salah satu syarat untuk memperoleh gelar Magister Sains pada Departemen Matematika
SEKOLAH PASCASARJANA INSTITUT PERTANIAN BOGOR BOGOR 2008
Judul Tesis : Pemodelan Optimal Implementasinya Nama : Khairunnisa NIM : G551050101
Konstruksi
Jadwal
Perkuliahan
dan
Disetujui, Komisi Pembimbing
Dr. Ir. Amril Aman, M.Sc. Ketua
Dr. Ir. I Gusti Putu Purnaba, DEA Anggota
Diketahui,
Ketua Program Studi Matematika Terapan
Dekan Sekolah Pascasarjana
Dr. Ir. Endar H.Nugrahani, MS.
Prof. Dr. Ir. Khairil A. Notodipuro, MS
Penguji Luar Komisi pada Ujian Tesis : Ir. N.K. Kutha Ardana, M.Sc.
Tanggal Ujian : 21 Februari 2008
Tanggal Lulus :
Untuk Ibundaku serta saudara-saudaraku T’ Nida, K’ Ihan, T’ Fifi, T’ Huri, K’ Ruham, Anam, T’ Fakhroh, Mas Heri, Mas Hendro, T Septi, dan keponakan-keponakanku Fadli, Hilma, Muthia, Raidha, Haidar, Aisha, Rahiel, dan Syafiq Terima kasih atas dukungan dan kasih sayangnya Semoga Allah memberi berkah dan ridhaNya
PRAKATA Puji dan syukur penulis panjatkan kepada Allah SWT atas segala karuniaNya sehingga karya ilmiah ini berhasil diselesaikan. Shalawat serta salam kepada Nabi Muhammad SAW. Judul yang dipilih pada penelitian yang dilaksanakan sejak Februari 2007 ini adalah Pemodelan Optimal Konstruksi Jadwal Perkuliahan dan Implementasinya Terima kasih penulis sampaikan kepada Dr. Ir. Amril Aman, M.Sc. dan Dr. Ir. I Gusti Putu Purnaba, DEA atas bimbingannya serta Ir. N.K. Kutha Ardhana, M.Sc. selaku penguji atas saran-sarannya. Ucapan terima kasih juga penulis sampaikan kepada seluruh staf pengajar dan staf lainnya di Departemen Matematika IPB. Ungkapan terima kasih juga disampaikan kepada: Yth. Dekan dan Pembantu Dekan Fakultas Ilmu Tarbiyah dan Keguruan UIN Syarif Hidayatullah Jakarta beserta seluruh staf, khususnya rekan-rekan di Jurusan Pendidikan Matematika. Teman-teman penulis di Departemen Matematika IPB, khususnya di SPs IPB, Eva Musyrifah, Yoanita Historiani, Cecep AHFS, Syamsuri dan Jaenudin. Teman serumah di Puri Hapsara (Mbak Diffah UNS, Bu Syahriani dan Bu Sri Purwanti UNHAS, Bu Insun Sangadji UNPATI, Mbak Elly dan Mbak Meisji UNSRI, Mbak Rahmi Univ. Jambi dan Ifa), serta semua pihak yang tak dapat penulis sebutkan satu persatu. Semoga Allah SWT senantiasa memudahkan semua urusan kita. Ytc. Ibunda dan Ayahandaku, Dra. Hj. Rohmah Sarmala dan H. Moch. Chairuddin, BS (Alm) atas segala doa, dukungan dan kasih sayangnya kepada penulis. Kepada kakak-kakakku, adikku, beserta seluruh keponakanku, terima kasih atas segala perhatian, pengertian dan bantuannya sehingga studi S2 ini dapat diselesaikan. Semoga karya ilmiah ini bermanfaat. Bogor, Maret 2008 Khairunnisa
RIWAYAT HIDUP Penulis dilahirkan di Jakarta pada tanggal 4 April 1981 dari ayah H. Moch. Chairuddin, BS dan ibu Dra. Hj. Rohmah Sarmala. Penulis merupakan putri keenam dari tujuh bersaudara. Tahun 1999 penulis lulus dari SMUN 47 Jakarta. Pendidikan sarjana ditempuh di Jurusan Pendidikan Matematika Fakultas Ilmu Tarbiyah dan Keguruan Universitas Islam Negeri Syarif Hidayatullah Jakarta dan menamatkannya pada tahun 2003. Kesempatan untuk melanjutkan ke program Magister pada Program Studi Matematika IPB diperoleh pada tahun 2005. Penulis adalah staf pengajar di Jurusan Pendidikan Matematika FITK UIN Syarif Hidayatullah sejak Agustus 2005. Mata kuliah yang diajarkan adalah Matematika Dasar.
DAFTAR ISI Halaman DAFTAR TABEL .....................................................................................
xii
DAFTAR LAMPIRAN .............................................................................
xiii
PENDAHULUAN ....................................................................................
1
Latar Belakang..................................................................................
1
Tujuan ..............................................................................................
3
Manfaat .............................................................................................
3
TINJAUAN PUSTAKA ............................................................................
4
Penjadwalan Perkuliahan di Beberapa Universitas ..........................
4
Landasan Teori .................................................................................
10
Linear Programmning .............................................................
10
Integer Programmning ............................................................
11
Branch and Bound...................................................................
12
ALUR PENELITIAN ................................................................................
18
PEMODELAN ...........................................................................................
20
Deskripsi Masalah ............................................................................
20
Formulasi Masalah ............................................................................
22
Model ................................................................................................
23
PEMBAHASAN ........................................................................................
25
Implementasi Model .........................................................................
25
Beberapa Skenario ............................................................................
30
SIMPULAN DAN SARAN .......................................................................
35
DAFTAR PUSTAKA ...............................................................................
36
LAMPIRAN...............................................................................................
37
DAFTAR TABEL Halaman Tabel 1 Daftar Mata Kuliah yang Ditawarkan...........................................
25
Tabel 2 Indeks Mata Kuliah.......................................................................
26
Tabel 3 Koefisien Nilai ..............................................................................
26
Tabel 4 Hasil Simulasi ...............................................................................
29
Tabel 5 Beberapa Skenario .......................................................................
30
Tabel 6 Skenario I ......................................................................................
31
Tabel 7 Skenario II.....................................................................................
32
Tabel 8 Skenario III ...................................................................................
33
Tabel 9 Skenario IV ...................................................................................
34
DAFTAR LAMPIRAN Halaman Lampiran 1 Penulisan Program dan Outputnya ........................................
38
Lampiran 2 Output Beberapa Skenario......................................................
42
DAFTAR LAMPIRAN Halaman Lampiran 1 Penulisan Program dan Outputnya ........................................
38
Lampiran 2 Output Beberapa Skenario......................................................
42
