PEMBUATAN JADWAL PELAJARAN DENGAN MENGGUNAKAN ALGORITMA FORD-FULKERSON
TUGAS AKHIR Diajukan untuk Memenuhi Persyaratan Sidang Sarjana Program Studi Matematika
Oleh Danny Chan 10100038
Program Studi Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Institut Teknologi Bandung 2007
PEMBUATAN JADWAL PELAJARAN DENGAN MENGGUNAKAN ALGORITMA FORD-FULKERSON
TUGAS AKHIR Diajukan untuk Memenuhi Persyaratan Sidang Sarjana Program Studi Matematika
Oleh Danny Chan 10100038
Telah diperiksa dan disetujui : Bandung, Juli 2007 Pembimbing Tugas Akhir,
Dr. Hilda Assiyatun
Program Studi Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Institut Teknologi Bandung 2007
Abstrak Jaringan adalah salah satu tipe graf berarah dengan dua subhimpunan titik yang penting yaitu subhimpunan titik sumber dan subhimpunan titik tujuan. Setiap busur pada jaringan mempunyai bobot yang disebut kapasitas. Jaringan dapat dilalui aliran dari titik sumber menuju titik tujuan. Aliran pada jaringan dibuat maksimum. Metode yang digunakan untuk membuat aliran maksimum adalah dengan menggunakan algoritma Ford-Fulkerson. Pada tugas akhir ini akan dikaji masalah penjadwalan pada sekolah menengah dengan memanfaatkan jaringan serta algoritma Ford-Fulkerson. Sebuah jaringan dikonstruksi sedemikian rupa sehingga dapat merepresentasikan masalah penjadwalan. Aliran maksimum yang didapat pada jaringan ini merepresentasikan suatu jadwal pelajaran. Sebagai bagian dari tugas akhir ini, dibangun program pembuatan jadwal pelajaran dengan dasar algoritma Ford-Fulkerson.
Abstract
A network is a type of directed graphs with two distinguished vertices, a source and a sink. Every arch on a network has a weight, which is called capacity. In network we are interested in finding a maximum flow from the source to the sink. The Ford-Fulkerson algorithm can be used to find a maximum flow in a network. In this final project we study scheduling problem in high schools. A network is constructed so that it can represent the scheduling problem. A maximum flow obtained on this network represents a school timetable. As a part of this final project, we build a computer program to generate school timetables. This program is constructed based on the Ford-Fulkerson algorithm.
.
Prakata Bismillahirohmanirrohim Segala puji dan syukur hanya kepada Allah SWT yang menciptakan alam semesta. Limpahan kasih dan sayang-Nya telah memberi petunjuk, kekuatan, dan kemudahan kepada penulis.
Penulis banyak mendapat bimbingan, dorongan, dan motivasi dari berbagai pihak dalam menyelesaikan tugas akhir ini. Ucapan terima kasih dengan ikhlas dan kerendahan hati penulis sampaikan kepada :
1. Dr. Hilda Assiyatun, selaku dosen pembimbing yang telah banyak memberikan
saran,
pemikiran,
dan
masukan
bagi
penulis
dalam
menyelesaikan tugas akhir ini dengan baik. 2. Mama dan Papa yang selalu memberikan doa dan dengan sabar menunggu kelulusan anaknya. 3. Dr. M. Salman dan yang bersedia meluangkan waktunya sebagai dosen penguji dalam seminar I dan seminar II. 4. Dr. Nana Nawawi Gaos, selaku dosen penguji dalam seminar II. 5. Koko Martono, M.si, selaku dosen wali yang sering memberi masukan dan arahan kepada penulis 6. Seluruh dosen di Program Studi Matematika, FMIPA, Institut Teknologi Bandung. 7. Seluruh pegawai perpustakaan dan seluruh staf tata usaha telah sangat membantu dalam pemberian informasi dan administrasi kuliah .
8. Kakak-kakakku yang sering bertanya “Kapan kamu wisuda ?”. Adik-adikku yang sering memberikan doa. 9. Husni Mubarok dan Reindra Jumara, teman untuk berdiskusi. 10. Semua pihak yang tidak dapat dituliskan satu persatu disini namun tidak kecil andilnya dalam membantu penyelesaian tugas akhir ini baik secara langsung maupun tidak langsung. Semoga Allah SWT selalu memberikan rahmat dan kasih sayang-Nya kepada semua pihak yang dengan ikhlas membantu penulis dalam menyelesaikan tugas akhir ini. Akhir kata, penulis berharap semoga tugas akhir ini dapat bermanfaat.
Bandung, Juli 2007
Penulis
Daftar Isi Abstrak ……………………………………………………….……………...…….
i
Abstract ………………………………………………………………...………….
ii
Prakata …………………………………………………………….…...…………..
iii
Daftar Isi ……...………………………………………………….............………...
v
Bab 1 Pendahuluan ..............................................................................................
1
Bab 2 Konsep Dasar ............................................................................................
5
2.1 Graf ............................................................................................................
5
2.2 Subgraf ......................................................................................................
6
2.3
Lintasan (Path) .........................................................................................
7
2.4 Graf Berarah dan Subgraf Berarah ........................................................
8
2.5 Jaringan (Network) ...................................................................................
10
2.6 Aliran Jaringan (Network Flow) ............................................................
11
2.7 Jaringan Sisa (Residual Network) ..........................................................
12
2.8
Augmenting Path dan Aliran Maksimum .............................................
12
2.9 Algoritma Ford-Fulkerson ......................................................................
12
Bab 3 Pembuatan Jadwal Pelajaran Sekolah dengan Menggunakan Jaringan .......................................................................................................
16
3.1 Pendefinisian Masalah Penjadwalan pada Sekolah Menengah .........
16
3.2 Pemodelan Masalah dengan Jaringan ………………………………...
17
Bab 4 Aplikasi Program Pembuatan Jadwal ……………………………….
43
4.1
Lembar Masukan Data ……………………...………………………….
44
4.2
Lembar Proses ..........................................................................................
47
Bab 5 Kesimpulan ..................................................................................................
52
Daftar Pustaka ........................................................................................................
55
Lampiran ..................................................................................................................
56
Lampiran A. Data-data di SMAN 2 Bandung yang digunakan sebagai masukan data ......................................................................................................
56
Lampiran B.Jadwal per Kelas dengan Urutan Jam .......................................
67
Lampiran C. Source Code Pencarian Augmenting Path ..............................
97
