BAB 2 LANDASAN TEORI

BAB 2 LANDASAN TEORI

Bab ini akan membahas tentang teori dan konsep dasar yang mendukung pembangunan dari aplikasi yang dibuat.

2.1 Penjadwalan Penjadwalan adalah pengaturan waktu dari suatu kegiatan operasi, mencakup kegiatan mengalokasi fasilitas, peralatan dan tenaga kerja bagi suatu kegiatan operasi serta menentukan urutan pelaksanaan kegiatan operasi. Penjadwalan atau scheduling juga merupakan salah satu kegiatan penting dalam menjalankan suatu perusahaan atau instansi yang diperlukan dalam mengalokasikan tenaga operator, mesin dan peralatan produksi, urutan proses, jenis produk dan sebabgainya. Umumnya disusun dengan mempertimbangkan berbagai batasan, misalnya meminimalkan waktu proses, waktu tunggu langganan, tingkat persediaaan serta penggunaaan yang efisien dari fasilitas, personel dan peralatan (Taufik, 2013). Penjadwalan pada prinsipnya terjadi baik untuk periode yang panjang (misalnya tahunan) ataupun periode yang lebih pendek (misalnya harian atau periode jam). Penjadwalan yang dimaksudkan di sini adalah penjadwalan jangka pendek karena penjadwalan jangka panjang biasanya dibahas dengan pendekatan lain seperti manajemen projek. Kalau pun penjadwalan jangka panjang tadi bukan bersifat projek, yaitu seperti kegiatan rutin tahunan, maka pendekatan penjadwalan jangka pendek ini pun dapat kita terapkan pada kasus tersebut (Mursyid, 2010).

2.1.1

Teknik-Teknik dalam Melakukan Penjadwalan

Ada dua jenis penjadwalan secara umum yaitu (Taufik, 2013) : a. Penjadwalan Maju

(Forward Scheduling) Pekerjaan dimulai sedini

mungkin sehingga pekerjaaan selesai sebelum batas waktu yang dijanjikan

Universitas Sumatera Utara

5

b. (due date). Konsekuensinya adalah terjadinya akumulasi persediaaan sampai pekerjaan tersebut diperlukan pada pusat kerja berikutnya. c. Penjadwalan Mundur (Backward Scheduling) Kegiatan operasi yang terakhir dijadwalkan lebih dulu, yang selanjutnya secara berturut-turut ditentukan jadwal untuk kegiatan sebelumnya satu per satu secara mundur.Konsekuensi dapat meminimalkan persediaaan karena baru selesai pada saat pekerjaan tersebut diperlukan pada stasiun kerja berikutnya. Catatan: harus disertai dengan perencanaan dan estimasi waktu tenggang yang akurat, tidak terjadi break down selama proses maupun perubahan due date yang lebih cepat.

2.1.2

Hal-Hal yang Harus Diperhatikan dalam Melakukan Penjadwalan

Ada beberapa hal penting yang sifatnya strategis dapat kita raih jika melakukan penjadwalan dengan baik (Mursyid, 2010) : a. Penjadwalan yang baik membuat organisasi dapat menggunakan aset atau sumber dayanya dengan lebih efisien dan berefek positif juga pada pencapaian tujuannya. b. Kapasitas yang fleksibel dalam memenuhi kebutuhan pelanggan. c. Kepastian dalam melaksanakan penjadawalan yang akan dibuat.

2.1.3

Implikasi Strategi Penjadwalan

Ada 4 macam implikasi dalam strategi penjadwalan (Taufik, 2013), yaitu: a. Dengan penjadwalan yang baik, penggunaan aset perusahaan menjadi lebih efektif sehingga biaya menjadi rendah. b. Penggunaan kapasitas menjadi bertambah karena perputaran aktiva menjadi lebih besar. c. Pelayanan pelanggan (customer service) menjadi lebih baik. d. Mendapatkan keunggulan kompetitif.

2.1.4

Keputusan-Keputusan dalam Penjadwalan

Setiap organisasi yang menjadi objek penelitian selalu memiliki keputusan dalam penjadwalan. Ini berfungsi sebagai objek kajian dalam sistem pendukung keputusan


6

