# Time Tabling Problem In School Of Computing Computer Science Essay

Published:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Timetabling problems are periodically faced in each and every school. The basic problem is that events those can be assigned to a set of times. Example classes, lectures, etc. the arrangement can be done in such a way that the students can attend all the classes. It's a difficult task to solve the time-tabling problem in all the schools. Some pair of events are edge-constrained because of some students must have to attend both class. So that they must be scheduled in perfect way that essentially a form of coloring problem. However the general school timetabling problem is known to be as NP-hard. Current timetabling problem can include tabu search, Genetic Algorithm.

It difficult to find the optimal solution which makes the toughness of the problem, to implement them in practice there are many techniques. This time-tabling problem is classified as NP-Complete Problem. A vast network of constraints that are related it means that assigns a set of courses, classes, rooms, lecturers, lectures and students. Thus the change in time of the lecture may affect all the students and classes as well. We need to consider different constraints, when it is necessary to fix some timeslots with lectures.

Among the several unknowns a constraint is a special logical relation. Hard constraints and soft constraints are referred in some of the constraints. If the solution is considered as valid (feasible) hard constraints are to be satisfied. Lecturers are preferred soft constraints and the school to improve the goodness. Soft constraints are desirable but not so essential. Soft constraints may be changeable. They may maintain the solution quantitatively.

2. Time-tabling problem

2.1 Background:

A vast network of constraints which schedules lot of classes, rooms, lecturers and student groups that relate each other. We consider two different constraints, hard and soft constraints. The Transforming Timetabling Project was established to bring about a new approach to timetabling and rooming. To get a feasible solution hard constraints are considered. For the effectiveness solution soft constraints are constraints. Examples of hard and soft constraints are that in hard constraints, a lecturer can take a class with a group of students at a time. Soft constraints depend on lecturer's choice about classes. A teacher working in several classes greater than that of a teacher working in fewer classes, the total number of teaching hours being the same. Here a school contains different types of classes in which common classes are to split or grouped.

Time-Tabling problem can be tackled with several techniques that belong into Artificial Intelligence.

Genetic algorithms

Tabu search

Constraint Satisfaction

2.2 Feasibility, Optimality and Complexity:

Time-Tabling problem must satisfy all the constraints. This problem is formulated using search problem and optimization problem. Time-tabling problem must satisfy all hard constraints that simultaneously satisfy soft constraints that are desirable over soft constraints.

Some cases apply optimization techniques to the search problem, so that it reduces the distance to feasibility. This feasibility function is an objective function. This is done to get the search for the best solution.

In search and optimization problem, appears the underlying problem. This problem occurs when the problem arises among the search and the optimization that refer the decision for the solution whether it is in the search problem or in the optimization problem.

The exact solution occurs only in some cases that might be like less than 10 courses. But the university has many courses. Thus we may not be guaranteed about the optimal solution.

3. Aim:

To create a constraint-based Time-Tabling that schedules classes in the school of computing.

4. Objectives:

To model the Time-Tabling problem in the school of computing as a constraint satisfaction problem.

To obtain a constraint based Time-table scheduler.

The obtained Time-Table has feasibility and effectiveness in a real situation.

5. Methodology

5.1 Different Techniques to solve the problem

## 5.1.1 The Timetable Problem

We will use the construction of a timetable schedule of classes for a school as the intermediate for our examination. The circumstance of "on field" testing has the main reason for choosing this example.

The development of the lesson timetable for a high school may be anatomizing in the formulation of several integrated timetables. In fact, sections are always appended in pairs, with a merge of sections sharing many teachers with resources. The "atomic unit" can be prepared by two pair of sections, its high internal dependencies were not given to further decomposable and other sections have been segregated relatively.

In a given these bounds, the problem can be described as:

a list with teachers of m (20-24 in our case)

a list of classes(p) involved (10 for the two coupled sections)

each class 30 with a list of weekly teaching hours(n)

