BAB 1

PENDAHULUAN

1.1 Latar Belakang

Masalah penjadualan terlihat seperti masalah biasa yang dapat diselesaikan dengan

metoda pemikiran biasa, akan tetapi jika sudah dalam jumlah data yang banyak akan

memerlukan banyak waktu untuk menyelesaikannya, contohnya penjadualan mata

kuliah. Jumlah data dalam penjadualan mata kuliah sangat banyak dan saling

berkaitan antara satu data dengan data lainnya dan adanya berbagai batasan sehingga

sulit untuk melakukan proses penjadualan secara cepat. Permasalahan semakin

bertambah dengan ketersediaan ruang kelas yang terbatas disertai banyaknya mata

kuliah yang harus ditempatkan, terlebih lagi jika hasil penjadualan harus memenuhi

kesediaan waktu mengajar dosen, distribusi jadwal yang merata di ruangan kelas dan

pemakaian ruangan yang seimbang dalam satu hari. Dengan permasalahan sebanyak

itu tidak dapat diselesaikan dengan hanya coretan di atas kertas untuk memperoleh

jadwal yang optimal. Dengan penggunaan komputer saat ini, dapat digunakan untuk

membuat suatu komputasi masalah penjadualan perkuliahan dengan menggunakan

metode graph coloring.

Teori graph coloring merupakan salah satu objek yang menarik dan terkenal

dalam bidang teori graph. Teori graph merupakan topik yang banyak mendapat

perhatian saat ini, karena model-model yang ada pada teori graph berguna untuk

aplikasi yang luas. Walaupun teori graph berasal dari bidang ilmu Matematika, namun

pada penerapannya teori graph dapat dihubungkan dengan berbagai bidang ilmu dan

juga kehidupan sehari-hari. Contohnya masalah dalam jaringan komunikasi,

penjadualan, optimisasi, transportasi, ilmu komputer, riset operasi, ilmu kimia,

Sosiologi, Kartographi dan lain sebagainya.

Universitas Sumatera Utara

2

Dalam pengimplementasian metode graph coloring pada suatu aplikasi

penjadualan juga dibutuhkan suatu metode yang dapat digunakan dalam permasalahan

coloring. Dengan pemanfaatan metode yang bagus maka akan didapatkan hasil

komputasi yang lebih baik. Oleh karena itu, penulis menggunakan algoritma greedy

dan metode graph coloring heuristic untuk menyelesaikan masalah penjadualan

perkuliahan.

1.2 Rumusan Masalah

Untuk menentukan solusi yang tepat dalam suatu permasalahan, maka terlebih dahulu

permasalahan tersebut dianalisis dan disusun ke dalam bentuk formulasi yang

sistematis. Adapun perumusan masalah yang akan dibahas pada skripsi ini adalah:

1. Bagaimana menangani pembuatan jadwal mata kuliah berdasarkan data kelas

yang ditawarkan pada semester ganjil Departemen/Program Studi Biologi,

Fisika, Kimia, dan Matematika Fakultas MIPA (Matematika dan Ilmu

Pengetahuan Alam) USU (Universitas Sumatera Utara).

2. Bagaimana mengatur jadwal mata kuliah agar sesuai dengan ruangan kelas

yang tersedia dan tidak terjadi bentrokan waktu perkuliahan.

3. Bagaimana mengatur jadwal mata kuliah agar memenuhi berbagai batasan dan

aturan yang dicantumkan dalam batasan masalah.

1.3 Ruang Lingkup

Untuk memfokuskan pada tujuan penelitian maka penulis membatasi ruang lingkup

skripsi ini. Adapun yang menjadi ruang lingkup adalah sebagai berikut:

a. Metode graph coloring yang dipakai dalam skripsi ini adalah coloring

vertex.

b. Ada 3 komponen utama dalam graph yang digunakan sebagai representasi

masalah perkuliahan dalam graph, yaitu:

1. Vertex menunjukkan mata kuliah.

Universitas Sumatera Utara

3

2. Edge menunjukkan pasangan mata kuliah yang mempunyai jadwal

yang sama, karena itu harus berada di ruangan kelas yang berbeda.

3. Warna untuk membedakan mata kuliah konflik dengan mata kuliah

tidak konflik.

c. Data mata kuliah yang dijadikan contoh masalah dalam skripsi ini adalah

mata kuliah empat departemen/program studi FMIPA USU Strata 1, yaitu

Biologi, Fisika, Kimia, dan Matematika pada semester ganjil Tahun Ajaran

2008/2009.

d. Semua mata kuliah pilihan pada departemen/program studi Kimia dan

Matematika diikutsertakan, begitu juga dengan mata kuliah

