Hyperheuristic berbasis particle swarm optimization untuk permasalahan penjadwalan job shop

Abstract

Skripsi ini menyelesaikan pengurutan job shop scheduling problem dengan menggunakan algoritma Particle Swarm Optimization based Hyperheuristic. Job shop scheduling problem adalah masalah optimasi di mana job diproses oleh sumber daya pada waktu-waktu tertentu. Urutan pengerjaan job pada penjadwalan job shop di setiap mesin dapat berbeda-beda. Banyak metode yang dapat digunakan dalam menyelesaikan penjadwalan job shop, salah satunya adalah dengan menggunakan priority dispatch rule. Priority dispatch rule dapat digunakan sebagai low-level heuristic atau yang biasa disebut heuristic. Heuristic adalah pendekatan untuk pemecahan masalah yang menggunakan metode yang memenuhi tujuan tapi tidak dijamin optimal atau sempurna. Hyperheuristic adalah heuristic yang memilih atau menghasilkan heuristic. Hyperheuristic menggunakan low-level heuristic dengan memilih low-level heuristic mana yang harus dipertimbangkan dan diterapkan. Hyperheuristic bertujuan menemukan metode yang tepat dalam situasi tertentu. Maka dari itu, hyperheuristic tidak memecahkan masalah secara langsung. Pada Particle Swarm Optimization based Hyperheuristic, partikel dari Particle Swarm Optimization akan menyimpan sejumlah low-level heuristic sebagai lokasi yang multi-dimensi.

Tujuan skripsi ini adalah membuat perangkat lunak yang dapat membantu menghasilkan jadwal yang lebih efisien atau jadwal yang memiliki makespan terkecil. Makespan adalah total waktu yang dibutuhkan untuk menyelesaikan seluruh job. Perangkat lunak yang dibangun tersebut memiliki input berupa file bertipe ’.txt’ berisi informasi dari job. Output dari perangkat lunak tersebut adalah jadwal tercepat yang didapat setelah melakukan sejumlah iterasi. Solusi dari Particle Swarm Optimization ini berupa himpunan dari beberapa bilangan bulat yang menandakan low-level heuristic yang akan digunakan untuk mengurutkan job di setiap mesin. Priority dispatch rule yang digunakan sebagai low-level heuristic pada skripsi ini adalah first come first served, last in first out, shortest processing time, longest processing time, earliest due date, latest due date, dan random.

Pengujian skripsi ini dilakukan terhadap 6 kasus permasalahan. Data yang digunakan adalah 3 kasus permasalahan sederhana dan Taillard Benchmark. Taillard benchmark adalah masalah yang belum terpecahkan dengan ukurannya sesuai dengan masalah industri yang dirancang Taillard untuk mengevaluasimetode yang sudah ada. Kasus permasalahan sederhana tersebut adalah 2 job 2 mesin, 3 job 4 mesin, dan 4 job 3 mesin. Taillard benchmark yang digunakan adalah 10 instansi dari kasus permasalahan 15 job 15 mesin. Solusi yang diperoleh dari 3 kasus permasalahan sederhana setelah beberapa iterasi adalah 15, 15, dan 20. Sedangkan dari pengujian Taillard benchmark dapat disimpulkan bahwa semakin besar permasalahan yang diuji, semakin kecil kemungkinan mendapat solusi yang optimal.