Bab III Pembuatan Jadwal Pelajaran Sekolah dengan Menggunakan Jaringan Pada bab ini akan dipaparkan cara memodelkan suatu jaringan, sehingga dapat merepresentasikan suatu jadwal pelajaran di sekolah. Tahap pertama yaitu mendefinisikan masalah penjadwalan. Tahap kedua yaitu mendapatkan model jaringan
yang
dapat
merepresentasikan
masalah
penjadwalan.
Proses
mendapatkan aliran maksimum pada jaringan terdapat pada tahap kedua.
3.1
Pendefinisian Masalah Penjadwalan pada Sekolah Menengah
Diberikan himpunan kelas, guru, kelas, dan slot waktu. Bagaimana menyusun suatu jadwal pelajaran yang memenuhi batasan-batasan tertentu ? Terdapat dua jenis batasan yang harus dipenuhi oleh jadwal yaitu batasan yang bersifat keras dan batasan yang bersifat lunak. Batasan keras yaitu batasan-batasan yang harus tercapai. Batasan-batasan keras antara lain : 1. Guru hanya boleh mengajar paling banyak satu pelajaran pada satu kelas pada setiap slot waktu. 2. Setiap kelas hanya menerima satu mata pelajaran pada setiap slot waktu. Batasan yang bersifat lunak yaitu batasan yang tidak harus tercapai. Batasanbatasan yang bersifat lunak antara lain : 1. Setiap kelas menerima pelajaran/guru yang sama paling banyak 2 (dua) jam dalam satu hari.
2. Pelajaran ilmu pasti tidak boleh berurutan diajarkan dalam satu kelas. 3. Seorang guru boleh mengajar paling banyak 6 jam setiap harinya. Jika semakin banyak batasan yang bersifat lunak dapat dipenuhi maka semakin lebih baik jadwal pelajaran yang didapat. Selain batasan-batasan yang diperlukan, juga terdapat asumsi-asumsi, yaitu : 1. Setiap kelas mempunyai banyaknya jam pelajaran yang sama untuk hari yang sama. 2. Setiap kelas dimulai dan diakhiri pada jam yang sama setiap harinya. 3. Setiap guru bisa mengajar pada semua slot waktu. 4. Setiap guru hanya mewakili satu mata pelajaran untuk setiap kelas. 3.2
Pemodelan masalah dengan Jaringan
Graf yang digunakan untuk memodelkan masalah penjadwalan adalah sebuah jaringan. yang memenuhi beberapa kriteria, yaitu : •
Himpunan titik pada jaringan dibagi menjadi beberapa partisi.
•
Setiap busur menghubungkan dua titik yang berasal dari partisi yang berbeda.
Pemodelan masalah penjadwalan dengan menggunakan jaringan dirujuk dari Toadere [5]. Sebagai ilustrasi, jaringan yang digunakan dalam masalah ini diberikan pada Gambar 3.1
17
Gambar 3. 1
3.2.1. Keterangan Model Jaringan A. Partisi dan Titik Himpunan titik pada setiap partisi, mewakili hal-hal yang diperlukan untuk penyusunan jadwal pelajaran, kecuali partisi yang hanya memuat titik s dan titik t. Pada partisi kelas, setiap titiknya mewakili satu kelas. Pada partisi guru, setiap titiknya mewakili seorang guru. Pada partisi hari, setiap titiknya mewakili satu hari pelajaran. Pada partisi jam, setiap titiknya mewakili satu slot jam pelajaran.
18
Khusus pada partisi hari dan partisi jam, kedua partisi ini dibuat sedikit berbeda. Banyaknya titik pada partisi hari adalah banyaknya hari pelajaran dikalikan banyaknya kelas. Partisi hari merupakan gabungan dari beberapa kelompok hari. Setiap kelompok hari memuat titik yang sama banyak. Banyaknya titik pada setiap kelompok hari sama dengan banyaknya hari pelajaran. Misalkan dalam satu minggu ada lima hari pelajaran. Lima hari pelajaran tersebut dimasukkan dalam satu kelompok yaitu kelompok hari, kemudian jika ada n kelas maka harus dibuat n kelompok hari. Penggunaan kelompok hari untuk memenuhi batasan lunak pertama. Gambar 3.2 memberikan ilustrasi tentang kelompok hari.
Partisi Kelas
Partisi Guru
Partisi Hari
Partisi Jam
Kelompok hari ke-1 j1 h11 g1
h12
k1
h13
j2
j3
g2
s
t
h21 k2
h22
g3
j4
j5
h23
Kelompok hari ke-2
j6
Gambar 3. 2
Pada partisi jam, titik pertama adalah jam pertama pada hari senin (jika hari senin adalah hari pelajaran pertama) dan titik terakhir adalah jam terakhir pada hari sabtu (jika hari sabtu adalah hari pelajaran terakhir).
19
B. Pelabelan titik pada jaringan Setiap titik pada jaringan harus diberi label. Pelabelan dimulai dari titik s yang diberi label “1”. Titik-titik pada partisi kelas mempunyai label “2” sampai dengan “M1 + 1”, dengan M1 adalah banyaknya titik pada partisi kelas. Titik-titik pada partisi guru mempunyai label “M1 + 2” sampai dengan “M1 + M2 + 1”, dengan M2 adalah banyaknya titik di partisi guru. Label titik-titik yang menyatakan guru yang mengajar mata pelajaran eksak dibuat tidak berurutan. Hal ini bertujuan untuk memenuhi batasan lunak kedua. Titik-titik pada partisi hari mempunyai label “M1 + M2 + 2” sampai dengan “M1 + M2 + M3 + 1”, dengan M3 adalah banyaknya titik di partisi hari. Titik –titik pada partisi jam mempunyai urutan label “M1 + M2 + M3 + 2” sampai dengan “M1 + M2 + M3 + M4 + 1”, dengan M4 adalah banyaknya titik di partisi jam. Label titik t adalah banyaknya titik pada jaringan. Gambar 3.3 memberikan ilustrasi pemberian label.
Partisi Kelas
Partisi Guru
Partisi Hari
Partisi Jam
2
M1+2
M1+M2 +2
M1+M2 +M3+2
total
1
M1+1
M1+M2 +1
M1+M2 +M3+1
M1+M2 +M3+ M4+1
Gambar 3. 3
Pada bagian A diketahui bahwa partisi hari terdiri dari beberapa kelompok hari. Misalkan jaringan N mempunyai titik pada partisi hari sebanyak a × b , dengan a banyak kelas dan b banyaknya hari pelajaran. Misalkan Li adalah kelompok hari
20
ke i, dengan 1 ≤ i ≤ a dan h j adalah hari pelajaran ke j, dengan 1 ≤ j ≤ b . Label “M1 + M2 + 2” diberikan pada hari pertama L1 dan Label “M1 + M2 + M3 + 1” diberikan pada hari terakhir La . Aturan pemberian label setiap pada partisi hari dapat menggunakan rumus seperti dibawah
X = ((i − 1) * b) + M 1 + M 2 + 2 + (j − 1) , dengan X menyatakan label yang diberikan pada titik yang berada pada kelompok hari ke-i dan menyatakan hari ke-j. C. Pendefinisian Busur dan Kapasitas
Jaringan seperti yang diberikan Gambar 3.1 mempunyai tiga buah warna yang diberikan pada busur. Ketiga warna tersebut mewakili himpunan suatu busur pada jaringan.
Warna
hitam
menyatakan
himpunan
busur
yang
busurnya
menghubungkan dua titik pada partisi yang berdekatan, selanjutnya disebut himpunan busur R. Warna merah menyatakan himpunan busur yang busurnya menghubungkan titik pada partisi kelas dengan titik pada partisi jam, selanjutnya disebut himpunan busur S. Warna biru menyatakan himpunan busur yang busurnya menghubungkan titik pada partisi guru dengan titik pada partisi jam, selanjutnya disebut himpunan busur T. Pemberian busur pada S dan T diperlukan untuk mencapai semua batasan keras dan membantu proses pencarian augmenting path. Titik s bertetangga dengan semua titik pada partisi kelas, dengan kapasitas setiap busur sebesar total jam belajar dalam satu minggu.
21
Titik ki pada partisi kelas bertetangga titik gj pada partisi guru jika guru gj mengajar kelas ki. Kapasitas busur ini menyatakan total jam mengajar guru gj pada kelas ki. Selain itu setiap titik pada partisi kelas bertetangga dengan semua titik pada partisi jam, dengan kapasitas setiap busur sebesar 1 (satu). Setiap titik pada partisi guru bertetangga dengan semua titik pada partisi hari, dengan kapasitas setiap busur sebesar maksimum jam mengajar seorang guru pada satu kelas dalam satu hari. Kapasitas setiap busur ini adalah dua. Pemilihan nilai dua disesuaikan dengan batasan lunak pertama. Setiap titik pada partisi guru juga bertetangga dengan semua titik di partisi jam, dengan kapasitas sebesar 1 (satu). Setiap titik hi pada partisi hari bertetangga dengan jk titik pada partisi jam jika slot jam jk termuat dalam hi. Kapasitas setiap busur sebesar 1 (satu). Sebagai contoh : jika hari senin mempunyai 7 jam pelajaran maka titik yang mewakili hari senin terhubung dengan dengan titik berlabel “M1 + M2 + M3 + 2” sampai “M1 + M2 + M3 + 8”. Selanjutnya, jika hari selasa mempunyai 8 jam pelajaran maka hari selasa terhubung dengan dengan titik berlabel “M1 + M2 + M3 + 9” sampai “M1 + M2 + M3 + 16”. Jika hari h bertetangga dengan jam j maka hari h disebut bersesuaian dengan jam j atau jam j termuat dalam hari h. Setiap titik pada partisi jam bertetangga dengan titik t dengan kapasitas lebih besar dari total jam pelajaran. Hal ini untuk mempermudah pencarian augmenting path.
22
3.2.2. Membuat aliran menjadi maksimum
Model jaringan yang didapat, kemudian diberi aliran sepanjang augmenting path. Setiap augmenting path menyatakan posisi pada jadwal pelajaran, sehingga dengan mendapatkan semua augmenting path dapat disusun jadwal pelajaran. Aliran pada jaringan dibuat menjadi maksimum dengan menggunakan algoritma Ford-Fulkerson. Aliran mencapai maksimum ketika tidak terdapat lagi augmenting path. Augmenting path hanya melintasi busur yang terdapat pada R. Pada jaringan ada empat partisi ditambah dua titik ujung sehingga didapatkan 5 busur untuk satu augmenting path.. Busur pertama adalah busur yang menghubungkan titik s dengan titik di partisi kelas. Busur kedua adalah busur yang menghubungkan titik pada partisi kelas dengan titik pada partisi guru. Busur ketiga adalah busur yang menghubungkan titik pada partisi guru dengan titik pada partisi hari. Busur keempat adalah busur yang menghubungkan titik pada partisi hari dengan titik pada partisi jam. Busur kelima adalah busur yang menghubungkan titik pada partisi jam dengan titik t. Metode untuk mendapatkan augmenting path adalah dengan mencari satu persatu busurnya, dimulai dari mendapatkan busur pertama hingga dapat busur kelima. Proses dasar pencarian setiap busur sebagai berikut : •
Pencarian busur pertama diawali dengan busur yang mempunyai kepala dengan label terkecil. Misalkan busur (s, k1) dan busur (s, k2) adalah busurbusur yang dapat dipilih, jika label k1 lebih kecil dari label k2 maka busur (s, k1) yang akan dipilih menjadi busur pertama.
23
•
Pencarian busur berikutnya sama seperti pada busur pertama, tetapi dimulai dengan label ekor sama seperti pada label kepala busur sebelumnya.
Prosedur diatas dikatakan dasar karena pada pencarian busur ketiga dan busur keempat ada beberapa prosedur tambahan atau perubahan metode. Pencarian busur ketiga dimulai dari busur yang mempunyai label kepala terkecil pada kelompok hari yang bersesuaian dengan kelas k. Kelas k merupakan kepala pada busur pertama atau ekor pada busur kedua. Misalkan titik yang menyatakan kelas k mempunyai label terbesar kedua pada partisi kelas. Busur ketiga yang akan dicari mempunyai label kepala pada kelompok hari ke-2 dan dimulai dari label terkecil pada kelompok hari tersebut. Pencarian pada busur keempat dimulai pada busur yang mempunyai label kepala lebih besar dari label kepala pada busur keempat pada augmenting path sebelumnya. Jika tidak ada yang lebih besar maka pencarian dimulai dari busur kepala yang mempunyai label kepala paling kecil. Pada saat mencari busur keempat akan ditemukan beberapa kasus yang berkaitan dengan slot jam sehingga tidak dapat memenuhi batasan keras yang pertama. Misalkan A(K) adalah himpunan slot jam yang belum terpakai oleh kelas k dan A(G) himpunan slot jam masih bisa digunakan oleh guru g untuk semua kelas.
Guru g merupakan kepala dari busur kedua dan kelas k merupakan kepala dari busur pertama pada augmenting path p yang akan dicari. Masalah terjadi jika A(G) ∩ A(K) = φ dengan A(G) ≠ φ dan A(K) ≠ φ . Jika hal ini terjadi, lakukan
proses dibawah. Jika tidak terjadi lanjutkan mencari langsung busur keempat .
24
a. Cari slot jam j1 yang tersisa untuk kelas k beserta hari h1 yang bersesuaian dengan slot jam j1 b. Cari slot jam j2 yang telah terpakai oleh kelas k beserta hari h2 yang bersesuaian dengan slot jam j2 nya, tetapi slot jam dan hari tersebut bisa digunakan oleh guru g. c. Cari augmenting path sebelumnya yang memuat kelas k, g2, h2, dan j2, dengan g2 bisa memakai slot jam j1. Guru g2 adalah guru yang telah habis jam mengajarnya untuk kelas k. d. Lakukan proses penukaran, yaitu menukar hari h2 dan slot jam j2 augmenting path yang lama dengan hari h1 dan slot jam j1. Hari dan slot jam pada augmenting path p adalah hari h2 dan slot jam j2. e. Cari augmenting path berikutnya jika masih ada augmenting path pada jaringan sisa. Jika guru g2 tidak dapat memakai slot jam yang tersisa untuk kelas k maka gunakan augmenting path lama yang memuat kelas k2 dengan label lebih kecil dari label kelas k. Proses yang terjadi adalah sebagai berikut : a. Cari slot jam j1 yang tersisa untuk kelas k beserta hari h1 yang bersesuaian dengan slot jam j1 b. Cari slot jam j2 yang telah terpakai oleh guru g pada kelas k2 beserta hari h2 yang bersesuaian dengan slot jam j2 nya. c. Cari augmenting path p1 sebelumnya yang memuat kelas k, g2, h2, dan j2, dengan g2 bisa memakai slot jam j1 dan augmenting path p2 sebelumnya yang memuat kelas k2, g, h2, dan j2.
25
d. Cari augmenting path p3 sebelumnya yang memuat kelas k2, g3, h3, dan j3. Guru g3 adalah guru yang telah habis jam mengajarnya untuk kelas k2 dan bisa menggunakan slot jam j2. Slot jam j3 adalah slot jam yang bisa dipakai oleh guru g dan hari h3 adalah hari yang bersesuaian dengan slot jam j3. e. Tukar hari h3 dan slot jam j3 pada augmenting path p3 dengan hari h2 dan slot jam j2. Tukar hari h2 dan slot jam j2 pada augmenting path p2 dengan hari h3 dan slot jam j3. f. Tukar hari h2 dan slot jam j2 pada augmenting path p1 dengan hari h1 dan slot jam j1. Hari dan slot jam yang dipakai oleh guru g pada augmenting path p adalah hari h2 dan slot jam j2. g. Teruskan pencarian pada augmenting path berikutnya jika masih ada augmenting path pada jaringan sisa. Sebagai ilustrasi, berikut ini diberikan suatu data yang akan dibuat menjadi jadwal pelajaran : •
Banyaknya kelas ada 2 (dua) dan banyaknya guru ada 3 (tiga).
•
Total jam pelajaran setiap kelas selama satu minggu adalah 6 jam.
•
Distribusi jam mengajar guru setiap kelas adalah sebagai berikut :
Kelas k1
Kelas k2
Guru g1
1 jam
1 jam
Guru g2
2 jam
2 jam
Guru g3
3 jam
3 jam
•
Setiap guru dibatasi hanya mengajar dua jam setiap hari untuk setiap kelas.
•
Banyaknya hari pelajaran selama satu minggu adalah 3 (tiga) hari.
•
Hari pertama memuat jam ke-1 dan jam ke-2.
26
•
Hari kedua memuat jam ke-3 dan jam ke-4.
•
Hari ketiga memuat jam ke-5 dan jam ke-6.
Gambar 3.4 merupakan gambar jaringan dengan menggunakan data-data diatas.
Gambar 3. 4
Proses mendapatkan aliran maksimum untuk jaringan pada gambar 3.2 dijelaskan dengan menggunakan ilustrasi gambar. Keterangan gambar-gambar adalah sebagai berikut : •
Panah tak putus menyatakan busur yang mempunyai kapasitas lebih besar dari 0 (nol).
•
Panah putus-putus menyatakan busur yang mempunyai kapasitas 0 (nol).
•
Panah hitam tebal menyatakan busur yang termuat pada suatu augmenting path.
27
•
Panah biru tebal dan panah merah tebal hanya mempertegas bahwa kelas k dan guru g masih dapat menggunakan slot jam yang termuat pada augmenting path.
Partisi Kelas
Partisi Guru
Partisi Hari
j1 j2 j3 j4 j5 j6 j1 j2 j3 j4 j5 j6
Partisi Jam
1 1
j1 j2 j3 h11 g1 k1 6
j1
1
2
1 2 3
j2
h12
10 10
h13
j3 10
g2
s
t 10
j4
h21
6 k2
1 2 3 g3
10 10
h22
j5
h23 j6
j4 j5 j6
j1 j2 j3 j4 j5 j6 j1 j2 j3 j4 j5 j6
Gambar 3. 5 Jaringan sisa ke-1 dan augmenting path ke-1
Augmenting path ke-1 : s → k1 → g1 → h1 → j1 → t Jam yang belum terpakai
Jam yang telah terpakai
Kelas k1
{2, 3, 4, 5, 6}
{1}
Kelas k2
{1, 2, 3, 4, 5, 6}
{}
Guru g1
{2, 3, 4, 5, 6}
{1}
Guru g2
{1, 2, 3, 4, 5, 6}
{}
Guru g3
{1, 2, 3, 4, 5, 6}
{}
28
Partisi Kelas
Partisi Guru
Partisi Hari
Partisi Jam
j1 j2 j3 j4 j5 j6 j1 j2 j3 j4 j5 j6
j1 j2 j3
j1 h11 g1
k1 5
1
1
j2
h12
9
2 3
10
2
h13
j3 10
g2
s
t 10
j4
h21
6 k2
1 2 3 g3
10 10
h22
j5
h23 j6
j4 j5 j6
j1 j2 j3 j4 j5 j6 j1 j2 j3 j4 j5 j6
Gambar 3. 6 Jaringan sisa ke-2 dan augmenting path ke-2
Augmenting path ke-2 : s → k1 → g 2 → h1 → j2 → t Jam yang belum terpakai
Jam yang telah terpakai
Kelas k1
{ 3, 4, 5, 6}
{1,2}
Kelas k2
{1, 2, 3, 4, 5, 6}
{}
Guru g1
{2, 3, 4, 5, 6}
{1}
Guru g2
{1, 3, 4, 5, 6}
{2}
Guru g3
{1, 2, 3, 4, 5, 6}
{}
29
Partisi Kelas
Partisi Guru
Partisi Hari
Partisi Jam
j1 j2 j3 j4 j5 j6 j1 j2 j 3 j4 j5 j6 j1 j2 j3
j1 h11 g1
k1 4
1
j2
h12
1 3
9 1
12
9
h13
j3 10
g2
s
t 10
6 k2
j4
h21
1 2 3
10 10
h22
g3
j5
h23 j6
j4 j5 j6 j1 j2 j3 j4 j5 j6 j1 j2 j3 j4 j5 j6
Gambar 3. 7 Jaringan sisa ke-3 dan augmenting path ke-3
Augmenting path ke-3 : s → k1 → g 2 → h2 → j3 → t Jam yang belum terpakai
Jam yang telah terpakai
Kelas k1
{ 4, 5, 6}
{1, 2, 3}
Kelas k2
{1, 2, 3, 4, 5, 6}
{}
Guru g1
{2, 3, 4, 5, 6}
{1}
Guru g2
{1, 4, 5, 6}
{2, 3}
Guru g3
{1, 2, 3, 4, 5, 6}
{}
30
Partisi Kelas
Partisi Guru
Partisi Hari
Partisi Jam
j1 j2 j3 j4 j5 j6 j1 j2 j3 j4 j5 j6
j1 j2 j3
j1 h11 g1
1 9
1
3
3
j2
h12
k1
11
9
h13
j3 9
g2
s
t 10
j4
h21
6 k2
1 2 3
10
2
10
h22
g3
j5
h23 j6
j4 j5 j6
j1 j2 j3 j4 j5 j6 j1 j2 j3 j4 j5 j6
Gambar 3. 8 Jaringan sisa ke-4 dan augmenting path ke-4
Augmenting path ke-4 : s → k1 → g3 → h2 → j4 → t Jam yang belum terpakai
Jam yang telah terpakai
Kelas k1
{ 5, 6}
{1, 2, 3, 4}
Kelas k2
{1, 2, 3, 4, 5, 6}
{}
Guru g1
{2, 3, 4, 5, 6}
{1}
Guru g2
{1, 4, 5, 6}
{2, 3}
Guru g3
{1, 2, 3, 5, 6}
{4}
31
Partisi Kelas
Partisi Guru
Partisi Hari
Partisi Jam
j1 j2 j3 j4 j5 j6 j1 j2 j 3 j4 j5 j6 j1 j2 j3
j1 h11 g1
1
j2
h12
k1
9
2
2
11
6 k2
j3 9
g2
s
9
h13
t
1
9
j4
h21
1 2 3
10
12
10
h22
g3
j5
h23 j6
j4 j5 j6 j1 j2 j3 j4 j5 j6 j1 j2 j3 j4 j5 j6
Gambar 3. 9 Jaringan sisa ke-5 dan augmenting path ke-5
Augmenting path ke-5 : s → k1 → g3 → h3 → j5 → t Jam yang belum terpakai
Jam yang telah terpakai
Kelas k1
{6}
{1, 2, 3, 4, 5}
Kelas k2
{1, 2, 3, 4, 5, 6}
{}
Guru g1
{2, 3, 4, 5, 6}
{1}
Guru g2
{1, 4, 5, 6}
{2, 3}
Guru g3
{1, 2, 3, 6}
{4, 5}
32
Partisi Kelas
Partisi Guru
Partisi Hari
Partisi Jam
j1 j2 j3 j4 j5 j6 j1 j2 j3 j4 j5 j6
j1 j2 j3
j1 h11 g1
1 j2
h12
k1
9
1
1
9
11
h13
j3 9
g2
s
t 9
h21
6 k2
1 2 3
1
j4 9
11
10
h22
g3
j5
h23 j6
j4 j5 j6
j1 j2 j3 j4 j5 j6 j1 j2 j3 j4 j5 j6
Gambar 3. 10 Jaringan sisa ke-6 dan augmenting path ke-6
Augmenting path ke-6 : s → k1 → g3 → h3 → j6 → t Jam yang belum terpakai
Jam yang telah terpakai
Kelas k1
{}
{1, 2, 3, 4, 5, 6}
Kelas k2
{1, 2, 3, 4, 5, 6}
{}
Guru g1
{2, 3, 4, 5, 6}
{1}
Guru g2
{1, 4, 5, 6}
{2, 3}
Guru g3
{1, 2, 3}
{4, 5, 6}
33
Partisi Kelas
Partisi Guru
Partisi Hari
Partisi Jam
j1 j2 j3 j4 j5 j6 j1 j2 j3 j4 j5 j6
j1 j2 j3
j1 h11 g1
k1
1 j2
h12
9
2 9
11
h13
j3
1
9
g2
s
t 9
j4
h21
6 k2
1 2 3
9
1
9
h22
g3
j5
h23 j6
j4 j5 j6
j1 j2 j3 j4 j5 j6 j1 j2 j3 j4 j5 j6
Gambar 3. 11 Jaringan sisa ke-7 dan augmenting path ke-7
Augmenting path ke-7 : s → k2 → g1 → h1 → j2 → t Jam yang belum terpakai
Jam yang telah terpakai
Kelas k1
{}
{1, 2, 3, 4, 5, 6}
Kelas k2
{1, 3, 4, 5, 6}
{2}
Guru g1
{3, 4, 5, 6}
{1, 2}
Guru g2
{1, 4, 5, 6}
{2, 3}
Guru g3
{1, 2, 3}
{4, 5, 6}
34
Partisi Kelas
Partisi Guru
Partisi Hari
Partisi Jam
j1 j2 j3 j4 j5 j6 j1 j2 j3 j4 j5 j6
j1 j2 j3
j1 h11 g1
k1
1 j2
h12
9
1 8
h13
11
j3 9
g2
s
t 9
5
2 k2
j4
h21
9
1
2 3
1
9
h22
g3
j5
h23 j6
j4 j5 j6
j1 j2 j3 j4 j5 j6 j1 j2 j3 j4 j5 j6
Gambar 3. 12 Jaringan sisa ke-8 dan augmenting path ke-8
Augmenting path ke-8 : s → k2 → g 2 → h2 → j4 → t Jam yang belum terpakai
Jam yang telah terpakai
Kelas k1
{}
{1, 2, 3, 4, 5, 6}
Kelas k2
{1, 3, 5, 6}
{2, 4}
Guru g1
{3, 4, 5, 6}
{1, 2}
Guru g2
{1, 5, 6}
{2, 3, 4}
Guru g3
{1, 2, 3}
{4, 5, 6}
35
Partisi Kelas
Partisi Guru
Partisi Hari
Partisi Jam
j1 j2 j3 j4 j5 j6 j1 j2 j3 j4 j5 j6
j1 j2 j3
j1 h11 g1
k1
1 j2
h12
9
1 8
h13
11
j3 9
g2
s
t 8
4
1 k2
j4
h21
9
1
1 3
2
9
h22
g3
j5 1
h23 j6
j4 j5 j6
j1 j2 j3 j4 j5 j6 j1 j2 j3 j4 j5 j6
Gambar 3. 13 Jaringan sisa ke-9 dan augmenting path ke-9
Augmenting path ke-9 : s → k2 → g 2 → h3 → j5 → t Jam yang belum terpakai
Jam yang telah terpakai
Kelas k1
{}
{1, 2, 3, 4, 5, 6}
Kelas k2
{1, 3, 6}
{2, 4, 5}
Guru g1
{3, 4, 5, 6}
{1, 2}
Guru g2
{1, 6}
{2, 3, 4, 5}
Guru g3
{1, 2, 3}
{4, 5, 6}
36
Partisi Kelas
Partisi Guru
Partisi Hari
Partisi Jam
j1 j2 j3 j4 j5 j6 j1 j2 j3 j4 j5 j6
j1 j2 j3
j1 h11 g1
k1
1 j2
h12 1
9
1 8
h13
11
j3 9
g2
s
t 8
3
j4
h21
1
8
1 k2
1
3
1
g3
9
h22
j5
h23 j6
j4 j5 j6
j1 j2 j3 j4 j5 j6 j1 j2 j3 j4 j5 j6
Gambar 3. 14 Jaringan sisa ke-10 dan augmenting path ke-10
Augmenting path ke-10 : s → k2 → g3 → h1 → j1 → t Jam yang belum terpakai
Jam yang telah terpakai
Kelas k1
{}
{1, 2, 3, 4, 5, 6}
Kelas k2
{3, 6}
{1, 2, 4, 5}
Guru g1
{3, 4, 5, 6}
{1, 2}
Guru g2
{1, 6}
{2, 3, 4, 5}
Guru g3
{2, 3}
{1, 4, 5, 6}
37
Partisi Kelas
Partisi Guru
Partisi Hari
Partisi Jam
j1 j2 j3 j4 j5 j6 j1 j2 j3 j4 j5 j6
j1 j2 j3
j1 h11 g1
k1
1 j2
h12
8
1 8
h13
11
j3 9
g2
s
t 8
2
h21
1
1
j4 8
1 k2
1
2
1 2
g3
9
h22
j5
h23 j6
j4 j5 j6
j1 j2 j3 j4 j5 j6 j1 j2 j3 j4 j5 j6
Gambar 3. 15 Jaringan sisa ke-11 dan augmenting path ke-11
Augmenting path ke-11 : s → k2 → g3 → h2 → j3 → t Jam yang belum terpakai
Jam yang telah terpakai
Kelas k1
{}
{1, 2, 3, 4, 5, 6}
Kelas k2
{6}
{1, 2, 3, 4, 5}
Guru g1
{3, 4, 5, 6}
{1, 2}
Guru g2
{1, 6}
{2, 3, 4, 5}
Guru g3
{2}
{1, 3, 4, 5, 6}
38
Partisi Kelas
Partisi Guru
Partisi Hari
Partisi Jam
j1 j2 j3 j4 j5 j6 j1 j2 j 3 j4 j5 j6 j1 j2 j3
j1 h11 g1
k1
1
j2
h12
8
2
8+1
h13
11
0+1
j3 8
g2
s
t
1 1 k2
1 g3
1
1+1 1 1
1
h21
8
j4 8 9
h22
j5
2 h23 j6
j4 j5 j6 j1 j2 j3 j4 j5 j6 j1 j2 j3 j4 j5 j6
0+1
Gambar 3. 16 Jaringan sisa ke-12 dan augmenting path ke-12
Pada tabel sebelumnya dapat dilihat sebagai berikut : •
Slot jam yang tersisa untuk kelas k2 hanya jam ke-6
•
Guru yang masih mempunyai jam mengajar untuk kelas k2 yaitu guru g3
•
Slot jam yang masih bisa dipakai oleh guru g3 hanya jam ke-2
Dari keterangan diatas dapat disimpulkan bahwa guru g3 tidak dapat mengajar kelas k2. Dengan demikian, supaya kelas k2 dapat mempunyai total jam pelajaran sebanyak 6 jam dilakukan penggantian titik pada augmenting path sebelumnya. Proses penggantiannya sebagai berikut : •
Slot jam masih bisa digunakan oleh kelas k2 adalah jam ke-6
39
•
Slot jam yang telah terpakai oleh kelas k2 adalah selain jam ke-6. Ternyata diantara slot-slot jam tersebut, ada yang bisa digunakan oleh guru g3 yaitu jam ke-2.
•
Cari augmenting path yang memuat jam ke-2 dan guru yang memakai slot jam tersebut. Guru g harus bisa memakai jam ke-6. Pencarian yang didapat adalah augmenting path ke-7 dengan guru g1.
•
Tukar hari dan slot jam pada augmenting path ke-7 dengan hari h3 dan jam ke-6. Hari dan slot jam pada augmenting path ke-12 adalah hari h1 dan jam ke-2.
•
Dari proses diatas didapat 2 (dua) augmenting path baru, yaitu :
Augmenting path ke-7 (yang telah diperbaharui) : s → k2 → g1 → h3 → j6 → t Augmenting path ke-12 : s → k2 → g3 → h1 → j2 → t Jam yang belum terpakai
Jam yang telah terpakai
Kelas k1
{}
{1, 2, 3, 4, 5, 6}
Kelas k2
{}
{1, 2, 3, 4, 5, 6}
Guru g1
{2, 3, 4, 5, 6}
{1, 6}
Guru g2
{1, 6}
{2, 3, 4, 5}
Guru g3
{}
{1, 2, 3, 4, 5, 6}
40
Partisi Kelas
Partisi Guru
Partisi Hari
Partisi Jam
j1 j2 j3 j4 j5 j6 j1 j2 j3 j4 j5 j6
j1 j2 j3
j1 h11 g1
k1
1 j2
h12
8
1 8
h13
11
j3 8
g2
s
t 8
j4
h21
1
8
1 k2
1 g3
1 1
8
h22
j5
2 h23 j6
j4 j5 j6
j1 j2 j3 j4 j5 j6
0+1
j1 j2 j3 j4 j5 j6
Gambar 3. 17 Jaringan sisa terakhir dan aliran jaringan yang maksimum
Semua augmenting path yang didapat dikumpulkan ke dalam satu tabel (tabel 3.1) yang hanya memuat kelas, guru, hari, dan slot jam. Tabel 3. 1
Augmenting
Kelas
Guru
Hari
Jam
1
Kelas k1
Guru g1
Hari h1
Jam j1
2
Kelas k1
Guru g2
Hari h1
Jam j2
3
Kelas k1
Guru g2
Hari h2
Jam j3
4
Kelas k1
Guru g3
Hari h2
Jam j4
5
Kelas k1
Guru g3
Hari h3
Jam j5
6
Kelas k1
Guru g3
Hari h3
Jam j6
7
Kelas k2
Guru g1
Hari h3
Jam j6
Path ke -
41
8
Kelas k2
Guru g2
Hari h2
Jam j4
9
Kelas k2
Guru g2
Hari h3
Jam j5
10
Kelas k2
Guru g3
Hari h1
Jam j1
11
Kelas k2
Guru g3
Hari h2
Jam j3
12
Kelas k2
Guru g3
Hari h1
Jam j2
42
