A.PLlKASI TABU SEARCH DALAM PENJADW ALAN KULIAH (Studi Kasus di Jurusan Teknik Industri Universitas Katolik Widya Mandala Surabaya)
TUGASAKHIR
() cr J <j; 10-4 .-------
Disusun Oleh :
I ~'
t;
Ti.r:~,j~-=- t .--~.:...: _ie.1I
MARGARETHA YUSTINA
5303098030
JURUSAN TEKNIK INDUSTRI FAKULTAS TEKNIK UNIVERSITAS KATOLIK WIDYA MANDALA SURABAYA 2003
o~. \.'l.. J!~~
LEMBAR PENGESAHAN Laporan Tugas Akhir dengan judul "Aplikasi Tabu Search dalam Penjadwalan Kuliah (Studi Kasus di Jurusan Teknik Industri Universitas Katolik Widya Mandala Surabaya)" telah diperiksa dan disetujui sebagai bukti bahwa mahasiswa: Nama: Margaretha Yustina Nrp
: 5303098030
telah menyelesaikan sebagian persyaratan kurikulum untuk memperoleh gelar Sarjana Teknik. Surabaya, 20 Februari 2003
IgnJoko Mulyono, STP,MT NIK : 531.98.0325 Dewan Pengujj
~-Ll--r-~ Martinus Edy S,ST,MT
Drs. Peter R.
NIK. 531.98.0305
NIK. 511.88.0136
NIK.5'31.97.0298
Jurus~'Feknik Industri
Dekan Falml", Tclmi
r\.·~·.· ....---Ke.'.tu.,.a
~-~.j ,',----,,-~--~
an ~etno S.D, ST, MT
gka,Mkomp
-----
\~~y , \
If. Nani Indraswati
NIK. 521.86.0121
NIK. 531.97.0298
ii
ABSTHAKSJ
Sclama ini pcnjadwalan mata klliiah dilakllkan secara IlH11lurd. KcslIlitan yang terjadi dalam pCI~adwalan sccara manual disebnbknn karcna adanya konllik yang terjadi. Konnik tcrsebut disebabkan banyak mata kuliah yang hams dibuka, I1lcngatur mata kuliah agar tidak diajar doscn scem'a bersamm1l1, (\;em kcbuluhan ruang yang tcrbatas. Olch karcna itu dibutuhkan alat bantu yang dapat I11cmpemlUdah dalnl11 menyusun jadwal kuliah. Algoritma 'l'a"ll ,<.,'earch (TS) dipakai sebagai alat bantu karena algoritll1a ini lebih pmktis daripada I11cnjadwalkan sccara manual. Algorilma ini dipakai karcna mcmiliki dacrflh pencarian yang Iuas dan mcnccgah adanya pcngulangan //love sebelu111nya. Algoritma 1'3 ini tidak akan mcnghilangkan pcran dalam pcn),usunan jadwal, tclapi mcmbantu dalam pengambilan kcplltllsan. Karcna mcnyangkut kcpentingan mahasiswa daJam pcngillllbiJan kuliah sccara tcpat maka jadwal kuJiah tersebut barus dibuat akurat. Ada bebcrapa kritcria yang hams dipcnuhi agar jadwal kllliah terscbllt optimal dan akurat yuilu anlam lain: waklu kcsediaan mengajar dosen yang tidak bersmnaan satu sama lain, status dosell, jcnis mata kuliah. kapasitas kelas, dan konnik dosen yang tcrjadi. Manraat dari pcmbuatan jadwal mata kuliah dcngan algoritma T3 dapat mcningkatkan prodllktivitas kc~ia. Dalam pcnjadwalan dengan algoritma TS ini dilakllkall kombinasi schingga I11cnuekati glolml dcngan pcncwpan 1'01111 .')'earc17 For 'f'illlcfahlil1}} ,<"'/lhl'mh!clII (algoril1l1a TATI). Proscdllr ini ditcrapkan untllk l11cngurangi jumlah konflik doscn dcngan mcmballgkitkan sebuah timetablc awal (initial timetable) dengan mengalokasikan dosen ke bagian pelajaran kCl11udian menggunakan suatu proscdur iteratir yang mcngatur timetable tersebllt secara berurutan sampai tidak ada lagi perbaikan dari fungsi tujuan yang diperolch. [Gunawan. 1994J Ilasil pcnelitian menunjukkan bahwa algoritma 7ct!JII ,<,'earch dcngml balltuan program komputer dapat menghilangkall konflik doscn dan penjadwalall terscbut 1l1cmcrlukan waktu yang relatif singkal dibamlingkan dcngan mcnjac\walkan sccara manual schingga penjadwalan dcngan algoritma Tahu Search dapat sangat mcmbantll dalam I11cl11bllatjadwall1lata klliiah.
III
KATA PENGANTAR
Puji syukur kami hadiratkan pad a Tuhan Yang MaIm Esa, sehingga penulis dapat menyelesaikan penulisan Tugas Akhir denganjudul : "Penjadwalan Mata Kuliah Dengan Menggunakan Algoritma Tabu Search Di JUnlsan Teknik Industri Universitas Widya Mandala Surabaya ". Tugas Akhir ini merupakan salah satu syara! untuk memperoleh gelar Sarjana Teknik Industri. Tersclcsainya Tugas Akhir ini tidak Icpas dari bantuan dari berbagai pihak yang telah meluangkan waktunya untuk memberikan masukkan dan dorongan dalam pclaksanaan dan pcnyusunan laporan Tugas Akhir inL Schingga pada kcscmpatall ini akan disampaikan rasa tcrima kasih kcpada : I.
Ibu Ir. Nani Indmswati, "e1aku Dekan
Fakult!1.~
Tcknik yang telah
mcmberikan ijin ulltuk mclaksanakan penclitian Tugas Akhir. 2.
Ibu Dian Relno Sari Dcwi, ST, MT seJaku Ketlla Jurusan Teknik Industri yang telah memberikan kesempatan untuk melakukan peneiitian Tugas Akhir dan memberikan bimbingan, infonnasi, maupun data yang menunjang penelitian Tugas Akhir.
3.
Bapak Martinus Edy S., ST, MT seJaku Sekretaris Jurusan Teknik lndustri yang telah memberi ijin dan memberikun billlbingun, infoTlllasi, maupun data yang menunjang penelitian Tugas Akhie
4.
Bapak Joko Mulyono, STP, MT selaku Dosen Pembimbing yang telah Illcngarahkun dan Illcmbimbing dalam Illcnyc\csaikan Tugas Akhir ini.
5.
Pihak Tata Usaha juntsan Teknik Tndustri maupun MKU yang telah mcmbantu mcmbcrikan data - data yang dipcrlukan dalam menunjang pcnelitian Tugas Akhir.
6.
Bapak Gcde yang telah melllbantu memheri pcngarahan dan bimhingan dalam Il1cnyc1csaikan Tugas Akhir.
7.
Scmua doscn jurusan Tcknik Industri yang tclah mcmbantu mcmbcrikan informasi dan bantuan dalam menyelesaikan Tugas Akhie
IV
8.
Keluarga dan saudara yang telah memberikan dukungan baik secara moral maupun material dalam menyelesaikan Tugas Akhir.
9.
HetTY Agustinus PM yang telah memberi dukungan, sel11angat, dan membantu dalam l11enyclesaikan Tugas Akhir.
lD.
Teman - teman yang memberi mendukung, semangat, dan membantu dalam mcnyelesaikan Tugas Akhir.
II.
Semua pihak yang telah membantu penyelesaian Tugas Akhir. Dcngan l11cnyadari scgala keterbatasan pada pClllllis, maka pClllllis s
l11engharapkan adanya kritikan-kritikan dan saran-saran yang bcrsifall11Cl11bangun dari pcmbaca, yang dapat mcmbantu mcnyempurnakan Tugas Akhir ini sehingga Icbih baik dari sebelumnya. Scmoga Tugas Akhir dapat bcrgllna dan bcnnanfaat bagi jurusan Tcknik Industri Universitas Katolik Widya Mandala Surabaya dan pembaca.
Surabaya, 20 Fcbruari 2003
Pcnulis
v
DAFTARISI
Cover. .............. '" .................................... '" .. , ........................... i Letnbar Pengesahan ................................................... '" ................. ii Abstraksi. ............................. '" .................................... '" ....... , ... iii Kata Pengantar. ...... " .................................................................... iv Daftar lsi ................... " ......... '" ... .. . .. . ... ... ... ... ... .. . .. . ... . . .. .. ......... vi Daftar Gatnbar. ......................................... '" ............................... viii Daftar Tabe!.. ............................................................................. ix Daftar Lampiran ..................... '" .................................... '" ............ x BAB I
BAB II
PENDAHULUAN 1.1
Latar belakang ...... '" .................................... '" ........... 1
1.2
Rumusan Masalah ........................................ '" ............ 2
1.3
Ttuuan .................................................................... 2
1.4
Batasan Masalah ......................................................... 2
1.5
Asumsi ................................. '" ................................ 2
1. 6
Sistematika Penulisan .................................................. 2
SURVEI LITERATUR 2.1
Penjadwalan ....................... , ..................................... 4
2.2
Pengertian Tabu Search Secara Umum ............................. 5
2.3
Algoritma
Tabu
Search
Kombinasi
Untuk
Masalah
Pcngalokasian ............................................. '" ........... 7 2.4
Tabu Search For Timetabling Subproblem (TATI) ................. 8
2.5
Konsep Delphi .......................................................... 9
BAB III METODOLOGI PENELITIAN DAN PENGEMBANGAN MODEL 3.1
Tahapan Penclitian ................. , .................... , ............... 11
3.2
Pengembangan Model... .................. , .............. '" ........... 14
BAB IV PENGUMPULAN DAN PENGOLAHAN DATA 4.1
Pcngumpulan Data ................................................... ". 18
4.2
Pcngolahan Data dan Pcmbuatan Program ...................... " .. 18
VI
4.2.1 Pembuatan Program ........ , ............ '" ...... '" ........... 18 4.2.2 Pembuatan Program Komputer. .......................... '" .21 4.2.3
Langkah Pengolahan Data ... '" ............................. 21
4.2.4 Pcngopcrasian Program Kompulcr Dclrhi 5 ............. 23 BAB V
ANALlSA DAN EVALUASI 5.1
Output Yang Dihasilkan Dalam Penelitian Tugas Akhir. ......... 29
5.2
Output Yang Dihasilkan Dalam Jadwal Terdahulu ................ 31
BAB VI KESIMPULAN DAN SARAN
6.1
Kesimpulan ........... , .................... , ........ , .................... 33
6.2
Saran ......... '" ...... '" .................................... '" ...... '" 33
DAFTAR PUST AKA ............... '" .................... , ...... '" ........... , ... '" . 34 LAMPIRAN .............................................................. ' .............. 36
VII
DAFTAR GAMBAR
Gambar 3.1 Flow Chart Tahapan Penclitian .............................. ' ........... 11 Gambar 3.2 Flow Chart Pengembangan Modal Tabu Search ....................... I 5 Gambar 4.1 Flow Chart Program Utama Tabu Search ............... '" '" ......... 19
viii
DAFTAR TABEL
Tabel 5.1 Output Jadwal Kuliah Hasil Penelitian .................................... 30 Tabel 5.2 Output ladwal Kuliah Hasil Sebelumnya ................................. 32
IX
DAFT AR LAMPIRAN
LAMPIRAN A. DATA MAT A KULIAH LAMPlRAN B. DATA DOSEN LAMPI RAN C. DATA RUANG LAMPI RAN D. LISTING PROGRAM
x