each class curriculum , that is the list of the frequencies of the teachers working in the class

Some external conditions (for example each and every hour the teachers are involved in other sections) [6].

A normal representation of the TTP is shown below.

Given the 5-tuple < T, A, H, R, f >

Where T is a finite set {T1, T2, Ti, Tm} of m resources (teachers)

A is a set of classes to be accomplished by the teachers

H is a finite set {H1, H2, .. , Hj, .. , Hn} of n time-intervals (hours)

R is an m.n matrix of rijïƒŽA (a timetable); f is a function to be minimized,

f: R ïƒžï€ Â®;

We want to compute MIN f (ï³, ï„, ï-, ï)

Where

ï³ï€ is the number of infeasibilities, as represented in the following;

ï„ï€ is the set of didactic costs e.g. for this is same subject that spread over the week which is not having the hours.

ï-ï€ is a set of organizational costs e.g. for this is possible temporary teaching post which not is having at least one teacher.

ïï€ is a set of personal costs e.g. for this is not having a day-off.

It satisfies the following constraints if every solution (timetable) generated by our algorithm is feasible: The present in the timetable for every teacher and every class must be in a predefined number of hours.

â€¢ In the same class in the same hour there may not be more than one teacher, and no teacher can take more than one class within an hour.

â€¢ No "uncovered hours" will be there (means, a class having only one teacher not more than one).

By the linear programming with binary variables the problem has been approached, using some heuristics. In fact, with standard algorithms if it were approached, i.e. defining binary variables xijk (where, based on the previous parameters specified, i defines a teacher, j defines a time-interval and k defines a class) the problem can be defined by 6000 variables (i = 1... 20, j = 1....30, k = 1... 10), which makes it difficult. Using Genetic Algorithm (GA) we approach has been done in order to solve the problem.

## 5.1.2 The genetic approach to the timetable problem:

When applying GAs to problems some difficulties have been encountered. The crossover and mutation operators are the most relevant of them may generate infeasible solutions as previously defined.

Those are shown below

â€¢ Crossover can be applied consistently in such a way that changes the representation of a solution.

â€¢ Only feasible solutions can be generated by defining a new crossover and mutation operators.

â€¢ Using of a filtering algorithm that changes the infeasible solutions to feasible solutions which make some kind of genetic repair.

A new crossover operator and the application of genetic repair case the most successful approaches have been introduced using the traveling salesman. The case particularly straightforward by the redefinition of mutation: exchanging the position of two cities is sufficient to a string. On the other hand the TTP, Redefining the both crossover and mutation is necessary to implement genetic repair.

In a high school we now describe for a pair of sections how we approach to solve problem of generating a school timetable. We chose is the set the alphabet A of the jobs which performed by the teachers: other activities and the elements of their classes are to be covered. Which we announce, those are shown below:

â€¢ The lessons have to be taught in the ten classes with the characters 1, 2, 3, 0.

â€¢ For temporary teaching posts the hours at disposal with the character D;

â€¢ For the professional development the hours with the character A;

â€¢ in different classes of sections the lessons are taught during the hours with the character S; in the initialization phase this hours are fixed and they are called as fixed hours;

â€¢ The hours with the character in which the teacher doesn't have to work;

â€¢ With the characters ----- the teacher's day-off.

Our alphabet is therefore A = {1,2,3,4,5,6,7,8,9,0,D,A,S,Â¨,-}.

This allows us to represent the problem in the form of matrix R (an m.n matrix of rijïƒŽA) where each row corresponds to a teacher and each column to an hour. Every element rij of the matrix R is a gene; its allelic value may vary on the subset of a specific to the teacher corresponding to the row containing the gene.

The problem can be represented by matrices shown in Figure 1.

## Fig.1 - Matrix representing a timetable [7].

The constraints are managed as shown below

â€¢ By the genetic operators, so that the set of hours to be taught by each teacher, allocated in the initialization phase, cannot be changed by the application of the genetic operators (which have been specifically redefined for this purpose);