kosentrasi/penjurusan pada departemen/program studi Matematika dan

Fisika. Sedangkan konsentrasi/penjurusan pada departemen/program studi

Biologi diabaikan.

e. Penjadualan mata kuliah memiliki batasan pokok (hard constraints) dan

batasan tambahan (soft constraints).

f. Prototype sistem penjadualan perkuliahan yang dibangun tidak memiliki

sistem login.

g. Prototype sistem penjadualan perkuliahan yang dibangun hanya

menjadwalkan mata kuliah, tidak menjadwalkan ujian dan pemakaian

laboratorium.

h. Prototype sistem penjadualan yang dibangun memiliki waktu perkuliahan

dari hari Senin s.d. hari Jumat.

i. Prototype sistem penjadualan mata kuliah yang dibangun tidak mendukung

adanya pergantian jadwal yang sudah ditentukan dan tidak mendukung

adanya pengambilan mata kuliah dua semester di atas maupun dua

semester di bawahnya.

1.4 Tujuan Penelitian

Adapun tujuan penelitian ini adalah untuk membuat suatu prototype sistem

penjadualan mata kuliah dengan menggunakan algoritma greedy dan metode graph

coloring heuristic untuk mengoptimalkan penggunaan ruangan kelas yang tersedia

Universitas Sumatera Utara

4

sesuai dengan mata kuliah yang ada dengan memperhatikan aturan dan batasan yang

ditetapkan.

1.5 Manfaat Penelitian

Manfaat dari skripsi ini adalah diharapkan dapat memberikan suatu penyelesaian

masalah dan mencari hasil penjadualan perkuliahan yang paling optimal sesuai dengan

batasan-batasan penjadualan yang telah ditetapkan.

1.6 Metode Penelitian

Penelitian yang akan dilakukan nantinya direncanakan ke dalam tahapan langkah-

langkah secara sistematis. Penelitian dilakukan dengan beberapa tahapan, yaitu:

1. Studi Literatur

Penulisan ini dimulai dengan studi kepustakaan yaitu mengumpulkan bahan-

bahan referensi baik dari buku, artikel, paper, jurnal, makalah, maupun situs

internet mengenai penjadualan mata kuliah, masalah graph coloring, algoritma

greedy, metode graph coloring heuristic, dan xml.

2. Analisis Permasalahan

Pada tahap ini dilakukan analisis permasalahan yang ada, batasan yang

dimiliki dan kebutuhan yang diperlukan.

3. Perancangan dan Implementasi Algoritma

Pada tahap ini dilakukan pendefinisian beberapa aturan dalam penjadualan

sesuai dengan batasan yang telah ditetapkan dan perancangan graph konflik,

penerapan algoritma greedy dan metode graph coloring heuristic dalam

penjadualan mata kuliah.

Universitas Sumatera Utara

5

4. Pengujian

Pada tahap ini dilakukan pengujian terhadap aplikasi yang telah dibangun serta

menguji algoritma greedy dan metode graph coloring heuristic.

5. Penyusunan Laporan dan Kesimpulan Akhir

Pada tahap ini dilakukan pendokumentasian hasil analisis dan implementasi

secara tertulis dalam bentuk laporan skripsi.

1.7 Sistematika Penulisan

Sistematika penulisan skripsi ini dibagi dalam lima bab, masing-masing bab diuraikan

sebagai berikut:

BAB 1: PENDAHULUAN

Bab ini akan menjelaskan mengenai latar belakang pemilihan judul, perumusan

masalah, tujuan penelitian, ruang lingkup, metode penelitian, manfaat penelitian dan

sistematika penulisan.

BAB 2: LANDASAN TEORI

Bab ini akan membahas teori-teori yang berkaitan dengan penjadualan, graph, graph

coloring, algoritma greedy, metode graph coloring heuristic, xml, dan bahasa

pemrograman yang dipakai.

BAB 3: ANALISIS DAN PERANCANGAN

Bab ini akan membahas aturan-aturan yang berkaitan dengan penjadualan, flowchart,

spesifikasi umum, perancangan mata kuliah konflik, algoritma quick sort, penerapan

algoritma greedy, dan penerapan metode graph coloring heuristic.

Universitas Sumatera Utara

6

BAB 4: IMPLEMENTASI DAN PENGUJIAN

Bab ini menjelaskan implementasi dari penerapan metode graph coloring heuristic

sehingga mendapatkan mata kuliah bebas konflik.

BAB 5: PENUTUP

Bab terakhir akan memuat kesimpulan isi dari keseluruhan uraian bab-bab

sebelumnya dan saran-saran dari hasil yang diperoleh yang diharapkan dapat

bermanfaat dalam pengembangan selanjutnya.

Universitas Sumatera Utara