Pengembangan algoritma Nawaz Enscore Ham untuk Permutation Flowshop Problem

Abstract

Permutation Flowshop Scheduling Problem (PFSP) adalah masalah penjadwalan yang terjadi pada aliran produksi yang memiliki urutan mesin yang sama untuk setiap pekerjaan. PFSP sendiri termasuk ke dalam NP-Hard (Non-deterministic Polynomial-time Hardness) sehingga diperlukan metode heuristik untuk melakukan penyelesaiannya. Terdapat beberapa metode heuristik yang dapat digunakan dalam menyelesaikan PFSP dengan ukuran performansi minimasi makespan. Metode heuristik untuk meminimasi makespan yang dapat digunakan dalam menyelesaikan PFSP adalah algoritma Palmer, Campbell Dudek Smith (CDS), Rapid Access (RA), Nawaz Enscore Ham (NEH), dan Gupta Chauhan. Dari metode-metode tersebut, algoritma NEH merupakan algoritma terbaik dalam menyelesaikan PFSP. Sehingga banyak penelitian yang dilakukan untuk meningkatkan performansi dari algoritma NEH. Pada penelitian ini, akan dilakukan pengembangan algoritma baru untuk menyelesaikan PFSP. Algortima baru yang akan dikembangkan ini berbasiskan algoritma NEH dan mengubah priority rule serta tie-breaking rule-nya. Hal ini dilakukan untuk meningkatkan performansi yang dapat dihasilkan oleh algoritma NEH. Di penelitian ini, priority rule dari algoritma NEH akan diganti menggunakan algoritma Gupta Chauhan karena algoritma ini dapat memberikan urutan awal untuk algoritma lain dan tie-breaking rule-nya akan diganti menggunakan tie-breaking rule dari NEHFF karena algoritma ini memiliki performansi yang paling baik untuk tie-breaking rule. Algoritma baru ini diimplementasikan ke dalam 12 kasus yang terdiri dari 10 problem instance. Pada penelitian ini juga dilakukan perbandingan performasi yang dihasilkan oleh algortima baru dengan algoritma pembanding yaitu algoritma Gupta Chauhan, Palmer, CDS, RA, NEH, dan NEHFF. Hasil implementasi menunjukan bahwa algoritma baru dapat memberikan performansi yang lebih baik dari algoritma Gupta Chauhan, Palmer, CDS, dan RA. Akan tetapi, algortima baru memberikan performansi yang lebih rendah dari NEH dan NEHFF pada kasus ke-9, ke-11, dan ke-12. Sedangkan pada kasus lainnya untuk beberapa problem instance, hasil dari algortima baru sama atau lebih baik dari NEH dan NEHFF.