Implementasi Algoritma Greedy dan Dynamic Programming untuk Masalah Penjadwalan Interval dengan Model Knapsack
DOI:
https://doi.org/10.22441/format.2024.v13.i2.005Abstract
Penelitian ini membahas implementasi algoritma Greedy dan Dynamic Programming untuk penjadwalan interval dengan model knapsack, yang esensial dalam optimasi. Tujuan penelitian ini adalah memberikan panduan praktis dalam memilih algoritma yang tepat untuk aplikasi dunia nyata. Metode yang digunakan mencakup algoritma Greedy, yang membuat pilihan lokal terbaik untuk mencapai solusi global optimal, dan Dynamic Programming, yang memecah masalah menjadi submasalah lebih kecil dan menyelesaikannya secara berulang. Hasil penelitian menunjukkan bahwa Dynamic Programming memberikan solusi optimal dengan penggunaan waktu dan ruang yang lebih besar dibandingkan dengan Greedy. Algoritma Greedy lebih cepat tetapi tidak selalu memberikan solusi optimal, sedangkan Dynamic Programming lebih cocok untuk masalah kecil yang membutuhkan solusi optimal. Penelitian ini menyimpulkan bahwa kedua algoritma memiliki kelebihan dan kekurangan masing-masing tergantung pada skala dan kebutuhan masalah. Penelitian ini berkontribusi dalam bidang optimasi dan penjadwalan serta membuka jalan bagi pengembangan algoritma lebih lanjut. Implementasi kedua algoritma ini membantu dalam pengambilan keputusan yang lebih baik dalam aplikasi penjadwalan interval dengan model knapsack.
Kata kunci: Algoritma Greedy, Dynamic Programming, Knapsack Problems, Interval Scheduling, Optimasi, Task Scheduling
Downloads
References
Zhou, H., Bai, G., and Deng, S. (2019). Optimal interval scheduling with nonidentical given machines. Cluster Computing, 22, 1007-1015. https://doi.org/10.1007/s10586-018-02892-z.
Yu, G., and Jacobson, S. H. (2019). Approximation algorithms for scheduling C-benevolent jobs on we- ighted machines. IISE Transactions, 52(4), 432–443. https:/doi.org/10.1080/24725854.2019.1657606.
Wang, Y. (2023). Review on greedy algorithm. Theoretical and Natural Science. https:/doi.org/10.54254/2753-8818/14/20241041.
Zhao, Z., Zhou, M., and Liu, S. (2022). Iterated Greedy Algori- thms for Flow-Shop Scheduling Problems: A Tutorial. IEEE Tran- sactions on Automation Science and Engineering, 19, 1941-1959. https://doi.org/10.1109/TASE.2021.3062994.
Wu, Y. (2023). Comparison of dynamic programming and gree- dy algorithms and the way to solve 0-1 knapsack problem. Ap- plied and Computational Engineering. https://doi.org/10.54254/2755- 2721/5/20230666.
Bold, M., and Goerigk, M. (2021). Recoverable robust single machine scheduling with interval uncertainty. ArXiv. https://consensus.app/papers/single-machine-scheduling-interval- uncertainty-bold/6a5c9777b1715b2681536df2b6b61fe7/.
Le, T. V., Lee, K., and Luong, N. C. (2023). Bitmask dynamic programming for user scheduling in multi-user MIMO mmWa- ve systems. IEEE Communications Letters, 27, 3365-3369. ht- tps://doi.org/10.1109/LCOMM.2023.3327764.
Lawrynowicz, M., and J’ozefczyk, J. (2021). Robust unrelated parallel machine scheduling problem with interval release dates. ArXiv. https://consensus.app/papers/robust- machine-scheduling-problem-interval-release-dates- lawrynowicz/33172c31239e5f6391dca98b70a659bc/.
He, X., Pan, Q., Gao, L., Wang, L., and Suganthan, P. (2021). A greedy cooperative co-evolutionary algorithm with problem- specific knowledge for multiobjective flowshop group schedu- ling problems. IEEE Transactions on Evolutionary Computa- tion. https://consensus.app/papers/greedy-cooperative-coevolutionary- algorithm-with-he/0b8fe3bdf25f53d883fadbbd6f53fd26/.
Zhao, Z., Zhou, M., and Liu, S. (2022). Iterated greedy algorithms for flow-shop scheduling problems: A tutorial. IEEE Transactions on Automation Science and Engineering, 19, 1941-1959. https://consensus.app/papers/iterated-greedy-algorithms-flowshop- scheduling-problems-zhao/4a6b455820105bf7893924c99d441442/.
Nada, R., Prasetya, A. (2020). Teknik-teknik Optimasi Knapsack Problem. Sains Aplikasi Komputasi dan Teknologi Informasi 2(1):35. http://dx.doi.org/10.30872/jsakti.v2i1.3299
Ariq, Ubaidillah. (n.d). Optimasi 0-1 Knapsack Dengan Dynamic Programming. Diakses pada 29 Juni 2024, Pukul 12.49. https://informatika.stei.itb.ac.id/˜rinaldi.munir/Stmik/2021- 2022/Makalah/Makalah-IF2211-Stima-2022-K1
Albert, Christian. (n.d). Pemanfaatan Decision Tree dalam Pemecahan Knapsack’s Problem dengan Metode Branch and Bound. Diakses pada 29 Juni 2024, Pukul 13.11. https://informatika.stei.itb.ac.id/˜rinaldi.munir/Matdis/2022- 2023/Makalah2022/Makalah-Matdis-2022
Jonathan, Christian. (n.d). Pengaplikasian Algoritma Greedy Untuk Mencari Rute Terpendek. Diakses pada 29 Juni 2024, Pukul 12.49. https://informatika.stei.itb.ac.id/˜rinaldi.munir/Stmik/2017- 2018/Makalah/Makalah-IF2211-2018-017.pdf
Darnita, Y., Toyib, R. (2018). Penerapan Algoritma Greedy Dalam Pencarian Jalur Terpendek Pada Instansi-Instasi Penting Di Kota Ar- gamakmur Kabupaten Bengkulu Utara. Jurnal Media Infotama Vol.15 No. 2. https://doi.org/10.37676/jmi.v15i2.867
Laaksonen, A. (2020). Dynamic Programming. In: Guide to Com- petitive Programming. Undergraduate Topics in Computer Science. Springer, Cham. https://doi.org/10.1007/978-3-030-39357-16
Downloads
Published
How to Cite
Issue
Section
License
The copyright to this article is transferred to Universitas Mercu Buana (UMB) if and when the article is accepted for publication. The undersigned hereby transfers any and all rights in and to the paper including without limitation all copyrights to UMB. The undersigned hereby represents and warrants that the paper is original and that he/she is the author of the paper, except for material that is clearly identified as to its original source, with permission notices from the copyright owners where required. The undersigned represents that he/she has the power and authority to make and execute this assignment.
We declare that this paper has not been published in the same form elsewhere.
Furthermore, I/We hereby transfer the unlimited rights of publication of the above-mentioned paper as a whole to UMB. The copyright transfer covers the right to reproduce and distribute the article, including reprints, translations, photographic reproductions, microform, electronic form (offline, online) or any other reproductions of similar nature.
The corresponding author signs for and accepts responsibility for releasing this material on behalf of any and all co-authors. This agreement is to be signed by at least one of the authors who have obtained the assent of the co-author(s) where applicable. After submission of this agreement signed by the corresponding author, changes of authorship or in the order of the authors listed will not be accepted.
Retained Rights/Terms and Conditions
Although authors are permitted to re-use all or portions of the Work in other works, this does not include granting third-party requests for reprinting, republishing, or other types of re-use.
Our Articles are licensed under CC BY-NC
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