â€¢ By the filtering algorithm, so that the infeasibilities caused by the application of genetic operators are, totally or partially, eliminated by filtering;

â€¢ By the objective function, so that selective pressure is used to limit the number of individuals with infeasibilities (infeasibilities are explicitly considered in the objective function, by means of high penalties).

It is possible to differentiate between two kinds of constraints: rows and columns. Row constraints are incorporated in the genetic operators and are therefore always satisfied; column constraints (infeasibilities due to superimpositions or uncovered classes) are managed by means of a combination of fitness function and genetic repair. Single-teacher solutions (i.e. solutions which satisfy a single teacher) are constrained each other by column constraints. Genetic repair must convert infeasible timetables into feasible ones, modifying them as little as possible.

We decided to manage the infeasibilities by means of both filtering and fitness function penalties because in this way the algorithm has a greater degree of freedom in moving through the search space. This choice is due to the difficulty of the problem: in our application, in fact, every teacher represents a TSP-like problem (consisting of the analysis of the permutations of a predefined symbol set), which has a search space of dimension

H where nh is the number of repetitions of the h-th character in the row representing the teacher, and n is the total number of weekly hours. A teacher working in several classes has a value of k greater than that of a teacher working in fewer classes, the total number of teaching hours being the same.

## 5.1.3 The hierarchical structure of the objective function:

The objective function is the basis for the computation of the f.f., which can provide the Genetic Algorithm with feedback. The feedback is used to direct the population towards areas of the search space characterized by better solutions.

The need to distinguish between objective function (o.f.) and the fitness function (f.f.) comes from the necessity to define the o.f. with reference to a cost minimization problem, while the GA has a structure which allows it to solve maximization problems. The transliteration from o.f. into f.f. is obtained by simply mapping the numeric values of the former into those of the latter, by means of a monotonically decreasing function. In particular, our system is based on a linear dynamic fitness

