Construction of Initial Solution Population for Curriculum-Based Course Timetabling using Combination of Graph Heuristics

Juliana Wahid, Naimah Mohd Hussin

Abstract


The construction of population of initial solution is a crucial task in population-based metaheuristic approach for solving curriculum-based university course timetabling problem because it can affect the convergence speed and also the quality of the final solution. This paper presents an exploration on combination of graph heuristics in construction approach in curriculum based course timetabling problem to produce a population of initial solutions. The graph heuristics were set as single and combination of two heuristics. In addition, several ways of assigning courses into room and timeslot are implemented. All settings of heuristics are then tested on the same curriculum based course timetabling problem instances and are compared with each other in terms of number of population produced. The result shows that combination of largest degree followed by saturation degree heuristic produce the highest number of population of initial solutions. The results from this study can be used in the improvement phase of algorithm that uses population of initial solutions

Keywords


Construction Phase; Curriculum-Based Timetabling; Graph Heuristics; Population-Based Metaheuristic;

Full Text:

PDF

References


S. Petrovic, “Towards the Benchmarks for Scheduling,” in The

International Conference on Automated Planning and Scheduling,

ICAPS07, 2007.

S. Rahnamayan, H. R. Tizhoosh, and M. M. a. Salama, “A novel population initialization method for accelerating evolutionary

algorithms,” Comput. Math. with Appl., vol. 53, no. 10, pp. 1605–1614,

K. Socha, K. Joshua, and S. Michael, “A max-min ant system for the university course timetabling problem,” Proc. 3rd Int. Work. Ant Algorithms (ANTS 2002).Lecture Notes Comput. Sci. Vol. 2463.

Springer-Verlag, Berlin, pp. 1-13, 2002.

R. Lewis and B. Paechter, “Application of the Grouping Genetic

Algorithm to University Course Timetabling,” in Evolutionary Computation in Combinatorial Optimization, vol. 3448, G. Raidl and J.

Gottlieb, Eds. Springer Berlin / Heidelberg, 2005, pp. 144–153.

M. A. Al-Betar and A. T. Khader, “A harmony search algorithm for university course timetabling,” Ann. Oper. Res., vol. 194, no. 1, pp. 1–29, 2010.

L. Di Gaspero, B. McCollum, and A. Schaerf, “The Second International Timetabling Competition (ITC-2007): Curriculum-based course timetabling (track 3),” School of Electronics, Electrical Engineering and Computer Science, Queens University, Belfast (UK). (Technical Report QUB/IEEE/Tech/ITC2007/CurriculumCTT/v1.0/1)., 2007.

K. Shaker and S. Abdullah, “Incorporating great deluge approach with kempe chain neighbourhood structure for curriculum-based course timetabling problems,” in 2nd Conference on Data Mining and Optimization, 2009. DMO ’09. 27-28 Oct. 2009, 2009, pp. 149–153.

K. Shaker, S. Abdullah, A. Alqudsi, and H. Jalab, “Hybridizing Metaheuristics Approaches for Solving University Course timetabling

Problems,” in Rough Sets and Knowledge Technology, vol. 8171, P.

Lingras, M. Wolski, C. Cornelis, S. Mitra, and P. Wasilewski, Eds.

Springer Berlin Heidelberg, 2013, pp. 374–384.

S. Abdullah, H. Turabieh, B. McCollum, and E. K. Burke, “An

Investigation of a Genetic Algorithm and Sequential Local Search Approach for Curriculum-based Course Timetabling Problems,”

Multidiscip. Int. Conf. Sched. Theory Appl. (MISTA 2009) 10-12 August

, Dublin, Irel., 2009.

S. Abdullah, H. Turabieh, B. McCollum, and P. McMullan, “A hybrid

metaheuristic approach to the university course timetabling problem,” J. Heuristics, vol. 18, no. 1, pp. 1–23, 2010.

E. K. Burke, B. McCollum, A. Meisels, S. Petrovic, and R. Qu, “A graph-based hyper-heuristic for educational timetabling problems,” Eur. J. Oper. Res. 176 177–192, 2007.

A. L. Bolaji, A. T. Khader, M. A. Al-Betar, and M. A. Awadallah, “Artificial Bee Colony Algorithm for Curriculum-Based Course Timetabling Problem,” ICIT 2011 5th Int. Conf. Inf. Technol., 2011.


Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.

ISSN: 2180-1843

eISSN: 2289-8131