rc'J:,
ISSN:2088-9658
KNTIA NASIONAL KONFERENSI
lnformasidan Aplikasinya Teknologi
Fakultas llmuKornputer UNSRI Palernba ng,2L-22Oktober2011 I
Diterbitkanoleh: llmuKomputer Informasi Fakultas Jurusan Sistern PALEM BANG2011 Universitas Sriwijaya,
KOMITE PROGRAM
hC
FimdD.Ir. Aniati Mumi (UniversitasIndonesia) FlmdT" Baseuddir,,ph.D (UniversitasIndonesia) eriEd -.l- Hasibuan,ph.D (UniversitasIndonesiaj ft" k Eko K. Budiardjo(UniversitasIndonesiaj M D- Srn'oto,M.Cs (UniversitasAtma JayaJogyakarta) lh. Ojuniadi"M!luniversitas Negeri Slmarilg) |ryCI ph.D (UnivJrsitasGajah-Mada) l'ardoyo, {.l., ph.D (Institut Teknologinandwrg) ' Survrdro, _fry ft- b- An-a-AkhnadArman (Institut feknol,ogi nandui'g) fridzil Nasm_di4ph.D (UniversitasKebangsaanMalaysia) Dr. yusuf Hartono(UniversitasSriwijaya) Dr. Darmawrjoyo(UniversitasSriwijayaj Dr.Ir. Siti Nurmaini M.T (UniversitasSriivi.;ay4 ' JaidanJauhari,M.T (UnivsersitasSriwijaya)
TIM EDITORIAL PENAIYGGUNGJAWAB Ali lbrahim,M.T.
KETUA PENYUNTING JaidanJauhari,M.T.
SEKRETARIS PEYUNTING KenDitha Tani4 M.Kom
PENYUNTING PELAKSANA Abdiansyah,M.Cs AhmadRifai, M.T Mgs.Afriyan Firdaus,M.IT Apriansyahputr4 M.Kom Ari WedhasmaraM.TI BayuAdhi Tama,M.TI EndangLestari,M.T Fathoni,MMSI JulianSupardi,M.T Mira Afrin4 M.Sc RifkiePrimartha,M.T Rizka Dhini Kumia, M.Sc Sutamo,M.T Yadi Utama"M.Kom YudhaPratomo,M.Sc
ALAMAT REDAKSI
Kampus -J--' L*g.g DiplomaKomputer(pDK) UniversitasSriwijaya Jl. SrijayaNggaraBukitBesarpalembang 30I3g
Fax(071r)37si4s .. T"tp(0ztl) 379249
E-mail : kntial l(dkntia
ors dnn lontio.tAr r.a**
PENERBIT JurusanSistemInformasi FakultasIImu Komputer UniversitasSriwijaya
DAFTAR ISI
",ffiffiffinffi:endek den ilffi
Melalui Pendekatan statisrik dansoftcomputi
Navigasi Flocking Mobire Robot denganIAprikasi rl,rrAsil SensorJarak uvrrDur J'lr'Llt
th
-,dlh
DJf-l
s 4Fr
cme Komputer untuk visuar Disability user (yudi prayudi)
Al4 Al8
Lrnek PenyusunanJadwalPerkuliahanMenggunakanAlgoritrna 4'Evrrsrrs Genetika vwrr!r^.
!qC-
1fu*ro"
t- lrF li.,!"!thr
A6
rchot PengamanRumahdenganKlasifikasi citra wajah @andapotansiagian)
*,ilHre"-*!
AI
Rido
Sapuha)
sisem Pend'kung KeputusanDalam Memilih program Studi Menggunakan "rvs66.*r44'
Fua.(Hetty
Rohayani. AII;
A23
A33
- Co4oareoce Matrix dan JaringanSyarafTiruan PropagasiBalik untuk Deteksi Manusia i5uffi -{,gustienSiradjuddin,Fitri Damayanti) A38 sMS GatewayGeneratorMenggunakanMetode Breadth-First -[ ==search v" (Ken \t\v' DfohaTania) A42 Problem-solvingEnvironmentMenggunakan gcase-BasedReasoning (Jaidan ry \roruqr Jnbfii-
AMiansah)
A46
!,S Felmkan JarakUntuk Navigasi GerakRobot (Ahyar Supani)
A50 Game Puzzle Hashiwokakero denganTeknik solving Hashi dan Depth First : ! Ii-:tTt* , *arch (Eriska Amrina pratiwi, Rusdi Efendi, RezaFirsandaya As4 Malik; Kata Makna GandapadaMesin TranslasiBerbasisstatistik o= (Ekawati mi*slasi A5g PerangkatLunak eBook ReaderBerbasisMobile Menggrrnakan i i :au,g:si Fitur Face I racking @ikza Azriyan, Saparudin,RezaFirsandaya A66 Malik)
t-
f,irerc
ffffi:%]|*Iffiintu
RelKereta ApiMenggunakan Sensor srrainGauge (suramo d*
A7l
Mobile computing dalamPengembangan Sistempakar unruk Mengukur tt P]::Ti*i rmgkat Kecemasan " Karyawan(AIi Ibrahim)
A77
PersonalBerdasarkanTulisan TanganMenggunakanpengenalanpola l6 :tt'i.ftttlsi utomimetik (Samsuryadi)
A83
Engingsring Kualitas website pemerintahDaerahdenganMenggunakan -l ll"l*:i webqual (studi KasusPadaKabupatenOganIlir) (Candrakawan)
BI
Kajian TentangRequirementsRecoverypadaArea Ri set ReverseEngineering -2 tl""h @lviawaty MttsaZamz.anri,Eko KuswardonoBudiardjo) PerancanganMobile Learning BerbasisJ2ME untuk PenyediaanBahanAjar perkuliahan ," ProgramStudi pendidikanEkonomi (yenni Anggrayni, B13 S.pd) E-PemiluBerintegrasiDenganE-KTP di Kota palembang(Heri 4' 5:.:t"p l:::*pT Wijaya, M Yusu{ yoga prima Hendar) Bt9
hkr
!!i laffiffi
Bdan
dengan
MenggunakanMedia pemberajaran $arxewarganegar:um rEBBLoc (Studi KasuJ:s"[orur,rr,r*engarr eJJarinJararcrnbang lsusi B.23 merepresentasikan Framework GSppada G'RE(Imam M.shofi, B.27
y:b:r: Construction asapublicrnformation 'n rvledra Medialor for ffi]rf1|o3^T rutuko, Siti Nururaini, Rossi "S*:*-T::"] 1i*'.'o"i*?e.Lu*e hrrhrspaKurnias*i,c*a*iiuiw**i l-.--_. -li*.
rivrrJ lrasa retlrcn selulat
m,T^Tf.::1Tir,:rar V si Amon Sujarwo,S.Kom) q--
I :--*
ruueruatc raoa Apllkasi
dengan Hybridcryprosysrem (Meea Mulia,M.r
I
*-n DeploymentlJasmanpardede) ffi,ff#;:"*-T"t-*::lpenentuan
-:
-r--EFruJsJarug
836
B.4r
Kualitas Jasa Dengan Metode euarity C 1
SosialDalamU"na,lt<.rrrg Jaringan Antarperguruan Tinggi(M. DOSI
lfb ffii:m:F rfrl, Dedi Rianto)
C7
-{pftasi Zerio soft 2padasistem KeamananSmart_Room 'n MenggunakanSmartRelay airyy t-aiftah Husni, na" S,n,o ioi6)ri, Rani (Jtami)
cl3
t]nrh PeningkatanKualitas Pada ProsesPelayananorder Taksi di pr. Blue Bird Group + Bmdung denganMenggrrnakan Metode six Sigma@udi Arr setianto, AmeriaKurniawati ST.,MT., Pratya poeri Suryadhini ST.,Mf)
c20
A'alisis 'en perancangansistem Informasi penjadwalan dan ManajemenTraining pada 5 SoftwareLaboratory center universitas nina Nusantara(Meiliana"Dwi Handri Kurniawan)
':ffi c33 ::::::::::i11o^"")rrur'*":i*,;kh*;dF,dj;';:;;o'; erservice pada;;;;;;;;;;Y, uu*^o (suryasari Ashid H;"*frf]*;lg:l Callista, , c39 Juwita Sari) "#;H?rTilliirX::::tTY:':i'lcllilyerororderbvsimiraritv ,
Pengembangan Murtimedia pembelajaranInterakti padaMataKuriah f Komputer Akuntansi Menggunakanprogram nivog (Dra. siti Fatimah,M.Si)
trrrT:ffi:#::f:K
c43
datam Komunikasi sosialdi Kalangan Mahasiswa (raminsoim[l],
c49 - Mengajar Berajar Antara Metode FacetoFacedanvideo uonrerence(yoice Silitongq EminencyD V) c57
to *l::::39*g"ualitas
Analisis Keputusan?elangganpada SistemE-Ticket Ndaskapai -t tpenerbanganGaruda Indonesia(VeneraGeniq Alvin p*""*i
c62
Pengembangan Media PembelajaranBerbasisKomputer '-' Untuk MeningkatkanKualitas " Pembelajarandi sMA paoa Mandiri r pr"i, (Sri Anggraini o"J, wioa, Liyana)
c69
PenganrhPenggunaanMultimedia Berbasis Komputer terhadapMinat BelajarMahasiswa 13 darampemberajaranstatistika Dar* r** sistem Informasi FeJrrKoM LTNSRI (Oktober20l l) @wi Citra Hartini Sela Taramita) ,
c16
t llrdr Aplikasi Berbasisweb DenganMenggunakanModel Kepuasan &G FskultasIhnu Komputer Unsri) (Fenty Tri Hidayati , Mamik
c80
rffi rerpustaraanBerbasisTeknologi Informasi untuk Meningkatkan r lkpsakaan dan mewujudkanperpustakaanideal berbasisoigitar ai lf.flhahin, MiraA&ina)
c87
lodd SisftemInformasi Inte grated Laboratory padaPerguruan Tinggi Frrrrg l€stari)
l&d h
rrosaksi cunsomer to cunsomer dalammembangunE-Marketing ros perluasansegmenpasm(Apriyansyahputr4 Alvibianto sidik)
rufU!*ngm SistemMonitoring PerkuliahanBerbasisWeb untuk Optimalisasi bnf*'r;O Ferkuliahandi FakultasIlmu Komputer UniversitasSriwijaya (Mgs. ,fi:rmrc, Firdaus,Ali Bardadi) ilh ftagtrgan SistemInformasi Klinis padaPelayananPasienRawat Jalan DH !*i BhEiangkaraPalembang@esi Pibriana,Mgs. Afiiyan Firdaus,Rizka Dhini h,r Informasi Akademik pada SMA Negeri I palembang @ka puspita sari, D - !:{-_l*pratomo, .lftn Firdaus, M.IT, Yudha fr S.T.,M.Sc) Wh hgcmbaDgan SistemInformasi pemetaanBlok pemakamanpadaTempat @ bm Umum Kota PalembangBerbasisWeb (SiskaIrawan, Mgs. Afriyan Firdaus, hinm Indah) linpbmean Aplikasi Multimedia SebagaiMedia Altematif PenyampaianInformasi !',p A&ft (AhmadRifai) lG-g BangunDatawarehouseuntuk MenunjangEvaluasiAkademik Fakultas 813 rlffilis Febriady,Bayu Adhi Tama) suategy Plaruring: A case study ofA Faculty of state university (Ari -1* Frr r'-ceasmara Bayu Adhi Tam4 Apriansyahputra) Efr..i*-ness of E-Leaming ImplementationAt UTM (Rizka Dhini Kurnia Azizah Abdul -r,r nrman) kp.o Metode Weightedproduct Model -.-. rrnrk SeleksiCalonKaryawan(Sri Lestari) Aralisis Dan PerancanganAplikasi CustomerRelationshipManagementUntuk Modul 5 PenangananJaminanPumaJual Terminal SmartphonePadapT. X (Aldhi Jaya dkk) Aplikasi Metode Tabu Searchpada -',, PeuyelesaianAssignmentProblem(Rusdi Efendi, Ernawati) PerancanganAplikasi Material Requirementplanning (I\dRp) 2t Untuk Produk MakananDenganBatasKadaluarsa( Studi Kasusdi pT. H )@utri W, dkk) CqrtcrBesed
C95
cl0r Cl l0
Cl15 Cl22 Cl30 C136
ct40 ct44 Cl49
ct52 Cl56
ct60 Cl66
Learning
,t ImplementasiAlgoritna Dijkstra Dalam Aplikasi untuk menentukanLintasan Temendek ' Dl JalanDaratAntar Kota di SumateraBagian Selatan(1 Fitria, 2 Apri Triansyah) Optimasi Tata Letak FasilitasDepartemenSpinning3 ft. GrandtexDan perancangan 2 Aplikasi Untuk Modifikasi Algorifina Craft Dan Planet(1 Kriswardani Saptaningtlas,2 Dr Luciana Andrawina) PembelajaranBahasaInggris unhrk Anak-anak ur^-qr^usru'aDtDr'ru*tl,'surat^srl,J'.na BerbasisMultimedia (Ken Ditha Te rarua' ,Alilbrahim)
Dg
Dl3
cl60
Aplikasi MetodeTabuSearchPada Penyelesaian problem Assignment Rusdi Efendi, Ernawati, Safta Hastini Program Studi Teknik Informatika, f"Uil, i"t"rit , (JniversirasBengkulu Jl. W.RSupratman Kandang Limun Bengkulu Bengkulu 38371A Telp. (0736) 344087,2t t70 _ 222 muncul dalam pengarahandan pengelolaandari suatu sistem yang terdiri dari manusia, mesin, bahan dan uang dalam industri, bisnis, pemerintahan dan pertahanan .....[6]. pada Riset Operasi terdapat permasalahan dalam pernilihan personal yang tepat dalam mengerjakan suaru tugas fentu yang berpengaruhuntuk suksesnyaiuatu usaha.Masalah ini disebut.assrgnmentproblem atau masalah penugasan yang merupakan suatu kasus khusus dari masalah linear programming tentang pembagian sumber Ok! daya dan tugas, larena itu, aplikasi ini diharapkan dapat diSana sejumlah n r plaku industri untuk mengamtit t"tiiofon daya dirugaskan kepiAa in lumber ,? rugas. Sumber diya ada-lah p"t"i* sumber dayo yang terbotas untuk ;ejyiah . (pekerja/agen) sedangkan yang dimaksud tugas aaaan mesin-mesin. Jadi, assignmenl problem akan mencakup sejumlah rn sumber daya yang mempunyai n tugas dengan penugasan yang Uertu;uan menghemat 9! ,biaya biaya/waktu pada kasus miiimasi ;; mendapatkan keuntungan maksimum pada kasus maksimasi. Daram hal ini, jumlah m sumber daya sama denganjumian n tugas. Dari sudut pandang masalah optimasi, penyelesaian assignment problem bertujuan untuk memetakan m sumber daya terhadap r fugas UeiOasartan p"nug* satu-ke_satu, Assigrunenl Problem, Metode Tabu Search, karena secara umun satu orang hanyaiisa mengerjakan U,DFD satu tugas dalam waktu bersamaan. Walaupun- turtuk menyelesaikan masalah ini bisa menggunakan metode I. PElroerruLueN t]mum yaitu dengan cara permutasi dari Je]umlah n sumber n ilmu pengetahuan saat ini, menuntut para day-a-dengansejumlah_n tug*, sehingga alan Operoteh nl (nfahorial) alternatif. Metode ini muiih dilakukan kalau n l. -untuk dapat mengambil keputusan ijaksanaandan tindakan secara ilmiah atau kecil, tetapi kalau sudah menyangkut untuk z yang besar IEK bagaimanamerancangdan menjatankan cara ini kurang efisien, karena harirs mencari altematif dari -mesin secaraterbaik walaupun menghadapi n/.buah kemungkinan yarg harus dipilih. Sehinggabesarnya sejumlah n yang harus dipetakan akan sumber daya yang terbatas.Masalah berdamput t".f,uaup ncul bilamana harus dipilih tingkat pekerjaan wak-ru yang digunakan untuk proses pengdolasian tugai Dersalngdengan sumber daya manusia yang tersebut. : melaksanakanpekeqiaanpekerjaan Untuk melakukan suatu tugas, sumber daya tersebui harus dipilih yangdidapatakanoptimal. b".$TTI* skiil yang.dimiliki,.yuitu Oipititi sesuai dengan a tingkat keterampilan, pengalaman keqia, probabilitas sumber daya yang tinggi ii-*u banyakiya pendidikan, dan latihan setiap pekeia sumber daya yang harus dipilih uni.ik -"ng"rjakan tugas Sehingga dalam waktu p"ny"i"rui* tertentu berpengaruh terhadap waktu pengaLkasian tulas samaitu berbedajuga. Masalahmanaiemen tersebut. Karena itu, permasalahan lni merupakan a menetapkan pemberian sejumlah tugas permasalahan optimasi kombinatorial (combinatorial optimamizat ion) y ang kompleks atau permasaiahan atas dasar satu-satu dengan yJng np-hard, "u* yaitu tugasdikerjal{anoleh satu pekerja), suatu permasalahanyang pencarian solusinya-(waktu dimani mempunyai tingkat efisiensi yang berbeda_ komputasinya) akan naik seiring dengan naiknya skala parameter n secara linear. Oleh karena yang berbeda-beda pula dan pekerja itu, pada penelitian lugas ingkat efisiensi yang sama dalam satu tusl ini digunakan metode heuristik *trl pemeeahan untuktugasyang lain. assignment problem- Metode heuristik adalah rnetode pencarian solusi permasalahanoptimasi kombinatorial i (Operations Research) merupakan suatu yang cukup sulit dan berskala besar dengan cara an masalah yang menerapkan *",;;: mencad good terhadap masalah-masalah rumit yang solution yang dapat mencapai ,.*ui kriteria dengan waktu yang relatifkecit[2].
Salah satu metode heuristik yang dapat digunalianadalah Tabel l. GambaranL:nuun penl.elesaral metode Tabu Search. "Metode Tabu Search merupakan h'oblent suatu metode optimasi yang menggunakan shrtrt_lerm memory untuk menjaga agar proses pencarian tidak teriebak pada nilai optimum local"[S]. Metode ini benujuan unruk mengefektifkan proses pencarian solusi terbaik dari suatu permasalahanoptimasi kombinatorial yang berskala besar. Untuk menj aga agar solusi terbaik tidak hilang, maka metode Tabu Search menyimpan solusi terbaif te aaam memory yang disebut tabu list, serta terus mencari solusi terbaik dari setiap iterasi, kemudian dilakukan perbandingan antara solusi terbaik yang baru dievaluasi dengan solusi terbaik sebelumnya. Selain itu, metode ini mengingat atau melakukan Denganmodelassrgnment pengecekansolusi yang pernah ditemui pada memory problemsebagai Qabu Funti tujgan(maksimum/minimum) li,st) dan melarang untuk menggunakan solusi yang ielah tnn dievaluasi untuk menghindari pengulanganyang iia-sia. Uat \a \"r ini yang membuat metode Tabu Search menjadi lebih Z = ) ) C't, . .'i\ ' , . LLefisien dalam hal waktu[8]. I I i.l Penelitian ini bertujuan untuk menerapkan metode Tqbu Batasan-batasan Seqrch dalam menyelesaikanassignmentproblem yang bisa menangani sejumlah n dengan waktu yang relatif singkat. Oleh karena itq untuk mencapai tujuan tersebut, riaka dibangun aplikasi metode Tabu Search pada penyelesaian assignmentproblem. II.
satu tugas dan : ;"a.Demikianjug ya. Sehinggani
, , - i \ ' r r )i ( 0 i -
penjelasan ignment problem inimum) dari p lll sumber da1ai kapasitas 1l kapasitas permi variabel keputus Cy yang terp -rnilai I yaitu s karena itu, ai k -ra dan b7 kapasiu nel keputusan -l :rbel gambaran u disederhan"k
" TabelOnekos
LANDASANTEoRI
danx';: 0 atauluntuki :t, 2, ...,m dany:1' 2.1. AssigmentProblem Assignment problem atau masalah penugasan pertama kali dikenalkan oleh seorang ahli matematika dari Hiongaria yang bernama D Konig pada tahun 1916. ..Assignment problem adalah jenis khusus linear programming dimana sumber-sumber dialokasilan kepada kegiatan-kegLtun utu, dasarsatu-satu(one-toone-basis)...',[3]. Assignment problem merupakan masalah pengalokasian . sejumlah m sumber daya yang ditugaskan kepada sejumlah ,? tugas (satu sumber daya untuk satu tugas) sehingga diperoleh biaya/waktu total yang minimum atau keuntunsan total yang maksimum. Dalam hal ini, sumber daya ada'iah pekerjaan (pekerja/agen),sedangkanyang dimaksud d"ng* tugas adalah mesin-mesin. Jadi, ada rz sumber daya ying ditugaskan kepada n tugas, dimana sumber daya i (i : I, 2, .....,m) ditugaskan kepada tugasjr (j : I, 2, ... , n) denganCij biaya penugasan. Pada assignment problem satu sumber daya hanya _ ditugaskan kepada satu tugas, maka ai kapasitaspenawarrul pada setiap sumber daya yang tersedia hanya I. Demikian pula halnya dengan tugas, karena satu tugas hanya dikerjakan oleh satu sumber daya, maka 67i kapasitas permintaan pada setiap tugas yang tersedia hanya l. Dengan biaya pengalokasian rn sumber daya ke n tugas sebesar-y. sehingga variabel keputusan Xy bemilai 0 atau I untuk sumber dayai: l, 2, ..., myangakan ditugaskankej : I, 2, n [3]. Secara matematis dapat dinyatakan sebagai berikut: ir:{.rskr, ; ,.' ' - itl.;ii<.rsrt:riitt'iri.ri..rt.-' r :r
Keterangandari model assignmentproblem &
I.
2.
Fungsi tujuan adalah Z sebagai rcrld penugasan yang menyatakan apalwfr. problem ini mencari nilai minimum arai; Variabelkeputusan adalahXii. Nilai dqi untuk i : I, 2, ..., m danj : l, 2. .. a. apabila I sumber daya ditugaskan una* bernilai 0, apabila i sumber daya riii*,
untuk/ tugas. Tetapan biaya yang telah ditentukan sumber daya yang ditugaskankepadaz 4. Jumlah sumber daya adalah m. J. Jumlah tugas yang akan diselesaikan J.
Variabel keputusan Xij bemilai 0 atau I untuk menyelesaikan assignment problem yang bernilai I dimana variabel Xti b€rni}n sumber daya ditugaskan ke n fugas l berdasarkan keputusan saat Xtj terpilih penugasan pada setiap peircarian solusi penugasan,sehingga angka tersebut dikalitm
terpilih dari sel tersebut(Xi* Ci) yang tidak terpilih maka nilai Xij bemllai A daya tidak terpilih untuk melakukan n fungsi tujuan Z dapat digambaran sebagai h
Z = ltCt,.f,,,i + {Crr..f!ri.i t ir.. .\rji.f ...i i,,-r lil-,.x.i
t{ ,,,..,\",, i{ r .- ,",..tri 4' ,,,, )r i {-r,'11. ,{,,,,1 i I
Berdasarkan Persamaan (4), misalnlr kolom pertama terpilih dengan C I t biay 1 variabel keputusanXI l bemilai I sedarqknrl pertama atau kolom p€rtama lainnya kapasitas penawaran setiap sumber da1,a permintaan setiap tugas hanya bemilai t
Tabu Search Tabu Search r r 3.'lg termasul( k Search memFer strulrtu bahwa metode
mengguneks proses pencari 't41 t'l'
"msarpenyelesaia proses pencaria Pada setiap rnh dapat dikarel akan meneh rengakibatkan i; solusi yang pc Iangkah-langta --aryang disehl --Ipat
unhrli
m
le dievaluasi- Pn alenentukan s (movei ke
sampai kric c:;apai. Kriteria ;r sejumlahien :-l CPU rener t p'eningkatan I :.--1. lvletode / -::akan algoritr:r "ns::carisolusi di.
cl6l satu tugalsdan sebaliknya safu tugas untuk satu Demikian juga untuk baris kedua kolom kedua ,a. Sehingga ntlai Z menjadi:
, . X r r) + { o i + " ' + { o } l + l ( o ) * - I r r ) + - . - + ( 0 ) l+ l { 0 }+ { 0 }+ . - - * ' X,on t5i )l penjelasan di atas, dapat disimpulkan problem adalah mencari Z total biaya 'minimum) dar' CU biaya yang telah ditentukan m sumber daya yang akan ditugaskan kepada n af kapasitas penawaran pada setiap sumber kapasitaspermintaan pada setiap tugas bernilar variabel keputusan Xy bernilai 0 atau l. Dalam i Cij yang terpilih dengan variabel keputusan ilai I yaitu sumber daya yang mengerjakan karena itu, al kapasitas penawaran pada setiap dan b7 kapasitas permintaan pada setiap tugas bel keputusan Xy tidak perlu dicantumkan. tabel gambaran umum penyelesaian assignmenl disederhanakanmenjadi tabel ongkos berikut
Tabel
As
hoblem
sotusi terbaik saat ini Pada setiap iterasi, atpritma ,ocal search memilih solusi tetangga dengan total tiaya/ua.ktu yang minimal pada kasus minimasi atau total keuntungan maksimum pada kasus maksimasi tergantung dari kasus yang dihadapi. Untuk efesiensi memory dan waktu proses, tabu list hanya menyimpwr move yang merupakan kebalikan dari langkah yang telah digunakan pada iterasi-iterasi sebelumnya dengan panjang iist yang dibatasi oleh user. Metode Tabu Search mempunyai stmktur memory yang menyimpan solusi terbaik ke dalam tabu list. Selain itu, metode ini mengingat solusi yang ada dengan cara melakukan pengecekan pada tabu list dan melarang menggunakan solusi yang pemah ditemui untuk menghindari pengulangan solusi yang sudah ada. Oleh karena itu, dengan menggunakan tabu list, metode Tabu Search dapat menerima solusi yang tidak memberikan peningkatankualitas,sehinggametodeTabu Searchbisa keluar dari optimum local. Akan tetapi, terdapatpengecualiandalam metode Tabu Search. Jika terdapatmove yang sudah berada dalam tabu /rst (terlarang untuk dipilih) tetapi memberikan solusiyang lebih baik dibandingkansemuasolusiterbaikyang pernahdievaluasi,maka rnovetersebutbisa diterima dan move tersebut harus dikeluarkan dari tabu list (dibebaskan dari larangan).Hal ini merupakanprioritas khusus pada tabu list yang disebut kriteria aspirasiatau kondisi aspirasi (aspiration conditions). Algoritma Tabu Search secaragaris besar dapat berikut[5]: ditulissebagai
iangkah Lingkah
T€LapF-aI:: EL{.:':1:rput b€luhuran :{-ltat rlks 1: e:--4.5 1 . x;:.lt €r:=':::k!,i.I:ru;e rando$ so1:"!5: secara i. 5-bangkltkan 2. ciaball4l-n=Fcosi {5} f. Sest =S 4. ? e , b u : - 1 s i = : l sarrpal dar! h=i 5. Eerlakan $axli€:: €SesESeF;r=!'Cosi i5: ?. 3est!{cv€=S dari i=i sarsl}ai {n-l } : *. f.€::jaka!: qj=:n: sa;r.Fai l:a:-.-akan darl :.., i=,?ukar{S!1l.stjl ). 11 a{}s.=iTost {LJ alau i: Jlka {L€T.abuLlsti icest
solusi lebesar
akhlr adalah clo:]aiHin.
::ng:(ah
:-:ngikah :.angkah Langkah :-engkah leng:cah
Tabu Search Tabu Search adalah suatu metode optimasi !'ang termasuk ke dalam kelas local search. Search memperbaiki performansi local search
strukturmemoryf\f. Definisi lainnya bahwa metode Tabu Search adalah suatu yang menggunakan short-term memory untuk proses pencarian tidak terjebak pada nilai
"t4).
dasar penyelesaianmetode Tabu Search adalah proses pencarian solusi dengan cara mencari pada setiap tahap pelacakan. Pada beberapa rakan dapat dikategorikan sebagai langkah tabu karena akan menghasilkan local optimal dan juga mengakibatkan langkah pengulangan kembali
;.anglreh iangk3h :"acgkah -ng(ah -ngkah L::rgkal :ar:gkai
-l]g?,a]r :ang:",ah l;I]gkah :-3::g!-ah :angkah Lat:gkal
o,
Esst.
d€ngan
qc'se
ke solusi yang pemah ditemukan sebelumnya 2.3. PengukuranWalidu Kerja Sistem l. Iangkah-langkah ini kemudian dimasukkan daftar yang disebut dengan tabu list. Tabu list
tempat untuk menyimpansekumpulansolusi sajadievaluasi.Prosespencariannyadilakukan menentukan solusi awal dan kemudian gerakan (move) ke solusi-solusi berikutnya dan i sampai kriteria penghentian (stopping tercapai. Kriteria penghentian metode Tabu nya sejumlah iterasi yang ditentukan oleh user. n'aktu CPU tertentu, atau sejumlah iterast nanpapeningkatan nilai fungsi objektif terbaik, nya[7]. Metode Tabu Search bekerja secara algoritma local search pada setiap mencari solusi diantara sebagian tetangga dari
Pengukuran kerja sistem dilakukan untuk mendapatkan ukuran-ukuran tentang kinerja dan beban yang berlaku pada suatu sistem kerja. Kinerja adalah kecepatan atau pengukuran waktu kerja sistem yang akan dibuat (ukuran kuantitas untuk kualitas tertentu), sedangkan beban adalah yang dialami sumber daya (beban frsik dan beban psikososiologik)[7]. Pada penelitian ini, pengukuran waktu keda sistem merupakan pengukuran waktu sejauh mana terdapat pengaruh parameter n, yaitu banyaknya sumber daya dan tugas, terhadap waktu pencarian yang digunakan untuk proses pengalokasian tugas kepada sumber daya dengan tujuan untuk mengetahui kinerja dari sistem yang telah dibangun. Selain itu, akan dilakukan analisis beban kerja.
Dalam penelitian ini, beban kerja adalah banyaknya sumber daya yang akan dialokasikan kepada tugas untuk mendapatkan solusi optimal. Waktu akan dicatat dengan menggunakan clock fisik yang terdapat pada komputer sebagai alat pengukur waktu dalam penyelesaian suatu aktivitas yang diamati. Clock adalah alat elektronik yang menghihrng osilasi yang terjadi pada frekuensi tertentq dan menyimpannya dalam counter register. Sistem operasi membaca clock frsik tersebut dan menerjemahkannya ke software clack. Software clock tidak selalu akurat sehingga perhitungan waktu hardware dan software memiliki perbedaan walaupun sangat kecil. Namun, software clock tetap menjadi acuan pencatatan waktu setiap kejadian proses[].
IIL PERANCANGITT FIowCHART SYSTEM Diagram alir (Iowchart) adalah suatu bagan (charr) yang menunjukkan aliran (flow) dalam program atau prosedur sistem secara logika[4]. Flowcharl sistem aplikasi secara umum dapat dilihat pada Gambar I di bawah ini:
IV. Aplikasi ini dapat seperti penugasanpekerja dengan pekerjaan dan kasrrs Dengan hasil dari pengujia pada penyelesaian assiga
pengujian jumlah sumberdryr bertambah untuk mengetahi pengujian jumlah ordo marrils"j
jumlah tugas untuk mengerfi dibutuhkan sampai proses dilakukan sebanyak5 kali. :6:t
4.1. Analisis Pengaruh Jurlyang Dihasilkan Analisis ini dilakukan unhrk iterasi terhadap solusi yang
Ji-lA(
Petg!ryr R'elilrP
5 pada kasus minimasi pengujir denganjumlah iterasil, solusi1q
ke 266. Padajumlah iterasi 3 rlen yang dihasilkan semakin baik, Fdisimpulkan bahwa jurnlah iterai kualitas solusi yang dihasilkan. Hal ii kesempatan yang lebih bany*
irl elahilan da ralru pui
pembangkitansolusi. Hasil pengujb Grafik 1.
btaya
r
Ddr
ordo matrfu Grafik i dF uhadap *alo
solusi-Fr
t+0 {00 :.rs:i
$lusi.
r,laftu pct I rata Pe|ri i jumlah iul 30.7601 ! disimPrrlkan I
ke:
=! t w ,i rsl
n*
:::-
sohni- I 56?9
JruJaI lterasi
9 P
sem*i
Crafik f . Hasil Pengr.yian Pea-qenft tedudap Solusi !"og Di
Gambar l. Flowchart sistem secaraumum Pada gambar di atas penyelesaian assignment problem dimulai dari proses input yxriah ln sumber daya dan jumlah rl tugas. Setelah itu dilakukan pengecekanjumlah sumber daya m dan tugas n. Itka m:n, maka lakukan langkah selanjutnya, yaitu penyusunantabel biaya dan peng-input-an biaya penugasanm ke n. Jika tidak (m
n), maka lakukan proses dummy (proses penambahan m atau n sehingga menjadi sama dengan biaya penugasan dummy sama dengan nol (Cij:O). Kemudian, lakukan langkah seperti pada kasus m:n (ytenyusunantabel biaya dan penginput-an biaya penugasan Pilih kasus yang diselesaikan. kasus minimasi untuk meminimumkan biaya/waktu atau kasus maksimasi untuk memaksimumkan keuntungan. Dari data yang di-inpul, dilakukan pemrosesandengan algoritma Tabu Search sampai mendapatkan output. output berupa penugasan kerja, total biaya penugasan (Cy) dan waktu pencarian dalam sekon tahap pemrosesanselesaidilakukan.
4.2. Analisis Pengaruh Jumlah Ordo Waktu Pencarian Analisis ini dilakukan turtuk melihat ordo matriks dari I sampai 100 terhadap yang dibutuhkan untuk mendapatkan solusidilakukan dengan I iterasi. Berdasarkan Grafik 2 dapat dilihat bah*z matriks berpengaruh terhadap waktu dibutuhkan untuk mendapatkan solusi. gsrnakL jumlah ordo matriks, maka semakin pencarian yang dibutuhkan. Peningkatan pada ordo matriks l, rata-rata waktu dibutuhkan adalah 0,038 sekon. Ordo matriL pencarian yang dibutuhkan ada.lah0,0468 sekoru jumlah ordo matriks ditambah secara linear dengan waktu pencarian yang dibutuhkan
12,5054sekon.Waktu pencarianterus meningkatsecaralinear yang untuk melakukan pembangkitan solusi dalam sar menjadi bertambah.
-i6
,r Penglr4re 3. Hasrl Waltu Pencan:
pengaruhir rdap waktu Pencr is ini dilakukan
daya dan tugas terl
n solusi. Unnl ihat pada Grafik 4-'
cl64 pada sumber daya terhadap waktu pencarian. Dengan jumlah sumber daya bertambahdari I sampai l0 dan jumlah tugas tetap, yakni l0 tugas. Dari Grafik tersebut dapar dilihat bahwa jika jurnlah sumber daya bertambah dan tugas tetap, maka akan mempengiuuhi waktu pencarian yang dibutuhkan untuk mendapatkan solusi optimal. Semakin bertambah .iumtah sumber daya, maka waktu pencarian yang dibutuhkan hampir sama dan ridak stabil. Hal ini terlihai pada jumtah sumber daya I sampai jumlah sumber daya 3, jurnlah sumber daya 4 sampai 5, jumlah sumber daya 6 sarnpai 7, dan jumlah sumber daya 7 sampai l0 terjadi peningkatan dan penurunanwaktu pencarian solusi (tidak stabil). . J 5 ; I 9 10t5:01530.10t0t00 Junlebfro \ha-rlis :i
d Pcagu.yian Peaganrh Junrlab Ordo
bp R"trt Pencari.rntmruk 1 Iterasi prrrh jumlah iterasi terhadap waktu
t u:) : o, -* t UU] 0
JqIkan dengan melihat pengaruh jumlah : I t'i*otLJ.r"t s 10 *ru prencarianyang dibutuhkan sampai Ei- Ddam pengujian ini data yang Grafili d. Hasrl Pengujian Jika Jurula; Stuuber Daya rdo marriks 10. Bertanrbah dan Junrlah Tugas Tetap efili 3 dapat dilihat bahwa jumlah iterasi hp saltu pencarian yang dibutuhkan t solu-si. Pada pengujian dengan jumlah .Dari seluruh pengujian di atas ditarik kesimpulan bahwa naktu prencarianadalah 0,1774 sekon, pada analisis solusi diketahui jumlah iterasi mempengamhi solusi yang dihasilkan. Dengan b€rtambahnyajumiah iterasl ra prncarian adalah 0,359 sekon, dan akan memperbaiki kualitas solusi dari algoitma Tabu rryilah iterasi ditambah menjadi 100, rata S-r6fll sekon. Sehingga dari dara feych. Sedangkan pada analisis kerja sistem disimpulkan bahwa jumlah ordo matriks, jumlah iterasi, jumlah surnber impulkan bahn'a bertambahnya jumlah daya" dan jumlah tugas mempengaruhi waktu pencarian kd':4 *'aktu pencarianyang dibutuhkan untuk mendapatkan solusi optimal. Semakin bertambah t solusi. Hal ini dikarenakan, jumlah jumlah ordo matriks dan jumlah iterasi, maka waktu an semakin banyak. pencarian yang dibutuhkan akan meningkat. Begitu juga dengan jumlah sumber daya dan jumlah tugas, semakin bertambah jumlah sumber daya atau jumlah tugas, rnaka waktu pencarian yang dibutuhkan untuk mendapatkansolusi optimal hampir samaatau tidak stabil.
V. KESIMPULAN
:
J - s 9 t0li:0:5io{,ci0100 JumlrhIrerasi
hngrl
t:n Peo-earuh Jturrlah lterasi
FencananturnrkOrdo tr'f:trrls l0 u'uh jumlah sumber daya dan tugas r pencarian ekulian untuk mengetahui pengaruh rgas terhadap waktu pencarian untuk L-ntuk mewakili analisis ini, maka rafik -1.laitu analisispengaruhdummy
Berdasarkan analisis dari aplikasi metode Tabu Search pada penyelesaianassignmentproblem yang telah dibangun, maka terdapatbeberapahal yang dapat disimpulkan, yaitl: l. Penelitian ini menghasilkan aplikasi metode Tabu Search oada penyelesaian assl'gnmentproblem yang cukup fisien dalam menyelesaikan kasus penugasan kerja. 2. Waktu pencarian naik seiring dengan bertambahnya jumlah ordo matriks secaralinear. 3. Penyelesaian ordo matriks 1000 atau lebih dengan perangkat uji (komputer) yang digunakan pacla penelitian ini belum bisa menyelesaikan assignment problem. 4. Kuafitas solusi algoritma Tahu Search dipengaruhi jumlah iterasi. DAFTAR PUSTAKA
J
i
-
Ardani,I, Hamdani,T" dan W Herusetyo,A. (2011). and Global Time State. http ://te.uem.ac.id/-risanuri/distributed /ringk/Bab I O.pdf. Terakhir diakses:6 Maret 20 I I I2l Betrianis dan Aryawan, P. T. (2003). Penerapan Algoritma Tabu Search dalam Penjadwalan Job Shop. Jurnal Teknologi Departemen Telmik Industri, Fakultas Tekni h Universi tas Indonesia. 7( 3), 107-l 12 13l Hillier, F., Lieberman, G.J. (1990). Introductionto Operations Research,fifth edition. (alih bahasa Ellen Gunawan) Jakarta: Erlangga [4] Jogiyanto. (2005). Anolisis dan Desain Sistem Informasi: Pendekotan Terstruhur Teori dan Pralaik Aplikasi Bisnis. Yogyakarta: ANDI f5/ Kusumadewi, Sri dan Pumomo, Hari. (2005). PenyeIesa i a n Mas aIah Opt i masi dengan Tekn i k-Tekni k Heuristik Yogyakarta: Graha Ilmu 16/ Mulyono, Sri. (2004). Rrsel Operasi. Edisi Revisi. Jakarta: FEUI [/ Sutalaksana,I.Z. (2010). Pengukuran Sistem Kerja l. Lab Perancangan Sistem Kerja &. Ergonomi. DepartemenTeknik Industri ITB: Tidak Diterbitkan 18/ Suyanto. (2010). Algoritma Optimasi Deterministik atau Probabililik. Yogyakarta: Graha llmu
tll
Mstcr Untuk Kad: Ernril Progra
N a a comP-q
inard Tle corrytaY t inM rut+'mdadl g.ess ra*'fli wt{ittwrtu;_ tlewt ldingat tha qeb
by tle ry
@uiranent Plani4l &ing. In calculafr ning the methd I' (FOQI d Wltiry &tedrccor&tgol ,nlgoduceamfuiinthb ds "i&ilstages fu fuendesigrcdut yovide ir{ormafun t ryith the rav'malail derfintctions- Fu' ,wtminimize tle rdi Yofrom the calctfr Floning existerca@ Kelrvords: Materid I Dtnamic Lot Siitr8'.' Suantity(FOQ),tr4
'fl ${:! *fili sli* #is ' {.ff! +.f.,i tF+; Yi..:
!el
