International Journal of Mathematics Trends and Technology
Volume 68 | Issue 1 | Year 2022 | Article Id. IJMTT-V68I1P507 | DOI : https://doi.org/10.14445/22315373/IJMTT-V68I1P507
Course scheduling problems is the most routine problems faced by academic institutions in every new semester. Scheduling is done by taking into resources such as students, lecturers, courses, and rooms whose purpose is to avoid conflicts by satisfying various preferential constraints. The presence of the various resources leads to difficulty in generating a schedule in a limited period. Room is assumed as zoom meeting accounts so that they are not limited by capacity. Graph coloring is one decent method to deal with a timetable scheduling problem. In this work, graph vertex coloring is applied for generating the schedule from the given data of Undergraduate Study Program of Mathematics, Universitas Padjadjaran. The scheduling problem is divided into a common case and a special case which has additional constraints on the special case. The scheduling problem is solved by the combination and modification of Bania-Duarah and Greedy algorithm. The workflow is initiated by constructing a graph and its matrix adjacency then the workflow completed by Greedy algorithm on the coloring phase. The main results from this work are a modified Python program for scheduling problems and the schedule of both cases. This work provides an alternative solution to the scheduling problem by using the concept of graph theory applying graph coloring for similar cases.
[1] Diveev, A. I., and O. V. Bobr, Variational genetic algorithm for np-hard scheduling problem solution, Procedia Computer Science 103 (2017) 52-58.
[2] F. Zhu, Z. Liu, Z. Yan and Y. Liang, A study into employee scheduling problem based on graph theory algorithms, 2018 IEEE Integrated STEM Education Conference (ISEC), (2018) 213-215, doi: 10.1109/ISECon.2018.8340484.
[3] F. A. Omara, M. M. Arafa, Genetic Algorithms for Task Scheduling Problem. In: Abraham A., Hassanien AE., Siarry P., Engelbrecht A. (eds) Foundations of Computational Intelligence Volume 3. Studies in Computational Intelligence, vol 203. Springer, Berlin, Heidelberg (2009). https://doi.org/10.1007/978-3-642-01085-9_16
[4] J. Kennedy & R. Eberhart, Particle swarm optimization, In Proceedings of ICNN'95-international conference on neural networks (4) (1995) 1942–1948, https://doi.org/10.1109/ICNN.1995.488968
[5] M. Dorigo, M. Birattari, & T. Stutzle, Ant colony optimization. IEEE Computational Intelligence Magazine, 1(4) (2006) 28–39. https://doi.org/10.1109/CI-M.2006.248054
[6] W. Deng, J. Xu and H. Zhao, An Improved Ant Colony Optimization Algorithm Based on Hybrid Strategies for Scheduling Problem, in IEEE Access, (7) (2019) 20281-20292 doi: 10.1109/ACCESS.2019.2897580.
[7] X. S. Yang & S. Deb, Cuckoo search via Lévy flights. In 2009 World Congress on nature & biologically inspired computing (NaBIC) (2009) 210–214, IEEE.
[8] X. S. Yang, A new metaheuristic bat-inspired algorithm. In Proceedings of nature inspired cooperative strategies for optimization (NICSO 2010) (2010) 65–74, Springer.
[9] X. S. Yang & S. Deb, Cuckoo search via Lévy flights. In 2009 World Congress on nature & biologically inspired computing (NaBIC) (2009) 210–214). IEEE.
[10] M. Dell'Amico, M. Trubian, Applying tabu search to the job-shop scheduling problem. Ann Oper Res (41) (1993) 231–252 https://doi.org/10.1007/BF02023076
[11] Abdel-Basset, Mohamed, G. Manogaran, D. El-Shahat, and S. Mirjalili., A hybrid whale optimization algorithm based on local search strategy for the permutation flow shop scheduling problem." Future Gener. Comput. Syst. 85 (2018) 129-145.
[12] T.A. Redl, University Timetabling via Graph Coloring: An Alternative Approach, Congressus Numerantium, (187) (2007) 174-186.
[13] D. C. Wood, A System for Computing University ExaminationTimetables, The Computer Journal (11) (1968) 41-47
[14] J. R. Allwright, R. Bordawekar, P. D. Coddington, K. Dincer & C. L. Martin, A Comparison of Parallel Graph Coloring Algorithms. SCCS-666 (1995) 1-19.
[15] R. K . Bania & P. Duarah. Exam Time Table Scheduling using Graph Coloring Approach. International Journal of Computer Sciences and Engineering, 6(5) (2018) 84-93.
[16] D.J.A. Welsh, & M. B. Powell, An Upper Bound for the Chromatic Number of a Graph and it's Application to Timetabling Problems. The Computer Journal. ,Vol.10, No.1, pp. (1967)85-86.
[17] E. K. Burke, D. G. Elliman, & R. Weare, A University Timetabling System Based on Graph Colouring and Constraint Manipulation. Journal of research on computing in education, 27(1) (1994) 1-18.
[18] M. Malkawi, M.A. Hassan, & O. A. Hassan, A New Exam Scheduling Algorithm using Graph Coloring. International Arab Journal of Information Technology (IAJIT), 5(1)(2008) 80- 86.
[19] E. K. Burke, K. Jackson, J.H. Kingston, & R. F. Weare, Automated University Timetabling: The State of the Art. Compute. J., 40(9) (1997) 565–571.
[20] T. Harju, Oxide Networks, Graph Theory, and The Passivity of Ni-Cr-Mo Ternary Alloys. Corrosion Science, 50(12) (2008) 3622–3628.
[21] R. M. R. Lewis, A Guide to Graph Coloring. In A Guide to Graph Coloring, 7(2016)
[22] K. Ruohonen, Graph Theory (Chapter 2). Network Science, 72(8)(2015) 1–35.
[23] R. J. Trudeau, Introduction to Graph Theory. Dover books on advanced mathematics. (1993)
[24] R. J. Wilson, Introduction to Graph Theory. Longman. (1996)8-14
[25] D. B. West, Graph Coloring. In Graph Theory with Applications (2nd ed.). (2000)1-19
[26] C. Vasudev, Graph Theory with Applications. New Age International (P). (2006) 153-155
[27] J. Zhang, An Introduction to Chromatic Polynomials. Journal of Combinatorial Theory, 4(1)(1968) 52–71.
Ugi Abdul Muchyi Sunanto, Herlina Napitupulu, Ema Carnia, Asep Kuswandi Supriatna, "Course Scheduling of Undergraduate Study Program of Mathematics Universitas Padjadjaran Case Using Graph Coloring with Modified Algorithm," International Journal of Mathematics Trends and Technology (IJMTT), vol. 68, no. 1, pp. 61-69, 2022. Crossref, https://doi.org/10.14445/22315373/IJMTT-V68I1P507
PDF 
Abstract 
Keywords 
References 
Citation