Open Access   Article Go Back

Exam Time Table Scheduling using Graph Coloring Approach

Rubul Kumar Bania1 , Pinkey Duarah2

  1. Department of Computer Applications, North-Eastern Hill University, Tura Campus, Meghalaya, India.
  2. Department of Computer Applications, North-Eastern Hill University, Tura Campus, Meghalaya, India.

Section:Research Paper, Product Type: Journal Paper
Volume-6 , Issue-5 , Page no. 84-93, May-2018

CrossRef-DOI:   https://doi.org/10.26438/ijcse/v6i5.8493

Online published on May 31, 2018

Copyright © Rubul Kumar Bania, Pinkey Duarah . This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

View this paper at   Google Scholar | DPI Digital Library

How to Cite this Paper

  • IEEE Citation
  • MLA Citation
  • APA Citation
  • BibTex Citation
  • RIS Citation

IEEE Style Citation: Rubul Kumar Bania, Pinkey Duarah, “Exam Time Table Scheduling using Graph Coloring Approach,” International Journal of Computer Sciences and Engineering, Vol.6, Issue.5, pp.84-93, 2018.

MLA Style Citation: Rubul Kumar Bania, Pinkey Duarah "Exam Time Table Scheduling using Graph Coloring Approach." International Journal of Computer Sciences and Engineering 6.5 (2018): 84-93.

APA Style Citation: Rubul Kumar Bania, Pinkey Duarah, (2018). Exam Time Table Scheduling using Graph Coloring Approach. International Journal of Computer Sciences and Engineering, 6(5), 84-93.

BibTex Style Citation:
@article{Bania_2018,
author = {Rubul Kumar Bania, Pinkey Duarah},
title = {Exam Time Table Scheduling using Graph Coloring Approach},
journal = {International Journal of Computer Sciences and Engineering},
issue_date = {5 2018},
volume = {6},
Issue = {5},
month = {5},
year = {2018},
issn = {2347-2693},
pages = {84-93},
url = {https://www.ijcseonline.org/full_paper_view.php?paper_id=1942},
doi = {https://doi.org/10.26438/ijcse/v6i5.8493}
publisher = {IJCSE, Indore, INDIA},
}

RIS Style Citation:
TY - JOUR
DO = {https://doi.org/10.26438/ijcse/v6i5.8493}
UR - https://www.ijcseonline.org/full_paper_view.php?paper_id=1942
TI - Exam Time Table Scheduling using Graph Coloring Approach
T2 - International Journal of Computer Sciences and Engineering
AU - Rubul Kumar Bania, Pinkey Duarah
PY - 2018
DA - 2018/05/31
PB - IJCSE, Indore, INDIA
SP - 84-93
IS - 5
VL - 6
SN - 2347-2693
ER -

VIEWS PDF XML
889 484 downloads 266 downloads
  
  
           

Abstract

One of the most common academic scheduling problems which can be perceived in any educational system is the exam time table generation. The presence of vast numbers of students and offered courses makes it difficult to schedule exams in a limited epoch of time. An appropriate schedule can be designed by utilizing different resources like subjects, teachers, students and classrooms in a way to evade conflicts by fulfilling special types of constraints. Graph coloring is one decent approach which can deal with timetable scheduling problem and can satisfy changing requirements. In this work, we have framed a systemic model by applying graph vertex coloring approach for generating exam timetabling with the help of a course matrix generated from given data of an educational institute. From the problem domain, different types of constraints viz., hard and soft are figured out and while solving emphasis is focused on the degree of constraint satisfaction. Workflow of the system is described by using a case study and the output which it has generated is efficient and satisfactory.

Key-Words / Index Term

Time table, Graph coloring, Scheduling, Hard constraints, Soft constraints, Course matrix

References

[1] Welsh D.J.A., and Powell M.B., “An Upper Bound for the Chromatic Number of a Graph and it`s Application to Timetabling Problems”, The Computer Journal. (1967), Vol.10, No.1, pp. 85-86.
[2] Mohammad M., Mohammad A.H., and Osama A.H., “A new exam scheduling algorithm using graph coloring”, The International Arab Journal of Information Technology, (2008), Vol. 5, No.1, pp. 80- 86.
[3] Burke K.E., Mccollum B., Meisels A.,and Petrovic S., “A Graph-Based Hyper-Heuristic for Educational Timetabling Problems”, European Journal of Operational Research (2007), Vol-176, pp. 177-192.
[4] Somasundaram M.R., “Discrete Mathematical structures”, 2nd edition, PHI, 2010.
[5] Bhasin H., “Algorithms Design and Analysis”, 1st edition, Oxford University Press, 2015.
[6] Akbulut A., and Yılmaz G., “University Exam Scheduling System Using Graph Coloring Algorithm and RFID Technology”, International Journal of Innovation, Management and Technology, (2013), Vol. 4, No. 1, pp. 66-72.
[7] Hussain B., Basari A.S.H., and Asmai S.A., “Exam Timetabling Using Graph Colouring Approach”, In the proceedings of IEEE Conference on Open Systems (ICOS2011), (2011), pp.139-144.
[8] Verma O.P., Garg. R.,and Bisht V.S., “Optimal Time-Table Generation by Hybridized Bacterial” Foraging and Genetic Algorithm”, In Proceedings of International Conference on Communication Systems and Network Technologies (CSNT’12), (2012), pp. 919-923.
[9] Jha. S.K., “Exam Timetabling Problem using Genetic algorithm”, International Journal of Research in Engineering and Technology, (2014),Vol.3, No.5, pp. 649-655.
[10] Alon N., “A Note on Graph Colorings and Graph Polynomials,” Journal of Combinatorial Theory Series B”, (1997), Vol. 70, No. 1, pp. 197-201.
[11] Gross J. and Yellen J., Handbook of Graph Theory, Discrete Mathematics and its Applications, CRC Press, Vol. 25, 2003.
[12] Norberciak. M., “Universal Method for Timetable Construction based on Evolutionary Approach” World Academy of Science, Engineering and Technology, (2006), pp. 91-96.