scaling procedure [1] .At each generation the maximum and the minimum objective function values of the individuals of the population are computed (max o.f. and min o.f. in Figure (2i) they define an interval on the o.f. axis which is linearly mapped onto an interval of the f.f. axis, limited by two system constants MINFIT and MAXFIT, in such a way that min o.f. corresponds to MAXFIT and max o.f. corresponds to MINFIT [5]. This procedure attains two objectives: first it minimizes the o.f. while it maximizes the f.f., second, it strongly discriminates solutions belonging to populations whose individuals have very small variations of o.f. values, which is often the case in the late stages of the search process.

Fig.2i - Mapping the o.f. into the f.f.

The o.f. for our problem measures a generalized cost which represents the gap between the timetable considered and an ideal timetable, i.e. a timetable which satisfies all the different

Constraints. The o.f. for timetable R is

Where

â€¢ #inf is the number of infeasibilities in the matrix R;

â€¢ sD measures the rate of dissatisfaction of didactic requirements in the matrix R;

â€¢ sW measures the rate of dissatisfaction of organizational requirements in the matrix R;

â€¢ sP measures the rate of dissatisfaction of teachers' requirements in the matrix R;

â€¢ a, b1, b2, and b3 are weights chosen by the user to bias the timetable towards different aspects.

Choosing a >> b1, b2, b3, we induce a hierarchical structure in the o.f., so that we acknowledge the different relevance of the several groups of problem conditions. In our application, the following structure has been chosen:

Level 1: feasibility conditions s;

Level 2: management conditions (D, W, P);

Level 3: single teacher's conditions.

At level 1 we handle possible superimpositions of teachers (two or more teachers during the same hour in the same class) and "uncovered hours" for the classes (hours when a class is not covered by any teacher).

At second level we consider the three following requirement typologies.

## ï„ï€ - didactic requirements

â€¢ No more than 4 teaching hours a day for each teacher (D1);

â€¢ Not the same teacher every day at the last hour (D2);

â€¢ Uniform distribution of the hours of the same subject over the week (D3);

â€¢ Pairs of hours for class work (D4);

W - Organizational requirements

â€¢ Concentration on the same day (as much as possible) for parent-teacher meeting hours (W1);

â€¢ No less than 2 teaching hours a day for each teacher (W2);

â€¢ As few holes in a teacher's schedule as possible (W3);

## P - Teachers' requirements

â€¢ A weight is chosen, for the full set of requirements of the different teachers (successively defined at level 3) with respect to the other requirements of level 2; moreover, a teacher ranking (based on criteria such as seniority, external engagements, etc.) is defined. At third level we consider the preferences represented by each teacher for his/her specific timetable. Each teacher assesses his/her personal requirements, such as the day-off desired or not having the first or the last hours, and so on. These assessments are then normalized, so that each teacher takes part with a specific quota to the determination of the requirements of the whole teaching staff.

Finally, an additional procedure was designed to compute the f.f. incrementally. In several instances in fact, a timetable of known fitness is modified by simply swapping, for example, two hours or two days. It is therefore worthwhile to maintain the values of some intermediate fitness components, so that only those directly affected by the modifications are computed again.

The algorithm, in Pascal-like notation, is the following:

initialization { this routine creates a population of N individuals, satisfying for every individual a set of constraints: every teacher (row) is given the right amount of hours to be taught. some hours are set to the "fixed hour status", which means they cannot be moved.}

while (NOT_VERIFIED_END_TEST)

do {the end test is on the number of iterations performed}

## begin

apply reproduction;

apply crossover;

for l: =1 to N does

## begin

apply mutation of order k;

apply day mutation;

if (LOCAL_ON) then apply local search {LOCAL_ON is a Boolean variable}

if (num_infeasibilities > MAX_INFEASIBILITIES) then apply filter {MAX_INFEASIBILITIES is a system constant}

## end.

We examine now the operators used by the Genetic Algorithm and their computational complexity. This complexity is a function of:

â€¢ the number N of individuals composing the population,

â€¢ the activation probabilities chosen for each genetic operator,

â€¢ the computational complexity of the f.f., and of the local f.f. (defined below), and the genetic repair (filter) algorithm.

We call FF the fitness function evaluation complexity, and GR the genetic repair (filter) complexity (see Appendix).

We have chosen to explicitly represent the activation probabilities in the complexity formulae because they are user-defined variables which can be set to zero in specific situations, thus heavily affecting the complexity of the operator they refer to.

## Reproduction:

This is the classical reproduction operator that promotes individuals with an above average value of the f.f. It gives every individual h a reproduction probability pr(h) equal to its fitness divided by the total fitness of the population. New populations are generated by using these reproduction probabilities in conjunction with Monte Carlo methods.

The complexity of one application of the reproduction operator to the whole population is then O(FF.N), where FF is fitness function.

## Crossover:

The task of this operator is that of efficiently recombining building blocks (defined below for our case), so that, given two parents, it is possible to generate two offspring with better f.f. values (or at least with one of them with a significantly better f.f. value). We call the local fitness function (l.f.f.).

Given two individuals (timetables) of the population, R1 and R2, the rows of R1 are sorted in order of decreasing l.f.f., and the first-rate k1 rows are taken as a building block. Then, the remaining m-k1 (where m is the number of teachers) rows are taken from R2 to generate the first son. The second son is obtained from the non-utilized rows of R1 and R2. The value of k1 is determined by the program on the basis of the l.f.f. of both parents. This operator is applied in probability to each selected pair of potential parents: the probability of its application is the system parameter pc. The crossover operator is implemented by means of the following algorithm: pair randomly the individuals of the population

for each pair of individuals

## do

with probability pc do begin {pc is a control parameter}

compute the l.f.f. of the rows of the two individuals;

sort by decreasing values of the l.f.f. the rows of the two individuals;

create two sons merging twice the two individuals

{the first son is generated taking the best k1 rows from the better parent and the worst rows from the worse parent; the second son is generated using the remaining unused rows from both the parents};

## end;

The complexity of one application of the crossover operator is O[(N.pc).(m.LFF)], where LFF is the complexity of computing the l.f.f.

Comparison with different crossover rate

## Mutation of order k:

This operator takes k contiguous genes and swaps them with another k contiguous non-overlapping ones belonging to the same row. Mutation of order one is a special case of this operator. It cannot be applied when, among the genes to be mutated, there are some special characters, like A or S (these fixed hours have in fact been allocated, during the initialization phase, to unconvertible activities). This operator is applied in probability to each row of each individual, the probability of its application is the system parameter pmk (pm1 in the case of mutation of order one).

A particular kind of mutation is day mutation, which takes one day and swaps it with another one belonging to the same row. The i-th day, in a teacher timetable, is a substring containing genes that codify five contiguous hours, from the first to the fifth of a same day. It is a special case of mutation 12 of order k and has been introduced for efficiency reasons (with special reference to day-off allocation) and it is controlled by a specific application probability parameter, pmd.

The complexity of one application of the mutation of order k operator to the population is O(N.n.m.pmk), where pmk is the probability of mutation operator.

## Local search:

It works in two stages. In the first it tries to eliminate infeasibilities without worsening second-level costs. This is done using a procedure taken from the filter algorithm - see appendix - that identifies the causes of the infeasibilities and removes them by swaps of hours. The second stage is a 2-opt that swaps hours and days until no better solutions are present in the neighborhood of the current timetable. The operator thus moves a solution to a point of the search space that is locally optimal with respect to a neighborhood defined by every possible swap of hours and of days.

## Filter:

The filter operator takes as input an infeasible solution and returns the output as a feasible one. It is used to ensure global feasibility to a timetable and is based on the observation that in each column that's in hour of the matrix every class must be present once and only once. If it present twice or more times, there's teacher superimpositions. If it were not present, the class would be uncovered. It is based on four procedures of increasing computational cost which are applied sequentially. The first two procedures identify swaps of hours of one teacher that eliminate infeasibilities. More than one teacher modifies the schedules of the other two procedures.

## 5.1.4 Computational results

The program we used for our experiments was written using the C language on an IBM PC with standard configuration. The model and the program were tested by defining the timetable for a large high school in Milan, in which the timetable was handmade by a group of teachers. In the academic year 1992-93 the handmade timetable had a cost of 234. This collaboration has been ongoing, from the design (for requirement definition) until the validation phase, which gave the results reported below. Moreover, to assess the relative efficacy of our approach, we compared our approach with simulated annealing (SA), adapting the indications of Abramson[4], and with tabu search (TS), adapting the approach of Hertz and de Werra[2].

## Parameter settings:

We conducted a number of experiments to determine an efficient parameter setting for our GA. The control parameters tested were:

i) Control probabilities: pm1, pmk and pmd of the different mutation operators, pc of the crossover;

