PEMODELAN Deskripsi Masalah Sebelum membuat penjadwalan perkuliahan 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. Sehingga untuk membuat jadwal harus memperhatikan aspek sebagai berikut: hari, jam, ruang dan mata kuliah. Setiap mata kuliah dialokasikan pada suatu hari. Pengalokasian hari dapat dirancang sesuai keinginan pengajarnya. Misalkan pengajar dapat meminta hari tertentu untuk mengajar mata kuliah atau untuk tidak mengajar mata kuliah. Ada hari tertentu yang disukai banyak pengajar untuk melaksanakan perkuliahan seperti Selasa, Rabu dan Kamis. Ada pula hari yang dihindari sebagian pengajar seperti Senin dan Jumat. Pada hari Sabtu kegiatan administrasi ditiadakan, tapi universitas mempersilahkan kegiatan perkuliahan dan perpustakaan. Perkuliahan yang dialokasikan pada hari Sabtu biasanya karena permintaan pengajarnya atau karena ketidaktersediaan ruang dari hari Senin sampai Jumat. Setiap mata kuliah memerlukan jam tertentu untuk melaksanakan kegiatan perkuliahan. Jam perkuliahan 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. Ada jam tertentu yang diinginkan untuk mengajar ada pula jam tertentu yang dihindari pengajar. Jam yang banyak disukai untuk mengajar mata kuliah seperti jam kedua dan ketiga. Perkuliahan memerlukan ruang yang fasilitasnya sesuai dengan kebutuhan kuliah tersebut. Misal mata kuliah Pemprograman Komputer memerlukan ruang berfasilitas komputer agar perkuliahan terlaksana, atau mata kuliah Listening memerlukan Laboratorium Bahasa agar perkuliahan lebih efektif. Perkuliahan yang tidak memerlukan fasilitas khusus dapat dilaksanakan di ruang regular yang pada umumnya berkapasitas 50 peserta. 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
21
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 sedemikian rupa 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. Berdasarkan sks-nya mata kuliah dapat dibedakan menjadi 2 sks dan 3 sks. Satu sks berdurasi 50 menit tatap muka, dua sks berdurasi 100 menit dan 3 sks berdurasi 150 menit. Sedangkan jam perkuliahan pada satu hari dibagi 5, yang setiap jamnya berdurasi 100 menit atau 2 sks. Jika pada jam pertama suatu ruang digunakan untuk perkuliahan 3 sks maka pada jam kedua pun ruang tersebut masih digunakan untuk kuliah yang sama. Sehingga pada jam kedua ruang tersebut tidak dapat dialokasikan mata kuliah lain. Perkuliahan selanjutnya harus dialokasikan setelah kuliah 3 sks tersebut selesai, yaitu jam ketiga. Demikian pula peserta perkuliahan. Jika peserta dijadwalkan untuk mengikuti kuliah 3 sks pada jam ketiga, maka mata kuliah selanjutnya diikuti pada jam kelima. Sedangkan kegiatan pendukung perkuliahan yang bobotnya 0 sks berdurasi 100 menit. Mata kuliah yang ditawarkan dapat dikelompokkan menjadi beberapa kompetensi, yaitu: Lintas Program Studi (Prodi)/Dasar, Prodi/Utama, dan Pendukung. Mata kuliah Utama memiliki muatan materi yang menjadi kompetensi wajib setiap peserta. Sehingga penjadwalan mengupayakan pada satu hari hanya ada satu mata kuliah utama atau paling banyak dua mata kuliah utama untuk satu peserta perkuliahan.
22
Formulasi Masalah Tujuan utama penjadwalan adalah memenuhi semua batasan dan memaksimalkan nilai kepuasan penggunaan waktu yang disukai untuk perkuliahan. Nilai kepuasan ini dilambangkan dengan koefisien nilai pada variabel hari dan jam. Batasan-batasan yang dihadapi terdiri dari batasan utama (hard constraints) dan batasan tambahan (soft constraints). Batasan utama 1. Semua mata kuliah yang ditawarkan harus terjadwalkan. 2. Pada setiap ruang pada suatu waktu paling banyak hanya ada satu perkuliahan. 3. Semua mata kuliah memerlukan ruang dengan kualifikasi tertentu. 4. Beberapa mata kuliah tidak dapat dilaksanakan bersamaan karena pesertanya sama. 5. Beberapa mata kuliah tidak dapat dijadwalkan bersamaan karena pengajarnya sama. 6. Pada ruang atau peserta yang sama setelah mata kuliah 3 sks tidak dapat dijadwalkan mata kuliah lain selama satu jam perkuliahan. Batasan tambahan 7. Beberapa mata kuliah yang sama dengan pengajarnya yang sama pula maka mata kuliah tersebut dijadwalkan berturut-turut. 8. Pengajar hanya mengajar pada hari yang diinginkan. 9. Beberapa mata kuliah tidak dapat dijadwalkan pada waktu tertentu. Untuk menyederhanakan masalah yang memudahkan pemodelan digunakan asumsi-asumsi sebagai berikut: 1. Semua mata kuliah yang ditawarkan dapat diidentifikasi pesertanya, ruang yang diperlukan, pengajarnya, kesediaan waktu mengajar, serta sksnya. 2. Perkuliahan 3 sks dilaksanakan dengan menggunakan dua jam perkuliahan dalam sehari.
23
Model Langkah selanjutnya akan dibuat model dari formulasi masalah tersebut. Misalkan: A
= Himpunan hari perkuliahan yang anggotanya terdiri dari Senin, Selasa,Rabu, Kamis, dan Jumat. Indeks a = 1, 2, 3, 4, 5.
B
= Himpunan jam perkuliahan yang anggotanya terdiri dari I (07.30 – 09.10), II (09.20 – 11.00), III (11.10 – 12.50), IV (13.30 – 15.10) dan V (15.30 – 17.10). Indeks b = 1, 2, 3, 4, 5.
C
= Himpunan semua ruang perkuliahan yang digunakan.
D
= Himpunan semua mata kuliah yang ditawarkan
Daa
= Himpunan bagian mata kuliah yang diselenggarakan pada hari ke-a.
Dbb
= Himpunan bagian mata kuliah yang diselenggarakan pada jam ke-b.
Dcc
= Himpunan bagian mata kuliah yang diselenggarakan di ruang c.
Dmm = Himpunan bagian mata kuliah yang diikuti oleh peserta perkuliahan ke-m. Dpp
= Himpunan bagian mata kuliah yang diajar oleh pengajar p.
Dss
= Himpunan bagian mata kuliah yang sksnya s.
Nab
= Nilai kepuasan pelaksanaan suatu mata kuliah pada hari dan jam tertentu.
Misalkan xa,b,c,d, dengan a ∈ A, A = 1, ...,p; b ∈ B, b = 1, ...,q; c ∈ C, k = 1, ..., r; d ∈ D, d = 1, ..., s merupakan variabel keputusan bernilai biner sebagai berikut:
xa ,b,c ,d = {
1, jika mata kuliah d dialokasikan pada hari a waktu b di ruang c 0 , selainnya
Maksimumkan z = ∑∑∑∑ xa ,b ,c ,d ∗ N a ,b
(1)
a∈A b∈B c∈C d∈D
Batasan utama yang dipergunakan sebagai berikut: 1.
Semua mata kuliah terjadwal di satu ruang pada suatu hari dan suatu jam.
∑∑∑ x a∈A b∈B c∈C
a ,b , c , d
= 1, untuk d ∈ D
(2)
24
2.
Semua mata kuliah terjadwal di suatu ruang yang sesuai dengan kualifikasinya pada suatu hari dan suatu jam.
∑∑∑ x a∈A b∈B c∈C
3.
a ,b ,c , dcc
= 1, untuk dcc ∈ D dan U dcc = D
(3)
Paling banyak satu mata kuliah yang dialokasikan pada satu ruang di setiap hari dan setiap jam.
∑x
d∈D
4.
≤ 1, untuk a ∈ A; b ∈ B; c ∈ C
a ,b ,c ,d
(4)
Perkuliahan yang pesertanya sama harus dialokasikan pada waktu yang berbeda.
∑x
≤ 1, untuk a ∈ A; b ∈ B; c ∈ C ; dmm ∈ D
a ,b ,c , dmm
(5)
dmm
5. Beberapa mata kuliah tidak dapat dijadwalkan bersamaan karena pengajarnya sama.
∑x
a ,b ,c , dp p
≤ 1, untuk a ∈ A; b ∈ B; c ∈ C ; dp p ∈ D
(6)
dp p
Pada batasan tambahan ini akan dimodelkan pengalokasian dua mata kuliah yang berurutan, tiga mata kuliah yang berurutan serta waktu tertentu yang tidak dapat dijadwalkan perkuliahan. Model sebagai berikut: 6.
Beberapa mata kuliah yang pengajarnya sama dijadwalkan berurutan.
∑ (x c∈C
7.
a ,b ,c ,i
− xa ,b +1,c , j ) = 0, untuk a ∈ A; b = 1,..., (q − 1); (i, j ) ∈ DxD
Ada mata kuliah yang dialokasikan pada hari tertentu, misalkan Senin.
∑∑ x b∈B c∈C
8.
(7)
1,b ,c , da1
= 1; untuk da1 ∈ D
Ada mata kuliah yang pengajarnya tidak
(8) dapat dijadwalkan pada jam
tertentu, misal jam pertama dan kedua. xa ,b ,c ,daa = 0, untuk a ∈ A; b = 1, 2; c ∈ C ; da a ∈ D 9.
(9)
Ada hari dan waktu tertentu tidak ada perkuliahan di ruang manapun, misal hari Jumat jam ketiga.
∑∑x c∈C d∈D
5 , 3, c , d
=0
(10)