nantinya menentukan rancangan penelitian. Perhatikan tabel dibawah ini, contohcontoh organisasi beserta keputusannya. Tabel 2.1 Keputusan dalam Penjadwalan Organisasi

Keputusan Dalam Penjadwalan

Rumah Sakit

Ruang operasi, Perawat, Security, Pasien Rawat Jalan

Universitas

Ruang kelas,Alat Audiovisual, Penjadwalan Dosen dan Mahasiswa, Jadwal Kursus

Pabrik

Produksi, Pembelian Bahan, Gaji

Café

Cheef, Bartender, Pelayan, Entertainer

Bandara Udara

Jadwal Penerbangan

2.2 Algoritma Genetika Algoritma ini ditemukan di Universitas Michigan, Amerika Serikat oleh John Holland (1975) melalui sebuah penelitian dan dipopulerkan oleh salah satu muridnya, David Goldberg. Algoritma genetik adalah algoritma yang berusaha menerapkan pemahaman mengenai evolusi alamiah pada tugas-tugas pemecahan-masalah (problem solving). Pendekatan yang diambil oleh algoritma ini adalah dengan menggabungkan secara acak berbagai pilihan solusi terbaik di dalam suatu kumpulan untuk mendapatkan generasi solusi terbaik berikutnya yaitu pada suatu kondisi yang memaksimalkan kecocokannya atau lazim disebut fitness. Generasi ini akan merepresentasikan perbaikanperbaikan pada populasi awalnya. Dengan melakukan proses ini secara berulang, algoritma ini diharapkan dapat mensimulasikan proses evolusioner (Ivan, 2008). Algoritma genetika merupakan algoritma pencarian yang menerapkan proses seleksi alam dan evolusi yang dikemukakan oleh Charles Darwin. Algoritma genetika pertama kali diperkenalkan oleh John Holland (1975) dari Universitas Michigan. John Holland menyatakan bahwa setiap masalah yang berbentuk adaptasi (alami maupun buatan) dapat diformulasikan kedalam terminologi genetika (Saraswat & Prayanthi, 2012).


7

Algoritma genetik bukanlah solusi terbaik untuk memecahkan segala masalah. Sebagai contoh, metode tradisional telah diatur untuk untuk mencari penyelesaian dari fungsi analitis convex yang “berperilaku baik” yang variabelnya sedikit. Pada kasuskasus ini, metode berbasis kalkulus lebih unggul dari algoritma genetik karena metode ini dengan cepat menemukan solusi minimum ketika algoritma genetik masih menganalisa bobot dari populasi awal. Untuk problemproblem ini pengguna harus mengakui fakta dari pengalaman ini dan memakai metode tradisional yang lebih cepat tersebut. Akan tetapi, banyak persoalan realistis yang berada di luar golongan ini. Selain itu, untuk persoalan yang tidak terlalu rumit, banyak cara yang lebih cepat dari algoritma genetik (Ivan, 2008). Sifat algoritma genetika adalah mencari kemungkinan-kemungkinan dari kandidat solusi untuk mendapatkan yang optimal untuk penyelesaian masalah. Ruang cakupan dari semua solusi yang layak (feasible), yaitu objek-objek diantara solusi yang sesuai, dinamakan ruang pencarian (search space). Tiap titik dalam ruang pencarian mempresentasikan satu solusi yang layak. Tiap solusi yang layak dapat ditandai dengan nilai fitness-nya bagi masalah. Algoritma genetika bekerja dari populasi yang merupakan himpunan solusi yang dihasilkan secara acak. Setiap anggota himpunan yang merepresentasikan satu solusi masalah. Suatu solusi masalah berevolusi dalam iterasi yang dinamakan generasi, tiap solusi masalah dievaluasi berdasarkan fungsi evaluasi (fitness function). Pada algoritma genetika, fitness biasanya dapat berupa fungsi objektif dari masalah yang akan dioptimalisasi (Saraswat & Prayanthi, 2012).

2.2.1

Teknik-Teknik dalam Algortima Genetik

Ada 4 teknik yang dapat dilihat dalam Speech Recognition (Ivan, 2008) yaitu : a. Fitness Function Setiap individual dievaluasi dengan fitness function. Sebuah fitness function mengembalikan nilai tertinggi untuk individual yang terbaik. Individu akan diurutkan berdasarkan nilai atau disebut dengan selection.


