(Publisher of Peer Reviewed Open Access Journals)
Navigation

International Journal of Advanced Computer Research (IJACR)

ISSN (Print):2249-7277    ISSN (Online):2277-7970
Volume-7 Issue-28 January-2017
Full-Text PDF
DOI:10.19101/IJACR.2016.627011
Paper Title : A local search algorithm based on chromatic classes for university course timetabling problem
Author Name : Velin Kralev and Radoslava Kraleva
Abstract :

This paper presents a study for a local search algorithm based on chromatic classes for the university course timetabling problem. Several models and approaches to resolving the problem are discussed. The main idea of the approach is through a heuristic algorithm to specify the chromatic classes of a graph in which the events of the timetable correspond to the graph vertices and the set of the edges represents the possible conflicts between events. Then the chromatic classes should be sorted according to specific sort criteria (a total weight or a total count of events in each class), and finally the local search algorithm starts. The aim of the experiments is to determine the best criterion to sort chromatic classes. The results showed that the algorithm generates better solutions when the chromatic classes are sorted in a total weight criterion.
Keywords : University course timetabling, Chromatic classes, Graph-coloring, Local search.
Cite this article : Velin Kralev and Radoslava Kraleva, " A local search algorithm based on chromatic classes for university course timetabling problem " , International Journal of Advanced Computer Research (IJACR), Volume-7, Issue-28, January-2017 ,pp.1-7.DOI:10.19101/IJACR.2016.627011
References :
[1]Gotlieb CC. The construction of class-teacher timetables. In proceedings IFIP congress 1963 (pp 73-7).
[Google Scholar]
[2]Even S, Itai A, Shamir A. On the complexity of time table and multi-commodity flow problems. In annual symposium on foundations of computer science 1975 (pp. 184-93). IEEE.
[Crossref] [Google Scholar]
[3]De Werra D. An introduction to timetabling. European Journal of Operational Research. 1985; 19(2):151-62.
[Crossref] [Google Scholar]
[4]Komijan AR, Koupaei MN. A mathematical model for university course scheduling: a case study. International Journal of Technical Research and Applications. 2015; 3(19):20-5.
[Google Scholar]
[5]Chen RM, Shih HF. Solving university course timetabling problems using constriction particle swarm optimization with local search. Algorithms. 2013;6(2):227-44.
[Crossref] [Google Scholar]
[6]Kohshori MS, Abadeh MS. Hybrid genetic algorithms for university course timetabling. International Journal of Computer Science Issues. 2012;9(2):446-55.
[Google Scholar]
[7]Burke EK, Mareček J, Parkes AJ, Rudová H. Decomposition, reformulation, and diving in university course timetabling. Computers & Operations Research. 2010;37(3):582-97.
[Crossref] [Google Scholar]
[8]Kralev V. Study and design of automated systems for allocation of resources. PhD Thesis. South-West University Press; 2010.
[Crossref]
[9]Kang L, White GM. A logic approach to the resolution of constraints in timetabling. European Journal of Operational Research.1992; 61(3):306-17.
[Crossref] [Google Scholar]
[10]Partovi FY, Arinze B. A knowledge based approach to the faculty-course assignment problem. Socio-Economic Planning Sciences. 1995;29(3):245-56.
[Crossref] [Google Scholar]
[11]Petrovic S, Burke E. University timetabling handbook of scheduling: algorithms, models and performance analysis. CRC Press; 2004.
[Google Scholar]
[12]Burke EK, Petrovic S. Recent research directions in automated timetabling. European Journal of Operational Research. 2002;140(2):266-80.
[Crossref] [Google Scholar]
[13]Patrick K, Godswill Z. Greedy ants colony optimization strategy for solving the curriculum based university course timetabling problem. British Journal of Mathematics & Computer Science. 2016;14(2):1-10.
[Crossref] [Google Scholar]
[14]Elmohamed MS, Coddington P, Fox G. A comparison of annealing techniques for academic course scheduling. In international conference on the practice and theory of automated timetabling 1997 (pp. 92-112). Springer Berlin Heidelberg.
[Crossref] [Google Scholar]
[15]Costa D. A tabu search algorithm for computing an operational timetable. European Journal of Operational Research. 1994;76(1):98-110.
[Crossref] [Google Scholar]
[16]Abdullah S, Burke EK, Mccollum B. An investigation of variable neighbourhood search for university course timetabling. In the multidisciplinary international conference on scheduling: theory and applications (MISTA) 2005 (pp. 413-27).
[Google Scholar]
[17]Soliman SE, Keshk AE. Memetic algorithm for solving university course timetabling problem. International Journal of Mechanical Engineering and Information Technology. 2015; 3(8):1476-86.
[Crossref] [Google Scholar]
[18]Lewis RM, Paechter B. New crossover operators for timetabling with evolutionary algorithms. International conference on recent advances in soft computing 2004(pp.189-95).RASC.
[Google Scholar]
[19]De Werra D. Extensions of coloring models for scheduling purposes. European Journal of Operational Research. 1996; 92(3):474-92.
[Crossref] [Google Scholar]
[20]Kralev V. A model for the university course timetabling problem. Information Technologies & Knowledge. 2009; 3(3): 276-89.
[Google Scholar]
[21]Kralev V. A genetic and memetic algorithm for solving the University course timetable problem. Information Theories & Applications. 2009;16(3):291-9.
[Google Scholar]
[22]Kralev V, Kraleva R. Variable neighborhood search based algorithm for University course timetabling problem. In proceedings of the fifth international scientific conference 2013(pp. 202-14).
[Google Scholar]
[23]Kralev V, Kraleva R, Yurukov B. An event grouping based algorithm for University course timetabling problem. International Journal of Computer Science and Information Security. 2016; 14(6):222-9.
[Google Scholar]
[24]Burke EK, Elliman DG, Weare R. A university timetabling system based on graph colouring and constraint manipulation. Journal of Research on Computing in Education. 1994;27(1):1-18.
[Crossref] [Google Scholar]
[25]Halldórsson MM. A still better performance guarantee for approximate graph coloring. Information Processing Letters. 1993;45(1):19-23.
[Crossref] [Google Scholar]
[26]Welsh DJ, Powell MB. An upper bound for the chromatic number of a graph and its application to timetabling problems. The Computer Journal. 1967;10(1):85-6.
[Crossref] [Google Scholar]
[27]Kralev V, Kraleva R, Siniagina N. An integrated system for university course timetabling. Mathematics and Natural Science. 2009:98-104.
[Google Scholar]
[28]Kralev V, Kraleva R. Web service based system for generating input data sets. Mathematics and Natural Science. 2011:49-56.
[Google Scholar]