Universitas Bina Nusantara Jurusan Teknik Informatika Program Studi Teknik Informatika Skripsi Sarjana Komputer Semester Ganjil tahun 2006/2007 PERANCANGAN OTOMATISASI PENJADWALAN PENGAJAR PRAKTIKUM DENGAN MENGGUNAKAN ALGORITMA GENETIK : STUDI KASUS PADA UPTPL BINA NUSANTARA
Yenni
0700733936
Abstrak Penelitian ini bertujuan untuk merancang aplikasi yang dapat melakukan penjadwalan asisten UPTPL secara otomatis dengan menggunakan algoritma genetik. Adapun manfaat yang diperoleh adalah dapat memudahkan penyusunan jadwal mengajar asisten dan mengoptimalkan penggunaan sumber daya sehingga pada akhirnya akan meningkatkan produktivitas UPTPL Bina Nusantara. Metodologi pengembangan piranti lunak yang digunakan adalah waterfall model, yang terdiri dari tahapan analysis, design, code, dan test. Hasil yang dicapai adalah jadwal asistensi yang di-generate secara otomatis sehingga memberi kemudahan bagi Kepala Asisten dalam pembuatan jadwal. Kesimpulan yg diperoleh adalah aplikasi otomatisasi penjadwalan ini dapat digunakan oleh Kepala Asisten UPTPL untuk memudahkan pembuatan jadwal asistensi dan memungkinkan pembuatan jadwal dapat dilakukan dalam hitungan jam. Saran yang dapat diberikan adalah penggunaan metode selection, mutation, dan crossover selain yang digunakan pada penelitian ini. Kata Kunci Otomatisasi, penjadwalan, algoritma genetik
iv
PRAKATA
Puji dan syukur ke hadirat Tuhan Yang Maha Esa atas kasih dan anugrah-Nya sehingga skripsi dengan judul ”Perancangan Otomatisasi Penjadwalan Pengajar Praktikum dengan Menggunakan Algoritma Genetik : Studi Kasus pada UPTPL Bina Nusantara” dapat diselesaikan. Skripsi ini disusun dalam rangka memenuhi persyaratan untuk kelulusan studi Strata-1 (S1) pada jurusan Teknik Informatika Universitas Bina Nusantara. Dalam penyusunan skripsi ini, banyak sekali pihak yang terlibat untuk memberikan bantuan serta dukungan secara langsung maupun tidak langsung sehingga proses penulisan bisa berjalan dengan baik. Untuk itu penulis mengucapkan terima kasih kepada: 1. Papa, Tjong Fong Khin, yang telah memberikan semangat dan motivasi; 2. Beben, yang telah memberi dukungan di dalam segala hal selama proses penyusunan skripsi ini; 2. Prof. Dr. Gerardus Polla, M.App.Sc., selaku Rektor Universitas Bina Nusantara yang telah memberi kepercayaan dan kesempatan untuk menyelesaikan skripsi ini; 3. Bapak Fredy Purnomo, S.Kom., M.Kom., selaku Sekretaris Jurusan Teknik Informatika yang telah memberikan dukungan dalam pembuatan skripsi ini; 4. Bapak Elidjen, S.Kom, MInfoCommTech, selaku dosen pembimbing yang telah banyak mengarahkan dan memberikan waktu, dukungan moril, saran serta bimbingan;
v
5. Bapak Wince, S.Kom, selaku Kepala UPT Piranti Lunak Universitas Bina Nusantara yang telah memberikan kesempatan untuk melakukan survei; 6. Kepala Asisten, Staff Data, dan rekan-rekan di UPT Piranti Lunak Universitas atas dukungan dan bantuannya selama ini; 7. Keluarga dan sahabat tercinta yang telah memberikan dukungan dan motivasi dalam menyelesaikan skripsi ini; 8. Serta pihak-pihak lainnya yang telah turut membantu dalam proses pembuatan skripsi ini baik secara langsung maupun tidak langsung. Saran, kritik, pendapat, koreksi dan tanggapan dari seluruh pembaca diharapkan untuk penyempurnaan skripsi ini. Semoga skripsi ini dapat bermanfaat bagi seluruh pembaca terlebih bagi UPTPL UBinus. Terima Kasih.
Jakarta, Januari 2007
Penulis
vi
DAFTAR ISI Halaman Judul Luar ............................................................................................................i Halaman Judul Dalam ....................................................................................................... ii Halaman Persetujuan Softcover........................................................................................ iii Abstrak ............................................................................. Error! Bookmark not defined. PRAKATA.........................................................................................................................v DAFTAR ISI................................................................................................................... vii DAFTAR TABEL.............................................................................................................xi DAFTAR GAMBAR ..................................................................................................... xiii DAFTAR LAMPIRAN...................................................................................................xvi BAB 1 PENDAHULUAN .................................................................................................1 1.1
Latar Belakang ...........................................................................................1
1.2
Ruang Lingkup...........................................................................................2
1.3
Tujuan dan Manfaat ...................................................................................3
1.4
Metodologi Pengembangan Software ........................................................3
1.5
Sistematika Penulisan ................................................................................4
BAB 2 LANDASAN TEORI.............................................................................................6 2.1
Sistem.........................................................................................................6
2.2
Linear Sequential Model ............................................................................6
2.3
Basis Data ..................................................................................................9
2.4
Penjadwalan .............................................................................................10
2.5
Algoritma Genetik....................................................................................11 2.5.1
Representasi Genetik dari Domain Solusi....................................13
vii
2.6
2.5.2
Inisialisasi.....................................................................................15
2.5.3
Fungsi Evaluasi ............................................................................15
2.5.4
Seleksi ..........................................................................................15
2.5.5
Crossover .....................................................................................18
2.5.6
Mutasi...........................................................................................22
2.5.7
Parameter-parameter Algoritma Genetik .....................................23
Unified Modeling Language (UML)........................................................24 2.6.1
Class Diagram ..............................................................................24
2.6.2
Use Case Diagram........................................................................27
2.6.3
Sequence Diagram .......................................................................29
2.6.4
Collaboration Diagram.................................................................29
2.6.5
Statechart Diagram.......................................................................30
2.6.6
Activity Diagram..........................................................................31
2.6.7
Component Diagram ....................................................................32
2.6.8
Deployment Diagram ...................................................................33
2.7
Microsoft Visual Studio 2005 ..................................................................33
2.8
Microsoft SQL Server 2000 .....................................................................34
BAB 3 ANALISIS DAN PERANCANGAN ..................................................................36 3.1
Latar Belakang Organisasi .......................................................................36 3.1.1
Universitas Bina Nusantara..........................................................36
3.1.2
UPT. Perangkat Lunak .................................................................38
3.2
Struktur Organisasi UPT. Perangkat Lunak.............................................39
3.3
Analisis Hasil Wawancara .......................................................................48
3.4
Permasalahan yang Dihadapi ...................................................................48 viii
3.5
Usulan Pemecahan Masalah.....................................................................49
3.6
Elemen-elemen yang Digunakan dalam Penjadwalan Asistensi .............51
3.7
Perancangan Perangkat Lunak .................................................................54 3.7.1
Class Diagram ..............................................................................54
3.7.2
Use Case.......................................................................................54
3.7.3
Sequence Diagram .......................................................................55 3.7.3.1
Sequence Diagram Generate Population.......................55
3.7.3.2
Sequence Diagram Generate Jadwal Basic ...................57
3.7.3.3
Sequence Diagram Generate Jadwal Advance..............58
3.7.3.4
Sequence Diagram View Prioritas Asisten ...................60
3.7.3.5
Sequence Diagram View Kualifikasi Asisten ...............61
3.7.3.6
Sequence Diagram View Jadwal Kuliah dan Jadwal Mengajar Per Asisten ....................................................63
3.7.3.7
Sequence Diagram View Jadwal Mengajar Seluruh Asisten...........................................................................65
3.8
Perancangan Layar ...................................................................................67 3.8.1
Rancangan Layar Form Utama ....................................................67
3.8.2
Rancangan Layar Form View Jadwal Mengajar dan Kuliah Per Asisten..........................................................................................67
3.8.3
Rancangan Layar Form View Kualifikasi Asisten.......................68
3.8.4
Rancangan Layar Form View Prioritas Mengajar Asisten ..........69
3.8.5
Rancangan Layar Form View Jadwal Mengajar Asisten.............69
3.8.6
Rancangan Layar Form Basic ......................................................70
3.8.7
Rancangan Layar Form Advance.................................................70 ix
3.8.8
Rancangan Layar Form Generate Population ..............................71
3.9
Perancangan Database..............................................................................71
3.10
Penerapan Algoritma Genetik Pada Otomatisasi Penjadwalan Asisten...78 3.10.1 Algoritma Genetik yang Digunakan ............................................78 3.10.2 Representasi Struktur Data...........................................................78 3.10.3 Urutan Proses dan Algoritma Penjadwalan Asisten ....................79
BAB 4 IMPLEMENTASI DAN EVALUASI ..............................................................111 4.1
4.2
Implementasi ..........................................................................................111 4.1.1
Spesifikasi Perangkat Keras.......................................................111
4.1.2
Spesifikasi Piranti Lunak ...........................................................111
4.1.3
Petunjuk Pengoperasian Aplikasi...............................................112
Evaluasi ..................................................................................................123 4.2.1
Pengujian terhadap Ukuran Populasi .........................................124
4.2.2
Pengujian terhadap Selection Rate.............................................126
4.2.3
Pengujian terhadap Mutation Rate .............................................127
4.2.4
Pengujian terhadap Crossover Method ......................................128
4.2.5
Proses Eksekusi dalam Pengujian Terhadap Ukuran Populasi ..129
4.2.6
Evaluasi Berdasarkan Hasil Wawancara....................................130
BAB 5 KESIMPULAN DAN SARAN .........................................................................131 5.1
Kesimpulan ............................................................................................131
5.2
Saran.......................................................................................................132
DAFTAR PUSTAKA ....................................................................................................133 RIWAYAT HIDUP........................................................................................................134 LAMPIRAN.................................................................................................................... L1 x
DAFTAR TABEL Tabel 2.1
Keuntungan dan Kerugian Menggunakan DBMS .....................................9
Tabel 2.2
Contoh Kromosom Dengan Representasi Biner ......................................13
Tabel 2.3
Contoh Kromosom Dengan Representasi Permutasi ...............................14
Tabel 2.4
Contoh Kromosom Dengan Representasi Nilai .......................................14
Tabel 2.5
Contoh Kromosom Dengan Representasi Pohon.....................................14
Tabel 3.1
Skenario Generate Population..................................................................55
Tabel 3.2
Skenario Generate Jadwal Basic ..............................................................57
Tabel 3.3
Skenario Generate Jadwal Advance.........................................................58
Tabel 3.4
Skenario View Prioritas Asisten ..............................................................60
Tabel 3.5
Skenario View Kualifikasi Asisten ..........................................................62
Tabel 3.6
Skenario View Jadwal Kuliah dan Jadwal Mengajar Per Asisten ...........63
Tabel 3.7
Skenario View Jadwal Mengajar Seluruh Asisten ...................................65
Tabel 3.8
Master Hari ..............................................................................................73
Tabel 3.9
Master Shift Asisten.................................................................................73
Tabel 3.10
Master Status Praktikum ..........................................................................73
Tabel 3.11
Master Matakuliah Kuliah........................................................................73
Tabel 3.12
Master Jabatan..........................................................................................74
Tabel 3.13
Master Wilayah ........................................................................................74
Tabel 3.14
Master Status............................................................................................74
Tabel 3.15
Master Shift..............................................................................................75
Tabel 3.16
Master Matakuliah Laboratorium ............................................................75
Tabel 3.17
Master Asisten..........................................................................................75
xi
Tabel 3.18
Master Prioritas ........................................................................................76
Tabel 3.19
Transaksi Alokasi Ruang .........................................................................76
Tabel 3.20
Transaksi Asisten Lulus Training ............................................................76
Tabel 3.21
Transaksi Kualifikasi ...............................................................................76
Tabel 3.22
Transaksi Alokasi Asisten........................................................................77
Tabel 3.23
Transaksi Kuliah Asisten .........................................................................77
Tabel 3.24
Transaksi Jadwal Mengajar......................................................................77
Tabel 3.25
Hard Constraint dan Soft Constraint ........................................................90
xii
DAFTAR GAMBAR
Gambar 2.1
Linear Sequential Model ............................................................................7
Gambar 2.2
One-point Crossover ................................................................................18
Gambar 2.3
Two-point Crossover................................................................................19
Gambar 2.4
Notasi Class Diagram...............................................................................26
Gambar 2.5
Notasi Use Case Diagram ........................................................................28
Gambar 2.6
Notasi Sequence Diagram ........................................................................29
Gambar 2.7
Notasi Collaboration Diagram .................................................................30
Gambar 2.8
Notasi Statechart Diagram .......................................................................31
Gambar 2.9
Notasi Activity Diagram ..........................................................................32
Gambar 2.10 Notasi Component Diagram.....................................................................32 Gambar 2.11 Notasi Deployment Diagram ...................................................................33 Gambar 3.1
Struktur Organisasi UPTPL .....................................................................39
Gambar 3.2
Class Diagram ..........................................................................................54
Gambar 3.3
Use Case...................................................................................................55
Gambar 3.4
Sequence Diagram Generate Population..................................................56
Gambar 3.5
Sequence Diagram Generate Jadwal Basic ..............................................58
Gambar 3.6
Sequence Diagram Generate Jadwal Advance.........................................60
Gambar 3.7
Sequence Diagram View Prioritas Asisten ..............................................61
Gambar 3.8
Sequence Diagram View Kualifikasi Asisten ..........................................63
Gambar 3.9
Sequence Diagram View Jadwal Kuliah dan Jadwal Mengajar Per Asisten ..................................................................................................................65
xiii
Gambar 3.10 Sequence Diagram View Jadwal Mengajar Seluruh Asisten...................66 Gambar 3.11 Rancangan Layar Form Utama ................................................................67 Gambar 3.12 Rancangan Layar Form View Jadwal Mengajar dan Kuliah Per Asisten 68 Gambar 3.13 Rancangan Layar Form View Kualifikasi Asisten...................................68 Gambar 3.14 Rancangan Layar Form View Prioritas Mengajar Asisten ......................69 Gambar 3.15 Rancangan Layar Form View Jadwal Mengajar Asisten.........................69 Gambar 3.16 Rancangan Layar Form Basic ..................................................................70 Gambar 3.17 Rancangan Layar Form Advance.............................................................70 Gambar 3.18 Rancangan Layar Form Generate Population ..........................................71 Gambar 3.19 Entity Relationship Diagram....................................................................72 Gambar 3.20 Jadwal Alokasi Ruang..............................................................................82 Gambar 3.21 Gambar Jadwal Hasil Random.................................................................88 Gambar 3.22 Jadwal Hasil Proses Algoritma Genetik.................................................110 Gambar 4.1
Form Utama ...........................................................................................112
Gambar 4.2
Form View Jadwal Mengajar dan Kuliah Per Asisten...........................115
Gambar 4.3
Form View Kualifikasi Asisten..............................................................116
Gambar 4.4
Form Prioritas Mengajar Asisten ...........................................................117
Gambar 4.5
Form View Jadwal Mengajar Asisten ....................................................118
Gambar 4.6
Form Generate Jadwal Basic..................................................................119
Gambar 4.7
Form Generate Jadwal Advance ............................................................120
Gambar 4.8
Form Generate Population .....................................................................121
Gambar 4.9
Laporan Jadwal Mengajar Asisten .........................................................122
Gambar 4.10 Help ........................................................................................................123 Gambar 4.11 Grafik Hasil Pengujian Terhadap Ukuran Populasi ...............................125 xiv
Gambar 4.12 Grafik Hasil Pengujian Terhadap Selection Rate...................................126 Gambar 4.13 Grafik Hasil Pengujian Terhadap Mutation Rate...................................127 Gambar 4.14 Grafik Hasil Pengujian Terhadap Crossover Method ............................128 Gambar 4.15 Grafik Proses Eksekusi dalam Pengujian Ukuran Populasi...................130
xv
DAFTAR LAMPIRAN
Lampiran 1 - Hasil Wawancara I .................................................................................... L1 Lampiran 2 - Hasil Wawancara II................................................................................... L6 Lampiran 3 - Daftar Asisten............................................................................................ L8 Lampiran 4 - Daftar Matakuliah ..................................................................................... L9 Lampiran 5 - Daftar Kuliah Asisten.............................................................................. L10 Lampiran 6 - Daftar Matakuliah yang Telah Diikuti oleh Asisten ............................... L14 Lampiran 7 - Daftar Asisten yang Memiliki Kualifikasi Mengajar Matakuliah........... L17 Lampiran 8 - Daftar Prioritas Mengajar Matakuliah yang Diisi oleh Asisten .............. L19
xvi