8

b. Crossover Untuk setiap pasang induk, sebuah titik crossover akan dipilih secara random dari posisi dalam string. Pada gambar titik crossover terletak pada indeks ketiga dalam pasangan pertama dan setelah indeks kelima pada pasangan kedua.

c. Mutasi Pada mutasi, tiap lokasi menjadi sasaran mutasi acak, dengan probabilitas independen yang kecil. Sebuah digit dimutasikan pada anak pertama, ketiga, dan keempat. Algoritma genetika mengkombinasikan suatu kecenderungan menaik dengan pengeksplorasian acak diantara thread pencarian paralel. Keuntungan secara matematis dapat tunjukkan bahwa bila posisi dari kode genetik di permutasikan di awal dengan urutan acak, crossover tidak memberikan keunggulan. Secara intuisi, keuntungannya didapat dari kemampuan crossover untuk menggabungkan blok-blok huruf berukuran besar yang telah berevolusi secara independen untuk melakukan fungsi yang bermanfaat sehingga dapat menaikkan tingkat granularity di mana pencarian dilakukan. Metode dan tipe mutasi yang dilakukan juga tergantung pada encoding dan permasalahan yang diangkat. Berdasarkan encodingnya terdapat beberapa macam, diantaranya adalah sebagai berikut (Ihsania, 2010) : 1. Binary Encoding Melakukan inversi pada bit yang terpilih, 0 menjadi 1 dan sebaliknya, 1 menjadi 0. Contoh : 11001001 => 10001001 2. Permutation Encoding Memilih dua nilai dari gen dan menukarnya. Contoh : ( 1 2 3 4 5 8 9 7 ) => ( 1 8 3 4 5 6 2 9 7 ) Beberapa operator mutasi telah diciptakan untuk representasi permutasi, seperti metode inversion, insertion, displacement, dan reciprocal exchange mutation (Ihsania, 2010).


9

a. Inversion Mutation Inversion mutation memilih dua posisi dalam sebuah kromosom

dengan

cara

acak

dan

kemudian

menginversikan substring di antara dua posisi tersebut. b. Insertion Mutation Insertion Mutation memilih sebuah gen dengan cara acak dan memasukkan ke dalam kromosom dengan cara acak pula. c. Dsisplacement Mutation Displacement Mutation memilih sebuah sub/sekelompok gen dengan cara acak kemudian memasukkan ke dalam kromosom dengan cara acak. d. Reciprocal Exchange Mutation (REM) Reciprocal Exchange Mutation memilih dua posisi secara acak, kemudian menukar dua gen dalam posisi tersebut.

3. Value Encoding Menentukan sebuah nilai kecil yang akan ditambahkan atau dikurangkan pada salah satu gen dalam kromosom. Contoh : ( 1.29 5.68 2.86 4.11 5.55 ) => ( 1.29 5.68 2.73 4.22 5.55)

4. Tree Encoding Node yang terpilih akan diubah.

d. Schema Teori dari algoritma genetik menjelaskan cara kerjanya menggunakan ide dari suatu schema, suatu substring di mana beberapa posisi tidak disebutkan. Dapat ditunjukkan bahwa, bila fitness rata-rata dari schema berada di bawah mean maka jumlah instansiasi dari schema di dalam populasi akan bertambah seiring bertambaahnya waktu. Jelas sekali bahwa efek ini tidak akan signifikan bila bit-bit yang bersebelahan sama sekali tidak berhubungan satu sama sekali, karena akan ada beberapa blok


10

kontigu yang memberikan keuntungan yang konsisten. Algoritma genetik paling efektif dipakai bila schema-schema berkorespondensi menjadi komponen berati dari sebuah solusi. Sebagai contoh, bila string adalah representasi dari sebuah antena, maka schema merepresentasikan komponen-komponen dari antena, seperti reflector dan deflector. Sebuah komponen yang baik cenderung akan berkerja baik pada rancangan yang berbeda. Ini menunjukkan bahwa penggunaan algoritma genetik yang benar memerlukan rekayasa yang baik pada representasinya.

2.2.2

