7
Bab II Tinjauan Pustaka
2.1
Penelitian Terdahulu Penelitian mengenai Visualisasi Rute Terpendek Jalur
Angkutan Kota Dengan Algoritma Genetika membahas tentang perancangan dan pembuatan aplikasi yang dapat digunakan untuk mencari rute terpendek dengan menerapkan algoritma Genetika optimization. Algoritma ini melakukan pencarian rute terpendek angkutan kota yang diaplikasikan di kota Jember. Aplikasi yang dibuat bermanfaat untuk memberikan informasi rute angkutan kota terpendek, berupa jalan-jalan yang dilalui, panjang perjalanan dan angkutan kota yang dapat digunakan. Sistem yang dibangun menggunakan aplikasi Visual Basic 6 dan Macromedia Flash. (Swastika, 2009) Penelitian Sistem Informasi Penjadwalan Kereta Rel Listrik menggunakan
algoritma
genetik
untuk
melakukan
optimasi
penjadwalan kereta api di daerah JABOBETABEK. Sistem yang dibangun akan melakukan penjadwalan Kereta Rel Listrik (KRL) yang lebih optimal dengan menggunakan algoritma genetik. Sistem yang dibangun menggukan Borland C++ Builder 6 dengan bahasa pemrogramman C sedangkan untuk databasenya menggunakan Interbase 7. (Wijaya, 2009)
8
Program algoritma genetika yang dijalankan dapat berjalan dengan efektif di dua eksperimen yang berbeda. Dimana eksperimen yang pertama setiap mesin hanya dapat menampung satu operasi sedangkan eksperimen yang kedua setiap mesin dapat menampung maksimal dua operasi. Program algoritma genetika dapat digunakan pada persoalan penjadwalan job shop yang produknya multi produk (mode 1) maupun persoalan penjadwalan job shop yang produknya berbaur dan multi produk (mode2). Program algoritma genetika dapat dijalankan pada berbagai data order dan data efisiensi operasi yang berbeda dengan ketentuan data-data tersebut memenuhi batasanbatasan dalam pemodelan yang sesuai dengan masalah penjadwalan job shop. Pengembangan yang dapat dilakukan terhadap program algoritma genetika pada permasalahan penjadwalan job shop terutama produknya yang dihasilkan bersifat berbaur dan multi produk dengan mempertimbangkan efek ketidakpastian yang terjadi pada proses penjadwalan.
Diantaranya
adalah
ketidakpastian
permintaan
konsumen, gangguan mesin, kekurangan bahan baku, ketidakhadiran operator mesin, dan lainnya. Hal-hal tersebut sangat berpengaruh dan menyebabkan perubahan yang cukup signifikan terhadap proses penjadwalan job shop. Begitu juga dengan pembatalan order yang telah terjadwal akan berakibat pada perubahan susunan operasi yang dikerjakan pada mesin produksi. (Fachrudin, dkk, 2011) Berbeda dengan penelitian sebelumnya, dalam penelitian kali ini dilakukan pada PT. KAI Semarang untuk mengatur penjadwalan kereta tujuan Semarang Jakarta dan sebaliknya. Metode pencarian solusi penjadwalan kereta api menggunakan algoritma genetik (Genetic Algorithm). Aplikasi Penjadwalan Kereta Api ini dibangun
9
dengan menggunakan bahasa pemrogramman Microsoft Visual Studio 2010 dan database MySQL .
2.2
Penjadwalan Penjadwalan adalah kegiatan pengalokasian sumber-sumber
atau mesin-mesin yang ada untuk menjalankan sekumpulan tugas dalam jangka waktu tertentu (Baker, 1974). Keputusan yang dibuat di dalam penjadwalan meliputi pengurutan pekerjaan (sequencing), waktu mulai dan selesai pekerjaan (timing), dan urutan operasi untuk urutan pekerjaan (routing). Persoalaan penjadwalan timbul apabila ada beberapa pekerjaan diselesaikan secara bersamaan, sedangkan fasilitas yang dimiliki terbatas seperti masalah pada penjadwalan kereta api ini. Dari penjelasan definisi penjadwalan diatas dapat dikatakan bahwa penjadwalan merupakan suatu kegiatan perancangan berupa pengalokasian sumber daya baik mesin maupun tenaga kerja untuk menjalankan sekumpulan tugas sesuai prosesnya di dalam jangka waktu tertentu 2.2.1 Masalah Penjadwalan Masalah penjadwalan muncul karena adanya keterbatasan waktu, tenaga kerja, jumlah mesin, sifat dan syarat pekerjaan yang akan dilaksanakan. Secara umum ada dua permasalahan utama yang akan
diselesaikan
melalui
penjadwalan,
yaitu
penentuan
pengalokasian mesin yang akan digunakan untuk menyelesaikan suatu proses produksi dan pengurutan waktu pemakaian mesin tersebut (Jovan, 2006).
10
Masalah penjadwalan dapat ditinjau dari berbagai aspek diantaranya: a.
Mesin (terbagi atas penjadwalan mesin tunggal, penjadwalan dua mesin, dan penjadwalan m mesin)
b. Aliran proses (terbagi atas job shop dan flow shop). Aliran proses job shop memungkinkan pekerjaan melalui lintasan yang berbeda antar jenisnya. Sedangakan aliran flow shop sebaliknya. c.
Pola kedatangan pekerjaan, secara statis maupun dinamis. Dimana jika semua pekerjaan datang secara bersamaan dan semua fasilitas tersedia pada saat kedatangan pekerjaan disebut pola kedatangan pekerjaan statis. Sedangkan jika pekerjaan datang secara acak selama masa penjadwalan disebut pola kedatangan pekerjaan dinamis.
d. Elemen penjadwalan, mengenai ketidakpastian pada pekerjaan dan mesin. Terdiri dari elemen penjadwalan deterministik dan elemen penjadwalan stokastik. Jika elemen penjadwalannya deterministik, maka terdapat kapasitas tentang pekerjaan dan mesin, misalnya tentang waktu kedatangan, waktu set up dan waktu proses. Sebaliknya jika tidak terdapat kepastian mengenai pekerjaan dan mesin, maka disebut elemen penjadwalan stokastik.
11
2.2.2 Tujuan Penjadwalan Secara umum, tujuan dari penjadwalan adalah sebagai berikut (Saputro dan Yento, 2004) : 1. Meningkatkan
produktivitas
kereta
api,
yaitu
dengan
mengurangi idle time. 2. Mengurangi jumlah rata-rata pemberangkatan yang menunggu dalam antrian kereta api yang sibuk. 3. Mengurangi keterlambatan karena batas waktu (due date) telah
dilewati
keterlambatan
dengan maupun
cara
mengurangi
dengan
maksimum
mengurangi
jumlah
pemberangkatan kereta api yang terlambat. 4. Penetapan due date, saat waktu dimana kereta api harus telah selesai proses.
2.2.3
Klasifikasi Penjadwalan Kereta Api Beberapa model penjadwalan yang sering terjadi di dalam
proses penjadwalan kereta api adalah sebagai berikut (Saputro dan Yento, 2004). : 1. Berdasarkan jumlah yang digunakan dalam proses : a. Penjadwalan pada kereta api tunggal Penjadwalan model ini adalah, dimana hanya terdiri dari satu kereta api dan semua proses pemberangkatan harus diproses pada kereta api ini. Kereta api dapat memproses satu pemberangkatan pemberangkatan
pada diproses
waktu pada
pemberangkatan itu telah selesai.
kapanpun. kereta
api
Sekali maka
12
b. Penjadwalan pada kereta api multi Dalam dunia industri sering kali jenis kereta api yang identik digabungkan menjadi satu region, hal ini sering disebut sebagai kereta api paralel. Dalam tipe kereta api paralel kita mengasumsikan bahwa pemberangkatan dapat dikerjakan pada beberapa kereta api berbeda dalam satu region. 2. Berdasarkan kedatangan job : a. Penjadwalan statis: penjadwalan statis adalah, dimana job yang datang bersamaan dan siap dikerjakan pada kereta api yang tidak bekerja. b. Penjadwalan dinamis: adalah penjadwalan dimana kedatangan job tidak menentu.
2.3
Algoritma Genetik Algoritma Genetika adalah algoritma yang memanfaatkan
proses seleksi alamiah yang dikenal dengan proses evolusi. Dalam proses evolusi, individu secara terus-menerus mengalami perubahan gen untuk menyesuaikan dengan lingkungan hidupnya. Hanya individu-individu yang kuat yang mampu bertahan. Proses seleksi alamiah ini melibatkan perubahan gen yang terjadi pada individu melalui proses perkembangbiakan. Dalam algoritma genetika ini, proses perkembang-biakan ini menjadi proses dasar yang menjadi perhatian utama, dengan dasar berpikir bagaimana mendapatkan keturunan yang lebih baik. Algoritma genetika ini ditemukan oleh
13
John Holland dan dikembangkan oleh muridnya David Goldberg. (Basuki, 2003) Hal-Hal Yang Harus Dilakukan Dalam Menggunakan Algoritma Genetika adalah: 1. Mendefinisikan individu, dimana individu menyatakan salah satu solusi (penyelesaian) yang mungkin dari permasalahan yang diangkat. 2. Mendefinisikan nilai fitness, yang merupakan ukuran baiktidaknya sebuah individu atau baik-tidaknya solusi yang didapatkan. 3. Menentukan proses pembangkitan populasi awal. Hal ini biasanya dilakukan dengan menggunakan pembangkitan acak seperti random-walk. 4. Menentukan proses seleksi yang akan digunakan. Menentukan proses perkawinan silang (cross-over) dan mutasi gen yang akan digunakan. Beberapa Definisi Penting Dalam Algoritma Genetika 1. Genotype (Gen), sebuah nilai yang menyatakan satuan dasar yang membentuk suatu arti tertentu dalam satu kesatuan gen yang dinamakan kromosom. Dalam algoritma genetika, gen ini bisa berupa nilai biner, float, integer maupun karakter, atau kombinatorial. 2. Allele, nilai dari gen. 3. Kromosom, gabungan gen-gen yang membentuk nilai tertentu.
14
4. Individu,
menyatakan
menyatakan
salah
satu
satu
nilai
solusi
atau
keadaan
yang
yang
mungkin
dari
permasalahan yang diangkat. 5. Populasi, merupakan sekumpulan individu yang akan diproses bersama dalam satu siklus proses evolusi. Generasi, menyatakan satu-satuan siklus proses evolusi. 6. Nilai Fitness, menyatakan seberapa baik nilai dari suatu individu atau solusi yang didapatkan.
2.3.1 Struktur Umum Algoritma Genetik Algoritma genetik memberikan suatu pilihan bagi penentuan nilai parameter dengan meniru cara reproduksi genetik, pembentukan kromosom baru serta seleksi alami seperti yang terjadi pada makhluk hidup. Algoritma Genetik secara umum dapat diilustrasikan dalam diagram alir berikut ini: (Sempena, 2010)
15
Gambar 2.1 Siklus Algoritma Genetik
Golberg (1989) mengemukakan bahwa algoritma genetik mempunyai karakteristik-karakteristik yang perlu diketahui sehingga dapat terbedakan dari prosedur pencarian atau optimasi yang lain, yaitu: 1. Algoritma genetik dengan pengkodean dari himpunan solusi permasalahan berdasarkan parameter yang telah ditetapkan dean bukan parameter itu sendiri. 2. Algoritma genetik pencarian pada sebuah solusi dari sejumlah individuindividu yang merupakan solusi permasalahan bukan hanya dari sebuah individu.
16
3. Algoritma genetik informasi fungsi objektif (fitness), sebagai cara untuk mengevaluasi individu yang mempunyai solusi terbaik, bukan turunan dari suatu fungsi. 4. Algoritma
genetik
menggunakan
aturan-aturan
transisi
peluang, bukan aturan-aturan deterministik. Variabel dan parameter yang digunakan pada algoritma genetik adalah: 1. Fungsi fitness (fungsi tujuan) yang dimiliki oleh masingmasing individu untuk menentukan tingkat kesesuaian individu tersebut dengan kriteria yang ingin dicapai. 2.
Populasi jumlah individu yang dilibatkan pada setiap generasi.
3. Probabilitas terjadinya persilangan (crossover) pada suatu generasi. 4. Probabilitas terjadinya mutasi pada setiap individu. 5. Jumlah generasi yang akan dibentuk yang menentukan lama penerapan algoritma genetik. Secara umum struktur dari suatu algoritma genetik dapat mendefenisikan dengan langkah-langkah sebagai berikut: 1. Membangkitkan
populasi
awal,
populasi
awal
ini
dibangkitkan secara random sehingga didapatkan solusi awal. Populasi itu sendiri terdiri atas sejumlah kromosom yang merepresentasikan solusi yang diinginkan. 2. Membentuk generasi baru, untuk membentuk generasi baru, digunakan operator reproduksi/ seleksi, crossover dan mutasi. Proses ini dilakukan berulang-ulang sehingga didapatkan
17
jumlah kromosom yang cukup untuk membentuk generasi baru dimana generasi baru ini merupakan representasi dari solusi baru. Generasi baru ini dikenal denga istilah anak (offspring). 3. Evaluasi solusi, pada tiap generasi, kromosom akan melalui proses evaluasi dengan menggunakan alat ukur yang dinamakan
fitness.
Nilai
fitness
suatu
kromosom
menggambarkan kualitas kromosom dalam populasi tersebut. Proses ini akan mengevaluasi setiap populasi dengan menghitung
nilai
fitness
setiap
kromosom
dan
mengevaluasinya sampai terpenuhi kriteria berhenti. Bila kriteria berhenti belum terpenuhi maka akan dibentuk lagi generasi baru dengan mengulangi langkah 2. Beberapa kriteria berhenti sering digunakan antara lain: berhenti pada generasi tertentu, berhenti setelah dalam beberapa generasi berturutturut didapatkan nilai fitness tertinggi tidak.
2.4
Pemodelan Algoritma Genetik Penjadwalan
yang
akan
diimplementasikan
memakai
algoritma genetik dibatasi sebagai berikut : tiap job diproses oleh sebuah mesin maksimal satu kali, tidak memiliki tenggat waktu penyelesaian, waktu perpindahan antar mesin dan waktu set up dapat diabaikan, dan penjadwalan bersifat non-preemptive. Ada empat hal dasar yang perlu diperhatikan, yaitu pemilihan representasi masalah ke bentuk string, operator genetik, fungsi fitness, dan parameter genetik (Saputro dan Yento, 2004).
18
2.4.1
Pemilihan Operator Genetik Operator genetik yang dipakai adalah operator reproduksi
gabungan dari elitism dan roulette wheel selection, operator Precedence Preservative Crossover (PPX) (Bierwirth, 1999) dan operator mutasi remove and insert (Manderick, 1991). Metode elitism membuat sejumlah string terbaik tiap generasi akan otomatis diturunkan ke generasi berikutnya Koza, 2001). Metode roulette wheel untuk memilih string-string yang akan dilakukan proses rekombinasi (Saputro, 2003). Pada PPX, string baru disusun secara acak dari allele stringstring induk. Angka acak 1 atau 2 dipakai untuk memilih induk. Jika 1 diturunkan allele paling kiri dari induk pertama, jika 2 diturunkan allele paling kiri dari induk kedua. Selanjutnya allele yang terpilih tadi dihapus dari kedua induk. Proses dilakukan sampai karakter di kedua induk habis. Sebagai contoh 2 induk ABCDEF dan CABFDE, dan angka acak 1 2 1 1 2 2, akan menghasilkan string baru ACBDFE. Pada mutasi, satu locus dipilih secara acak dan karakter diposisi tersebut di hapus. Satu locus baru dipilih, dan karakter yang telah dihapus tadi disisipkan. Gambar 2.2 menunjukkan proses mutasi pada locus ketiga dan ketujuh.
Gambar 2.2 String A dan Hasil Mutasi
19
2.4.2
Fungsi Fitness Pada dynamic scheduling dengan kedatangan job tidak dapat
diperkirakan sebelumnya, minimalisasi makespan dirasakan kurang berarti (Lin, 1997). Oleh karena itu, rata-rata waktu penyelesaian sebuah job (average flow time) pada satu periode penjadwalan digunakan sebagai fungsi fitness. Waktu selesainya sebuah job dapat dihitung dari selisih waktu tiba (ri) dengan waktu selesainya operasi terakhir dari job (Ci). Satu periode penjadwalan melibatkan operasioperasi yang belum mulai diproses mesin. Tujuan penjadwalan adalah minimasi fungsi fitness, sedangkan pada algoritma genetik, sesuai proses di alam, prosesnya adalah maksimasi. Oleh karena itu, fungsi fitness penjadwalan diubah menjadi 1/f. 2.4.3 Parameter Genetik Parameter Genetik berguna dalam pengendalian operatoroperator genetik. Parameter yang digunakan adalah : ukuran populasi, jumlah generasi, Probabilitas Crossover (Pc), dan Probabilitas Mutasi (Pm). Tidak ada aturan pasti tentang berapa nilai setiap parameter ini (Koza, 2001). Ukuran populasi kecil berarti hanya tersedia sedikit pilihan untuk Crossover dan sebagian kecil dari domain solusi saja yang dieksplorasi untuk setiap generasinya. Sedangkan bila terlalu besar, kinerja algoritma genetic menurun. Penelitian menunjukkan ukuran populasi besar tidak mempercepat proses pencarian solusi. Disarankan ukuran populasi berkisar antara 20-30, probabilitas Crossover berkisar 80%-95%, dan probabilitas mutasi kecil berkisar 0.5%-1%. Jumlah generasi besar
20
berarti semakin banyak iterasi yang dilakukan, dan semakin besar domain solusi yang akan dieksplorasi. 2.4.4
Pemodelan Penjadwalan Pemodelan penjadwalan yang dimaksud adalah proses
penyusunan jadwal dari string. Permutasi operasi-operasi yang direpresentasikan oleh string akan di-decode untuk menghasilkan jadwal. Ada tiga karakteristik jadwal yang dapat dihasilkan, yaitu semiactive, active, dan non delay (Bierwirth, 1999). Makalah ini memakai jadwal hybrid yaitu gabungan antara jadwal active dan non delay. Notasi-notasi yang dipakai pada jadwal hybrid maupun proses kerja penjadwalan job shop dengan algoritma genetik dapat dilihat pada gambar 2.3
Gambar 2.3 Notasi
Langkah-langkah prosedur hybrid (Bierwirth, 1999) : 1. Buat himpunan operasi yang mengawali pekerjaan: A={oi1 | 1 £ i £ n}.
21
2. Pilih o1, operasi dengan waktu selesai tercepat, t1 + p1 £ tik + pik untuk semua oikÎA. Jika lebih dari satu operasi, pilih operasi yang terletak paling kiri di string. 3. Jika M1 adalah mesin yang dipakai oleh o1, buat himpunan B yang berisi semua operasi dari A yang diproses di M1, B:={oikÎA|mi(k)=M1} 4. Pilih o11, operasi dengan waktu mulai paling awal di B, t11
t*ik-1+p*ik-1
waktu
selesai
operasi
ke-(k-1),
yaituoperasi sebelumnya dari job ke-i dan ohl=operasi ke-l dari job ke-h yang mendahuluio*ik pada mesin yang sama. 8. Jika terdapat suksesor dari o*ik, yaitu o*i,k+1, tambahkan ke A. 9. Ulangi langkah 2 sampai isi A habis.
