International Journal of Intelligent Systems and Applications (IJISA)
IJISA Vol. 15, No. 3, 8 Jun. 2023
Cover page and Table of Contents: PDF (size: 549KB)
Graph Coloring in University Timetable Scheduling
Full Text (PDF, 549KB), PP.16-32
Views: 0 Downloads: 0
Author(s)
Swapnil Biswas
1
Syeda Ajbina Nusrat
1
Nusrat Sharmin
1,*
Mahbubur Rahman
1
Index Terms
Graph Coloring, Scheduling
Abstract
Addressing scheduling problems with the best graph coloring algorithm has always been very challenging. However, the university timetable scheduling problem can be formulated as a graph coloring problem where courses are represented as vertices and the presence of common students or teachers of the corresponding courses can be represented as edges. After that, the problem stands to color the vertices with lowest possible colors. In order to accomplish this task, the paper presents a comparative study of the use of graph coloring in university timetable scheduling, where five graph coloring algorithms were used: First Fit, Welsh Powell, Largest Degree Ordering, Incidence Degree Ordering, and DSATUR. We have taken the Military Institute of Science and Technology, Bangladesh as a test case. The results show that the Welsh-Powell algorithm and the DSATUR algorithm are the most effective in generating optimal schedules. The study also provides insights into the limitations and advantages of using graph coloring in timetable scheduling and suggests directions for future research with the use of these algorithms.
Cite This Paper
Swapnil Biswas, Syeda Ajbina Nusrat, Nusrat Sharmin, Mahbubur Rahman, "Graph Coloring in University Timetable Scheduling", International Journal of Intelligent Systems and Applications(IJISA), Vol.15, No.3, pp.16-32, 2023. DOI:10.5815/ijisa.2023.03.02
Reference
[1]Sadaf Naseem Jat and Shengxiang Yang. A hybrid genetic algorithm and tabu search approach for post enrolment course timetabling. Journal of Scheduling, 14(6):617–637, 2011.
[2]Wang Wen-jing. Improved adaptive genetic algorithm for course scheduling in col- leges and universities. International Journal of Emerging Technologies in Learning, 13(6), 2018.
[3]Raneem Gashgari, Lamees Alhashimi, Raed Obaid, Thangam Palaniswamy, Lujain Aljawi, and Abrar Alamoudi. A survey on exam scheduling techniques. In 2018 1st International Conference on Computer Applications Information Security (ICCAIS), pages 1–5. IEEE, 2018.
[4]D aniel Marx. Graph colouring problems and their applications in scheduling. Pe- riodica Polytechnica Electrical Engineering (Archives), 48(1-2):11–16, 2004.
[5]Dominic JA Welsh and Martin B Powell. An upper bound for the chromatic number of a graph and its application to timetabling problems. The Computer Journal, 10(1):85–86, 1967.
[6]Murat Aslan and Nurdan Akhan Baykan. A performance comparison of graph coloring algorithms. International Journal of Intel- ligent Systems and Applications in Engineering, pages 1–7, 2016.
[7]Narayan Poddar and Basudeb Mondal. An instruction on course timetable schedul- ing applying graph coloring approach. Inter- national Journal of Recent Scientific Research, 9(2):23939–23945, 2018.
[8]Runa Ganguli and Siddhartha Roy. A study on course timetable scheduling us- ing graph coloring approach. international journal of computational and applied mathematics, 12(2):469–485, 2017. Graph coloring in university timetable scheduling: A compar- ative study 23
[9]Walter Klotz. Graph coloring algorithms. Verlag nicht ermittelbar, 2002.
[10]Akhan Akbulut and G uray Yilmaz. University exam scheduling system using graphcoloring algorithm and rfid technology. International Journal of Innovation, Management and Technology, 4(1):66, 2013.
[11]Kristoforus Jawa Bendi, Theresia Sunarni, and Achmad Alfian. Using graph color- ing for university timetable problem. Interna- tional Journal of Science and Research (IJSR), 7:1692–1697, 11 2018.
[12]NK Cauvery. Timetable scheduling using graph coloring. International Journal of P2P Network Trends and Technology, 1(2):57–62, 2011.
[13]P Nandal, Ankit Satyawali, Dhananjay Sachdeva, and Abhinav Singh Tomar. Graph coloring based scheduling algorithm to automatically generate college course timetable. In 2021 11th International Conference on Cloud Computing, Data Sci- ence Engineering (Confluence), pages 210–214. IEEE, 2021.
[14]J Akbari Torkestani and MR Meybodi. Graph coloring problem based on learning automata. In 2009 International Conference on Information Management and Engineering, pages 718–722. IEEE, 2009.
[15]Timothy A Redl. University timetabling via graph coloring: An alternative ap- proach. Congressus Numerantium, 187:174, 2007.
[16]Zafer Bozyer, M Sinan Ba sar, and Alper Aytekin. A novel approach of graph coloring for solving university course timetabling problem. Proceeding Number, 300:23, 2011.
[17]Sara Miner, Saleh Elmohamed, and Hon W Yau. Optimizing timetabling solutions using graph coloring. NPAC, Syracuse Uni- versity, pages 99–106, 1995.
[18]EK Burke, DG Elliman, and R Weare. A university timetabling system based on graph colouring and constraint manipulation. Journal of research on computing in education, 27(1):1–18, 1994.
[19]Tansel Dokeroglu and Ender Sevinc. Memetic teaching–learning-based optimiza- tion algorithms for large graph coloring prob- lems. Engineering Applications of Artificial Intelligence, 102:104282, 2021.
[20]Hussein Al-Omari and Khair Eddin Sabri. New graph coloring algorithms. Amer- ican Journal of Mathematics and Statistics, 2(4):739–741, 2006.
[21]Linda Ouerfelli and Hend Bouziri. Greedy algorithms for dynamic graph coloring. In 2011 International Conference on Commu- nications, Computing and Control Applications (CCCA), pages 1–5. IEEE, 2011.
[22]NS Narayanaswamy and R Subhash Babu. A note on first-fit coloring of interval graphs. Order, 25(1):49–53, 2008.
[23]Stavros D Nikolopoulos and Charis Papadopoulos. On the performance of the first-fit coloring algorithm on permutation graphs. Information Processing Letters, 75(6):265–273, 2000.
[24]Dominic JA Welsh and Martin B Powell. An upper bound for the chromatic number of a graph and its application to timetabling problems. The Computer Journal, 10(1):85–86, 1967.
[25]Dahlan Abdullah, Marsali Yaton, Heri Sujatmiko, Sepyan Purnama Kristanto, Hendra Nazmi, Irma Lisa Sridanti, Andang Suhendi, Abdurrozzaq Hasibuan, Renny Kurniawati, Darmadi Erwin Harahap, et al. Lecture scheduling system us- ing welch powell graph coloring algorithm in informatics engineering departement of universitas malikussaleh. In Journal of Physics: Con- ference Series, volume 1363, page 012074. IOP Publishing, 2019.
[26]J Arthy and J Aiswarya. Classification of algorithms and largest degree ordering.
[27]Michael W Carter. Or practice—a survey of practical applications of examination timetabling algorithms. Operations research, 34(2):193–202, 1986. 24 Authors Suppressed Due to Excessive Length
[28]William Hasenplaugh, Tim Kaler, Tao B Schardl, and Charles E Leiserson. Or- dering heuristics for parallel graph coloring. In Proceedings of the 26th ACM sym- posium on Parallelism in algorithms and architectures, pages 166–177, 2014.
[29]Daniel Br elaz. New methods to color the vertices of a graph. Communications of the ACM, 22(4):251–256, 1979.
[30]Pablo San Segundo. A new dsatur-based algorithm for exact vertex coloring. Com- puters Operations Research, 39(7):1724–1733, 2012.
[31]Anuj Mehrotra and Michael A Trick. A column generation approach for graph coloring. informs Journal on Computing, 8(4):344–354, 1996.