Contoh-contoh Pengaplikasian Algoritma Genetik

Algoritma genetika sudah banyak diaplikasikan untuk penyelesaian masalah dan pemodelan dalam bidang teknologi, bisnis, dan entertainment (Ihsania, 2010), seperti : a. Optimasi Algoritma genetika untuk optimasi numerik dan optimasi kombinatorial seperti Traveling Salesman Problem (TSP), perancangan Integrated circuit atau IC, optimasi video dan suara.

b. Pemrograman Otomatis Algoritma genetika telah digunakan untuk melakukan proses evolusi terhadap program komputer untuk merancang struktur komputasiona, seperti cellular automata dan sorting network.

c. Machine Learning Algoritma genetika telah berhasil diaplikasikan untuk memprediksi struktur protein, dan berhasil diaplikasikan dalam perancangan neural networks (jaringan syaraf tiruan) untuk melakukan proses evolusi terhadap aturan-aturan pada learning classifier system atau symbolic production system, juga digunakan untuk mengontrol robot.

d. Model Ekonomi Algoritma genetika telah digunakan untuk memodelkan proses-proses inovasi dan pembangunan bidding strategies.


11

e. Model Sistem Imunisasi Algoritma genetika telah berhasil digunakan untuk memodelkan berbagai aspek pada sistem imunisasi alamiah, termasuk somatic mutation selama kehidupan individu dan menemukan keluarga dengan gen ganda (multigene families) sepanjang waktu evolusi.

f. Model Ekologis Algoritma genetika berhasil digunakan untuk memodelkan fenomena ekologis seperti host-parasite co-evolutions, simbiosis, dan aliran sumber daya dalam ekologi.

2.2.3

Masalah-masalah yang Bisa Diselesaikan dengan Algoritma Genetik

Algoritma genetika sangat berguna dan efisien untuk masalah-masalah dengan karakteristik sebagai berikut (Ihsania, 2010) : a. Ruang masalah sangat besar, kompleks, dan sulit dipahami. b. Kurang atau bahkan tidak ada pengetahuan yang memadai untuk merepresentasikan masalah ke dalam ruang pencarian yang lebih sempit. c. Tidak tersedianya analisis matematika yang memadai. d. Ketika metode-metode konvensional sudah tidak mampu meyelesaikan masalah yang dihadapi. e. Solusi yang diharapkan tidak harus paling optimal, tetapi cukup bagus atau bisa diterima. f. Terdapat batasan waktu, misalnya real time system atau sistem waktu nyata.

2.3 Algoritma Simulated Annealing Algoritma Simulated Annealing adalah sebagai berikut : 1. Evaluasi keadaan awal. Jika keadaan awal merupakan tujuan, maka pencarian berhasil dan KELUAR. Jika tidak demikian, lanjutkan dengan menetapkan keadaan awal sebagai kondisi sekarang. 2. Inisialisasi BEST_SO_FAR untuk keadaan sekarang. 3. Inisialisasi T sesuai dengan annealing schedule.


12

4. Kerjakan hingga solusi ditemukan atau sudah tidak ada operator baru lagi akan diaplikasikan ke kondisi sekarang. a. Gunakan operator yang belum pernah digunakan tersebut untuk menghasilkan kondisi baru. b. Evaluasi kondisi yang baru dengan menghitung: ΔE = nilai sekarang – nilai keadaan baru. i. Jika kondisi baru merupakan tujuan, maka pencarian berhasil dan KELUAR. ii. Jika bukan tujuan, namun memiliki nilai yang lebih baik daripada kondisi sekarang, maka tetapkan kondisi baru sebagai kondisi sekarang. Demikian pula tetapkan BEST_SO_FAR untuk kondisi yang baru tadi. D-23 iii. Jika nilai kondisi baru tidak lebih baik dari kondisi sekarang, maka tetapkan kondisi baru sebagai kondisi sekarang dengan probabilitas: p' = e−ΔE / T Langkah ini biasanya dikerjakan dengan membangkitkan suatu bilangan random r pada range [0 1]. Jika r < p’, maka perubahan kondisi baru menjadi kondisi sekarang diperbolehkan. Namun jika tidak demikian, maka tidak akan dikerjakan apapun.

