A Comparison of Welch Powell Algorithm and Greedy Algorithm in Odd Semester Lecture Room Scheduling Optimization Faculty of Computer Science

Alif Nur Fadilah; Pungkas Subarkah; Reyvaldo Shiva Pramudya; Amin Syabani

doi:10.31764/jtam.v8i4.23142

A Comparison of Welch Powell Algorithm and Greedy Algorithm in Odd Semester Lecture Room Scheduling Optimization Faculty of Computer Science

Alif Nur Fadilah, Pungkas Subarkah, Reyvaldo Shiva Pramudya, Amin Syabani

Abstract

Scheduling is a systematic method to optimize work time, and avoid failure when problems occur. Scheduling is widely applied in the world of education, one of which is in preparing course schedules. Scheduling itself needs to be optimized to ensure a smooth lecture process without any problems between courses. As happened at the Faculty of Computer Science, Amikom Purwokerto University, where in the preparation of the schedule there is no information about lecture rooms. Therefore, the author compiled a lecture hall scheduling optimization journal by comparing the performance between the Welch Powell Algorithm and the Greedy Algorithm as optimization and graph coloring on the lecture hall schedule.The data used in this study are 88 courses spread across 3 study programs, namely Informatics Study Program, Information Systems Study Program, and Informatics Engineering Study Program. This research uses a comparative method on graph vertex coloring, where execution time as duration, lines as algorithm complexity, and manual algorithm calculation as parameters. Based on the research that has been done, the results of 14 full spectrum colors are obtained which are then applied to 23 lecture rooms that can be used without clashes at the Faculty of Computer Science. This can minimize the possibility of overlapping room usage between courses. In addition to comparing the performance of the Welch-Powell Algorithm and the Greedy Algorithm to produce optimal scheduling of lecture rooms, this research can also optimize the schedule of lecturers when entering class to optimize students to be more organized in entering lecture classes at the Faculty of Computer Science, Amikom Purwokerto University.

Keywords

Problem; Schedulling; Optimization; Constraint; Algorithm; Greedy; Welch Powell.

Full Text:

DOWNLOAD [PDF]

References

Abdullah, D., Nurdin, Yaton, M., Sujatmiko, H., Kristanto, S. P., Nazmi, H., Sridanti, I. L., Suhendi, A., Hasibuan, A., Kurniawati, R., Harahap, D. E., Hutabarat, H. D., & Sudarsana, I. K. (2019). Lecture Scheduling System Using Welch Powell Graph Coloring Algorithm in Informatics Engineering Departement of Universitas Malikussaleh. Journal of Physics: Conference Series, 1363(1), 1363–1370. https://doi.org/10.1088/1742-6596/1363/1/012074

Arai, Y., Takahashi, K., Horinouchi, T., Takahashi, K., & Ozaki, H. (2023). SAGAS: Simulated annealing and greedy algorithm scheduler for laboratory automation. SLAS Technology, 28(4), 264–277. https://doi.org/10.1016/j.slast.2023.03.001

Buulolo, F., & Simanjorang, R. M. (2020). Application Employee Shift Scheduling Algorithm Recursive Largest First (RLF) at PT. Invilon Sagita Medan. Journal Of Computer Networks, Architecture and High Performance Computing, 2(1), 83–87. https://doi.org/10.47709/cnapc.v2i1.362

Çakir, E., Ulukan, Z., & Acarman, T. (2021). Shortest Fuzzy Hamiltonian Cycle on Transportation Network Using Minimum Vertex Degree and Time-dependent Dijkstra’s Algorithm. IFAC-PapersOnLine, 54(2), 348–353. https://doi.org/10.1016/j.ifacol.2021.06.048

Chalopin, J., Changat, M., Chepoi, V., & Jacob, J. (2024). First-order logic axiomatization of metric graph theory. Theoretical Computer Science, 993(1), 1–37. https://doi.org/10.1016/j.tcs.2024.114460

Chen, Y., & Lv, X. (2022). Fast Adaptive Character Animation Synthesis Algorithm Based on Depth Image Sequence. Proceedings - 2022 2nd International Conference on Networking, Communications and Information Technology, NetCIT 2022, 2021(2), 622–626. https://doi.org/10.1109/NetCIT57419.2022.00145

Cipta, H., Widyasari, R., & Batubara, F. H. (2023). Graph Coloring Implementation Using Welch Powell Algorithm In Lecture Scheduling Design For Mathmatics Department. Mathline : Jurnal Matematika Dan Pendidikan Matematika, 8(4), 1383–1398. https://doi.org/10.31943/mathline.v8i4.537

Ermanto, Y. V., & Riti, Y. F. (2022). Comparison of Welch-Powell and Recursive Largest First Algorithm Implementation in Course Scheduling. Journal of Management Science (JMAS), 5(1), 5–12. https://doi.org/https://doi.org/10.35335/jmas.v5i1.119

Fransisca, D. C., & Kurniawan, S. D. (2020). Welch powell algoritma aplication to identify the conflict of lesson timetable (case study: informatics engineering, stikom yos sudarso Purwokerto). International Journal of Technology, Innovation and Humanities, 1(1), 57–61. https://doi.org/10.29210/881801

