8
BAB 2 LANDASAN TEORI
2.1 Penjadwalan Masalah
penjadwalan
secara
umum
adalah
aktifitas
penugasan
yang
berhubungan dengan sejumlah kendala, sejumlah kejadian yang dapat terjadi pada suatu periode waktu dan tempat / lokasi sehingga fungsi objektif sedekat mungkin dapat terpenuhi.Masalah ini muncul di berbagai bidang kegiatan maupun instansi seperti rumah sakit, universitas, penerbangan, pabrik dan lain-lain.Desain model masalah itu bervariasi sesuai dengan kebutuhan serta kendala di lapangan.
Optimalisasi penjadwalan merupakan suatu persoalan yang telah diteliti sejak lama dalam ilmu komputer. Suatu permasalahan penjadwalan akan muncul dalam situasi dimana satu kumpulan aktivitas harus diproses pada jumlah sumber daya (resources) yang terbatas dalam waktu yang terbatas[Bartak,2003].
2.2 Sistem Sistem adalah sekumpulan obyek yang tergabung dalam suatu interaksi dan interdependensi yang teratur.Sistem dibedakan menjadi dua tipe yaitu sistem diskrit dan sistem kontinu. Komponen sistem: • Entitas – objek yang sedang diamati dari sistem.
9
• Atribut – identitas dari entitas. • Aktivitas – suatu masa yang mewakili proses suatu entitas. • Status – kumpulan variabel yg dibutuhkan untuk menggambarkan sistem. • Kejadian – Kejadian yg mengubah status sistem.
2.3 Teori Harmony Search Dari gagasan bahwa ada algoritma meta-heuristic atau evolusi algoritma yang meniru alam, ilmiah atau fenomena perilaku di sekitar kita, maka suatu algoritma baru dapat dikonseptualisasikan dari proses pertunjukan musik (improvisasi jazz) melibatkan pencarian harmoni yang lebih baik. Sama seperti improvisasi musik untuk mencari keadaan terbaik (harmoni terbaik) yang ditentukan berdasarkan estimasi estetika, proses optimalisasi juga mencari keadaan terbaik (global optimum) yang ditentukan berdasarkan fungsi evaluasi obyektif; Sama seperti estimasi estetika yang ditentukan oleh beberapa tangga nada yang dimainkan oleh instrument-instumen, fungsi evaluasi obyektif ditentukan oleh set nilai yang sudah ditetapkan untuk variabel-variabel keputusan; Sama seperti kualitas suara estetika yang dapat ditingkatkan melalui latihan dan latihan, fungsi evaluasi obyektif dapat ditingkatkan melalui iterasi-iterasi bertingkat.
Menurut Zong Woo Geem, Harmony Search adalah algoritma fenomenapeniruan (dikenal juga sebagai algoritma meta-heuristik, algoritma komputasi lunak atau algoritma evolusioner) yang terinspirasi oleh proses improvisasi para musisi. Dalam algoritma Harmony Search, masing-masing musisi (=variabel keputusan) memainkan (=menghasilkan) catatan (=nilai) untuk menemukan harmoni terbaik (=global optimum)
10
semua bersama-sama. Algoritma Harmony Search memiliki manfaat sebagai berikut(Geem, HS Intro, 2006): 1) Harmony Search tidak memerlukan gradient yang berbeda, sehingga dapat memperhitungkan fungsi kontinu dan fungsi diskontinu. 2) Harmony Search dapat menangani variabel diskrit serta variabel kontinu. 3) Harmony Search tidak memerlukan pengaturan nilai awal untuk variabelvariabel. 4) Harmony Search bebas dari divergen. 5) Harmony Search dapat menghindari local optima. 6) Harmony Search memiliki turunan stohastik yang dapat diterapkan untuk variabel diskrit dimana memerlukan pengalaman musisi sebagai arah pencarian. 7) Obyek Harmony Search tertentu tidak memerlukan algoritma parameter seperti HMCR(Harmony Memory Considering Rate) dan PAR(Pitch Adjusting Rate), sehingga pengguna dapat dengan mudah menggunakan algoritma ini.
11
2.4 AlgoritmaHarmony Search
Gambar 2.1 StrukturHarmony Search
Gambar diatas menunjukkan struktur memori harmoni yang merupakan inti sari dari algoritma Harmony Search. Misalkan ada trio jazz yang terdiri dari saksofon, twin bass, dan gitar. Pada trio jazz tersebut terdapat beberapa nada yang dimiliki dalam setiap memori musisi: saksofon, {Do, Fa, Mi, Sol, Re}; twin bass, {Si, Do, Si, Re, Sol}; dan gitar, {La, Sol, Fa, Mi, Do}. Jika pemain saksofon secara acak memainkan {Sol} dari memorinya {Do, Fa, Mi, Sol, Re},pemain twin bass memainkan {Si} dari memorinya {Si, Do, Si, Re, Sol}, dan pemain gitar memainkan {Do} dari memorinya {La, Sol, Fa, Mi, Do}, harmoni baru (Sol, Si, Do) menjadi harmoni lain (dalam nada musik yaitu C-7 akord). Dan jika harmoni ini lebih baik daripada harmoni yang berada pada memori harmoni, maka harmoni baru dimasukkan ke dalam memori harmoni, lalu harmoni
12
terburuk dikeluarkan dari memori harmoni tersebut.Prosedur ini diulang sampai harmoni terbaik ditemukan.
Dalam optimalisasi, setiap musisi dapat digantikan dengan variabel keputusan, dan nada masing-masing pemain dapat digantikan dengan nilai-nilai variabel pilihan.Misalkan kita menetapkan bahwa setiap variabel keputusan mewakili diameter antara dua node dan nada lagu. {Do, Re, Mi, Fa, Sol, La, Si} diwakili {100mm, 200mm, 300mm, 400mm, 500mm, 600mm, 700mm}. Dan jika variabel pertama memilih {500mm} dari { 100mm, 400mm, 300mm, 500mm, 200mm}, variabel kedua {700mm} dari {700mm, 100mm, 700mm, 200mm, 500mm}, dan variabel ketiga {100mm} dari {600mm, 500mm, 400mm, 300mm, 100mm}, nilai-nilai tersebut (500mm, 700mm, 100mm) membuat solusi vektor lainnya. Dan jika nilai vektor baru ini lebih baik daripada nilai vektor lainnya, nilai vektor baru dimasukkan kedalam memori harmoni dan nilai vektor terburuk dikeluarkan dari memori harmoni.Prosedur ini diulang sampai kriteria pemberhenti tercapai(Geem, Lee, & Park, Application of Harmony Search to Vehicle Routing, 2005).
Menurut konsep algoritma di atas, langkah-langkah dalam prosedur Harmony Search untuk masalah penjadwalan kendaraan bus adalah sebagai berikut: 1) Menginisialisasi masalah dan parameter algoritma. 2) Menginisialisasi memori harmony. 3) Improvisasi harmoni baru dari memori harmoni. 4) Perbaharui memori harmoni.
13
5) Ulangi langkah 3 dan 4 sampai kriteria pemberhenti tercapai.
2.5 Langkah-langkah Algoritma Harmony Search Menurut Zong Woo Geem dan Justin C. Williams, langkah – langkah Algoritma Harmony Search terbagi menjadi (Geem & Williams, Harmony Search and Ecological Optimization, 2007, 150-151): 2.5.1
Inisialisasi Parameter Pada langkah pertama, masalah optimalisasi diberikan sebagai berikut:
Minimalkan(atau maksimalkan)f (x)
(1)
dimana Xi∈Xi , I = 1,2,…, N
(2)
f (x) adalah fungsi objektif: x adalah himpunan masing-masing variabel keputusan Xi ; Xi adalah himpunan nilai-nilai yang mungkin untuk setiap variabel keputusan, yaitu: Xi = { Xi(1), Xi(2),…, Xi(K)} variabel keputusan diskrit Xi 1
Xi 2
..
Xi
; N
adalah jumlah variabel keputusan ( sejumlah instrument musik); dan Kadalah jumlah nilai yang mungkin untuk variabel-variabel diskrit (rentang pitch instrument masingmasing).
Parameter algoritma Harmony Search juga ditentukan melalui: 1) Ukuran memori harmoni(=jumlah solusi vektor)(HMS). 2) Ukuran pertimbangan memori harmoni(HMCR). 3) Ukuran penyesuaian solusi(PAR). 4) Kriteria pemberhenti(=jumlah improvisasi).
14
2.5.2
Inisialisasi Memori Harmoni Pada langkah 2, matriks memori harmoni seperti yang ditunjukkan dalam
persamaan 3, diisi dengan solusi vektor acak sebanyak ukuran dari memori harmoni dan diurutkan berdasarkan nilai-nilai dari fungsi objektif, f (x).
X1 X2 Memori Harmoni(HM) =
(3) … xHM S
2.5.3
Improvisasi Harmoni Baru Sebuah vektor harmoni baru, x` = (x1`,x2`,…,x`N) yang dihasilkan dari salah satu
dari tiga tindakan berikut: Pertimbangan memori harmoni, pengukuran solusi, ataupun nilai acak. Misalnya, nilai dari variabel pertama (x1`) untuk vektor baru dapat dipilih dari siapapun dari nilai-nilai yang tersimpan dalam memori harmoni (xi1 ~ X1HMS). Nilai dari variabel lainnya (xi`) dapat dipilih dengan cara yang sama. Di bagian ini, dapat terjadi kemungkinan dimana suatu nilai acak dapat dipilih dengan menggunakan parameter HMCR(Harmony Memory Considering Rate), yang bervariasi antara 0 dan 1 sebagai berikut: Xi` ∈ {xi1, xi2, … ,xiHMS}
w.p.
HMCR
Xi`
(4) Xi`∈Xi
w.p.
(1-HMCR)
15
HMCR yang menentukan tingkat pemilihan satu nilai dari nilai-nilai yang tersimpan dalam memori harmoni, dan (1-HMCR) menentukan tingkat acak pemilihan satu nilai dari rentang nilai-nilai yang mungkin. Lalu, setiap komponen dari vektor harmoni baru x` = (x1`,x2`,…,x`N) diperika apakah hal tersebut harus disesuaikan. Prosedur ini menggunakan parameter PAR yang menetapkan tingkat penyesuaian untuk solusi dari memory harmony sebagai berikut:
Penyesuaian solusi for xi`
Ya
w.p.
PAR
Tidak
w.p.
(1-PAR)
(5)
Proses penyesuaian solusi dilakukan hanya dilakukan setelah suatu nilai dipilih dari memori harmoni. Nilai (1-PAR) tersebut menentukan tingkat untuk tidak melakukan apa-apa. Jika keputusan penyesuaian solusi untuk xi` adalah Ya dan xi` diasumsikan menjadi xi(k) (element ke-kpada Xi ), nilai penyesuaian solusi dari xi(k) adalah Xi`
Xi (k + m) untuk variabel keputusan diskrit
(6)
Dimana m adalah index terdekat, m∈{…, -2, -2, 1, 2, …}. Parameter HMCR dan PAR diperkenalkan dalam Harmony Search untuk membantu algoritma meningkatkan pencarian solusi secara lokal maupun global.
16
2.5.4
Perbaharui Memori Harmoni Setelah ditentukan oleh nilai fungsi objektif, jika vektor harmoni baru, x` =
(x1`,x2`,…,x`N) lebih baik daripada harmoni terburuk di memori harmoni, maka harmoni baru dimasukkan ke dalam memori harmoni dan harmoni terburuk dikeluarkan. Kemudian memori harmoni diurutkan berdasarkan nilai fungsi objektif.
2.5.5
Ulangi Langkah 3 dan 4 Langkah 3 dan 4 diulang sampai kriteria pemberhenti (misalnya, jumlah
maksimal improvisasi) tercapai.
2.6 Rapid Application Development (RAD)
Gambar 2.2 Rapid Application Development Method (RAD) Metodologi yang banyak digunakan untuk membangun perangkat lunak bisnis, dimana tahap awal merupakan analisa terhadap kebutuhan bisnis saat ini, kemudian
17
pengumpulan data untuk digunakan sebagai bahan perancangan sampai terbentuknya suatu perangkat lunak aplikasi yang membantu dalam pengambilan keputusan manajer. Langkah – Langkah RAD terbagi menjadi: 1. Analisis dan Draft Desain Awal dari tahap perancangan program yaitu analisis masalah dan desain pemecahan masalah. Pada tahap ini, analisis dan desain pemecahan sudah jelas. 2. Repetisi Prototype, pada bagian perulangan prototype ini terbagi menjadi: a) Demonstrasi Demonstrasi program sementara untuk menunjukkan perkembangan dari program yang didapat dari hasil analisis dan desain pemecahan masalah. b) Perbaiki Memperbaiki program dan mencatat erroryang terjadi pada program. Tahap ini dilakukan terus – menerus sampai error tidak muncul lagi. c) Rancang Merancang program berdasarkan analisis dan desain pemecahan masalah yang terus menerus disesuaikan agar desain tersebut dan analisa yang ingin diterapkan dapat terealisasikan dengan sempurna. 3. Uji Coba Menguji coba hasil program jadi pada lapangan sebagai uji coba terakhir pada program dengan mengikuti data lapangan
18
4. Implementasi Menerapkan program / sistem yang sudah jadi pada lapangan sehingga sistem tersebut dapat berfungsi sepenuhnya sesuai yang diharapkan.
2.7 PHP (Hypertext Preprocessor) PHP merupakan salah satu bahasa pemrograman web yang paling banyak digunakan saat ini. Hasil dari Netcraft, menyatakan bahwa ada kurang lebih 52juta pengguna PHP diseluruh dunia atau kalau di persentase sekitar 70,9%. Sebuah angka yang fantastis untuk sebuah bahasa pemrograman.
Sejarah PHP dimulai pada Tahun 1995, ketika Rasmus Lerdorf -seorang software development contractor - mengembangkan skrip Perl/CGI untuk mengetahui jumlah pembaca online resume-nya. Skrip tersebut mengerjakan dua hal: mencatat informasi pengunjung, dan menampilkan jumlah pengunjung ke halaman web. Waktu itu belum ada tools seperti yang dibuat oleh Rasmus, sehingga banyak developer yang mengirimkan e-mail ke Rasmus, menanyakan tentang skrip yang dibuatnya. Hal itulah yang membuat Rasmus melepas skripnya, dan diberi nama PHP (Personal Home Page). Rasmus kemudian mulai mengembangkan banyak tambahan pada PHP, salah satu diantaranya adalah mengubah data yang dimasukkan dalam form HTML menjadi sebuah variabel. Pengubahan data ini nantinya akan memungkinkan user untuk mengekspor data ke dalam sistem mereka. Untuk menyelesaikan tambahan tersebut, Rasmus lebih memilih menggunakan bahasa C daripada Perl.
19
Tambahan terus-menerus kepada PHP toolset memuncak pada November 1997 dengan pelepasan PHP 2.0, atau Personal Home Pageb Form Interpreter (PHPFI).Peluncuran ini juga meningkatkan popularitas PHP, yang ditandai dengan banyaknya pengembangan dan perbaikan yang dilakukan oleh programmer di seluruh dunia.Peluncuran PHP yang sedemikian populer, membuat sebuah tim developer bergabung dengan Rasmus. Mereka menjaga konsep penyisipan kode secara langsung ke dalam HTML, dan menulis kembali parsing engine-nya.Hal ini kemudian melahirkan PHP 3.0.Pada pelepasannya -ditahun 1998-, ada 50.000 user yang menggunakan PHP pada website mereka.Pada tahun 1999, NetCraft mencatat ada 1.000.000 lebih pengguna PHP yang membuat PHP menjadi “the most popular scripting languages in the world”.Dua pengembang inti PHP, Zeev Suraski dan Andi Gutmans, mengambil inisiatif untuk mempelopori pemikiran kembali tentang bagaimana PHP dioperasikan, dan kemudian mengenalkan Zend scripting engine (Anonym, 2006).
PHP (akronim dari PHP Hypertext Preprocessor) yang merupakan bahasa pemrograman berbasis web yang memiliki kemampuan untuk memproses data dinamis.PHP dikatakan sebagai sebuah server-side embedded script language artinya sintaks-sintaks dan perintah yang kita berikan akan sepenuhnya dijalankan oleh server tetapi disertakan pada halaman HTML biasa. Aplikasi-aplikasi yang dibangun oleh PHP pada umumnya akan memberikan hasil pada web browser, tetapi prosesnya secara keseluruhan dijalankan di server.Pada prinsipnya
server akan bekerja apabila ada
permintaan dari client. Dalam hal ini client menggunakan kode-kode PHP untuk mengirimkan permintaan ke server (dapat dilihat pada gambar dibawah). Ketika
20
m menggunaka an PHP sebbagai server-side embeddded script language maka m server akan m melakukan hal-hal h sebaggai berikut: 1) Mem mbaca permiintaan dari client/browse c er 2) Men ncari halamaan/page di seerver 3) Melakukan instrruksi yang diberikan d oleeh PHP untukk melakukann modifikasii pada halaman n/page. 4) Men ngirim kembbali halaman tersebut keppada client melalui m internet atau intrranet.
bar 2.3 Stru uktur PHP Gamb
Keun ntungan mennggunakan PHP P adalah: 1) Practtical / Praktiis: PHP adalah bahaasa pemrogrraman yang sangat fleksibel dalam penulisan, p daan ini meniingkatkan kepraktisan buat b para peenggunanya.. Misalnya saja program mmer tidak k diharuskann untuk menuuliskan atauu menghapuss variabel. Walaupun W kaadang
21
mereka juga tidak bisa mengatakan dengan mudah yang kemudian dipanggil dalam sebuah skrip, menebak formula terbaik dalam penetapan variabel secara otomatis kemudian menghapus variabel dan dan mengembalikan resource ke sistem setelah skrip berhasil di eksekusi. Pada akhirnya, PHP mampu membuat programmer lebih berpikir pada tujuan akhir dari project yang akan dibuat.
2) Power: Sudah jadi rahasia umum kalau PHP mampu membuat halaman dinamis, memanipulasi form, dan dapat dihubungkan dengan database. Selain yang disebutkan tadi, ternyata PHP juga mampu melakukan hal-hal dibawah ini: •
Membuat dan memanipulasi file Macromedia Flash, gambar, dan Portable Document Format (PDF).
•
Mengevaluasi sebuah password. Misal: Apakah sebuah password yang dibuat, gampang ditebak atau tidak.
•
Berkomunikasi dengan LDAP.
•
Menguraikan
string,
bahkan
yang
kompleks
sekalipun,
dengan
menggunakanPOSIX dan Perl Based Regular Expression Library. •
Berkomunikasi dengan banyak protokol, termasuk IMAP, POP3 dan NNTP.
•
Berkomunikasi dengan credit-card processing solution.
3) Possibility Jarang ada developer PHP yang terikat pada suatu implementasi pemecahan masalah. Dilain sisi, ada banyak pilihan yang ditawarkan oleh PHP.
22
Contohnya ada pada database yang didukung oleh PHP. Kurang lebih semuanya ada 25 database, termasuk Adabas D, dBase, Empress, FilePro, FrontBase, Hyperwave, IBM DB2, Informix, Ingres, Interbase, mSQL, direct MS-SQL, MySQL, Oracle, Ovrimos, PostgreSQL, Solid, Sybase, Unix dbm, dan Velocis.Kemampuan string-parsing juga bisa dianggap sebagai banyaknya kemungkinan yang ditawarkan oleh PHP.Dalam hal in, PHP memiliki lebih dari 85 function untuk memanipulasi string. Kelebihan ini tak hanya akan menawarkan keleluasaan untuk melakukan operasi string yang kompleks, namun juga menjembatani program yang memiliki fungsionalitas yang sama (seperti Python dan Perl) lewat PHP.
4) Price PHP merupakan salah satu open source software, yang dapat diartikan sebagai berikut: * PHP dapat dimodifikasi, didistribusikan, dan diintegrasikan dengan produk lain olehpenggunanya. * Pengembangan dan auditing yang dilakukan secara terbuka. * Semua orang bebas berpastisipasi.
2.8 Interaksi Manusia dan Komputer Berdasarkan evaluasi dari sudut interaksi manusia dan komputer, program yang dirancang harus bersifat interaktif. Suatu program yang interaktif dan baik harus bersifat user friendly, dengan lima kriteria sebagai berikut:
23
1) Waktu belajar yang tidak lama. 2) Kecepatan penyajian informasi yang tepat. 3) Tingkat kesalahan pemakaian rendah. 4) Penghafalan sesudah melampaui jangka waktu. 5) Kepuasan pribadi.
Dalam merancang sistem interaksi manusia dan komputer yang baik juga harus memperhatikan delapan aturan utama (eight golden rules), yaitu: 1) Strive for consistency (berusaha untuk konsisten). 2) Enable frequent user to use shortcuts (memungkinkan pengguna untuk menggunakan jalan pintas). 3) Offer informative feedback (memberikan balasan yang informatif). 4) Design dialogs to yield closure (pengorganisasian yang baik sehingga pengguna mengetahui kapan awal dan akhir dari suatu aksi). 5) Offer simple error handling (memberikan pencegahan dan pengaturan kesalahan yang sederhana). 6) Permit easy reversal of actions (memungkinkan kembali ke aksi sebelumnya dengan mudah). 7) Support internal locus of control (memungkinkan pengguna untuk menguasai dan mengontrol sistem). 8) Reduce short term memory load (mengurangi beban ingatan jangka pendek, sehingga pengguna tidak perlu banyak menghafal).
