Penetuan Titik Awal Penyelesaian Quadratic Assignment Problem

Abstract

Quadratic Assignment Problem (QAP) merupakan problema kombinatorial, dalam menentukan penempatan fasilitas di lokasi tertentu sedemikian sehingga meminimumkan fungsi objektif yang dinyatakan dengan jarak antara lokasi dan flow antara fasilitas. Pertama sekali dilakukan pendekatan heuristic sederhana untuk mendapatkan titik awal penugasan. Metode Heuristik Tabu Search digunakan untuk mendapatkan titik awal penugasan yang lain yang akan digunakan untuk titik awal pendekatan Nonlinier Programing. Selanjutnya problems Nonlinier Programing di proses menggunakan metode heuristik yang lain untuk mendapatkan penyelesaian layak bulat dari Quadratic Assignment Problem. Sifat tidak konveks dari problema mengakibatkan diperlukannya suatu titik awal yang baik agar dapat diperoleh penyelesaian optimal global. Prosedur ini diterapkan kepada problems Backboard Wiring dengan dimensi 12 x 12, 15 x 15 dan 20 x 20.