Penggunaan aljabar max-plus dalam penjadwalan flow shop

Abstract

Misalkan sebuah proyek terdiri atas beberapa pekerjaan dan dua mesin, di mana setiap pekerjaan harus diproses di mesin pertama dahulu, baru kemudian diproses di mesin kedua. Dalam setiap saat, setiap mesin hanya dapat memproses satu pekerjaan saja. Bagaimana cara menentukan urutan pemrosesan pekerjaan-pekerjaan tersebut supaya total durasi penyelesaian proyek tersebut mencapai minimum? Masalah ini disebut masalah flow shop dengan dua mesin. Dalam skripsi ini, dieksplorasi penggunaan aljabar max-plus dalam menyelesaikan masalah flow shop, pertama-tama dengan dua mesin, dan selanjutnya dengan tiga atau lebih mesin. Penyelesaian masalah tersebut akan dilakukan dengan menggunakan algoritma penjadwalan yang dibahas secara analitik dan kemudian diimplementasikan pada komputer, dengan menggunakan bahasa pemrograman Python. Waktu eksekusi dari algoritma-algoritma tersebut dibandingkan dengan waktu eksekusi dari algoritma trial and error, yaitu algoritma yang menentukan urutan optimal dengan memeriksa semua kemungkinan urutan pekerjaan. Jika pekerjaan-pekerjaan yang ada cukup sedikit, maka waktu eksekusi algoritma trial and error sedikit lebih singkat dibandingkan waktu eksekusi algoritma penjadwalan. Tetapi jika pekerjaan-pekerjaan yang ada cukup banyak, maka waktu eksekusi algoritma trial and error meningkat menjadi jauh lebih lama, sedangkan waktu eksekusi algoritma penjadwalan tidak mengalami peningkatan yang signifikan.