Penerapan Algoritma Kuhn-Munkres dalam Penyelesaian Masalah Penugasan Multi-objective pada Industri Konveksi Tas DP. SPORTY
Article Sidebar
Main Article Content
Abstract
Pada penelitian ini, diberikan suatu prosedur untuk menyelesaikan masalah penugasan multi-objective (MOAP) dengan menggunakan Algoritma Kuhn-Munkres. Algoritma Kuhn-Munkres hanya dapat diterapkan pada kasus masalah penugasan sederhana (single-objective), sedangkan pada masalah penugasan multi-objective membutuhkan optimasi secara serempak dari beberapa tujuan pengoptimalan (biaya, waktu, dan kualitas). Untuk menyelesaikan masalah tersebut, dilakukan transformasi fungsi tujuan multi-objective ke dalam bentuk single-objective dengan menggunakan pendekatan vektor bobot. Kemudian, prosedur yang diusulkan diilustrasikan dengan studi kasus masalah penugasan pada industri konveksi tas DP. Sporty. Hasil penerapan metode pada data studi kasus diperoleh solusi masalah penugasan berupa pasangan pekerja dan tugas dengan total pemanfaatan sumber daya yang optimal secara bersamaan. Selain menggunakan Algoritma Kuhn-Munkres, dilakukan pencarian pasangan penugasan optimal menggunakan Solver. Hasil perhitungan dengan Solver memberikan pasangan penugasan yang sama dengan hasil perhitungan dengan Algoritma Kuhn-Munkres.
Article Details
References
Belhoul, L., Galand, L., & Vanderpooten, D. 2014. An Efficient Procedure for Finding Best Compromise Solutions to the Multi-Objective Assignment Problem. In Computers & Operations Research. Elsevier.
Bondy, J.A. & Murty, U. S. 1976. Graph Theory with Applications. New York: Elsevier Science Publishing Co., Inc.
Chartrand, G. & Oellermann, O. R. 1993. Applied and Algorithmic Graph Theory. New York: Mc Graw Hill, Inc.
Deb K., Pratap, A., Agarwal, S., & Meyarivan, T. 2002. A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II. Journal of IEEE Transactions on Evolutionary Computation, 6(2): 182-97.
Garrett, J.D., Vannucci, J., Silva, R., Dasgupta, D., & Simien, J. 2007. Applying Hybrid Multiobjective Evolutionary Algorithms to the Sailor Assignment Problem. In Advances in Evolutionary Computing for System Design. Springer Verlag.
Geetha, S. & Nair, K. P. K. 1993. A Variation of the Assignment Problem. European Journal of Operational Research, 68(3): 422-426.
Hillier, S. F. & Lieberman, J. G. 2008. Introduction To Operations Research (9th ed.). New York: Mc Graw-Hill, Inc.
Knowles, J.D. & Corne, D.W. 2000. Approximating the Nondominated Front Using the Pareto Archived Evolution Strategy. Journal of Evolutionary Computation, 8(2): 149–72.
Kuhn, H.W. 1955. The Hungarian Method for the Assignment Problem. Journal of Naval Research Logistics Quarterly, 2: 83-97.
Mills-Tettey, G. A., Stentz, A., & Dias, M. B. 2007. The Dynamic Hungarian Algorithm for the Assignment Problem with Changing Cost. Pittsburgh: Carnegie Mellon University.
Munkres, J. 1957. Algorithms for the Assignment and Transportation Problems. Journal of the Society for Industrial and Applied Mathematics, 5(1): 32-38.
Przybylski, A., Gandibleux, X., & Ehrgott, M. 2009. Computational Results for Four Exact Methods to Solve the Three-Objective Assignment Problem. In Lecture Notes in Economics and Mathematical Systems, 618: 79-88. Edited by V. Barichard, M. Ehrgott, X. Gandibleux, & V. T’Kindt. Berlin: Springer Verlag.
Przybylski, A., Gandibleux, X., & Ehrgott, M. 2010. A Two Phase Method for Multi-Objective Integer Programming and Its Application to the Assignment Problem with Three Objectives. Journal of Discrete Optimization, 7: 149-165.
Yen, G.G. & Lu, H. 2003. Dynamic Multiobjective Evolutionary Algorithm: Adaptive Cell-Based Rank and Density Estimation. Journal of IEEE Transactions on Evolutionary Computation, 7(3): 253–74.