PROSIDING
SNTI 2011 SEMINAR NASIONAL TEKNOLOGI INFORMASI
VOL. 8 No. 1 Tahun 2011 ISSN: 1829-9156
26 NOVEMBER 2011 UNIVERSITAS TARUMANAGARA JAKARTA
Fakultas Teknologi Informasi Universitas Tarumanagara Jakarta
KATA SAMBUTAN KETUA PELAKSANA Puji dan syukur sudah sepantasnya kita panjatkan kepada Tuhan Yang Maha Esa karena atas rahmat dan karunia Nya kita dapat berkumpul di Universitas Tarumanagara Jakarta dalam rangka melaksanakan Seminar Nasional Teknologi Informasi (SNTI) 2011. SNTI merupakan kegiatan rutin tahunan dari Fakultas Teknologi Informasi Universitas Tarumanagara sejak tahun 2004. Seminar ini bertujuan untuk menjadi sarana bertukar pikiran dan gagasan yang merupakan hasil kajian maupun penelitian dari para akademisi, peneliti maupun praktisi di bidang teknologi informasi dan bidang-bidang lain yang berkaitan. SNTI 2011 mengambil tema “ICT Technopreneurship : Opportunities and Challenges” dengan dua pembicara utama yaitu Prof. Ir. Abdullah Alkaff, Ph.D ( Staf Ahli Menteri Pendidikan dan Kebudayaan) dan Onno W.Purbo, Ph.D (Pakar ICT) . Jumlah makalah yang diseminarkan pada SNTI 2011 sebanyak 40 makalah dari 51 makalah yang diseleksi. Makalah yang diterima telah dibukukan dalam prosiding SNTI 2011. Kami mengucapkan terima kasih kepada pembicara utama, para pemakalah dan peserta yang telah hadir dalam seminar serta kepada bebagai pihak yang telah membantu terlaksananya kegiatan seminar ini. Kami menyadari bahwa masih terdapat kekurangan-kekurangan dalam penyelenggaraan seminar ini. Untuk itu atas nama panitia kami mohon ma’af apabila ada hal-hal yang kurang berkenan. Semoga seminar ini bermanfaat, selamat mengikuti seminar dan sampai bertemu kembali pada SNTI 2012 dan Seminar Internasional 2012 yang akan dieslenggarakan pada bulan September 2012. Jakarta, 26 November 2011
Bagus Mulyawan,S.Kom.,MM Ketua Pelaksana
ii
KATA SAMBUTAN DEKAN FAKULTAS TEKNOLOGI INFORMASI UNIVERSITAS TARUMANAGARA Puji syukur kepada Tuhan Yang Maha Esa, dengan Rahmat dan KaruniaNya, Fakultas Teknologi Informasi Universitas Tarumanagara dapat menyelenggarakan kegiatan Seminar Nasional Teknologi Informasi (SNTI) yang ke 8 tahun 2011. SNTI dilaksanakan sejak tahun 2004, merupakan kegiatan pertemuan ilmiah tahunan antar para peneliti, prktisi dan pengguna teknologi informasi dan komunikasi untuk saling tukar menukar informasi, menyebarkan pengetahuan dan pengalaman di bidang teknologi informasi dan komunikasi terkini, serta dapat saling menjalin jaringan dan kerjasama. Pada SNTI 2011 memilih Tema : “ICT Technopreneurship : Opportunities and Challenges” Tema ini dipilih dengan tujuan untuk meningkatkan semangat kewirausahaan yang berbasis teknologi , khususnya teknologi informasi. Dengan kemampuan kewirausahaan yang bersinergi dengan teknologi kita harapkan dapat menunjang kemandirian masyarakat. Seminar tahun ini juga mengelompokkan menjadi 5 topik makalah yaitu : Computational, Intelligent System & Application, Instrumentation, Information System & Applications, dan Networking & Distributed System. Perkenankanlan saya mengucapkan terimakasih kepada saudara Bagus Mulyawan, S.Kom, MM dan Zyad Rusdi,M.Kom yang telah bekerja keras mengkoordinir kegiatan SNTI tahun ini dengan baik, dan perkenankan juga saya mengucapkan terimakasih kepada seluruh panitia SNTI dosen, karyawan dan mahasiswa Fakultas Teknologi Informasi yang telah membantu dalam persiapan dan pelaksanaan seminar ini. Harapan kami, tahun mendatang SNTI dapat diikuti oleh lebih banyak peserta dengan topik terbaru yang lebih menarik. Kami ucapkan terimakasih kepada, Bapak Prof. Ir. Abdullah Alkaff, Ph.D, dan Bapak Onno W.Purbo, Ph.D , yang telah meluangkan waktu sebagai pembicara Utama , terimakasih pula kepada para pemakalah dan peserta seminar atas partisipasinya. Mohon maaf apabila dalam penyelenggaraan seminar ini terjadi kekurangan dan tidak berkenan di hati bapak/ ibu, Semoga seminar ini bisa bermanfaat bagi peningkatan kehidupan masyarakat secara umum . Jakarta, 26 November 2011 Dekan
Dra. Ery Dewayani,MMSI iii
PANITIA SNTI 2011 Penanggung Jawab
:
Dra. Ery Dewayani,MMSI Dr. Ir. Dyah Erni Herwindiati, M.Si Prof. Dr. Ir. Dali S. Naga , MMSI Prof. Dr. Ir. Aniati Murni., M.Sc Prof. Jazi Eko Istiyanto, M.Sc., Ph.D Prof. Dr. Ir. Eko Sediyono, M.Kom Ir. Jap Tji Beng, MMSI., Ph.D Dr. Ir. Dyah Erni Herwindiati, M.Si Tony Mulia, Ph.D Lina , ST., M.Kom., Ph.D Ir. Dana Indra Sensuse, MLIS., Ph.D Wisnu Djatmiko,ST., M.Kom., Dr. Eng M. Rahmat Widyanto, Dr. Eng Agus Hardjoko,M.Sc., Ph.D Retantyo Wardoyo, M.Sc., .Ph.D Sri Hartati, M.Sc., Ph.D Dr. Ir. Agus Buono , M.Si., M.Kom Dr. Ir. Aji Hamim Wigena, M.Sc Dr. Ir. Sri Nurdiati, M.Sc
(DEKAN FTI) (PUDEK FTI) (UNTAR) (UI) (UGM) (UKSW) (UNTAR) (UNTAR) (UNTAR) (UNTAR) (UI) (UI) (UI) (UGM) (UGM) (UGM) (IPB) (IPB) (IPB)
Komite Program
:
Ketua Pelaksana
:
Bagus Mulyawan,S.Kom.,MM
(UNTAR)
Komite Pelaksana
:
Zyad Rusdi, M.Kom Dra. Chairisni Lubis, M.Kom Ir. Jeanny Pragantha,M.Sc. Sani M. Isa , M.Si., M.Kom Dedi Trisnawarman,M.Kom Helmi Thendean, ST., M.Kom Lely Hiryanto, ST., M.Sc Susany Soplanit,ST., M.Kom Desi Arisandi, S.Kom., MTI Viny Christanti, S.Kom., M.Kom Wasino, S.Kom., M.Kom Tony,M.Kom Agus Budi Darmawan,MT,M.Sc Ruwanto,S.Kom Susanti,SE
(UNTAR) (UNTAR) (UNTAR) (UNTAR) (UNTAR) (UNTAR) (UNTAR) (UNTAR) (UNTAR) (UNTAR) (UNTAR) (UNTAR) (UNTAR) (UNTAR) (UNTAR)
iv
DAFTAR ISI Kata Sambutan Ketua Pelaksana
ii
Kata Sambutan Dekan Fakultas Teknologi Informasi
iii
Susunan Panitia
iv
Daftar Isi
V
A. ALGORITHM, INTELLIGENT SYSTEM, COMPUTATIONAL A1
Implementation Of Fuzzy If-Then Rules And Fuzzy Histogram Hyperbolization On Digital Mammography Enhancement
Susany Soplanit Helmi Thendean Meylina Sugiharto
1
A2
Pengaruh Windowing Pada Akurasi Hasil Klasifikasi Tahapan Tidur
Ary Noviyanto Sani M. Isa Aniati Murni Arymurthy
6
A3
Klasifikasi Tekanan Intrakranial Menggunakan Possibilistic C-Means
Putu Wira Angriyasa Zuherman Rustam Wismaji Sadewo
12
A4
Analisa Penentuan Layak Tambang Bentonit Provinsi Jawa Timur Dengan ANP
Erlin Windia Ambarsari Khamami Herusantoso
17
A5
Perancangan Program Klasifikasi Penutup Lahan Citra Satelit Menggunakan Analisis Diskriminan
Melisa, S.Kom Dyah Erny H Sani M.Isa
22
A6
Program Bantu Pendeteksi Kanker Rahim
Marvin Chandra W Semuil Tjiharjadi
28
A7
Kuantisasi Ruang Warna Hsl Untuk Pewarnaan Peta Dasar
Darma Rusjdi
34
A8
Implementasi Metode Tabu Search Untuk Penjadwalan Kelas
Ade Trisnawati Iriansyah BM Sangadji Sely Karmila
39
A9
Fuzzy Parametric Sample Selection Models Of Married Women By Mle : Case Study The Mpfs-1994
Yaya Sudarya Triana L. Muhamad Safiih
45
A10
Aplikasi Online Spherical K-Means Untuk Mendiagnosa Cancer Berdasarkan Konsentrasi Unsur Kimia Dalam Darah
Zuherman Rustam
51
A11
Implementasi Fuzzy Multi-Attribute Decision Making Dengan Pendekatan Simple Additive Weighting Untuk Membantu Mutasi Pendeta Gereja Minahasa
Daniel Riano Kaparang Yos Richard Beeh Eko Sediyono
54
v
A12
Komparasi Model Clustering Menggunakan Metode K-Means Dan Fcm Dalam Menentukan Kuantifikasi Kriteria .
A13
Pengembangan Transliterator Aksara Jawa Dengan Menggunakan Ibus Framework Tri Hartanto Noor Hendratwan Tedy Setiadi Dan Ekspresi Reguler Dewi Soyusiawati
68
A14
Image Color Watermarking Dengan Paralelisasi Block-Based Svd
Lely Hiryanto Harprori Patti Lina
75
A15
Aplikasi Antivirus Menggunakan Teknik Pendeteksian Md5 Checksum Dan Pendekatan Heuristic
Wasino, Herman Deven Prawito
81
A16
Metode K-Nearest Neighbors Untuk Aplikasi System Informasi Geografis Track Record Penyakit Pada Rsu Dr. Soetomo
Gregorius S. Budhi Silvia Rostianingsih Oviliani Yenty Yuliana Darmawan S. Putra
85
A17
Perancangan Edugame History Tell Of Pangeran Antasari
Jeanny Pragantha . Yonathan Justianus Muliawan Darius Andana Haris
92
A18
Perolehan Opini Pada Dokumen Blog
Eddy Agus Sofian Viny Christanti Jeanny Pragantha
97
Berbahasa Indonesia
Dine Tiarakusuma Iriansyah BM.Sangadji Dewi Arianti W
60
B. INFORMATION SYSTEM B1
Pengembangan Model Manajemen Sumber Daya Manusia Berbasis Decision Support Systems: Studi Kasus Sekretariat Pemerintahan Kota Depok
Dedi Trisnawarman Zyad Rusdi
1
B2
Rancang Bangun Sistem Pendukung Keputusan Kelulusan Sertifikasi Guru
Edi Setiawan Eko Sediyono Kodrat Iman Satoto
7
B3
The Implementation Of Canreg5 Software For Indonesian Cancer Registry.
Jonathan Aditya Mulyono
13
B4
Pengembangan Model Egovernment Pada Pemerintahan Daerah; Studi Kasus Pemerintah Daerah Kabupaten Musi-Rawas
Zyad Rusdi Dedi Trisnawarman Wasino
20
B5
Implementasi CBIA - DM pada Sistem Informasi berbasis SMS untuk self management penyandang Diabetes Mellitus
Irya Wisnubhadra Reinard Kristyanto, Th. B. Titien S. Hartayu
27
vi
B6
Pengembangan Sistem Informasi Tanaman Obat Indonesia Berbasis Linked Data
Hendrik , Ikhwanur Rahman
32
B7
Implementasi E-Learning Pada Amik Panca Bhakti Pontianak
Robertus Laipaka Aripin Manurung Edi Setiawan
38
B8
Perancangan Strategis E-leraning Pada Proses Belajar Mengajar Sebagai Aplikasi Peningkatan Kualitas Siswa (Studi Kasus Pada SMK Xaverius 1 Palembang)
Nyimas Artina
43
B9
Mengelola Proyek E- Commerce Management Project Dan Subversion
Sofi Defianti Dian Ambar Wasesha
49
B10
Penerapan Enterprise Resource Enterprise
Julisar
55
B11
Pemanfaatan Website Sebagai Media Promosi Pada Industri Kerajinan Di Daerah Tasikmalaya Jawa Barat
Rodiah ,Bagus Mulyawan,
62
B12
Pemetaan Tata Kelola Teknologi Informasi Menggunakan Cobit Framework Studi Kasus Rumah Sakit “X”
Bagus Mulyawan Ery Dewayani Wasino
69
Menggunakan
Planning
Di
Redmine
Small-Medium
C. NETWORK, DISTRIBUTED SYSTEM,INSTRUMENTATION C1
Object Position Estimation And Tracking Using An Active Camera Network.
Agus Budi Dharmawan Karl Kleinmann Hermann Meuth Mauridhi Hery Purnomo
1
C2
Perancangan Robot Surveillance Pendeteksi Tekanan Udara Dan Temperatur
Irvan Sunardi, Toni Mulia, Tony
7
C3
Pengembangan Virtual Market Untuk Memperluas Pasar Hasil Pertanian Di Indonesia (Studi Kasus: Gabungan Kelompok Tani Padi di Kabupaten Demak)
Johan J.C Tambotoh, Wiwin Sulistyo
13
C4
Pengembangan Aplikasi Voip Phone Berbasis Web Dengan Red5 Dan Library Mjsip
Muchammad Husni Erina Letivina Angraini Frenda Rangga Aksara
19
C5
Cell Broadband Architecture Engine Exploitation
Suryo Bramasto
25
vii
C6
Realisasi Novel Elektronik Pada Telepon Genggam Dengan Sistem Operasi Android
Timothy Rainier A. Farid Thalib
35
C7
Prototipe Sms Gateway Sebagai Media Konvergensi Bencana Alam Gempa Bumi
Hernando Ivan Teddy
41
C8
Sistem Pelaporan Dan Informasi Posisi Kereta Api Berbasis Global Positioning System (Gps) Pada Device Berbasis Android
Ary Mazharudin Shiddiqi Adhitya Bhawiyuga Baskoro Adipratomo
45
C9
Sistem Informasi Geografis (Sig) Untuk Optimasi Jalur Disribusi Bahan Bakar Minyak (Bbm
Edy Irwansyah Tani Kusumawardana Fariz Aldriansyah
51
C10
Mail Server Zimbra Menggunakan Teknologi Virtualisasi Di Smk Negeri 1 Tangerang
Herman, S.Kom, MM Heru Soetanto Putra Sugar
58
viii
Seminar Nasional Teknologi Informasi 2011
A8
IMPLEMENTASI METODE TABU SEARCH UNTUK PENJADWALAN KELAS 1)
2)
Ade Trisnawati , Iriansyah BM Sangadji , Sely Karmila
3)
1), 2), 3)
Teknik Informatika Sekolah Tinggi Teknik PLN Jl. Lingkar Luar Duri Kosambi Jak Bar 11750
Email:
[email protected],
[email protected] untuk setiap kelas. Pekerjaan penjadwalan mata kuliah ini akan semakin berat jika melibatkan semakin banyak kelas perangkatannya. Pada saat ini sebagian besar pembuatan jadwal masih belum memiliki proses yang lebih efisien. Hal ini dibuktikan dengan masih digunakan cara; taf tata usaha akan mendata seluruh mata kuliah yang akan dibuka pada suatu semester. Kemudian mencatat prioritas-prioritas yang akan diberikan terhadap suatu mata kuliah. Baru kemudian mengatur penjadwalan, dan membuat laopran jadwal kuliah dengan menggunakan Microsoft Excel. Proses seperti ini membutuhkan banyak variable seperti dosen, mata kuliah, hari, ruang dan waktu (ketersediaan dosen), masing-masing variable terdiri dari sejumlah dosen, enampuluhan mata kuliah dengan 156 sks, 5 hari, dan terdapat 16 ruangan. Selain itu proses ini membutuhkan ketelitian dan waktu pengerjaan yang tidak singkat, sehingga seringkali terjadi jadwal yang bentrok yang menyebabkan suasana belajar mengajar terhambat. Diharapkan dengan digunakannya algoritma Tabu Search akan diperoleh optimasi penjadwalan yaitu kondisi dimana terjadi kombinasi terbaik untuk pasangan mata kuliah dan dosen pengajar secara keseluruhan, tidak ada permasalahan bentrokan jadwal, serta ketersediaan ruang yang cukup dan sesuai secara fasilitas untuk seluruh mata kuliah yang ada. Berdasarkan uraian tersebut maka dalam penelitian ini akan dijelaskan bahwa dengan bantuan algoritma Tabu Search penyusunan penjadwalan mata kuliah dapat dioptimalkan. Program dapat mencari solusi penjadwalan pada waktu yang dapat digunakan baik oleh dosen, kelas maupun ruangan yang terlibat dalam suatu mata kuliah.
ABSTRACT Scheduling is an activity to allocate a number of resources available. This activity is done to ensure that planning can go well with the time and energy used efficiently. Taboo search algorithm will keep the best solution is not lost by storing the best solution and continue to search by last solution. This algorithm is forbidden to use solutions that have been used so as to avoid useless repetition. The solution of this paper is the schedule of implementation of the model generated using taboo search
Key words Taboo search, Schedulling , Implementation Methode
1. Pendahuluan Penjadwalan merupakan kegiatan untuk mengalokasikan sejumlah sumber daya yang tersedia. Kegiatan ini dilakukan untuk memastikan bahwa perencanaan dapat berjalan dengan baik dengan waktu dan tenaga yang digunakan secara efisien. Banyak modelmodel penjadwalan yang telah digunakan. Berbagai algoritma telah banyak juga dimanfaatkan. Penjadwalan kelas merupakan kegiatan yang mengawali pergantian semester di setiap perguruan tinggi. Proses ini harus memperhitungkan banyaknya mata kuliah, ketersediaan ruang, dan rentang waktu yang digunakan. Inti dari penjadwalan kuliah adalah menjadwalkan beberapa komponen yang terdiri dari mata kuliah, ruang, dan waktu dengan memperhatikan sejumlah batasan dan syarat tertentu. Permasalahan yang dihadapi penjadwal terletak pada lebih banyaknya mata kuliah yang harus dijadwalkan daripada ruang yang tersedia, kesesuaian kebutuhan perkuliahan dengan fasilitas ruangnya, kapasitas ruang yang harus sesuai dengan jumlah mahasiswa, serta keinginan pengajar untuk mengajar pada suatu hari atau jam tertentu. Distribusi jadwal perkuliahan juga diharapkan dapat merata tiap harinya
2. Tujuan 1. 2.
39
Mengimplementasikan Algoritma Tabu Search dalam penjadwalan perkuliahan. Menghasilkan solusi penjadwalan yang optimal.
A8
Seminar Nasional Teknologi Informasi 2011
(kls)i = Jumlah kelas matakuliah ke-i S = Total nilai cost r = Nilai cost total yang dihasilkan
3. Teori 3.1. Penjadwalan
3.2. Tabu Search
Penjadwalan menurut Rosani Ginting[1] adalah pengalokasian sumber daya pada objek-objek yang ada pada ruang waktu dan bergantung pada kendala-kendala yang sedemikian sehingga sedapat mungkin memenuhi sekumpulan sasaran yang diinginkan. Secara sederhana, penjadwalan dapat diartikan sebagai pengalokasian sumber-sumber daya yang tersedia pada ruang waktu yang ada sehingga memenuhi kondisi-kondisi tertentu. Tujuannya adalah untuk memaksimalkan suatu proses dengan tetap menjaga agar tidak melanggar constraint yang berlaku pada proses yang bersangkutan. Penjadwalan kuliah merupakan salah satu masalah optimasi, dimana definisi optimasi adalah sarana untuk mengekspresikan model matematika yang bertujuan memecahkan masalah dengan cara yang tepat
Menurut F Glover[2] Tabu search adalah teknik local search yang memilih langkah berikutnya (neighborsolution) berdasarkan constraint dan pinalty. Setiap constraint yang ada akan didefenisikan dengan sebuah nilai pinalty yang akan dikenakan apabila constraint itu terlanggar. Metode ini menggunakan Tabu List untuk menyimpan sekumpulan solusi yang baru saja dievaluasi. Selama proses optimasi, pada setiap iterasi, solusi yang akan dievaluasi akan dicocokkan terlebih dahulu dengan isi Tabu List untuk melihat apakah solusi tersebut sudah ada pada Tabu List. Apabila solusi tersebut sudah ada pada Tabu List, maka solusi tersebut tidak akan dievaluasi lagi pada iterasi berikutnya. Sejumlah pengembangan yang baru dari Tabu Search memungkinkan sebuah solution diterima kembali menjadi current solution apabila nilai pinalty keseluruhan jauh lebih kecil daripada solusi sebelumnya menurut batasan-batasan tertentu. Glover mengatakan bahwa prosedur TS ini dapat ditemukan dalam tiga pola (scheme) utama. Pola pertama adalah adanya penggunaan struktur memori berbasiskan atribut-atribut fleksibel yang dirancang untuk membolehkan sebuah kriteria evaluasi dan hasil pencarian di masa lalu dieksploitasi lebih mendalam. Pola ini menjadikan TS berbeda dengan aplikasi lain yang menggunakan struktur memori yang rigid (kaku) atau tanpa menggunakan struktur memori (seperti simulated annealing). Pola kedua adalah penggunaan mekanisme atau kondisi yang dapat membatasi atau membebaskan suatu proses pencarian yang sedang berlangsung. Pola tabu kedua ini dikenal sebagai mekanisme restriction dan aspiration criteria. Pola ketiga adalah pelibatan suatu fungsi memori dengan rentang waktu yang berbeda yakni berupa memori jangka pendek (short term memory) dan memori jangka panjang (long term memory) untuk menjalankan strategi intensifikasi dan diversifikasi dalam proses pencarian solusi. Strategi intensifikasi adalah strategi pencarian yang mengarahkan/ mengfokuskan pencarian pada suatu area tertentu, sedangkan strategi diversifikasi adalah strategi pencarian yang mengarahkan pencarian pada area baru. Setiap constraint yang ada akan didefinisikan sebagai sebuah nilai pinalti yang akan dikenakan apabila constraint ini dilanggar.
Constraint Di dalam penjadwalan dikenal 2 macam constraint ( persyaratan) yaitu Hard Constraint dan Soft Constraint. Constraint penjadwalan perkuliahan yang berlaku tentunya berbeda tergantung dari aturan dan tata cara perkuliahan dari institusi yang bersangkutan. Constraint pada umumnya terbagi menjadi dua jenis yaitu hard constraint dan soft constraint. Hard constraint adalah batasan yang wajib untuk dipenuhi atau tidak boleh dilanggar, sementara soft constraint adalah batasan yang masih memberi toleransi terhadap pelanggaran, namun sebisa mungkin diminimalisir pelanggarannya. Contoh hard constraint dan soft constraint pada kasus penjadwalan perkuliahan adalah : 1. Mata kuliah yang berbeda tidak boleh dijadwalkan pada waktu dan tempat yang sama, serta mahasiswa tidak boleh menghadiri 2 mata kuliah pada waktu yang sama (hard constraint). 2. Dalam satu hari mahasiswa tidak boleh menghadiri lebih dari 3 x timeslot kuliah berturut-turut,harus ada jeda minimal 1 timeslot (soft constraint). Perhitungan Constraint
Cji n
S
n
j 1
i 1
(kls)i n
i 1
r S1 S 2.....Sn
…(1)
Prosedure dari metode TS adalah : 1. Pilih inisialisasi solusi i dalam S. Set i*=i dan k=0. 2. Set k=k+ 1 dan buat subset V* dari solusi dalam N(i,k) sedemikian sehingga kondisi TS tr(i,m) )∈ Tr
Dimana : Cji = Nilai cost constraint ke-j pada kelas mta kuliah ke-i 40
Seminar Nasional Teknologi Informasi 2011
A8
neighbour solution tersebut harus ditolak dan proses dilanjutkan dengan memeriksa neighbour solution yang baru. Dengan demikian dengan adanya tabu list dapat menghindari cycles (iterasi berjalan terus tanpa memperbaiki kualitas solusi). Tabu list bisa disimpan dalam bentuk array atau tree, tergantung dari masalah dan implementasi yang diinginkan. Ukuran tabu list dapat mengikuti aturan berikut : 1. Menggunakan ukuran tabu list statis. Ukuran tabu list tidak berubah sesuai dengan yang telah ditentukan sebelumnya. 2. Ukuran tabu list disesuaikan dengan masalah. Semakin besar masalah, semakin besar juga ukuran tabu list yang dibutuhkan. 3. Mengubah ukuran tabu list sesuai dengan kualitas solusi. Move adalah suatu cara untuk menghasilkan solusi yang baru di dalam sebuah neighborhood. Dalam penjadwalan matakuliah move bisa berupa : a) Pertukaran nilai dalam 2 baris atau kolom yang berbeda b) Pergeseran nilai yang ada dalam suatu baris dan
dilanggar (r=i,...,t) atau sedikitnya satu dari kondisi dipenuhi a (i,m) ∈A (i,m) terpenuhi (r=i,...,a). 3. Pilih yang terbaik j = i ⨁ m dalam V* (yang didasarkan pada atau fungsi yang sudah dirumuskan) dan set i = j. 4. Jika f(i) < f(i*) maka set i*=i. 5. Perbaharui tabu dan kondisi aspirasi 6. Jika tercapai kondisi pemberhentian, hentikan.Jika tidak, kembali ke langkah 2. Algoritma Tabu search Mulai
Pilih solusi awal i dalam S
Set k = k+1
Buat subset V* dari N(i,k)
Pilih nilai terbaik j = i Tidak
Set i = j
kolom Cari f(i) < f (i*) dan set i* = i
Perpindahan nilai yang ada pada suatu baris atau kolom ke baris atau kolom lainnya.
Kondisi pemberhentian terpenuhi?
4. Metodologi Mulai
Ya
Identifikasi Masalah
Selesai
Rumusan Masalah
Gambar 1 Flowchart Algoritma Tabu search
Kajian Pustaka
Keterangan : S = himpunan semesta dari fungsi tujuan i = solusi awal k = iterasi V* = nilai subset optimal dari N(i,k) j = solusi tetangga terbaik dari V* f(i) = nilai fungsi dengan variabel i
Pengumpulan Data
Sistem Berjalan
Analisis Sistem
Sistem dg Algoritma Tabu Search
Menentukan data input sistem
Pemberian nilai cost pada tiap parameter
Mempresentasikan dengan tabu search
Analisis Kebutuhan Sistem
Perancangan Sistem Penjadwalan
f(i*) = nilai fungsi dengan variabel optimal Tabu List
Perancangan Proses
Tabu list digunakan untuk menyimpan n solusi yang sudah dikunjungi sebelumnya. Jadi setiap current solution yang ditinggalkan akan dicatat dan dimasukkan ke dalam sebuah daftar yang disebut tabu list. Tabu list juga digunakan untuk menghindari diterimanya kembali solusi sebelumnya menjadi current solution pada looping selanjutnya. Sebelum sebuah neighbour solution diperiksa, terlebih dahulu harus diperiksa apakah solusi tersebut sudah pernah masuk ke dalam tabu list. Jika sudah maka
Perancangan Basis Data
Perancangan Antar Muka
Perancangan Program Implementasi dan Pengujian Sistem Berhasil Ya
Pembahasan & Penulisan Laporan Selesai
Gambar 2 Metodologi Penelitian dan PerancanganTabu Search
41
Tidak
A8
Seminar Nasional Teknologi Informasi 2011
b. Jumlah mata kuliah adalah 68 mata kuliah dengan 146 sks. Semester gasal: 34 mata kuliah dan 79 sks Semester genap: 34 mata kuliah dan 77 sks c. Waktu perkuliahan yang diperbolehkan adalah Senin - Jumat pukul 08.00 – 16.10 WIB. d. Jumlah ruang kelas ada 17 ruang yang terdiri dari 12 ruang belajar kelas dan 5 laboratorium. 4. Program kuliah satu SKS setara dengan 50 menit kegiatan tatap muka terjadwal, merupakan perkuliahan dimana dosen memberikan bahan kuliah di kelas untuk dipahami dan dimengerti.
Alat dan Bahan Alat Penelitian 1.
Alat – alat yang digunakan dalam penelitian meliputi : Spesifikasi Hardware a. Prosesor Intel(R) Atom(TM) CPU N475 @1,83GHz 1,83 GHz b. RAM 1 GB c. HDD 320 GB d. Keyboard dan Mouse e. Monitor f. Printer 2. Spesifikasi Software a. Sistem operasi yang digunakan, yaitu Windows 7 Home Premium b. Microsoft office Word 2007, Microsoft Visio 2007, SQL Server Management Studio Ekspress 2005, Microsoft Visual Studio 2010.
Menentukan Nilai Cost parameter Perhitungan cost pada algoritma Tabu Search telah dirancang untuk menghasilkan nilai 0, apabila kelas tersebut sudah memiliki komposisi dosen dan waktu kuliah yang paling baik, yang tidak melanggar semua constraint yang ada. Sebaliknya apabila nilainya mendekati 1, dapat disimpulkan bahwa jadwal yang dimiliki kelas tersebut mengandung banyak pelanggaran soft constraint. Rumus untuk menghitung nilai cost :
Bahan Penelitian Adapun bahan penelitian yang digunakan dalam pembuatan makalah ini, dan dijadikan acuan oleh penulis adalah sebagai berikut : 1. Daftar data dosen berupa kode dosen, nama dosen dan gelar. 2. Daftar data mata kuliah berupa kode mata kuliah, nama mata kuliah, semester dan SKS. 3. Daftar data ruang, berupa kode ruang dan kapasitas.
Sd
Sk
3.
dh
…..(2)
Nd .Nh
C k 1 h 1
Proses pembuatan jadwal kuliah mengenai penetapan waktu, mata kuliah dan dosen yang mengajar di lakukan oleh sekretaris jurusan sedangkan penetapan dilakukan oleh oleh staf tata usaha Jurusan Teknik Informatika. Pengaturan jadwal kuliah dilakuakan setiap tahun sebanyak dua periode, yaitu : a. Semester ganjil : awal September – akhir februari tahun berikutnya. b. Semester genap : awal maret – akhir agustus tahun yang sama. Data yang digunakan adalah nama dosen, nama mata kuliah, waktu kesediaan dosen mengajar, jumlah kelas dan ruangan yang tersedia. a. Jumlah dosen berjumlah 31 orang yang terdiri dari 22 orang dosen tetap dan 9 orang dosen tidak tetap.
kh
Nk.Nh
r Sd Sk
Constrain yang berlaku :
2.
d 1 h 1
Nk Nh
5. Analisis
1.
C Nd Nh
…(3) ....(4)
Keterangan dimana : Cdh : Jumlah cost untuk dosen ke d pada hari ke h Ckh: Jumlah cost untuk kelas ke k pada hari ke h dimana cost a ≤ x ≤ b ,0 b ≤ x ≤ c , (x-b/c-b) c ≤ x ≤ d,1 Sk : Total nilai cost pada soft constraint kelas Sd : Total nilai cost pada soft constraint dosen Nk : Jumlah kelas Nh : Jumlah hari Nd : Jumlah seluruh dosen r : Nilai cost total yang dihasilkan Agar solusi yang diinginkan tercapai, tiap pelanggaran soft constraint didefinisikan sebagai nilai cost yang berbeda. Hal ini dilakukan karena tingkat keharusan untuk 42
Seminar Nasional Teknologi Informasi 2011
A8
b. Nilai-nilai parameter yang digunakan untuk pengujian yaitu Random search, TSMaxIter dan Target Cost. c. Masing-masing skenario dilakukan 10 kali uji untuk mendapatkan hasil pengujian yang valid.
memenuhi sebuah soft constraint berbeda antara satu dengan yang lain. Soft constraint yang lebih perlu untuk dipenuhi diberi bobot yang lebih tinggi dari pada soft constraint yang dipandang lebih bisa ditoleransi. Berikut adalah nilai cost untuk masing-masing pelanggaran soft constraint: Jadwal mengajar seorang dosen dalam sehari maksimal 6 slot waktu.
Tabel 1Hasil Pengujian no
Random
TSMaxiter
Rata-rata Cost
1
100
5
0,345296
2
500
5
0,219553
3
300
7
0,618906
4
500
7
0,219546
5
300
8
0,319268
6
500
8
0,119103
7
300
9
0,218819
8
500
9
0,119268
9
50
10
0,119478
10
300
10
0,019466
11
500
10
0,219368
12
1000
10
0,319608
1 x 6 , 0 x6 Maxd 6 x 10, 4 U = [1,12] 10 x 12, 1
Setiap jadwal kelas mahasiswa dalam sehari dijadwalkan maksimal adalah 6 slot waktu. 1 x 6 , 0 x6 Maxk 6 x 10, 4 U = [1,12] 10 12 , 1 x
Tabel 2 Detil Pengujian Total Hard
Total Soft
Total Cost
0,01843
0
0,02028
0,02028
0,02003
0
0,02003
0,02003
0,00062
0,01923
0
0,01985
0,01985
0
0,00062
0,02003
0
0,02065
0,02065
0
0
0,00062
0,01603
0
0,01665
0,01665
0
0
0
0,00123
0,01923
0
0,02046
0,02046
7
0
0
0
0
0,01843
0
0,01843
0,01843
8
0
0
0
0
0,02003
0
0,02003
0,02003
9
0
0
0
0
0,01843
0
0,01843
0,01843
10
0
0
0
0,00062
0,01923
0
0,01985
0,01985
jumlah
0
0
0
0,00556
0,1891
0
0,19466
rata-rata
0
0
0
0,000556 0,01891
0
0,19466 0,0194 66
No
HD
HR
HM
SD
1
0
0
0
0,00185
2
0
0
0
0
3
0
0
0
4
0
0
5
0
6
SK
Merepresentasi dengan Tabu Search 1. 2. 3.
4. 5. 6.
Cari kelas yang memiliki nilai cost yang terbesar atau paling banyak melanggar soft constraint. Cari kombinasi komponen utama yang memenuhi hard constraint. Periksa apakah neighbour solution sudah tercatat dalam Tabu List, bila sudah kembali kelangkah ke dua. Alokasikan komponen–komponen utama penjadwalan. Catat neighbour solution ke dalam Tabu List. Periksa nilai cost secara keseluruhan apakah telah memenuhi syarat untuk berhenti, jika belum maka ulangi langkah 1.
0,019466
Keterangan nilai pinalti pada tabel diatas adalah sebagai berikut : o Hd adalah besarnya nilai pinalti (pelanggaran) hard constraint dosen. o Hr adalah besarnya nilai pinalti (pelanggaran) hard constraint ruang o Hm adalah besarnya nilai pinalti (pelanggaran) hard constraint kelas mahasiswa o Sd adalah besarnya nilai pinalti (pelanggaran) soft constraint dosen (dalam himpunan fuzzy). o Skk adalah besarnya nilai pinalti (pelanggaran) soft constraint kelas kuliah (dalam himpunan fuzzy) .
7. Pembahasan Hasil Skenario Pengujian Skenario pengujian yaitu mengobservasi parameterparameter yang digunakan pada Algoritma Tabu Search (TS) pada Soft Constraint, yaitu Random search, TSMaxIter dan Target Cost. Hal ini bertujuan untuk melihat bagaimana pengaruh masing-masing parameter pada algoritma, sehingga untuk menghasilkan solusi yang optimal bisa menggunakan parameter yang sesuai. Ketentuan-ketentuan yang digunakan dalam skenario ini yaitu: a. Data yang digunakan yaitu data semester genap tahun ajaran 2010/2011. 43
A8
Seminar Nasional Teknologi Informasi 2011
- Hard Constraint dan Total pelanggaran Hard (hard constraint Dosen, Mahasiswa (Kelas Kuliah) dan Ruang) Dari 10 kali percobaan pada tabel diatas, tidak ada satupun pelanggaran pada hard constraint dosen,mahasiswa (kelas kuliah) dan ruang semuanya bernilai 0. Nilai cost tergantung dari solusi awal yang dihasilkan yang dilakukan secara random dan metoda pencarian tetangga yaitu move dan swap. - Soft Constraint Dosen Dari 10 kali percobaan pada tabel diatas ,nilai rata-rata soft constraint dosen adalah 0,000556 nilai ini terendah jika dibandingkan dengan nilai rata-rata soft constraint mahasiswa. Hal ini disebabkan karena jadwal jam mengajar setiap dosen lebih sedikit dibandingkan jadwal kuliah mahasiswa dalam satu hari. Nilai terendah dari soft constraint dosen adalah 0. - Soft Constraint Mahasiswa (Kelas Kuliah Mahasiswa). Dari 10 kali percobaan pada tabel diatas,nilai rata-rata soft constraint Mahasiswa adalah 0,01891 nilai ini tinggi jika dibandingkan dengan nilai rata-rata soft constraint dosen. Hal ini disebabkan karena jumlah jam atau jadwal kuliah mahasiswa dalam sehari lebih banyak dibandingkan jumlah jam atau jadwal mengajar dosen.Nilai terendah dari soft constraint mahasiswa (kelas kuliah) adalah 0,01603. - Total pelanggaran Soft Constraint Rata-rata total pelanggaran soft constraint adalah 0,019466. Total pelanggaran soft constraint tertinggi pada percobaan ke 4 adalah 0,02065, sedangkan pelanggaran soft constraint terendah pada percobaan ke 5 adalah 0,01665.
Gambar 4 Cost Hard Constrain
Berdasarkan gambar 3 dan 4 bahwa parameter yang mempengaruhi Tabu Search adalah jumlah iterasi. Tetapi hal ini juga dipengaruhi oleh probabilitas nilai random yang dibangkitkan pada setiap yang diinputkan untuk mendapatkan hasil penjadwalan kuliah menuju arah yang optimal. Karena inisialisasi awal selalu diawali dengan jadwal yang di generate secara random.
8. Kesimpulan 1. Jadwal yang dihasilkan dalam setiap percobaan adalah berbeda, maka hasil yang didapatkan akan bervariasi setiap run time, karena inisialisasi awal selalu diawali dengan jadwal yang di generate secara random.Kualitas solusi yang didapatkan juga bervariasi, maka soft constraint pada kasus ini sulit mendapatkan jadwal yang valid dengan menghasilkan nilai pelanggaran 0. 2. Dalam pengujian yang dilakukan pada kasus Implementasi Penjadwalan Kegiatan Belajar Mengajar dengan Algoritma Tabu Search (TS) menggunakan Soft Constraint,menemukan parameter yang baik yaitu Random = 300 dan TSMaxiter = 10, dimana hasil ratarata hard constraint adalah 0 dan hasil rata-rata soft constraint adalah 0,019466, hasil soft constraint tersebut telah memenuhi penjadwalan ke arah yang optimal.
Analisis Parameter Berdasarkan hasil perbandingan 10 kali pengujian grafik terdapat rata-rata cost terendah yaitu kombinasi parameter yang menghasilkan pelanggaran paling sedikit ada pada pengujian nomor 10, dimana Random search = 300 dan TSMaxiter = 10 menghasilkan rata-rata cost = 0,019466. Berikut ini adalah grafik dari pengujian tersebut(diambil salah satu dari 10 kali ujicoba).
REFERENSI
[1] Glover,F, 1990, “Tabu Search, Part II”,ORSA Journal on Computing, Vol 2 No 1 pp 4 – 32 [2] Glover,F, 1989,” Candidate List strategies and Tabu search”, CAAI Research report, University Of Colorado, Boulder. [3] Glover,F, and greenberg HJ, 1989, “New Approaches for Heuristic Search. A bilateral link-age with Artificial Intelligence, European Journal Of Operational Research, Vol 39 No 2 p 119 – 130. [4] Hertz A and de Werra,D., 1987, “Using Tabu search Techniques for graph coloring”, Computing, Vol 29 p 345 – 351. [5] Hertz A and de Werra,D.D. Forthcoming, 1987,” The Tabu search Meta Heuristic : How We Use it”, Annals of Mathematics and Artificial Intelligence.
Gambar 3 Cost Soft Constrain
44