ii) Local search enabled/disabled;

iii) Cost of infeasibilities: it has been set to a high value (1000, one order of magnitude greater than weights for management conditions) or to a low value (3, to ease explorations of infeasible regions).

The first point was tested considering 5 sets of values for each parameter chosen at regular intervals. The range of the intervals would be enlarged if the best performing value resulted to be at one extreme of the range. Five runs were carried out for each value combination, with only one change from the initial setting, performed on a parameter per run. In this way, we could identify a good parameter setting, and the values are reported in Table 2. The

algorithm was found somewhat insensitive when changes of pm1 and pc were held to within Â± 0.2. However, this insensitivity was not evident for changes of pmd (day mutation probability) or pmk, the values of which should be kept very small.

Point (ii) was tested running the algorithm 10 times with local search enabled and 10 times with local search disabled, always using the optimal parameter setting found in point (i)[3]. The average cost of the timetable found without local search was 160.1 (variance s=14.4) with a best cost 138. Meanwhile, the average cost with local search was 111.1 (s=16.2) with a best cost 91. The GA with local search is therefore definitely superior to its counterpart, in accordance with the indications expressed by Muhlenbein[3] .Figure (3) presents the evolution of the best values in the two cases. Both were run lasted eight hours. The difference in the number of generations is due to the computational cost of local search. As a further test, we applied the local search operator to the best timetables found without local search, thus carrying them to their local optima. The average cost of these locally optimized timetables was 157.7 (s=14.4), with a best cost 136. This shows that it is worthwhile to search in the space of the local optima: local optimization of the result of genetic search is not as effective as genetic search among local optima.