Hassan, O. A. H., Qtaish, O., Abuhamdeh, M., & Hassan, M. A. H. (2019). A hybrid exam scheduling technique based on graph coloring and genetic algorithms targeted towards student comfort. International Journal of Advanced Computer Science and Applications, 10(3), 503–512. https://doi.org/10.14569/IJACSA.2019.0100365

Hidayatulloh, H., Subarkah, P., Dermawan, R. D., & Rohman, M. A. (2023). Optimizing the Implementation of the Greedy Algorithm to Achieve Efficiency in Garbage Transportation Routes. JTAM (Jurnal Teori Dan Aplikasi Matematika), 7(4), 1143. https://doi.org/10.31764/jtam.v7i4.16612

Jason, Siever, M., Valentino, A., Suryaningrum, K. M., & Yunanda, R. (2022). Dijkstra’s algorithm to find the nearest vaccine location. Procedia Computer Science, 216(2022), 5–12. https://doi.org/10.1016/j.procs.2022.12.105

Kawatu, F. F., Mangobi, J. U. L., & ... (2023). Welch-Powell Algorithm Implementation In Compiling Lecture Schedules In The Mathematics Education Study Program, Manado State University. Jurnal Kendali Teknik …, 1(2), 16–37. https://journal.widyakarya.ac.id/index.php/jkts-widyakarya/article/view/13%0Ahttps://journal.widyakarya.ac.id/index.php/jkts-widyakarya/article/download/13/13

Kehinde, S., Olalekan, P., Olusayo, E., & Akin, C. (2024). First Fit Algorithm : A Graph Coloring Approach to Conflict - Free University Course Timetabling. 17(5), 125–139. https://doi.org/10.9734/AJRCOS/2024/v17i5443

Leong, Y. W., Goh, S. M., Chau, C. F., Voon, B. W. N., Ong, H. S., Yahaya, M. P., Abdullah, N., Mohd Hatta, N., Tial, M. K. S., & Sulaiman, N. F. (2024). A 3-year observation on analyzing cloud-to-ground lightning in Peninsular Malaysia using graph theory. Ain Shams Engineering Journal, 15(4), 102610. https://doi.org/10.1016/j.asej.2023.102610

Lu, P., Hu, T., Wang, H., Zhang, R., & Wu, G. (2021). G-CAS: Greedy Algorithm-Based Security Event Correlation System for Critical Infrastructure Network. Security and Communication Networks, 2021(6), 1–13. https://doi.org/10.1155/2021/3566360

Musa, U. B., & Oyelakin, A. M. (2024). A Survey of Approaches for Designing Course Timetable Scheduling Systems in Tertiary Institutions. 03(01), 1–6. https://doi.org/10.29207/joseit.v3i1.5609

Nandal, P., Satyawali, A., Sachdeva, D., & Tomar, A. S. (2021). Graph Coloring based Scheduling Algorithm to automatically generate College Course Timetable. Proceedings of the Confluence 2021: 11th International Conference on Cloud Computing, Data Science and Engineering, 2021(October), 210–214. https://doi.org/10.1109/Confluence51648.2021.9377151

Nie, J., Graizer, V., & Seber, D. (2023). A greedy algorithm for wavelet-based time domain response spectrum matching. Nuclear Engineering and Design, 410(May), 112384. https://doi.org/10.1016/j.nucengdes.2023.112384

Pamela. (2023). Naval Postgraduate [Naval Postgraduate School]. In Security (Issue December). https://apps.dtic.mil/sti/trecms/pdf/AD1150599.pdf

Phillips, D. J., Mcglaughlin, A., Ruth, D., Jager, L. R., & Soldan, A. (2015). NeuroImage : Clinical Graph theoretic analysis of structural connectivity across the spectrum of Alzheimer 3 s disease : The importance of graph creation methods. YNICL, 7(1), 377–390. https://doi.org/10.1016/j.nicl.2015.01.007

Popov, A. A., Lopateeva, O. N., Ovsyankin, A. K., & Satsuk, M. M. (2020). Application of greedy algorithms for the formation of the educational schedule in the higher education. Journal of Physics: Conference Series, 1691(1), 1–9. https://doi.org/10.1088/1742-6596/1691/1/012066

Shao, Y., Chu, S., Zhang, T., Yang, Y. J., & Yu, T. (2019). A Greedy Sampling Design Algorithm for the Modal Calibration of Nodal Demand in Water Distribution Systems. Mathematical Problems in Engineering, 2019. https://doi.org/10.1155/2019/3917571

Xiao, Y., Dong, G., & Song, X. (2020). Data-Based Reconstruction of Chaotic Systems by Stochastic Iterative Greedy Algorithm. Mathematical Problems in Engineering, 2020(1), 1–9. https://doi.org/10.1155/2020/6718304

Xu, J., Qiang, X., Zhang, K., Zhang, C., & Yang, J. (2018). A DNA Computing Model for the Graph Vertex Coloring Problem Based on a Probe Graph. Engineering, 4(1), 61–77. https://doi.org/10.1016/j.eng.2018.02.011

DOI: https://doi.org/10.31764/jtam.v8i4.23142