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]
2
1 0 0 B= 0 1 0 0 0 1 Dengan menggunakan matriks basis tersebut, diperoleh T xN = ( 0 0) , …(5) T −1 xB = B b = ( 4 11 5 ) Solusi (5) merupakan solusi basis, karena solusi tersebut memenuhi kendala pada LP (4) dan kolom-kolom pada matriks kendala yang berpadanan dengan komponen taknol dari (5) yaitu B adalah bebas linear (kolom yang satu bukan merupakan kelipatan dari kolom yang lain). Solusi (5) juga merupakan solusi fisibel basis, karena nilai-nilai variabelnya lebih dari atau sama dengan nol.
Jika vektor x dapat dinyatakan sebagai vektor x =
xB
dengan xB adalah vektor
xN
variabel basis dan xN adalah vektor variabel nonbasis, maka Ax=b dapat dinyatakan sebagai Ax = ( B
N)
xB xN
…(2)
= Bx B + Nx N = b Karena B adalah matriks tak singular, maka B memiliki invers, sehingga dari (2) xB dapat dinyatakan sebagai −1 −1 xb = B b − B Nx N …(3) Definisi 5 (Solusi Basis) Vektor x disebut solusi basis jika : i. x memenuhi kendala persamaan (Ax=b) dari LP. ii. Kolom-kolom dari matriks koefisien yang berpadanan dengan komponen tak nol dari x adalah bebas linear. [Nash & Sofer, 1996]
2.2 Integer Linear Programming Model ILP atau disebut juga Integer Programming (IP), adalah suatu model LP yang menggunakan bilangan bulat (integer). Jika semua variabel harus berupa integer, maka masalah tersebut disebut pure integer programming. Jika hanya sebagian yang harus integer, maka disebut mixed integer programming. IP dengan semua variabelnya harus bernilai 0 atau 1 disebut 0-1 IP. [Garfinkel & Nemhauser, 1972]
Definisi 6 (Solusi Fisibel Basis) Vektor x disebut solusi fisibel basis jika x merupakan solusi basis dan x ≥ 0 . [Nash & Sofer, 1996]
Definisi 5(Linear Programming Relaksasi) LP-Relaksasi dari suatu IP merupakan LP yang diperoleh dari IP tersebut dengan menghilangkan kendala integer atau kendala 01 pada variabelnya. [Winston, 1995]
Ilustrasi solusi basis dan solusi fisibel basis dapat dilihat dalam contoh berikut : Contoh 1 Misalkan diberikan LP berikut: Minimumkan z = −2 x1 − 3 x2
terhadap : −2 x1 + x2 + x3 = 4 − x1 + 2 x2 + x4 = 11 x1 + x5 = 5 x1 , x2 , x3 , x4 , x5 ≥ 0
Dari LP tersebut didapatkan : −2 1 1 0 0
A = −1 2 0 1 0
…(4)
4
, b = 11
1 0 0 0 1 5 Misalkan dipilih T xB = x3 x4 x5 dan x N = x1 maka matriks basisnya adalah
(
)
(
x2
T
)
2.3 Metode Branch and Bound untuk menyelesaikan masalah Integer Programming Dalam penulisan karya ilmiah ini, untuk memperoleh solusi optimal dari masalah IP digunakan software Lingo 8.0 yaitu sebuah program yang didesain untuk menentukan solusi model linear, nonlinear, dan optimisasi integer menjadi lebih cepat, mudah, dan lebih efisien. Software Lingo 8.0 ini menggunakan metode branch and bound untuk menyelesaikan masalah ILP. Prinsip dasar metode branch and bound adalah memecah daerah fisibel dari masalah LP-relaksasi dengan membuat subproblemsubproblem.
3
Branch Membuat partisi daerah solusi ke dalam subproblem. Tujuannya untuk menghapus daerah solusi yang tidak fisibel. Hal ini dicapai dengan menentukan kendala yang penting untuk menghasilkan solusi IP, secara tidak langsung titik integer yang tidak fisibel terhapus. Dengan kata lain, hasil pengumpulan dari subproblem-subproblem yang lengkap menunjukkan setiap titik integer yang fisibel dari masalah asli. Karena sifat alami partisi itu, maka proses tersebut dinamakan Branching. Bound Misalkan masalahnya diasumsikan merupakan tipe maksimisasi, nilai objektif yang optimal untuk setiap subproblem dibuat dengan membatasi pencabangan dengan batas atas dari nilai objektif yang dihubungkan dengan sembarang nilai integer yang fisibel. Hal ini sangat penting untuk mengatur dan menempatkan solusi optimum. Operasi ini yang menjadi alasan dinamakan Bounding. [Taha, 1975] Aspek kunci dari metode branch and bound adalah sebagai berikut: Langkah 1 : Periksa apakah IP memenuhi kondisi berikut : 1) Subproblem tidak fisibel. 2) Subproblem menghasilkan solusi optimal dengan semua variabel bernilai integer. 3) Nilai optimal untuk subproblem lebih kecil dari (dalam masalah memaksimumkan) batas bawah (lower bound/LB). Jika ketiga kondisi tersebut terpenuhi maka cabang subproblem tidak diperlukan. Langkah 2 : Sebuah subproblem mungkin dapat dihapuskan dari pertimbangan dengan kondisi sebagai berikut : 1) Subproblem tidak fisibel. 2) Batas bawah (yang menunjukkan nilai optimal dari kandidat terbaik) setidaknya lebih besar dari nilai optimal subproblem. [Winston, 1995] Contoh 2 Misalkan diberikan IP berikut: Maksimumkan z = 2 x1 + 3 x2 Terhadap : x1 + 2 x2 ≤ 10 3 x1 + 4 x2 ≤ 25 x1 , x2 ≥ 0 dan integer
Daerah fisibel untuk masalah IP di atas diberikan pada gambar berikut : x2
6
Solusi Optimal Subproblem 1
5
x 1= 5 x2= 2,5
4 3 2 1
-1
2
4
6
8
10
x1
Gambar 1. Daerah Fisibel IP Metode branch and bound dimulai dengan menentukan solusi LP-relaksasi (subproblem 1). Solusi LP-relaksasi untuk masalah di atas adalah x1 = 5, x2 = 2,5, dan z = 17,5. Solusi tersebut tidak memenuhi kendala integer. Oleh karena itu, harus dibuat subproblem yang baru dengan memilih variabel yang tidak memenuhi kendala integer. Dengan memilih x2 = 2,5 secara sembarang, diketahui bahwa daerah (2<x2<3) dari daerah fisibel subproblem 1 tidak akan memuat solusi IP yang fisibel karena tidak memenuhi kendala integer. Subproblem yang baru adalah sebagai berikut : Subproblem 2 : Subproblem 1 + kendala ( x2 ≥ 3) Subproblem 3 : Subproblem 1 + kendala ( x2 ≤ 2 ) Daerah fisibel untuk subproblem 2 dan subproblem 3 diberikan pada gambar berikut : x2
6 5 4 3 2 1 2
4
6
8
10
-1
Gambar 2. Daerah Fisibel untuk Subproblem 2 dan Subproblem 3 Subproblem 2 dan subproblem 3 tidak dapat diselesaikan secara bersamaan, sehingga harus diselesaikan dengan dua masalah linear programming yang berbeda. Pada subproblem 2 diperoleh solusi x1 = 4, x2 = 3, dan z = 17. Karena semua variabel bernilai integer
x1
4
(solusinya memenuhi kendala integer), maka tidak perlu membuat subproblem baru. Pada subproblem 3 diperoleh solusi x1 = 5,667, x2 = 2, dan z = 13,3333. Karena variabelnya tidak memenuhi kendala integer, maka harus dibuat subproblem baru. Subproblem untuk masalah IP di atas diberikan pada gambar 3.
Pada Gambar 3, subproblem 2 dan subproblem 7 merupakan kandidat terbaik karena semua variabelnya bernilai integer. Subproblem 2 dan subproblem 7 merupakan solusi optimal untuk masalah IP di atas karena mempunyai nilai z sama besar. Solusi lengkapnya dapat dilihat pada Lampiran 1.
Subproblem 1 x1 = 5, x2 = 2,5 dan z = 17,5 x2 ≤ 2
x2 ≥ 3 Subproblem 2*
Subproblem 3
x1 = 4, x2 = 3 dan z = 17
x1 =5,667, x2 = 2 dan z = 13,333 x1 ≤ 5
x1 ≥ 6
Subproblem 4
Subproblem 5
Solusi tak fisibel
x1 = 6, x2 = 1,75 dan z = 17,25 x2 ≥ 2
Subproblem 6 Solusi tak fisibel
x2 ≤ 1 Subproblem 7* x1 = 7, x2 = 1 dan z = 17
Gambar 3. Metode branch and bound untuk menentukan solusi IP
III PEMODELAN
Langkah awal membangun model penjadwalan mata kuliah adalah mendeskripsikan masalah tersebut secara jelas dan lengkap. Selanjutnya masalah tersebut diformulasikan dalam bentuk ILP yang siap diselesaikan dengan metode yang sesuai.. Pemodelan masalah penjadwalan dibuat berdasarkan ketersediaan sejumlah ruangan yang dapat digunakan untuk kegiatan perkuliahan, waktu yang diatur setiap harinya dalam periode lima hari (senin s.d.
jum’at), serta sejumlah mata kuliah yang akan dijadwalkan. Jadwal tersebut dibuat sedemikian rupa sehingga memenuhi kendala utama dan kendala tambahan. Kendala utama dalam penjadwalan, yaitu : 1. Semua mata kuliah terjadwalkan 2. Tidak ada overlapping mata kuliah wajib di semester yang sama 3. Tidak ada overlapping mata kuliah pilihan untuk bidang minat yang sama.
5
sedangkan kendala tambahan, yaitu : 1. Mata kuliah wajib tidak boleh dilaksanakan pada waktu sore hari. 2. Mata kuliah beresponsi, jadwal kuliah dan jadwal responsi harus diselenggarakan pada hari yang berbeda. 3. Setiap mata kuliah diselenggarakan tepat dalam satu ruangan. 4. Untuk mata kuliah yang terdiri dari kuliah dan responsi, jadwal kuliah
xi , j ,k =
{
1 ; 0 ;
dilaksanakan lebih dulu dari jadwal responsi. 5. Setiap mata kuliah diselenggarakan pada periode waktu yang sesuai. Misalkan mata kuliah dengan waktu tatap muka 3 jam tidak boleh diselenggarakan pada waktu tatap muka 2 jam. Untuk memformulasikan masalah tersebut ke dalam ILP tentunya diperlukan beberapa asumsi yang mendukung. Selain itu diperlukan pula pendefinisian suatu variabel keputusan:
jika mata kuliah j diselenggarakan pada waktu i dalam ruangan k 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
dengan kendala-kendala sebagai berikut: 1. Mata kuliah wajib dalam semester yang sama tidak boleh dijadwalkan pada periode waktu yang sama. j k
xi , j ,k ≤ 1 ; ∀i
j = Mata kuliah wajib di semester yang sama 2. Mata kuliah beresponsi, jadwal kuliah dan jadwal responsi harus diselenggarakan dalam hari yang berbeda. i k ˆj
j k
3. Mata kuliah wajib dan mata kuliah pilihan dalam semester yang sama tidak boleh diselenggarakan pada periode waktu yang sama. xi , j ,k ≤ 1 ; ∀i
ˆj = Mata kuliah wajib dan mata kuliah pilihan pada semester yang sama.
xi , j ,k ≤ 1 ; ∀i
j = Mata kuliah pilihan dalam bidang minat yang sama. kuliah tertentu tidak dapat 5. Mata diselenggarakan pada periode waktu tertentu. Misal : Mata kuliah wajib tidak boleh diselenggarakan pada waktu sore hari. i k ˆj
x
i , ˆj ,k
=0
i = Periode waktu sore hari ˆj = Mata kuliah wajib 6. Setiap mata kuliah diselenggarakan tepat dalam satu ruangan pada suatu periode waktu.
x ˆ ≤1 i , j ,k
ˆj = Mata kuliah beresponsi
ˆj k
4. Mata kuliah dalam bidang minat yang sama tidak boleh diselenggarakan pada periode waktu yang sama.
i k
xi , j ,k = 1 ; ∀j
7. Paling banyak satu mata kuliah diselenggarakan dalam suatu ruangan dan suatu periode waktu. j
xi , j ,k ≤ 1 ; ∀i, k
8. Mata kuliah dengan waktu tatap muka 3 jam tidak boleh diselenggarakan pada waktu tatap muka 2 jam.
6
i k ˆj
9. Semua variabel keputusan adalah integer nol atau satu.
x ˆ =0 i , j ,k
i = Waktu tatap muka 2 jam. ˆj = Mata kuliah dengan waktu tatap muka
xi , j ,k ∈ {0,1} ; ∀i , j , k
3 jam.
IV. STUDI KASUS MASALAH PENJADWALAN DI DEPARTEMEN MATEMATIKA FMIPA IPB Masalah yang akan dicontohkan di sini adalah masalah penjadwalan perkuliahan semester genap di Departemen Matematika. Hal yang perlu diperhatikan adalah ruangan yang sangat terbatas dikarenakan departemen matematika baru saja dipindahkan ke kampus IPB Dramaga, sehingga ruangan yang tersedia adalah ruangan milik Fakultas Pertanian. Asumsi yang digunakan dalam memodelkan penentuan jadwal mata kuliah semester genap ini adalah: 1. Mata kuliah yang diselenggarakan terdiri dari mata kuliah wajib, yaitu mata kuliah yang diperlukan untuk pembentukan kompetensi utama seorang lulusan perguruan tinggi yang wajib diambil oleh mahasiswa dan mata kuliah pilihan, yaitu mata kuliah yang dapat diambil oleh mahasiswa untuk melengkapi pembentukan keahlian program studinya serta dasar bagi pengembangan lebih lanjut. 2. Mata kuliah wajib semester 4 boleh diselenggarakan bersamaan dengan mata kuliah wajib semester 6.
genap memiliki bobot sks yang berbeda-beda. Bobot sks tersebut yaitu : 4 (4-0), 4 (3-3), 3 (30), 3 (2-3), 2 (2-0), dan 2 (1-1). Arti penulisan bobot sks adalah sebagai berikut: Tabel 1 Arti bobot sks Dijit Diisi dengan: ke: 1 Total beban kredit 2 Tanda kurung buka “(“ 3 Jam tatap muka kuliah dari mata kuliah yang bersangkutan 4 Tanda “-“ 5 Jam tatap muka praktikum 6 Tanda kurung tutup “)”
Di Departemen Matematika, telah ditentukan bahwa satu jam tatap muka di kelas dilakukan selama 50 menit. Untuk mata kuliah yang terdiri dari dua pertemuan yaitu kuliah dan responsi atau praktikum, sebaiknya jadwal kuliah mendahului jadwal responsi atau praktikum. Data yang diperlukan untuk memodelkan penjadwalan semester genap untuk mahasiswa passing out diberikan sebagai berikut :
Setiap mata kuliah yang diselenggarakan Departemen Matematika pada semester
Tabel 2. Daftar mata kuliah wajib semester genap di Departemen Matematika Indeks 1 2 3 4 5 6 7 8 9
Kode MAT 212 MAT 212 MAT 232 MAT 232 MAT 242 MAT 262 MAT 352 MAT 352 MAT 392
Mata Kuliah Kalkulus III Kalkulus III Persamaan Differensial Biasa Persamaan Differensial Biasa Geometri Riset Operasi Analisis Real Analisis Real Statistika Matematika
SKS 3(2-3) 3(2-3) 4(3-3) 4(3-3) 3(3-0) 3(3-0) 4(4-0) 4(4-0) 4(3-3)
Peserta Mat 4 Mat 4 Mat 4 Mat 4 Mat 4 Mat 4 Mat 6 Mat 6 Mat 6
7
10 11
MAT 392 Statistika Matematika MAT 322 Struktur Aljabar
4(3-3) 3(3-0)
Mat 6 Mat 6
Tabel 3. Daftar mata kuliah pilihan bidang minat pemodelan semester genap di Departemen Matematika Indeks 12 13 14 15 16 17
Kode MAT 282 MAT 412 MAT 412 MAT 394 STK 425 STK 425
Mata Kuliah Pengantar Matematika Demografi Pemodelan Matematika Pemodelan Matematika Proses Stokastik Analisis Peubah Ganda Analisis Peubah Ganda
SKS 3(3-0) 3(2-3) 3(2-3) 3(3-0) 3(2-3) 3(2-3)
Peserta Mat 4 Mat 6 Mat 6 Mat 6 Mat 8 Mat 8
Tabel 4. Daftar mata kuliah pilihan bidang minat industri semester genap di Departemen Matematika Indeks 18 19 20 21
Kode MAT 272 MAT 302 MAT 362 MAT 364
Mata Kuliah Graf Algoritmik Kapita Selekta Matematika Industri Simulasi Sistem Kontrol Optimum
SKS 3(3-0) 3(3-0) 3(3-0) 3(3-0)
Peserta Mat 4 Mat 6 Mat 6 Mat 6
Tabel 5. Daftar mata kuliah pilihan bidang minat murni semester genap di Departemen Matematika Indeks 22 23 24 25 26 27 28 29
Kode MAT 332 MAT 305 MAT 372 MAT 372 MAT 334 MAT 452 MAT 376 MAT 376
Mata Kuliah Persamaan Differensial Biasa Tak Linear Kapita Selekta Matematika Murni Analisis Numerik Lanjut Analisis Numerik Lanjut Pengendalian Automatik Pengantar Analisis Fungsional Numerik Stokastik Numerik Stokastik
SKS 3(3-0) 3(3-0) 4(3-3) 4(3-3) 3(3-0) 3(3-0) 3(2-3) 3(2-3)
Peserta Mat 6 Mat 6 Mat 6 Mat 6 Mat 6 Mat 8 Mat 8 Mat 8
Tabel 6. Daftar mata kuliah pilihan bidang minat komputasi semester genap di Departemen Matematika Indeks 30 31 32 33 34
Kode KOM 212 KOM 212 MAT 374 MAT 303 MAT 342
Mata Kuliah Struktur Data Struktur Data Pengantar Teori Komputasi Kapita Selekta Matematika Komputasi Simulasi Komputer
SKS 3(2-3) 3(2-3) 3(3-0) 3(3-0) 3(3-0)
Peserta Mat 4 Mat 4 Mat 6 Mat 6 Mat 6
Tabel 7. Daftar mata kuliah pilihan bidang minat ekonomi semester genap di Departemen Matematika Indeks 35 36 37 38
Kode SEP 262 MAT 301 MAT 382 MAT 396
Mata Kuliah Makroekonomi Kapita Selekta Matematika Ekonomi Matematika Pasar Modal Matematika Aktuaria
SKS 3(3-0) 3(3-0) 3(3-0) 3(3-0)
Peserta Mat 4 Mat 6 Mat 6 Mat 6
8
Tabel 8. Daftar mata kuliah pilihan bidang minat lingkungan semester genap di Departemen Matematika Indeks 39 40
Kode Mata Kuliah MAT 304 Kapita Selekta Matematika Lingkungan MAT 384 Matematika Lingkungan
SKS 3(3-0) 3(3-0)
Peserta Mat 6 Mat 6
Tabel 9. Daftar mata kuliah pilihan tambahan Indeks 41 42
Kode MAT 408 MAT 300
Mata Kuliah Sejarah Matematika Kerja Mandiri Terpantau
Tabel 10. Periode Waktu Indeks 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
Hari Senin
Selasa
Rabu
Kamis
Jum'at
SKS 2(2-0) 2(1-1)
Peserta Mat 8 Mat 6
Tabel 11. Ruangan yang tersedia Waktu 07.00-09.30 10.00-12.30 13.00-15.30 16.00-17.40 07.00-09.30 10.00-12.30 13.00-15.30 16.00-17.40 07.00-09.30 10.00-12.30 13.00-15.30 16.00-17.40 07.00-09.30 10.00-12.30 13.00-15.30 16.00-17.40 07.00-09.30 09.50-11.30 13.00-15.30
No 1 2 3 4 5 6 7 8 9 10 11 12
Ruangan 16 Fak 401 A 16 Fak 401 B 16 Fak 401 C 16 Fak 401 D 16 Fak 401 E 14 Fak 401 A 14 Fak 401 B 14 Fak 401 C 14 Fak 401 D 14 Fak 401 E 15 TAN 301 A 15 TAN 301 B
Kapasitas 67 67 67 67 67 67 67 67 67 67 67 67
Untuk memformulasikan ILP, definisikan peubah xi , j ,k =
{
1 ; 0 ;
jika mata kuliah j diselenggarakan pada waktu i dalam ruangan k selainnya
untuk setiap periode waktu i = 1,2,…,19, mata kuliah j = 1,2,…,42, dan ruangan k = 1,2,…,12. Sehingga masalahnya dapat diformulasikan dalam ILP berikut :
Maksimumkan
i j k
xi , j ,k
9
dengan kendala : 1. Mata kuliah wajib dalam semester yang sama tidak boleh dijadwalkan pada periode waktu yang sama. xi , j ,k ≤ 1 ; ∀i j k
j = 1, 2, ..., 6
j k
xi , j ,k ≤ 1
; ∀i
j = 7, 8,...,11
2. Mata kuliah beresponsi, jadwal kuliah dan jadwal responsi harus diselenggarakan dalam hari yang berbeda. 12 2 i k =1 j =1 12
4
i k =1 j =3 12
8
i k =1 j =7 12 10 i k =1 j =9
xi , j ,k ≤ 1 xi , j ,k ≤ 1 xi , j ,k ≤ 1 xi , j ,k ≤ 1
12 14 i k =1 j =13 12 17 i k =1 j =16 12 25 i k =1 j = 24 12
29
i k =1 j = 28 12
31
i k =1 j =30
xi , j ,k ≤ 1 xi , j ,k ≤ 1 xi , j ,k ≤ 1
xi , j , k ≤ 1 ; ∀i
j = 7, 8, ...,11,19, 20, 21 j k
xi , j , k ≤ 1 ; ∀i
j = 7, 8, ...,11, 22, 23, 24, 25, 26
j k
xi , j , k ≤ 1 ; ∀i
j = 7, 8, ...,11, 32, 33, 34
j k
xi , j , k ≤ 1 ; ∀i
j = 7, 8, ...,11, 36, 37, 38
j k
xi , j , k ≤ 1 ; ∀i
j = 7, 8,...,11, 39, 40
4. Mata kuliah dalam bidang minat yang sama tidak boleh diselenggarakan pada periode waktu yang sama. 12 j =12 k 15 j =13 k 17 j =16 k 18
xi , j , k ≤ 1 xi , j , k ≤ 1
Masing-masing menggunakan i = 1, 2, 3, 4 ; i = 5, 6, 7, 8 ; i = 9,10,11,12 i = 13,14,15,16 i = 17,18,19
3. Mata kuliah wajib dan mata kuliah pilihan dalam semester yang sama tidak boleh diselenggarakan pada periode waktu yang sama. xi , j ,k ≤ 1 ; ∀i j k
j = 1, 2,..., 6,12,18, 30, 31, 35
j k
j k
xi , j ,k ≤ 1 ; ∀i
j = 7, 8, ...,11,13,14,15
j =18 k 21 j =19 k 26 j = 22 k 29 j = 27 k 31 j =30 k 34 j =32 k 35 j =35 k
xi , j , k ≤ 1 ; ∀i xi , j ,k ≤ 1 ; ∀i xi , j , k ≤ 1 ; ∀i xi , j ,k ≤ 1 ; ∀i xi , j , k ≤ 1 ; ∀i xi , j , k ≤ 1 ; ∀i xi , j , k ≤ 1 ; ∀i xi , j , k ≤ 1 ; ∀i xi , j , k ≤ 1 ; ∀i xi , j , k ≤ 1 ; ∀i
10
42 38 j =36 k 40 j =39 k
j =1
xi , j ,k ≤ 1 ; ∀i
12 12
5. Mata kuliah wajib tidak diselenggarakan pada sore hari i k =1 j =1
i k =1 j =1 12
boleh
xi , j ,k = 0
12 27 i k =1 j =18 12
6. Setiap mata kuliah diselenggarakan tepat dalam satu ruangan pada suatu periode waktu. i =1 k =1
xi , j ,k = 1
xi , j ,k = 0
i k =1 j =15
i = 4, 8,12,16
19 12
∀i , k
8. Mata kuliah dengan waktu tatap muka 3 jam tidak boleh dilaksanakan pada waktu tatap muka 2 jam.
xi , j ,k ≤ 1 ; ∀i
12 11
xi , j ,k ≤ 1 ;
;
∀j
7. Paling banyak satu mata kuliah diselenggarakan dalam suatu ruangan dan suatu periode waktu.
40
i k =1 j =32
xi , j ,k = 0 xi , j ,k = 0 xi , j ,k = 0
i = 4, 8,12,16,18
9. Semua variabel keputusan adalah integer nol atau satu. xi , j ,k ∈ {0,1} ; ∀i , j , k
Jika masalah di atas diuraikan secara manual sebagai berikut : Maks
x1,1,1 + x1,1,2 + ... + x1,1,12 + x1,2,1 + x1,2,2 + ... + x1,2,12 + ... + x1,42,1 + x1,42,2 + ... + x1,42,12 + x2,1,1 + x2,1,2 + ... + x2,1,12 + x2,2,1 + x2,2,2 + ... + x2,2,12 + ... + x2,42,1 + x2,42,2 + ... + x2,42,12 + ... + x19,1,1 + x19,1,2 + ... + x19,1,12 + x19,2,1 + x19,2,2 + ... + x19,2,12 + ... + x19,42,1 + x19,42,2 + ... + x19,42,12
Dengan kendala : Misalkan diuraikan kendala 7
.. .
x1,1,1 + x1,2,1 + ... + x1,42,1 ≤ 1
.. .
x1,1,2 + x1,2,2 + ... + x1,42,2 ≤ 1 x1,1,3 + x1,2,3 + ... + x1,42,3 ≤ 1
.. .
x2,1,12 + x2,2,12 + ... + x2,42,12 ≤ 1 x19,1,1 + x19,2,1 + ... + x19,42,1 ≤ 1
.. .
x19,1,12 + x19,2,12 + ... + x19,42,12 ≤ 1
x1,1,12 + x1,2,12 + ... + x1,42,12 ≤ 1
x2,1,1 + x2,2,1 + ... + x2,42,1 ≤ 1 Pada uraian tersebut, terlihat bahwa banyak sekali persamaan maupun pertidaksamaan yang harus diselesaikan. Dalam hal ini tidak memungkinkan jika digunakan metode branch and bound secara manual. Masalah di atas selanjutnya diselesaikan menggunakan Lingo 8.0 (Lihat lampiran 2).
Nilai fungsi objektif yang didapat adalah 42, diperoleh pada iterasi ke 7867. Hal ini memperlihatkan bahwa semua mata kuliah yang ditawarkan telah terjadwalkan. Jadwal Perkuliahan yang terbentuk adalah sebagai berikut:
11
Tabel 12. Jadwal Kuliah dan Praktikum Program Sarjana Matematika Semester Genap No 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
Hari
Senin
Selasa
Rabu
Kamis
Jum'at
Waktu 07.00-09.30 07.00-09.30 07.00-09.30 10.00-12.30 10.00-12.30 13.00-15.30 13.00-15.30 16.00-17.40 16.00-17.40 07.00-09.30 07.00-09.30 07.00-09.30 07.00-09.30 07.00-09.30 10.00-12.30 10.00-12.30 13.00-15.30 13.00-15.30 13.00-15.30 13.00-15.30 13.00-15.30 13.00-15.30 07.00-09.30 07.00-09.30 07.00-09.30 07.00-09.30 07.00-09.30 07.00-09.30 10.00-12.30 10.00-12.30 10.00-12.30 10.00-12.30 13.00-15.30 07.00-09.30 13.00-15.30 15.30-18.00 16.00-17.40 07.00-09.30 07.00-09.30 13.00-15.30 13.00-15.30 13.00-15.30
Mata Kuliah
Ruangan Kalkulus 3 / K 14 Fak 401 C Analisis Real 14 Fak 401 E Analisis Peubah Ganda / K 16 Fak 401 A Persamaan Differensial Biasa / K 16 Fak 401 A Statistika Matematika / K 16 Fak 401 B Geometri 16 Fak 401 A Struktur Aljabar 16 Fak 401 B Pemodelan Matematika / K 16 Fak 401 B Struktur Data / K 16 Fak 401 A Persamaan Differensial Biasa / R 16 Fak 401 A Analisis Real 16 Fak 401 B Analisis Peubah Ganda / P Lab. Komputer A Pengantar Analisis Fungsional 16 Fak 401 C Kerja Mandiri Terpantau 14 Fak 401 A Riset Operasi 16 Fak 401 A Statistika Matematika / R 16 Fak 401 B Pengantar Matematika Demografi 16 Fak 401 A Pemodelan Matematika / P Lab. Komputer A Kapita Selekta Matematika Industri 16 Fak 401 C Persamaan Differensial Biasa Tak Linnear 16 Fak 401 D Pengantar Teori Komputasi 16 Fak 401 E Matematika Pasar Modal 14 Fak 401 A Proses Stokastik 16 Fak 401 A Graf Algoritmik 16 Fak 401 B Simulasi Sistem 16 Fak 401 C Kapita Selekta Matematika Murni 16 Fak 401 E Kapita Selekta Matematika Komputasi 16 Fak 401 D Matematika Aktuaria 14 Fak 401 A Kalkulus 3 / R 14 Fak 401 D Kontrol Optimum 16 Fak 401 A Analisis Numerik Lanjut / K 16 Fak 401 B Simulasi Komputer 16 Fak 401 C Pengendalian Automatik 16 Fak 401 A Analisis Numerik Lanjut / P Lab. Komputer A Numerik Stokastik / K 16 Fak 401 A Struktur Data / P Lab. Komputer A Sejarah Matematika 14 Fak 401 A Numerik Stokastik / P Lab. Komputer A Kapita Selekta Matematika Lingkungan 16 Fak 401 C Makroekonomi 15 TAN 301 B Kapita Selekta Matematika Ekonomi 16 Fak 401 A Matematika Lingkungan 16 Fak 401 D
12
V. SIMPULAN DAN SARAN 5.1 Simpulan
Masalah penjadwalan ruang kuliah merupakan hal penting dalam pelaksanaan proses perkuliahan di beberapa sekolah tinggi ataupun universitas. Hal ini dialami oleh Institut Pertanian Bogor khususnya di Departemen Matematika. Dalam penulisan ini telah diperlihatkan bahwa masalah penjadwalan perkuliahan di departemen matematika dapat dipandang sebagai masalah 0-1 ILP. Penyelesaian masalah ini menggunakan software LINGO 8.0 dengan metode Branch and Bound. Hasil yang diperoleh yaitu jadwal perkuliahan dan praktikum semester genap yang memenuhi kendala utama dan kendala tambahan yang ada, dengan nilai fungsi objektif 42, artinya semua mata kuliah yang ditawarkan terjadwalkan, didapat pada iterasi ke 7867. Keuntungan dari menyelesaikan masalah penjadwalan perkuliahan dengan menggunakan model ILP adalah memungkinkan pengguna untuk mengontrol
atau menambahkan kendala dengan bebas dan mengatur koefisien fungsi objektifnya. Sebagai contoh, jika departemen menginginkan keadaan bahwa dosen tidak dapat mengajar dua mata kuliah dalam waktu yang berurutan, maka kendala harus ditambahkan. Begitu pula, tingkat kepuasan pilihan mata kuliah dan pilihan waktu dapat diubah dengan menyertakan ke dalam koefisien fungsi objektif. Perubahan yang lain sangat mungkin untuk dilakukan. 5.2 Saran
Pada tulisan ini telah dibahas Jadwal Perkuliahan Semester genap di Departemen Matematika. Akan lebih baik lagi jika ada yang dapat menindaklanjuti penelitian ini dengan masalah yang lebih kompleks lagi, misalnya membuat jadwal yang mempertimbangkan mahasiswa pengulang selain itu juga mempertimbangkan kesediaan dosen mengajar pada jadwal yang dihasilkan.
13
DAFTAR PUSTAKA Anonim .2003. Buku Panduan Pendidikan Program Sarjana IPB tahun 2000-2005 edisi tahun 2003. BAPSI dan BAAK IPB.
Ng PH, Martin LM. 2002. Classroom Scheduling Problems:A Discrete Optimization Approach. The UMAP Journal 23.1:57-66.
Garfinkel RS, Nemhauser GL .1972. Integer Programming. New York: John Willey & Sons.
Taha HA .1975. Integer Programming. New York: Academic Press.
Nash SG, Sofer A .1996. Linear and Nonlinear Programming. New York: McGraw-Hill.
Winston WL .1995. Introduction to Mathematical Programming 2nded. New York: Duxbury.
14
LAMPIRAN
15
Lampiran 1 Contoh penyelesaian suatu LP dengan metode branch and bound
Dari LP pada Contoh 2 Misalkan diberikan integer programming berikut: Maksimumkan z = 2 x1 + 3 x2 …(1) Terhadap : x1 + 2 x2 ≤ 10 3 x1 + 4 x2 ≤ 25
…(2) …(3)
x1 , x2 ≥ 0 dan integer ...(4) Penyelesaian : Daerah fisibel untuk masalah IP di atas diberikan pada gambar berikut :
x2 6
Solusi Optimal Subproblem 1
5
x1 = 5 x2= 2,5
4 3 2 1 2
-1
4
6
8
10
x1
Gambar 1. Daerah Fisibel IP LP tersebut anggap sebagai Subproblem 1. 1. Cari solusi LP-Relaksasi dari subproblem 1 Dengan mengeliminasi persamaan (2) dan (3) didapat x1 = 5, x2 = 2,5. Substitusikan hasil tersebut ke dalam persamaan (1) didapat z = 17,5. Karena solusi yang didapat belum memenuhi kendala integer maka harus dibuat subproblem baru, yaitu: Subproblem 2 : Subproblem 1 + kendala ( x2 ≥ 3)
Subproblem 3 : Subproblem 1 + kendala ( x2 ≤ 2 ) Daerah fisibel untuk subproblem 2 dan subproblem 3 diberikan pada gambar berikut :
x2
6 5 4 3 2 1 2
4
6
8
x1
10
-1
Gambar 2. Daerah Fisibel untuk Subproblem 2 dan Subproblem 3 2.
Cari solusi LP-Relaksasi dari subproblem 2 x2 = 3 Substitusikan x2 = 3 ke persamaan x1 + 2 x2 = 10 …(5)
16
Sehingga didapatkan x1 = 4 . Substitusikan nilai x1 dan x2 yang didapat ke persamaan (1) sehingga diperoleh z = 17. 3.
Cari solusi LP-Relaksasi dari subproblem 3 x2 = 2 Substitusikan x2 = 2 ke persamaan (5) Sehingga didapatkan x1 = 5, 667 . Substitusikan nilai x1 dan x2 yang didapat ke persamaan (1) sehingga diperoleh z = 13,333. Karena solusi yang didapat belum memenuhi kendala integer maka harus dibuat subproblem baru, yaitu:
( ) Subproblem 5 : Subproblem 3 + kendala ( x1 ≥ 6 ) Subproblem 4 : Subproblem 3 + kendala x1 ≤ 5
Daerah fisibel untuk subproblem 4 dan subproblem 5 diberikan pada gambar berikut : x2
6 5 4 3 2 1 2
4
6
8
x1
10
x1
-1
Subproblem 4
Subproblem 5
Gambar 4. Daerah Fisibel untuk subproblem 4 dan subproblem 5 4.
Cari solusi LP-Relaksasi dari subproblem 4 x1 = 5 Substitusikan x1 = 5 ke persamaan (5) Sehingga didapatkan x2 = 2, 5 . Substitusikan nilai x1 dan x2 yang didapat ke persamaan (1) sehingga diperoleh z = 17,5. Karena titik (5;2,5) tidak berada di daerah fisibel subproblem 4, maka subproblem 4 tidak memiliki solusi fisibel.
5.
Cari solusi LP-Relaksasi dari subproblem 5 x1 = 6 Substitusikan x1 = 6 ke persamaan 3 x1 + 4 x2 = 25 …(6) Sehingga didapatkan x2 = 1, 75 . Substitusikan nilai x1 dan x2 yang didapat ke persamaan (1) sehingga diperoleh z = 17,25. Karena solusi yang didapat belum memenuhi kendala integer maka harus dibuat subproblem baru, yaitu:
( ) Subproblem 7 : Subproblem 5 + kendala ( x2 ≤ 1) Subproblem 6 : Subproblem 5 + kendala x2 ≥ 2
17
Daerah fisibel untuk subproblem 6 dan subproblem 7 diberikan pada gambar berikut : x2
6 5 4 3
Subproblem 6
2 1 2
4
6
8
x1
10
x1
-1
Subproblem 7
Gambar 5. Daerah Fisibel untuk subproblem 6 dan subproblem 7 6.
Cari solusi LP-Relaksasi dari subproblem 6 x2 = 2 Substitusikan x2 = 2 ke persamaan (5) Sehingga didapatkan x1 = 6 . Substitusikan nilai x1 dan x2 yang didapat ke persamaan (1) sehingga diperoleh z = 18. Karena titik (6,2) tidak berada di daerah fisibel LP (lihat gambar), maka subproblem 6 tidak memiliki solusi fisibel.
7.
Cari solusi LP-Relaksasi dari subproblem 7 x2 = 1 Substitusikan x2 = 1 ke persamaan (6) Sehingga didapatkan x1 = 7 . Substitusikan nilai x1 dan x2 yang didapat ke persamaan (1) sehingga diperoleh z = 17.
Dari subproblem-subproblem di atas terlihat bahwa subproblem 2 dan subproblem 7 yang memenuhi kendala integer. Karena nilai fungsi objektik dari kedua subproblem tersebut sama, maka solusi optimal dari LP tersebut terdapat pada titik x1 = 7 dan x2 = 1 serta x1 = 4 dan x2 = 3 dengan nilai fungsi objektif 17.
18
Lampiran 2 Program untuk menyelesaikan masalah Penjadwalan Perkuliahan Semester Genap di Departemen Matematika dengan menggunakan Lingo 8.0. MODEL: TITLE Penjadwalan Mata Kuliah Semester genap di Departemen Matematika; SETS: WAKTU /W1 W2..W19/; MATA_KULIAH /M1 M2..M42/; RUANGAN / R1 R2 .. R12/; KOMBINASI(WAKTU,MATA_KULIAH,RUANGAN): X; ENDSETS !Fungsi Objektif; MAX = @SUM(KOMBINASI(I,J,K):X); !Kendala; !1 Mata kuliah wajib semester yang sama tidak boleh diselenggarakan pada periode waktu yang sama; !a Mata kuliah wajib semester 4; @FOR(WAKTU(I):@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#7:X(I,J,K)) )<=1); !b Mata kuliah wajib semester 6; @FOR(WAKTU(I):@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#12 #AND# J#GT#6:X(I,J,K)))<=1); !2 Mata kuliah beresponsi, jadwal kuliah dan jadwal responsi harus diselenggarakan dalam hari yang berbeda; ! Kalkulus 3; @SUM(WAKTU(I)|I#EQ#1:@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#3:X( I,J,K)+ X(I+1,J,K)+X(I+2,J,K)+X(I+3,J,K))))<=1; @SUM(WAKTU(I)|I#EQ#5:@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#3:X( I,J,K)+ X(I+1,J,K)+X(I+2,J,K)+X(I+3,J,K))))<=1; @SUM(WAKTU(I)|I#EQ#9:@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#3:X( I,J,K)+ X(I+1,J,K)+X(I+2,J,K)+X(I+3,J,K))))<=1; @SUM(WAKTU(I)|I#EQ#13:@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#3:X (I,J,K)+ X(I+1,J,K)+X(I+2,J,K)+X(I+3,J,K))))<=1; @SUM(WAKTU(I)|I#EQ#17:@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#3:X (I,J,K)+ X(I+1,J,K)+X(I+2,J,K))))<=1; !Persamaan Differensial Biasa; @SUM(WAKTU(I)|I#EQ#1:@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#5 #AND# J#GT#2:X(I,J,K)+ X(I+1,J,K)+X(I+2,J,K)+X(I+3,J,K))))<=1; @SUM(WAKTU(I)|I#EQ#5:@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#5 #AND# J#GT#2:X(I,J,K)+ X(I+1,J,K)+X(I+2,J,K)+X(I+3,J,K))))<=1; @SUM(WAKTU(I)|I#EQ#9:@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#5 #AND# J#GT#2:X(I,J,K)+ X(I+1,J,K)+X(I+2,J,K)+X(I+3,J,K))))<=1; @SUM(WAKTU(I)|I#EQ#13:@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#5 #AND# J#GT#2:X(I,J,K)+ X(I+1,J,K)+X(I+2,J,K)+X(I+3,J,K))))<=1;
19
@SUM(WAKTU(I)|I#EQ#17:@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#5 #AND# J#GT#2:X(I,J,K)+ X(I+1,J,K)+X(I+2,J,K))))<=1; !Analisis Real; @SUM(WAKTU(I)|I#EQ#1:@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#9 #AND# J#GT#6:X(I,J,K)+ X(I+1,J,K)+X(I+2,J,K)+X(I+3,J,K))))<=1; @SUM(WAKTU(I)|I#EQ#5:@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#9 #AND# J#GT#6:X(I,J,K)+ X(I+1,J,K)+X(I+2,J,K)+X(I+3,J,K))))<=1; @SUM(WAKTU(I)|I#EQ#9:@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#9 #AND# J#GT#6:X(I,J,K)+ X(I+1,J,K)+X(I+2,J,K)+X(I+3,J,K))))<=1; @SUM(WAKTU(I)|I#EQ#13:@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#9 #AND# J#GT#6:X(I,J,K)+ X(I+1,J,K)+X(I+2,J,K)+X(I+3,J,K))))<=1; @SUM(WAKTU(I)|I#EQ#17:@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#9 #AND# J#GT#6:X(I,J,K)+ X(I+1,J,K)+X(I+2,J,K))))<=1; !Statistika Matematika; @SUM(WAKTU(I)|I#EQ#1:@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#11 #AND# J#GT#8:X(I,J,K)+ X(I+1,J,K)+X(I+2,J,K)+X(I+3,J,K))))<=1; @SUM(WAKTU(I)|I#EQ#5:@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#11 #AND# J#GT#8:X(I,J,K)+ X(I+1,J,K)+X(I+2,J,K)+X(I+3,J,K))))<=1; @SUM(WAKTU(I)|I#EQ#9:@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#11 #AND# J#GT#8:X(I,J,K)+ X(I+1,J,K)+X(I+2,J,K)+X(I+3,J,K))))<=1; @SUM(WAKTU(I)|I#EQ#13:@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#11 #AND# J#GT#8:X(I,J,K)+ X(I+1,J,K)+X(I+2,J,K)+X(I+3,J,K))))<=1; @SUM(WAKTU(I)|I#EQ#17:@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#11 #AND# J#GT#8:X(I,J,K)+ X(I+1,J,K)+X(I+2,J,K))))<=1; !Pemodelan Matematika; @SUM(WAKTU(I)|I#EQ#1:@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#15 #AND# J#GT#12:X(I,J,K)+ X(I+1,J,K)+X(I+2,J,K)+X(I+3,J,K))))<=1; @SUM(WAKTU(I)|I#EQ#5:@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#15 #AND# J#GT#12:X(I,J,K)+ X(I+1,J,K)+X(I+2,J,K)+X(I+3,J,K))))<=1; @SUM(WAKTU(I)|I#EQ#9:@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#15 #AND# J#GT#12:X(I,J,K)+ X(I+1,J,K)+X(I+2,J,K)+X(I+3,J,K))))<=1; @SUM(WAKTU(I)|I#EQ#13:@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#15 #AND# J#GT#12:X(I,J,K)+ X(I+1,J,K)+X(I+2,J,K)+X(I+3,J,K))))<=1; @SUM(WAKTU(I)|I#EQ#17:@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#15 #AND# J#GT#12:X(I,J,K)+ X(I+1,J,K)+X(I+2,J,K))))<=1; !Analisis Peubah Ganda; @SUM(WAKTU(I)|I#EQ#1:@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#18 #AND# J#GT#15:X(I,J,K)+ X(I+1,J,K)+X(I+2,J,K)+X(I+3,J,K))))<=1; @SUM(WAKTU(I)|I#EQ#5:@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#18 #AND# J#GT#15:X(I,J,K)+ X(I+1,J,K)+X(I+2,J,K)+X(I+3,J,K))))<=1;
20
@SUM(WAKTU(I)|I#EQ#9:@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#18 #AND# J#GT#15:X(I,J,K)+ X(I+1,J,K)+X(I+2,J,K)+X(I+3,J,K))))<=1; @SUM(WAKTU(I)|I#EQ#13:@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#18 #AND# J#GT#15:X(I,J,K)+ X(I+1,J,K)+X(I+2,J,K)+X(I+3,J,K))))<=1; @SUM(WAKTU(I)|I#EQ#17:@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#18 #AND# J#GT#15:X(I,J,K)+ X(I+1,J,K)+X(I+2,J,K))))<=1; !Analisis Numerik Lanjut; @SUM(WAKTU(I)|I#EQ#1:@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#26 #AND# J#GT#23:X(I,J,K)+ X(I+1,J,K)+X(I+2,J,K)+X(I+3,J,K))))<=1; @SUM(WAKTU(I)|I#EQ#5:@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#26 #AND# J#GT#23:X(I,J,K)+ X(I+1,J,K)+X(I+2,J,K)+X(I+3,J,K))))<=1; @SUM(WAKTU(I)|I#EQ#9:@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#26 #AND# J#GT#23:X(I,J,K)+ X(I+1,J,K)+X(I+2,J,K)+X(I+3,J,K))))<=1; @SUM(WAKTU(I)|I#EQ#13:@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#26 #AND# J#GT#23:X(I,J,K)+ X(I+1,J,K)+X(I+2,J,K)+X(I+3,J,K))))<=1; @SUM(WAKTU(I)|I#EQ#17:@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#26 #AND# J#GT#23:X(I,J,K)+ X(I+1,J,K)+X(I+2,J,K))))<=1; !Numerik Stokastik; @SUM(WAKTU(I)|I#EQ#1:@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#30 #AND# J#GT#27:X(I,J,K)+ X(I+1,J,K)+X(I+2,J,K)+X(I+3,J,K))))<=1; @SUM(WAKTU(I)|I#EQ#5:@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#30 #AND# J#GT#27:X(I,J,K)+ X(I+1,J,K)+X(I+2,J,K)+X(I+3,J,K))))<=1; @SUM(WAKTU(I)|I#EQ#9:@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#30 #AND# J#GT#27:X(I,J,K)+ X(I+1,J,K)+X(I+2,J,K)+X(I+3,J,K))))<=1; @SUM(WAKTU(I)|I#EQ#13:@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#30 #AND# J#GT#27:X(I,J,K)+ X(I+1,J,K)+X(I+2,J,K)+X(I+3,J,K))))<=1; @SUM(WAKTU(I)|I#EQ#17:@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#30 #AND# J#GT#27:X(I,J,K)+ X(I+1,J,K)+X(I+2,J,K))))<=1; !Struktur Data; @SUM(WAKTU(I)|I#EQ#1:@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#32 #AND# J#GT#29:X(I,J,K)+ X(I+1,J,K)+X(I+2,J,K)+X(I+3,J,K))))<=1; @SUM(WAKTU(I)|I#EQ#5:@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#32 #AND# J#GT#29:X(I,J,K)+ X(I+1,J,K)+X(I+2,J,K)+X(I+3,J,K))))<=1; @SUM(WAKTU(I)|I#EQ#9:@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#32 #AND# J#GT#29:X(I,J,K)+ X(I+1,J,K)+X(I+2,J,K)+X(I+3,J,K))))<=1; @SUM(WAKTU(I)|I#EQ#13:@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#32 #AND# J#GT#29:X(I,J,K)+ X(I+1,J,K)+X(I+2,J,K)+X(I+3,J,K))))<=1; @SUM(WAKTU(I)|I#EQ#17:@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#32 #AND# J#GT#29:X(I,J,K)+ X(I+1,J,K)+X(I+2,J,K))))<=1; !3 Mata kuliah wajib dengan mata kuliah pilihan dalam semester yang sama tidak boleh diselenggarakan pada waktu sama;
21
!a Mata kuliah wajib semester 4 dengan mata kuliah pilihan semester 4; @FOR(WAKTU(I):@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#EQ#1:X(I,J,K)+ X(I,J+1,K)+X(I,J+2,K)+X(I,J+3,K)+X(I,J+4,K)+X(I,J+5,K)+X(I,J+11,K) +X(I,J+17,K)+X(I,J+29,K)+X(I,J+30,K)+X(I,J+34,K)))<=1); !b Mata kuliah wajib semester 6 dengan mata kuliah pilihan bidang minat pemodelan; @FOR(WAKTU(I):@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#EQ#7:X(I,J,K)+ X(I,J+1,K)+X(I,J+2,K)+X(I,J+3,K)+X(I,J+4,K)+X(I,J+6,K)+X(I,J+7,K)+ X(I,J+8,K)))<=1); !c Mata kuliah wajib semester 6 dengan mata kuliah pilihan bidang minat industri; @FOR(WAKTU(I):@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#EQ#7:X(I,J,K)+ X(I,J+1,K)+X(I,J+2,K)+X(I,J+3,K)+X(I,J+4,K)+X(I,J+12,K)+X(I,J+13,K )+X(I,J+14,K)))<=1); !d Mata kuliah wajib semester 6 dengan mata kuliah pilihan bidang minat murni; @FOR(WAKTU(I):@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#EQ#7:X(I,J,K)+ X(I,J+1,K)+X(I,J+2,K)+X(I,J+3,K)+X(I,J+4,K)+X(I,J+15,K)+X(I,J+16,K )+X(I,J+17,K)+X(I,J+18,K)+X(I,J+19,K)))<=1); !e Mata kuliah wajib semester 6 dengan mata kuliah pilihan bidang minat komputasi; @FOR(WAKTU(I):@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#EQ#7:X(I,J,K)+ X(I,J+1,K)+X(I,J+2,K)+X(I,J+3,K)+X(I,J+4,K)+X(I,J+25,K)+X(I,J+26,K )+X(I,J+27,K)))<=1); !f Mata kuliah wajib semester 6 dengan mata kuliah pilihan bidang minat ekonomi; @FOR(WAKTU(I):@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#EQ#7:X(I,J,K)+ X(I,J+1,K)+X(I,J+2,K)+X(I,J+3,K)+X(I,J+4,K)+X(I,J+29,K)+X(I,J+30,K )+X(I,J+31,K)))<=1); !g Mata kuliah wajib semester 6 dengan mata kuliah pilihan bidang minat lingkungan; @FOR(WAKTU(I):@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#EQ#7:X(I,J,K)+ X(I,J+1,K)+X(I,J+2,K)+X(I,J+3,K)+X(I,J+4,K)+X(I,J+32,K)+X(I,J+33,K )))<=1); !4 Mata kuliah dalam bidang minat yang sama tidak boleh diselenggarakan pada periode waktu yang sama; !a Bidang minat pemodelan; @FOR(WAKTU(I):@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#EQ#12:X(I,J,K) ))<=1); @FOR(WAKTU(I):@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#16 #AND# J#GT#12:X(I,J,K)))<=1); @FOR(WAKTU(I):@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#18 #AND# J#GT#15:X(I,J,K)))<=1); !b Bidang minat industri; @FOR(WAKTU(I):@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#EQ#18:X(I,J,K) ))<=1); @FOR(WAKTU(I):@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#22 #AND# J#GT#18:X(I,J,K)))<=1); !c Bidang minat murni; @FOR(WAKTU(I):@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#27 #AND# J#GT#21:X(I,J,K)))<=1);
22
@FOR(WAKTU(I):@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#30 #AND# J#GT#26:X(I,J,K)))<=1); !d Bidang minat komputasi; @FOR(WAKTU(I):@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#32 #AND# J#GT#29:X(I,J,K)))<=1); @FOR(WAKTU(I):@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#35 #AND# J#GT#31:X(I,J,K)))<=1); !e ekonomi; @FOR(WAKTU(I):@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#EQ#35:X(I,J,K) ))<=1); @FOR(WAKTU(I):@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#39 #AND# J#GT#35:X(I,J,K)))<=1); !f lingkungan; @FOR(WAKTU(I):@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#41 #AND# J#GT#38:X(I,J,K)))<=1); !5 Mata kuliah yang wajib tidak boleh dilaksanakan pada sore hari; @SUM(WAKTU(I)|I#EQ#4:@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#12: X(I,J,K) + X(I+4,J,K)+X(I+8,J,K)+X(I+12,J,K))))=0; !6 Setiap mata kuliah dilaksanakan tepat dalam satu ruangan; @FOR(MATA_KULIAH(J):@SUM(WAKTU(I):@SUM(RUANGAN(K):X(I,J,K)))=1); !7 Paling banyak satu mata kuliah diselenggarakan dalam suatu ruangan dan suatu periode waktu; @FOR(WAKTU(I):@FOR(RUANGAN(K):@SUM(MATA_KULIAH(J):X(I,J,K))<=1)); !8 Mata kuliah dengan waktu tatap muka di kelas 3 jam tidak boleh dilaksanakan pada waktu tatap muka di kelas 2 jam; @SUM(WAKTU(I)|I#EQ#4:@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#13: X(I,J,K) + X(I+4,J,K)+X(I+8,J,K)+X(I+12,J,K)+X(I+14,J,K))))=0; @SUM(WAKTU(I)|I#EQ#4:@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#EQ#15: X(I,J,K) + X(I+4,J,K)+X(I+8,J,K)+X(I+12,J,K)+X(I+14,J,K))))=0; @SUM(WAKTU(I)|I#EQ#4:@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#28 #AND# J#GT#17: X(I,J,K) + X(I+4,J,K)+X(I+8,J,K)+X(I+12,J,K)+X(I+14,J,K))))=0; @SUM(WAKTU(I)|I#EQ#4:@SUM(RUANGAN(K):@SUM(MATA_KULIAH(J)|J#LT#41 #AND# J#GT#31: X(I,J,K) + X(I+4,J,K)+X(I+8,J,K)+X(I+12,J,K)+X(I+14,J,K))))=0; !9 variabel X adalah integer nol atau satu; @FOR(KOMBINASI:@BIN(X)); END
23
Solution Report : Global optimal solution found at iteration: Objective value:
7867 42.00000
Model Title: Penjadwalan Mata Kuliah Semester genap di Departemen Matematika Variable X( W1, M1, R8) X( W1, M7, R10) X( W1, M16, R1) X( W2, M3, R1) X( W2, M9, R2) X( W3, M5, R1) X( W3, M11, R2) X( W4, M13, R2) X( W4, M31, R1) X( W5, M4, R1) X( W5, M8, R2) X( W5, M17, R4) X( W5, M27, R3) X( W5, M42, R6) X( W6, M6, R1) X( W6, M10, R2) X( W7, M12, R1) X( W7, M14, R2)
Value 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000
ReducedCost -1.000000 -1.000000 -1.000000 -1.000000 -1.000000 -1.000000 -1.000000 -1.000000 -1.000000 -1.000000 -1.000000 -1.000000 -1.000000 -1.000000 -1.000000 -1.000000 -1.000000 -1.000000
24
X( W7, M19, R3) X( W7, M22, R4) X( W7, M32, R5) X( W7, M37, R6) X( W9, M15, R7) X( W9, M18, R6) X( W9, M20, R1) X( W9, M23, R1) X( W9, M33, R2) X( W9, M38, R3) X( W10, M2, R4) X( W10, M21, R5) X( W10, M24, R6) X( W10, M34, R6) X( W11, M26, R2) X( W13, M25, R1) X( W15, M28, R3) X( W16, M30, R1) X( W16, M41, R1) X( W17, M29, R1) X( W17, M39, R6) X( W19, M35, R10) X( W19, M36, R4) X( W19, M40, R9)
1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000
-1.000000 -1.000000 -1.000000 -1.000000 -1.000000 -1.000000 -1.000000 -1.000000 -1.000000 -1.000000 -1.000000 -1.000000 -1.000000 -1.000000 -1.000000 -1.000000 -1.000000 -1.000000 -1.000000 -1.000000 -1.000000 -1.000000 -1.000000 -1.000000
