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
- Attribution (BY): You must give appropriate credit to the original creator, provide a link to the license, and indicate if you made any changes.
- ShareAlike (SA): If you remix, transform, or build upon the material, you must distribute your new creation under the same or a compatible license (such as CC BY-SA 4.0).
- No Additional Restrictions: You cannot apply legal terms or technological measures that legally restrict others from doing anything the license permits.
- Share: Copy and redistribute the material in any medium or format.
- Adapt: Remix, transform, and build upon the material to create new works (like artwork, code, or documentation).
- Commercial Use: You can use and sell your adaptations or distributions commercially, provided you respect the ShareAlike condition.
- Irrevocable: Once granted by the creator, the license cannot be taken back as long as you comply with its terms.
- No Warranties: The material is provided "as-is," and the licensor gives no guarantees or warranties regarding your use of the work.
- Official Reference: You can read the full legal summary on the Creative Commons Attribution-ShareAlike 4.0 International Deed.