Nama : Arifiyanto Hadinegoro
Nim :
115301619
Problem scheduling whit
genetic algorithm
Genetic algorithm ( GA ) merupakan salah satu dari evolutionary computation yang paleng sederhana yang pertama kali di usulkan oleh hon Holland pada era 1975 di amerika Genetic Algorithm memiliki bentuk yang sederhana sehingga di sebut simple GA ( SGA). Pada beberapa buku dan makalah, SGA sering juga di sebut sebagai classical GA atau Caninical GA. Pada umumnya SGA di gunakan untuk menyelesaikan masalah optimasi diskrit. Salah satu ciri utama dari SGA adalah tidak terlalu cepat dalam menemuan solusi optimal, tetapi memiliki heuristic yang baik untuk masalah kombinatorial, ciri lainnya adalah SGA menitik beratkan pada rekombinasi atau crossover, yang berarti bagian SGA yang paling penting untuk menemukan adalalh seolusi rekombinasi.
Dari pengertian tentang SGA di atas dapat disimpulkan SGA bisa di implementasi kan untuk kasus kasus yang cuup sederhana dan membutuhkan waktu yang cepat untuk menghasilkan optimasi atau solusi terbaik. Salah satu kasus yang bisa menggunkan SGA adalah penjadwalan atau scheduling problem
Aplikasi GA bebrbasiskan system fleksibel yagn di muali dari populasi awal yang di peroleh dengan menggunakan standar aturan sequencing bersama dengan beberapa kromosom acak. Setiap kromosom di evaluasi dengan menghitung nilai dari make-spannya, nilai ini di gunakan untuk menghitung nilai fitness, untuk memulai menghitung untuk generasi berikutnya. Kromosom dengan yang terbaik nilai fitness langsugn di tempatkan pada populasi baru. Langkaha ini disebut elitisme dan mencegah hilangnya solusi tebaik karena teknik evoslusi, sisa kromosom yang lain di pilih atas dasar seleksi dari roda roulette, kemudian angka acak dihasilkan dan kromosom yang sesuai dengan di mana jatuhnya nomor acak. Pemilihan adalah waktu untuk menerapkan operator crossover dan mutasi pada penduduk menengah.setelah operasi ini lengkap, populasi siap untuk dievaluasi lagi. Proses ini berulang sampai iterasi tertentu.
Masalah umum yang menjadi ide dari scheduling problem adalah untuk alokasi sumber daya, alokasi waktu, masalah masalah yang ada saat pemecahan masalah dan optimasi pada skedull atau jadwal yang akan di buat.
Constrain
dari sebuah problem scheduling adalah :
·
Setiap mesin
hanya dapat memproses satu pekerjaan pada satu waktu
·
Setipa
pekerjaan hanya dapat diproses oleh satu mesin setiap saat
·
Setelah mesin
telha melalui proses pekerjaan , akan terus berjalan pada sampai pekerjaan
terselesaikan
Dari
constrain atau batasan yang ada maka bisa dibagi lagi masalah yang ada yaitu:
·
Single-machine
problems
·
Multi-machine
problems
·
Single-stage
problems
·
Multi-stage
problems
Dari
klasifikasi di atas ada beberpa klasifikasi lagi untuk multi machine dan multi
stage dan multi machine
●
Parallel Machine Problems
·
Identical
parallel machine problems
·
Uniform
parallel machine problems
·
Unrelated
parallel machine problems
·
Multi stage
·
Flow Shop
Problems
·
Open Shop
Problems
·
Job Shop
Problems
·
Group Shop
Environment
Salah satu contoh kasus yang tentang problem scheduling menggunakan genetic “A Genetic Algorithm Based Scheduling for a Flexible System” di tulis oleh S. Wadhwa, J. Madaan and R. Raina. Menjelaskan tentang penggunaan GA pada flexible system.
Fleksibel system sendiri adalah system yang mengakomodasi varian output yang lebih besar, tidak hanya respon perusahaan untuk ketidak pastian. Bentuk fluktuasi permintaan dan juga ketidak sempurnaan pasar. Carlsson (1989), Wadhwa dan Rao(2000) meilhat sistem yang fleksibel sebagai sistem yang memilii kemampuan utnuk menghadap peruhbahan dengan untuk penyediaan dan pemanfaatan opsi yang dikontrol secara dinamis. Dan dalam contoh kasus ini untuk mencari pendekatan yang sama untuk menunukan aplikasi GA dapat membantu meningkatkan kenera sistem fleksibel .
Aplikasi model GA yang berbasis sistem fleskibel di muli dengan populasi awa yang di peroleh dengan penggunaan standar aturan urutan dengan beberapa kromosom acak, setiap kromosom ini kemudian di evaluasi dengan menghitung nilai dari nilai rentang yang digunakan untuk menghitung nilai fitness setiap kromosom. Nilai fitness ini berbanding terbalik dengan nilai rentang. Berdasarkan nilai fitness, dimulai proses seleskai untuk generasi berikutnya. Kromosom dengan nilai fitness terbaik akan secaralangsung di tempatkan pada populasi terbaru. Langkah ini di sebut elitism dan mencegah hilanggnya solusi terbaik karena tenik evolusi. Kromosom berikutnya di pilih atas daasar seleksi roulette wheel, setiap kromosom di berikan bagian dari roda rolet berdasarkan nilai kebugaran. Kemudain angka acak yang di hasilkan dan kromosom yang sesuai dengan wilayah di mana jatuh nomor acak yang terpilih. Setelah pemilihan,adalah waktu unutk menerapkan operator crossover dan mutasi pada populasi menengah, setelah operasi ini lengkap, populasi baru siap di evaluasi lag, dan proses ini berulang sampai jumlah tertentu dari iterasi.
Model
matetmatika untuk menghitung nilai rentang adalah sebagai berikut :
. Let(
) menjadi permutasi,
perhitungan selesai C (
)
untuk ith pekerjaan dari permutasi di berikan Ő dan j untuk mesin
dapat dibuat sebagai berikut:
) menjadi permutasi,
perhitungan selesai C ()
untuk ith pekerjaan dari permutasi di berikan Ő dan j untuk mesin
dapat dibuat sebagai berikut: 
GA
Bases Arsitektur bahasa
Arsitektur GA secara keseluruhan untuk optimasasi berbasiskan Flow-shop scheduler model telah di kembangkan seperti pada gambar 1, telah di rancang dengan menggunakan pendekatan modular, modul modul utama yang di identifikasi adalah scheduler model, yang menyediakan populasi input dasar dan fungsi fitness untuk masalah tertentu yang eksstraktor, GA modul yagn mengimplementasikan beberapa teknik Seleksi, crossover dan mutasi ke data dan modul checker yang akan memeriksa apakah hasilnya telah optimaljika solusi optimal maka akan di kirim sebagai output yang lain akan di proses di changer modul untuk menghasilkan populasi baru.
 |
| Gambar 1 Arsitektur GA dan Detail Applied to scheduler model |