Constructing population of initial university timetable: design and analysis

Abstract

The construction of population of initial timetable is an essential stage in population-based metaheuristic approach for solving curriculum-based university course timetabling problem because it may impact the quality of the final timetable. This paper presents population of initial timetable construction approach in curriculum based course timetabling problem by using the graph heuristics to determine the sequential order of courses/lectures to be assigned in the timetable. The graph heuristics were implemented as single and combination of two heuristics. The courses in curriculum-based university course timetabling problem that was organized based on the heuristics setting will be repeatedly assigned to valid empty slots while fulfilling all the hard constraints. If a course is unable to be assigned to whichever slots because of no more valid empty slots, it will be inserted into the unscheduled courses/lectures list. The unscheduled courses/lectures list will be assigned later to the timetable using several procedures executed in a sequence. The approaches were tested on the ITC2007 instances and the results were analyzed with some statistical tests to determine the best setting of heuristics in the construction approach.  The result shows that the construction approach with combination of largest degree followed by saturation degree heuristic, generate the maximum number of population of initial timetables. The result from this study can be used in the improvement stage of metaheuristic algorithm that uses population-based approach.