PENJADWALAN MATA KULIAH MENGGUNAKAN INTEGER NONLINEAR PROGRAMMING Studi Kasus di Bina Sarana Informatika Bogor
ERLIYANA
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2011
ABSTRACT ERLIYANA. Courses Scheduling Using Integer Nonlinear Programming. A Case Study of Bina Sarana Informatika Bogor. Supervised by PRAPTO TRI SUPRIYO and FARIDA HANUM. This research aims to formulate courses scheduling based on lecturers’ and students’ preferences and other constraints. The model used is Integer Nonlinear Programming (INLP), with lecturers’ and students’ preferences are represented by course weights. The smaller weights of subjects indicate that their preferences are more prefered. This model is implemented to schedule courses of 5th semester classes at the Academy of Bina Sarana Informatika Bogor. The solution of this model is carried out using Lingo 8.0. The result shows that the schedule fulfill 98,57% preferences of regular students, 100% of extension students, and 100% of lecturers.
ABSTRAK ERLIYANA. Penjadwalan Mata Kuliah Menggunakan Integer Nonlinear Programming. Studi Kasus di Bina Sarana Informatika Bogor. Dibimbing Oleh PRAPTO TRI SUPRIYO dan FARIDA HANUM. Tujuan penelitian ini adalah membuat model penjadwalan mata kuliah berdasarkan preferensi dosen dan mahasiswa dan memenuhi berbagai kendala lain. Model yang digunakan adalah Integer Nonlinear Programming (INLP), sedangkan preferensi dosen dan mahasiswa direpresentasikan dengan suatu bobot. Bobot mata kuliah yang lebih kecil menandakan bahwa preferensinya lebih diutamakan. Model penjadwalan yang telah disusun diimplementasikan untuk menyusun jadwal mata kuliah semester 5 di Akademi Bina Sarana Informatika. Solusi yang diperoleh dari penyelesaian model dengan menggunakan Lingo 8.0 untuk studi kasus yang dilakukan adalah jadwal mata kuliah yang memenuhi 98,57% keinginan mahasiswa reguler, 100% keinginan mahasiswa ekstensi, dan 100% keinginan dosen.
PENJADWALAN MATA KULIAH MENGGUNAKAN INTEGER NONLINEAR PROGRAMMING Studi Kasus di Bina Sarana Informatika Bogor
ERLIYANA
Skripsi sebagai salah satu syarat untuk memperoleh gelar Sarjana Sains pada Fakultas Matematika dan Ilmu Pengetahuan Alam Institut Pertanian Bogor
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2011
: Penjadwalan Mata kuliah Menggunakan Integer Nonlinear Programming: Studi Kasus di Bina Sarana Informatika Bogor Nama : Erliyana NIM : G54050056
Judul
Menyetujui,
Pembimbing I
Pembimbing II
Drs. Prapto Tri Supriyo, M.Kom. NIP. 19630715 199002 1 002
Dra. Farida Hanum, M.Si. NIP. 19651019 199103 2 002
Mengetahui: Ketua Departemen
Dr. Berlian Setiawaty, M.S. NIP. 19650505 198903 2 004
Tanggal Lulus :
KATA PENGANTAR Puji syukur penulis panjatkan kepada Allah SWT atas berkat, rahmat dan kasih sayang-Nya sehingga penulis mampu menyelesaikan karya ilmiah ini. Berbagai kendala dialami oleh penulis sehingga banyak sekali orang yang membantu dan berkontribusi dalam pembuatan karya ilmiah ini. Oleh karena itu, dalam kesempatan ini penulis mengucapkan terima kasih kepada: 1. Sang pencipta, Tuhan semesta alam Allah SWT, atas maha karya-Nya yaitu bumi yang sempurna ini; 2. nabi besar Muhammad SAW sebagai penutup para nabi; 3. keluarga tercinta: bapak dan ibu, ibu sebagai pemberi motivasi dan bapak sebagai sumber inspirasi, untuk Istiajid yang selalu memberikan semangat dan doa. 4. Drs. Prapto Tri Supriyo, M.Kom. selaku dosen pembimbing I yang telah meluangkan waktu dan pikiran dalam membimbing, memberi motivasi, semangat dan doa; 5. Dra. Farida Hanum, M.Si. selaku dosen pembimbing II yang telah memberikan ilmu, kritik dan saran, motivasi serta doanya; 6. Dr. Ir. Amril Aman, M.Sc. selaku dosen penguji yang telah memberikan ilmu, saran dan doanya; 7. semua dosen Departemen Matematika, terima kasih atas semua ilmu yang telah diberikan; 8. staf Departemen Matematika: Bapak Yono, Bapak Hery, Bapak Deni, Ibu Ade, Bapak Epul, Bapak Bono dan Ibu Susi atas semangat dan doanya, 9. Raka yang selalu setia mendampingi, memberi dukungan, dan doa, 10. sahabat yang selalu memberi semangat: Niken, Idha, Oby, Eyyi, Jane, 11. teman-teman yang mengajarkan Lingo: Apri, Dj, Bima, 12. teman yang selalu memberi motivasi dan bantuan: Dio, Erpan, 13. Andri yang membantu dalam pembuatan abstrak, 14. semua teman Matematika 42 yang selalu menjadi contoh yang baik, 15. semua teman Matematika 43 yang selalu menjadi bagian dari keluarga, 16. semua teman Matematika 44 yang selalu mendukung agar terus berkembang, 17. teman satu pembimbing: Yudi, Slamet, Zil, 18. Gumatika yang telah mengasah pribadi ini menjadi pribadi yang tangguh, 19. semua pihak yang telah membantu dalam penyusunan karya ilmiah ini. Penulis menyadari bahwa dalam tulisan ini masih terdapat kekurangan dan jauh dari kesempurnaan, oleh karena itu penulis mengharapkan kritik dan saran yang membangun dari pembaca. Semoga tulisan ini dapat bermanfaat.
Bogor, Juni 2011
Erliyana
RIWAYAT HIDUP Penulis dilahirkan di Bogor pada 10 Maret 1987 sebagai anak pertama dari dua bersaudara, anak dari pasangan Mochammad Yahya Permana dan Usmanah. Pada tahun 1999 penulis lulus dari SD Negeri Gunung Batu 01 Bogor kemudian tahun 2002 lulus dari SLTP Negeri 06 Bogor. Tahun 2005 penulis lulus dari SMA Negeri 6 Bogor dan pada tahun yang sama penulis lulus seleksi masuk IPB melalui jalur USMI (Undangan Seleksi Masuk IPB). Pada tahun 2007, penulis memilih Mayor Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam. Selama mengikuti perkuliahan, penulis aktif dalam mengajar Matematika bimbingan belajar privat maupun kelompok mahasiswa dan siswa SMA. Penulis aktif dalam organisasi kemahasiswaan di kampus, seperti organisasi himpunan profesi Departemen Matematika yang dikenal dengan GUMATIKA (Gugus Mahasiswa Matematika) sebagai anggota Departemen KEWIRAUSAHAAN tahun 2006/2007 dan kepala divisi Departemen KEWIRAUSAHAAN tahun 2007/2008. Selain itu, penulis juga terlibat dalam beberapa kegiatan, antara lain koordinator Humas Try-Out Pengantar Matematika mahasiswa IPB 2007, koordinator dekorasi Masa Pengenalan Departemen Matematika 2008, koordinator Dekorasi dan Dokumentasi Matematika Ria dalam acara Pesta Sains se-Indonesia 2009. Pada tahun 2009 penulis mencoba untuk mengajar di SMP/SMK Nusantara Mandiri dan beberapa lembaga bimbingan belajar.
DAFTAR ISI Halaman DAFTAR TABEL
viii
DAFTAR GAMBAR
viii
DAFTAR LAMPIRAN
viii
I
PENDAHULUAN 1.1 Latar Belakang 1.2 Tujuan
1 1
II LANDASAN TEORI 2.1 Pemrograman Linear 2.2 Integer Programming 2.3 Nonlinear Programming 2.4 Integer Nonlinear Programming 2.5 Metode Branch and Bound
1 3 3 4 5
III DESKRIPSI DAN FORMULASI MASALAH 3.1 Deskripsi Masalah 3.2 Formulasi Masalah 3.3 Model Matematika
9 9 10
IV PENYELESAIAN MASALAH PENJADWALAN MATA KULIAH
11
V SIMPULAN DAN SARAN 5.1 Simpulan 5.2 Saran
16 16
DAFTAR PUSTAKA
16
LAMPIRAN
17
vii
DAFTAR TABEL
1 2 3 4 5
Subproblem-subproblem masalah INLP (10) Pencabangan Subproblem P(X1) Pencabangan Subproblem P ( X 13 ) Pencabangan Subproblem P(X2) Pencabangan Subproblem P( X 22 )
Halaman 7 7 7 8 8
6 Pencabangan Subproblem P( X 23 )
8
Pencabangan Subproblem P( X 24 ) Daftar mata kuliah semester lima di AMIK Ruangan yang tersedia Periode hari Periode waktu Daftar kelompok Daftar dosen Jadwal kegiatan belajar mengajar untuk program regular Akademi Manajemen Informatika dan Komunikasi BSI Bogor 15 Jadwal kegiatan belajar mengajar untuk program ekstensi Akademi Manajemen Informatika dan Komunikasi BSI Bogor
7 8 9 10 11 12 13 14
8 11 12 12 12 12 12 15 15
DAFTAR GAMBAR Halaman 1 Daerah fisibel (daerah yang diarsir) untuk NPL-relaksasi dari INLP (10). 6 2 Daerah fisibel subproblem P(X1) dan subproblem P(X2). 6 3 Bobot suatu mata kuliah yang diharapkan diajarkan di awal periode waktu untuk mahasiswa program regular. 10 4 Bobot suatu mata kuliah yang diharapkan diajarkan di akhir periode waktu untuk mahasiswa program ekstensi. 10 5 Bobot mata kuliah Pemrograman Visual FOXPRO (K) yang diharapkan diajarkan di awal periode waktu untuk mahasiswa program regular. 13 6 Bobot mata kuliah Pemrograman Visual FOXPRO (P) yang diharapkan diajarkan di akhir 13 periode waktu untuk mahasiswa program ekstensi.
DAFTAR LAMPIRAN Halaman 1 Syntax Program LINGO 8.0 dalam mencari nilai awal solusi fisibel Contoh 2 18 2 Syntax Program LINGO 8.0 untuk Menyelesaikan Masalah Pemrograman Taklinear dengan Metode Branch-and-Bound Beserta Hasil yang Diperoleh 18 3 Program untuk menyelesaikan masalah penjadwalan kegiatan belajar mengajar di Akademi Manajemen Informatika dan Komunikasi BSI Bogor. 23
viii
