MASALAH PENJADWALAN MATA KULIAH : STUDI KASUS DI DEPARTEMEN MATEMATIKA FMIPA IPB
MAYANG SARI G54103006
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2007
ABSTRACT In every beginning of semester, some colleges and universities facing the same problem, which is usage of classrooms for supporting lecturing activities. Generally, in every semester, number of students that following a lecturing is not always be the same. It will generate problem which related to the classroom capacities. This Lecturing Scheduling Problem can be modeled as an Integer Linear Programming problem (ILP). ILP is the problem of optimization with objective function and constraints which is linear and also integer variables. The problem of scheduling model is made based on availability of rooms, arranged time everyday in period of five days (Monday to Friday) and also a number of courses that provided. The schedule made in such a manner so that fulfill main constraint, that is scheduling of all courses, non-overlapping between major courses in the same semester, non-overlapping between supporting courses for same enthusiasm area, and also fulfill a number of additional constraints. To formulate the problem into ILP, we need some supporting assumptions. It is also needed to define a decision variable : xi , j ,k =
{
1 ; if course j is taught at time period i in classroom k ; 0 ;
otherwise
for each time period i, for each course j, and for each classroom k. Because the major goals are determining scheduling which is loading as many as possible courses that provided, the objective function of this problems is modeled as follows :
Maximize
i j k
xi , j , k
This study discuss how to formulate the Lecturing Scheduling Problem into ILP by taking a case study at the Department of Mathematics, Faculty of Mathematic and Natural Science, IPB. The assumptions we used are courses that available consist of major courses and supporting courses, and major courses in fourth semester could be taken at the same time with major courses at sixth semester. The data used are those for time periods (i), i = 1, 2, …, 19, course that provided (j) which is, j = 1, 2, …, 42 and room (k) that been used, k = 1, 2, …, 12. To solve this model we need Lingo 8.0 software with Branch and Bound method. The resulted output is usage of classroom schedule that fulfilling all main constraints and existing additional constraints.
ABSTRAK MAYANG SARI. Masalah Penjadwalan Mata Kuliah : Studi Kasus di Departemen Matematika FMIPA IPB. Dibimbing oleh PRAPTO TRI SUPRIYO dan SISWANDI.
Di setiap awal semester, beberapa sekolah tinggi dan universitas menghadapi permasalahan yang sama, yakni penjadwalan penggunaan ruang kuliah untuk memenuhi kegiatan perkuliahan. Pada setiap semester, jumlah mahasiswa yang mengikuti suatu mata kuliah pada umumnya tidak selalu sama, sehingga menimbulkan permasalahan yang terkait dengan kapasitas ruang kuliah. Permasalahan penjadwalan ruang kuliah ini dapat dimodelkan sebagai masalah Integer Linear Programming (ILP). ILP adalah masalah optimisasi dengan fungsi objektif dan kendala yang linear serta variabel integer. Pemodelan masalah penjadwalan dibuat berdasarkan ketersediaan sejumlah ruangan, waktu yang diatur setiap harinya dalam periode lima hari (senin s.d. jum’at) serta sejumlah mata kuliah yang ditawarkan. Jadwal tersebut dibuat sedemikian rupa sehingga memenuhi kendala utama, yaitu semua mata kuliah yang ditawarkan terjadwalkan, tidak ada overlapping (saling tumpang tindih) antar mata kuliah wajib di semester yang sama, tidak ada overlapping antar mata kuliah pilihan untuk bidang minat yang sama, serta memenuhi sejumlah kendala tambahan. Untuk memformulasikan masalah tersebut ke dalam ILP diperlukan beberapa asumsi yang mendukung. Selain itu diperlukan pula pendefinisian suatu variabel keputusan : xi , j ,k =
{
1 ;
jika mata kuliah j diselenggarakan pada waktu i dalam ruangan k
0 ;
selainnya
untuk setiap periode waktu i, untuk setiap mata kuliah j, dan untuk setiap ruangan k. Karena tujuan utama adalah menentukan penjadwalan yang memuat sebanyak mungkin mata kuliah yang ditawarkan, maka fungsi objektif dari permasalahan ini dimodelkan sebagai berikut : Maksimumkan
i j k
xi , j , k
Tulisan ini membahas bagaimana memformulasikan masalah penjadwalan mata kuliah dalam ILP dengan mengambil contoh kasus di Departemen Matematika FMIPA IPB. Asumsi yang digunakan adalah mata kuliah yang diselenggarakan terdiri dari mata kuliah wajib dan mata kuliah pilihan, dan mata kuliah wajib semester empat boleh diselenggarakan bersamaan dengan mata kuliah wajib semester enam. Data yang digunakan yaitu periode waktu (i), i = 1, 2, …, 19, mata kuliah (j) yang ditawarkan, j = 1, 2, …, 42 dan ruangan (k) yang dipakai, k = 1, 2, …, 12. Penyelesaian model ini menggunakan software Lingo 8.0 dengan metode Branch and Bound. Output yang dihasilkan adalah jadwal penggunaan ruang kuliah yang memenuhi semua kendala utama dan kendala tambahan yang ada.
MASALAH PENJADWALAN MATA KULIAH : STUDI KASUS DI DEPARTEMEN MATEMATIKA FMIPA IPB
Skripsi Sebagai salah satu syarat untuk memperoleh gelar Sarjana Sains pada Fakultas Matematika dan Ilmu Pengetahuan Alam Institut Pertanian Bogor
Oleh : MAYANG SARI G54103006
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2007
Judul
:
Nama NRP
: :
Masalah Penjadwalan Mata Kuliah : Studi Kasus di Departemen Matematika FMIPA IPB Mayang Sari G54103006
Menyetujui : Pembimbing I,
Pembimbing II,
Drs. Prapto Tri Supriyo, M.Kom. NIP 131878952
Drs. Siswandi, M.Si. NIP 13195732
Mengetahui : Dekan Fakultas Matematika dan Ilmu Pengetahuan Alam Institut Pertanian Bogor
Prof. Dr. Ir. Yonny Koesmaryono, M.S. NIP 131473999
Tanggal Lulus :
KATA PENGANTAR Puji dan syukur penulis panjatkan kehadirat Allah SWT atas rahmat serta nikmat sehat jasmani maupun rohani sehingga penulis mampu menyelesaikan karya ilmiah ini. Shalawat serta salam tercurah kepada junjungan kita nabi besar Muhammad SAW yang telah memberikan suri tauladan kepada umatnya hingga akhir jaman. Pada mulanya karya ilmiah ini merupakan tugas mata kuliah Kapita Selekta Matematika Industri di Departemen Matematika. Dari tugas ini penulis mencoba mengembangkan dan menerapkannya dengan mengambil studi kasus di Departemen Matematika, akhirnya penulis berhasil menyusun karya ilmiah ini sebagai salah satu syarat untuk memperoleh gelar sarjana sains. Berbagai permasalahan muncul selama penulisan karya ilmiah ini. Oleh karena itu, dalam kesempatan ini penulis mengucapkan terima kasih kepada : 1. Bpk. Drs. Prapto Tri Supriyo , M.Kom selaku Pembimbing I yang telah meluangkan waktu dan pikirannya membimbing, memberikan dorongan dan pengarahan kepada penulis hingga penulisan karya ilmiah ini selesai, Bpk. Drs. Siswandi, M.Si. selaku Pembimbing II atas bimbingan dan saran yang telah bapak berikan, Bpk. Dr. I Gusti Putu Purnaba, DEA selaku dosen penguji atas saran dan masukan yang telah Bapak berikan. 2. Papah dan Mamah tersayang, atas segala doa serta curahan kasih sayang yang telah kalian berikan hingga sekarang. 3. Tetehku Ayuliana,ST,MMSI, yang sangat membantu penulis dalam berbagai hal dari awal hingga penulisan ini selesai. Aa Awang, Aa Yadi, dan adikku Aal. 4. Dosen-dosen di departemen matematika, terima kasih atas ilmu yang telah Bapak dan Ibu berikan, serta staff departemen matematika : Mas Deny, Mas Yono, Mas Bono, Bu Ade, Bu Susi, Bu Marisi, terima kasih atas bantuan selama di Departemen Matematika. 5. Pratomo Aji, atas semua dukungan moril, doa, dan semangat, M.Hafidzi, terima kasih banyak, dan Retno Pratiwi, terima kasih atas persahabatan kalian selama ini. 6. Elis Lestari, yang selalu ada saat penulis mengalami hal-hal buruk di kampus juga atas bantuan komputer, printer, tempat menginap, kue, dll. 7. Teman-teman Matematika 40 : Elis, Nchie, Uve, Sriti, Marlin, Yuda, Uli, Walidah, Dwi, Sawa, Mufti, Komeng, Demi, Amie, Mika, Gatha, Indah, Ifni, Iwit, Jaja, Mita, Icha, Vina, Meta, Achie, Herni, Nisa, Azis, Prima, Aam, Lili, Manto, Mukafi, Ari, Bedu, Jayu, Rusli, Berri, Rama, Anton, Dimas, Ali, Abay, Fe, Yusuf, Putra. Kalian semua mewarnai kisah bahagia, sedih, susah, senang bersama selama 4 tahun di Departemen Matematika. 8. Kakak-kakak kelasku : K Ari ’39, terima kasih sudah membantu menyusun kata-kata waktu poster, K Irwan n K Avi ’39, terima kasih sudah bantu belajar Lingo 8.0 sampai malam sebelum seminar. 9. Adik-adik kelasku : Diah, Lia Y, Ani, Ayu, Iyank, Dian, Nidia, Mukti, Mahnuri, Aji (matematika 41), Syadid (Ilkom 41) dan Feby (Kimia 41). Terima kasih atas doa dan semangatnya selama ini. 10. Anak-anak di kostan, Andaleber’s, special buat Ade TPG 41, Ukhuwah Crews, yang sudah membantu waktu poster dan tempat menginap yang menyenangkan, Rainbow Crews, terima kasih sudah mau direpotkan menitip motor. 11. Semua pihak yang ikut membantu dan penulis tidak dapat menyebutkan satu persatu. Penulisan karya ilmiah ini tidak mungkin luput dari kekurangan, oleh karena itu kririk dan saran dari semua pihak akan sangat membantu demi kesempurnaan penulisan ini. Harapan penulis adalah semoga penulisan karya ilmiah ini akan memberikan manfaat bagi para pembacanya.
Bogor, Mei 2007 Mayang Sari
RIWAYAT HIDUP Mayang Sari dilahirkan di Bogor pada tanggal 8 Maret 1985. Penulis merupakan anak keempat dari pasangan H. Adang Jaya Saputra dan Hj. Cucu Rohayati yang bertempat tinggal di Kp. Tipar RT 04/08 No. 8 Mekarsari Cimanggis Depok 16952. Pada tahun 1991 penulis mulai bersekolah di SDN Mekarsari VI, dan tahun 1997 penulis melanjutkan sekolah ke SLTPN 103 Jakarta Timur. Pada tahun 2003 penulis lulus dari SMUN 39 Jakarta Timur dan berhasil menjadi mahasiswi Departemen Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Institut Pertanian Bogor melalui jalur USMI (Undangan Seleksi Masuk IPB). Selama mengikuti kegiatan perkuliahan penulis pernah menjadi asisten dosen pada mata kuliah Persamaan Differensial Biasa (2006). Penulis juga aktif dalam keanggotaan himpunan profesi matematika yang dikenal dengan nama GUMATIKA dan menjabat sebagai Kepala Departemen Keilmuan pada periode 2005/2006.
vii
DAFTAR ISI Halaman Daftar Tabel …………………………………………………………………………………… viii Daftar Gambar ………………………………………………………………………………… viii Daftar Lampiran ……………………………………………………………………………… viii I
PENDAHULUAN 1.1 Latar Belakang ……………………………………………………………………… 1.2 Tujuan ………………………………………………………………………………
II
LANDASAN TEORI 2.1 Linear Programming ……………………………………………………………… 2.1.1 Solusi suatu Linear Programming …………………………………………. 2.2 Integer Linear Programming ………………………………………………………. 2.3 Metode Branch and Bound untuk menyelesaikan masalah Integer Programming ……………………………………………………………….
1 1 1 1 2 2
III PEMODELAN……………………………………………………………………………
4
IV STUDI KASUS MASALAH PENJADWALAN DI DEPARTEMEN MATEMATIKA FMIPA IPB ……………………………………………………………
6
V
SIMPULAN DAN SARAN 5.1 Simpulan……………………………………………………………………………
12
5.2 Saran ………………………………………………………………………………..
12
DAFTAR PUSTAKA ………………………………………………………………………..
13
LAMPIRAN ………………………………………………………………………………….
14
viii
DAFTAR TABEL Halaman Arti bobot sks …………………………………………………………………………… 6 Daftar mata kuliah wajib semester genap di Departemen Matematika ………………… 6 Daftar mata kuliah pilihan bidang minat pemodelan semester genap di Departemen Matematika ……………………………………………………………. 7 4 Daftar mata kuliah pilihan bidang minat industri semester genap di Departemen Matematika ……………………………………………………………. 7 5 Daftar mata kuliah pilihan bidang minat murni semester genap di Departemen Matematika ……………………………………………………………. 7 6 Daftar mata kuliah pilihan bidang minat komputasi semester genap di Departemen Matematika ……………………………………………………………. 7 7 Daftar mata kuliah pilihan bidang minat ekonomi semester genap di Departemen Matematika ……………………………………………………………. 7 8 Daftar mata kuliah pilihan bidang minat lingkungan semester genap di Departemen Matematika ……………………………………………………………. 8 9 Daftar mata kuliah pilihan tambahan ………………………………………………….. 8 10 Periode Waktu ………………………………………………………………………… 8 11 Ruangan yang tersedia ………………………………………………………………… 8 12 Jadwal Kuliah dan Praktikum Program Sarjana Matematika Semester Genap ………. 11 1 2 3
DAFTAR GAMBAR
1 2 3 4 5
Daerah Fisibel IP ……………………………………………………………………… Daerah Fisibel untuk Subproblem 2 dan Subproblem 3 ……………………………… Metode Branch and Bound untuk menentukan solusi IP …………………………….. Daerah Fisibel untuk Subproblem 4 dan Subproblem 5 ……………………………… Daerah Fisibel untuk Subproblem 6 dan Subproblem 7 ………………………………
Halaman 3 3 4 16 17
DAFTAR LAMPIRAN
1 2
Contoh penyelesaian suatu LP dengan metode Branch and Bound………………… Program untuk menyelesaikan masalah Penjadwalan Perkuliahan Semester Genap di Departemen Matematika dengan menggunakan Lingo 8.0 ………………
Halaman 15 18
1
I. PENDAHULUAN 1.1 Latar Belakang Di setiap awal semester, beberapa sekolah tinggi dan universitas menghadapi permasalahan yang sama, yakni penjadwalan penggunaan ruang kuliah untuk memenuhi kebutuhan kegiatan perkuliahan. Pada setiap semester, jumlah mahasiswa yang mengikuti suatu mata kuliah pada umumnya tidak selalu sama, sehingga menimbulkan permasalahan yang terkait dengan kapasitas ruang kuliah. Oleh sebab itu, permasalahan ini harus dapat diatasi. Permasalahan penjadwalan ruang kuliah ini dapat dimodelkan sebagai masalah pemrograman linear integer / Integer Linear
Programming (ILP). ILP adalah masalah optimisasi dengan fungsi objektif dan kendala yang linear serta variabel integer. Tulisan ini akan membahas bagaimana memformulasikan masalah penjadwalan mata kuliah dalam ILP dengan mengambil contoh kasus di Departemen Matematika FMIPA IPB. 1.2 Tujuan Tujuan penulisan ini adalah: 1. Menunjukkan peranan ILP dalam menentukan jadwal perkuliahan. 2. Memodelkan masalah penjadwalan mata kuliah di Departemen Matematika ke dalam bentuk ILP.
II. LANDASAN TEORI Untuk membuat model penentuan jadwal perkuliahan, diperlukan beberapa pemahaman teori seperti linear programming (LP), integer linear programming, dan metode branch and bound untuk menyelesaikan masalah integer programming. Berikut ini akan dibahas satu persatu. 2.1 Linear Programming LP merupakan tindakan untuk memperoleh hasil yang optimal dari tujuan yang diinginkan terhadap kendala yang ada. Model LP meliputi pengoptimuman suatu fungsi linear terhadap kendala linear. Pada tulisan ini, suatu LP mempunyai bentuk standar seperti yang didefinisikan sebagai berikut : Definisi 1(Bentuk standar suatu LP) Bentuk standar suatu linear programming adalah : Minimumkan fungsi objektif z = cTx Terhadap Ax = b x≥0 …(1) dengan b ≥ 0 dengan x dan c berupa vektor berukuran n, vektor b berukuran m, sedangkan A berupa matriks berukuran m x n yang disebut juga matriks kendala. [Nash & Sofer, 1996] 2.1.1 Solusi suatu Linear Programming
Untuk menyelesaikan suatu masalah LP, metode simpleks merupakan salah satu metode yang dapat menghasilkan solusi optimum, Metode ini mulai dikembangkan oleh Dantzig tahun 1947. Dalam perkembangannya, metode ini adalah metode yang paling umum digunakan untuk menyelesaikan masalah LP, yaitu berupa metode iteratif untuk menyelesaikan masalah LP dalam bentuk standar. Definisi 2 (Solusi Fisibel) Suatu solusi disebut fisibel jika memenuhi semua kendala pada LP. [Nash & Sofer, 1996] Definisi 3 (Daerah Fisibel/Himpunan Fisibel) Daerah fisibel atau himpunan fisibel adalah himpunan dari semua solusi fisibel. [Nash & Sofer, 1996]
Misalkan matriks A dapat dinyatakan sebagai A = ( B N ), dengan B adalah matriks yang elemennya berupa koefisien variabel basis dan N merupakan matriks yang elemennya berupa koefisien variabel nonbasis pada matriks kendala. Matriks B disebut matriks basis untuk LP (1). Berikut definisi matriks Basis : Definisi 4(Matriks Basis) Matriks B disebut matriks basis untuk LP (1) jika B adalah matriks tak singular, yaitu matriks yang determinannya tidak sama dengan nol. [Garfinkel & Nemhauser, 1972]
