INTRODUCTION

A different scheduling and timetabling problems. The problems are characterized as constraints satisfaction problems. The solution methodology uses genetic algorithms to minimize the total penalty for constraint violation. Encoding, genetic operators and fitness evaluation are implemented. To solve this problem, a genetic algorithm maintains a population of chromosomes, each of which represents a possible solution (timetable). In every generation, a new population of chromosomes is created using bits and pieces of the fittest of the old generation. The main tasks of applying a genetic algorithm to solve a problem are: encoding the solution as chromosomes; developing a fitness evaluation function; choosing genetic operators and run parameters. The genetic algorithm includes the following functions: initialize, evaluate, select, crossover, mutate, create new population. Our genetic algorithm proposes a solution which consists of a number of tuples, one for each class. The timetabling constraints are classified: unary constraints, binary constraints; k-nary constraints. The fitness function is a linear combination of a cost function and a penalty function. The goal is that all constraints be satisfied. We use a constraint propagation approach.
Genetic algorithms (GAs) provide a powerful alternative for tackling this type of problem. To date many of the timetabling problems tackled by genetic algorithms have been based on examination timetables. These problems are characterised by a large number of 'hard' constraints and in some cases extend the time in the examination schedule. A legal solution is the prime objective. School timetabling has been tackled using genetic algorithms, however again the timetable is highly constrained and the emphasis is on finding a feasible solution. Such papers have mainly based the genetic algorithm's search on the number of conflicting lectures or examinations. This paper concentrates on a timetable where 'soft' constraints are the key consideration. In addition to the constraint satisfaction approach a greedy algorithm using an order based GA, with a new fitness function, has been used as the closest reasonable approximation to existing GA techniques for tackling the problem. The key disadvantage to the order-based GA using a greedy algorithm is that it searches a subset of legal space and so is not ideal. Consequently, this paper concentrates on different encoding techniques and operators in order to try and identify a more effective method. Variants of the crossover operators used in scheduling are proposed in order to try and find an improved timetabling algorithm.

Talk to Expert

Problem Description

Timetabling problem considered here is actually reduction of typical class timetabling problem. According to Rossi-Doria [1] the problem consists of a set of events of classes E to be scheduled in available timeslots along with a set of rooms R in which events can take place and the set of students S who can attend these events and set of fea- ture F which is required by events and satised by rooms. A feasible timetable is one in which all events have been assigned to room and timeslot so that following hard constraints are satised.

No student can attend more than one event at the same time.
The room is big enough to schedule the event and it must satisfy features required by the event.
Only one event can be scheduled in a room at any timeslot. In addition to this timetable is equally penalized for the occurrences of following soft constraints
Students attend class in the last slot of the day.
Students attend more than two classes in row.
Students attend single class on a day.

Note that the soft constraint selected is representative of three dierent classes; rst one checked with no knowledge of rest of timetable; second one checked while building a solution taking into account that events are assigned to nearby timeslots and nally last one checked only when timetable is complete and all events are assigned to timeslots. The main objective here is to minimize number of soft constraint violation while generating feasible solution. A solution is feasible if it does not have any hard constraint violation.

Genetic Algorithm

We used Genetic Algorithm to solve class scheduling problem with custom selection methods. Genetic algorithm is population based heuristic method largely applied to solve the scheduling problems. It is search methods based on principles of natural selection and genetics. The basic working of genetic algorithm is given by following algorithm.