Citation :

Dr Cauvery N K, "Timetable Scheduling using Graph Coloring," International Journal of P2P Network Trends and Technology (IJPTT), vol. 1, no. 2, pp. 24-29, 2011. Crossref, https://doi.org/10.14445/22492615/IJPTT-V1I2P410

Abstract

The problem of constructing an automated system for timetabling is a particularly well known one. Timetabling is a common example of a scheduling problem and can manifest itself in several different forms; the particular form of timetable required is specific to the environment or organization in which it is needed. Many programs exist for this task but they perform well only in particular isolated environment. With the help of graph coloring, it is proposed to develop a general system that can cope with the ever changing requirements of large educational institutions. Timetabling problem is a NP-hard problem. many combinatorial problems (optimization problems) are NPhard. It is generally believed that NP-hard problems cannot be solved to optimality within times which are polynomial bounded functions of input size. Therefore there is much interest in heuristic algorithms which can find near optimal solutions within reasonable running time. One of the most studied NP-hard problems is the “graph coloring problem”. Graph coloring has numerous applications in scheduling and other practical problem; “timetabling” is one of them. One of the heuristic approaches to solve graph coloring is “Ant algorithm” [1].

Keywords

Graph coloring, Ant colony optimization, Pheremone trails

References

[1] SangHyuck Ahn, SeungGwan Lee, TaeChoong Chung, “Modified Ant Colony System for Coloring Graphs”, ICICS-FCM 2003 15-18 December 2003. http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=12 92787
[2] Spyros Kazarlis, Vassilios Petridis and Pavlina Fragkou, “Solving University Timetabling Problems Using Advanced Genetic Algorithms”, International Journal, Vol. 4.2009, p no. 260-279.
[3] Ehsan Salari and Kourosh Eshghi,“An ACO Algorithm for the Graph Coloring Problem”, International Journal Contemp. Math. Sciences, Vol. 3, 2008, no. 6, 293 – 304.
[4] Malika Bessedik, Rafik Laib, Aissa Boulmerka et Habiba Drias, “Ant Colony System for Graph Coloring Problem”. J. Op. Res. Society, pp. 290-300 (2004) [5] D. Costa and Hertz A. “Ant can colour graphs”, J. Op. Res. Society, pp. 295-305 (1997)
[6] E.K.Burke, D.G.Elliman, R.Weare, “A University Timetabling System based on Graph Colouring and Constraint Manipulation”.
[8] Dorigo M, Maniezzo V, Colorni A, “The ant system:Optimization by a colony of cooperation agents”,IEEE Transaction of Systems, Man and Cybernetics-Part B, vol 26, no.2 pp. 29-41(1996).
[9] Malika Bessedik, Rafik Laib,“Ant Colony System for Graph Coloring Problem”, International Conference on Computational Intelligence for Modeling, 2005.