PEMODELAN OPTIMAL KONSTRUKSI JADWAL PERKULIAHAN DAN IMPLEMENTASINYA
KHAIRUNNISA
SEKOLAH PASCASARJANA INSTITUT PERTANIAN BOGOR BOGOR 2008
PERNYATAAN MENGENAI TESIS DAN SUMBER INFORMASI Dengan ini saya menyatakan bahwa tesis dengan judul Pemodelan Optimal Konstruksi Jadwal Perkuliahan dan Implementasinya adalah karya saya dengan arahan dari komisi pembimbing dan belum diajukan dalam bentuk apapun kepada perguruan tinggi manapun. Sumber informasi yang berasal atau dikutip dari karya yang diterbitkan maupun tidak diterbitkan dari penulis lain telah disebutkan dalam teks dan dicantumkan dalam Daftar Pustaka di bagian akhir tesis ini.
Bogor, Maret 2008
Khairunnisa NIM G551050101
ABSTRACT KHAIRUNNISA. An Optimal Modeling for Constructing University Timetabling and Its Implementation. Under direction of AMRIL AMAN and I GUSTI PUTU PURNABA. The construction of timetable that satisfies all operational rules and needs in an academic institution, while at the same time fulfills as many of the wishes and requirements of the teaching staff and the students is an important but extremely difficult task. Formally, timetable problem is defined as the process of assigning courses to specific time periods and to specific classrooms suitable for the number of the student and the needs of the each course. This paper presents an Integer Programming formulation of the timetable problem. A prototype of this model is implemented using LINGO software and produced timetable that satisfies all constraints. Keywords : timetabling, integer programming, university timetabling,
RINGKASAN KHAIRUNNISA. Pemodelan Optimal Konstruksi Jadwal Perkuliahan dan Implementasinya. Dibimbing oleh AMRIL AMAN dan I GUSTI PUTU PURNABA. Penjadwalan kuliah merupakan kegiatan yang mengawali pergantian semester di setiap perguruan tinggi. Proses ini harus memperhitungkan banyaknya mata kuliah, ketersediaan ruang, dan rentang waktu yang digunakan. Inti dari penjadwalan kuliah adalah menjadwalkan beberapa komponen yang terdiri dari mata kuliah, ruang, dan waktu dengan memperhatikan sejumlah batasan dan syarat tertentu Permasalahan yang dihadapi penjadwal terletak pada lebih banyaknya mata kuliah yang harus dijadwalkan daripada ruang yang tersedia, kesesuaian kebutuhan perkuliahan dengan fasilitas ruangnya, kapasitas ruang yang harus sesuai dengan jumlah mahasiswa, serta keinginan pengajar untuk mengajar pada suatu hari atau jam tertentu. Sejumlah algoritma dikembangkan untuk menyelesaikan masalah ini agar sesuai dengan kebutuhan instansi yang memerlukannya. Masalah penjadwalan kuliah menjadi topik yang dibahas dalam penelitian ini. Penyelesaian yang dicari berupa suatu model matematika yang merepresentasikan masalah penjadwalan kuliah yang sesuai dengan keadaan di Fakultas Ilmu Tarbiyah dan Keguruan (FITK) Universitas Islam Negeri (UIN) Syarif Hidayatullah Jakarta. Model tersebut kemudian diimplementasikan pada suatu kondisi. Untuk membuat penjadwalan kuliah 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. Pengalokasian hari dapat dirancang sesuai keinginan pengajarnya. Misalkan pengajar dapat meminta hari tertentu untuk mengajar mata kuliah atau untuk tidak mengajar mata kuliah. Setiap mata kuliah memerlukan jam untuk perkuliahan. Jam 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. Perkuliahan memerlukan ruang yang fasilitasnya dapat menunjang pelaksanaan kuliah tersebut. Misal mata kuliah Pemprograman Komputer memerlukan ruang yang difasilitasi komputer agar perkuliahan efektif. 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 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 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. Masalah penjadwalan kuliah tersebut disajikan dalam model Integer Programming. Model tersebut mempunyai fungsi obyektif memenuhi semua batasan utama serta memaksimalkan nilai kepuasan penggunaan waktu yang disukai untuk perkuliahan. Model Integer Programming untuk masalah penjadwalan kuliah diselesaikan dengan menggunakan metode branch and bound yang tersedia pada software LINGO 8.0. Nilai kepuasan penggunaan waktu dilambangkan dengan koefisien nilai yang diberikan pada variabel hari dan jam. Waktu yang disukai untuk perkuliahan diberikan koefisien nilai yang tinggi sedangkan pada waktu yang kurang disukai diberikan koefisien nilai yang lebih rendah. Hal ini menyebabkan penjadwalan dengan menggunakan waktu yang disukai untuk perkuliahan memiliki fungsi obyektif yang lebih besar daripada penjadwalan dengan menggunakan waktu yang kurang disukai untuk perkuliahan. Model diimplementasikan pada beberapa skenario. Contoh suatu skenario mempunyai koefisien nilai nol pada jam tertentu di tiap harinya sedangkan skenario lain memiliki koefisien nilai nol pada jam tertentu di tiap harinya dan pada satu hari tertentu. Berdasarkan skenario tersebut dihasilkan dua jadwal yang nilai fungsi obyektifnya berbeda, yaitu skenario pertama lebih besar daripada skenario kedua. Kemudian melalui jadwal yang dihasilkan dapat dipastikan bahwa batasan utama tidak terlanggar walaupun ada perkuliahan yang terjadwal di waktu perkuliahan yang koefisiennya bernilai nol. Berdasarkan hal tersebut dapat disimpulkan bahwa model menghasilkan jadwal bernilai optimal dengan tetap mengakomodasi batasan-batasan serta mata kuliah yang terjadwal pada waktu yang kurang disukai terjadi agar tetap terpenuhi batasan yang ada. Kata kunci : penjadwalan, integer programming, penjadwalan kuliah
© Hak Cipta milik Institut Pertanian Bogor, tahun 2008 Hak cipta dilindungi Undang-undang 1. Dilarang mengutip sebagian atau seluruh karya tulis ini tanpa mencantumkan atau menyebutkan sumber. a. Pengutipan hanya untuk kepentingan pendidikan penelitian, penulisan karya ilmiah, penyusunan laporan, penulisan kritik atau tinjauan suatu masalah b. Pengutipan tidak merugikan kepentingan yang wajar Institut Pertanian Bogor 2. Dilarang mengumumkan dan memperbanyak sebagian atau seluruh karya tulis dalam bentuk apapun tanpa izin Institut Pertanian Bogor
PEMODELAN OPTIMAL KONSTRUKSI JADWAL PERKULIAHAN DAN IMPLEMENTASINYA
KHAIRUNNISA
Tesis sebagai salah satu syarat untuk memperoleh gelar Magister Sains pada Departemen Matematika
SEKOLAH PASCASARJANA INSTITUT PERTANIAN BOGOR BOGOR 2008
Judul Tesis : Pemodelan Optimal Implementasinya Nama : Khairunnisa NIM : G551050101
Konstruksi
Jadwal
Perkuliahan
dan
Disetujui, Komisi Pembimbing
Dr. Ir. Amril Aman, M.Sc. Ketua
Dr. Ir. I Gusti Putu Purnaba, DEA Anggota
Diketahui,
Ketua Program Studi Matematika Terapan
Dekan Sekolah Pascasarjana
Dr. Ir. Endar H.Nugrahani, MS.
Prof. Dr. Ir. Khairil A. Notodipuro, MS
Penguji Luar Komisi pada Ujian Tesis : Ir. N.K. Kutha Ardana, M.Sc.
Tanggal Ujian : 21 Februari 2008
Tanggal Lulus :
Untuk Ibundaku serta saudara-saudaraku T’ Nida, K’ Ihan, T’ Fifi, T’ Huri, K’ Ruham, Anam, T’ Fakhroh, Mas Heri, Mas Hendro, T Septi, dan keponakan-keponakanku Fadli, Hilma, Muthia, Raidha, Haidar, Aisha, Rahiel, dan Syafiq Terima kasih atas dukungan dan kasih sayangnya Semoga Allah memberi berkah dan ridhaNya
PRAKATA Puji dan syukur penulis panjatkan kepada Allah SWT atas segala karuniaNya sehingga karya ilmiah ini berhasil diselesaikan. Shalawat serta salam kepada Nabi Muhammad SAW. Judul yang dipilih pada penelitian yang dilaksanakan sejak Februari 2007 ini adalah Pemodelan Optimal Konstruksi Jadwal Perkuliahan dan Implementasinya Terima kasih penulis sampaikan kepada Dr. Ir. Amril Aman, M.Sc. dan Dr. Ir. I Gusti Putu Purnaba, DEA atas bimbingannya serta Ir. N.K. Kutha Ardhana, M.Sc. selaku penguji atas saran-sarannya. Ucapan terima kasih juga penulis sampaikan kepada seluruh staf pengajar dan staf lainnya di Departemen Matematika IPB. Ungkapan terima kasih juga disampaikan kepada: Yth. Dekan dan Pembantu Dekan Fakultas Ilmu Tarbiyah dan Keguruan UIN Syarif Hidayatullah Jakarta beserta seluruh staf, khususnya rekan-rekan di Jurusan Pendidikan Matematika. Teman-teman penulis di Departemen Matematika IPB, khususnya di SPs IPB, Eva Musyrifah, Yoanita Historiani, Cecep AHFS, Syamsuri dan Jaenudin. Teman serumah di Puri Hapsara (Mbak Diffah UNS, Bu Syahriani dan Bu Sri Purwanti UNHAS, Bu Insun Sangadji UNPATI, Mbak Elly dan Mbak Meisji UNSRI, Mbak Rahmi Univ. Jambi dan Ifa), serta semua pihak yang tak dapat penulis sebutkan satu persatu. Semoga Allah SWT senantiasa memudahkan semua urusan kita. Ytc. Ibunda dan Ayahandaku, Dra. Hj. Rohmah Sarmala dan H. Moch. Chairuddin, BS (Alm) atas segala doa, dukungan dan kasih sayangnya kepada penulis. Kepada kakak-kakakku, adikku, beserta seluruh keponakanku, terima kasih atas segala perhatian, pengertian dan bantuannya sehingga studi S2 ini dapat diselesaikan. Semoga karya ilmiah ini bermanfaat. Bogor, Maret 2008 Khairunnisa
RIWAYAT HIDUP Penulis dilahirkan di Jakarta pada tanggal 4 April 1981 dari ayah H. Moch. Chairuddin, BS dan ibu Dra. Hj. Rohmah Sarmala. Penulis merupakan putri keenam dari tujuh bersaudara. Tahun 1999 penulis lulus dari SMUN 47 Jakarta. Pendidikan sarjana ditempuh di Jurusan Pendidikan Matematika Fakultas Ilmu Tarbiyah dan Keguruan Universitas Islam Negeri Syarif Hidayatullah Jakarta dan menamatkannya pada tahun 2003. Kesempatan untuk melanjutkan ke program Magister pada Program Studi Matematika IPB diperoleh pada tahun 2005. Penulis adalah staf pengajar di Jurusan Pendidikan Matematika FITK UIN Syarif Hidayatullah sejak Agustus 2005. Mata kuliah yang diajarkan adalah Matematika Dasar.
DAFTAR ISI Halaman DAFTAR TABEL .....................................................................................
xii
DAFTAR LAMPIRAN .............................................................................
xiii
PENDAHULUAN ....................................................................................
1
Latar Belakang..................................................................................
1
Tujuan ..............................................................................................
3
Manfaat .............................................................................................
3
TINJAUAN PUSTAKA ............................................................................
4
Penjadwalan Perkuliahan di Beberapa Universitas ..........................
4
Landasan Teori .................................................................................
10
Linear Programmning .............................................................
10
Integer Programmning ............................................................
11
Branch and Bound...................................................................
12
ALUR PENELITIAN ................................................................................
18
PEMODELAN ...........................................................................................
20
Deskripsi Masalah ............................................................................
20
Formulasi Masalah ............................................................................
22
Model ................................................................................................
23
PEMBAHASAN ........................................................................................
25
Implementasi Model .........................................................................
25
Beberapa Skenario ............................................................................
30
SIMPULAN DAN SARAN .......................................................................
35
DAFTAR PUSTAKA ...............................................................................
36
LAMPIRAN...............................................................................................
37
DAFTAR TABEL Halaman Tabel 1 Daftar Mata Kuliah yang Ditawarkan...........................................
25
Tabel 2 Indeks Mata Kuliah.......................................................................
26
Tabel 3 Koefisien Nilai ..............................................................................
26
Tabel 4 Hasil Simulasi ...............................................................................
29
Tabel 5 Beberapa Skenario .......................................................................
30
Tabel 6 Skenario I ......................................................................................
31
Tabel 7 Skenario II.....................................................................................
32
Tabel 8 Skenario III ...................................................................................
33
Tabel 9 Skenario IV ...................................................................................
34
DAFTAR LAMPIRAN Halaman Lampiran 1 Penulisan Program dan Outputnya ........................................
38
Lampiran 2 Output Beberapa Skenario......................................................
42
DAFTAR LAMPIRAN Halaman Lampiran 1 Penulisan Program dan Outputnya ........................................
38
Lampiran 2 Output Beberapa Skenario......................................................
42
PENDAHULUAN Latar Belakang Penjadwalan kuliah merupakan kegiatan yang mengawali pergantian semester di setiap perguruan tinggi. Hal ini dilaksanakan oleh bagian administrasi perguruan tinggi. Petugas administrasi yang membuat jadwal memulainya dengan pengumpulan informasi yang diperlukan seperti: mata kuliah yang ditawarkan, peserta perkuliahan, ruang yang dapat digunakan, nama dosen yang mengajar dan rentang waktu yang diperlukan. Jadwal ini merupakan rancangan aktivitas mahasiswa dan dosen selama satu semester. Penjadwalan kuliah merupakan proses penempatan suatu mata kuliah pada ruang yang sesuai, periode waktu tertentu, dan dosen yang sesuai. Proses ini harus memperhitungkan banyaknya mata kuliah, ketersediaan ruang, dan rentang waktu yang digunakan. Permasalahan yang dihadapi penjadwal terletak pada lebih banyaknya mata kuliah yang harus dijadwalkan daripada ruang yang tersedia, kesesuaian kebutuhan perkuliahan dengan fasilitas ruangnya, kapasitas ruang yang harus sesuai dengan jumlah mahasiswa, serta keinginan pengajar untuk mengajar pada suatu hari atau jam tertentu. Masalah lainnya tergantung pada kebutuhan perguruan tinggi tersebut. Sebagian petugas membuat jadwal kuliah secara manual dan sebagian lain secara otomatis. Petugas yang membuat secara manual menggunakan lembar draft penjadwalan untuk diisi dengan alat tulis dan kemudian menggunakan komputer untuk kerapihan hasilnya saja. Sedangkan petugas yang membuat jadwal secara otomatis menggunakan komputer untuk membantu menghasilkan jadwal selain untuk kerapihan hasilnya. Pembuatan jadwal kuliah secara manual menghasilkan jadwal kuliah yang sesuai dengan keinginan banyak pihak seperti jurusan, fakultas, mahasiswa dan dosen, karena penyusunan jadwal mempertimbangkan keinginan mereka. Namun cara tersebut memerlukan waktu yang lama. Penjadwal membutuhkan waktu kurang dari satu minggu bahkan lebih untuk membuat jadwal, kemudian merevisinya kembali agar sesuai dengan keinginan banyak pihak. Lembar
2
penjadwalan pun banyak mengalami perubahan, sehingga harus dibuat berulangkali agar mengakomodasi semua perubahan. Pembuatan jadwal kuliah secara otomatis dapat juga menghasilkan jadwal sebaik buatan manual. Hal ini tergantung pada batasan yang diterapkan dalam software komputer tersebut. Batasan yang digunakan bisa bermacam-macam bentuk sesuai dengan kebutuhannya. Misal, ada batasan yang mengasumsikan jadwal yang memuat semua mata kuliah teralokasikan pada suatu ruang, dan waktu tertentu saja tanpa mempertimbangkan kesediaan waktu dosen. Ada juga batasan yang memperhitungkan kesesuaian fasilitas ruang dengan keperluan kuliah. Penjadwalan dengan banyak batasan membutuhkan waktu pembuatan yang lebih lama dibandingkan dengan yang memuat sedikit batasan. Penjadwalan kuliah secara manual masih dilakukan di Fakultas Ilmu Tarbiyah dan Keguruan (FITK) Universitas Islam Negeri (UIN) Syarif Hidayatullah Jakarta. Fakultas ini terdiri dari delapan jurusan dan sepuluh program studi. Jurusan memiliki staf administrasi yang membuat jadwal secara manual
tiap
semester.
Setelah
itu
Fakultas
mengadakan
rapat
untuk
menyosialisasikan jadwal. Melalui rapat tersebut akan diketahui beban satuan kredit semester (sks) dosen dan ruang-ruang yang digunakan. Setiap dosen hanya mengajar sesuai banyaknya sks yang diberikan. Selanjutnya apabila terdapat suatu ruang digunakan untuk dua kuliah pada waktu yang sama maka jadwal diperbaiki. Jadwal perbaikan ini akan dirapatkan kembali pada minggu berikutnya dan seterusnya sampai tidak ada lagi perbaikan jadwal. Pembuatan jadwal di FITK memerlukan waktu berminggu-minggu. Penyusunan jadwal secara manual di FITK memboroskan waktu, tenaga dan biaya. Penyebabnya memerlukan waktu yang lama, dilaksanakan oleh delapan orang yang berbeda dan juga harus dirapatkan berulang kali. Penjadwalan kuliah secara otomatis perlu dikembangkan di FITK. Masalah penjadwalan kuliah menjadi topik yang dibahas dalam penelitian ini.
Pemecahan
yang
dicari
berupa
suatu
model
matematika
yang
merepresentasikan masalah penjadwalan kuliah agar sesuai dengan keadaan di FITK. Melalui model matematika tersebut masalah penjadwalan dapat diselesaikan secara matematis dengan bantuan perhitungan komputer.
3
Tujuan 1. Membangun model optimasi untuk masalah penjadwalan kuliah di Fakultas Ilmu Tarbiyah dan Keguruan. 2. Mengimplementasikan model untuk beberapa kondisi. Manfaat Kegunaan model matematika dari masalah penjadwalan kuliah dapat membantu penjadwal untuk menghasilkan jadwal secara otomatis namun tetap sebaik buatan manual. Penerapan model matematika dalam masalah penjadwalan kuliah yang penyelesaiannya didapat dari perhitungan komputer dapat menghemat waktu dan biaya yang dikeluarkan untuk membuat jadwal secara manual.
TINJAUAN PUSTAKA Penjadwalan Kuliah di Beberapa Universitas Masalah penjadwalan kuliah merupakan masalah yang sangat kompleks yang intinya adalah bagaimana menjadwalkan beberapa komponen yang terdiri dari mahasiswa, dosen, ruang, dan waktu dengan memperhatikan sejumlah batasan dan syarat (constraint) tertentu (Anbulagan & Winata 2001). Sejumlah algoritma dikembangkan untuk menyelesaikan masalah ini sesuai dengan kebutuhan
instansi yang memerlukannya. Keanekaragaman ini tidak
terlepas dari kenyataan bahwa setiap perguruan tinggi memiliki sejumlah komponen dan kendalanya sendiri dalam menyusun jadwal kuliah (Anbulagan & Setiadi 2001). Beberapa survey menyajikan tipe-tipe yang berbeda dari masalah penjadwalan dan strategi utama untuk menyelesaikan masalah tersebut. Pada kasus-kasus yang jadwalnya harus memenuhi banyak persyaratan mendapatkan kesulitan terbesar dalam menghasilkan penyelesaian yang feasible pada proses optimasi (Papoutsis et al 2003). Terdapat banyak perbedaan bentuk dalam masalah penjadwalan. Beberapa tulisan menunjukkan cara memformulasikan masalah penjadwalan ke dalam bentuk mathematical programming problem sementara lainnya mengusulkan pendekatan heuristik untuk mendapatkan pemecahan yang sesuai (Fizzano & Swanson 2000). Carter dan Tovey (1992) memformulasikan masalah penjadwalan sebagai bentuk Binary Integer Programming (BIP) bernilai nol dan satu (0-1) dengan tujuan feasibility, satisfice dan optimize. Dari tiga tujuan tersebut, satisfice merupakan yang paling dekat dengan penerapan masalah penjadwalan. Penjadwal manual lebih memikirkan untuk menghasilkan jadwal perkuliahan yang acceptable. Masalah penjadwalan kuliah ini juga menjadi bahan kajian oleh Glassey dan Mizrach (1986) pada University of California (UC) di Berkeley. Masalah tersebut dimodelkan menjadi BIP 0-1. Variabel yang digunakan dikaitkan dengan keputusan jika suatu mata kuliah dialokasikan ke suatu ruang maka bernilai satu, selain itu bernilai nol.
5
Permasalahan yang dihadapi berupa mengalokasikan semua mata kuliah yang ditawarkan dengan memenuhi batasan yang ada. Batasan tersebut berupa setiap mata kuliah teralokasi pada satu ruang saja dan ruang yang digunakan untuk suatu mata kuliah tidaklah dapat dipergunakan lagi untuk mata kuliah lain. Fungsi obyektif dari pemodelan ini memiliki koefisien yang berkorelasi dengan jarak, fasilitas ruang dan kapasitas ruang. Semua mata kuliah memiliki nilai koefisien tertentu jika dialokasikan ke suatu ruang. Misal mata kuliah yang dialokasikan pada ruang yang gedungnya berbeda dari gedung asal mata kuliah akan memiliki nilai koefisien atau biaya yang besar. Maka dari itu fungsi obyektif dari pemodelan ini berupa meminimumkan biaya pengalokasian mata kuliah ke suatu ruang. Pemodelan BIP ini diselesaikan dengan suatu algoritma heuristik yang dijalankan pada program Fortran. Masalah yang dikemukakan pada UC belum mengakomodasi keinginan pengajar untuk mengajar di waktu yang mereka harapkan. Ng dan Martin (2002) memodelkan penjadwalan kuliah yang diasumsikan dapat memenuhi keinginan pengajar tersebut. Kajian ini dilakukan di Universitas Minnesota-Morris (UMM). Permasalahan yang dihadapi di UMM secara umum berupa jadwal yang dibuat dapat memenuhi permintaan kebanyakan penggunanya. Seperti waktu perkuliahan sesuai dengan waktu kesediaan pengajarnya. Perkuliahan yang menggunakan komputer haruslah di ruang yang difasilitasi komputer. Beberapa mata kuliah perlu dijadwalkan lebih dari satu periode tiap minggu. Ada ruang berkapasitas terbatas, jika peserta perkuliahan melebihi kapasitas ruang maka mata kuliah itu tidak dapat dialokasikan pada ruang tersebut. Setiap mata kuliah harus dialokasikan ke tepat suatu ruang pada periode waktu tertentu. Paling banyak satu mata kuliah dialokasikan ke suatu ruang pada setiap waktu. Ada mata kuliah yang tidak dapat diselenggarakan pada periode waktu tertentu karena peserta perkuliahannya diprioritaskan mengikuti mata kuliah lain. Beberapa mata kuliah tidak dapat dijadwalkan berurutan. Beberapa mata kuliah tingkat awal harus dijadwalkan pada waktu tertentu. Pemecahan yang dicari berupa semua mata kuliah yang ditawarkan terjadwal di suatu ruang pada periode waktu tertentu dengan memenuhi beberapa batasan. Agar masalah tersebut didapat pemecahannya maka penjadwalan kuliah
6
dibagi dalam dua tahap. Tahap pertama semua mata kuliah dialokasikan ke suatu ruang pada waktu tertentu. Tahap kedua menyesuaikan waktu perkuliahan dengan waktu kesediaan pengajar. Misalkan: K = Himpunan semua mata kuliah yang ditawarkan W = Himpunan semua periode waktu perkuliahan R = Himpunan semua ruang perkuliahan yang digunakan P = Himpunan semua pengajar mata kuliah Berikut ini cara menyelesaikan masalah penjadwalan kuliah di UMM: Tahap pertama Misalkan αw,k,r, dengan w ∈ W, w = 1, ...,a; k ∈ K, k = 1, ...,b; r ∈ R, r = 1, ..., c merupakan variabel keputusan bernilai biner sebagai berikut: mata kuliah k dialokasikan pada waktu w di ruang r α w,k ,r = { 10,, jika selainnya
Fungsi obyektif penjadwalan kuliah di UMM dapat dimodelkan sebagai berikut: Maksimumkan z =
∑ ∑∑α
w∈W k∈K r∈R
w, k , r
(1)
Model ini berbeda dengan yang digunakan pada UC. Fungsi obyektif di UC berupa meminimumkan biaya pengalokasian mata kuliah k ke ruang r. Sedangkan pada UMM berupa memaksimumkan pengalokasian mata kuliah k pada waktu w di ruang r, yang nilainya sama dengan jumlah mata kuliah yang akan dijadwalkan. Misalkan nilai k sama dengan 1 s.d. 20 maka nilai fungsi obyektifnya 20. Selain itu terdapat juga perbedaan dari variabel keputusannya. Pada UC variabel keputusannya hanya menyertakan mata kuliah dan ruang. Sedangkan pada UMM variabel keputusannya juga menyertakan waktu. Batasan yang digunakan di UMM sebagai berikut: 1. Perkuliahan yang menggunakan komputer haruslah dijadwalkan di ruang yang difasilitasi dengan komputer. Misal ruang yang difasilitasi dengan komputer diberi indeks 1 dan mata kuliah yang menggunakan komputer berindeks 1 – 7, maka modelnya sebagai berikut:
∑α
w∈W
w, k ,1
= 1, untuk k = 1,...,7
(2)
7
2. Perkuliahan yang berangkai harus dialokasikan pada waktu yang berbeda. Misal mata kuliah yang berangkai berindeks 8 – 11, maka modelnya sebagai berikut: 11
∑α k =8
w,k ,r
≤ 1, untuk w ∈ W ; r ∈ R
(3)
3. Setiap mata kuliah dialokasikan tepat ke satu ruang pada waktu tertentu. Sehingga tidak ada mata kuliah yang dijadwalkan pada dua ruang yang berbeda. Hal ini bertujuan mencegah pengalokasian ganda atau lebih suatu mata kuliah pada suatu ruang dan waktu yang berbeda. Modelnya sebagai berikut:
∑∑α
w∈W r∈R
w,k ,r
= 1, untuk k ∈ K
(4)
4. Paling banyak satu mata kuliah yang dialokasikan pada satu ruang di setiap waktu. Hal ini bertujuan mencegah penggunaan ganda atau lebih dari suatu ruang pada waktu yang sama dengan mata kuliah berbeda (overlapping ruang).
∑α
k∈K
w, k ,r
≤ 1, untuk w ∈W ; r ∈ R
(5)
5. Beberapa mata kuliah tidak dapat dijadwalkan pada waktu tertentu. Batasan ini tidak ada pada UC. Misal mata kuliah berindeks 9 – 13 tidak dapat dijadwalkan pada waktu berindeks 3 – 10.
∑α r∈R
w,k ,r
= 0, untuk w = 3, ..., 10; k = 9, ..., 13
(6)
6. Ada mata kuliah yang tidak boleh dijadwalkan dengan waktu berurutan. Batasan ini tidak ada pada UC. Misal mata kuliah berindeks 11 dan 15 tidak boleh dijadwalkan berurutan. Modelnya sebagai berikut:
∑ (α r∈R
w,11,r
+ α w+1,12,r ) ≤ 1, untuk w = 1, ..., (a − 1)
(7)
7. Beberapa mata kuliah tingkat awal tidak dapat dijadwalkan pada waktu tertentu. Batasan ini juga tidak ada di UC. Misalkan mata kuliah tingkat awal berindeks 6 – 9 tidak boleh dijadwalkan pada waktu yang berindeks 8 – 12. Berikut ini modelnya: 12
∑∑α w=8 k∈K
w, k ,r
= 1, untuk k = 6, ..., 9
(8)
8
Kemudian model tersebut dicari penyelesaiannya yang memenuhi semua batasan yang ada (feasible). Adanya batasan seperti setiap mata kuliah dialokasikan ke tepat satu ruang pada tiap periode waktu mengakibatkan nilai optimalnya sebesar b. Semakin banyak batasan semakin besar kemungkinan model tersebut tidak memiliki penyelesaian yang feasible. Namun masalah penjadwalan pada UMM mendapatkan solusi feasible. Tahap kedua
Tahap ini memodelkan cara mengalokasikan pengajar ke suatu mata kuliah pada waktu tertentu di suatu ruang. Para pengajar ini lebih mengutamakan kesediaan mereka mengajar suatu mata kuliah terpenuhi dibandingkan dengan memenuhi kesediaan waktu mengajar. Model yang dibuat mengakomodasi hal tersebut. Model tahap pertama menghasilkan himpunan solusi feasible. Himpunan tersebut didefinisikan sebagai berikut: A = {{w,k,r}:αw,k,r = 1}, dari model waktu – mata kuliah – ruang
(9)
Misalkan a = {w,k,r} dengan waktu w, mata kuliah k, dan ruang r ke pengajar p memiliki koefisien berikut:
χ p ,a
⎧10, ⎪ 5, ⎪ =⎨ ⎪ 1, ⎪⎩ 0,
jika mata kuliah k dan waktu w sesuai permintaan p jika mata kuliah k sesuai namun waktu w tidak sesuai permintaan p jika mata kuliah k tidak sesuai tapi waktu w sesuai permintaan p jika mata kuliah k maupun waktu w tidak sesuai permintaan p
dengan β merupakan variabel keputusan bernilai biner, ⎧1, ⎩0,
β p ,a = ⎨
Jika p mengajar mata kuliah k pada waktu t Selainnya
Fungsi obyektif pengalokasian pengajar di UMM dimodelkan sebagai berikut: Maksimumkan
∑∑ χ a∈ A p∈P
p ,a
β p ,a
(10)
Untuk setiap pengajar p = 1, …,d dan tiap a Є A memiliki batasan sebagai berikut:
9
1.
Setiap pengajar dapat mengajar paling banyak satu mata kuliah pada tiap periode waktu.
∑β
p ,a a∈ A:a ={k , w, r }
2.
≤ 1, untuk p ∈ P
(11)
Setiap pengajar ditugaskan paling sedikit dua dan paling banyak tiga mata kuliah.
∑β
≤ 3, untuk p ∈ P
(12)
∑β
≥ 2, untuk p ∈ P
(13)
p ,a a∈A:a ={k ,w,r } p,a a∈ A:a ={k , w, r }
3.
Setiap mata kuliah diajar oleh satu dan hanya satu pengajar.
∑β p∈P
4.
p,a
= 1, untuk a ∈ A
(14)
Ada pengajar tertentu yang tidak boleh mengajar suatu mata kuliah. Misal pengajar berindeks 3 tidak boleh mengajar mata kuliah berindeks 8.
β 3,a = 0, untuk a ∈ A dan a = {w,8, r} 5.
(15)
Salah satu dari tiga pengajar mata kuliah yang sama harus mengajar mata kuliah tertentu. Misalkan tiga pengajar tersebut secara berurutan berindeks 4, 6, 7 dan mata kuliah yang dimaksud berindeks 14.
β 4,a + β 6,a + β 7,a = 1, untuk a ∈ A dan a = {w,14, r}
(16)
Model tahap satu dan dua diselesaikan dengan menggunakan metode branch-andbound. Tujuan dari tahap pertama berupa memaksimalkan fungsi obyektif yang memenuhi batasan yang ada. Karena variabel keputusannya bernilai biner 0-1, maka nilai maksimalnya adalah jumlah mata kuliah yang dijadwalkan. Sedangkan pada tahap kedua fungsi obyektifnya mengandung koefisien yang merefleksikan kesukaan waktu mengajar. Jika mata kuliah pada suatu ruang dialokasikan pada waktu yang sama dengan kesediaan waktu pengajarnya, maka nilai koefisien paling tinggi. Kemudian nilai koefisien terendah apabila baik mata kuliah dan waktu tidak sesuai dengan keinginan pengajarnya. Permasalahan ini dimodelkan dalam Integer Programming dan diselesaikan dengan software CPLEX (simplex algorithm written in the C language). Model penjadwalan kuliah di UMM memperoleh solusi optimal dan feasible yang memuaskan orang-orang yang terlibat. Memang tidak semua pengajar
10
mendapatkan waktu kesediaan mengajar yang sesuai dengan keinginan. Hal ini karena mata kuliah terlebih dahulu dialokasikan ke suatu ruang dan waktu tertentu. Sehingga waktu perkuliahan telah ditentukan baru kemudian memecahkan masalah pengalokasian pengajar ke mata kuliah yang sesuai dengan permintaan. Integer programming juga digunakan pada studi kasus yang dilakukan Daskalaki dan Birbas (2004). Pemodelan yang dibuat menggunakan enam parameter, yaitu: hari; periode waktu; kelompok peserta; pengajar; mata kuliah dan ruang kelas. Berdasarkan enam parameter tersebut dibentuk dua himpunan variabel biner yang berbeda. Pertama himpunan variabel dasar. Variabel ini bernilai satu apabila mata kuliah disampaikan pengajar kepada kelompok peserta dijadwalkan pada periode waktu pada hari tertentu di suatu ruang, maka selain itu bernilai nol. Kedua himpunan variabel tambahan. Variabel ini bernilai satu apabila mata kuliah yang membutuhkan sesi tertentu dengan periode yang berurutan disampaikan pengajar kepada kelompok peserta dijadwalkan pada periode waktu pada hari tertentu di suatu ruang, maka selain itu bernilai nol. Pada fungsi obyektif terdapat koefisien yang nilainya paling besar pada periode waktu yang kurang disukai dan paling kecil pada periode waktu yang paling digemari (prime time). Tujuan pemodelan berupa meminimumkan fungsi obyektif. Penyelesaian model ini menggunakan The Mixed Integer Programming (MIP) solver dengan software CPLEX 5.1. Landasan Teori
Untuk membuat model dari masalah penjadwalan diperlukan beberapa pemahaman teori seperti linear programming (LP), integer linear programming, dan metode branch and bound untuk menyelesaikan masalah integer programming (IP). Berikut ini ulasan teori tersebut: Linear Programming
Model LP menyajikan bentuk matematika dari fungsi obyektif, dan pembatasnya berupa fungsi linier. Pada tulisan ini, suatu LP memiliki bentuk standar berikut (Wagner 1985):
11
n
Maksimumkan z = ∑ c j x j
(17)
j =1
n
∑a x
terhadap
≤ bi
i = 1,2,..., m
(18)
xj ≥ 0
j = 1,2,..., n
(19)
ij
j =1
j
n
atau Minimumkan z = ∑ c j x j
(20)
j =1
n
∑a x
terhadap
j =1
ij
= bi
j
xj ≥ 0
i = 1,2,..., m (bi ≥ 0)
(21)
j = 1,2,..., n
(22)
dengan cj, aij dan bi merupakan konstanta yang nilainya diketahui. Model penjadwalan kuliah dapat diekspresikan sebagai sebuah LP. Dengan memisalkan xij sebagai variabel yang mewakili mata kuliah i dialokasikan ke ruang j. Kemudian cij diasumsikan sebagai biaya yang harus dikeluarkan jika mata kuliah i dialokasikan ke ruang j. Setiap mata kuliah yang dijadwalkan pada suatu ruang paling banyak satu kali. Maka modelnya sebagai berikut: p
q
z = ∑∑ cij xij
Minimumkan
(23)
i =1 j =1 q
∑x
terhadap
ij
j =1
≤1
i = 1,2,..., p
(24)
Suatu mata kuliah yang akan dijadwalkan ke suatu ruang hanya memiliki dua keputusan, yaitu dijadwalkan atau tidak dijadwalkan. Sehingga xij merupakan variabel keputusan bernilai biner nol dan satu. Jika suatu mata kuliah i dijadwalkan pada suatu ruang j maka xij bernilai satu, selain itu bernilai nol. Integer Programming
Secara sederhana model LP dengan pembatas tambahan berupa variabelnya bernilai integer disebut sebagai model Integer Programming (IP). Pada tulisan ini, suatu IP memiliki bentuk standar berikut: n
Optimumkan z = ∑ c j x j
(25)
j =1
terhadap
n
∑a x j =1
ij
≤ bi
i = 1,2,..., m
(26)
xj ≥ 0
j = 1,2,..., n
(27)
j = 1,2,..., p (≤ n)
(28)
j
xj bernilai integer
12
dengan cj, aij dan bi merupakan konstanta yang nilainya diketahui (Taha 1975). Pada penjadwalan akan diputuskan suatu mata kuliah akan dijadwalkan atau tidak pada suatu ruang. Sehingga xij pada persamaan 23 tidaklah bernilai pecahan. Variabel keputusan harus bernilai diskret sehinga dapat dikelaskan sebagai IP. Suatu masalah IP yang variabelnya hanya memiliki dua nilai saja, misalnya nol dan satu disebut BIP (Wolsey 1998). Algoritma Branch and Bound
Masalah integer programming dapat dipecahkan dengan metode branch and bound. Konsep dasar branch and bound berupa teknik untuk membagi daerah feasible menjadi cabang-cabang subproblem dan mengukurnya (Hillier 1990). Setiap subproblem diukur dengan tiga cara berikut: T (1) Bound dari subproblem ≤ solusi optimum yang didapat saat ini (z*) T (2) LP-relaksasi tidak memiliki solusi feasible. T (3) Solusi optimal dari LP-relaksasi berupa integer. Jika solusi ini lebih baik dari solusi optimum yang didapat sebelumnya maka solusi ini menjadi solusi optimum yang baru dan cara pertama digunakan kembali untuk semua subproblem dengan nilai z* baru yang lebih besar. Langkah-langkah metode branch and bound dalam menyelesaikan masalah BIP sebagai berikut: Langkah 0 Atur nilai optimum ( z*) = - ∞, karena nilai optimumnya belum diketahui. Langkah 1 Membagi dan membatasi 1. Membagi masalah BIP menjadi dua subproblem dengan nilai salah satu variabelnya nol dan yang lainnya satu 2. Membuat LP-relaksasi dari BIP dengan cara menghilangkan kendala integer atau kendala 0-1 pada setiap variabelnya 3. Menggunakan metode simpleks untuk mendapatkan solusi optimal 4. Solusi optimal (z) yang didapat dibulatkan ke bawah dan menjadi batas (bound) untuk semua subproblem 5. Menentukan bound (z) dari kedua subproblem
13
Langkah 2 Mengukur subproblem yang ada. 1. Jika subproblem terukur maka percabangan pada subproblem
ini
dihentikan. Kemudian jika mempunyai nilai z maka nilai z-nya menjadi kandidat solusi optimum (z*) 2. Jika subproblem terukur menghasilkan nilai z ≤ z* maka percabangan pada subproblem ini dihentikan. 3. Jika subproblem tidak terukur (subproblem yang tersisa) maka dibuat lagi percabangan pada subproblem ini, seperti pada langkah 1 4. Jika tidak ada subproblem yang tersisa maka percabangan dihentikan Langkah 3 Tes keoptimalan 1. Tidak ada subproblem yang tersisa 2. Menjadikan kandidat solusi optimum dengan nilai z terbesar sebagai solusi optimum atau masalah BIP tersebut tidak memiliki solusi feasible. Berikut ini contoh untuk memudahkan pemahaman tentang metode branch and bound: Contoh 1:
Misalkan diberikan BIP sebagai berikut: Maksimumkan terhadap
z = 9 x1 + 5 x2 + 6 x3 + 4 x4 , 6 x1 + 3x2 + 5 x3 + 2 x4 ≤ 10 x3 + x4 ≤ 1 − x1 + x3 ≤ 0 − x2 + x4 ≤ 0 xj ≤1
(29) (30) (31) (32) (33) (34)
xj ≥ 0
(35)
x j merupakan integer
untuk j = 1,2,3,4
(36)
Masalah BIP dibagi menjadi dua subproblem sebagai berikut: Subproblem 1: (x1 = 0 ) terhadap
z = 5 x2 + 6 x3 + 4 x4 , 3x2 + 5 x3 + 2 x4 ≤ 10 x3 + x4 ≤ 1 x3 ≤ 0
(38) (39) (40) (41)
14
x j merupakan integer
− x2 + x4 ≤ 0 xj ≤1
(42) (43)
xj ≥ 0
(44)
untuk j = 2,3,4
(45)
Subproblem 2: (x1 = 1) terhadap
z = 9 + 5 x2 + 6 x3 + 4 x4 , 3x2 + 5 x3 + 2 x4 ≤ 4 x3 + x4 ≤ 1 x3 ≤ 1 − x2 + x4 ≤ 0 xj ≤1
(46) (47) (48) (49) (50) (51)
xj ≥ 0
(52)
x j merupakan integer
untuk j = 2,3,4
(53)
Batasan baru x1 = 0 dan x1 = 1 tidak dapat dipenuhi secara bersamaan. Kedua subproblem harus ditangani sebagai dua BIP yang berbeda. Kemudian setiap subproblem diberikan batas (bound) yang merupakan solusi feasible terbaik. Batas ini didapat dengan menghilangkan (relaxing) satu himpunan pembatas (constraint) yang menyebabkan masalah sulit diselesaikan, misalkan menghilangkan baris terakhir dari subproblem 2 (persamaan 53). Selanjutnya untuk menyelesaikan LP-relaksasi ini secara cepat digunakan 5 metode simpleks sehingga didapat solusi optimal, ( x1 , x2 , x3 , x4 ) = ( ,1,0,1) 6 1 1 dengan z = 16 . Maka z ≤ 16 untuk semua solusi feasible dari masalah BIP 2 2 1 awal. Kemudian bound 16 dibulatkan menjadi 16. Karena semua koefisien dari 2
fungsi obyektif berupa integer maka semua solusinya memiliki z bernilai integer. Kemudian kedua subproblem diberikan bound dengan cara yang sama. LP-relaksasi subproblem 1: ( x1 , x2 , x3 , x4 ) = (0,1,0,1) dengan z = 9 4 1 LP-relaksasi subproblem 2: ( x1 , x2 , x3 , x4 ) = (1, ,0,1) dengan z = 16 5 5
Bound untuk subproblem 1: z ≤ 9 Bound untuk subproblem 2: z ≤ 16
15
Subproblem 1 menghasikan solusi integer dengan z ≤ 9 , maka terukur (T(3)) dengan 9 merupakan kandidat solusi optimal. Sedangkan subproblem 2 tersisa sehingga perlu dilakukan percabangan kembali sebagai berikut: Iterasi kedua Subproblem 3: ( x1 = 1, x2 = 0 ) z = 9 + 6 x3 + 4 x4 , 5 x3 + 2 x4 ≤ 4
terhadap
x3 + x4 ≤ 1 x3 ≤ 1 x4 ≤ 0
xj ≤1 xj ≥ 0 x j merupakan integer
untuk j = 3,4
(54) (55) (56) (57) (58) (59) (60) (61)
Subproblem 4: ( x1 = 1, x2 = 1) z = 14 + 6 x3 + 4 x4 , 5 x3 + 2 x4 ≤ 1
terhadap
x3 + x4 ≤ 1 x3 ≤ 1 x4 ≤ 1
xj ≤1 xj ≥ 0 xj
merupakan integer
untuk j = 3,4
(62) (63) (64) (65) (66) (67) (68) (69)
LP-relaksasi dari kedua subproblem didapat dengan menghilangkan baris terakhir dari pembatas. 4 4 LP-relaksasi subproblem 3: ( x1 , x2 , x3 , x4 ) = (1,0, ,0) dengan z = 13 5 5 1 LP-relaksasi subproblem 4: ( x1 , x2 , x3 , x4 ) = (1,1,0, ) dengan z = 16 2
Bound untuk subproblem 3: z ≤ 13 Bound untuk subproblem 4: z ≤ 16
16
Subproblem yang tersisa berdasarkan hasil pengukuran adalah subproblem 3 dan 4. Karena bound dari subproblem 4 lebih besar daripada subproblem 3, maka percabangan dibuat di subproblem 4. Namun subproblem 3 dikategorikan subproblem yang tersisa. Iterasi ketiga Subproblem 5: (x1 = 1, x2 = 1, x3 = 0) z = 14 + 4 x4 , 2 x4 ≤ 1
terhadap
x4 ≤ 1 x4 ≤ 0
xj ≤1 xj ≥ 0 x j merupakan integer
untuk j = 4
(70) (71) (72) (73) (74) (75) (76)
Subproblem 6: (x1 = 1, x2 = 1, x3 = 1) terhadap
z = 20 + 4 x4 , 2 x4 ≤ − 4 x4 ≤ 0 x4 ≤ 1
xj ≤1 xj ≥ 0
(77) (78) (79) (80) (81)
(82) x j merupakan integer untuk j = 4 (83) LP-relaksasi dari kedua subproblem didapat juga dengan menghilangkan baris terakhir dari pembatas. 1 LP-relaksasi subproblem 5: ( x1 , x2 , x3 , x4 ) = (1,1,0, ) dengan z = 16 2
LP-relaksasi subproblem 6: Tidak ada solusi feasible Bound untuk subprolem 5: z ≤ 16 Berdasarkan hasil pengukuran subproblem yang tersisa adalah subproblem 5 dan variabel percabangannya hanya x4 .
17
Iterasi keempat x4 = 0 : ( x1 , x2 , x3 , x4 ) = (1,1,0,0) dengan z = 14 x4 = 1 : ( x1 , x2 , x3 , x4 ) = (1,1,0,1), tidak ada solusi feasible Kedua solusi tersebut terukur. Kandidat solusi optimal yang didapat sekarang lebih besar daripada kandidat sebelumnya (14 > 9), sehingga kandidatnya solusi optimal yang sekarang adalah ( x1 , x2 , x3 , x4 ) = (1,1,0,0)
dengan z = 14 . Subproblem 3 masih tersisa. Perlu diukur kembali dengan solusi terbaik yang baru. Bound subproblem 3 = 13 ≤14. Maka subproblem 3 terukur. Jadi solusi optimal untuk BIP (3) adalah ( x1 , x2 , x3 , x4 ) = (1,1,0,0)
Gambar 1 Metode branch and bound untuk menentukan solusi IP.
Pada Gambar 1, percabangan dengan memilih x1 = 1, x2 = 1, x3 = 0, x1 = 0 menghasilkan solusi optimum integer terbaik yaitu z = 14.
ALUR PENELITIAN Penelitian ini dibagi menjadi empat tahap, yaitu: i) pendeskripsian dan formulasi masalah, ii) pemodelan, iii) solusi model, dan iv) implementasi model. Pendeskripsian dan Formulasi Masalah Tahap pertama dalam pemodelan berupa menentukan tujuan penjadwalan perkuliahan.
Secara
umum
masalah
penjadwalan
perkuliahan
berupa
mengalokasikan suatu mata kuliah dengan seorang pengajar yang mengajar mahasiswa pada ruang yang sesuai dengan kebutuhan perkuliahan ke suatu periode waktu tertentu di salah satu hari dalam seminggu. Karena belum dapat diketahui maka masalah inilah menjadi variabel keputusan yang hendak ditentukan nilainya. Dalam penjadwalan perkuliahan variabel tersebut akan dibatasi oleh beberapa hal. Batasan tersebut terbagi dua, yaitu batasan yang tidak boleh dilanggar (hard constraint) dan batasan untuk memberi nilai lebih dari suatu jadwal (soft constraint). Pemodelan Setelah
tahap
memformulasikan
masalah,
selanjutnya
adalah
merepresentasikan masalah tersebut ke dalam model matematika. Melalui model ini masalah dideskripsikan sebagai suatu sistem persamaan atau pertidaksamaan dan ekspresi matematika lain. Masalah penjadwalan dapat dimodelkan sebagai model Linear Programming (LP) atau Integer Programming (IP). Solusi model Model matematika yang sangat sederhana dapat diselesaikan dengan secarik kertas dan pena. Namun model matematika untuk menyelesaikan masalah nyata membutuhkan kinerja komputer. Untuk mendapatkan solusi model penjadwalan digunakan software LINGO 8.0 dengan pendekatan branch and bound. Kemudian solusi yang diperoleh merupakan solusi yang paling banyak mengakomodasi semua batasan dan memaksimumkan fungsi tujuan.
19
Implementasi Model Implementasi model dilakukan dengan cara menyimulasikan model dengan data mata kuliah semester I Jurusan Pendidikan Matematika FITK . Kemudian mengubah nilai pada koefisien fungsi obyektifnya dengan nilai yang berbeda untuk melihat konsistensi model dalam mengakomodasi semua batasan dan fungsi obyektifnya tetap bernilai optimal.
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)
PEMBAHASAN Implementasi Model Implementasi model yang telah diperoleh dilakukan dengan cara simulasi model. Simulasi tersebut menggunakan data mata kuliah yang ditawarkan pada semester I jurusan Pendidikan Matematika yang terdiri dari dua kelas sebagai berikut: Tabel 1 Daftar Mata Kuliah yang Ditawarkan No 1. 2. 3. 4. 5. 6. 7. 8. 9. 10.
Mata Kuliah SKS Pengajar Bahasa Arab I 2 Siti Maryam Bahasa Inggris I 2 Hapsari Filsafat Umum 2 Moh. Dahlan Fiqh 2 Rusydi Jamil Ilmu Sosial Dasar 2 Ulfa Fajarini Pendidikan Kewargaan 2 Wahdi Sayuti Penguatan Komputer 2 Anwar Syaddad Biologi Umum 3 Zulfiani Fisika Dasar 3 Erina Hertanti Matematika Dasar 3 Anwar Syaddad
Ruang R_1 atau R_2 R_1 atau R_2 R_1 atau R_2 R_1 atau R_2 R_1 atau R_2 R_1 atau R_2 Lab. Komputer R_1 atau R_2 R_1 atau R_2 R_1 atau R_2
Jadwal yang diharapkan berupa: 1.
Semua mata kuliah terjadwal di suatu ruang pada suatu hari dan suatu jam.
2.
Semua mata kuliah terjadwal di ruang yang sesuai dengan kualifikasinya.
3.
Tidak terjadi penggunaan ruang, hari dan jam yang sama untuk lebih dari satu mata kuliah yang berbeda.
4.
Tidak terjadi satu peserta mengikuti lebih dari satu mata kuliah yang berbeda pada hari dan jam yang sama.
5.
Tidak terjadi satu pengajar mengajar lebih dari satu mata kuliah yang berbeda pada hari dan jam yang sama.
6.
Mata kuliah Bahasa Arab dialokasikan pada hari Senin.
7.
Mata kuliah Bahasa Inggris tidak dapat dialokasikan pada jam pertama sampai dengan jam ketiga.
8.
Selain pengajar Biologi Umum dan Bahasa Inggris, semua pengajar menginginkan hari yang sama untuk mata kuliah yang sama dengan jam yang berurutan.
26
Langkah berikutnya penentuan indeks hari, jam, ruang dan mata kuliah. Hari berindeks 1, 2, 3, 4 dan 5 untuk hari Senin sampai dengan Jumat. Jam berindeks 1, 2, 3, 4 dan 5 untuk jam pertama sampai dengan jam kelima. Ruang R_1(regular satu) berindeks 1, R_2 berindeks 2 dan Laboratorium Komputer berindeks 3. Sedangkan untuk indeks mata kuliah sebagai berikut: Tabel 2 Indeks mata kuliah Indeks
Mata Kuliah
SKS
Pengajar
Peserta
Ruang
1
Bahasa Arab I
2
Siti Maryam (SM)
I/A
R_1 atau R_2
2
Bahasa Inggris I
2
Hapsari (H)
I/A
R_1 atau R_2
3
Filsafat Umum
2
Moh. Dahlan (MD)
I/A
R_1 atau R_2
4
Fiqh
2
Rusydi Jamil (RJ)
I/A
R_1 atau R_2
5
Ilmu Sosial Dasar
2
Ulfah Fajarini (UF)
I/A
R_1 atau R_2
6
Pendidikan Kewargaan
2
Wahdi Sayuti (WS)
I/A
R_1 atau R_2
7
Penguatan Komputer
2
Anwar Syaddad (AS)
I/A
Lab Komputer
8
Biologi Umum
2
Zulfiani (Z)
I/A
R_1 atau R_2
9
Biologi Umum
2
Zulfiani (Z)
I/A
R_1 atau R_2
10
Fisika Dasar
2
Erina Hertanti (EH)
I/A
R_1 atau R_2
11
Matematika Dasar
2
Anwar Syaddad (AS)
I/A
R_1 atau R_2
12
Fisika Dasar
2
Erina Hertanti (EH)
I/AB
R_1 atau R_2
13
Matematika Dasar
2
Anwar Syaddad (AS)
I/AB
R_1 atau R_2
14
Bahasa Arab I
2
Siti Maryam (SM)
I/B
R_1 atau R_2
15
Bahasa Inggris I
2
Hapsari (H)
I/B
R_1 atau R_2
16
Filsafat Umum
2
Moh. Dahlan (MD)
I/B
R_1 atau R_2
17
Fiqh
2
Rusydi Jamil (RJ)
I/B
R_1 atau R_2
18
Ilmu Sosial Dasar
2
Ulfah Fajarini (UF)
I/B
R_1 atau R_2
19
Pendidikan Kewargaan
2
Wahdi Sayuti (WS)
I/B
R_1 atau R_2
20
Penguatan Komputer
2
Anwar Syaddad (AS)
I/B
Lab Komputer
21
Biologi Umum
2
Zulfiani (Z)
I/B
R_1 atau R_2
22
Biologi Umum
2
Zulfiani (Z)
I/B
R_1 atau R_2
23
Fisika Dasar
2
Erina Hertanti (EH)
I/B
R_1 atau R_2
24
Matematika Dasar
2
Anwar Syaddad (AS)
I/B
R_1 atau R_2
Nilai kepuasan pelaksanaan suatu mata kuliah pada hari dan jam tertentu (Nab) ditunjukkan dengan suatu konstanta yang dapat bernilai berapa saja. Pada model akan diberikan nilai yang besar pada hari dan jam utama agar mata kuliah terpengaruhi untuk terjadwal pada hari dan jam tersebut. Kemudian ada hari dan
27
jam tertentu seperti Jumat jam ketiga saat tidak ada satu perkuliahan pun yang dijadwalkan. Nilai kepuasan sebagai berikut: Tabel 3 Koefisien nilai Hari Senin Selasa Rabu Kamis Jumat
1 200 300 300 300 100
Jam ke2 3 4 300 300 300 300 300 300 300 300 300 300 300 300 100 100 100
5 100 100 100 100 100
Pemodelan dari permasalahan yang diberikan sebagai berikut: Batasan utama 1.
Semua mata kuliah terjadwal di satu ruang pada suatu hari dan suatu jam.
∑∑∑ x a∈A b∈B c∈C
2.
a ,b ,c , d
= 1, untuk d ∈ D
Semua mata kuliah terjadwal di ruang yang sesuai. 2
∑∑∑ x a∈A b∈B c =1
∑∑ x a∈A b∈B
3.
(1)
a ,b ,c , dcc
a ,b , 3, dc3
= 1, untuk dcc ∈ D
= 1, untuk dc3 ∈ D
(2) (3)
Tidak terjadi penggunaan ruang, hari dan jam yang sama untuk lebih dari satu mata kuliah yang berbeda.
∑x
a ,b ,c ,d
d∈D
4.
≤ 1, untuk a ∈ A; b ∈ B; c ∈ C
(4) Tidak terjadi satu peserta mengikuti lebih dari satu mata kuliah yang berbeda.
∑x
a ,b ,c ,dm A
≤ 1, untuk a ∈ A; b ∈ B; c ∈ C; dm A = 1, ..., 13
(5)
a ,b ,c , dmB
≤ 1, untuk a ∈ A; b ∈ B; c ∈ C; dm B = 12, ..., 24
(6)
dm A
∑x dmB
5.
Tidak terjadi satu pengajar mengajar dua mata kuliah yang berbeda pada hari dan jam yang sama.
∑x
a ,b ,c , dp1
≤ 1, untuk a ∈ A; b ∈ B; c ∈ C; dp1 = 7, 11, 13, 20, 24
dp1
Batasan tambahan 6.
Mata kuliah Bahasa Arab dialokasikan pada hari Senin.
(7)
28
∑∑ x b∈B c∈C
7.
1,b ,c ,da1
= 1; untuk da1 = 1, 14
(8)
Mata kuliah Bahasa Inggris tidak dapat dialokasikan pada jam pertama sampai dengan jam ketiga. xa ,b ,c ,daa = 0, untuk a ∈ A; b = 1, 2; c = 1, 2, 3; da a = 2, 15
8.
(9)
Selain pengajar Biologi Umum dan Bahasa Inggris, semua pengajar menginginkan hari yang sama untuk mata kuliah yang sama dengan jam yang berurutan.
∑ (x c∈C
a ,b ,c ,i
− xa ,b+1,c , j ) = 0, untuk a ∈ A; b = 1,..., (q − 1); (i, j ) =
(10)
(1,14), (3,16), ( 4,17), (5,18), (6,19), (7,20)
Untuk mata kuliah Biologi Umum:
∑ (x ∑ (x c∈C
a ,b ,c ,8
− xa ,b+1,c ,9 ) = 0, untuk a ∈ A; b = 1,..., (q − 1) − xa ,b+1,c , 22 ) = 0, untuk a ∈ A; b = 1,..., (q − 1)
(12)
Untuk mata kuliah Fisika Dasar dan Matematika Dasar: ∑ (xa ,b,c,10 + xa,b+1,c,12 − 2 * xa ,b+1,c, 23 ) = 0, untuk a ∈ A; b = 1,..., (q − 2)
(13)
∑ (x
(14)
c∈C
a ,b ,c , 21
c∈C
c∈C
a ,b ,c ,11
+ xa ,b+1,c ,13 − 2 * xa ,b+1,c , 24 ) = 0, untuk a ∈ A; b = 1,..., (q − 2)
xa ,b ,c ,dab = 0, untuk a ∈ A; b = 1, 2; c = 4, 5; dab = 10, 11
9.
(11)
(15)
Ada mata kuliah yang tidak dapat dijadwalkan pada hari dan waktu tertentu, seperti: Tidak ada perkuliahan pada hari Jumat jam ketiga: ∑ ∑ x5 , 3 , c , d = 0
(16)
c∈C d ∈D
Beberapa mata kuliah tidak dapat dijadwalkan pada tiap jam kelima: (17) ∑∑ xa ,b,c,db5 = 0; untuk a ∈ A c∈C db5
Fungsi Obyektif dari pembatasan ini berupa: Maksimumkan z = ∑∑∑ ∑ xa ,b ,c ,d ∗ N a ,b
(18)
a∈A b∈B c∈C d∈D
Kemudian model dituliskan programnya. Setelah itu program disimulasikan dengan menggunakan software LINGO 8.0 metode branch and bound. Penulisan program dan outputnya dapat dilihat pada lampiran 1. Hasil simulasi dapat dilihat pada Tabel 4.
29
Tabel 4 Hasil simulasi Hari
Senin
Jam
Semester I Kelas A Ruang
Mata kuliah Penguatan 07.30 - 09.10 Lab Kom Komputer
Semester I Kelas B
Pengajar Ruang
R_2
Bahasa Arab
SM
11.00 - 12.50
R_1
Biologi Umum
Z
Lab Kom R_2
13.30-15.10
R_1
Biologi Umum
Z
R_2
07.30 - 09.10 Selasa
R_2
09.20 - 11.00
R_1
11.00 - 12.50
R_1
WS
R_2
MD
R_2
13.30 - 15.10
Rabu
Pengajar
AS
09.20 - 11.00
Pendidikan Kewargaan Filsafat Umum
Mata kuliah
R_1
Penguatan Komputer Bahasa Arab Bahasa Inggris Biologi Umum Biologi Umum Pendidikan Kewargaan Filsafat Umum
AS SM H Z Z WS MD
07.30 - 09.10
R_1
Fisika Dasar
EH
09.20 - 11.00
R_1
Fisika Dasar
EH
11.00 - 12.50
R_2
RJ
R_1
Fisika Dasar
EH
13.30 - 15.10
R_1
H
R_2
Fiqh
RJ
07.30 - 09.10
R_1
09.20 - 11.00
R_1
Fiqh Bahasa Inggris Matematika Dasar Matematika Dasar
Kamis
AS AS
11.00 - 12.50 13.30 - 15.10
R_1 R_2
Ilmu Sosial Dasar
UF
R_2
Matematika Dasar Ilmu Sosial Dasar
AS UF
Berdasarkan tabel di atas dapat diperiksa bahwa pembatas tidak dilanggar. Pembatas pertama terpenuhi sebab semua mata kuliah yang ada pada Tabel 2 ada di Tabel 4. Kemudian mata kuliah dialokasikan ke ruang yang sesuai. Contoh Penguatan Komputer dialokasikan ke Laboratorium Komputer. Kemudian setiap ruang pada suatu hari dan suatu jam hanya terdapat satu mata kuliah saja. Peserta hanya mengikuti satu perkuliahan pada suatu waktu di satu ruang. Pengajar juga hanya mengajar satu mata kuliah saja pada suatu waktu di satu ruang. Pada hari Senin terdapat mata kuliah Bahasa Arab. Kemudian mata kuliah Bahasa Inggris dialokasikan pada jam ke-4. Semua mata kuliah, selain Biologi Umum dan Bahasa Inggris dijadwalkan berurutan.
30
Beberapa Skenario Misalkan nilai kepuasan penggunaan waktu perkuliahan memiliki beberapa skenario sebagai berikut: Tabel 5 Beberapa Skenario Hari
1 Senin 1000 Skenario Selasa 1000 I Rabu 1000 Kamis 1000 Jumat 1000 Hari Senin Skenario Selasa II Rabu Kamis Jumat Hari Senin Skenario Selasa III Rabu Kamis Jumat Hari
2 1000 1000 1000 1000 1000
1 1000 1000 1000 1000 1000
2 0 0 0 0 0
1 1000 1000 0 1000 1000
2 1000 1000 0 1000 1000
1 2 Senin 0 1000 Skenario Selasa 1000 0 IV Rabu 1000 1000 Kamis 1000 0 Jumat 0 1000
Jam ke3 1000 1000 1000 1000 1000 Jam ke3 1000 1000 1000 1000 1000 Jam ke3 0 0 0 0 0 Jam ke3 1000 1000 0 1000 1000
4 1000 1000 1000 1000 1000
5 1000 1000 1000 1000 1000
4 1000 1000 1000 1000 1000
5 1000 1000 1000 1000 1000
4 1000 1000 0 1000 1000
5 1000 1000 0 1000 1000
4 5 1000 0 0 1000 1000 1000 0 1000 1000 0
Pada skenario I semua waktu perkuliahan bernilai sama yaitu 1000. Skenario II menyatakan bahwa jam kedua di tiap hari kurang disukai untuk perkuliahan. Sedangkan pada skenario III jam ketiga dan hari Rabu kurang disukai untuk perkuliahan. Skenario IV menyatakan beberapa jam perkuliahan di beberapa hari kurang disukai untuk perkuliahan. Penyebaran mata kuliah pada skenario I dapat dilihat pada Tabel 6. Berdasarkan Tabel 6 tersebut dapat diketahui bahwa batasan utama dan batasan tambahan tidak terlanggar dengan nilai koefisien sama di setiap hari dan jam.
31
Tabel 6 Skenario I Smt
Hari
Jam 07.30 - 09.10 09.20 - 11.00 11.00 - 12.50 13.30-15.10 15.40 - 17.20
Senin
Selasa
07.30 - 09.10 09.20 - 11.00 11.00 - 12.50 13.30 - 15.10 15.40 - 17.20 07.30 - 09.10
Semester I Kelas A
Semester I Kelas B
Ruang Mata kuliah Pengajar Ruang R_1 Biologi Umum R_1 Biologi Umum
Z Z
R_2 Bahasa Arab
SM
R_1
RJ
R_2 R_2 R_1
Fiqh Fisika Dasar Fisika Dasar Ilmu Sosial Dasar
R_1 R_1
Bahasa Inggris Bahasa Arab
H SM
R_2
Fiqh
RJ
R_2
Fisika Dasar
EH
R_2
Ilmu Sosial Dasar
UF
R_2
Pendidikan Kewargaan
WS
Lab Kom
Penguatan Komputer
AS
R_2
Matematika Dasar
AS
R_1
Filsafat Umum
MD
R_2 R_2
Biologi Umum Biologi Umum
Z Z
UF
11.00 - 12.50 13.30 - 15.10
R_2
Pendidikan Kewargaan
WS
15.40 - 17.20 07.30 - 09.10
Lab Kom
Penguatan Komputer
AS
09.20 - 11.00 Kamis
11.00 - 12.50
R_2
13.30 - 15.10
R_2
Matematika Dasar Matematika Dasar
AS AS
15.40 - 17.20
Jumat
Pengajar
EH EH
09.20 - 11.00 Rabu
Mata kuliah
07.30 - 09.10 09.20 - 11.00 11.00 - 12.50 13.30 - 15.10 15.40 - 17.20
R_1 Filsafat Umum MD
R_1 Bahasa Inggris
H
Skenario II menyatakan bahwa jam kedua merupakan waktu yang kurang disukai untuk mengajar. Pada jadwal yang dihasilkan (Tabel 7) masih terdapat mata kuliah yang terjadwal di jam kedua tersebut. Walaupun demikian jadwal tersebut tidaklah melanggar batasan utama dan batasan tambahan.
32
Tabel 7 Skenario II Smt
Hari
Senin
Semester I Kelas A
Semester I Kelas B
Jam
Ruang
Mata kuliah
Pengajar Ruang
Mata kuliah
Pengajar
07.30 - 09.10
R_1
Fisika Dasar
EH
09.20 - 11.00
R_1
Fisika Dasar
EH
11.00 - 12.50
R_2
Bahasa Arab
SM
R_1
Fisika Dasar
EH
13.30-15.10
R_1
Filsafat Umum
MD
R_2
Bahasa Arab
SM
15.40 - 17.20
R_2
Bahasa Inggris
H
R_1
Filsafat Umum
MD
07.30 - 09.10 09.20 - 11.00 Selasa
11.00 - 12.50 Lab Kom 13.30 - 15.10
R_2
Penguatan Komputer Pendidikan Kewargaan
AS WS
15.40 - 17.20
Lab Kom R_2
Penguatan Komputer Pendidikan Kewargaan
AS WS
07.30 - 09.10 09.20 - 11.00 11.00 - 12.50
Rabu
13.30 - 15.10
R_2
Ilmu Sosial Dasar
UF
15.40 - 17.20 07.30 - 09.10
R_1
09.20 - 11.00
R_1
Kamis
Matematika Dasar Matematika Dasar
R_1
Biologi Umum
Z
R_1
Biologi Umum
Z
R_1
Ilmu Sosial Dasar
UF
R_1
Matematika Dasar
AS
R_2
Bahasa Inggris
H
R_2
Fiqh
RJ
AS AS
11.00 - 12.50 13.30 - 15.10
R_2
Biologi Umum
Z
15.40 - 17.20
R_2
Biologi Umum
Z
R_1
Fiqh
RJ
07.30 - 09.10 09.20 - 11.00 Jumat
11.00 - 12.50 13.30 - 15.10 15.40 - 17.20
Skenario III menyatakan bahwa jam ketiga dan hari Rabu merupakan waktu yang kurang disukai untuk mengajar. Pada jadwal yang dihasilkan (Tabel 8) tidak terdapat perkuliahan pada hari Rabu, meskipun masih ada beberapa mata kuliah yang tersebar di jam ketiga. Batasan utama dan batasan tambahan tidak terlanggar.
33
Tabel 8 Skenario III Smt
Hari
Senin
Semester I Kelas A
Jam
Ruang
07.30 - 09.10
R_1
09.20 - 11.00
R_2
11.00 - 12.50
R_2
13.30-15.10
R_1
Semester I Kelas B
Mata kuliah Pengajar Ruang Pendidikan WS Kewargaan Matematika AS R_1 Dasar Matematika AS Dasar Bahasa Arab
SM
15.40 - 17.20 07.30 - 09.10
R_1
Biologi Umum
Z
09.20 - 11.00
R_1
Biologi Umum
Z
13.30 - 15.10
R_2
Filsafat Umum MD
15.40 - 17.20
R_1
Bahasa Inggris
H
07.30 - 09.10
R_1
Fiqh
RJ
09.20 - 11.00
R_2
Fisika Dasar
EH
Kamis 11.00 - 12.50
R_2
EH
13.30 - 15.10
R_1
Fisika Dasar Ilmu Sosial Dasar
Mata kuliah
Pengajar
Pendidikan Kewargaan
WS
R_2
Matematika Dasar Bahasa Arab
SM
R_1
Bahasa Inggris
H
R_2
Filsafat Umum
MD
R_1
Fiqh
RJ
R_2
Fisika Dasar
EH
R_2
AS
Selasa 11.00 - 12.50
07.30 - 09.10 09.20 - 11.00 Rabu
11.00 - 12.50 13.30 - 15.10 15.40 - 17.20
Jumat
UF
15.40 - 17.20
R_1
07.30 - 09.10
R_1
Ilmu Sosial Dasar Biologi Umum
09.20 - 11.00
R_1
Biologi Umum
Z
Lab Kom
Penguatan Komputer
AS
UF Z
11.00 - 12.50 13.30 - 15.10 15.40 - 17.20
Lab Kom
Penguatan Komputer
AS
Skenario IV menyatakan jam tertentu kurang disukai untuk mengajar. Pada jadwal yang dihasilkan (Tabel 9) masih terdapat mata kuliah yang terjadwal pada jam tertentu tersebut. Namun batasan utama dan batasan tambahan tidak terlanggar.
34
Tabel 9 Skenario IV
Hari
Smt Jam
Semester I Kelas A
Semester I Kelas B
Ruang
Mata kuliah
Pengajar
Ruang
Mata kuliah
Pengajar
09.20 - 11.00
R_2
Bahasa Arab
SM
11.00 - 12.50
R_1
Biologi Umum
Z
R_2
Bahasa Arab
SM
13.30-15.10
R_1
Biologi Umum
Z
07.30 - 09.10
R_1
Fisika Dasar
EH
09.20 - 11.00
R_1
Fisika Dasar
EH
Selasa 11.00 - 12.50
R_1
Filsafat Umum
MD
R_1
Fisika Dasar
EH
13.30 - 15.10
R_2
Bahasa Inggris
H
R_1
Filsafat Umum
MD
07.30 - 09.10
R_1
Biologi Umum
Z
09.20 - 11.00
R_1
Biologi Umum
Z
07.30 - 09.10 Senin
15.40 - 17.20
15.40 - 17.20
Rabu
11.00 - 12.50 Lab Kom 13.30 - 15.10
R_1
Penguatan Komputer
AS
Fiqh
RJ
15.40 - 17.20
Lab Kom R_1
Penguatan Komputer Fiqh
AS RJ
07.30 - 09.10 09.20 - 11.00 Kamis 11.00 - 12.50
R_2
13.30 - 15.10
R_2
Matematika Dasar Matematika Dasar
AS AS
15.40 - 17.20 07.30 - 09.10
R_2
Ilmu Sosial Dasar
Matematika Dasar
AS
R_1
Ilmu Sosial Dasar
UF
R_2
Bahasa Inggris
H
R_2
Pendidikan Kewargaan
WS
UF
09.20 - 11.00 Jumat
R_2
11.00 - 12.50 13.30 - 15.10
R_1
Pendidikan Kewargaan
WS
15.40 - 17.20
Beberapa waktu perkuliahan yang memiliki nilai kepuasan penggunaan waktunya nol memang terjadwal mata kuliah. Namun hal tersebut tidak melanggar batasan utama dan batasan tambahan yang ada.
SIMPULAN DAN SARAN Simpulan 1. Model yang telah diimplementasikan menghasilkan jadwal bernilai optimal dengan tetap mengakomodasi batasan utama dan batasan tambahan. 2. Penjadwalan kuliah pada waktu yang kurang disukai terjadi agar tetap memenuhi batasan-batasan yang ada. 3. Pemilihan skenario disesuaikan dengan kondisi yang terjadi pada tempat penjadwalan kuliah tersebut. Saran Menindaklanjuti penelitian ini dengan masalah yang lebih kompleks seperti: memodelkan secara linier dengan variabel yang lebih sederhana dua mata kuliah yang dijadwalkan pada hari yang sama namun berurutan tanpa menentukan urutan pertama atau keduanya, membuat jadwal dengan mempertimbangkan mahasiswa pengulang selain itu juga mempertimbangkan jumlah sks dosen mengajar pada jadwal yang dihasilkan.
DAFTAR PUSTAKA Anbulagan, Setiadi R. 2001. Pemecahan Masalah Penjadwalan Kuliah di Perguruan Tinggi dengan Menggunakan Teknik Intelligent Search. Prosiding Seminar Nasional Kecerdasan Komputasional II; Universitas Indonesia, 16-17 Oktober 2001. Depok, Universitas Indonesia Anbulagan, Winata N. 2001. Penggunaan Tabu Search dalam Penjadwalan Kuliah di Perguruan Tinggi. Prosiding Seminar kecerdasan Komputasional II; Universitas Indonesia, 16 – 17 Oktober 2001. Depok, Universitas Indonesia Carter MW, Tovey CA.1992. When Is The Classroom Assignment Problem Hard? Operation Research 40: S28 –S39 Daskalaki S, Birbas T, Housos E. 2004. An Integer Programming Formulation for A Case Study in University Timetabling. Elsevier 153: 117 – 135. Fizzano P, Swanson S. 2000. Scheduling Classes on a College Campus. Computational Optimization and Aplications 16: 279–294. Glassey CR, Mizrach M. 1986. A Decision Support System for Assigning Classes to Rooms. Interfaces 16: 92–100. Hillier FS, Lieberman GJ. 1990. Introduction to Mathematical Programming. McGraw-Hill, New York. Ng PH, Martin LM. 2002.Classroom Scheduling Problems: A Discrete Optimization Approach. The UMAP Journal 23: 57–66. Papoutsis K, Valouxis C, Housos E. 2003. A Coloumn Generation Approach for the Timetabling Problem of Greek High Schools. Journal of Operation Research Society 54: 230–238. Taha HA. 1975. Integer Programming: Theory,Applications, and Computations. Academic Press, New York. Wagner HM. 1985. Principles of Operation Research with Aplications to Managerial Decisions. Prentice Hall of India. New Delhi. Wolsey LA. 1998. Integer Programming. John Wiley and Sons, New York.
LAMPIRAN
38
Lampiran 1 Penulisan Program dan Outputnya Penulisan Program MODEL: TITLE PENJADWALAN PERKULIAHAN JURUSAN PENDIDIKAN MATEMATIKA SEMESTER I; SETS: DAY/SENIN SELASA RABU KAMIS JUMAT/; TIME/JAM_1 JAM_2 .. JAM_5/; SUBTIME(TIME)/JAM_1 JAM_2 JAM_3 JAM_4/; SUB(TIME)/JAM_1 JAM_2 JAM_3/; COURSE/1 2 ..24/; COURSE_R(COURSE)/1 2 3 4 5 6 8 9 10 11 12 13 14 15 16 17 18 19 21 22 23 24/; COURSE_K(COURSE)/7 20/; P_1(COURSE)/7 11 13 20 24/; P_2(COURSE)/8 9 21 22/; H_1(COURSE)/1 14/; J_1(COURSE)/2 15/; S_3(COURSE)/10 11/; S_2(COURSE)/8 21/; SEQUENCE(COURSE,COURSE)/1,14 3,16 4,17 5,18 6,19 7,20/; SEQ(COURSE,COURSE)/8,9 21,22/; RUANG/R_1 R_2 KOM/; RUANG_R(RUANG)/R_1 R_2/; CO(DAY,TIME):N; COMB(DAY,TIME,RUANG,COURSE):X; ENDSETS !DATA; DATA: N = 200 300 300 300 100 300 300 300 300 100 300 300 300 300 100 300 300 300 300 100 100 100 100 100 100; ENDDATA !FUNGSI OBJEKTIF; MAX = @SUM(COMB(A,B,C,D):X(A,B,C,D)*N(A,B)); !VARIABEL KEPUTUSAN; !1 variabel X adalah integer nol atau satu; @FOR(COMB:@BIN(X)); !KENDALA;
39 !1 SETIAP MK DIALOKASIKAN KE TEPAT SATU RUANG PADA PERIODE TERTENTU KE RUANG YANG SESUAI; @FOR (COURSE_R(D):@SUM(DAY(A):@SUM(TIME(B):@SUM (RUANG(C)|C#LT#3:X(A,B,C,D))))=1); @FOR (COURSE_K(D):@SUM(DAY(A):@SUM(TIME(B):X(A,B,3,D)))=1); @FOR (COURSE(D):@SUM(DAY(A):@SUM(TIME(B):@SUM (RUANG(C):X(A,B,C,D))))=1); !2 PALING BANYAK SATU MK DIALOKASIKAN KE SUATU RUANG PADA PERIODE MANAPUN; @FOR (DAY(A):@FOR(TIME(B):@FOR (RUANG(C): @SUM(COURSE(D):X(A,B,C,D))<=1))); !3 ADA MATA KULIAH YANG HARUS DIALOKASIKAN KE WAKTU YANG BERBEDA KARENA PESERTANYA SAMA; @FOR(DAY(A):@FOR(TIME(B):@SUM (RUANG(C):@SUM (COURSE(D)|D#LT#14:X(A,B,C,D)))<=1)); @FOR(DAY(A):@FOR(TIME(B):@SUM (RUANG(C):@SUM (COURSE(D)|D#GT#11: X(A,B,C,D)))<=1)); !4 ADA MATA KULIAH YANG HARUS DIALOKASIKAN KE WAKTU YANG BERBEDA KARENA PENGAJARNYA SAMA; @FOR(DAY(A):@FOR(TIME(B):@SUM (RUANG(C):@SUM (P_1(D):X(A,B,C,D)))<=1)); @FOR(DAY(A):@FOR(TIME(B):@SUM (RUANG(C):@SUM (P_2(D):X(A,B,C,D)))<=1)); !5 PERKULIAHAN BAHASA ARAB HANYA PADA HARI SENIN; @FOR(H_1(D):@SUM(TIME(B):@SUM(RUANG(C):X(1,B,C,D)))=1); !6 TIDAK ADA PERKULIAHAN BAHASA INGGRIS PADA JAM PERTAMA SAMPAI DENGAN KETIGA; @FOR (J_1(D):@FOR(DAY(A):@FOR(SUB(B):@SUM(RUANG(C):X(A,B,C,D))=0))); !7 ADA MATA KULIAH YANG HARUS DIJADWALKAN BERURUTAN; @FOR(SEQUENCE(I,J):@FOR(DAY(A):@FOR(SUBTIME(B):@SUM(RUANG(C):X(A,B,C,I)X(A,B+1,C,J))=0))); @FOR(SEQUENCE(I,J):@FOR(DAY(A):@SUM(RUANG(C):X(A,5,C,I))=0)); !8 PERKULIAHAN BIOLOGI UMUM; @FOR(SEQ(I,J):@FOR(DAY(A):@FOR(SUBTIME(B):@FOR(RUANG(C):X(A,B,C,I)X(A,B+1,C,J)=0)))); @FOR(DAY(A):@SUM(RUANG(C):X(A,5,C,8))=0); @FOR(DAY(A):@SUM(RUANG(C):X(A,5,C,21))=0); !9 ADA MATA KULIAH YANG HARUS DIJADWALKAN BERURUTAN (3 SKS); @FOR(DAY(A):@FOR(SUB(B):@FOR(RUANG(C):X(A,B,C,10)+X(A,B+1,C,12)2*X(A,B+2,C,23)=0))); @FOR(DAY(A):@FOR(SUB(B):@FOR(RUANG(C):X(A,B,C,11)+X(A,B+1,C,13)2*X(A,B+2,C,24)=0))); @FOR(DAY(A):@FOR(TIME(B)|B#GT#3:@FOR(RUANG(C):@FOR(S_3(D):X(A,B,C,D)=0)))); !10 TIDAK ADA PERKULIAHAN PADA RUANG MANAPUN DI HARI JUMAT JAM KETIGA; @SUM(COURSE(D):@SUM(RUANG(C):X(5,3,C,D)))=0;
END
40
Output Global optimal solution found at iteration: Objective value:
165 7100.000
Model Title: PENJADWALAN PERKULIAHAN JURUSAN PENDIDIKAN MATEMATIKA SEMEST Variable N( SENIN, JAM_1) N( SENIN, JAM_2) N( SENIN, JAM_3) N( SENIN, JAM_4) N( SENIN, JAM_5) N( SELASA, JAM_1) N( SELASA, JAM_2) N( SELASA, JAM_3) N( SELASA, JAM_4) N( SELASA, JAM_5) N( RABU, JAM_1) N( RABU, JAM_2) N( RABU, JAM_3) N( RABU, JAM_4) N( RABU, JAM_5) N( KAMIS, JAM_1) N( KAMIS, JAM_2) N( KAMIS, JAM_3) N( KAMIS, JAM_4) N( KAMIS, JAM_5) N( JUMAT, JAM_1) N( JUMAT, JAM_2) N( JUMAT, JAM_3) N( JUMAT, JAM_4) N( JUMAT, JAM_5) X( SENIN, JAM_1, R_1, 1) X( SENIN, JAM_1, R_1, 2)
… X( X( X( X( X(
SELASA, SELASA, SELASA, SELASA, SELASA,
JAM_3, JAM_3, JAM_3, JAM_3, JAM_3,
R_1, R_1, R_1, R_1, R_1,
1) 2) 3) 4) 5)
…
Reduced Cost 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 -200.0000 -200.0000
…
…
0.000000 0.000000 1.000000 0.000000 0.000000
…
X( JUMAT, JAM_5, KOM, 23) X( JUMAT, JAM_5, KOM, 24) Row 1 2 3
… 661 662
Value 200.0000 300.0000 300.0000 300.0000 100.0000 300.0000 300.0000 300.0000 300.0000 100.0000 300.0000 300.0000 300.0000 300.0000 100.0000 300.0000 300.0000 300.0000 300.0000 100.0000 100.0000 100.0000 100.0000 100.0000 100.0000 0.000000 0.000000
-300.0000 -300.0000 -300.0000 -300.0000 -300.0000
…
0.000000 0.000000
-100.0000 -100.0000
Slack or Surplus 7100.000 0.000000 0.000000
Dual Price 1.000000 0.000000 0.000000
… 0.000000 0.000000
… 100.0000 0.000000
41
Dengan menggunakan fitur filter data yang ada di Ms.Excel, didapat hasil sebagai berikut:
X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X(
Variabel SENIN JAM_1 SENIN JAM_2 SENIN JAM_2 SENIN JAM_3 SENIN JAM_3 SENIN JAM_4 SENIN JAM_4 SELASA JAM_1 SELASA JAM_2 SELASA JAM_2 SELASA JAM_3 SELASA JAM_3 SELASA JAM_4 RABU JAM_1 RABU JAM_2 RABU JAM_3 RABU JAM_3 RABU JAM_4 RABU JAM_4 KAMIS JAM_1 KAMIS JAM_2 KAMIS JAM_3 KAMIS JAM_3 KAMIS JAM_4
KOM R_2 KOM R_1 R_2 R_1 R_2 R_1 R_1 R_2 R_1 R_2 R_1 R_1 R_1 R_1 R_2 R_1 R_2 R_1 R_1 R_1 R_2 R_2
7 1 20 8 14 9 15 21 22 6 3 19 16 10 12 23 4 2 17 11 13 24 5 18
Value 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000
Reduced Cost ‐2.000.000 ‐3.000.000 ‐3.000.000 ‐3.000.000 ‐3.000.000 ‐3.000.000 ‐3.000.000 ‐3.000.000 ‐3.000.000 ‐3.000.000 ‐3.000.000 ‐3.000.000 ‐3.000.000 ‐3.000.000 ‐3.000.000 ‐3.000.000 ‐3.000.000 ‐3.000.000 ‐3.000.000 ‐3.000.000 ‐3.000.000 ‐3.000.000 ‐3.000.000 ‐3.000.000
42
Lampiran 2 Output Beberapa Skenario Skenario Dasar Jam ke-
Hari 1
2
3
4
5
Senin
200
300
300
300
100
Selasa
300
300
300
300
100
Rabu
300
300
300
300
100
Kamis
300
300
300
300
100
Jumat
100
100
100
100
100
X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X(
Variabel SENIN JAM_1 SENIN JAM_2 SENIN JAM_2 SENIN JAM_3 SENIN JAM_3 SENIN JAM_4 SENIN JAM_4 SELASA JAM_1 SELASA JAM_2 SELASA JAM_2 SELASA JAM_3 SELASA JAM_3 SELASA JAM_4 RABU JAM_1 RABU JAM_2 RABU JAM_3 RABU JAM_3 RABU JAM_4 RABU JAM_4 KAMIS JAM_1 KAMIS JAM_2 KAMIS JAM_3 KAMIS JAM_3 KAMIS JAM_4
KOM R_2 KOM R_1 R_2 R_1 R_2 R_1 R_1 R_2 R_1 R_2 R_1 R_1 R_1 R_1 R_2 R_1 R_2 R_1 R_1 R_1 R_2 R_2
7 1 20 8 14 9 15 21 22 6 3 19 16 10 12 23 4 2 17 11 13 24 5 18
Value 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000
Reduced Cost -2.000.000 -3.000.000 -3.000.000 -3.000.000 -3.000.000 -3.000.000 -3.000.000 -3.000.000 -3.000.000 -3.000.000 -3.000.000 -3.000.000 -3.000.000 -3.000.000 -3.000.000 -3.000.000 -3.000.000 -3.000.000 -3.000.000 -3.000.000 -3.000.000 -3.000.000 -3.000.000 -3.000.000
43
Skenario I
Hari Senin Selasa Rabu Kamis Jumat
1 1000 1000 1000 1000 1000
X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X(
2 1000 1000 1000 1000 1000
Jam ke3 1000 1000 1000 1000 1000
4 1000 1000 1000 1000 1000
Variabel SENIN JAM_1 SENIN JAM_2 SENIN JAM_4 SENIN JAM_4 SENIN JAM_5 SELASA JAM_1 SELASA JAM_2 SELASA JAM_3 SELASA JAM_4 SELASA JAM_5 RABU JAM_1 RABU JAM_2 RABU JAM_4 RABU JAM_5 KAMIS JAM_1 KAMIS JAM_2 KAMIS JAM_3 KAMIS JAM_4 KAMIS JAM_5 JUMAT JAM_1 JUMAT JAM_2 JUMAT JAM_4 JUMAT JAM_4 JUMAT JAM_5
5 1000 1000 1000 1000 1000
R_1 R_1 R_1 R_2 R_1 R_1 R_2 R_2 R_2 R_2 R_1 R_2 R_2 R_2 KOM KOM R_2 R_2 R_2 R_1 R_1 R_1 R_2 R_2
8 9 15 1 14 4 17 10 12 23 5 18 6 19 7 20 11 13 24 3 16 2 21 22
Value 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000
Reduced Cost -1.000.000 -1.000.000 -1.000.000 -1.000.000 -1.000.000 -1.000.000 -1.000.000 -1.000.000 -1.000.000 -1.000.000 -1.000.000 -1.000.000 -1.000.000 -1.000.000 -1.000.000 -1.000.000 -1.000.000 -1.000.000 -1.000.000 -1.000.000 -1.000.000 -1.000.000 -1.000.000 -1.000.000
44
Skenario II Hari Senin Selasa Rabu Kamis Jumat
1 1000 1000 1000 1000 1000
2 0 0 0 0 0
X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X(
Jam ke3 1000 1000 1000 1000 1000
4 1000 1000 1000 1000 1000
Variabel SENIN JAM_1 SENIN JAM_2 SENIN JAM_3 SENIN JAM_3 SENIN JAM_4 SENIN JAM_4 SENIN JAM_5 SENIN JAM_5 SELASA JAM_3 SELASA JAM_4 SELASA JAM_4 SELASA JAM_5 RABU JAM_3 RABU JAM_4 RABU JAM_4 RABU JAM_5 KAMIS JAM_1 KAMIS JAM_2 KAMIS JAM_3 KAMIS JAM_4 KAMIS JAM_5 JUMAT JAM_4 JUMAT JAM_4 JUMAT JAM_5
5 1000 1000 1000 1000 1000
R_1 R_1 R_1 R_2 R_1 R_2 R_1 R_2 KOM R_2 KOM R_2 R_1 R_1 R_2 R_1 R_1 R_1 R_1 R_2 R_2 R_1 R_2 R_2
10 12 23 1 3 14 16 2 7 6 20 19 21 22 5 18 11 13 24 8 9 4 15 17
Value 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000
Reduced Cost -1.000.000 0.000000 -1.000.000 -1.000.000 -1.000.000 -1.000.000 -1.000.000 -1.000.000 -1.000.000 -1.000.000 -1.000.000 -1.000.000 -1.000.000 -1.000.000 -1.000.000 -1.000.000 -1.000.000 0.000000 -1.000.000 -1.000.000 -1.000.000 -1.000.000 -1.000.000 -1.000.000
45
Skenario III Hari Senin Selasa Rabu Kamis Jumat
1 1000 1000 0 1000 1000
2 1000 1000 0 1000 1000
X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X(
Jam ke3 0 0 0 0 0
4 1000 1000 0 1000 1000
Variabel SENIN JAM_1 SENIN JAM_2 SENIN JAM_2 SENIN JAM_3 SENIN JAM_4 SENIN JAM_4 SENIN JAM_5 SELASA JAM_1 SELASA JAM_2 SELASA JAM_4 SELASA JAM_4 SELASA JAM_5 SELASA JAM_5 KAMIS JAM_1 KAMIS JAM_2 KAMIS JAM_2 KAMIS JAM_3 KAMIS JAM_4 KAMIS JAM_4 KAMIS JAM_5 JUMAT JAM_1 JUMAT JAM_2 JUMAT JAM_4 JUMAT JAM_5
5 1000 1000 0 1000 1000
R_1 R_1 R_2 R_2 R_1 R_2 R_2 R_1 R_1 R_1 R_2 R_1 R_2 R_1 R_1 R_2 R_2 R_1 R_2 R_1 R_2 R_2 KOM KOM
6 19 11 13 1 24 14 8 9 15 3 2 16 4 17 10 12 5 23 18 21 22 7 20
Value 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000
Reduced Cost -1.000.000 -1.000.000 -1.000.000 0.000000 -1.000.000 -1.000.000 -1.000.000 -1.000.000 -1.000.000 -1.000.000 -1.000.000 -1.000.000 -1.000.000 -1.000.000 -1.000.000 -1.000.000 0.000000 -1.000.000 -1.000.000 -1.000.000 -1.000.000 -1.000.000 -1.000.000 -1.000.000
46
Skenario IV Hari Senin Selasa Rabu Kamis Jumat
1 0 1000 1000 1000 0
2 1000 0 1000 0 1000
X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X( X(
Jam ke3 4 0 1000 0 0 0 1000 0 0 0 1000
SENIN SENIN SENIN SENIN SELASA SELASA SELASA SELASA SELASA SELASA RABU RABU RABU RABU RABU RABU KAMIS KAMIS KAMIS JUMAT JUMAT JUMAT JUMAT JUMAT
Variabel JAM_2 JAM_3 JAM_3 JAM_4 JAM_1 JAM_2 JAM_3 JAM_4 JAM_5 JAM_5 JAM_1 JAM_2 JAM_3 JAM_4 JAM_4 JAM_5 JAM_3 JAM_4 JAM_5 JAM_1 JAM_2 JAM_4 JAM_4 JAM_5
5 0 1000 1000 1000 0
R_2 R_1 R_2 R_1 R_1 R_1 R_1 R_1 R_1 R_2 R_1 R_1 KOM R_1 KOM R_1 R_2 R_2 R_2 R_2 R_1 R_1 R_2 R_2
1 8 14 9 10 12 23 3 16 2 21 22 7 4 20 17 11 13 24 5 18 6 15 19
Value 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000
Reduced Cost -1.000.000 -1.000.000 -1.000.000 -1.000.000 -1.000.000 0.000000 -1.000.000 0.000000 -1.000.000 -1.000.000 -1.000.000 -1.000.000 0.000000 -1.000.000 -1.000.000 -1.000.000 -1.000.000 0.000000 -1.000.000 0.000000 -1.000.000 -1.000.000 -1.000.000 0.000000
