Perancangan dan Analisis Algoritma Greedy: Studi Kasus SPOJ 389 Use of Hospital Facilities

Syambudi, Moh Adib (2025) Perancangan dan Analisis Algoritma Greedy: Studi Kasus SPOJ 389 Use of Hospital Facilities. Other thesis, Institut Teknologi Sepuluh Nopember.

Text 5025211017-Undergraduate_Thesis.pdf - Accepted Version Restricted to Repository staff only Download (6MB) | Request a copy

Abstract

Sphere Online Judge (SPOJ) merupakan platform penilaian daring yang menyediakan berbagai permasalahan algoritma pemrograman dan mendukung lebih dari 45 bahasa pemrograman.Salah satu permasalahan yang terdapat di platform ini adalah Use of Hospital Facilities (ID: 389), yang dikembangkan oleh Adrian Kuegel dan termasuk dalam kategori classical problem dengan tingkat penyelesaian sebesar 15.24%. Permasalahan ini menuntut pemahaman mendalam terkait penjadwalan dengan dua kendala utama, yaitu keterbatasan kapasitas sumber daya dan aturan pengerjaan tugas. Skripsi ini membahas penyelesaian permasalahan tersebut menggunakan pendekatan algoritma greedy,berdasarkan pada karakteristik greedy choice property dan optimal substructure. Algoritma yang dikembangkan memilih ruang operasi dan pemulihan berdasarkan urutan ketersediaan terkini secara deterministik. Evaluasi dilakukan melalui dua skenario, yakni pengujian lokal dan pengujian eksternal melalui situs SPOJ. Pengujian lokal dilakukan terhadap lima variasi jumlah pasien (100 hingga 500) dan lima kali pengulangan untuk setiap kasus, guna mengevaluasi waktu
eksekusi dan penggunaan memori. Hasil pengujian menunjukkan bahwa solusi algoritma greedy mampu menyelesaikan permasalahan dengan waktu eksekusi rata-rata sebesar 0,01
detik dan penggunaan memori sebesar 5,2 MB. Kompleksitas algoritma dalam kasus terburuk adalah O(n² log n), dengan kompleksitas rata-rata O(n²).

=========================================================================================================================================

Sphere Online Judge (SPOJ) is an online evaluation platform that provides a wide range of programming algorithm problems and supports more than 45 programming languages. One of the problems featured on this platform is Use of Hospital Facilities (ID: 389), developed by Adrian Kuegel. It falls under the classical problem category with a completion rate of 15.24%. This problem requires a deep understanding of scheduling, particularly in handling two main constraints: limited resource capacity and task execution rules. This thesis addresses the problem using a greedy algorithm approach, based on the characteristics of the greedy choice
property and optimal substructure. The developed algorithm selects operating and recovery rooms based on the earliest available order in a deterministic manner. Evaluation was carried out through two scenarios: local testing and external testing via the SPOJ platform. The local tests were conducted with five variations in the number of patients (ranging from 100 to 500), each repeated five times to evaluate execution time and memory usage. The test results show that the greedy algorithm is capable of solving the problem with an average execution time of 0.01 seconds and memory usage of 5.2 MB. The algorithm has a worst-case time complexity of O(n² log n), with an average complexity of O(n²).

Item Type:	Thesis (Other)
Uncontrolled Keywords:	Algoritma Greedy, Kompleksitas, SPOJ, Greedy, Complexity, SPOJ
Subjects:	Q Science Q Science > Q Science (General) Q Science > Q Science (General) > Q325 GMDH algorithms.
Divisions:	Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering > 55201-(S1) Undergraduate Thesis
Depositing User:	Moh Adib Syambudi
Date Deposited:	31 Jul 2025 03:15
Last Modified:	31 Jul 2025 03:15
URI:	http://repository.its.ac.id/id/eprint/124631

Actions (login required)

View Item