2.3.1

Konsep Dasar Simulated Annealing

Ide dasar simulated annealing terbentuk dari pemrosesan logam . Annealing (memanaskan kemudian mendinginkan) dalam pemrosesan logam ini adalah suatu proses bagaimana membuat bentuk cair berangsur-angsur menjadi bentuk yang lebih padat seiring dengan penurunan temperatur. Simulated annealing biasanya digunakan untuk penyelesaian masalah yang mana perubahan keadaan dari suatu kondisi ke kondisi yang lainnya membutuhkan ruang yang sangat luas, misalkan perubahan gerakan dengan menggunakan permutasi pada masalah Travelling Salesman Problem. Pada simulated annealing, ada 3 parameter yang sangat menentukan, yaitu: tetangga, gain, temperatur, pembangkitan bilangan random. Tetangga akan sangat berperan dalam membentuk perubahan pada solusi sekarang. Pembangkitan bilangan random akan berimplikasi adanya probabilitas.


13

2.4 Algoritma Particle Swarm Optimazation Particle Swarm Optimization adalah salah satu metode optimasi yang terinspirasi dari perilaku gerakan kawanan hewan seperti ikan (school of fish), hewan herbivor (herd), dan burung (flock) yang kemudian tiap objek hewan disederhanakan menjadi sebuah partikel. Suatu partikel dalam ruang memiliki posisi yang dikodekan sebagai vektor koordinat. Vektor posisi ini dianggap sebagai keadaan yang sedang ditempati oleh suatu partikel di ruang pencarian. Setiap posisi dalam ruang pencarian merupakan alternatif solusi yang dapat dievaluasi menggunakan fungsi objektif. Setiap partikel bergerak dengan kecepatan v. Particle Swarm Optimization atau yang kita kenal dengan PSO menerapkan sifat masing-masing individu dalam satu kelompok besar. Kemudian menggabungkan sifat-sifat tersebut untuk menyelesaikan permasalahan. Particle Swarm Optimization pertama kali dimunculkan pada tahun 1995, sejak saat itulah para peneliti banyak menurunkan dan mengembangkan metode PSO. Ciri khas dari PSO adalah pengaturan kecepatan partikel secara heuristik dan probabilistik. Jika suatu partikel memiliki kecepatan yang konstan maka jika jejak posisi suatu partikel divisualisasikan akan membentuk garis lurus. Dengan adanya faktor eksternal yang membelokkan garis tersebut yang kemudian menggerakkan partikel dalam ruang pencarian maka diharapkan partikel dapat mengarah, mendekati, dan pada akhirnya mencapai titik optimal. Faktor eksternal yang dimaksud antara lain posisi terbaik yang pernah dikunjungi suatu partikel, posisi terbaik seluruh partikel (diasumsikan setiap partikel mengetahui posisi terbaik setiap partikel lainnya), serta faktor kreativitas untuk melakukan eksplorasi. Particle Swarm Optimization memiliki kesamaan sifat dengan teknik komputasi seperti Algoritma Genetika (Genetic Algorithm). Sistem PSO diinisialisasi oleh sebuah populasi solusi secara acak dan selanjutnya mencari titik optimum dengan cara meng-update tiap hasil pembangkitan. Metode optimasi yang didasarkan pada swarm intelligence ini disebut algoritma behaviorally inspired sebagai alternatif dari algoritma genetika, yang sering disebut evolution-based procedures. Dalam konteks optimasi multivariabel, kawanan diasumsikan mempunyai ukuran tertentu atau tetap


14

dengan setiap partikel posisi awalnya terletak di suatu lokasi yang acak dalam ruang multidimensi. Setiap partikel diasumsikan memiliki dua karakteristik: posisi dan kecepatan. Setiap partikel bergerak dalam ruang/space tertentu dan mengingat posisi terbaik yang pernah dilalui atau ditemukan terhadap sumber makanan atau nilai fungsi objektif. Setiap partikel menyampaikan informasi atau posisi bagusnya kepada partikel yang lain dan menyesuaikan posisi dan kecepatan masing-masing berdasarkan informasi yang diterima mengenai posisi yang bagus tersebut.


BAB 2 LANDASAN TEORI

Recommend Documents