Abstrak
Desain jaringan merupakan salah satu bidang yang banyak terapannya dalam optimisasi kombinatorik. Masalah Instalasi Jaringan Multi Tahap atau Multiperiod Degree Constrained Minimum Spanning Tree (MPDCMST) merupakan salah satu masalah desain jaringan dimana akan ditentukan biaya minimum untuk menghubungkan titik-titik yang dipertimbangkan pada tahap-tahap tertentu, dan tidak melanggar syarat atau kendala yang diberikan . Kendala yang diberikan adalah interkoneksi pada tiap titik tidak melebihi b, b= integer nonnegatif. Selain itu, ada skala prioritas titik-titik yang harus terhubung pada tahap tahap tertentu. Pada penelitian ini akan didiskusikan proses instalasi/koneksi tiap titik pada masing-masing tahap yang menggunakan Modifikasi Algoritma Prim untuk menyelesaikannya. Ada dua algoritma (WWM1 dan WWM2) yang akan dibandingkan proses instalasinya. Hasil penelitian menunjukkan bahwa algoritma WWM2 memberikan solusi yang lebih baik dari algoritma WWM1.
Author Biographies
Wamiliana Wamiliana, Universitas Lampung
Jurusan MatematikaWarsono Warsono, Universitas Lampung
Jurusan MatematikaMas Dafri Maulana, Universitas Lampung
Jurusan Matematika
References
[1] Kruskal, J.B. On the Shortest Spanning Tree of a Graph and the Travelling Salesman Problem, Proc. Amer. Math. Soc. , vol. 7 : p. 48-50, 1956.
[2] Prim, R.C. Shortest Connection Networks and Some Generalizations. Bell Syst. Tech Journal, vol.36 p: 1389-1401, 1957.
[3] Narula,S.C., and Cesar A.Ho, “Degree-Constrained Minimum Spanning Tree”, Computer and Operation Research. Vol. 7; pp. 239-249, 1980.
[4] Zhou, G. and Mitsuo Gen,”A Note on Genetics Algorithms for Degree- Constrained Spanning Tree Problems”, Networks, Vol. 30: p.91 – 95, 1997.
[5] Deo N. and Nishit Kumar, Computation of Constrained Spanning Trees: A Unified Approach. Network Optimization ( Lecture Notes in Economics and Mathematical Systems, Editor : Panos M. Pardalos, et al. ,Springer-Verlag, Berlin, Germany, pp. 194 – 220., 1997.
[6] Wamiliana, “ Solving the Degree Constrained Minimum Spanning Tree Using Tabu and Penalty Method”, Jurnal Teknik Industri: p.1-9, 2004.
[7] Caccetta L. and Wamiliana, Heuristics Algorithms for the Degree Constrained Minimum Spanning Tree Problems, Proceeding of the International Congress on Modelling and Simulation (MODSIM),Canberra, Editors: F. Ghassemi et.al; p. 2161-2166, 2001.
[8] Wamiliana and Caccetta, Tabu search Based Heuristics for the Degree Constrained Minimum Spanning Tree Problem, Proceeding of South East Asia Mathematical Society, p. 133-140, 2003.
[9] Wamiliana and L. Caccetta, The Modified CW1 Algorithm for The Degree Restricted Minimum Spanning Tree Problem, Proceeding of International Conference on Engineering and Technology Development, Bandarlampung 20-21 June. 2012; p. 36-39.
[10] Kawatra R. “A multi period degree constrained Minimum Spanning Tree Problem”, European Journal of Operational Research, Vol 143, pp. 53 – 63 , 2002.
[11] Wamiliana, Dwi Sakethi, and Restu Yuniarti, Computational Aspect of WADR1 and WADR2 Algorithms for The Multi Period Degree Constrained Minimum Spanning Tree Problem, Proceeding SNMAP, Bandar lampung 8 – 9 December 2010. p. 208 – 214.
[12] Wamiliana, Amanto, and Mustofa Usman, Comparative Analysis for The Multi Period Degree Constrained Minimum Spanning Tree Problem, Proceeding The International Conference on Engineering and Technology Development (ICETD), pp. 39 – 43, 2013.
[13] Wamiliana, Faiz A.M. Elfaki, Mustofa Usman, and M. Azram, “Some Greedy Based Algorithms for Multi Periods Degree Constrained Minimum Spanning Tree Problem”, ARPN Journal of Engineering and Applied Sciences, 2015; Vol. 10 (21): pp.10147 – 10152, 2015.
[14] Wamiliana, Mustofa Usman, Dwi Sakethi, Restu Yuniarti, and Ahmad Cucus, “The Hybrid of Depth First Search Technique and Kruskal’s Algorithm for Solving The Multiperiod Degree Constrained Minimum Spanning Tree Problem”, The 4th International Conference on Interactive Digital Media (ICIDM). IEEE Explore, Dec 2015.
Full PDF : https://journal.uhamka.ac.id/index.php/teknoka/article/view/751/295
This web supported by : www.uhamka.ac.id