## Fig.3 - Perfect values with and without local search.

Finally, tests on point (iii) suggest that a high value for the cost of infeasibilities should be used when local search is off, a low value used when local search is on. In the case in which local search is on, swaps are applied which maximally decrease the cost of the timetable; i.e., the highest-cost which unsatisfied requirements are removed first. When very low infeasibility costs are used, local search tries first to assemble a good timetable from the point of view of second level requirements, and only

later it tries to make it feasible. Since we have an explicit filter operator applied after local search, we observe that, on the average, local search coupled with low infeasibility cost is much more effective than local search coupled with high infeasibility costs. In fact, if infeasibilities had a high cost, local search would first try to recover feasibility, even though this process leads to a great increase of second-level costs. Subsequent local optimization, performed on feasible or quasi-feasible timetables, cannot change these second-level costs much. A further benefit of low infeasibility costs results from the fact that in the first iterations more infeasible timetables survive in the population. This broadens the search region which can be reached from the current population, thus allowing the exploration of otherwise unreachable areas.

The case of Genetic Algorithm without local search yields opposite results. With low infeasibility costs, filtering is always applied intensively, thus dramatically slowing down the search process. The surviving infeasible solutions however are usually the best-rated ones and generate many offspring.

As a final observation, note also that, while exploring promising zones of the search space, the algorithm always identified feasible solutions within very little iteration; very good solutions, however, needed much iteration to be devised.

## 5.1.5 Comparison with other approaches

We provide a comparison with two alternative approaches to evaluate how well our algorithm performs with respect to the state of the art of automatic timetable design. Again, the algorithm was implemented and tested in a high school in Milan. Since we could use any predefined population of solutions as our starting point, we chose the previous year's timetables and adjusted them to meet the new needs. This gave us a proven basis from which to begin, thereby saving computing time and leading to improved solutions with respect to the handmade ones. The PC 386 environment allowed on-site runs, and the carefully designed menu-based user interface allowed the users both to directly interact with the computer in the input phase and to slightly edit the final solution: all these features, beside increasing the effectiveness of the interaction, greatly helped the acceptance of the package by the users.

When we applied our algorithm to the timetable used in the previous year in the school, we were able to better arrange many lessons, so that both some didactical requirements and several teachers' preferences were better satisfied. The total cost of the hand-designed timetable was in fact of 234, while our GA has been able to lower it to 91. Note that we computed for our problem a lower bound of 54 for the cost function, due to the presence of inconsistent single teacher's requirements and fixed hours. For example, so many teachers chose Saturday as desired day-off, which made it impossible to satisfy all of them within a feasible timetable. Therefore, any timetable was bound to reflect costs due to unsatisfied day-off requests. Similarly, some teachers had fixed hours that did not meet their requirements, which again introduced unavoidable costs.

A comparison was carried out with respect to a Simulated Annealing (SA) based timetable designer. We implemented a system following the indications presented by Abramson, using the non-genetic part of our system as objective function evaluator. Given the differences between the specific problems undertaken by Abramson and by us, we had to adapt the SA to work with our fitness function. In particular, we defined the neighborhood of a timetable as we had done in the GA case. Also, the SA was asked to minimize not just the number of infeasibilities, but also didactical, organizational and teachers' requirements. The use of this algorithm in our example problem led to timetables consistently worse than the handmade ones: it could not even recover the initial cost level when it was let evolve from the previous year timetable (final results all had a cost well over 300). And while SA was very efficient in recovering feasible timetables from infeasible ones, it could not effectively optimize feasible timetables. This was true both in the case of high and of low infeasibility costs.

