BAB III ANALISIS DAN PERANCANGAN
3.1 ANALISIS
Subbab ini akan berisi pembahasan mengenai cara kerja algoritma WelchPowell dalam mewarnai simpul graf dan implementasinya dalam penyusunan jadwal ujian mata kuliah.
3.1.1 Analisis Kebutuhan Sistem
Analisis kebutuhan sistem merupakan proses identifikasi dan evaluasi permasalahan-permasalahan yang ada, sehingga sistem yang dibangun sesuai dengan kriteria yang diharapkan. Algoritma Welch-Powell akan diterapkan pada studi kasus penjadwalan ujian mata kuliah. Oleh karena itu, aplikasi yang dihasilkan, harus memenuhi kebutuhan sebagai berikut: 1. Aplikasi akan menerima input berupa Nim dan nama mahasiswa, kode matakuliah dan nama mata kuliah yang diujikan dan daftar ujian mata kuliah yang diikuti / diambil oleh para mahasiswa. 2. Aplikasi harus mampu melakukan penjadwalan waktu ujian mata kuliah dengan menggunakan algoritma Welch-Powell.
Output dari aplikasi adalah berupa
serangkaian aturan yang harus dituruti dalam pembuatan jadwal ujian mata kuliah. Contohnya: waktu ujian mata kuliah-1 tidak boleh bersamaan dengan ujian mata kuliah-3, dan seterusnya. Dengan aturan ini, akan dihasilkan jadwal ujian mata
kuliah yang seminimal mungkin dan tidak berbenturan antar mahasiswa yang mengikutinya. 3. Aplikasi harus mampu menampilkan langkah-langkah pewarnaan graf dengan algoritma Welch-Powell di dalam penerapannya pada penjadwalan ujian mata kuliah. 4. Aplikasi harus dapat menyimpan dan membuka kembali data yang pernah disimpan sebelumnya ke database.
3.1.2 Analisis Proses Pewarnaan Simpul Graf dengan Welch-Powell
Untuk mewarnai graf dengan menggunakan algoritma Welch-Powell, penulis melakukan hal berikut: 1. Urutkan semua simpul berdasarkan derajat simpul. Pengurutan simpul dilakukan berdasarkan derajat simpul secara menurun (descending) atau dari derajat simpul paling tinggi ke derajat simpul paling rendah. Derajat simpul adalah banyaknya garis yang berhubungan dengan simpul tersebut. 2. Warnai simpul dengan warna baru. Ambil simpul berderajat tertinggi yang belum diwarnai dan berikan satu warna baru pada simpul tersebut. 3. Warnai simpul tetangga. Berikan warna yang sama pada simpul lainnya yang tidak bertetangga (tidak terhubung) dengan simpul pada poin no-2. 4. Apabila masih ada simpul yang belum diwarnai, maka ulangi poin no-2 dan poin no3, hingga semua simpul terwarnai.
Proses kerja pewarnaan graf ini dapat digambarkan dalam bentuk flowchart, seperti terlihat pada gambar 3.1 berikut: START
Urutkan semua simpul berdasarkan derajat simpul secara menurun (dari derajat tertinggi sampai terendah)
Ambil simpul berderajat tertinggi yang belum diwarnai dan berikan warna baru pada simpul tersebut
Apakah terdapat simpul yang tidak bertetangga ?
Tidak
Ya Warnai semua simpul yang tidak bertetangga dengan warna yang sama
Ya
Apakah masih terdapat simpul yang belum diwarnai ? Tidak END
Gambar 3.1 Flowchart Pewarnaan dengan Algoritma Welch Powell Agar lebih jelas dalam proses pewarnaan graf dengan algoritma Welch-Powell, perhatikan contoh graf pada gambar 3.2 berikut:
A
B
C
G D E
F
H Gambar 3.2 Contoh Graf
Hasil pengurutan derajat simpul secara menurun pada gambar 3.2 adalah sebagai berikut: 1. Simpul E memiliki derajat sebesar 5 (ditandai dengan adanya lima sisi yang terhubung dengan simpul). 2. Simpul C memiliki derajat sebesar 4. 3. Simpul B, D dan F memiliki derajat sebesar 3. 4. Simpul A, H dan G memiliki derajat sebesar 2. Proses pewarnaan graf yang dilakukan pada gambar 3.2 adalah sebagai berikut: 1. Ambil simpul berderajat tertinggi yang belum diwarnai, dalam hal ini adalah simpul E, dan berikan warna baru pada simpul tersebut. Misalkan, kita memberikan warna biru pada simpul E. Prosesnya dapat dilihat pada gambar 3.3
A (2)
B (3)
C (4)
G (2) D (3) E (simpul = 5) F(3) Simpul tertinggi dan berikan warna biru
H (2)
Gambar 3.3 Warnai Simpul E
2. Berikan warna biru juga pada simpul yang tidak bertetangga (simpul yang tidak terhubung langsung) dengan simpul E, yaitu simpul A dan simpul G. Prosesnya dapat dilihat pada gambar 3.4
A (2)
B (3)
Berikan warna biru pada simpul yang tidak bertetangga dengan simpul E C (4)
G (2) D (3) E (5)
F(3)
H (2) Gambar 3.4 Warnai Simpul A dan simpul G 3. Selanjutnya, ambil simpul berderajat tertinggi berikutnya yang belum diwarnai. Dalam hal ini adalah simpul C dengan derajat sebesar 4. Berikan warna merah pada simpul tersebut. Prosesnya dapat dilihat pada gambar 3.5
A (2)
B (3)
C (4)
Simpul tertinggi berikutnya yang belum diwarnai dan berikan warna merah
G (2) D (3) E (5)
F(3)
H (2) Gambar 3.5 Warnai Simpul C 4. Berikan warna merah juga pada simpul yang tidak bertetangga (simpul yang tidak terhubung langsung) dengan simpul C, yaitu simpul D. Simpul H tidak diwarnai karena bertetangga dengan simpul D. Prosesnya dapat dilihat pada gambar 3.6
A (2)
B (3)
C (4)
G (2) D (3) F(3)
E (5) H (2) Berikan warna merah pada simpul yang tidak bertetangga dengan simpul C
Gambar 3.6 Warnai Simpul D 5. Selanjutnya, ambil simpul berderajat tertinggi berikutnya yang belum diwarnai. Dalam hal ini adalah simpul B dengan derajat sebesar 3. Berikan warna hijau pada simpul tersebut. Prosesnya dapat dilihat pada gambar 3.7 Simpul tertinggi berikutnya yang belum diwarnai dan berikan warna hijau
B (3)
A (2)
C (4)
G (2) D (3) E (5)
F(3)
H (2) Gambar 3.7 Warnai Simpul B 6. Berikan warna hijau juga pada simpul yang tidak bertetangga (simpul yang tidak terhubung langsung) dengan simpul B, yaitu simpul F dan simpul H. Prosesnya dapat dilihat pada gambar 3.8
A (2)
B (3)
C (4)
G (2) D (3) F(3)
E (5) H (2)
Berikan warna hijau pada simpul yang tidak bertetangga dengan simpul B
Gambar 3.8 Warnai Simpul F dan H
3.1.3 Analisis Proses Penjadwalan Ujian Mata Kuliah
Salah satu implementasi dari pewarnaan graf dengan algoritma Welch-Powell adalah dalam menentukan jadwal ujian. Misalkan terdapat 12 orang mahasiswa (1, 2, …, 12) dan 8 mata kuliah yang dapat dipilihnya (A, B, C, …, H). Tabel 3.1 berikut memperlihatkan matriks delapan mata kuliah dan sepuluh orang mahasiswa. Karakter “X” pada elemen (i, j) menyatakan bahwa mahasiswa ke-i memilih mata kuliah ke-j, sedangkan Karakter “-“ menyatakan mahasiswa ke-i tidak memilih mata kuliah ke-j. Tabel 3.1 Daftar Ujian Mata Kuliah yang Diambil oleh Mahasiswa
1 2 3 4 5 6 7 8 9 10 11 12
A X X -
B X X X -
C X X X X -
D X X X -
E X X X X X -
F X X X
G X X
H X X -
Berdasarkan tabel 3.1, pihak universitas ingin menentukan jadwal ujian sedemikian rupa sehingga semua mahasiswa dapat mengikuti ujian mata kuliah yang diambilnya tanpa bertabrakan waktunya dengan jadwal ujian mata kuliah lain yang juga diambilnya. Secara singkat, jika ada mahasiswa yang mengambil dua mata kuliah atau lebih, jadwal ujian mata kuliah tersebut harus pada waktu yang tidak bersamaan. Ujian dua buah mata kuliah dapat dijadwalkan pada waktu yang sama jika tidak ada mahasiswa yang sama yang mengikuti ujian dua mata kuliah itu. Selain ingin mencegah jadwal ujian bertabrakan, pihak universitas juga ingin mengatur agar jumlah hari yang dibutuhkan untuk menyelenggarakan ujian adalah yang paling minimal, sehingga dapat menghemat waktu penyelenggaraan ujian tersebut. Penyelesaian permasalahan menentukan jadwal ujian semua mata kuliah sama dengan menggambarkan graf yang menyatakan penjadwalan ujian. Simpul-simpul pada graf menyatakan mata kuliah, sedangkan sisi yang menghubungkan dua buah simpul menyatakan ada mahasiswa yang memilih kedua mata kuliah tersebut.
Graf yang
merepresentasikan persoalan pada tabel 3.1 ditunjukkan pada gambar 3.9
A (2)
B (3)
C (4)
G (2) D (3) E (5)
F(3)
H (2) Gambar 3.9 Graf Penjadwalan Ujian 8 Mata Kuliah untuk 12 orang mahasiswa Berdasarkan graf pada gambar 3.9, dapat disimpulkan bahwa apabila terdapat dua buah simpul yang dihubungkan oleh sisi, maka ujian kedua mata kuliah tersebut tidak dapat dibuat pada waktu yang sama. Warna-warna yang berbeda dapat diberikan pada
simpul graf yang akan menunjukkan bahwa waktu ujiannya berbeda.
Dibutuhkan
jadwal ujian yang sesedikit mungkin untuk menghemat waktu pelaksanaan ujian. Dengan mengikuti langkah-langkah pewarnaan graf dengan algrotima Welch-Powell pada subbab 3.1.2, akan didapatkan pewarnaan simpul graf seperti terlihat pada gambar 3.10 berikut:
A (2)
B (3)
C (4)
G (2) D (3)
F(3)
E (5) H (2)
Gambar 3.10 Hasil Pewarnaan pada Simpul Graf Kesimpulan penjadwalan ujian yang dapat dilihat pada gambar 3.10 adalah sebagai berikut: 1. Ujian mata kuliah A, E dan G (warna simpul biru) dapat dilaksanakan secara bersamaan. Sebagai contoh: Senin, 2 November 2009, pukul: 10:00. 2. Ujian mata kuliah C dan D (warna simpul merah) dapat dilaksanakan secara bersamaan. Sebagai contoh: Senin, 2 November 2009, pukul: 13:00. 3. Ujian mata kuliah B, F dan H (warna simpul hijau) dapat dilaksanakan secara bersamaan. Sebagai contoh: Senin, 2 November 2009, pukul: 18:00. Dengan demikian, berarti terdapat 3 waktu pelaksanaan ujian mata kuliah yang harus diselenggarakan oleh pihak universitas.
Untuk graf dengan jumlah simpul sedikit,
mungkin kita dapat menentukan graf dan mewarnai simpulnya dengan mudah. Namun, untuk graf dengan simpul yang besar, dibutuhkan pembuatan aplikasi untuk menentukan graf dan mewarnai semua simpulnya.
3.1.4 Analisis Perancangan Sistem
Perancangan Sistem adalah penggambaran, perancangan dan pembuatan sketsa. Diagram konteks dari proses penjadwalan ujian mata kuliah ini dapat dilihat pada gambar 3.11 Pada gambar tersebut, yang menjadi entitas adalah user (pengguna aplikasi). Di sini, user bisa berupa staff administrasi kampus atau staff lainnya yang bertugas untuk meng-input daftar ujian mata kuliah. Data Mata Kuliah (Jumlah dan nama mata kuliah yang diujikan)
0 Daftar Ujian Mata Kuliah (Ujian mata kuliah yang diikuti oleh mahasiswa)
User
Proses Penjadwalan Ujian Mata Kuliah
Data Mahasiswa (Jumlah dan nama mahasiswa) Hasil Penjadwalan
Gambar 3.11 Diagram Konteks Proses Penjadwalan Ujian Mata Kuliah
3.2 DIAGRAM USE CASE
Berdasarkan spesifikasi kebutuhan, maka dapat didefinisikan fungsionalitas sistem sebagai berikut. Gambar 3.16 menunjukkan use case dari sistem.
Penjadwalan Ujian Mata Kuliah Menggunakan Algoritma Welch-Powell
Input Data Mata Kuliah
<< include >> << e
Input Banyak Mata Kuliah
xten
Input Data Mahasiswa
d >>
Input Kode dan Nama Mata Kuliah
<< include >> <<
exte
nd >
>
Input Banyak Mahasiswa Input NIM dan Nama Mahasiswa
<< uses >>
Input Daftar Ujian Mata Kuliah << uses
>> s>
>
USER
<<
use
Buka Daftar Ujian
Penjadwalan Ujian Mata Kuliah
<< uses >>
Simpan Daftar Ujian
Gambar 3.12 Diagram Use Case dari Aplikasi Gambar 3.16 menunjukkan bahwa use case dari sistem yang terdiri dari seorang aktor yaitu user. User bisa berupa pengguna aplikasi, staff administrasi kampus atau staff lainnya yang bertugas untuk meng-input daftar ujian mata kuliah. Adapun narasi dari use case dapat dilihat pada tabel 3.2
Tabel 3.2 Narasi Use Case
Nama use case Aktor Deskripsi Prakondisi
Input Banyak Mata Kuliah User Use case ini mendeskripsikan proses input banyak mata kuliah. Tabel mata kuliah masih kosong dan tabel daftar ujian mata kuliah masih tidak memiliki kolom.
Sasaran
Use case ini diawali saat user ingin menentukan banyaknya mata kuliah yang diujikan.
Aksi Aktor Respons Sistem Bidang khas 1. User mengklik 2. Sistem menampilkan pilihan suatu event combobox ”Jumlah dari 2 sampai 100 buah mata kuliah Mata Kuliah”. pada combobox. 4. Sistem menyesuaikan jumlah 3. User mengklik baris pada tabel mata kuliah dan salah satu pilihan jumlah kolom pada tabel daftar pada combobox. ujian mata kuliah dengan pilihan pada combobox.
Bidang alternatif
Alt langkah 3: User tidak mengklik pilihan pada combobox. Alt langkah 4: Sistem tidak menyesuaikan jumlah baris pada tabel nama mata kuliah dan jumlah kolom pada tabel daftar ujian mata kuliah. Kesimpulan Use case ini mengatur jumlah baris pada tabel mata kuliah dan jumlah kolom pada tabel daftar ujian mata kuliah. Postkondisi Jumlah baris pada tabel mata kuliah dan jumlah kolom pada tabel daftar ujian mata kuliah disesuaikan dengan banyaknya mata kuliah yang diujikan. Nama use case Input Kode dan Nama Mata Kuliah Aktor User Deskripsi Use case ini mendeskripsikan input kode dan nama mata kuliah. Prakondisi sutasKode dan nama mata kuliah masih kosong. Header kolom dari tabel daftar ujian juga kosong. Sasaran Use case ini diawali saat user ingin memasukkan namanama dari mata kuliah yang diujikan. Aksi Aktor Respons Sistem Bidang khas 1. User memasukkan 2. Sistem menampilkan kode dan suatu event kode dan nama mata nama mata kuliah pada tabel mata kuliah pada tabel. kuliah. Kode mata kuliah juga ditampilkan pada kolom tabel daftar ujian. 4. Sistem tidak menampilkan 3. User mengetikkan karakter selanjutnya, karena kode kode mata kuliah lebih mata kuliah dibatasi maksimal 10 dari 10 karakter dan karakter dan nama mata kuliah nama mata kuliah lebih dibatasi maksimal 50 karakter. dari 50 karakter. Kesimpulan
Use case ini menampilkan dan menyimpan kode dan nama untuk setiap mata kuliah yang diujikan. Kode mata kuliah dibatasi maksimal 10 karakter dan nama mata kuliah dibatasi 50 karakter.
Postkondisi
Kode dan nama mata kuliah yang dimasukkan, ditampilkan pada tabel mata kuliah. Kode mata kuliah juga ditampilkan pada setiap header kolom dari tabel Daftar Ujian / Partisipasi.
Nama use case Aktor Deskripsi Prakondisi
Input Banyak Mahasiswa User Use case ini mendeskripsikan input banyak mahasiswa. Tabel mahasiswa masih kosong dan tabel daftar ujian mata kuliah masih tidak memiliki baris. Sasaran Use case ini diawali saat user ingin menentukan banyaknya mahasiswa yang mengikuti ujian. Aksi Aktor Respons Sistem Bidang khas 1. User mengklik 2. Sistem menampilkan pilihan suatu event combobox ”Jumlah dari 2 sampai 1000 orang Mahasiswa”. mahasiswa pada combobox. 4. Sistem menyesuaikan jumlah 3. User mengklik baris pada tabel mahasiswa dan salah satu pilihan jumlah baris pada tabel daftar ujian pada combobox. mata kuliah dengan pilihan pada combobox. Bidang alternatif
Alt langkah 3: User tidak mengklik pilihan pada combobox. Alt langkah 4: Sistem tidak menyesuaikan jumlah baris pada tabel mahasiswa dan jumlah baris pada tabel daftar ujian mata kuliah. Kesimpulan Use case ini mengatur jumlah baris pada tabel mahasiswa dan jumlah baris pada tabel daftar ujian mata kuliah. Postkondisi Jumlah baris pada tabel mahasiswa dan jumlah baris pada tabel daftar ujian mata kuliah disesuaikan dengan banyaknya mata kuliah yang diujikan. Nama use case Input NIM dan Nama Mahasiswa Aktor User Deskripsi Use case ini mendeskripsikan proses input NIM dan nama mahasiswa. Prakondisi NIM dan nama mahasiswa masih kosong. Header baris dari tabel daftar ujian juga kosong. Sasaran Use case ini diawali saat user ingin memasukkan NIM dan nama-nama mahasiswa yang mengikuti ujian. Aksi Aktor Respons Sistem Bidang khas 1. User memasukkan 2. Sistem menampilkan NIM dan suatu event NIM dan nama nama mahasiswa pada tabel mahasiswa pada tabel. mahasiswa. NIM mahasiswa juga tertera pada header setiap baris dari tabel daftar ujian. 4. Sistem tidak menampilkan
Kesimpulan
Postkondisi
karakter selanjutnya, karena NIM 3. User mengetikkan dibatasi maksimal 10 karakter dan NIM lebih dari 10 nama mahasiswa dibatasi karakter dan nama maksimal 50 karakter. mahasiswa yang lebih dari 50 karakter. Use case ini menampilkan dan menyimpan NIM dan nama untuk setiap mahasiswa yang mengikuti ujian. NIM dibatasi maksimal 10 karakter dan nama mahasiswa dibatasi maksimal 50 karakter. Kode dan nama mahasiswa yang mengikuti ujian, ditampilkan pada tabel mahasiswa. Nama mahasiswa juga ditampilkan pada setiap header baris dari tabel Daftar Ujian / Partisipasi.
Nama use case Aktor Deskripsi
Input Daftar Ujian Mata Kuliah User Use case ini mendeskripsikan proses input daftar ujian mata kuliah. Prakondisi Tabel daftar ujian mata kuliah masih kosong dan semua cell di dalam tabel masih berisi karakter ”-”. Sasaran Use case ini diawali saat user ingin memasukkan daftar ujian mata kuliah yang diikuti oleh setiap mahasiswa. Aksi Aktor Respons Sistem Bidang khas 1. User menekan 2. Sistem akan menampilkan suatu event sembarang tombol karakter ”X” pada cell tersebut. Ini pada salah satu cell berarti mahasiswa dengan baris ke-i yang memiliki pada tabel mengikuti ujian mata karakter ”-” dalam kuliah dengan kolom ke-j pada tabel daftar ujian. tabel daftar ujian. 4. Sistem akan menampilkan karakter ”-” pada cell tersebut. 3. User menekan sembarang tombol pada salah satu cell yang memiliki karakter ”X” dalam tabel daftar ujian. Kesimpulan Use case ini mengatur input daftar ujian mata kuliah yang diikuti oleh mahasiswa. Postkondisi Tabel daftar ujian mata kuliah telah terisi. Nama use case Simpan Daftar Ujian Aktor Deskripsi Prakondisi
User Use case ini mendeskripsikan proses penyimpanan daftar ujian beserta dengan data mata kuliah dan data mahasiswa. Daftar ujian, data mata kuliah dan data mahasiswa belum tersimpan.
Sasaran
Use case ini diawali saat user ingin menyimpan daftar ujian, data mata kuliah dan data mahasiswa ke database. Aksi Aktor Respons Sistem Bidang khas 1. User menekan 2. Sistem membuka tampilan suatu event tombol ”Simpan simpan data. Daftar”. 4. Sistem menyimpan daftar ujian, 3. User memasukkan data mata kuliah dan data nama daftar dan mahasiswa ke dalam database. menekan tombol ”Simpan”. Bidang Alt langkah 3: User menekan tombol ”Batal”. Alternatif Alt langkah 4: Sistem membatalkan penyimpanan data. Kesimpulan Use case ini melakukan penyimpanan daftar ujian, data mata kuliah dan data mahasiswa ke database. Postkondisi Daftar ujian, data mata kuliah dan data mahasiswa yang telah di-input disimpan ke dalam database. Nama use case Aktor Deskripsi
Buka Daftar Ujian User Use case ini mendeskripsikan proses pembukaan daftar ujian, data mata kuliah dan data mahasiswa dari database. Prakondisi Tabel nama mata kuliah, nama mahasiswa dan daftar ujian masih kosong. Sasaran Use case ini diawali saat user ingin membuka daftar ujian, data mata kuliah dan data mahasiswa yang sudah pernah disimpan sebelumnya. Aksi Aktor Respons Sistem Bidang khas 1. User menekan 2. Sistem membuka tampilan buka suatu event tombol ”Buka data dengan tabel berisi list nama Daftar”. daftar ujian. 4. Sistem memanggil record daftar 3. User mengklik ujian, data mata kuliah dan data salah satu nama daftar mahasiswa dari dalam database, ujian pada tabel dan sesuai dengan nama daftar ujian menekan tombol yang terpilih. Kemudian, sistem ”Buka”. mengisi tabel mata kuliah, tabel mahasiswa dan tabel daftar ujian sesuai dengan record yang dibuka. Bidang Alt langkah 3 : User menekan tombol ”Batal”. alternatif Alt langkah 4 : Sistem membatalkan pembukaan data. Kesimpulan Use case ini membuka kembali daftar ujian, data mata kuliah dan data mahasiswa yang telah tersimpan ke database. Postkondisi Tabel nama mata kuliah, nama mahasiswa dan daftar ujian sudah terisi. Nama use case Penjadwalan Ujian Mata Kuliah Aktor User Deskripsi Use case ini mendeskripsikan proses penjadwalan ujian.
Prakondisi Sasaran
Belum terdapat penjadwalan ujian mata kuliah. Use case ini diawali saat user ingin menghasilkan penjadwalan yang seminimal mungkin dan tidak bentrok satu sama lain dari daftar ujian yang telah di-input. Aksi Aktor Respons Sistem Bidang khas 1. User mengklik 2. Sistem menjalankan proses suatu event tombol ’Tampilkan penjadwalan dan menampilkan Hasil Penjadwalan hasil pewarnaan untuk setiap mata Ujian’. kuliah pada tampilan hasil penjadwalan. 4. Jadwal ujian untuk mata kuliah 3. User memasukkan akan ter-update dengan tanggal tanggal dan waktu dan waktu, sesuai dengan warna untuk mewakili warna yang dimiliki. yang dihasilkan. Kesimpulan Use case ini melakukan penjadwalan ujian terhadap data yang telah di-input. Postkondisi Proses penjadwalan ujian mata kuliah dijalankan dan menghasilkan tanggal dan waktu penjadwalan.
3.3 PERANCANGAN
Perancangan aplikasi penjadwalan ujian mata kuliah dengan algoritma WelchPowell menggunakan bahasa pemrograman Microsoft Visual Basic 6.0 dan Microsoft Access 2003 sebagai database engine untuk menyimpan data penjadwalan.
3.3.1
Perancangan Database
Dalam database yang digunakan, terdapat 5 (lima) buah tabel, yaitu: 1. Tabel ”ListDaftarUjian”. Tabel ini berfungsi untuk menyimpan semua nama daftar ujian yang pernah di-input dan disimpan oleh user. Struktur tabelnya adalah sebagai berikut. Tabel 3.3 Struktur Tabel ”ListDaftarUjian” No. 1. 2.
Field Name IndeksDaftar NamaDaftar
Data Type Number Text
Field Size Integer 30
Field ”NamaDaftar” adalah nama daftar ujian yang diberikan oleh user, sedangkan Field ”IndeksDaftar” adalah nomor urut yang dihasilkan program secara otomatis sebagai representasi dari setiap nama daftar ujian. 2. Tabel ”Mahasiswa”. Tabel ini berfungsi untuk menyimpan nama-nama mahasiswa dalam sebuah daftar ujian. Struktur tabelnya adalah sebagai berikut: Tabel 3.4 Struktur Tabel ”Mahasiswa” No. 1. 2. 3.
Field Name IndeksDaftar NIM NamaMahasiswa
Data Type Number Text Text
Field Size Integer 10 50
Field ”IndeksDaftar” adalah indeks daftar ujian dimana mahasiswa di-input. Field ”NIM” adalah nomor indeks mahasiswa, dan Field ”NamaMahasiswa” adalah nama dari mahasiswa. 3. Tabel ”MataKuliah”. Tabel ini berfungsi untuk menyimpan nama-nama mata kuliah dalam sebuah daftar ujian. Struktur tabelnya adalah sebagai berikut. Tabel 3.5 Struktur Tabel ”MataKuliah” No. 1. 2. 3.
Field Name IndeksDaftar KodeMataKuliah NamaMataKuliah
Data Type Number Text Text
Field Size Integer 10 50
Field ”IndeksDaftar” adalah indeks daftar ujian dimana mata kuliah di-input. Field ”KodeMataKuliah” adalah kode mata kuliah, dan Field ”NamaMataKuliah” adalah nama dari mata kuliah yang diujikan. 4. Tabel ”DaftarUjian”
Tabel ini berfungsi untuk menyimpan daftar partisipasi mahasiswa dalam ujian mata kuliah. Struktur tabelnya adalah sebagai berikut : Tabel 3.6 Struktur Tabel ”DaftarUjian” No. 1. 2. 3. 4.
Field Name IndeksDaftar NIM KodeMataKuliah Partisipasi
Data Type Number Text Text Boolean
Field Size Integer 10 10 -
Field ”IndeksDaftar” adalah indeks daftar ujian dimana daftar partisipasi mahasiswa dalam setiap ujian mata kuliah di-input, field ”NIM” adalah indeks mahasiswa yang mengikuti ujian, field ”KodeMataKuliah” adalah kode mata kuliah dan field ”Partisipasi” berisi ”X / Yes” untuk kode mata kuliah yang diambil mahasiswa dan ”- / No” untuk kode mata kuliah yang tidak diambil mahasiswa.
5. Tabel ”TabelWaktu” Tabel ini berfungsi untuk menyimpan input waktu untuk setiap hasil pewarnaan. Struktur tabelnya adalah sebagai berikut. Tabel 3.7 Struktur Tabel ”TabelWaktu” No. 1. 2. 3.
Field Name IndeksDaftar IndeksWarna Waktu
Data Type Number Text Text
Field Size Integer Integer 50
Field ”IndeksDaftar” adalah indeks daftar ujian dimana hasil pewarnaan dihasilkan dan disimpan, field ”IndeksWarna” adalah nomor pewarnaan (misalnya: 1 untuk warna ”T1”, 2 untuk warna ”T2”, dan selanjutnya) dan field ”Waktu” adalah representasi waktu untuk setiap warna.
Gambaran relasi antar tabel dapat dilihat pada gambar berikut. Nama field yang dicetak tabel adalah primary key.
Gambar 3.13 Relasi Antar Tabel
3.3.2 Perancangan Proses
Proses penjadwalan ini juga dapat dirancang dalam bentuk activity diagram, seperti terlihat pada gambar berikut
Gambar 3.14 Diagram activity
Algoritma pewarnaan Welch-Powell yang diterapkan di dalam aplikasi adalah sebagai berikut: IndeksWarna = 0 WHILE (semua simpul belum terwarnai) IndeksMaks = 0 [Cari simpul berderajat tertinggi yang belum diwarnai] UNTUK I = 1 SAMPAI banyak_simpul JIKA (jumlah derajat simpul(I)) > (jumlah derajat simpul(IndeksMaks)) AND Simpul(i).Warna=0 MAKA IndeksMaks = I End JIKA NEXT I [Warnai Simpul Tersebut] IndeksWarna = IndeksWarna + 1 Simpul(IndeksMaks).Warna = IndeksWarna [Warnai Simpul Tidak Bertetangga dengan Warna yang Sama] UNTUK I = 1 SAMPAI (banyak koneksi simpul(indeksmaks)) SimpulTetangga(I) = Simpul(IndeksMaks).Koneksi(I) NEXT I UNTUK I = 1 SAMPAI (jumlah simpul) JIKA I <> IndeksMaks MAKA Tetangga = False UNTUK J = 1 SAMPAI (banyak SimpulTetangga) JIKA I = SimpulTetangga(J) maka Tetangga = True Keluar dari perulangan UNTUK END JIKA NEXT J JIKA Tetangga = False AND Simpul(I).Warna=0 MAKA Simpul(I).Warna = Simpul(IndeksMaks).Warna END JIKA UNTUK J=1 SAMPAI (banyak koneksi simpul(I)) K = (jumlah SimpulTetangga) + 1 SimpulTetangga(K)=Simpul(I).Koneksi(J) NEXT J END JIKA NEXT I WEND
3.3.3 Perancangan Tampilan
Aplikasi penyusunan jadwal ujian mata kuliah dengan menggunakan algoritma Welch-Powell memiliki 5 (lima) buah tampilan, yaitu: 1. Tampilan Splash Screen. 2. Tampilan Input. 3. Tampilan Hasil Penjadwalan. 4. Tampilan Buka Data (Load). 5. Tampilan Simpan Data (Save).
3.3.3.1 Rancangan Tampilan Splash Screen
Tampilan splash screen akan menjadi layar yang muncul pertama sekali saat aplikasi dijalankan. Tampilan ini berfungsi sebagai identitas aplikasi yang berisi logo / icon dan nama aplikasi serta identitas penulis dan nama kampus. Rancangan tampilan splash screen dapat dilihat pada gambar berikut.
2
1
3
4
Gambar 3.15 Rancangan Tampilan Splash Screen
Keterangan gambar: 1
: icon atau logo perangkat lunak.
2
: nama perangkat lunak.
3
: identitas penulis.
4
: jurusan, program studi dan tahun pembuatan aplikasi.
3.3.3.2 Rancangan Tampilan Input
Tampilan input akan menjadi tempat untuk memasukkan jumlah dan nama mata kuliah yang diujikan, jumlah dan nama mahasiswa serta tabel daftar ujian mata kuliah yang diikuti oleh mahasiswa. Pada tampilan ini, pengguna juga menyimpan atau membuka data penjadwalan yang sudah tersimpan ke database sebelumnya. Rancangan tampilan input dapat dilihat pada gambar berikut. x
Implementasi Algoritma Welch-Powell dalam Penyusunan Jadwal Ujian Mata Kulia
IMPLEMENTASI ALGORITMA WELCH-POWELL DALAM PENYUSUNAN JADWAL UJIAN
1 1. Jumlah Mata Kuliah : Kode MK
Tabel Partisipasi Mahasiswa dalam Ujian Mata Kuliah:
Nama Mata Kuliah
2 5
3
2. Jumlah Mahasiswa : NIM
Nama Mahasiswa
4
Tampilkan Hasil Penjadwalan Ujian
6
Simpan
7
Keluar
Buka
8
Gambar 3.16 Rancangan Tampilan Input
9
Keterangan gambar: 1
: combobox, untuk memasukkan jumlah mata kuliah.
2
: tabel, untuk memasukkan kode dan nama mata kuliah.
3
: combobox, untuk memasukkan jumlah mahasiswa.
4
: tabel, untuk memasukkan NIM dan nama mahasiswa.
5
: tabel, untuk memasukkan daftar ujian mata kuliah yang diikuti oleh mahasiswa. (bentuk tabel sama seperti tabel 3.1)
6
: tombol ‘Penjadwalan’, untuk memulai proses penjadwalan ujian mata kuliah dan menampilkan hasilnya pada tampilan Hasil Penjadwalan.
7
: tombol ‘Simpan’, untuk membuka tampilan ‘Simpan’.
8
: tombol ‘Buka’, untuk membuka tampilan ‘Buka’
9
: tombol ‘Keluar’, untuk menutup tampilan dan keluar dari aplikasi.
3.3.3.3 Rancangan Tampilan Hasil Penjadwalan
Tampilan
hasil
penjadwalan,
berfungsi
untuk
menampilkan
hasil
penjadwalan beserta langkah-langkah pewarnaan graf yang dilakukan oleh aplikasi. Rancangan tampilan dapat dilahat pada gambar berikut
Gambar 3.17 Rancangan Tampilan Hasil Penjadwalan
Keterangan gambar: 1 : textbox, untuk menampilkan langkah-langkah pewarnaan simpul graf. 2 : daerah tampilan hasil penjadwalan ujian mata kuliah. 3 : tombol ‘Keluar’, untuk menutup tampilan hasil penjadwalan dan kembali ke tampilan input.
3.3.3.4 Rancangan Tampilan Buka Data
Tampilan buka data, berfungsi untuk membuka daftar ujian mata kuliah yang sudah disimpan sebelumnya ke database. gambar berikut.
Rancangan tampilan dapat dilihat pada
Buka Daftar Ujian Mata Kuliah
Buka Daftar Ujian Mata Kuliah Pilih daftar ujian mata kuliah yang ingin dibuka :
No.
Nama Daftar Ujian
Mata Kuliah
Mahasiswa
1
Buka
2
Batal
3
Gambar 3.18 Rancangan Tampilan Buka Data
Keterangan gambar: 1 : tabel, untuk memilih data yang ingin dibuka. 2 : tombol ‘Buka’, untuk membuka data yang telah dipilih pada tabel. 3 : tombol ‘Batal’, untuk membatalkan pembukaan data, menutup tampilan dan kembali ke tampilan input.
3.3.3.5 Rancangan Tampilan Simpan Data
Tampilan simpan data, berfungsi untuk menyimpan input daftar ujian mata kuliah ke database. Rancangan tampilan dapat dilihat pada gambar berikut.
Simpan Daftar Ujian Mata Kuliah
Simpan Daftar Ujian Mata Kuliah Nama Daftar : 1
Batal
Simpan
2
3
Gambar 3.19 Rancangan Tampilan Simpan Data
Keterangan gambar: 1 : textbox, untuk memasukkan nama daftar ujian mata kuliah. 2 : tombol ‘Simpan’, untuk menyimpan daftar ujian mata kuliah. 3 : tombol ‘Batal’, untuk membatalkan penyimpanan data, menutup tampilan dan kembali ke tampilan input.
