Implementasi Algoritma Greedy dan Dynamic Programming untuk Masalah Penjadwalan Interval dengan Model Knapsack

Achmad Ardani Prasha; Clavino Ourizqi Rachmadi; Amanda Puspita Sari; Nanda Garin Raditya; Sabrina Laila Mutiara; Mohamad Yusuf

doi:10.22441/format.2024.v13.i2.005

Implementasi Algoritma Greedy dan Dynamic Programming untuk Masalah Penjadwalan Interval dengan Model Knapsack

Achmad Ardani Prasha, Clavino Ourizqi Rachmadi, Amanda Puspita Sari, Nanda Garin Raditya, Sabrina Laila Mutiara, Mohamad Yusuf

Abstract

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

Full Text:

PDF

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

DOI: http://dx.doi.org/10.22441/format.2024.v13.i2.005

Refbacks

There are currently no refbacks.

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Format : Jurnal Ilmiah Teknik Informatika
Fakultas Ilmu Komputer Universitas Mercu Buana
Jl. Raya Meruya Selatan, Kembangan, Jakarta 11650
Tlp./Fax: +62215840816
http://publikasi.mercubuana.ac.id/index.php/format