We therefore modified the basic SA in two ways. First, we tested a SA with reinitialization of the temperature. As soon as a timetable got frozen, i.e., when the SA was unable to improve the current timetable since no proposed swap was accepted anymore, the temperature was set to its starting level. The annealing process could then start again from the previously frozen timetable. The best timetable we found with this modified algorithm had a cost of 183. A graph of the cost evolution for the corresponding run is presented in Figure 4, where the lower line plots the evolution of the best so far solution and the higher one the evolution of the current solution.

## Fig.4 - SA with temperature reinitialization.

Alternatively, we tried to relax the problem when the timetable became frozen. We set the infeasibility costs to 3 for a given (parametric) number of iterations after which the normal cost function was applied again. This approach, coupled with a cooling rate of 0.9, yielded a timetable with a cost of 164. A graph of the cost evolution of the "best-so-far" and current solutions for the corresponding 10-hour-long run is presented in Figure 5.

## Fig.5 - SA with temporary relaxations.

Finally, we tested tabu search (TS), following the indications of Hertz and De Werra. We implemented a variable-length tabu list and used part of our system to assess the cost of the timetables, as in the case of SA. The results achieved with this simple model were not very satisfying, so we implemented a relaxation procedure identical to that used with SA. The results so obtained were very good indeed, reliably producing timetables with costs lower than 100, with the best one 85.

A straightforward statement of the constraints serves as a part of the program and it is compared with local search procedures.

Constraints serve's as part of the program. This makes the program easy to modify, which is crucial in real-world problems. Constraint Programming has succeeded in solving standard benchmarks and real-world problems from the area of scheduling.

It is large, highly constrained and much more complicated. Problem differs greatly for different schools and educational institutions. Although manual construction of timetables is time-consuming, it is still widespread, because of lack of appropriate programs.

The constraints are handled through a system of constraint propagation, which reduces domains of variables, coupled with backtracking search. In modern CP languages, both features don't need to be programmed explicitly.

The main disadvantages of this approach are:

difficulties with expressing 'soft' constraints,

Problems with improving the initial feasible solution.

Both local search procedures and CP have advantages and disadvantages therefore it is worth to connect these two approaches to overcome drawbacks. White and Zhang made a successful approach to combine local search with constraint satisfaction. They determined an initial solution using constraint logic programming and then optimized it using tabu search, but it was rather switching between approaches. An idea of this paper is to incorporate local search into constraint programming.

The difficulty of taking into account hard constraints, the determination of their parameters through experimentation. Although they are good for optimizing the initial feasible solution, they have problems with finding it. The constraints are handled through a system of constraint propagation, which reduces domains of variables, coupled with backtracking search. In modern CP languages, both features don't need to be programmed explicitly.

7. Role of Artificial Intelligence

Constraint programming has been emerged from the AI. Which has been becoming an important role in the Time-Tabling programming with constraints allows flexibility for the solution of the problem that helps for the success of Time-Tabling problem. Sometimes the problem's constraints can be modified with the user. This mainly occurs due to the identification of the real constraints for giving effective time-table.

Time-Tabling problem is computationally hard that constraint processing methods are not effective. Constraint logic programming is now tending to manage the automatic backtracking based on heuristics.

8. Conclusion

This paper has presented the constraint propagation that includes backtracking which involves the concept of Arc Consistency for obtaining a constraint-based timetabling.

As it is shown, the proposed algorithm can be near to the optimal solution that gives the better solution.

9. Software Requirements

Microsoft windows XP

Intel core CPU

Java (Jdk1.5)

Web browser (Internet Explorer/Mozilla Firefox)