Hybrid Metaheuristic Algorithms for Highly Constrained Combinatorial Optimization Problems

Abstract

In this thesis a study has been devoted in the field of Timetable Scheduling problems and more explicitly University Course Timetabling Problems (UCTP). The study exposed that these course timetabling problems are highly challenging and lie in NP class problems domain, therefore no algorithm or approach exists which can solve these problems in polynomial time span. An approach found to solve one type will not achieve the same success for another type and hence they are solved differently from each other. Further, for each of the problem types, this also extends to each problem instances can differ extremely in terms of dimensions and constraints. These combinatorial optimization problems are extensively studied and attracted the attention of scientific community from several disciplines such as Computer Science (CS), Operational Research (OR) and many other applied areas. The manual generation of timetables is very time-consuming and takes countless efforts. Furthermore, the resulting timetables are usually incompetent and expensive in terms of resources and money. They are defined as involving the allocation of events (meetings between groups of students and lecturers in a particular venue or between classes and teachers) to timetable periods while at the same time satisfying a set of hard constraints and minimizing a set of soft constraints violations. It necessitates the development of automated timetables which minimizes errors, reduces their time of creation and satisfies desirable objectives as much as possible. Introduction of the study work is discussed in Chapter 1, Literature review is covered in Chapter 2, Objectives and Research Methodologies are discussed in Chapter 3. In Chapter 4 AHP technique is proposed to solve a single section teacher course assignment problem. The teacher course allocation problem is a sub problem of UCTP, In general there is no standard procedure to schedule the courses to teacher. This assignment process in general done at mutual understanding and compromising basis.