Content area
Full Text
ABSTRACT
The high school timetabling is a combinatorial optimization problem. It is proved to be NP-hard and has several hard and soft constraints. A given set of events, class-teacher meetings and resources are assigned to the limited space and time under hard constraints which are strictly followed and soft constraints which are satisfied as far as possible. The feasibility of timetable is determined by hard constraints and the soft constraints determine its quality. Difficult combinatorial optimization problems are frequently solved using Genetic Algorithm (GA). We propose Partial Feasibility Preserving Genetic Algorithm (PFP-GA) combined with tabu search to solve hdtt4, "hard timetabling" problem a test data set in OR-Library. The solution to this problem is zero clashes and maintaining teacher's workload on each class in given venue. The modified GA procedures are written for intelligent operators and repair. The PFP-GA in association with Tabu Search (TS) converges faster and gives solution within a few seconds. The results are compared to that of using different methodologies on same data set.
KEYWORDS: Genetic Algorithm, Hard Timetabling, Intelligent Operators, Repair
(ProQuest: ... denotes formulae omitted.)
I. Introduction
The timetabling is one of the major activities for an institution. It is an optimization problem and supposed to be a subset of scheduling problems. Timetabling is a problem of assigning a number of events into a number of time slots. The problem has many forms like educational timetabling, employee timetabling, sports timetabling, transportation scheduling, etc. Timetabling problems are computationally complex, constrained optimization problems. Main objective of such constraint satisfaction problem is to assure all constraints, rather than optimizing a number of objectives. Automated timetabling saves a lot of man-hours and provides optimal solutions within short time which can boost productivity, quality of education and services.
The NP hard problems are computationally complex hence computations in order to explore an optimal result increase exponentially with the structure of the problem. The goal of timetabling process is satisfying certain set of constraints with respect to variables like rooms, teachers, time slots, classes, courses etc. Institutions will have different protocols for maintaining the timetables for the students. Therefore, it is difficult to design a common framework which will work for all the instances. Timetabling problem may not be completely automated as one solution...