Penyelesaian Masalah Penempatan Fasilitas dengan Algoritma Estimasi Distribusi dan Particle Swarm Optimization
Abstract
Abstrak—Masalah penempatan fasilitas pada garis lurus dikenal sebagai problem Penempatan Fasilitas pada Satu Baris (PFSB). Tujuan PFSB, yang dikategorikan sebagai masalah NP-Complete, adalah untuk mengatur tata letak sehingga jumlah jarak antara pasangan semua fasilitas bisa diminimalisir. Algoritma Estimasi Distribusi (EDA) meningkatkan kualitas solusi secara efisien dalam beberapa pengoperasian pertama, namun keragaman dalam solusi hilang secara pesat ketika semakin banyak iterasi dijalankan. Untuk menjaga keragaman, hibridisasi dengan algoritma meta-heuristik diperlukan. Penelitian ini mengusulkan EDAPSO, algoritma yang terdiri dari hibridisasi EDA dan Particle Swarm Optimization (PSO). Tujuan dari penelitian ini yaitu untuk menguji performa algoritma EDAPSO dalam menyelesaikan PFSB.Kinerja EDAPSO yang diuji dalam 10 masalah benchmark PFSB dan EDAPSO berhasil mencapai solusi optimal.
Kata kunci—penempatan fasilitas, algoritma estimasi distribusi, particle swarm optimization
Abstract—The layout positioning problem of facilities on a straight line is known as Single Row Facility Layout Problem (PFSB). Categorized as NP-Complete problem, PFSB aim to arrange the layout so that the sum of distances between all facilities’ pairs can be minimized. Estimation of Distribution Algorithm (EDA) improves the solution quality efficiently in first few runs, but the diversity lost grows rapidly as more iterations are run. To maintain the diversity, hybridization with meta-heuristic algorithms is needed. This research proposes EDAPSO, an algorithm which consists of hybridization of EDA and Particle Swarm Optimization (PSO). The objective of this research is to test the performance of EDAPSO algorithm for solving PFSB. EDAPSO’s performance is tested in 10 benchmark problems of PFSB and it successfully achieves optimum solution.
Keywords— facility layout, estimation distribution algorithm, particle swarm optimization
Keywords
Full Text:
PDFReferences
Amaral, A. R. (2006). On the exact solution of a facility layout problem. European Journal of Operational Research , 173 (2), 508–518.
Chen, Y. M., Chen, M. C., Chang, P. C., & Chen, S. H. (2012). Extended artificial chromosomes genetic algorithm for permutation flowshop scheduling problems. Computers & Industrial Engineering , 62 (2), 536-545.
Datta, D., Amaral, A. R., & Figueira, J. (2011). Single row facility layout problem using a permutation-based genetic algorithm. European Journal of Operational Research , 213 (2), 388-394.
Haupt, R. L., & Haupt, S. E. (2004). Practical Genetic Algorithms. Ney Jersey: John Wiley & Sons.
Hauschild, M., & Pelikan, M. (2011). An introduction and survey of estimation of distribution algorithms. Swarm and Evolutionary Computation , 1 (3), 111-128.
Heragu, S. S., & Kusiak, A. (1991). Efficient models for the facility layout problems. European Journal of Operational Research , 53 (1), 1–13.
Hu, X., Eberhart, R. C., & Shi, Y. (2003). Swarm intelligence for permutation optimization: a case study of n-queens problem. IEEE swarm intelligence symposium (hal. 243–246). Indianapolis: IEEE.
Samarghandi, H., & Eshghi, K. (2010). An efficient tabu algorithm for the single row facility layout problem. European Journal of Operational Research , 205 (1), 98-105.
Samarghandi, H., Taabayan, P., & Jahantigh. (2010). A particle swarm optimization for the single row facility layout problem. Computers and Industrial Engineering , 58 (4), 529-534.
Zhang, Q., & Muehlenbein, H. (2004). On the Convergence of a Class of Estimation of Distribution Algorithms. IEEE Trans. on Evolutionary Computation , 8 (2), 127-136.
Refbacks
- There are currently no refbacks.
Copyright (c) 2016 Amalia Utamima, Angelia Melani Andrian
This work is licensed under a Creative Commons Attribution 4.0 International License.
Journal of Information Systems Engineering and Business Intelligence (e-ISSN 2443-2555)
JISEBI is licensed under a Creative Commons Attribution 4.0 International License.
Indexed in DOAJ ,Google Scholar , Indonesian Scientific Journal Database, Portal Garuda IPI, BASE, Indonesia OneSearch and Microsoft Academic