1
I PENDAHULUAN 1.1 Latar Belakang Salah satu bagian penting yang tidak dapat dipisahkan dalam sekolah tinggi dan universitas adalah masalah penjadwalan mata kuliah dengan kendala waktu yang diinginkan (preferensi) dosen, mahasiswa, dan banyaknya ruangan yang terbatas. Oleh sebab itu perlu dibuat sebuah penjadwalan mata kuliah yang memenuhi semua kendala dan memuaskan semua pihak. Bina Sarana Informatika (BSI) merupakan salah satu perguruan tinggi yang menyelenggarakan program regular dan ekstensi. Program regular diselenggarakan pada waktu pagi atau siang hari, sedangkan program ekstensi diselenggarakan pada waktu sore atau malam hari. Setiap mahasiswa dan dosen mempunyai preferensi hari dan periode waktu dalam pelaksanaan kuliah. Atas dasar ini, masalah penjadwalan mata kuliah akan dibuat.
Permasalahan penjadwalan mata kuliah ini dapat dimodelkan sebagai masalah Integer Nonlinear Programming (INLP). INLP adalah suatu model pemrograman matematika dimana variabel keputusan berupa bilangan integer dengan fungsi objektif atau kendalanya nonlinear. Tulisan ini merupakan rekontruksi dari artikel A 0-1 integer programming approach to a university timetabling problem yang ditulis oleh M Akif Bakir dan Cihan Askop. 1.2 Tujuan Tujuan dari karya ilmiah ini adalah memodelkan masalah penjadwalan mata kuliah yang meminimumkan ketidakpuasan mahasiswa dan dosen di Bina Sarana Informatika (BSI) Bogor ke dalam bentuk INLP. Selanjutnya model diselesaikan dengan bantuan software LINGO 8.0.
II LANDASAN TEORI Berikut ini akan dijelaskan definisi dan teori yang terkait dengan Integer Nonlinear Programming (INLP). 2.1 Pemrograman Linear Fungsi linear dan pertidaksamaan linear merupakan salah satu konsep dasar yang harus dipahami terkait dengan konsep pemrograman linear. Definisi 1 (Fungsi Linear) dalam Suatu fungsi f ( x1 , x 2 ,..., x n ) variabel-variabel x1 , x2 ,..., xn adalah suatu fungsi linear jika dan hanya jika untuk suatu himpunan konstanta c1 , c2 ,..., cn , f ( x1 , x 2 ,..., x n ) = c1 x1 + c 2 x 2 + ... + c n x n . (Winston 2004) Sebagai contoh, f ( x1 , x2 ) = 3x1 + 4 x2 merupakan fungsi linear, sementara f ( x1 , x2 ) = x12 x 22 bukan fungsi linear. Definisi 2 (Pertidaksamaan dan Persamaan Linear) Untuk sembarang fungsi linear f ( x1 , x 2 ,..., x n ) dan sembarang bilangan b , pertidaksamaan atau f ( x1 , x 2 ,..., x n ) ≤ b
f ( x1 , x 2 ,..., x n ) ≥ b adalah pertidaksamaan linear. Misalkan b sembarang bilangan, suatu persamaan f ( x1 , x 2 ,..., x n ) = b merupakan persamaan linear. (Winston 2004)
Pemrograman linear (PL) atau linear programming (LP) adalah suatu masalah optimisasi yang memenuhi ketentuanketentuan sebagai berikut: a) Tujuan masalah tersebut adalah memaksimumkan atau meminimumkan suatu fungsi linear dari sejumlah variabel keputusan. Fungsi yang akan dimaksimumkan atau diminimumkan ini disebut fungsi objektif. b) Nilai variabel-variabel keputusannya harus memenuhi suatu himpunan kendala. Setiap kendala harus berupa persamaan linear atau pertidaksamaan linear. c) Ada pembatasan tanda untuk setiap variabel dalam masalah ini. Untuk sembarang variabel xi , pembatasan tanda menentukan xi harus taknegatif ( xi ≥ 0) atau tidak dibatasi tandanya (unrestricted in sign). (Winston 2004)
2
Suatu PL mempunyai bentuk standar seperti yang didefinisikan sebagai berikut. Definisi 3 (Bentuk Standar PL) Suatu PL dikatakan berbentuk standar jika berbentuk: min z = cT x terhadap Ax = b (1) x≥0 dengan x dan c berupa vektor berukuran n, vektor b berukuran m, sedangkan A berupa matriks berukuran m × n yang disebut juga matriks kendala. (Nash & Sofer 1996) Sebagai catatan, yang dimaksud dengan vektor berukuran n adalah vektor yang memiliki dimensi (ukuran) n × 1. Solusi Pemrograman Linear Suatu masalah PL dapat diselesaikan dalam berbagai teknik, salah satunya adalah metode simpleks. Metode ini dapat menghasilkan suatu solusi optimum bagi masalah PL dan telah dikembangkan oleh Dantzig sejak tahun 1947, dan dalam perkembangannya merupakan metode yang paling umum digunakan untuk menyelesaikan masalah PL. Metode ini berupa metode iteratif untuk menyelesaikan masalah PL berbentuk standar. Pada masalah PL (1), vektor x yang memenuhi kendala Ax = b disebut solusi PL (1). Misalkan matriks A dinyatakan sebagai A = ( B N ) , dengan B adalah matriks taksingular berukuran m × m yang elemennya berupa koefisien variabel basis dan N merupakan matriks berukuran m × (n − m) yang elemen-elemennya berupa koefisien variabel nonbasis pada matriks kendala. Dalam hal ini matriks B disebut matriks basis untuk PL (1). Misalkan x dinyatakan sebagai vektor ⎛x ⎞ x = ⎜ B ⎟ , dengan xB adalah vektor variabel ⎝ xN ⎠ basis dan x N adalah vektor variabel nonbasis, maka Ax = b dapat dinyatakan ⎛x ⎞ sebagai Ax = ( B N ) ⎜ B ⎟ ⎝ xN ⎠
= BxB + NxN = b.
(2)
Karena matriks B adalah matriks taksingular, maka B memiliki invers, sehingga dari (2) x B dapat dinyatakan sebagai: x B = B -1b − B -1 Nx N . Kemudian, fungsi objektifnya menjadi:
(3) berubah
min z = c B x B + c N x N . T
T
Definisi 4 (Daerah Fisibel) Daerah fisibel suatu masalah PL adalah himpunan semua titik yang memenuhi semua kendala dan pembatasan tanda pada masalah PL tersebut. (Winston 2004) Definisi 5 (Solusi Basis) Solusi dari suatu masalah PL disebut solusi basis jika memenuhi syarat berikut: i. solusi tersebut memenuhi kendala pada masalah PL; ii. kolom-kolom dari matriks kendala yang berpadanan dengan komponen taknol dari solusi tersebut adalah bebas linear. (Nash & Sofer 1996) Definisi 6 (Solusi Basis Fisibel) Vektor x disebut solusi basis fisibel jika x merupakan solusi basis dan x ≥ 0. (Nash & Sofer 1996) Ilustrasi solusi basis dan solusi basis fisibel diberikan dalam Contoh 1. Contoh 1 Misalkan diberikan masalah PL berikut: min z = −3 x1 − 2 x2 , − 2 x1 + x2 + x3 = 3,
terhadap
− x1 + 2 x2 + x4 = 8,
(4)
x1 + x5 = 5, x1 , x2 , x3 , x4 , x5 ≥ 0. Dari PL tersebut diperoleh: ⎛ −2 1 1 0 0 ⎞ ⎛ 3⎞
A = ⎜ −1 2 0 1 0 ⎟ , b = ⎜ 8 ⎟ . ⎜ ⎟ ⎜ ⎟ ⎝ 1 0 0 0 1⎠ ⎝ 5⎠
Misalkan dipilih x B = ( x3
x4
T
x5 )
dan x N = ( x1
maka matriks basisnya adalah
T
x2 )
,
3
⎛1 0 0⎞ ⎛1 -1 ⎜ ⎜ ⎟ B= 0 1 0 , B = 0 ⎜ ⎟ ⎜ ⎝0 0 1⎠ ⎝0 ⎛ -2 1 ⎞ N = ⎜ -1 2 ⎟ ⎜ ⎟ ⎝1 0 ⎠ cTB = (3 8 5) , cTN = ( 0 Dengan menggunakan tersebut, diperoleh x N = ( 0 0)
T
0 0⎞ 1 0⎟ ,
⎟
0 1⎠
0) .
matriks
basis
,
x B = B b = ( 3 8 5) -1
T
(5)
z = cTB B -1b = −25
Solusi (5) merupakan solusi basis, karena memenuhi kendala pada masalah PL (4) dan kolom-kolom pada matriks kendala yang berpadanan dengan komponen taknol dari (5), yaitu B bebas linear (kolom yang satu bukan merupakan kelipatan dari kolom yang lain). Solusi (5) juga merupakan solusi basis fisibel, karena nilai-nilai variabelnya lebih dari atau sama dengan nol. Hal yang juga penting dalam konsep pemrograman linear untuk model ini adalah daerah fisibel dan solusi optimum yang didefinisikan sebagai berikut. Definisi 7 (Solusi Optimum) Untuk masalah maksimisasi, solusi optimum suatu PL adalah suatu titik dalam daerah fisibel dengan nilai fungsi objektif terbesar. Untuk masalah minimisasi, solusi optimum suatu PL adalah suatu titik dalam daerah fisibel dengan nilai fungsi objektif terkecil. (Winston 2004) 2.2 Integer Programming Integer programming (IP) atau pemrograman integer adalah suatu model pemrograman linear dengan variabel yang digunakan berupa bilangan bulat (integer). Jika semua variabel harus berupa integer, maka masalah tersebut dinamakan pure integer programming. Jika hanya sebagian yang harus berupa integer, maka disebut mixed integer programming (MIP). IP dengan semua variabelnya harus bernilai 0 atau 1 disebut 0-1 IP. (Garfinkel & Nemhauser 1972)
Definisi 8 (Pemrograman Linear Relaksasi) Pemrograman linear relaksasi atau sering disebut PL-relaksasi merupakan suatu pemrograman linear yang diperoleh dari suatu IP dengan menghilangkan kendala integer atau kendala 0-1 pada setiap variabelnya. Untuk masalah maksimisasi, nilai optimum fungsi objektif PL-relaksasi lebih besar atau sama dengan nilai optimum fungsi objektif IP, sedangkan untuk masalah minimisasi, nilai optimum fungsi objektif PLrelaksasi lebih kecil atau sama dengan nilai optimum fungsi objektif IP. (Winston 2004) 2.3 Nonlinear Programming Model nonlinear programming (NLP) meliputi pengoptimuman suatu kondisi berikut : a) fungsi objektif nonlinear terhadap kendala linear, b) fungsi objektif nonlinear terhadap kendala nonlinear, c) fungsi objektif nonlinear dan takberkendala. (Sharma 2006) Definisi 9 (bentuk umum suatu NLP) Bentuk umum suatu nonlinear programming adalah : max (atau min) z = f(x1, x2, ..., xn) terhadap kendala: g1(x1, x2, ..., xn) (≤, =, ≥) b1 g2(x1, x2, ..., xn) (≤, =, ≥) b2
M
gm(x1, x2, ..., xn) (≤, =, ≥) bm
(6)
Komponen x1, x2, ..., xn merupakan variabel keputusan dan b1, b2, ..., bm adalah konstanta. f(x1, x2, ..., xn) adalah fungsi objektif dan gj(x1, x2, ..., xn) menyatakan fungsi-fungsi kendala persamaan atau pertaksamaan, dengan j = 1, 2, …, m. Jika bentuk umum memiliki kendala, maka masalah (6) dinamakan masalah nonlinear programming berkendala. Jika bentuk umum tidak memiliki kendala, maka masalah (6) dinamakan masalah nonlinear programming takberkendala. (Winston 2004) 2.3.1 Konsep Dasar NLP Untuk menyelesaikan suatu masalah nonlinear programming diperlukan konsep
4
dasar, yaitu gradien dan matriks Hesse fungsi banyak variabel. Vektor Gradien dan Matriks Hesse Misalkan f adalah fungsi dari n variabel x1 , x2 ,..., xn (biasa dituliskan dengan f ( x ) = f ( x1 , x2 ,..., xn ) dan terdiferensialkan dua kali secara kontinu, dan dinyatakan dengan f ∈ C 2 . Untuk f ∈ C 2 didefinisikan vektor gradien fungsi f di titik x adalah ⎛ ∂f ⎞ ⎜ ∂x (x) ⎟ ⎜ 1 ⎟ ⎜ ∂f ⎟ ( x) ⎟ ⎜ ∇f (x) = ⎜ ∂x2 ⎟ ⎜ M ⎟ ⎜ ⎟ ⎜ ∂f (x) ⎟ ⎜ ∂x ⎟ ⎝ n ⎠ Jika fungsi terdiferensialkan secara kontinu dua kali maka di titik x terdapat matriks turunan parsial yang disebut matriks Hesse (Hessian matrix) ⎧⎪ ∂ 2 f (x) ⎫⎪ 2 H ( x) = ⎨ ⎬ = ∇ f ( x) ∂ x ∂ x ⎩⎪ i j ⎭⎪ ⎛ ∂ f (x) ⎜ 2 ⎜ ∂x1 ⎜ 2 ⎜ ∂ f (x) = ⎜ ∂x2 ∂x1 ⎜ ⎜ M ⎜ 2 ⎜ ∂ f (x) ⎜ ⎝ ∂xn ∂x1 2
∂ f ( x) ∂ f ( x) ⎞ L ⎟ ∂x1∂x2 ∂x1∂xn ⎟ ⎟ ∂ 2 f ( x) ∂ 2 f ( x) ⎟ K ∂x2 ∂xn ⎟ ∂x2 2 ⎟ M O M ⎟ ⎟ ∂ 2 f ( x) ∂ 2 f ( x) ⎟ L ∂xn ∂x2 ∂xn 2 ⎟⎠ 2
2
2.3.2 Fungsi Konveks dan Fungsi Konkaf Definisi 10 (Fungsi Konveks dan Konkaf) Fungsi f dikatakan fungsi konveks pada selang I jika hanya jika f (λ x1 + (1 − λ ) x2 ) ≤ λ f ( x1 ) + (1 − λ ) f ( x2 ), untuk setiap x1 , x2 ∈ I dan untuk setiap 0 ≤ λ ≤ 1 . Fungsi f dikatakan fungsi konkaf pada selang I jika hanya jika f (λ x1 + (1 − λ ) x2 ) ≥ λ f ( x1 ) + (1 − λ ) f ( x2 ), untuk setiap x1 , x2 ∈ I dan untuk setiap 0 ≤ λ ≤ 1 . (Ecker & Kupferschmid 1998) 2.3.3 Pengoptimuman Berkendala Metode yang dapat digunakan dalam menyelesaikan pengoptimuman berkendala di antaranya adalah metode iteratif (metode
penalti) dan metode analitik (pengali Lagrange dan kondisi Karush-Kuhn-Tucker). Di bawah ini akan dibahas salah satu metode penyelesaian untuk pengoptimuman berkendala. Kondisi Karush-Kuhn-Tucker (KKT) Misalkan diberikan pengoptimuman kendala pertidaksamaan, maka salah satu alternatif penyelesaian adalah dengan mengubah semua pertaksamaan menjadi persamaan dengan menambah variabel tambahan, seperti: g ( x) ≤ 0 → g ( x) + y = 0 Namun dengan cara ini tidak efektif jika terlalu banyak kendala yang harus diubah karena mengakibatkan bertambah banyak variabel keputusan yang harus dilibatkan. Teknik lain untuk menyelesaikan masalah tersebut adalah dengan menggunakan kondisi Karush-Kuhn-Tucker. Misalkan diberikan masalah pengoptimuman: min f ( x) … (8) terhadap g j ( x ) = 0, j = 1, 2, ..., m − 1 g j ( x ) ≤ 0, j = m, ..., p dan x ∈ R
n
dengan f dan gj merupakan fungsi-fungsi yang mempunyai turunan pertama yang kontinu. Didefinisikan fungsi Lagrange L(x,λ) = f(x) +
m
∑λ g j =1
j
j
( x)
Karush (1939) dan Kuhn dan Tucker (1951) secara terpisah menurunkan syarat perlu yang harus dipenuhi oleh solusi (minimizer) x* dari masalah (8), yang disebut kondisi KKT, yaitu n
terdapat λ * ∈ R sehingga: m ∂g j ∂f (x*) + ∑ λ *j (x*) = 0, i = 1, 2,..., l 1. ∂xi ∂xi j =1 2. g j (x*) ≤ 0, j = m,..., p 3. λ *j g j (x*) = 0, j = m,..., p 4. λ *j ≥ 0, j = m,..., p dengan λ * pengali Lagrange. Kondisi di atas dapat menjadi syarat cukup untuk strong global minimizer x* jika f dan gj merupakan fungsi konveks. (Snyman 2005) 2.4 Integer Nonlinear Programming Model integer nonlinear programming (INLP) merupakan suatu model pemrograman matematika di mana variabel keputusan
5
berupa bilangan integer dengan fungsi objektif atau kendalanya nonlinear. (Ecker & Kupferschmid 1998) Bentuk umum dari masalah nonlinear programming (INLP) sebagai berikut: min f ( x)
integer adalah
terhadap gi (x) ≤ bi , i = 1, 2,..., m (9)
hk (x) = ck , k = 1, 2,..., l
n x ∈ X ⊆ Z
dengan f ( x ) , gi (x) , hk (x) merupakan fungsi n
n
bilangan real pada R dan Z merupakan n
himpunan nilai-nilai integer di R . x° Î X adalah solusi fisibel pada masalah (9) jika g i ( x°) £ bi , untuk semua i = 1,..., m dan hk ( x°) = ck , untuk semua k = 1,..., l . Sebuah
solusi fisibel x* dinamakan solusi optimal pada masalah (9) jika f ( x*) £ f ( x ) untuk semua solusi fisibel x pada masalah (9). Setiap menyelesaikan masalah INLP dilakukan relaksasi untuk melepaskan nilai x yang bernilai integer. Penyelesaian masalah relaksasi pada nonlinear programming, di antaranya menggunakan kondisi Karush Kuhn Tucker (KKT) dan metode global descent. 2.5 Metode Branch-and-Bound Dalam penulisan karya ilmiah ini, untuk memperoleh solusi optimum dari masalah INLP digunakan software LINGO 8.0 yaitu sebuah program yang didesain untuk menentukan solusi model linear, nonlinear, dan optimisasi integer. Software LINGO 8.0 ini menggunakan metode branch and bound untuk menyelesaikan masalah IP atau INLP. Prinsip dasar metode branch and bound adalah memecah daerah fisibel dari masalah (9) dengan memartisi ruang pencarian, dilakukan dengan membagi daerah fisibel ke dalam p himpunan bagian X1, X2,…, Xp dengan p ≥ 2 . • Branch Branching (pencabangan) adalah proses membagi-bagi permasalahan menjadi subproblem-subproblem yang mungkin mengarah ke solusi. • Bound Bounding (pembatasan) adalah suatu proses untuk mencari atau menghitung batas
atas (dalam masalah minimisasi) dan batas bawah (dalam masalah maksimisasi) untuk solusi optimum pada subproblem yang mengarah ke solusi. Metode branch-and-bound untuk masalah minimisasi diawali dengan membuat subproblem-subproblem. Sebuah subproblem pada node i, (P(Xi)), i=1,…, p adalah bentuk dari masalah (9) dengan menggantikan X dengan Xi. Satu atau lebih subproblem dipilih dari daftar subproblem yang ada. Untuk setiap node dipilih sebuah batas bawah LBi dari nilai yang optimal subproblem (P(Xi)) diperkirakan. Jika LBi lebih besar atau sama dengan nilai fungsi objektif dari nilai awal maka kandidat solusi fisibel terbaik telah ditemukan, kemudian subproblem (P(Xi)) dieliminasi dari pertimbangan selanjutnya. Jika tidak, masalah (P(Xi)) disimpan dalam daftar subproblem. Nilai awal diperbarui setiap kali sebuah solusi fisibel terbaik ditemukan. Satu dari node yang tidak dieliminasi, (P(Xi)), dipilih untuk dilakukan pencabangan (branching) menjadi subproblem yang lebih kecil. Proses ini diulang sampai tidak ada subproblem yang tersisa dalam daftar. Berikut ini adalah langkah-langkah penyelesaian suatu masalah minimisasi dengan metode branch-and-bound. Misalkan diberikan masalah INLP (9). • Langkah 0 (Inisialisasi) Didefinisikan L = {P(X)} sebagai subproblem dari fungsi INLP, x* dan v* = f (x) sebagai kandidat solusi optimum masalah INLP. Jika tidak ada solusi fisibel yang tersedia, maka dimisalkan v* = +∞ dan i = 0. • Langkah 1 (Pemilihan node) Jika L = ∅ , proses berhenti dan x* adalah solusi optimum INLP. Jika tidak, pilih salah satu atau lebih subproblem {P(X)} dari L sebagai bagian masalah berikutnya untuk diperiksa. Dinotasikan k sebagai banyaknya subproblem yang dipilih dari Ls = {P(X1),... s P(Xk)}. Misalkan L := L \ L ; i = 1. • Langkah 2 (Bounding) Subproblem P ( X i ) diselesaikan sehingga didapatkan batas bawah LBi . LBi P(X)
takfisibel.
Jika
LBi
≥
=
+∞ jika
v*
proses
6
dilanjutkan ke Langkah 5. Jika tidak, proses dilanjutkan ke Langkah 3.
Daerah fisibel
• Langkah 3 (Solusi fisibel) Simpan solusi fisibel yang ditemukan pada Langkah 2 atau temukan solusi fisibel yang lebih baik dari metode heuristik tertentu. Perbarui kandidat solusi optimal x* dan v*. Jika solusi INLP yang diperoleh lebih baik dari solusi fisibel yang diperoleh sebelumnya, LB j
≥
s
P ( X i ) dari
eliminasi
L yang
memenuhi
v * ; 1 ≤ j < i. Jika i < k ; i = i + 1 maka
Langkah 2 diulangi. Jika tidak, proses dilanjutkan ke Langkah 4 untuk melakukan pencabangan P ( X i ) . •
Langkah 4 (Branching) s
Jika L = ∅ , kembali ke Langkah 1. Jika tidak pilih salah satu subproblem P(Xi) dari s
L dan X i dibagi menjadi subset yang lebih s
s
p
kecil Li = { X 1 ,..., X i }. Eliminasi P(Xi) dari s
Ls dan misalkan L := L U L U Li . Kembali ke s
Langkah 1. •
Langkah 5 (Fathoming) s
Eliminasi P ( X i ) dari L . Jika i < k dengan i = i + 1 maka kembali ke Langkah 2. Jika tidak, kembali ke Langkah 4. (Li & Sun 2006)
Untuk memudahkan pemahaman mengenai metode branch-and-bound diberikan contoh sebagai berikut.
x12 + x2 2
P(X2)
≤ 16,
5 x1 − 3 x2 ≥ −4, x1 , x2 ≥ 0
Langkah awal metode branch and bound adalah menentukan daftar subproblem L = {P(X)} dari kendala yang ada. Solusi yang didapatkan masalah (10) belum memenuhi syarat integer, maka dimisalkan v* = +∞ . Karena L ≠ ∅ maka dibuat subproblemsubproblem baru, dimisalkan sebanyak k = 2 yang memenuhi kendala masalah INLP (10). Subproblem-subproblem tersebut dinotasikan Ls={P(X1), P(X2)}, didefinisikan sebagai berikut: • Subproblem P(X1): masalah INLP (10) ditambah kendala 0 ≤ x2 ≤ 2 ; • Subproblem P(X2): masalah INLP (10) ditambah kendala 2 ≤ x2 ≤ 4 Hal ini diilustrasikan secara grafis pada Gambar 2.
P(X1)
Contoh 2 Misalkan diberikan INLP berikut: 2 2 min v = 2 x1 + x2 − 2 x1 x2 − 5 x1 − 2 x2 terhadap
Gambar 1 Daerah fisibel (daerah yang diarsir) untuk NLP-relaksasi dari INLP (10).
(10)
x1 , x2 integer. Solusi optimum NLP-relaksasi dari masalah INLP (10) adalah x1 = 2.57 , x2 = 3.06 , dan v = − 12.13 (lihat Lampiran 1). Batas atas nilai optimum fungsi objektif masalah (10) adalah v = − 12.13. Daerah fisibel masalah (10) ditunjukkan pada Gambar 1. Solusi optimum berada di daerah fisibel yang berasal dari kendala pertidaksamaan masalah (10).
Gambar 2 Daerah fisibel subproblem P(X1) dan subproblem P(X2) Langkah selanjutnya adalah menghitung batas atas UBi setiap subproblem. UBi merupakan pendekatan nilai fungsi objektif yang terdapat pada subproblem (P(Xi)). Jika subproblem (P(Xi)) memiliki solusi tidak fisibel maka UBi = +∞. Penghitungan semua subproblem menggunakan software LINGO 8.0, ditulis pada Lampiran 2. Hasil semua
7
subproblem masalah INLP (10) ditulis dalam Tabel 1 di bawah ini: Tabel 1 Subproblem-subproblem masalah INLP (10) No Subproblem UBi x 1 P(X1) (2.25,2) −10.13 2 P(X2) (2.57,3.06) −12.13 Langkah berikutnya adalah bounding dan fathoming. Jika UBi ≥ v * maka eliminasi subproblem P(Xi). Perbarui nilai x* dan v* dengan solusi fisibel yang memiliki nilai fungsi objektif terkecil dan memenuhi kendala integer. Batas atas yang dihasilkan pada subproblem P(X1), UB1 = −10.13 tidak lebih dari v* dan solusi yang dihasilkan tidak memenuhi kendala integer, maka dipilih salah satu variabel untuk dasar pencabangan. Misalnya dipilih x1 sebagai dasar pencabangan dari subproblem P(X1). Pencabangan Subproblem P(X1) s 1 2 menghasilkan L1 = { P ( X 1 ), P ( X 1 ), P ( X 13 ), P ( X 14 ) }, yaitu:
• Subproblem P ( X ) : Subproblem P(X1) ditambah kendala 0 ≤ x1 ≤ 1 ; • Subproblem P ( X 12 ) : Subproblem P(X1) ditambah kendala 1 ≤ x1 ≤ 2 ; • Subproblem P ( X 13 ) : Subproblem P(X1) ditambah kendala 2 ≤ x1 ≤ 3 ; • Subproblem P ( X ) : Subproblem P(X1) ditambah kendala 3 ≤ x1 ≤ 4 Solusi dari hasil pencabangan Subproblem P(X1) ditunjukkan dalam Tabel 2. 4 1
Tabel 2 Pencabangan Subproblem P(X1) No Subproblem UBi x P ( X 11 ) 1 (1,2) −7 3 4
P ( X 12 )
(2,2)
−10
3 1
(2.25,2)
−10.125
4 1
(3,2)
−9
P( X ) P( X )
Pencabangan subproblem P ( X 13 ) didefinisikan L13.s = {P ( X 13.1 ), P ( X 13.2 )} , yaitu:
•
3.1
3
Subproblem P ( X 1 ) : Subproblem P ( X 1 ) ditambah kendala 0 ≤ x2 ≤ 1 ;
•
3
Subproblem P ( X 13.2 ) : Subproblem P ( X 1 )
ditambah kendala 1 ≤ x2 ≤ 2 ; Solusi dari hasil pencabangan Subproblem 3
1 1
2
yaitu dihasilkan Subproblem P ( X 12 ) 1 UB1 = −10 < v * , solusi yang dihasilkan memenuhi kendala integer dan lebih baik dari Subproblem P ( X 11 ) sehingga perbarui x* = (2,2) dan v* = −10 sebagai kandidat solusi optimum INLP. Dari Tabel 2, batas atas Subproblem P ( X 13 ) tidak memenuhi syarat eliminasi, karena UB13 = −10.125 < v * . Solusi yang dihasilkan tidak memenuhi kendala integer, maka dipilih salah satu variabel untuk dasar pencabangan. Misalnya x2 sebagai dasar pencabangan subproblem P ( X 13 ) .
Periksa setiap subproblem baru, jika UBi ≥ v * maka eliminasi subproblem (P(Xi)). Dari Tabel 2, solusi yang dihasilkan Subproblem P ( X 11 ) memenuhi kendala integer dan UB11 = −7 < v * , maka perbarui x* = (1,2) dan v* = −7 sebagai kandidat solusi optimum. Langkah selanjutnya adalah memeriksa Subproblem P ( X 12 ) . Batas atas yang
P ( X 1 ) ditunjukkan dalam Tabel 3. 3
Tabel 3 Pencabangan Subproblem P ( X 1 ) No 1
Subproblem P ( X 13.1 )
x (2,1)
2
P ( X 13.2 )
(2.25,2)
UBi −7 −10.125
Dari Tabel 3, batas atas Subproblem P ( X 13.1 ) memenuhi syarat eliminasi karena UB13.1 = −7 > v * , sedangkan batas atas subproblem P ( X 13.2 ) tidak tereliminasi karena UB13.2 = −10.125 < v * . Solusi yang dihasilkan Subproblem P ( X 13.2 ) tidak diperbarui karena tidak memenuhi kendala integer. Selain dari itu Subproblem P ( X 13.2 ) memiliki daerah fisibel yang tidak dapat dipartisi sehingga tidak dicabangkan lagi. Selanjutnya diperiksa Subproblem P ( X 14 ). Batas atas Subproblem P ( X 14 ) , yaitu UB14 = −9 > v * sehingga x* dan v* tidak diperbarui. Subproblem yang belum diperiksa, yaitu Subproblem P(X2). Batas atas Subproblem P(X2) adalah UB2 = −12.13 < v * dan solusi yang dihasilkan tidak memenuhi kendala integer, maka dilakukan pencabangan. Hasil pencabangan Subproblem P(X2) didefinisikan Ls2 = {P ( X 21 ), P ( X 22 ), P ( X 23 ), P ( X 24 )} , yaitu:
8
• Subproblem P ( X 21 ) : Subproblem P(X2) ditambah kendala 0 ≤ x1 ≤ 1 ; • Subproblem P ( X 22 ) : Subproblem P(X2) ditambah kendala 1 ≤ x1 ≤ 2 ; • Subproblem P ( X 23 ) :
Subproblem P(X2)
ditambah kendala 2 ≤ x1 ≤ 3 ; • Subproblem P ( X 24 ) : Subproblem P(X2) ditambah kendala 3 ≤ x1 ≤ 4 . Solusi dari hasil pencabangan Subproblem P(X2) ditunjukkan dalam Tabel 4. Tabel 4 Pencabangan Subproblem P(X2) No Subproblem UBi x 1 P( X 2 ) 1 (1,2) −7 2 3 4
P ( X 22 )
(2,3.33)
−11
3 2
(2.57,3.06)
−12.13
4 2
(3,2.65)
−11.16
P( X ) P( X )
Periksa setiap subproblem baru, jika UBi ≥ v * maka eliminasi subproblem (P(Xi)). Dari Tabel 4, batas atas yang dihasilkan subproblem P ( X 12 ), yaitu UB21 = −7 > v*, sehingga x* dan v* tidak diperbarui. Batas atas P ( X 22 ) , P ( X 23 ) ,dan P ( X 24 ) tidak lebih dari v* dan solusi yang dihasilkan tidak memenuhi kendala integer, maka dilakukan pencabangan dari setiap subproblem. Hasil pencabangan Subproblem P ( X 22 ) , yaitu: • Subproblem P ( X 22.1 ) : Subproblem P ( X 22 ) ditambah kendala 2 ≤ x2 ≤ 3 ; • Subproblem P ( X 22.2 ) : Subproblem P ( X 22 ) ditambah kendala 3 ≤ x2 ≤ 4 . Solusi dari hasil pencabangan Subproblem P ( X 22 ) ditunjukkan dalam Tabel 5. Tabel 5 Pencabangan Subproblem P ( X 22 ) No Subproblem UBi x 2.1 P ( X ) 1 (2,3) −11 2 2 P(X22.2) (2,3) −11 Dari Tabel 5, batas atas Subproblem dan P ( X 22.1 ) P ( X 22.2 ), UB2 2 = −11 < v * sehingga perbarui nilai x* dan v*. Subproblem P ( X 22.1 ) dan P ( X 22.2 ) memiliki daerah fisibel yang tidak dapat dipartisi, maka subproblem ini tidak dicabangkan lagi. Semua variabel subproblem P ( X 22.1 ) dan P ( X 22.2 ) bernilai integer (solusinya memenuhi kendala integer) dan solusi yang dihasilkan pada
subproblem ini lebih baik dari batas atas sebelumnya sehingga solusi pada subproblem ini menjadi kandidat batas atas baru dari solusi INLP (10) yaitu x* = (2,3), v* = −11 . Hasil pencabangan subproblem P ( X 23 ), yaitu: • Subproblem P ( X 23.1 ) : Subproblem P ( X 23 ) ditambah kendala 2 ≤ x2 ≤ 3 ; • Subproblem P ( X 23.2 ) : Subproblem P ( X 23 ) ditambah kendala 3 ≤ x2 ≤ 4 . Solusi dari hasil pencabangan Subproblem P ( X 23 ) ditunjukkan dalam Tabel 6. Tabel 6 Pencabangan Subproblem P ( X 23 ) No Subproblem UBi x P ( X 23.1 ) 1 (2.65,3) −12.10 2
P ( X 23.2 )
(2.57,3.06)
−12.13
Nilai batas bawah Subproblem P(X23.1), dan Subproblem UB2 3.1 = −12.10 < v * sehingga P(X23.2), UB2 3.2 = −12.13 < v * perbarui nilai x* dan v*. Akan tetapi, solusi yang dihasilkan tidak memenuhi kendala integer sehingga x* dan v* tidak diperbarui. Subproblem P ( X 23.1 ) dan P ( X 23.2 ) memiliki daerah fisibel yang tidak dapat dipartisi lagi, maka subproblem ini tidak dicabangkan. Langkah selanjutnya adalah memilih masalah yang belum diselesaikan, yaitu pencabangan Subproblem P ( X 24 ) . Hasil pencabangan Subproblem P ( X 24 ) , yaitu: • Subproblem P ( X 24.1 ) : Subproblem P ( X 24 ) ditambah kendala 2 ≤ x2 ≤ 3 ; • Subproblem P ( X 24.2 ) : Subproblem P ( X 24 ) ditambah kendala 3 ≤ x2 ≤ 4 . Solusi dari hasil pencabangan Subproblem P ( X 24 ) ditunjukkan dalam Tabel 7. Tabel 7 Pencabangan Subproblem P ( X 24 ) No Subproblem UBi x 4.1 P( X 2 ) 1 (3,2.65) −11.17 2
P ( X 24.2 )
Takfisibel
+∞
Nilai batas atas P ( X 24.1 ), UB2 4.1 = −11.17 < v*, sehingga tidak memenuhi syarat eliminasi. Akan tetapi, solusi yang dihasilkan tidak memenuhi kendala integer sehingga x* dan v* tidak diperbarui. Subproblem P ( X 24.1 ) memiliki daerah fisibel yang tidak
9
dapat dipartisi lagi, maka subproblem ini tidak dicabangkan. Subproblem P ( X 24.2 ) memenuhi syarat eliminasi, yaitu UBi ≥ v *. Karena subproblem pada percabangan ini tereliminasi maka x* dan v* tidak diperbarui. Semua subproblem sudah diperiksa dan tidak ada subproblem tersisa dalam daftar
sehingga L = ∅ . Subproblem P ( X 22.1 ) dan P ( X 22.2 ) menghasilkan solusi optimal yang berupa integer. Dengan demikian, solusi optimum pada masalah INLP (10) adalah x1* = 2, x2* = 3, v* = −11.
III PEMODELAN Model penjadwalan pada karya ilmiah ini menggunakan enam parameter utama sebagai penyusun jadwal yaitu; 1. Hari, yaitu hari di mana kegiatan perkuliahan diselenggarakan. Hari = {Senin, Selasa, …, Jumat}. 2. Periode waktu, yaitu waktu kuliah di mana mata kuliah diselenggarakan. Periode waktu = {08.00-08.45, 08.45-09.30, …, (tt+1)}. 3. Kelompok, yaitu kelompok mahasiswa yang menghadiri mata kuliah yang sama berdasarkan program kuliah yang telah tersedia. Kelompok program regular diselenggarakan pukul 08.00-16.00, sedangkan pukul 17.00-22.00 untuk program ekstensi. 4. Dosen, yaitu orang yang mengajar suatu mata kuliah tertentu dalam suatu kelas. Dosen = {Dosen 1, Dosen 2, …, Dosen l}. 5. Mata kuliah, yaitu pelajaran yang diajarkan di kelas oleh seorang dosen. Mata kuliah = {mata kuliah 1, mata kuliah 2, …, mata kuliah m}. 6. Ruangan, yaitu tempat berlangsungnya kegiatan perkuliahan. Ruangan = {ruangan 1, ruangan 2, …, ruangan n}. Jadwal tersebut dibuat sedemikian rupa sehingga memenuhi kendala utama dan kendala tambahan. Kendala utama dalam penjadwalan, yaitu: 1. Semua mata kuliah terjadwalkan di setiap semesternya. 2. Tidak ada overlapping mata kuliah. 3. Dosen tidak boleh mengajar lebih dari satu kelas pada periode waktu yang sama. Sedangkan kendala tambahan, yaitu : 1. Untuk mata kuliah yang tediri atas kuliah dan praktikum, jadwal kuliah dilaksanakan lebih dulu dari jadwal praktikum. 2. 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.
3. Setiap dosen tidak mengajarkan mata kuliah yang bukan bidangnya. 4. Sebagian dosen berharap tidak mengajar pada waktu tertentu. Dalam model penjadwalan karya ilmiah ini terdapat koefisien (bobot) yang merupakan nilai dari ketidakpuasan yang diberikan oleh mahasiswa program regular dan ekstensi terhadap penjadwalan suatu mata kuliah. Penentuan besar kecilnya bobot ditentukan atas keinginan mahasiswa terhadap suatu mata kuliah yang akan dijadwalkan di awal atau di akhir periode waktu. Semakin kecil bobot maka peluang dijadwalkannya mata kuliah yang sesuai dengan keinginan mahasiswa semakin besar. Penentuan bobot yang disebutkan tidaklah mutlak. Bobot yang ada di sini hanyalah sebagai gambaran saja. Sebagai contoh : 1. Mahasiswa program regular mengharapkan mata kuliah dapat diajarkan di awal periode waktu. Oleh karena itu kepuasan mahasiswa ini diberi bobot (koefisien) yang kecil di awal periode waktu dan bobot yang besar di akhir periode waktu, sehingga mata kuliah ini memiliki peluang yang lebih besar untuk dijadwalkan di awal periode waktu (Gambar 3). 2. Mahasiswa program ekstensi mengharapkan mata kuliah diajarkan di akhir periode waktu. Oleh karena itu kepuasan mahasiswa ini diberi bobot (koefisien) yang kecil di akhir periode waktu dan bobot yang besar di awal periode waktu, sehingga mata kuliah ini memiliki peluang yang lebih besar untuk dijadwalkan di akhir periode waktu (Gambar 4).