AKNOWLEDGEMENT

I would like to express my gratitude to my supervisors Michel Gourgand and Christophe Cuax without their help it was impossible to complete this work. I am really thankful to them for their precious time, guidance, patience, motivation and enthusiasm. They were always available for my help whenever I found any difficulty. They were really helpful to solve my administration related problems as well.

Besides my supervisors, I would like to thank Michel Chabrolle for her care and interest in my work. Her comments and guidance played a vital role in the completion of this work. I would also pay my gratitude to my jury members Gulgun Alpan and Ameur Soukhal for their comments and corrections which made this thesis more accurate and give us more ideas for our future work. I am grateful to my examiners for their comments and suggestions.

I would like to extend my gratitude to our Montlucon team for their support. I would never forget their cooperation. I am also thankful to my colleagues of LIMOS with whom I passed a very good time.

My profound gratitude is also for my friends, who were always with me in any time of difficulty. Their company was a source of inspiration and pleasure for me. I would always miss their company and talks.

I would like to extend my gratitude to my parents, brothers, sisters and all relatives whose prayers and good wishes were really important for me while staying abroad.

Last but not least, my profound gratitude is for my wife and daughter who helped me a lot to do this work and facilitated (especially in form of time) me during this work. Table 1. 6.1: Differences and similarities between our HBM algorithm and previous population based algorithms. ''-'' means the method did not use the corresponding operator. .............. 137 Table 6.2: Differences and similarities between our HBM algorithm, HBMO [START_REF] Abbass | A monogenous MBO approach to satisfiability[END_REF] and HBMO-ETP [START_REF] Sabar | A honey-bee mating optimization algorithm for educational timetabling problems[END_REF] 7.2: Frequency or the portion of period-room slots in use, utilisation in terms of used seats in percentage, numbers of edges in conflict graphs (CG), density in conflict graphs (CG) with vertices representing courses rather than events and total unavailability constraints. ... 150 Table 7.3: Aaverage number of conflicts (Co), average teacher availability (TA), average number of lessons per curriculum per day (CL) and average room occupation (RO) ........... 150 Table 7.4

List of Figures

List of Tables

SUMMARY OF THE THESIS

In this thesis we have concerned ourselves with university timetabling problems both course timetabling and examination timetabling problems. Most of the timetabling problems are computationally NP-complete problems [START_REF] Garey | Computers and Intractability: A guide to NPcompleteness[END_REF][START_REF] Pongcharoen | Stochastic optimisation timetabling tool for university course scheduling[END_REF], which means that the amount of computation required to find solutions increases exponentially with problem size. These are idiosyncratic nature problems, for example different universities have their own set of constraints, their own definition of good timetable, feasible timetable and their own choice about the use of constraint type (as a soft or hard constraint).

Unfortunately, it is often the case that a problem solving approach which is successfully applied for one specific problem may not become suitable for others. This is a motivation, we propose a generalized problem which covers many constraints used in different universities or never used in literature. Many university timetabling problems are sub problems of this generalized problem. Our proposed algorithms can solve these sub problems easily, moreover constraints can be used according to the desire of user easily because these constraints can be used as reference to penalty attached with them as well. It means that give more penalty value to hard constraints than soft constraint. Thus more penalty value constraints are dealt as a hard constraint by algorithm. Our algorithms can also solve a problem in two phases with little modification, where in first phase hard constraints are solved. In this work we have preferred and used two phase technique to solve timetabling problems because by using this approach algorithms have broader search space in first phase to satisfy hard constraints while not considering soft constraints at all. Two types of algorithms are used in literature to solve university timetabling problem, exact algorithms and approximation algorithms. Exact algorithms are able to find optimal solution, however in university timetabling problems exact algorithms constitute brute-force style procedures. And because these problems have the exponential growth rates of the search spaces, thus these kinds of algorithms can be applied for small size problems. On the other side, approximation algorithms may construct optimal solution or not but they can produce good practically useable solutions. Thus due to these factors we have proposed approximation algorithms to solve university timetabling problem.

We have proposed metaheuristic based techniques to solve timetabling problem, thus we have mostly discussed metaheuristic based algorithms such as evolutionary algorithms, simulated annealing, tabu search, ant colony optimization and honey bee algorithms. These algorithms have been used to solve many other combinatorial optimization problems other than timetabling problem by modifying a general purpose algorithmic framework. We also have presented a bibliography of linear integer programming techniques used to solve timetabling problem because we have formulated linear integer programming formulations for our course and examination timetabling problems.

We have proposed two stage algorithms where hard constraints are satisfied in first phase and soft constraints in second phase. The main purpose to use this two stage technique is that in first phase hard constraints satisfaction can use more relax search space because in first phase it does not consider soft constraints. In second phase it tries to satisfy soft constraints when maintaining hard constraints satisfaction which are already done in first phase.

As mentioned above, our scientific investigations are related to linear integer programming formulations for generalized university course and examination timetabling problems, transformation of course timetabling problem models to resource constrained project scheduling problem (RCPSP) and metaheuristics to solve timetabling problem. A major part of thesis consists of examining proposed algorithms. From our studies of these mathematical models and algorithms, the following scientific work is made.

• We have proposed two mathematical formulations of course timetabling problem which are the prototype of single-mode RCPSP. The main benefit of these formulations is that these give us the idea of using different durations for lessons in course timetabling and the implementation of precedence constraints through RCPSP to timetabling problem. This work equates the two different problems through mathematical formulation.

• We have proposed a new 0-1 linear integer programming formulation for university course timetabling problem. The mathematical model for the problem provides many operational rules and requirements which are needed in many universities. We have discussed how different objective functions can be deduced from this formulation by using these mathematical relations as a soft constraint.

• Different university environments have been shown as a sub problem of our generalized model. Sub problem mathematical formulations have been deduced from generic model. We have written mathematical equations of objective functions of these problems.

• A new 0-1 linear integer programming formulation for examination timetabling problem is proposed. This generic model is made by gathering many constraints from different university environments in a single problem and by adding some extra constraints which were never used in literature according to our knowledge.

•We have proposed two algorithms to solve course and examination timetabling problem. Our first algorithm is memetic algorithm. Memetic algorithm is a genetic algorithm with local search; we also have proposed a local search for our memetic algorithm. Our second algorithm is honey bee mating algorithm, use of this algorithm in educational timetabling problems is not common. We have discussed in detail differences and similarities between our algorithms and previously used algorithms.

Our thesis is structured as follows.

In Chapter 1 we have given an introduction to the university timetabling problem. We have explained what is timetabling problem and what kind of constraints are used in university timetabling problem. We have discussed similarities of graph coloring problems with educational timetabling problems. We also have given a review of different solution techniques used to solve this kind of problems, concentrating mainly on metaheuristics.

In Chapter 2, we have given a connection of single mode RCPSP with course timetabling problem. This chapter transforms course timetabling problem to RCPSP through two equivalent mathematical formulations proposed by us.

In Chapter 3, we have proposed a generic model for university course timetabling problem.

We have defined different sets, sub sets and parameters to formulate a generalized mathematical model.

In Chapter 4, we have proposed a generic model for examination timetabling problem, this model resembles to the generic model for course timetabling but its structure is different from course timetabling problem.

In Chapter 5, we have discussed about different instances from literature. The formulations of these instances can be made by our generic model for university course timetabling problem.

We have also discussed instances used in literature for examination timetabling problem. We have shown in detail how these instances can be obtained from our model.

In Chapter 6, we have explained in detail our proposed memetic algorithm and honey bee mating algorithm. We have explained how these algorithms work. We have explained in detail our chromosome representation, different operators used and different repair functions.

In Chapter 7, we have solved dataset instances of ITC-2007 with our proposed memetic algorithm and compared our results with the results of techniques used in literature. We have generated data for our generalized problem for both course and examination timetabling. We solve these datasets with our proposed algorithms. After getting results we have discussed about the performance of these algorithms. We have also tested the effect of different parameters and operators on the performance of algorithm.

At the end, we have given summary of the main conclusions which can be drawn from this thesis. Moreover, future research perspectives have been discussed which can give the good ideas for further possible research directions.

We want to keep this thesis at a reasonable length and we write this thesis considering that the reader has some basic knowledge of university timetabling problem and used solution techniques especially metaheuristics. Readers who do not have prerequisite knowledge are invited to study some good texts about these topics. We refer these works for basic understanding of the domain.

• One can find good articles on various different timetabling problems from the website of ASAP group (http://www.asap.cs.nott.ac.uk/?q=bibliography). This website also contains many good publications of the PATAT series (The Practice and Theory of Automated Timetabling).

• One can also find good overviews on the basic principles of metaheuristics on website http://en.wikipedia.org/wiki/Metaheuristic.

• We have given reference of some good surveys on educational timetabling problems, which can be found in the bibliography at the end of this thesis.

Chapter 1

INTRODUCTION

This chapter presents the general overview of timetabling problems, what actually these problems are, how much trouble they can create for scheduler and how many different ways can be used to solve them. In the next Section 1.1, we have discussed different timetabling problems used by research community and expressed how these problems have a significant effect on user's life. In Section 1.2, we have presented different types of educational timetabling problems. In Section 1.3, we have spoken about major types of constraints used in educational timetabling problems. In Section 1.4, we have a categorization of these constraints. In Section 1.5, we have brief detail of different objective functions used in literature. In Section 1.6, we have talked about different neighbourhood structures used for educational timetabling as a part of different metaheuristics. In Section 1.7, we have shown a comparison between simple timetabling problem and another combinatorial optimization problem: graph colouring. In Section 1.8, we have included a detailed review of different methods used to solve various university timetabling problems proposed by researchers in the literature. This chapter's conclusion is given in Section 1.9.

Brief introduction of timetabling problems

Wren [START_REF] Wren | Scheduling, timetabling and rostering -A special relationship, Practice and Theory of Automated Timetabling[END_REF] defines timetabling as follows: ''Timetabling is the allocation, subject to constraints, of given resources to objects being placed in space time, in such a way as to satisfy as nearly as possible a set of desirable objectives''.

Timetables have become very important part of our daily life such as transport, work, sports and education. It is very hard to imagine and organize life in modern society without them.

The construction of workable and attractive timetables is not an easy task in real world cases where one has limited resources like people, space and time. Using limited resources it becomes a challenging problem even for the experienced designers. These timetables have a significant effect on the people who use them. These timetables construction should be as best as one can. Often such type of timetables will be updated or completely rescheduled. School or university timetables will be rescheduled at the beginning of the new academic year, similarly bus or train timetable will be modified to cope with new road layouts and stops. So this is a problem which people and institution will face on regular basis.

Train or railway timetabling is the planning of arrivals and departures of trains at stations and from stations. The objective is to minimize travel times, satisfy user requirements and solve conflicts between different trains. This is the simple theoretical view but in real situation there are many more problems to solve. There could be many additional constraints like when some trains are standing on tracks, some platforms are not available etc. Bus or train timetables show that when a journey will be conducted on any particular routes or paths. It does not tell about which driver or which vehicle will be used. The allocation of derivers and vehicles is the part of scheduling process. So railway scheduling means design of pattern journeys [5,[START_REF] Zhou | Single-track train timetabling with guaranteed optimality: branch-and-bound algorithms with enhanced lower bounds[END_REF].

Employee timetabling is very important when one wants to produce goods to meet some demand in any production system. This type of schedule will take into account the availability of the human resources. So with production schedule an employee schedule should be made simultaneously [START_REF] Guyon | Cut generation for an integrated employee timetabling and production scheduling problem[END_REF]. Employee timetabling will minimize labor costs while production scheduling should insure that production can be done on time.

Nurse rostering problems will arise in hospital practice. This is about personal scheduling and this generates daily schedules for nurses by assigning shifts according to their skills and predefined hard and soft constraints. It can be defined this way " Given a set of shifts and set of nurses over a certain period, assign each shift of nurse subject to a set of constraints" [START_REF] Zhipeng | Adaptive neighborhood search for nurse rostering[END_REF].

The main purpose of this scheduling is to make a plan for nurses who can satisfy nurses and patients. Due to many constraints of conflicting nature and requirements (like coverage demand, consecutive demands of shifts, day off requirements, work load of nurses, weekend related requirements) this is a very difficult problem to solve for hospital's personal managers and for researchers as well.

Sports have great attraction all over the world. Professional sport leagues invest a lot of money in players. Now these games have become multimillion dollar industries. Big events like the Football world cup, Olympic Games and major golf tournaments generate huge television audiences worldwide. Thus the key aspect of this type of scheduling is the assignment of venues and times to different competitions over multiple venues that can satisfy to all those who have interest in these competitions. So constraints of the problem can vary from competition to competition. These requirements could be of different type, each team should play at each station, each team will counter against each other team at least once in tournament etc. [START_REF] Kendall | Scheduling in sports: An annotated bibliography[END_REF].

Main categories of educational timetabling problems

Educational timetabling problems could be divided in main three categories, High school timetabling, University timetabling and Examination timetabling problems. There are some good reviews on the topic in the literature [START_REF] Lewis | A survey of metaheuristic-based techniques for university timetabling problems[END_REF][START_REF] Werra | An introduction to timetabling[END_REF][START_REF] Ahmad | A survey on recent developments in automated timetabling, 12 e congrès annuel de la[END_REF][START_REF] Burke | Recent research directions in automated timetabling[END_REF].

High school timetabling

In high school timetabling each class has a particular lessons and this timetabling is majorly driven by curriculum. Number of hours of each subject per week set nationally. Each class normally has a set of students which will attend same courses all day and a specific teacher will be allocated for each course. Teachers are normally allocated before scheduling so the main purpose is to assign courses of teachers to classes in particular periods.

University timetabling

University timetabling can be formally defined in this way, task of assigning a number of events such as lessons, examinations, meetings and so on, to a limited set of periods (perhaps rooms) in accordance with a set of constraints.

The university course timetabling problem is an assignment of courses to periods and rooms like high school timetabling but major difference between university course timetabling and high school timetabling is that university classes can have common students while school classes have disjoint sets of students. So if two classes have common students these can not be scheduled together in the same period. School teachers most of the time teach more than one class while university professor may teach only one course. In high school timetabling rooms are not a big issue because each class has its own room but in university course timetabling problem rooms have a lot of importance. In university environment some classes need some specific rooms with specific equipment. Room size plays a vital role, one big room can be partitioned into many small rooms and some rooms are not available all times.

Characteristics of university timetabling

The university timetabling problem has special features that highly depend upon the resource arrangement, their availability and other characteristics that the courses taught in a university carry along. A course can have particular requirements, which can be related to periods, teachers, rooms, sessions, arrangement of lessons of the course etc. [START_REF] Daskalaki | An integer programming formulation for a case study in university timetabling[END_REF].

Structure of university courses

A course offered by any institution may consist of just lessons, or lessons and recitations, or lessons, recitations, and/or work in a laboratory. The lessons are delivered by professors, teachers or other teaching staff and it is their choice, how they will carry out them in single or multi period session. Recitations are considered as lessons delivered by the same teacher, while in other cases they may be considered time for exercises to enhance the understanding of the material covered during lessons. In this last case the class is split into many parts and one or more persons are assigned to attend them. Lab work is usually part of a given course or sometimes a course by itself and the group of students is split into several sub-groups for training. Lab work is performed in special type of rooms (special type rooms may be laboratory, computer room etc.) which may need special equipment and professors and assistants are assigned to pursue these lessons. If number of students attending a course is more than a certain limit, course can be divided into sessions, these sessions can be taught by the same teacher and by different teachers depending upon the situation, resources and requirement of the university.

Types of university courses

In many universities courses are categorized in two categories mandatory and electives [START_REF] Daskalaki | An integer programming formulation for a case study in university timetabling[END_REF]. Mandatory courses are compulsory courses which each student should take for his basic training. These courses are more in lower grade years, so these are designed for all students of the same year. Elective courses are less in numbers in lower grade years. So these elective and mandatory courses have common students thus they should be scheduled on different periods.

In higher grade years case is opposite where mandatory courses are less in numbers but elective course are more in numbers. It is common in higher grade years to divide their students in different divisions according to student choices and each division has their own mandatory and elective courses. Then to make schedule for them is hard because some divisions have no common interests and some divisions are sharing courses. Different students may belong to different lab groups or recitation and this will enhance more difficulty in scheduling.

Availability of resources

For the university timetabling problem resources refer to human resources, available periods and classrooms. Availability of human resources is restricted because due to administrative duties and some other projects teachers may not be available all the time. Some faculty members may like some free days or periods during the week. Similarly periods are also not available all the day, scheduler has to spare periods for lunch time or for tutorials etc., some periods are scheduled already due to the choices of faculty members to teach course in a specific period and some periods are forbidden for some courses due to non availability of teachers. Rooms may be of many types and which course uses which type of room depends on course and room type. All rooms will not be vacant all the time because some other departments of the university may be using them for their courses and these are available on specific periods for scheduling.

Rules for timetabling in the university

These basic rules in university timetabling regarded as hard constraints.

1. There is a conflict in a timetable when two or more courses are scheduled at the same period for the same teacher or for the same classroom for the same group of students. Also, when two or more teaching persons are assigned to the same group of students to teach two different courses at the same period; and lastly when two or more classrooms are assigned to the same course and to the same group of students at the same period.

2. A timetable is complete when total number of hours of the course should be scheduled, also teaching load of the teacher should not be more than a certain predefined limit. Similarly, there are rules which are regarded as soft constraints; some of them are given as follows:

1. Preferences for teachers in specific time intervals are satisfied if possible. Each faculty member can express his/her preference for his/her course. For example one does not want to teach course on Friday and other prefer to teach his/her courses in morning session.

2. Students' schedule should be as compact as possible; however there should be empty periods for lunch. So called difficult courses should be scheduled earlier in the day then others should be scheduled. If one lesson of a course is scheduled in a day then if any other lesson of the same course is assigned to the same day, it should be compact with previous one.

3. If one course is scheduled in any room first time, it should be scheduled in the same room next time.

Examination timetabling

The examination timetabling is an assignment of events where now events are examination. It is same as course timetabling but has few differences with course timetabling problem.

Normally each course has one examination. Major difference of this timetabling with course timetabling is that if a lesson is scheduled in a room then this room will not host any other lesson in that period. But in examination timetabling a room can host more than one examination depending upon the capacity of the room and the availability of invigilator. In course timetabling one teacher can teach only one lesson per period but in examination timetabling one examination can be supervised by more than one invigilator. Restrictions are strict in examination timetabling like we can think that a student is enforced to skip his course due to overlapping in schedule but it is not possible to skip examination. In course timetabling, scheduler makes a timetable for a week and repeats it for other weeks, means that course timetabling has fixed set of periods but in examination timetabling problem number of used periods can be relaxed.

The timetabling problem, like many others in the area of combinatorial optimization, has been approached by several well-known techniques of the operational research and the computer science fields. Several surveys on course timetabling [START_REF] Carter | Recent developments in practical examination timetabling, Practice and Theory of Automated Timetabling[END_REF][START_REF] Schaerf | A survey of automated timetabling[END_REF], which focus other aspects of the problem also have managed to record this work in a systematic way by categorizing the different variations of the problem and solution approaches.

Different types of constraints

In university timetabling, a set of lessons would be scheduled into rooms and periods subject to constraints that are usually divided in two categories, which are hard and soft constraints.

Constraints and their importance however differ significantly among countries and institutions. A timetable is considered to be effective when it is useable and may be considered satisfactory by the institution when it carries certain quality characteristics that keep its users satisfied at least to a certain degree.

Hard constraints

Hard constraints must be strictly satisfied and have higher priority than soft constraints. A time table will be called feasible if it satisfies all hard constraints. Event clash constraints perhaps are considered common hard constraints in educational timetabling problems. These constraints normally occur when there is a resource which is only one and is required by two events at the same period which is impossible. This constraint exists in almost every educational institution, for example courses taken by some common students could not be scheduled in the same period.

Soft constraints

Soft constraints fulfillment is not obligatory like hard constraints but these are the constraints which scheduler wants to obey if possible, but these will decide the quality of the timetable according to the timetabling policies of university concerned and by the users who will use these timetables (like students, teachers etc.).

Categorization of constraints into five main classes

Despite the wide range of these different constraints, these constraints can be categorized into five main classes. This classification was suggested by Corne et al. [START_REF] Corne | Evolving timetables in the practical handbook of genetic algorithms[END_REF].

Unary constraints

These are the constraints which involve only one event. For example event c should be scheduled on Monday or event c should be scheduled on any last period of the day. This type of constraints can occur both in course and examination timetabling. It can be both hard and soft.

Binary constraints

These are the constraints which involve pairs of events. For example event c should be scheduled before event d or two events c and d can be scheduled in same period. This type of constraints can occur both in course and examination timetabling. It can be both hard and soft.

Capacity constraints

These constraints are about capacity of rooms. If a course c is scheduled in a room then the number of students taking course c should be less than or equal to the capacity of the room. This type of constraints can occur both in course and examination timetabling. It can be both hard and soft.

Event spread constraints

This is a constraint which talks about spreading out or clumping together events. There are some time requirements that lessons of a class should be scheduled together or examination of a class should be scheduled after a gap of g periods. So these constraints can be in both course and examination timetabling and these are normally soft constraints.

Agent constraints

These constraints are about the preference of the people who will use this timetable, for example teacher a wants two free mornings, some classes want their language courses should be scheduled in evening session, these constraints are used normally as soft constraints.

From this whole analysis it is clear that each institution has a wide range of their own preference and requirements which can entirely be different from other institutions. It is entirely understandable that each institution has their own needs and timetabling policies, for example one institution wants that course should be clump together because institution have some more courses to schedule for part time students and other institution wants that events of a student should be spread out within the week as much as possible, so these two scenarios are entirely different than each other.

If we look timetable from an optimization perspective, it tells us that if one wants to get a workable timetable in a limited time, this will depend upon the problem instance. There are some universities which have fairly loose requirements, have a lot of resources (like many rooms, less classes, less courses, etc.) and fewer events to schedule. In this scenario it is easy to find many workable solutions from the search space. On the other hand, some universities may have more demanding requirements, a huge work load and fewer resources in comparison with requirements, so in this scenario there will be very less workable solutions in the search space of the problem instance. In practice, sometimes constraints of the problem are so complex and are making problem impossible to solve that scheduler has to relax some of them. So to solve harder problems we need some robust and powerful methods for tackling these sorts of problems.

Objective Functions

Different types of objective functions had been used in literature. In this section we shall write some of them which were used commonly by different authors. These objective functions were used for course timetabling problem.  To spread out examinations over the exam period for each student  Minimize the distance between rooms of an exam that is being held in multiple rooms and to minimize splitting an exam over several rooms  Minimize the assignment cost and penalty for exceeding the maximum work load of invigilators  Minimize the cost function Similar to course timetabling problems, exam timetabling problems had also been used objective functions with weighted sum of penalties of soft constraints.



Next section talks about neighbourhood structures in detail because we have used neighbourhood based algorithms for our experiments.

Neighbourhood Structures

One of the most important features of a local search algorithm is the definition of its neighbourhood. In local search procedure new solution X  mv is obtained by using a move mv to a candidate solution X. Thus a neighborhood N of X can be defined by, N(X) = {X  mv / mv M(X)}, where M(X) is the set of all possible moves which can be applied to X.

We can find many type of neighbourhood used for timetabling problem [START_REF] Zhipeng | Adaptive tabu search for course timetabling[END_REF].

Simple swap

Some authors have used simple swap, which have further two types. First one swaps any lesson from to any null slot (Figure 1.1b) and the second one swaps course 1 c to the place of

Room swap neighborhood

This is neighborhood where the move would take place in a same period, means that lessons of one period will swap with each other. If presentation is a matrix of rooms (R) and periods (P), periods are the columns of matrix and rooms are the rows of the matrix (Figure 1.2). Then the lessons will swap in the same column. Benefit of this type of move is that after getting feasible solution, it will not become infeasible.

Time swap neighborhood

This explores the moves that select a lesson and swap it horizontally (Figure 1.3), this means that chosen lesson will use same room but in any other period. By using this one is becoming much more specific and it will put a restriction on search space. It can be used partially as neighborhood but overall it is not advisable. The simple swap move is the generalization of

Kempswap neighborhood

This move was defined by Zhipeng Lü and Jin-Kao Hao [START_REF] Zhipeng | Adaptive tabu search for course timetabling[END_REF] and is called kempswap. A kemp swap is the interchange of two kemp chains. Course can be seen as lessons and conflicts and we can write them in form of a graph. Nodes are courses and edge between two courses is the conflict between these courses. This means that these courses could not be scheduled in a same period. A kemp swap produces a feasible assignment by swapping periods assigned to courses belonging to one or two specified kemp chains.

Let 1 K and 2 K be two kemp chains in the subgraph of two periods i p and j p . A kempswap produces an assignment by replacing

i p with )) ( ( )) _( ( 2 1 2 1 K K p K K p j i     and j p with )) ( ( )) _( ( 2 1 2 1 K K p K K p i j    
. According to definition at least three courses should be involved.

We can illustrate the procedure by Figure 1.4 which is showing that this sub graph is obtained by two different periods and five kemp chains,

 1 K { 5 6 11 12 , , , c c c c },  2 K { 4 7 10 , , c c c },  3 K { 1 2 9 , , c c c },  4 K { 8 c },
( ( ) _ ( K p K p j i   and j p with ) ( ( ) _ ( K p K p j j  
where K is a non empty kemp chain. For example in Figure 1.4a, if we take the non empty

 1 K { 5 6 11 12 , , , c c c c },  2 K { 4 7 10 , , c c c },  3 K { 1 2 9 , , c c c },  4 K { 8 c },  5 K { 3 c } Figure 1.4: Kemp chain illustration
This list of neighborhoods was used by many authors [START_REF] Sadaf | A Memetic Algorithm for the University Course Timetabling Problem[END_REF][START_REF] Daskalaki | Efficient solutions for a university timetabling problem through integer programming[END_REF] in literature, which are used to define genetic operators for genetic algorithm and also for constructing local searches for the sake of quality improvement of the solution. We have also used some of them for our local search method.

 N1: Select two lessons at random and swap periods.

 N2: The neighbourhood defined by an operator that moves one lesson from a period to a different one.

 N3: the neighbourhood defined by an operator, a lesson can be moved only if the corresponding period is empty.

 N4: Select two periods at random and simply swap all the lessons in one period with all the lessons in the other period.

 N5: Move the highest penalty lesson from a random 10% selection of the lessons to a random feasible period.

 N6: Carry out the same process as in N5 but with 20% of the lessons.

 N7: Move the highest penalty lesson from a random 10% selection of the lessons to a new feasible period that can generate the lowest penalty cost.

 N8: Carry out the same process as in N7 but with 20% of the lessons.

 N9: Select two periods based on the maximum enrolled lessons, say i t and j t . Select the most conflicted lesson in i t and j t and then swap them.  N10: the neighbourhood defined by an operator that swaps the periods of two lessons  N11: the neighbourhood defined by an operator that permutes three lessons in three distinct periods in one of the two possible ways other than the existing permutation of the three lessons.

One can also define particular swap moves as time swap, room swap depending on the representation of the solution.

Graph colouring and timetabling problem

Timetabling problem has a resemblance with graph colouring problem. This was the basic reason that many early techniques used in timetabling algorithms were derived directly from graph colouring-based heuristics. One can see some of these from the review of Carter [START_REF] Carter | A survey of practical applications of examination timetabling Algorithms[END_REF]. Now we explain how a timetabling problem can be solved with graph colouring. Given a simple and undirected graph G having n set of vertices, where V= {

n v v v ,...., , 2 1
} is a set of n vertices and E is the set of edges which joins different pairs of vertices of set V. This is a NP hard problem [START_REF] Garey | Computers and Intractability: A guide to NPcompleteness[END_REF] which finds an assignment of colours for every vertex in V such that (i) vertices with common edge can not be assigned same color (ii) target is to find a solution which uses the minimum number of colours. It is easy to convert the simplest timetabling problems to graph colouring problems (and vice-versa) by considering vertices as events and edge between any pair of vertices shows that there is a conflict between these lessons. So edge between any pair of vertices cannot have same colour. Then each colour in Graph colouring represents a period available for timetabling problem. Now task with respect to graph colouring problem is to use maximum colours which should be less or equal to the available periods for timetabling problem [START_REF] Werra | Graphs, hypergraphs and timetabling[END_REF][START_REF] Burke | Applications to timetabling[END_REF]. Construction of timetable by graph colouring is shown in Figure 1.5.

The term "chromatic number" number (commonly denoted χ ) is used in graph colouring problems to refer the minimum number of colours which are required to colour a particular problem feasibly. Obviously for simple timetabling problem this means that the minimum number of required periods to schedule a clash free timetable for a particular problem.

The Clique is the second parallel that can be drawn between these two problems, which involves the identification of the features. A clique is a collection of vertices which are mutually adjacent, for example vertices 1, 3, 4, 6, and 7 in Figure 1.5 (b); this is a clique of size 5. It is worth noting that real world problems which uses graph colouring often have fairly large cliques. In many real world problems there are many events which are required not to be scheduled in the same period. In graph coulouring the vertices representing these events make a clique and it is trivial that no two vertices in this graph colorling could be assigned the same colour (or equivalently all events of a clique should be assigned different periods). So it can be deduced easily that for any graph colouring or timetabling problem if the maximum size of a clique is C then to make a feasible (that is χ ≥C) timetable minimum C colours are required [START_REF] Garey | Computers and Intractability: A guide to NPcompleteness[END_REF].

As mentioned earlier, graph coluring problem only exists when one is considering hard conflicting constraints. When other type of constraints such as room type constraints, ordering constraints etc. are added in the problem then it will add extra complications. However, regardless of this nearly all timetabling problems are featuring this graph colouring problem in some form or another form in their work. Many timetabling problem algorithms are still using various bits of heuristic information extracted from this graph colouring problems as a driving force to achieve their solutions [START_REF] Lewis | Metaheuristics For University Course Timetabling[END_REF] . (a) Given a simple timetabling problem having 10 lessons to schedule by using minimum number of periods, first problem is converted into its graph colouring equivalent.

(b) A solution is then found, which uses five colours (optimal number of colours) for this problem.

p Q  .
The component of trivial course timetabling is given in [START_REF] Burke | Decomposition, reformulation and diving in university course timetabling[END_REF]. Three courses are given Juggling,

Resolution techniques

Two techniques had been used in the literature to solve timetabling problems, namely exact methods and heuristic methods. In this section we shall present literature review on these two methods.

Exact methods

Exact methods consist of formulating and finding solution with integer programming models.

Exact methods may not work to find optimal solution especially in short computing times for large size problem. This makes the reason to develop heuristics to get good solutions in moderate limit of time. We have presented generalized formulations for exam and course timetabling problems so we shall discuss integer programming techniques used in literature.

Integer programming techniques

Linear integer programming techniques have also been used to solve educational timetabling problems such as the algorithm of Carter [START_REF] Carter | A langarian relaxation approach to the classroom assignment problem[END_REF], Tripathy [START_REF] Tripathy | School timetabling -A case in large binary linear integer programming[END_REF] in the 1980s and Breslaw [START_REF] Breslaw | A linear programming solution to the faculty assignment problem[END_REF] provided a solution for the faculty assignment problem, a problem closely related to the timetabling problem, using linear programming models in the 1970s. The same problem was studied by McClure and Wells [START_REF] Mcclure | A mathematical programming model for faculty course assignment[END_REF] and a solution was attempted again with the help of mathematical programming. Hultberg and Cardoso [START_REF] Hultberg | The teacher assignment problem: A special case of the fixed charge transportation problem[END_REF] formulated teacher assignment problem as a mixed integer programming problem and solved as a special case of the fixed charge transportation problem.

Among the first approaches in mathematical programming, in [START_REF] Badri | A multi-objective course scheduling model: Combining faculty preferences for courses and times[END_REF] the teacher assignment problem is combined with a form of the timetabling problem and solved through commercial software for goal programming. In a similar manner, Gosselin and Truchon [START_REF] Gosselin | Allocation of classrooms by linear programming[END_REF] provided a linear programming formulation for the classroom allocation problem, a sub-problem of the university timetabling. Integer programming formulations for the school and the university timetabling problems as optimization problems are also discussed by Werra in [START_REF] Werra | An introduction to timetabling[END_REF], where the NP-completeness of both problems is shown even for simple versions. The author, however, chooses graph theory approaches for the solution of the problems under consideration. Extensions to this work, especially with regards to the so-called conflict matrix are presented by Tripathy in [START_REF] Tripathy | School timetabling-A case in large binary integer linear programming[END_REF]. Given the difficulties of those days to solve large integer programming problems, the Lagrangean relaxation was proposed as a possible solution approach for the resulting model.

Many other articles have also used these techniques. Schimmelpfeng and Helber [START_REF] Schimmelpfeng | Application of a real world university course timetabling model solved by integer programming[END_REF] described an integer programming approach which has been implemented at the School of Economics and Management at Hannover University, Germany, to create the complete timetable of all courses for a term and formulation was solved with CPLEX solver. Broek et al. [START_REF] Broek | Timetabling problems at the TU Eindhoven[END_REF] have divided the timetabling problem into four sub problems which are formulated as an integer linear programming problem. The goals of the four divided sub problems are specific as: maximize the number of assigned courses with urgency, maximize the total assigned workload, minimize the shortage of students to reach the minimum number of students of a section, optimize the timetable. The models introduced were solved by IP solver CPLEX.10.0. Boland et al. [START_REF] Boland | New integer linear programming approaches for course timetabling[END_REF] applied blocking strategy, in which the classes can be partitioned into sets of classes (or blocks) that will be timetabled in parallel. The problem of constituting the blocks and populating the classes is known as the course blocking and population problem. This formulation was made for high school timetabling and model was implemented in the modeling language AMPL, and solved using the ILOG package CPLEX 8.0.

Birbas et al. [START_REF] Birbas | Timetabling for Greek high schools[END_REF] presented a 0-1 integer programming model for the timetabling problem of Greek high schools. In their model, a binary variable indicates whether or not a specific lesson to be taught by a given teacher is to be held at a specific time of the week. The model generates timetables that satisfy all the hard and soft constraining. Werra [START_REF] Werra | An introduction to timetabling[END_REF] presented some basic models for course timetabling problem and these were described with an emphasis on graph theoretical models. Mingozzi et al. [START_REF] Mingozzi | An exact algorithm for the resource-constrained project scheduling problem based on a new mathematical formulation[END_REF] presented a 0-1 linear programming formulation that requires an exponential number of variables corresponding to all feasible subsets of activities that can be simultaneously executed. Hassani [START_REF] Hassani | A computational approach to enhancing course timetabling with integer programming[END_REF] has developed an integer programming approach and solved the timetabling problem for Shahrood University of Technology, Iran. This approach was implemented on the problem of scheduling of 8 terms of graduation students. Two terms mean that the course which every student would take in one year. In order to solve the above problem, he formulated it with AIMMS using some identifiers.

Daskalaki et al. [START_REF] Daskalaki | An integer programming formulation for a case study in university timetabling[END_REF] presented integer programming formulation for university timetabling problem. The timetable for the Electrical and Computer Engineering Department in the University of Patras was used as a case study. Yakoob and Sherali [START_REF] Yakoob | Mathematical programming models and algorithms for a class-faculty assignment problem[END_REF][START_REF] Yakoob | A mixed-integer programming approach to a class timetabling problem: A case study with gender policies and traffic considerations[END_REF] addressed a faculty-class assignment problem, periods for classes are initially assumed to be given and then integer programming model is constructed to minimize the individual and collective dissatisfaction of faculty members. Their second article's main focus is to design efficient class offering patterns while taking into consideration newly imposed gender policies. The both models were solved with CPLEX. Daskalaki and Birbas [START_REF] Daskalaki | Efficient solutions for a university timetabling problem through integer programming[END_REF] considered the institutions which provide three to five year study program and provide a quite well structured curricula for their students. In this article author presents a two stage algorithm to solve this kind of problems. In the first stage they relax some constraints and solve them in second stage. They are relaxing courses compactness (if lessons of same course are scheduled on the same day they should be adjacent to each other) constraint at the first stage because in their opinion these constraints are computationally heavier than the others. These constraints are recorded in the second stage and sub problems, one for each day of the week are solved for local optima.

Daskalaki et al. presented [START_REF] Daskalaki | An integer programming formulation for a case study in university timetabling[END_REF] an integer programming where problem was solved with modeling process result to solvable and flexible models. The flexibility was obtained by the multi-dimensional variables which allow details of the educational system to be modeled as constraints of the integer programming model. A variety of constraints could be represented by using this model. In order to check the capabilities of the proposed model for solving timetabling problem, the department of Electrical and Computer Engineering at the University of Patras was chosen. This is one of the largest departments in the Engineering School and has a five year program for students. During the first three years the students follow a general education program in Electrical and Computer Engineering and in the last two years each student join one of the four divisions of the department for specialization. Natashia Boland et al. [START_REF] Boland | New integer linear programming approaches for course timetabling[END_REF] discussed the solution which uses the procedure of blocking.

Blocking is a set of classes which can be partitioned into subsets in such a way that all classes of a block can be scheduled in parallel. Each such type of subset is called block. Their method will induce a partition of the sessions available for the timetable in such a way that none of these sessions can be used for classes in other blocks. This means that each session will use only their block classes. This avoids the clashes to occur within blocks, and in this way it removes the clash conflict constraints. This further divide problem into two sub problems: the class blocking and population problem (CBPP) and the block timetabling problem (BTP).

Class blocking and population problem means to make block of the given problem and block timetabling problem schedule the all blocks.

Metaheuristic methods

In this section we shall discuss about different metaheuristic techniques to solve educational timetabling problems. As we are going to propose two population based algorithms so we shall talk in detail about these algorithms. We have given a detailed review of evolutionary algorithms and Honey bee algorithms. We shall give a brief review of other techniques, which we found in literature like ant colony optimization, tabu search, simulated annealing and local search.

We shall also discuss some other techniques such as neural networks, hyper heuristics, these techniques can be considered as metaheuristic techniques. There are many good surveys on educational timetabling problems in the literature in the past including survey conducted by Carter and Laporte [START_REF] Carter | A survey of practical applications of examination timetabling Algorithms[END_REF][START_REF] Carter | Recent developments in practical examination timetabling, Practice and Theory of Automated Timetabling[END_REF] and Burke et al. [START_REF] Burke | The automation of the timetabling process in higher education[END_REF][START_REF] Burke | Recent research directions in automated timetabling[END_REF][START_REF] Burke | Examination timetabling in british universities: A Survey, Practice and Theory of Automated Timetabling (PATAT[END_REF]. Other timetabling surveys can be found at [START_REF] Carter | Recent developments in practical course timetabling[END_REF][START_REF] Ross | Advances in Evolutionary Computing: Theory and Applications, topic: Genetic algorithms and timetabling[END_REF][START_REF] Schaerf | A survey of automated timetabling[END_REF], by Lewis and by Qu et al. [START_REF] Lewis | A survey of metaheuristic-based techniques for university timetabling problems[END_REF][START_REF] Qu | A survey of search methodologies and automated system development for examination timetabling[END_REF].

Tabu search algorithms

Abdullah et al. [START_REF] Abdullah | An investigation of a genetic algorithm and sequential local search approach for curriculum-based course timetabling problems[END_REF] combined their genetic algorithm with sequential combined local search.

In first step they find initial solutions for population pool by using these three heuristics: large degree heuristic, local search and tabu search. In this way they constructed feasible timetables for their population. Then results were improved by using genetic algorithm, in this algorithm single point crossover was used. After cross over and mutation they used local search heuristic to improve offspring.

Zhipeng Lu and Jin Kao Hao [START_REF] Zhipeng | Adaptive tabu search for course timetabling[END_REF] present a tabu search algorithm about curriculum based course timetabling problem which was the part of International timetabling completion 2007.

Their algorithm has three stages namely initialization, intensification and diversification. In first phase they generate feasible initial solution and to achieve this task they use greedy heuristic starting from an empty timetable. During this process at each time one adequate lesson is inserted into the timetable. At each step two distinct operations were done, first is to choose an unassigned lesson and second is to find appropriate place (room, period) for this lesson. For lesson selection they use greedy colouring heuristics and when lesson has been chosen they select period for this lesson by using this heuristic.

They select period which is least likely to be used by other unassigned lessons on the next steps. They have used two neighborhood namely simple swap and kamp swap. They start tabu search algorithm by simple swap and when they get solution best local optima, they again start tabu search algorithm with other neighbourhood when using local optimum solution as an initial solution. Their intensification phase minimizes the soft constraints without breaking hard constraints any more. Their diversification criteria based on local search provide such mechanism which guides the search to escape from the current local optimum and move the solution towards new promising solutions.

In this article [START_REF] Abdullah | On the use of multi neighbourhood structures within a tabu based memetic approach to university timetabling problems[END_REF], a Tabu-based memetic algorithm is proposed by Salwani Abdullahand and Hamza Turabieh which hybridises a genetic algorithm with a Tabu Search algorithm as an improved algorithm for university timetabling problems. This algorithm uses a set of neighbourhood structures during the search process to obtain improvements in solution quality. They propose a sequence of neighbourhood structures to understand its effect on the search space. They evaluate random, best and general sequences of neighbourhood structures in this work. Those neighbourhood structures are penalized which do not generate better solutions. In this article Batenburg and Palenstijn [START_REF] Batenburg | A new exam timetabling algorithm[END_REF] used evolutionary and tabu search algorithm in parallel. They show that for large problems using a parallel variant of tabu search with genetic algorithm shows significant improvements in the obtained timetable comparatively to the memetic algorithm. But this procedure will enhance the run times.

Local search algorithms

Duong Tuan Anh et al. [START_REF] Duong | Generating complete university course timetables by using local search methods[END_REF] proposed a two stage algorithm, in which first stage will get feasible solution not having any hard constraint and in second stage they try to minimize soft constraints. In first they use backtracking free constructive method with local search and look ahead. The local search used in first stage is Minimum Conflict Hill Climbing with dynamic constraint weighing mechanism. For improving the initial feasible solution produced at first stage was improved in second stage by using two candidate local search methods. Hill climbing algorithm is a first candidate method where local minima was escaped by using stochastic strategy. Hill climbing algorithm also is a second candidate method where local minima was escaped by using short term memory strategy.

Edmund Burke [START_REF] Burke | Decomposition, reformulation and diving in university course timetabling[END_REF] wrote this article about partial solutions achievements when trying to get a good time table where task is to minimize soft constraints. This article covers an approach of such problems which could be a multiphase exploitation of multi objective sub models. In this problem at first step only one difficult component of problem and related objective function is taken. This would find a partial solution which would further define interesting neighbourhood in the search space of the entire problem. Variable aggregation can be performed by picking the initial component at the first stage and by exploring neighbourhoods at next stage to ensure feasible solutions. Then it is easy to use integer programming to implement heuristics to produce solutions with bounds on their quality. This study was performed on International timetabling competition track whose datasets comes from Udine university (Italy).They use objective restricted neighbourhood generator in their heuristic for the assignments of periods to lessons, with minimizing the violations of two period related soft constraints. Patrick De Causmaecker [START_REF] Causmaecker | A decomposed metaheuristic approach for a real-world university timetabling problem[END_REF] represents a decomposed heuristic for solving a university course timetabling problem. The datasets were taken from KaHo Saint-Lieven School of Engineering. They use the technique to make pillars of similar lessons to make problem less complex. In this way no doubt search space will become smaller than original search space.

Then this problem was solved by sequentially evaluating the constraints one by one by using the procedure that solution obtain in one stage will be used in the next stage as an initial solution. In fact soft constraints were minimized one by one and by using this procedure they get good results for their problem compared to solve all constraints at once. Ersoy [START_REF] Ersoy | Memetic algorithms and hyper hill-climbers[END_REF] proposed a combination of hill-climbing and memetic algorithms as a hyper-heuristic framework. They tested its performance on the Carter benchmark datasets. The results showed that a memetic algorithm based hyper-heuristic using a single hill climber at a time gave the best results among other variants of hill climbing hyper-heuristics proposed by the same authors.

Qu and Burke [START_REF] Qu | Hybridizations within a graph-based hyper-heuristic framework for university timetabling problems[END_REF] constructed a unified graph-based meta-heuristic (GHH) framework, upon which a number of local search-based algorithms as the high level heuristics are studied to search upon sequences of low-level graph coloring heuristics. To gain an in-depth understanding on their framework, they addressed some fundamental issues concerning neighborhood structures and characteristics of the two search spaces, the search spaces of the heuristics and the actual solutions. Furthermore, they investigated efficient hybridizations in GHH with local search methods and mentioned issues concerning the exploration of the highlevel search and the exploitation ability of the local search.

Jacques A. Ferland and Alain Lavoie [START_REF] Jacques | Exchanges procedures for timetabling problems[END_REF] also used a heuristic iterative procedure where assignment of one event can be modified at each iteration. This is an exchange procedure, which applies first to find a feasible solution (satisfying hard constraints) and then it improves the objective function value. A geometrical interpretation of the exchange is given to understand the theoretical framework of the procedure. Two more procedures are introduced to avoid jumping outside the feasible domain or at local optimum. The first procedure relies on Lagrangean relaxation and second one uses inductively more than one exchange per iteration.

Simulated annealing algorithms

Simulated Annealing algorithm was initially proposed by Kirkpatrick et al. [START_REF] Kirkpatrick | Optimization by simulated annealing[END_REF] for solving combinatorial optimization problems. Simulated annealing procedure is prevented by accepting deteriorating moves that worsen the objective function value. In this way search procedure can be protected by getting trapped with a local optimum. This algorithm application in timetabling problem can be found in works by Abramson [START_REF] Abramson | Constructing school timetables using simulated annealing: sequential and parallel algorithms[END_REF] and Bullnheimer [START_REF] Bullnheimer | An examination scheduling model to maximize students[END_REF]. A review of Simulated Annealing algorithms for solving the University Course Timetabling Problem can be found in Kostuch [START_REF] Kostuch | The university course timetabling problem with a three-phase approach[END_REF]. Abramson [START_REF] Abramson | Constructing school timetables using simulated annealing: sequential and parallel algorithms[END_REF], Melicio and Caldeira [START_REF] Melicio | Implementation aspects of simulated annealing on timetabling[END_REF] and Elmohamed et al. [START_REF] Elmohamed | A comparison of annealing techniques for academic course scheduling, Practice and Theory of Automated Timetabling (PATAT[END_REF] proposed simulated annealing algorithms.

Elmohamed et al. [START_REF] Elmohamed | A comparison of annealing techniques for academic course scheduling, Practice and Theory of Automated Timetabling (PATAT[END_REF] considered the timetabling problem of Syracuse University in the USA and used a weighted-sum scoring function which penalized violations of the hard constraints. They also used general simulated annealing practices to enhance the algorithm performance.

Merlot et al. [START_REF] Merlot | A hybrid algorithm for the examination timetabling problem[END_REF] proposed a three stage approach for solving examination timetabling which consisted of constraint programming, simulated annealing and then hill climbing.

Constraint programming was used to construct a feasible timetable. The other two stages were used to minimize the soft constraints through the use of simulate annealing and a hillclimber using Kempe chain interchanges. The algorithm was tested by using real-world problem datasets from the University of Melbourne and also for various benchmark problem datasets such as the Carter datasets. Defu Zhang et al. [START_REF] Zhang | A simulated annealing with a new neighborhood structure based algorithm for high school timetabling problems[END_REF] presented a simulated annealing based approach which used new extended neighborhood structure obtained by performing a series of swaps of pairs of assignments during two periods. This algorithm was tested on high school timetabling problems. Sara Ceschia et al. [START_REF] Ceschia | Design, engineering, and experimental analysis of a simulated annealing approach to the post-enrolment course timetabling problem[END_REF] also presented a simulated annealing approach for a post enrolment course timetabling problem. Their solution was based on a relatively simple single-step algorithm. They used preprocessing, constraint reformulation for the improvement of the local search and room assignment procedure based on attractiveness which allowed them to refrain from using the matching algorithm. Their single-step procedure considers the soft constraints from the very beginning and it can save computational time.

Aldy Gunawan [START_REF] Gunawan | A hybridized lagrangian relaxation and simulated annealing method for the course timetabling problem[END_REF] proposed which used Lagrangian relaxation and a simulated annealing algorithm. They used Lagrangian relaxation approach to generate initial feasible solutions in the construction phase. Simulated annealing algorithm was used for the improvement of initial feasible solutions. Thompson and Dowsland [31] proposed a two phase simulated annealing algorithm. The first phase finds a feasible solution and second phase satisfies the secondary objectives and soft constraints. They discuss in detail about the parameter used to control the algorithm and how to model a simulated annealing framework for successful implantations by using judicious choices in both areas. They tested different neighborhoods and cooling schedules over a data from various institutions. They concluded that neighborhoods based on the graph-theoretic concept of Kempe chains are the most efficient regardless of the objectives or size of the problem.

Great deluge algorithms

Turabieh et al. [START_REF] Turabieh | Electromagnetism-like mechanism with force decay rate great deluge for the course timetabling problem, Rough Set and Knowledge Technology (RSKT 2009)[END_REF] proposed a great deluge algorithm for university course timetabling. This depends upon attraction-repulsion movement for solutions in the search space. Algorithm starts with a population of randomly generated feasible initial solutions and an attractionrepulsion mechanism is used to check the quality of the great deluge algorithm. Then a great deluge algorithm is applied to increase the solution quality. This algorithm's performance was also tested on Socha datasets. Fukushima Makoto [START_REF] Makoto | A hybrid algorithm for the university course timetabling problems[END_REF] proposed a hybrid algorithm which includes Simulated Annealing, Local Search and Great Deluge to perform for solving the university course timetabling problem. The Great Deluge algorithm (GD) is a generic algorithm applied to optimization problems. It is similar in many ways to the hill-climbing and simulated annealing algorithms. The name comes from the analogy that in a great deluge a person climbing a hill will try to move in any direction that does not get his/her feet wet in the hope of finding a way up as the water level rises.

In a typical implementation of the GD, the algorithm starts with a poor approximation, S, of the optimum solution. A numerical value called the badness is computed based on S and measures how undesirable the initial approximation is. The higher the value of badness the more undesirable the approximate solution is. Another numerical value called the tolerance is calculated based on a number of factors, often including the initial badness.

A new approximate solution S', called a neighbour of S, is calculated based on S. The badness of S', b', is computed and compared with the tolerance. If b' is better than tolerance, then the algorithm is recursively restarted with S: = S', and tolerance: = decay (tolerance) where decay is a function that lowers the tolerance (representing a rise in water levels). If b' is worse than tolerance, a different neighbour S* of S is chosen and the process repeated. If all the neighbours of S produce approximate solutions beyond tolerance, then the algorithm is terminated and S is put forward as the best approximate solution obtained [START_REF] Dueck | New optimization heuristics the great deluge algorithm and the record-torecord travel[END_REF]. In [START_REF] Makoto | A hybrid algorithm for the university course timetabling problems[END_REF] they proposed two enhancements in their algorithm, where one of three soft constraints is satisfied when obtaining a feasible timetabling solution and a few parameters for escaping local minima are introduced in the Great Deluge algorithm which is used for reducing the violations of the soft constraints.

Shaker and Abdullah [START_REF] Shaker | Incorporating great deluge approach with kempe chain neighbourhood structure for curriculum-based course timetabling problems[END_REF] presented curriculum based course timetabling (CB-CTT) problem and they solved it by a hybridization of great deluge algorithm with kempe chain neighbourhood structure. The problem was solved in two steps, in first step they used a graphbased heuristic to construct a feasible timetable and in second step they improve their feasible solution by employing a hybrid approach. The algorithm was tested on the curriculum-based course timetabling problems as described in the 2 nd International Timetabling Competition (ITC2007).

Population based algorithms

Many population based algorithms have given good performance in educational timetabling problems. In this section, we discuss different population based techniques and their variants.

Ant colony algorithms

Socha et al. [START_REF] Socha | A MAX-MIN Ant system for the university course timetabling problem[END_REF][START_REF] Socha | Ant algorithms for the university course timetabling problem with regard to the state-of-the-art[END_REF] used the ant colony optimisation metaheuristic to university course timetabling problem. They proposed two ant-based algorithms, an Ant Colony System and a MAX-MIN system. They gave a qualitative comparison between them. Every ant first constructs a complete assignment of events to periods using heuristics and pheromone information, at each step in both of the algorithms. Then local search procedure was used for further improvements of timetables. The major differences between the two approaches are the way that heuristic and pheromone information is interpreted, and the approaches used for updating the pheromone matrix. However MAX-MIN system generally gave better results when experiments were conducted on a range of problem instances.

Clemens Nothegger et al. [START_REF] Nothegger | Solving the post enrolment course timetabling problem by ant colony optimization[END_REF] proposed a new approach to solve the problem of Post Enrolment Course Timetabling by using Ant Colony Optimization. In this algorithm ants successively construct solutions based on pheromones (stig-mergy) and local information.

The main feature of this algorithm was the use of two distinct but simplified pheromone matrices for improving performance but still provide enough edibility for effectively guiding the solution construction process. Furthermore a local improvement method was embedded and algorithm was applied to datasets used for the First and Second International Timetabling Competition (ITC 2002 and ITC2007). Michael Eley Max-Min [START_REF] Eley | Some experiments with ant colony algorithms for the exam timetabling problem, Ant Colony Optimization and Swarm Intelligence[END_REF] presented ant colony algorithm and used ANTCOL approach. They compared the performance of this algorithm with other approaches presented in the literature and with modified graph coloring algorithms.

He tested his algorithm on examination timetabling problem.

Michael Eley [START_REF] Eley | Ant algorithms for the exam timetabling problem[END_REF] proposed two more ant colony algorithms which were applied simultaneously to construct and improve examination timetables. The first algorithm was (MMASET) based on the MAX-MIN Ant System. This algorithm was used by [START_REF] Socha | Ant algorithms for the university course timetabling problem with regard to the state-of-the-art[END_REF] for course timetabling problems. The second algorithm was (ANTCOL-ET) a modified version of ANTCOL. This was originally used by [START_REF] Costa | Ant can colour graphs[END_REF] to solve graph coloring problems. Dowsland and Thompson [START_REF] Dowsland | Ant colony optimization for the examination scheduling problem[END_REF] proposed Ant colony optimization algorithm for the examination scheduling problem. It built on an existing implementation for the graph colouring problem to make non conflicting timetables and went on to consider the introduction of a number of additional practical constraints and objectives. They modified and improved the original algorithm. They tested the performance of proposed algorithm on carter bench mark datasets.

Partical swarm optimization algorithm

Der-Fang Shiau [START_REF] Shiau | A hybrid particle swarm optimization for a university course scheduling problem with flexible preferences[END_REF] proposed a new meta-heuristic algorithm that is based on the principles of particle swarm optimization for course scheduling problem by designing an 'absolute position value representation for the particle, allowing instructors that they are willing to lesson based on flexible preferences, the maximum number of teaching-free periods and the lecturing format and employing a repair process for all infeasible timetables. Furthermore, a local search mechanism is incorporated into the proposed PSO in order to explore a better solution improvement.

Ioannis and Beligiannis [START_REF] Ioannis | A hybrid particle swarm optimization based algorithm for high school timetabling problems[END_REF] have proposed hybrid particle swarm optimization (PSO) based algorithm for high school timetabling problems. This algorithm has produced feasible and efficient high school timetables. They have used real world data coming from many different Greek high schools for their experimental work. The performance of this algorithm is better than existing approaches applied to the same school timetabling input data while using the same evaluation criteria.

Qarouni-Fard et al. [START_REF] Qarouni | Finding feasible timetables with particle swarm optimization[END_REF] have proposed the particle swarm optimization algorithm to the classic timetabling problem. Their algorithm is inspired by approaches belonging to the evolutionary paradigm where involved metaheuristic is tweaked to suit for the problems such as timetabling, graph coloring or bin packing. For evolutionary algorithms, it means to substitute the "traditional operators" with newly defined operators that evolve fit groups rather than fit items. Authors have applied a similar idea for their PSO algorithm and performance of proposed algorithm is better in comparison with previously used approaches.

Genetic algorithms

Evolutionary algorithms have been extensively and successfully used to solve timetabling problems since their first applications to timetabling problems at the beginning of the 1990s. Now we explain some main stages of evolutionary algorithms which are performed during the execution of these algorithms.

Initialization

Evolutionary algorithms have been extensively and successfully used to solve timetabling problems since their first applications to timetabling problems at the beginning of the 1990s.

Genetic algorithms are used generally with an initial population. This initial population sometimes is generated randomly and sometimes by using special techniques to make a higher quality initial solutions for population [START_REF] Carter | A survey of practical applications of examination timetabling Algorithms[END_REF][START_REF] Abdullah | A hybrid evolutionary approach to the university course timetabling problem[END_REF][START_REF] Tavares | Infected genes evolutionary algorithm[END_REF][START_REF] Cote | A hybrid multi-objective evolutionary algorithm for the uncapacitated exam proximity problem[END_REF]. After getting the initial solution repairing can be mainly done on violation of hard constraints. We have shown in (2) Choose the unscheduled course with the smallest number of possible room-period pairs to which it can be feasibly assigned in the current timetable.

(3) Choose an unscheduled course randomly.

(4) Choose the period that the least number of other unscheduled courses could be feasibly assigned to this period in the current timetable.

(5) Choose the place that defines the period with the fewest events in.

(6) Choose a room period pair randomly. [START_REF] Guyon | Cut generation for an integrated employee timetabling and production scheduling problem[END_REF]Those courses have priority which has small number of available periods and a large number of unassigned lessons. This heuristic is akin to the greedy colouring heuristic [START_REF] Brelaz | New methods to color the vertices of a graph[END_REF].

Once a lesson of a course is chosen then for period selection this criterion is used, select a period among all available ones that is least likely to be used by other unfinished courses at later steps [START_REF] Zhipeng | Adaptive tabu search for course timetabling[END_REF][START_REF] Rossi-Doria | An hyperheuristic approach to course timetabling problem using an evolutionary algorithm[END_REF]. We have given a procedure of such type heuristic to form initial solutions for population Figure 1.9.

Selection

Build (tt, U).

If (len (tt) < t)

2. Open (tlen (tt)) new timeslots; 3. Insert-Events (tt, U, 1, len (tt));

Insert-Events (tt, U, l, r).

1. While (there are events in U with feasible places in tt between timeslots l and r) 2. Choose an event e from U that has feasible places in tt;

3. Pick a feasible place p for e; The most used selection operators are described as follows.

(

1) Elitism

This method is used to select the best chromosome or a few best chromosomes for the next population. This procedure can increase algorithm performance very quickly because it preserves the best found solutions [START_REF] Chakraborty | On the use of genetic algorithm with elitism in robust and nonparametric multivariate analysis[END_REF].

(

2) Roulette Wheel Selection

This procedure is a probability based method where better chromosomes have the more chances of selection. It could be understood by a simple example, consider a roulette wheel where all chromosomes are placed in the population. Every chromosome has its place as big as fitness function value is good, it is shown in the following picture [START_REF] Mitchell | An Introduction to Genetic Algorithms[END_REF] (

3) Tournament Selection

A specific number of chromosomes are selected from the population, and the one having the best fitness value will go for the next generation [START_REF] Michalewicz | Genetic Algorithms + Data Structures = Evolution Programs[END_REF][START_REF] Pillay | An informed genetic algorithm for the examination timetable problem[END_REF].

Cross over

In the following we will now describe the different crossover operators used in our experiments.

(

1) One-point crossover

First of all a single crossover point on both parents organism strings is selected. Then all data beyond that point is swapped in either organism string between the two parent organisms. The The Uniform Crossover checks each gene in the parent strings for exchange with a probability of 0.5. So each gene of both parents has equal chance of selection. The evidence suggests that it is a more exploratory approach to crossover than the traditional approaches that maintains longer schemata [START_REF] Chawdhry | Soft computing in engineering design and manufacturing[END_REF][START_REF] Michalewicz | Genetic Algorithms + Data Structures = Evolution Programs[END_REF][START_REF] Goldberg | Genetic Algorithms in Search, Optimization and Machine Learning[END_REF].

N-point crossover is quite different from the Uniform crossover. N-point crossover exchanges material between points of parents chromosome strings but in uniform crossover each parents gene has a probability of changing, for example if probability is 0.5 it means that both parents have equal chance of giving gene to child chromosome. After cross over, mutation is normally performed.

Reproduction

Reproduction is the procedure of making new children to bring new population. There are generally two types of reproduction: generational reproduction and steady-state reproduction.

(

1) Generational reproduction

The whole of a population is replaced at each generation in generational reproduction. The procedure which is often used is N/2 times. This means, produce two offspring from selected two parents (according to the selection procedure) and finally produce N new chromosomes where N is the population size [START_REF] Bratkovic | University course timetabling with genetic algorithm: a laboratory exercises case study, Evolutionary Computation in Combinatorial Optimization[END_REF][START_REF] Özcan | A memetic algorithm for solving a timetabling problem: An incremental strategy[END_REF][START_REF] Rossi-Doria | A memetic algorithm for University Course Timetabling[END_REF].

(

2) Steady-state reproduction

This method selects two parents according to the selection procedure, generates one or two children and installs the result back into that population; the least fit of the population is destroyed. These off springs are the only generated solution for this generation [START_REF] Naseem | A guided search genetic algorithm for the university course timetabling problem[END_REF][START_REF] Daskalaki | Efficient solutions for a university timetabling problem through integer programming[END_REF][START_REF] Rossi-Doria | An hyperheuristic approach to course timetabling problem using an evolutionary algorithm[END_REF].

Genetic algorithms in educational timetabling

Sadaf Naseem Jat and Shengxiang Yang [START_REF] Naseem | A guided search genetic algorithm for the university course timetabling problem[END_REF] proposed a guided search genetic algorithm, i.e., GSGA for solving the university course timetabling problem. This is a steady state genetic algorithm where a guided search strategy and a local search technique are integrated; Chiarandini et al. [START_REF] Chiarandini | An effective hybrid algorithm for university course timetabling[END_REF] used local search method for their algorithm as well. Steady state genetic algorithm means that only one child solution is generated per iteration/generation. Useful information are stored in guided search strategy. These information contained room, period pairs of those lessons for which there is no hard or soft constraints violation. These information are used to guide the generation of child into the next population. Local search is used to improve the quality of individuals by using three neighborhood structures.

Bratkovic [START_REF] Bratkovic | University course timetabling with genetic algorithm: a laboratory exercises case study, Evolutionary Computation in Combinatorial Optimization[END_REF] used a genetic algorithm to solve laboratory exercises timetabling problem. This algorithm used especially crafted crossover and mutation operators that are closed over the space of feasible solutions and these genetic operators are designed to satisfy only hard constraints. A local search was used to reduce the soft constraints and it improves the solution quality.

Olivia Rossi-Doria and Ben Paechter [START_REF] Rossi-Doria | An hyperheuristic approach to course timetabling problem using an evolutionary algorithm[END_REF] described a steady state evolutionary algorithm with binary tournament selection and random mutation. One point crossover is used to make offspring. This algorithm evolves the choice of the heuristics to be used at each step of the building process of a timetable. This idea was originally published in Blum et al. [START_REF] Blum | A GA evolving instructions for a timetable builder[END_REF]. This genetic algorithm proposed by Hitoshi Kanoh and Yuusuke Sakamoto [START_REF] Kanoh | Knowledge-based genetic algorithm for university course timetabling problems[END_REF] uses installed knowledge base and an infection operation. The knowledge base means set of candidate partial solutions of the final solution which are built from past years timetables and about request of teachers related to their work choices. So in this way current timetable can preserve the advantages of past timetables. This algorithm performance is tested on the timetables of University of Tsukuba. Amin Jula and Narjes Khatoon Naseri [START_REF] Jula | Using CMAC to obtain dynamic mutation rate in a metaheuristic memetic algorithm to solve university timetabling problem[END_REF] presented a new hybridized genetic algorithm by adding local search algorithm. They applied Cerebellar model of Articulation Controller (CMAC) as a trainable machine to calculate and update mutation rate related to different possible states in the process of algorithm execution. CMAC is a neural network that simulates the structure and functions of a part of the brain called Cerebellum. CMAC model is based on associative memory cells and searching table. Their experimental results obtained showed that heuristics applied in this approach lead to better solutions with CMAC.

Dilip Datta et al. [START_REF] Datta | Solving class timetabling problem of IIT Kanpur using multi-objective evolutionary algorithm[END_REF] presented the problem of preparation of class timetable in IIT Kanpur, India. The entire timetable is composed of two phases. The first phase contains all the common compulsory classes of the institute, which are scheduled by a central team. The second phase contains the individual departmental classes. The evolutionary algorithms have been exploited in this article to schedule the classes. They showed that using NSGA-II-UCTO, a multi-objective EA-based university class timetable optimizer, a number of trade-off solutions, in terms of multiple objectives of the problem, could be obtained.

The significance of crossover while finding global optimal in maintaining diversity has been identified in M.Nandhini [START_REF] Nandhini | Performance analysis of diversity measure with crossover operators in genetic algorithm[END_REF] and found that combination of grade selection with combinatorial Partially Matched Cross over of better performance. Sadaf Naseem Jat and Shengxiang Yang [START_REF] Naseem | A guided search genetic algorithm for the university course timetabling problem[END_REF] state a guided search algorithm for the university course timetabling problem, where guided search strategy and local search is integrated to solve the datasets. The guided search strategy uses a data structure to store full information about events. This data structure (memory) does not store whole timetables but it stores some best scheduled events from the timetable. Data structure is regularly maintained after few generations. This data structure can be formed by selecting N set of best individuals from the whole population.

Then take one individual solution to check its all events that whether its penalty is zero or not, if its penalty is zero then all information about this event like room and period will be added in the data structure. Then next individual solution will be picked and all information about each zero penalty event will be added in the data structure. Then these data structure information are used to guide the generation of children for the next population. Then author uses a local search technique to improve the individual solutions searching through their neighborhood structures in the solution space.

Adaptive genetic algorithms are GAs in which the parameters like population size, crossover probability or mutation probability can be varied while the GA is in progress. A simple example can be the following, the mutation rate is not fixed in the population but it changes according to the performance of the algorithm. If the fitness of the population does not improve for long time, the mutation rate increases. A lower mutation rate is chosen again if the population shows an improvement as described in Zafer Bingul [START_REF] Bingul | Adaptive genetic algorithms applied to dynamic multiobjective problems efficient combination of genetic operators[END_REF].

It is important to use appropriate values for parameters such as mutation rate, crossover rate and population size to get good performance of genetic algorithms [START_REF] Goldberg | Genetic Algorithms in Search, Optimization and Machine Learning[END_REF]. So selection of these parameters has a wide range to get best solutions [START_REF] Reardon | Fuzzy logic versus niched pareto multiobjective genetic algorithm optimization[END_REF]. So some authors used the technique of varied based parameters (these parameters were adjusted during the run) for genetic algorithms which varied according to the performance of the genetic algorithm [START_REF] Bingul | Evolutionary approach to multiobjective problems using adaptive genetic algorithms, Systems, Man, and Cybernetics[END_REF][START_REF] Bingul | Genetic algorithms applied to real time multiobjective optimization problems[END_REF]. It is observed that solver takes low mutation rate, high crossover rate at the beginning of the algorithm and high mutation rate and low crossover rate towards the end of the run. The reason behind is that at the beginning they want to go towards good solutions and take mutation rate less. But when research goes towards end, solution gets stuck and they increase mutation rate for getting diversity. The relationship between population features and GA parameters are very complex and non-linear [START_REF] Bingul | Adaptive genetic algorithms applied to dynamic multiobjective problems efficient combination of genetic operators[END_REF].

Burke, E.K [START_REF] Burke | Hybrid variable neighbourhood approaches to university exam timetabling[END_REF] proposed a variant of variable neighbourhood search for solving examination timetabling problems. Genetic algorithm was used to select a subset of neighborhoods. They tested the performance of algorithm on the Carter benchmark problem datasets. Pillay and Banzhaf [START_REF] Pillay | An informed genetic algorithm for the examination timetable problem[END_REF] presented a two-stage informed genetic algorithm for examination timetabling problems. First phase got feasible solutions and second stage was used to eliminate soft constraint violations. In both phases genetic algorithm was used to construct solution and then to improve it.

Landa-Silva and Obit [START_REF] Landa-Silva | Evolutionary non-linear great deluge for university course timetabling, Hybrid Artificial Intelligent[END_REF] proposed an evolutionary non-linear great deluge algorithm for course timetabling problem. Tournament selection was used as a selection operator. Better improved individual was replaced with worst individual in population. Algorithm performance was tested on the Socha datasets and results showed that the hybridization between the non-linear great deluge and evolutionary operators produced good quality results. This algorithm is similar to the one given by Abdullah [START_REF] Abdullah | A hybrid evolutionary approach to the university course timetabling problem[END_REF].

A simple example of genetic algorithm

We take a simple example to show how basic components of genetic algorithm work through optimization of a function. The function is defined as f (x) = x sin (1/x). The objective is to find a minimum for this function on the interval [0, 0.5], i.e. to find a value 0

x such that f ( 0 x )

≤ f (x) ∀x∈ [0,0.5].
The first derivative of this function is as follows.

0 ) / 1 cos( ) / 1 sin( ) (     x x x x f
We can find the maximum or the minimum values of a function by equating its first derivative to zero.

We can write its first derivative in the following form as well.

1 ) / 1 tan( ) (    x x x f
And it shows that there are infinite many solutions. However we want to solve it with genetic algorithm.

Representation

A chromosome is a binary vector and represents a real number. This binary vector has 32-bits since the processor allows this number. This means that the length of the domain of variable x, which is 0.5 in this example, is divided It can be easily noticed that (0000000000000000000000000000000) and

(11111111111111111111111111111111) represent the boundaries of the domain, 0 and 0.5 respectively.

Initial population

The initial population consists of 10 random chromosomes in form of binary vectors each of 32 bits. Following are the 10 chromosomes Objective function has an important role as it gives information about good solutions in terms of fitness. These are fitness values of the chromosomes in our population:

obj ( c1 ) = f(x1) = -0.214885912 obj ( c2) = f(x2) = 0.172565550 obj ( c3 ) = f(x3) = 0.410983902 obj ( c4) = f(x4) = -0.132941257 obj ( c5 ) = f(x5) = -0.086269622 obj ( c6) = f(x6) = -0.160509512 obj ( c7 ) = f(x7) = -0.185396112 obj ( c8) = f(x8) = 0.286388252 obj ( c9) = f(x9) = -0.088302975 obj ( c10 ) = f(x10) = 0.228031778
We can see that the fittest chromosome in the population is chromosome c1 because it gives the smallest value and c3 is the worst chromosome with the highest fitness value.

Genetic operators

There are two classical operators in genetic algorithm namely crossover and mutation. One point crossover is applied on two fittest chromosomes c1 and c7. We choose a random number, say 21 for crossover point. This means that we split the chromosomes at the 21st gene and then we exchange the parts of the chromosomes as given below:

c1 = (011011100100101100011 | 11111101001) c7 = (011001010001101101011 | 01011110000)
We get these two children from parents:

o1 = (01101110010010110001101011110000) o2 = (01100101000110110101111111101001)
Now the fitness of these new chromosomes and their corresponding real values can be calculated as following.

f(o1) = f(0.21541676) = -0.214885813 f(o2) = f(0.19747604) = -0.185400708
The first child o1 has a better fitness value than its parents however this improvement can be seen till ninth decimal point.

The next step is to mutate the children to get better chromosomes. For this purpose, we select 6 random genes and change their values. The bit value '1' is changed to '0' or vice

versa.

An example of this type of mutations is given below:

o1 = (01101110010010110001101011110000) o1m = (01110010110010110001101011110110) o2 = (01100101000110110101111111101001) o2m = (01111001100110110101111111101111)
After applying mutation, we re-calculate the fitness of these new chromosomes and the corresponding real values below:

f(o1m) = f(0.22420582) = -0.217113164 f(o2m) = f(0.23751354) = -0.208197846
It is easy to notice that objective function value of mutated children is better than their parents also from children which are not mutated. These mutated children act as parents for the next generation, this means that each iteration starts with a better population. Thus genetic algorithm finds optimal or near optimal solutions gradually by this way. In this example, we have explained only one iteration.

Memetic algorithms

Population based algorithms have been used to solve educational timetabling problems in the literature. Cote et al. [START_REF] Cote | A hybrid multi-objective evolutionary algorithm for the uncapacitated exam proximity problem[END_REF] proposed an evolutionary algorithm to minimize the timetable length and the conflicting examinations as much as possible. They used two local searches (tabu search and variable neighbourhood descent) instead of recombination operators to deal with hard and soft constraints violations. However replacement of recombination operators with two local searches increased number of parameters that should be tuned.

Ersoy et al. [START_REF] Ersoy | Memetic algorithms and hyper hill-climbers[END_REF] proposed a combination of hill-climbing and memetic algorithms as a hyperheuristic framework. They tested its performance on the Carter benchmark datasets. The results showed that a memetic algorithm based hyper-heuristic using a single hill climber at a time gave the best results among other variants of hill climbing hyper-heuristics proposed by the same authors.

Salwani Abdullah et al. [START_REF] Abdullah | A hybrid evolutionary approach to the university course timetabling problem[END_REF] employed evolutionary algorithm together with local search. The main technique used in this evolutionary algorithm is a light mutation operator followed by a randomised iterative improvement algorithm. The crossover operator is not used in this approach. The local search approach discussed in Abdullah et al. [START_REF] Abdullah | Using a randomised iterative improvement algorithm with composite neighbourhood structures for the university course timetabling problem[END_REF] is used as the operator and is applied after the mutation takes place; similar work was also done by Soolmaz

Massoodian and Afsaneh Esteki [START_REF] Massoodian | A Hybrid Genetic Algorithm for Curriculum Based Course Timetabling[END_REF].

Ender Özcan and Alpay Alkan [START_REF] Özcan | A memetic algorithm for solving a timetabling problem: An incremental strategy[END_REF] solved a University Exam Preparation School Timetabling Problem (PSTP), this is a course timetabling problem. A memetic algorithm is used as an incremental multistage approach. At each stage a new subset of unscheduled events is selected using some criteria. Within a population of candidate solutions unscheduled events for the selected subset of events are randomly generated. This population is exposed to the memetic operators and whenever some termination criteria are satisfied, then another new subset of events is chosen. This procedure is repeated until all unscheduled events are scheduled and some additional termination criteria are satisfied. The size of individuals incrementally increased as the new subsets of events is added for optimization at each stage.

In this way, no portion of the search landscape is ignored.

Olivia Rossi-Doria and Ben Paechter [START_REF] Rossi-Doria | A memetic algorithm for University Course Timetabling[END_REF] proposed a memetic algorithm to solve university course timetabling problem, which uses the representation and local search, due to Socha and Chiarandini [START_REF] Chiarandini | An effective hybrid approach for the University Course Timetabling Problem[END_REF][START_REF] Socha | The influence of run-time limits on choosing ant system parameters[END_REF].This algorithm is a Steady-State evolution algorithm, proposed by Withley [START_REF] Whitley | A Different Genetic Algorithm[END_REF], where only one offspring solution is produced from two parents at each generation. Local search is used in two phases, where first phase makes an infeasible timetable feasible by reducing the number of periods used and second phase is used to improve the quality of a feasible timetable by minimizing the number of soft constraint violations. This algorithm uses constructive heuristics as used in [START_REF] Carter | Examination timetabling: Algorithmic strategies and applications[END_REF][START_REF] Terashima | Evolution of constraint satisfaction strategies in examination timetabling, genetic and evolutionary computation conference[END_REF] to make initial solutions for initial population.

Ender Ozcan et al. [START_REF] Ozcan | The interleaved constructive memetic algorithm and its application to timetabling[END_REF] proposed a hybrid method, ''Interleaved Constructive Memetic Algorithm'' (ICMA) that interleaves memetic algorithms with constructive methods. This algorithm starts working by using an active subset of all the lessons. In multiple construction stages ICMA increases the active sub sets one by one and eventually include all of them starting with single set. At each stage a memetic algorithm is used to improve the quality of current partial solution before the next construction stage. This algorithm is used to solve Preparation School Timetabling Problem (PSTP).

Ricardo Santiago-Mozos et al. [START_REF] Santiago | A two-phase heuristic evolutionary algorithm for personalizing course timetables: a case study in a Spanish university[END_REF] proposed a two-phase heuristic evolutionary algorithm to construct personalizing timetables. They tackle the problem of assigning a feasible and personalized timetable for every student. Students are allowed to choose a set of priority courses and non-priority courses. Priority courses will always be assigned. This algorithm uses two-phase heuristic with evolutionary algorithm to solve course timetabling problem.

First phase of heuristic is used for the assignment of priority courses and when this task is done then the second heuristic manages the non-priority course's assignment. This algorithm is used to make personalized timetables of the School of Telecommunications Engineers, Universidade de Vigo (Galicia, Spain).

Honey bee algorithms

We have proposed a honey bee algorithm for educational timetabling problem. In this section we present some details about the algorithm. There are two major types of Honey bee algorithms. First type is a honey bee colony algorithm which was mostly used to solve educational timetabling problems [START_REF] Alzaqebah | Artificial bee colony search algorithm for examination timetabling problems[END_REF][START_REF] Nguyen | A hybrid algorithm of harmony search and bees algorithm for a university course timetabling problem[END_REF][START_REF] Alzaqebah | The bees algorithm for examination timetabling problems[END_REF]. The honey bees colony Algorithm was introduced in 2005 by Pham et al. [START_REF] Pham | The Bees Algorithm[END_REF][START_REF] Pham | The Bees Algorithm -A novel tool for complex optimisation problems, Intelligent Production Machines and Systems[END_REF]. Honey bee colony algorithm is about the food collection of the bees. It is a nature inspired algorithm [START_REF] Frisch | Bees: Their Vision, Chemical Senses and Language[END_REF][START_REF] Seeley | The wisdom of the hive: The social physiology of honey bee colonies[END_REF][START_REF] Bonabeau | Swarm Intelligence: From Natural to Artificial Systems[END_REF][START_REF] Camazine | Self-Organization in Biological Systems[END_REF][START_REF] Pham | The Bees Algorithm -A novel tool for complex optimisation problems, Intelligent Production Machines and Systems[END_REF].

Figure 1.14: Original HBMO for SAT [START_REF] Abbass | A monogenous MBO approach to satisfiability[END_REF] The second type is honey bee mating optimization (HBMO) algorithm [START_REF] Sabar | A honey-bee mating optimization algorithm for educational timetabling problems[END_REF]. This was proposed by Abbass in 2001 [START_REF] Abbass | A monogenous MBO approach to satisfiability[END_REF][START_REF] Abbass | Marriage in honey-bee optimization (MBO): A haplometrosis polygynous swarming approach[END_REF]. This naturally inspired algorithm simulates the process of real honeybees mating. It was successfully used for solving job shop scheduling, data Define M, E(t), and S(t) to be the spermatheca size and the queen's energy and speed at time t respectively Initialize the queen's genotype at random select a worker at random, apply it to improve the queen's genotype, and update its fitness while the stopping criteria are not satisfied t = 0, generate a drone at random initialize E(t) and S(t) randomly and the energy reduction step ° to 0:5£E(t)

M while E(t) > 0 evaluate the drone's genotype if the drone passes the probabilistic condition, and the queen's spermatheca is not full, then add the drone's sperm to the queen's spermatheca

t = t + 1; E(t) = E(t -1) - ; S(t) = 0:9* S(t -1)
with a probability of S(t) flip each bit in the drone's genotype end while for brood = 1 to total number of broods select a queen in proportion to her fitness and a sperm from that queen at random generate a brood by crossovering the queen's genome with the selected sperm mutate the generated brood's genotype use a worker selected in proportion to its fitness to improve the drone's genotype update the worker's fitness based on the amount of drone's improvement end for if the best brood is better than the queen then replace the queen with the best brood kill all broods end while mining, 3-sat, integrated partitioning/scheduling, stochastic dynamic programming and continuous optimization, nonlinear constrained and unconstrained optimization problems [START_REF] Baykasoulu | Artificial bee colony algorithm and its application to generalized assignment problem[END_REF]. We have given pseudo code of original honey bee mating algorithm in Figure .1.14.

The strength of this algorithm is to explore simultaneously and exploit problem search space. This is achieved by the queen's transition in the search space and employing a local search at each iteration. These features of honey bee algorithms make it different from other population based algorithms that had been used on educational timetabling problems [START_REF] Burke | A memetic algorithm for university exam timetabling[END_REF][START_REF] Socha | Ant algorithms for the university course timetabling problem with regard to the state-of-the-art[END_REF][START_REF] Pillay | An informed genetic algorithm for the examination timetable problem[END_REF]. Honey bees are selected to create the population of the initial hive. Previous work [START_REF] Qu | A survey of search approaches and automated system development for examination timetabling[END_REF][START_REF] Lewis | A survey of metaheuristic-based techniques for university timetabling problems[END_REF][START_REF] Sabar | Tabu exponential Monte-Carlo with counter heuristic for examination timetabling[END_REF][START_REF] Sabar | Roulette wheel graph colouring for solving examination timetabling problems[END_REF][START_REF] Ayob | Solving a practical examination timetabling problem: a case study[END_REF] showed that in many cases, random generation methods may not necessarily guarantee a good quality in some cases. Therefore, in this work, we employ heuristics which are described in later chapter (Chapter 7) to generate an initial population of drones.

Review of Honey bee algorithms

Alzaqebah and Abdullah's [START_REF] Alzaqebah | Artificial bee colony search algorithm for examination timetabling problems[END_REF] article speaks about how to use artificial bee colony for solving the examination timetabling problems. This algorithm works with three categories of bees namely employed, onlooker and scout bees. Employed bees fly around the search space to find food source and come back in hive to share collected information with onlooker bees.

Onlooker bees relay on these information and they choose their food source according to these information.

Brief review of RCPSP

Francisco Ballestin et al. [START_REF] Ballestın | Pre-emption in resource-constrained project scheduling[END_REF] study the case when pre-emption is allowed for processing jobs. The generalized case of this problem is m_PRCPSP, which means that one job can be pre-empted at most m times but case studied in this paper is 1_PRCPSP, for reason, it is easy and also if one pre-empted in more time, objective function normally does not improve.

Sonke Hartmann and Dirk Briskorn [START_REF] Hartmann | A survey of variants and extensions of the resourceconstrained project scheduling problem[END_REF] give an overview over extensions of the RCPSP such as multiple modes, minimal and maximal time lags. The extensions are classified according to the structure of the RCPSP. They summarize generalizations of the activity concept, of the precedence relations, of the resource constraints and discuss the notations, models and classification schemes. Sonke Hartmann and Rainer Kolisch [START_REF] Hartmann | Experimental evaluation of the state of the art heuristics for the resource constrained project scheduling problem[END_REF] first present a literature survey. They discuss about X-pass method, in which they use SGS (Serial schedule generation scheme). Here they present the results and find out the performance of many state of the heuristics on some benchmark datasets. They compare the results and point out the most performing procedure.

Ana Viana and Jorge Pinho [START_REF] Viana | Using metaheuristics in multiobjective resource constrained project scheduling[END_REF] used multiobjective metaheuristics to solve the resource constrained project scheduling problem (RCPSP). They applied multiobjective versions of simulated annealing and tabu search inorder to minimise the makespan, lateness of activities and the violation of resource constraints. They checked the performance of these metaheuristics on randomly generated instances. The benefit of this multiobjective version is that it is near to real world problems where many objectives are required to achieve.

Job shop scheduling problem is a special case of resource-constrained project scheduling problem. Peter Brucker et al. [START_REF] Brucker | Resource-constrained project scheduling: Notation, classification, models, and methods[END_REF] presented a classification scheme compatible with machine scheduling. Project scheduling researchers used a variety of symbols to denote one and the same subject. So there is a gap of notations and classification scheme between machine scheduling and project scheduling and also a lot of articles are publishing which makes this problem more worst. Authors tried to minimize this gap and presented a classification scheme (description of the resource environment, the activity characteristics, the objective function etc.), compatible with machine scheduling. They also reviewed some recent developments in exact and heuristic algorithms for the single-mode and the multi-mode RCPSP.

Krzysztof Fleszar and Khalil Hindi [START_REF] Fleszar | Solving the resource-constrained project scheduling problem by a variable neighbourhood search[END_REF] proposed a solution method based on variable neighbourhood search. They coded solution by using activity sequences which are available in form of precedence constraints. These sequences became valid active schedules through a serial scheduler. The solution is coded by using activity sequences that are valid in terms of precedence constraints. The sequences are turned into valid active schedules through a serial scheduler. Two types of move strategies were used to explore solution space by generating valid sequences, effective lower bounding and precedence augmentation were employed to reduce the solution space. Rainer Kolisch and Sonke Hartmann [START_REF] Kolisch | Experimental investigation of heuristics for resourceconstrained project scheduling: An update[END_REF] discussed heuristics for solving resource-constrained project scheduling problem (RCPSP). This was an update of previous review. They summarized and categorized a large number of heuristics recently proposed in literature. They evaluated these heuristics in a computational study and compared them on the basis of their standardized experimental design and on the basis of these results they discussed features of good heuristics.

Conclusion

This chapter basically consists of introduction of educational timetabling problems and the approaches used to solve these problems. We have discussed different types of timetabling problems and especially our main concerned is educational timetabling problems. We have noticed that there are mainly two types of solution techniques. First type of technique is the one which solves problem directly without giving any focus on hard or soft constraints but this procedure tries only to minimize objective value of the function where hard constraints have more penalty value than soft constraints. Second type of technique is the one which solves the problem in two steps. In the first step the algorithm solves hard constraints of the problem and in the second step the algorithm tries to solve soft constraints while maintaining the solution feasible (means no violation of hard constraints). We shall say that this is not a concrete classification.

We have noticed that many algorithms have been used to solve a particular problem or the author's own institution problem. So this is quite understandable that obviously they will be motivated to solve that specific problem. But according to research point of view it is difficult to judge how their algorithms performance is good with respect to others's algorithms. As university timetabling problems often do not have any standardized problem definitions and do not have many different problem instance libraries available for benchmarking algorithms.

Thus there is a need of more and generalized problem instance libraries to analyze and compare different algorithms performance.

We have tried to present details of the domain in our Chapter 1. But if someone does not have prerequisite knowledge of these problems, we feel that this chapter is not sufficient for his foundation in this domain, one can study referred literature given in our general introduction.

Chapter 2

TRANSFORMATION OF COURSE TIMETABLING PROBLEM TO RCPSP

In this chapter, we have proposed two equivalent mathematical formulations which transform course timetabling problem to RCPSP (resource constrained project-scheduling problem). In Section 2.1, we have given a brief introduction to RCPSP. In Section 2.2, we have discussed why we choose single mode RCPSP for transformation and benefits of this transformation. In Section 2.3, we have presented our mathematical models and chapter is concluded in Section 2.4.

The resource constrained project scheduling problem (RCPSP)

The classical resource constrained project-scheduling problem (RCPSP) may be stated as follows. A project consists of a set of n activities numbered 1 to _ j , where each activity has to be processed without interruption to complete the project. We consider additional activities j = 1 and j = _ j representing the single source and single sink activity of the network respectively. The duration of an activity j is denoted by

Basic single-mode RCPSP and course timetabling

Our purpose is to transform educational timetabling problem (course timetabling) to resource constrained project scheduling problem. There are six major classes of RCPSP: 1. Basic Single-Mode RCPSP 2. Basic Multi-Mode RCPSP 3. RCPSP problems with non regular objective functions 4. Stochastic RCPSP 5. Bin-packing-related RCPSP problems 6. Multiresource-constrained project scheduling problems.

If a resource constrained project scheduling problem (RCPSP) uses a single execution mode for every activity, with specific time and resource requirements is called single mode resource constrained project scheduling problem. Here we shall only discuss and use single mode RCPSP because in timetabling problem, courses are assigned to teachers in first stage and total duration for each course is also predefined. So by using single mode RCPSP, scheduling of these courses could be done. In our formulations we use set of lessons instead of set of courses to transform problem in RCPSP for that purpose we decompose firstly the courses durations into set of lessons.

One benefit to transform timetabling problem in RCPSP is that durations of lessons can be set according to choice but normally solvers take lesson length uniform for the easiness and the other thing is that if there are precedence constraints (i.e lesson i of duration i d must be taught before lesson j of duration j d ) between lessons then this kind of formulations will be more beneficial to use than others timetabling formulations. The other aspect of attention is a new dimension of thought and beauty of mathematical work which can open new rooms for researchers. We are thinking on the idea that how many other features of RCPSP and its generalizations can be attached to timetabling problems that these problems could be solved by using RCPSP solvers or techniques.

Transformation of timetabling problem to RCPSP

This section defines many sets and sub sets, which are used to formulate mathematical models. Our two proposed formulations are the part of this section as well.

General features of the models

In this section we shall define our sets and sub sets, which will be used in our formulations.

-A set of lessons J ={1,…, _ j }.

-A set of types of rooms R= {1,…, r }.

-A set of rooms Y= {1,…,  y }.

-A set of periods T = {1,…, t }. T is a set of periods, which all have same length.

-A set of classes C= {1,…, c }. Class is a set of lessons which have common students.

-A set of teachers P = {1,…, _ p }. Each lesson will have a teacher previously assigned to it. Some additional parameters and sets are defined on the basis of previous sets to make easy the presentation of model. We have formulated timetabling problem in two different ways on the prototype of Resource constrained project scheduling problem. We have formulated high school timetabling problem in a two different ways.

Proposed mathematical model 1

With these variables, the first formulation can be defined as follows.

{ 1  jt x if lesson j is scheduled in period t, jt x = 0 otherwise ;} for J j  and T t  Max jt T t J j jt d x     T t jt x = j d J j  (1)
The constraint [START_REF] Zhipeng | Adaptive tabu search for course timetabling[END_REF] ensures that each lesson is scheduled for

j d periods. 0 ) .( 1 1 ,        t ES q jt t j jt j j x x x d J j  ,  t [ 1  j ES ,…, 1  j LF ] (2)
The constraint (2) is a non preemption constraint which ensures that processing of each lesson is not interrupted. 0 .

1 1       t ES q it jt i i x x d J j  , i j P  ,  t [ 1  j ES ,…, i LF ] (3)
The constraint [START_REF] Causmaecker | A decomposed metaheuristic approach for a real-world university timetabling problem[END_REF] shows that a lesson j must not be started before all its predecessors have been processed completely.

rt jt t E j jr a x u    . ) ( R r  , T t  (4)
The constraint (4) guarantees that the number of lessons scheduled in period t requiring rooms of type r will be less than or equal to the number of rooms of type r available at period t.

1    p J j jt x T t  , P p  (5)
The constraint (5) ensures that teacher p cannot teach more than one lesson at period t.

1   c j jt x T t  , C c  (6)
The constraint [START_REF] Zhou | Single-track train timetabling with guaranteed optimality: branch-and-bound algorithms with enhanced lower bounds[END_REF] ensures that class c cannot attend more than one lesson at period t.

 jt x {0,1} J j  , T t 
Where jt d is the desirability to schedule lesson j in period t, basically this is preference to teach lesson for teachers in periods because sometimes they are performing some other administration duties and some teaching periods are more suitable for them than others.

Objective function can be used according to demand, if one wants to schedule these lessons as early as possible, one can use Min 

    j n LF ES t jt x t 1 .
, which is same as one uses in RCPSP (minimize the project completion time).

Proposed mathematical model 2

The second formulation is proposed using these variables. This is equivalent to the first formulation.

{ jyt x = 1 if lesson j is scheduled in period t at room y, jyt x = 0 otherwise ;} for J j  , Y y  and T t  Max jt T t J j jyt Y y d x          T t jyt Y y x = j d J j  (7) 0 ) .( 1 1 ,            t ES q jyt Y y t j jyt j Y y j x x x d J j  ,  t [ 1  j ES ,…, 1  j LF ] (8) 0 . 1 1           t ES q iyt Y y jyt i Y y i x x d J j  , i j P  ,  t [ 1  j ES ,…, i LF ] ( 9
) rt J j Y y jyt a x r r      R r  , T t  (10) 1      p J j jyt Y y x T t  , P p  (11) 1      c j jyt Y y x T t  , C c  (12)  jyt x {0, 1} Y y  , J j  , T t 
The constraints 1 and 7, 2 and 8, 3 and 9, 4 and 10, 5 and11, 6 and12 are representing the same constraints.

Conclusion

The Resource-constrained project scheduling problem (RCPSP) is concerned with single-item or small batch production where limited resources have to be allocated to dependent activities over time. Over the past few decades, a lot of work has been done with the use of optimal solution procedures for this basic problem type and its extensions. Brucker and Knust [START_REF] Brucker | Resource-constrained project scheduling and timetabling[END_REF] had discussed how timetabling problems can be modelled as a RCPSP. Authors discuss high school timetabling and university course timetabling problem as an example. We have formulated two mathematical formulations of course timetabling problem which are the prototype of single-mode RCPSP [START_REF] Ahmad | Transformation of course timetabling problem to RCPSP[END_REF].

These formulations are basically linear integer programming and could be solved by using linear programming solvers like CPLEX, LINGO etc. It would be interesting to correlate more features of timetabling problem to RCPSP. We expect, this effort would be thought provoking and would be a new addition in this domain. The purpose of the work is to show how course timetabling problem can be transformed into RCPSP. Chapter 3

A GENERIC MODEL OF UNIVERSITY COURSE TIMETABLING PROBLEM

In this chapter, we have presented a new 0-1 linear integer programming formulation for university course timetabling problem. The mathematical model for the problem provides many operational rules and requirements which are needed in many institutions. We have formulated a generic model by gathering many constraints from different university environments in a single formulation. Remaining of the chapter is organized as follows.

In Section 3.1, we have explained the terms, sets, sub sets and parameters required to formulate the mathematical model. In Section 3.2, we have proposed the mathematical formulation of our generalized university course timetabling problem. In Section 3.3, we have demonstrated how the constraints of this model can be used as hard and soft and how one can make objective function using these soft constraints. In Section 3.4, we have explained the procedure of the construction of a timetable by using a small problem instance. Finally, the chapter is concluded in last Section 3.5.

General features of the proposed model

In this section, we are going to propose a generic mathematical formulation for university course timetabling problem which covers many constraints of different university environments.

Used entities of the model

Our generalized problem consists of the following entities.

Courses and Teachers

Each course has fixed number of lessons to be assigned in distinct periods. It is attended by given number of students and is taught by a teacher.

Days, Periods per day and Total Periods

We have a number of teaching days in a week. Each day has a fixed number of periods. Total periods are the product of number of periods per day and number of days.

Slots

A triplet of room-period-day is called one slot. Total number of slots can be found by multiplying total number of days, total number of rooms and total number of periods per day.

Rooms

Each room has a given capacity (number of available seats). Each room also has a type called room type. Two rooms of same capacity can have different types.

Class

A class is a group of courses which have common students. Thus the courses of one class must not be scheduled at the same period.

Notations, sets, sub sets and parameters

Now we shall define our sets and present in detail the problem requirements.

-A set of course C= {1,…, c }. Each course has a fixed number of hours per week, which can be taught during the week.

-A set of rooms R= {1,…, r }. Rooms can be of different types, including computer rooms and laboratories for specific subjects. Each room has a fixed capacity.

-A set of total periods P = {1,…, p }. P is a set of periods (all of the same length, 1 hour).

Total number of periods P can be found by multiplying number of periods per day with total number of days.

-A set of days D = {1,…, d }. D is the teaching days of the week.

-A set of classes K = {1,…, k }. K is a set of classes (classes are groups of students attending exactly the same courses).

-A set of teachers T = {1,…, t }. Each course will have a teacher previously assigned to it.

-A set of types of rooms X= {1,…, x }. We have defined k C , group of students attending exactly the same courses but it can also be defined another way, group courses in such a way that any pair of courses in the group have one or more common students. The other way is more general than the first way.

A timetable is an assignment of courses C to rooms R and to periods P. A timetable fulfills some basic requirements, which are normally called hard constraints, mostly common for every institution. It also satisfies some other constraints whose satisfaction is not mandatory but their fulfillment shows that how good timetable is.

Decision variables

We have defined these decision variables to formulate our mathematical model. We have defined four binary variables.

-

crp x = 1 if course c C is scheduled in room r  R at period pP, crp x = 0 otherwise; - cd u = 1 if course cC is assigned to day d D, 0 otherwise; - td  = 1 if d  D is a teaching day for teacher t  T, 0 otherwise; - rc z = 1 if room r R is used by course cC, 0 otherwise;

Objective function

We have proposed a generalized model for course timetabling. This generalized model consists of many constraints. For this generic model the objective function is also generic and can be adopted for specific problems. These constraints of the generic model can be used as hard or soft constraints in a specific problem. One can write the objective function when he knows exactly which constraint is soft and which constraint is required as hard. We have shown in Section 3.3, how one can write objective function from a specific problem by taking an example.

Integer programming formulation for generalized problem

In this section, we have presented our mathematical formulation. This formulation has many different types of constraints and we have divided them in six main categories, which are described in the following.

Hard constraints

In this section, we have written four constraints which are normally used as hard constraints in different university environments.

For every course C c  , c n hours a week must be scheduled.

c R r P p crp n x     C c  (1)
For every class K k  , class k cannot attend more than one course at period

P p  .    k C c R r crp x  1 K k  , P p  (2)
For every teacher tT, teacher t cannot teach more than one course at time

P p  .    t C c R r crp x  1 P p  , T t  (3)
For every room rR, room r cannot host more than one course at time

P p  .  C c crp x  1 P p  , R r  (4)

Period related constraints

For every pP, the number of courses scheduled in period p requiring room type x will be less than or equal to the number of rooms of type x available at period p.

xp R r C c crp m x x x      X x P p   , (5)
For every pP, if course is not adequate to room type, it could not be assigned to that room.

0       x x R r C C c crp x X x P p   , (6)
For every period p ' d P  , course c will not be scheduled in the last period of the day.

0     C c R r crp x  p ' d P  (7)
Let us suppose, period 1 p and 2 p of day d are fixed for lunch break, then each class will be free at least one period ( 1 p or 2 p will be free).

      R r C c crp crp k x x 1 ) ( 2 1 K k  , D d  , d p p  2 1 , (8)

Room related constraints

This inequality shows relationship between decision variable z and x.

rc crp z x  C c  , R r  , P p  (11)
If room r is used for course c, it may be used for more than one period.

rc P p crp z x    C c  , R r  (12)
For each room r  R and each day d D , the timetable should be compact, if room r is used in period i p and in period j p then it should be used for every period between i p and

j p . 1 ) (     C c crp crp crp j k i x x x R r  , D d  , d j k i P p p p    (13)
There are some rooms which administration wants to spare. So these free rooms should not be scheduled.

0     P p C c crp x f R r  (14)
Number of students taking course c in a room r at period p should be less than or equal to the capacity of room r.

Class related constraints

For every K k  , class should not have more than two consecutive courses on each day, it means that maximum two lessons can be scheduled in a row.

) ( 2 1          i i i k crp crp R r crp C c x x x K k  , D d  , d i i i P p p p      2 1 (16)
In class timetables, any class should not have a day with a single course (means that only one lesson is scheduled on whole day), in equation ( 17), kd w is number of courses of class k in day d and kd l counts class as having single course violations.

kd R r crp C c P p w x k d        K k  , D d  1  kd l if 1  kd w and 0  kd l if 1  kd w (17)     D d kd K k l K k  , D d 
Now by summing up all classes on all days total violations can be found.

For every K k  , two courses of a class must be scheduled in different periods. This is same constraint like (2) but written in a different way.

1 ) ( 1        i i k crp R r crp C c x x K k  , D d  , d i i P p p   1 (18)
No class can attend more than max l teaching hours a day.

      k d C c R r crp P p x max l K k  , D d  (19)
Here max l is fixed for every class but we can use it as that each class has its own fix teaching hours and it can be written in such a way.

      k d C c R r crp P p x max k l K k  , D d  (20)
No class can attend less than min k l teaching hours a day.

      k d C c R r crp P p x min k l K k  , D d  (21)
1       R r rp c R r rp c j j i i x x K k  , i c , j c  k C , i c  j c , D d  (22) 1      d j d i d t p l p t
For each class k  K, the timetable should be compact, empty periods between any two courses are not allowed.

1 ) (        k j i k crp crp R r crp C c x x x K k  , D d  , d k j i P p p p    (23)
For each class k  K, class must not be scheduled on periods where it is unavailable.

0       k k C c R r crp P p x K k  (24)
For each class k  K, any two of its lessons should be scheduled after a gap of g periods.

1 ... 1             k C c R r g q q q p crp x (25)
It occurs most of the time that some courses are taking place in one department and some others are taking place in any other department and distance between the buildings is long, so students or teachers could not reach on time after attending a course in one building to other building. So such type of courses should not be scheduled in consecutive periods. Let us suppose, i c and j c are two courses of the same class which take place in different long distance buildings, so these could not be scheduled on consecutive periods.

1 1            d i i j d i i i P p R r rp c P p R r rp c x x D d  (26)
We can handle this issue by defining room types in such a way that all rooms of one building have different types from the room of other building, so these courses would be scheduled according to their types. In this way every course would be scheduled in its required building.

But if the courses of different buildings occur on consecutive periods, long distance between these buildings would create a problem for students to reach on time to attend the lesson.

There are courses in which, many students have enrolled. It is very difficult to handle such a big lesson so we would prefer to divide this course in sub courses and consider each sub course as a complete course. One could also divide these big courses in many sections. Then he can accordingly write mathematical formulation. We would like to explain, how one would define sets and subsets to write such type of formulation. This division would be more beneficial if one want to put some conditions on the sections of a course particularly. The same would be the case for big classes and these big classes could also be divided in sections.

Similarly one can divide big courses in sections and can accordingly write new sets to formulate problem.

A set of classes K ={1,…, k } k S = {1,…, _ k s } K k  k S C = {Set

of courses in sections of class k}

One can write mathematical model after defining these subsets. For example, sections of same class could not be scheduled at the same period (same teacher teaches).

1      k S C c R r crp x P p  (27)

Course related constraints

For every course c C, if course c is scheduled in day d, i.e.,

     d P p R r crp x max c n cd u C c  , D d  (28)
For every course c C, the timetable should be compact. If more than one hours of the same course c are scheduled in day d, they have to be assigned to adjacent periods.

1 ) (      k j i crp crp R r crp x x x C c  , D d  , d k j i P p p p    (30)
All the hours of a course c  C scheduled in a day d  D should be located in the same room r  R.

 

j j i i p cr p cr x x 1 C c  , r r r j i    1 , D d  , d j i P p p   (31)
All the hours of a course c  C should be scheduled in the same room r  R for whole timetable.

 

j j i i p cr p cr x x 1 C c  , r r r j i    1 , P p p j i   (32)
For every course cC, course will not be scheduled in period p at room r, if room r will not be available at period p.

0  crp x C c  , R r  , P p  \ r P (33)
For every course t C c  (taught by teacher t), course will not be scheduled in period p, if teacher t will not be available at period p.

0  crp x T t  ,  c t C , R r  , P p  \ t P (34)
For every course cA, courses c will be scheduled in its pre assigned periods.

For every course cF, that course c will not be scheduled on its forbidden period.

0     c P p R r crp x F c  (36)
For every course cC, Constraints (37), ( 38) and ( 39) guarantee minimum and maximum working days for course c constraints are satisfied.

Inequality [START_REF] Mccollum | Setting the research agenda in automated timetabling[END_REF] shows the relationship between decision variables u and x.

dc R r t p t crp u x d d       1 C c  , D d  (40)
Some courses should be scheduled on the same day. Let

... 2 1     d c d c d c j u u u D d  (42)
We can define precedence constraints among courses as in relation [START_REF] Gaspero | The second international timetabling competition (ITC-2007): curriculum-based course timetabling (Track 3)[END_REF]. Let

  

      R r R r rp c rp c R r rp c j x x x ...

Teacher related constraints

For every , T t  constraint (48) and ( 49) limit the number of working days for each teacher t.

Constraint [START_REF] Sabar | A honey-bee mating optimization algorithm for educational timetabling problems[END_REF] speaks about role of td  in this relation and ( 49) ensures the maximum working days limit for every teacher t. Because some teachers are involved in administrative or non academic activities, they need some free days to do this work. Similarly one can write relation for minimum working days.

 R r crp x  td   c t C , T t  , D d  , 1    d d t p t ( 48
) t D d td e     T t  (49)
The constraint (49) could be written in this way as well. Teachers should have q days free when total days in timetable are d .

q d td D d       T t  (50)
We can define minimum and maximum load per day for every teacher t. Let us suppose lt min and lt max are non negative integers defining minimum and maximum load.

lt P p R r C c crp d t x max        T t  , D d  ( 51
) lt P p R r C c crp d t x min        T t  , D d  (52)
For each teacher t  T, any two of its courses should be scheduled after a gap of g periods for every day

D d  . 1 ... 1             t C c R r g q q q p crp x D d P g q q q d        , ... 1 (53)
Every teacher has a preference to teach in some specific rooms.

0         t t C c R R r P p crp x T t  (54)  crp x {0,1} P p  , R r  , C c  , cd u {0,1} C c  , D d  td  {0, 1} T t  , D d 

Discussion on Objective functions

In timetabling problem we have two types of constraints, which are called hard constraints and soft constraints. Hard constraints have a higher priority than soft, and their satisfaction is usually mandatory. Solution should satisfy maximum number of soft constraints too. The usage of constraints as hard or soft depends on the demands and requirements of the institution. In one problem, a constraint used as a hard constraint it can be used as a soft constraint in other problem. Normally soft constraints are written in the objective function and penalty or desirability of any event is set by giving value to the weights.

Many objective functions can be written according to the institution requirements by using soft constraints. Here we have taken some constraints as soft constraints and have shown how objective function from these constraints can be written. We use minimum working days for course c, room capacity, each course should use minimum rooms i.e. if it is scheduled in some room next time it should be scheduled again in the same room, compactness for course c i.e., it is required that the periods assigned to day d for course c should be adjacent, the timetable should be compact for every class i.e. empty periods between any two courses of same class are not allowed, classes should not have a course in the last period of the day, any class should not have more than two consecutive courses on each day and any class should not have single course on any day. Now multi objective function for these soft constraints can be written in this manner.

Min z = f  F(c) + h  F(r,p,c) + i  G(c) + w  F(c,d) + l  F(k,d) + j  F(p) + k  G(k,d) + m  S(k,d) F(c) = 
C c  c g = (  R r rc z ) -1 C c  cd m = 1 ) ( 3 2 1      crp crp R r crp x x x C c  , D d  , 1 3 2 1      d d t p p p t kd y = 1 ) ( 3 2 1        crp crp R r crp C c x x x k K k  , D d  , 1 3 2 1      d d t p p p t p o =    C c R r crp x  p ' d P  2 ) ( 3 2 1         crp crp R r crp C c kd x x x b k K k  , D d  , 1 3 2 1      d d t p p p t kd R r crp C c P p w x k d        K k  , D d  kd l =1, if kd w =1 and 0 otherwise c q 0  , c g 0  , cd m 0  , kd y 0  , p o 0  , 0  kd b C c  , D d  , K k  , K k  ,  p ' d P  and f > 0 , h > 0 , i > 0 , w > 0, l > 0, j > 0, k > 0, m > 0
The failure to satisfy constraint type is measured by the non-negative variable

c q 0  , c g 0  , cd m 0  , kd y 0  , p o 0  , 0  kd b
and is penalized via fixed parameters f, i, w, l, j, k each respectively and h is penalized fixed parameter for capacity constraint. Which constraint is more agreeable than other, these penalty parameters decide. The objective function sets to minimize the infeasibility of the soft constraints required by the scheduler.

An example of timetabling problem

Now we present an example which considers some constraints of university course

timetabling problem namely all lessons of a course should be scheduled, courses of a curriculum must not be scheduled in a same period, teacher should not be double booked and room should not be double booked. With these constraints, we have two more hard constraints, course should be scheduled in the required room type and a course cannot occur in a forbidden period.

The objective function is maximizing the desirability cp d of scheduling all courses. Each course has a desirability index for each period. This desirability index ranges from 0 to 4, where 4 represents most desirable period and 0 represents the least desirable period for that course. The purpose of solving this simple example is to show that how sets and subsets can be used for the timetabling problem. We think that the solution of this simple example can help to understand the procedure of the solution. The data of the example is given as follows:

Data: cp d c=1 c=2 c=3 c=4 xp m x=1 x=2 p=1 0 2 0 4 p=1 1 2 p=2 0 1 3 2 p=2 2 1 p=3 1 0 2 2 p=3 1 2 p=4 1 0 0 3 p=4 2 1 p=5 2 1 1 2 p=5 1 2 p=6 2 0 4 3 p=6 2 1 p=7 0 1 3 4 p=7 1 2
x = 1 if course C c  is scheduled in room R r  at period P p  , crp x = 0 otherwise; max       R r crp C c P p cp x d     R r P p crp x = c n C c  (a)    k C c R r crp x  1 K k  , P p  (b)    t C c R r crp x  1 P p  , T t  (c)  C c crp x  1 P p  , R r  (d) xp R r C c crp m x x x      X x P p   , (e) 0       x x R r C C c crp x X x P p   , (f) 0     c P p R r crp x F c  (g)
We have solved this example by CPLEX. The result is shown in Table 3.1 where green block represents that the room is available but red block represents non availability of the room.

Conclusion

The university course timetabling problem is a hard problem which must be solved by departments in the beginning of the semester. It is a difficult task for which universities devote a large amount of human and material resources every year. These problems involve lot of constraints, which should be satisfied. A huge search space has to be explored, even if the size of the problem is not large enough. There is not a specific definition of this problem because each institution has its own priorities and choices. In this chapter we have given a generalized mathematical formulation for university course timetabling problem. Many constraints from different university environments have been discussed and have been written

in their mathematical relations. We have given details in Chapter 5 of those different problems which have been become sub problem of our generalized model.

In the beginning of the chapter we have defined sets, subsets, different parameters and decision variables needed for formulating this generalized problem. We have classified these constraints in six sets namely, hard constraints, period related constraints, room related constraints, class related constraints, course related constraints and teacher related constraints.

Hard constraints means here is that these constraints normally have been used as hard in university course timetabling problem. We have explained how the problem of big courses (means many students have enrolled) can be tackled. Similarly we have demonstrated big classes can cause problem for administration and how these can be divided in sections.

In university timetabling problem cost function has many objectives to achieve and normally all these objectives are expressed in form of unique objective function. In this chapter, we have discussed different objective functions when treating university course timetabling problem as an optimization problem and have explained how soft constraints can be used as a part of objective function. At the end, chapter is finished with an example of university timetabling problem solved by CPLEX.

Chapter 4

GENERIC MODEL FOR EXAMINATION TIMETABLING PROBLEM

The primary purpose of examination timetabling problems is to assign a session to a room for every examination which satisfies a given set of constraints. Each institution has its own set of constraints according to its policies and it varies from institution to institution like course timetabling problem. Each institution wants to have a good quality of examination timetable and quality of timetable would also differ from institution to institution. For some institution, a feasible timetable may be acceptable timetable but for others it does not satisfy the university required criteria.

Usually the quality of a timetable is measured by the satisfaction of soft constraints. For example a student cannot have more than one examination per day. So how many students would have examinations more than one on any day is counted as a violation and it decreases the quality of the timetable. So for an acceptable timetable there would be several different quality measures simultaneously. And the objective function is the combination of these measures with relative weights that shows their importance in the timetable. For example in some institutions, there is sufficient number of available rooms or these rooms have large capacities. So these institutions give less importance to room related constraints while scheduling.

A common constraint for educational institutions is an event clash constraint. It also occurs in examination timetabling. But due to difficult nature of examination timetabling problems, even some institutions relax this constraint. So these institutions allow a student to take two examinations at the same time and they try to resolve this conflict by quarantining. But normally it would not happen and it is very rare.

Our remaining chapter is arranged in this way. In Section 4.

Most frequently used constraints for examination timetabling

These constraints have been used many times by different authors.

(1) Clashing: Any student cannot have two examinations in the same periods.

(2) Total capacity: The total number of students taking exams in the same period should be less than the total number of students allowed for that period.

(3) Room capacity: Total number of students taking examinations in the same room in the same period should be less than the capacity of the room.

(4) Examination capacity: The total number of examinations scheduled in a period should be less than a defined specific number.

(5) Room availability: All rooms are not available all the time. They can be only available in some specific periods.

(6) Exam availability: Some examinations are already assigned to specific periods or can only be held in a limited set of periods.

(7) Room-Exam compatibility: Some examinations are required to be held in some specified type of rooms.

(8) Exam precedence constraints: There could be precedence constraints between examinations i.e. that some examinations should be held before others.

(9) Examination compactness: There should not be compactness in some examinations. This means that some examinations should not be scheduled in adjacent periods.

(10) Large exams: Large examinations should be scheduled earlier in the timetable (e.g.

examinations with more than 500 students must be held in the first 10 sessions).

We have written some mostly used constraints as an example but in real world problems institutions use many more constraints. Some institutions use them as soft constraints and some others consider them as hard constraints [START_REF] Merlot | A hybrid algorithm for the examination timetabling problem[END_REF].

Features of the generic model

In this section, we shall propose a generic mathematical formulation for examination timetabling problem.

Entities for the model

We have used the following entities for our generalized examination timetabling problem.

Examinations and Invigilators

Each examination has a fixed number of hours to be scheduled and invigilators have been assigned previously to each examination.

Days, Periods per day and Total Periods

We have fixed number of examination days. Each day has a specified number of periods.

Total number of periods is the sum of all days periods.

Slots

A triplet of room-period-day is called one slot. Total number of slots can be found by adding all days slots.

Rooms

Each room has its own capacity (number of available seats). Each room also has a type called room type. Two rooms of same capacity can have different types.

Class

Class is a group of students attending exactly the same examinations.

Notations, sets, sub sets and parameters

This section is devoted for notations, sets, sub sets and parameters required to formulate mathematical model.

-A set of examination E= {1,…, e }. Each examination has a fixed number of hours, which can be scheduled during the timetable.

-A set of rooms R= {1,…, r }. Rooms can be of different types, including computer rooms and laboratories for specific examination. Each room has a fixed capacity.

-A set of periods P = {1,…, p }. P is a set of periods, which have different durations.

-A set of days D = {1,…, d }. D is the examination day of the timetable.

-A set of classes K = {1,…, k }. K is a set of classes (classes are groups of students attending exactly the same examinations).

-A set of invigilators I = {1,…, i }. Invigilators have been assigned previously to each examination.

-A set of types of rooms X= {1,…, x }.

-A set of duration types of examinations should not be scheduled in any period P p  , in these rooms.

f P  P = set of periods which should be free in timetable, it means that any examination E e  should not be scheduled in any room r R, in these periods.

Decision variables

We have defined four binary variables to formulate our mathematical model.

-

erp x = 1 if examination E e  is scheduled in room R r  at period P p  , erp x = 0 otherwise; - rp d y  = 1 if duration type d is used in room R r  at period P p  , rp d y  = 0 otherwise; - id  = 1 if d  D is a surveillance day for invigilator I i  , 0 otherwise; - ed u = 1 if examination E e  is assigned to the day D d  , 0 otherwise;

Objective function

We have presented a generalized model for examination timetabling which consists of many constraints. Many examination timetabling problems are sub problem of this generic model (Chapter 5, Section 5.2). So we have not written any specific objective function here for this model. We have formulated mathematical relations for different constraints of timetabling problem. One can write mathematical objective function equation using this model after choosing constraints as hard and soft. We have explained the procedure of writing any objective function from these constraints in (Chapter 3, Section3.3).

Integer programming model for generalized examination timetabling problem

In this section, we present our linear integer programming model for examination timetabling problem.

For every examination

E e  , it should be scheduled exactly once, in unique room and in unique period.

1     R r P p erp x E e  (1)
Sum of number of students taking examinations in a room r at period p should be less than or equal to the capacity of room r.

For every class k K, class k cannot take more than one examination at period p P.



  k E e R r erp x  1 K k  , P p  (4)
We can define precedence constraint among examinations in this way. Let i e < j e are two examinations and i e should be scheduled before j e .

 

      erp R r erp E e x x k K k  , D d  , d P p p   2 1 (9)
For each class k  K, we put penalty for every two examinations, which are scheduled on same day but on non consecutive periods. One should not be confused with the notation

d P p p p    3 2 1
this does not mean that these

       erp erp R r erp E e x x x k K k  , D d  , d P p p p    3 2 1 (10)
Front load penalty constraint, which explains big examinations with respect to number of students should be scheduled earlier in the timetable because they require much time for their marking.

For every examination eF, examination e will not be scheduled on its forbidden period.

0      e P p R r erp x F e  (11)
There are some rooms which administration wants to be spare. So these free rooms should not be scheduled.

0     P p E e erp x f R r  (12)
There are some periods which should not be scheduled. So these free periods should remain spare.

0     R r E e erp x f P p  (13)
For each class k  K, any two of its examinations should be scheduled after a gap of g periods for every day d. [START_REF] Kendall | Scheduling in sports: An annotated bibliography[END_REF] Examinations of equal length should be scheduled together. [START_REF] Kostuch | The university course timetabling problem with a three-phase approach[END_REF] Some examinations are supervised by more than one invigilator, let i e and j e are any two examinations which are supervised by same two invigilator i i and j i , if these examinations are scheduled in period p, then these will be scheduled in a same room.

1 ... 1             k E e R r g q q q p erp x D d P g q q q d        , ... 1
2 2 1 1       R r rp e R r rp e x x K k  , 1 e , 2 e  k E , , 1 2 1      d d d t p l p t
i i i j i j i j i     , , , , , , (19)
For every , I i  constraints (20) and ( 21) limit the number of working days for each invigilator i. Constraint [START_REF] Werra | Graphs, hypergraphs and timetabling[END_REF] speaks about role of id  in this relation and ( 21) ensures the maximum working days limit for every invigilator i.

 R r erp x  id   e i E , I i  , D d  , d P p  (20) i D d id e     I i  ( 21
)
Invigilators should have q days free when total days in timetable are  d , some invigilators are involved in administrative or non academic activities so they need some free days to do this work.

q d id D d       I i  ( 22
) D d 
We can define minimum and maximum load per day for every invigilator i. Let us suppose li min and li max are non negative integers defining minimum and maximum load.

li P p R r E e erp d i x max       I i  , D d  ( 23
) li P p R r E e erp d i x min       I i  , D d  ( 24
)
For every exam eE, examination will not be scheduled in period p at room r, if room r will not be available at period p.

0  erp x E e  , R r  , P p  \ r P ( 25
)
For every examination eE, examination will not be scheduled in period p, if invigilator i

will not be available at period p.

0  erp x I i  ,  e i E , R r  , P p  \ i P (26)
For every pP, the capacity of examinations (number of students) scheduled in period p requiring room type x will be less than or equal to the capacity of rooms of type x available at

period p. xp R r E e erp e c x s x x      X x P p   , (27)
For every pP, if examination is not adequate to room type, it could not be assigned to that room.

0       x x R r E E e erp x X x P p   , (28)
For every examination eA, examination e will be scheduled in its pre assigned period.

Conclusion

Examination timetabling is a well known combinatorial optimization problem. It is becoming hard to develop adequate examination timetables for educational institutions. Institutions are now introducing a wide range of courses including a number of combined degree courses.

Also they are enrolling more students in many courses. Thus the institutes have to schedule the examinations which are in thousands each year. Consequently it makes examination timetabling a difficult combinatorial optimization problem and it is very complex to solve this problem by manual means. Many appropriate algorithms have been suggested in literature to solve this kind of problem. We have proposed memetic and honey bee mating algorithms to solve examination timetabling problems (Chapter 6, Sections 6.3 and 6.4).

It is difficult to give a universal definition of examination timetabling problem because the exact nature of the constraints and quality measures are unique for individual institutions. This is the motivation to discuss different examination timetabling instances used in literature (Chapter 5, Section 5.2). Thus we have proposed a generic examination timetabling model, which could be applicable across a wide range of scenarios. We have presented here a generalized model of examination timetabling problem which covers the previously described instances and many other real world constraints.

Chapter 5

DIFFERENT INSTANCES OF GENERIC MODELS FOR UNIVERSITY COURSE AND EXAMINATION TIMETABLING PROBLEMS

In this chapter, we have discussed about different instances from literature. The formulations of these instances can be made by our generic model for university course and examination timetabling problems. We have discussed in detail how these instances can be obtained using our model. We have also written the objective functions for these instances by using our generic model. If any instance has used different features than us then we have explained how this is different from us and how our formulation can be used to formulate it.

Before going to instances, we would discuss about mostly used hard constraints for course timetabling. We also present here some features of examination timetabling problem which makes them different from course timetabling problem.

These are the constraints ((1), ( 2), ( 3), ( 4

Instances of our generalized course timetabling problem

These instances are the part of our generalized university course timetabling problem and their details could be found in Sections

Pasquale Avella and Andigor Vasil'ev model

Pasquale Avella and Andigor Vasil'ev [START_REF] Pasquale | A computational study of a cutting plane algorithm for university course timetabling[END_REF] article on cutting plane algorithm for course timetabling problem had used many constraints first time. They described a case study where branch and cut algorithm was used. They transformed course timetabling as a set packing problem with side constraints. They showed a relation between course timetabling problem and the set packing problem. This relation was used to get timetabling problem inequalities from the polyhedral description of the set packing polytope, whose structure was widely studied.

In fact this was an attempt to transform course timetabling problem to set packing problem. A set packing problem could be transformed to stable set problem by making intersection graph.

Let A be a matrix of size m n, whose entries are 0 or 1. Let y be a set of n variables and c be a cost vector. Then set packing problem can be defined as max All hours of a course per week must be scheduled [START_REF] Zhipeng | Adaptive tabu search for course timetabling[END_REF].

Any class cannot attend more than one course at any period (2).

Teacher t cannot teach more than one course at any period (3).

Any room cannot host more than one course at anyperiod (4).

These constraints were used as soft constraints by them.

Daily hours of course c in a day d should be between min c n and max c n [START_REF] Daskalaki | An integer programming formulation for a case study in university timetabling[END_REF] and [START_REF] Kolisch | Experimental investigation of heuristics for resourceconstrained project scheduling: An update[END_REF].

For every course the timetable should be compact. If more than one hours of the same course c are scheduled in day d, they have to be assigned to adjacent periods [START_REF] Batenburg | A new exam timetabling algorithm[END_REF].

No class can attend more than max l teaching hours a day [START_REF] Bonutti | Benchmarking curriculumbased course timetabling: formulations, data formats, instances, validation, visualization, and results[END_REF].

All the courses of a class in a day d must be scheduled either in the morning or in the afternoon session [START_REF] Brucker | Resource-constrained project scheduling: Notation, classification, models, and methods[END_REF].

For each class the timetable should be compact, empty periods between any two courses are not allowed [START_REF] Fleszar | Solving the resource-constrained project scheduling problem by a variable neighbourhood search[END_REF].

Teacher can not work more than maximum number of working days allowed for him [START_REF] Baykasoulu | Artificial bee colony algorithm and its application to generalized assignment problem[END_REF] Course should be scheduled in a room which is adequate for it ( 5) and [START_REF] Zhou | Single-track train timetabling with guaranteed optimality: branch-and-bound algorithms with enhanced lower bounds[END_REF].

A course will not be scheduled in a period at room, if room is not available at that period [START_REF] Burke | On a clique-based integer programming formulation of vertex colouring with applications in course timetabling[END_REF].

A course will not be scheduled in a period, if teacher is not available at period [START_REF] Ross | Advances in Evolutionary Computing: Theory and Applications, topic: Genetic algorithms and timetabling[END_REF].

International timetabling competition 2007 (ITC 2007)

Post enrollment based course timetabling

This was a track in timetabling competition 2007 and this was the extension of international timetabling competition 2002. This model was about the real situation where students are given choices to attend lessons according to their wish and time table was scheduled after students had given their choices. This model was based on the model of 2002 competition which was held in conjunction of PATAT and Metaheuristic Network.

In original model, the number of events must be scheduled in limited number of rooms when satisfying two types of constraints. These were hard and soft constraints, hard constraints are those for which the fulfillment is obligatory and soft constraints are those for which the fulfillment is optional. The solution quality depends mainly on the satisfaction of soft constraints.

Used constraints and difference with ITC 2002

Formally this competition problem was defined in this way. These were the constraints which were used as hard constraint in the problem model.

1.

No student can attend more than one event at the same time.

2. Every event must be scheduled in a room whose capacity is less than or equivalent to the capacity of room and should be of required type.

3. Only one event should be scheduled in a room at the same period.

4. Events should be scheduled on available periods because all the periods are not available all the time. 5. Precedence constraints amongst events should be satisfied.

The last two hard constraints were added additionally in International timetabling competition 2007 (ITC 2007) and all other hard constraints were same. With these five constraints, three soft constraints were added in this problem; 1. Students should not attend events in the last period of the days.

2. Students should not attend three successive events in the same day.

Students should not attend only single event on any day.

These three soft constraints were same, as these are used in 2002 competition. This mathematical model can be written by using these constraints of our mathematical formulation of Chapter 3, where constraints (2), ( 5), ( 6), ( 15), ( 4), [START_REF] Schaerf | A survey of automated timetabling[END_REF], [START_REF] Gaspero | The second international timetabling competition (ITC-2007): curriculum-based course timetabling (Track 3)[END_REF] are expressing hard constraints and ( 16), ( 17), [START_REF] Guyon | Cut generation for an integrated employee timetabling and production scheduling problem[END_REF] are expressing soft constraints.

We can write objective function for this model by using constraints ( 16), ( 17), [START_REF] Guyon | Cut generation for an integrated employee timetabling and production scheduling problem[END_REF]. Objective function can be written as follows.

For every K k  , class should not have more than two consecutive courses on each day.

2 ) ( 2 1           i i i k crp crp R r crp C c kd x x x u K k  , D d  , d i i i P p p p    2 1 , , (16)
where

kd i i i u U 2 , 1 ,   is the sum over all the periods . 2 , 1 ,   i i i
In class timetables, any class should not have a day with a single course (means that only one lesson is scheduled on whole day).

kd R r crp C c P p w x k d        K k  , D d  1  kd l if 1  kd w and 0  kd l if 1  kd w (17)
For every period p ' d P  , course c will not be scheduled in the last period of the day.

p C c R r crp b x     p d P  (7) Min z = a      D d K k kd i i i u U , 2 , 1 , + b     K k kd D d l + c    d P p p b
The failure to satisfy constraint type is measured by the non-negative variable

kd i i i u U 2 , 1 ,   0  , kd l 0  , 0  p b
and is penalized via fixed parameters a, b, c respectively.

Difference of our model with Post enrolment based course timetabling

In our model, we are using classes and courses but in competition model, they used events and students taking these events because this is a post enrollment model and in this model firstly students enroll in events then there is scheduling. We can consider each event like an examination and can make a model (examination timetabling model) or simply for understanding we can say that each course has only one lesson to schedule. Like examination timetabling each event is a unique entity means that when it is scheduled, it is finished, opposite to course timetabling where each course has some lessons. We have written all requirements in our model, we are using classes but in post enrollment problem each event has specific students, one know specifically which students are attending this event but in our model we have classes (set of courses taken by some common students) but we do not know who these students are.

We have to modify data to use this model, firstly make curriculum from data and then solve it according to this way. We can solve all the hard constraints and one soft constraint by reforming sets.

Now we can make classes in this way, take event 1 and see all its students as {1,2,5,9} are taking this event, then all the events which have any student from {1,2,5,9}, is one set of events including event 1. This set is called one class. Similarly see for events 2, 3, 4 and 5, then take all these sets and delete the sets which are repeating (just take one set from repeated sets). These all sets are set of classes for that problem. For our example, classes are as follows. First soft constraint (students should not have events scheduled in the last period of the day) can easily be handled. If event of class is scheduled in the last period of the day, any other event of the class could not be scheduled in this period according to definition. So numbers of students in that event are the students scheduled in the last period.

If we look at second soft constraint according to our model then the situation is that no class can attend more than two of its courses consecutively, so common students can not come more than twice of a class. But when there will be violation of consecutiveness then the common students of all these classes will be counted and these students will violate soft constraint and soft constraint could not be scheduled directly using sets and subsets of students. Problem will be solved if to take it as soft constraint.

Students should be scheduled in this way that they should not have single event on any day, this constraint satisfaction is also difficult. One class is schedule lonely on any specific day, so according our model this is violation of soft constraint but according to student based model (Post enrollment based problem), this is not violation. Because for example, if one class is scheduled lonely on a day and another class has also been scheduled lonely on the same specific day but these two different classes can have common students, so according to post enrollment based problem this is not violation.

It is quite possible in universities that some rooms are very large and they can be partitioned in to sub rooms (partitioning is possible within them). For example a room r is used as a big room in period i p but is partitioned into five small rooms in the next period 1  i p . Thus one can decompose this into two different room types and different room capacities. So it is quite easy to put this feature in our model because rooms are not uniformly available in our model, we can say in period p one room of type x is available and in period p+1 room of type x is not available but five rooms of type y are available.

Curriculum based course timetabling problem

Curriculum based course timetabling problem is a track in ITC 2007 and this track is about weekly scheduling where university publishes curricula first. This model applied to University of Udine (Italy) and many other Italian universities. Datasets were taken from these universities and were modified little to make them general to use them as competition datasets. The problem consists of the following entities, number of days, number of periods per day, number of courses, number of teachers, number of rooms, capacity of each room, number of curricula and many other constraints. Now we would like to express thoroughly the competition problem.

Here we present one of its tracks namely the curriculum-based course timetabling. We shall talk about the features of the model and the datasets used together with the evaluation Table 5.1 : Score matrix Their runs were checked with the submitted seed to make sure that they can repeat. If these were not repeatable then other participant next to him was chosen for the top five. Then the final was conducted between these finalists. Final was conducted in this way.

1. All datasets with hidden ones were used.

2. The solvers were run by organizers.

3. For each dataset, 10 independent trials were conducted by providing solvers with a sequence of random seeds (the same was done for all solvers). They proceeded as earlier by calculating ranks and averaging them on all trials on all datasets.

The final winner of the competition was the finalist with the lowest mean rank and in case of tie more additional trials were added for all datasets until a single winner was found. Only feasible solutions were accepted in ITC-2002 because there it was purposely easy to produce feasible solutions for all datasets. In ITC-2007 organizers relaxed the condition for feasible solution so solvers can submit their solutions with few infeasible solutions as well, although all the datasets had at least one feasible solution. In case of infeasible solution for some datasets from different solvers comparison was conducted on an evaluation based ranking of solutions on each dataset, rather than on the actual scores. An infeasible solution on one dataset did not necessarily prejudice the overall performance of the participant due to this scoring based on rankings. Datasets were collected from larger set of interesting case which was coming from real world problem without the limitation of easy feasibility.

In ITC-2002 ranking was fully based on the solution provided by participants because for each single trial maximum CPU time was granted to each solver. So solver was able to run as many trials as he could and report only the best of all of them.In ITC-2007, Finalist solvers run on organizers machine (with new seeds), hidden datasets were used to stop this approach.

Moreover in the case of stochastic algorithms, this fostered the design of robust solvers. In ITC-2002, organizers also tested the few best algorithms on unseen datasets and indeed results were good as were good for known datasets.

Time was fixed to solve datasets for competition because organizers wanted to remove degree of variability from the scoring system. This was a main question, what is a good feasible fixed amount of running time for the actual timetabling. Timetabling is done few times in a year in educational institutions so one can think that more than 10 minutes would be a reasonable grant of time. In real case timetabling many researchers have pointed out that solution of real problem is an interactive process during which a lot of datasets should be solved. Constraints and objectives are manually adjusted between runs of a working session for one single case due to live situation or last minute changes, etc. Thus a long to solve datasets can be tiresome for human operator. Although, organizers decided maximum 10 minutes time to solve a dataset.

Used sets for the problem

There are following entities for this problem.

Days, Periods per day and Total periods

There are 5 to 6 days per week and equal number of periods for each day. Total number of periods can be found by multiplying number of days with number of periods per day.

Courses and Teachers

Each course has fixed number of lessons to schedule and it is attended by number of student.

A teacher will teach this course and each course should be scheduled for specified minimum number of working days. Moreover, there are some forbidden periods for each course.

Rooms

Each room has its capacity and each course can be scheduled to each room if it satisfies the capacity constraint.

Curricula

A curriculum is set of courses which have common students, so these courses can not be scheduled in a same period. Moreover there are also some soft constraints on curricula.

Purpose of the competition

There are total 21 datasets, 7 datasets are early datasets, 7 datasets are late datasets and 7

datasets are hidden datasets. All datasets are coming from University of Udine. If all hard constraints are satisfied in any solution, it is called feasible solution and all these 21 datasets have at least one feasible solution but optimal values for the soft constraints were not known.

The motivation of this competition track was to make bridge between practice and research, these datasets have certain degree of complexity in this problem so that new formulations could be brought near to those of real world problems (where data is coming from real world) [5].

The second innovation aimed at bridging the gap between research and practice: the competition introduced a significant degree of complexity in all tracks so that the new formulations employed are closer (in more aspects, although not all) to those of 'real world' problems [5] and data was coming from the real world.

Original timetabling problem of Udine University

Some of the participants criticized on these datasets that these are not properly designed because these do not use the most important cost component or these do not penalize the right patterns. To answer these questions organizers added some more features in the formulation [START_REF] Bonutti | Benchmarking curriculumbased course timetabling: formulations, data formats, instances, validation, visualization, and results[END_REF] and main purpose was to make a formulation which could be accepted by a larger community of researchers. So this article [START_REF] Bonutti | Benchmarking curriculumbased course timetabling: formulations, data formats, instances, validation, visualization, and results[END_REF] was accompanied by a web site (http: //tabu.diegm.uniud. it/ctt/) from which all information about datasets or problem description could be found. They added the following new features in the Curriculum based course timetabling problem model. These constraints can be written from our formulation of Chapter 3 by using these constraints ( 23), ( 20), ( 21), ( 26), ( 5), ( 6), [START_REF] Batenburg | A new exam timetabling algorithm[END_REF].

Windows (Curriculum Compactness)

There should not be windows (i.e., periods without teaching) among lessons belonging to a same curriculum.

Curriculum Min, Max Load

The number of daily lessons for each curriculum should be within a given range. Each lesson below the minimum or above the maximum limit counts as one violation.

Travel Distance

Sometimes students have to move from one building to another and between these two buildings there is a long distance. So such type of lessons should not be scheduled on consecutive periods.

Room Suitability

Each course should be assigned a room which has all necessary equipment (projector, computer lab, etc.) required by course. Each lesson of a course in an unsuitable room counts as one violation.

Double Lessons

Some courses are required that their lessons scheduled in the same day are adjacent to each other. So for these courses non grouped lessons are not allowed.

Hard constraints

1. Each course has a specific number of lessons; all these lessons must be scheduled to distinct periods.

2. A room can not host more than one lesson in the same period.

3. A teacher can not teach more than one lesson in the same period.

4. Lessons of courses in the same curriculum should be scheduled in the distinct periods.

5. A lesson of a given teacher should not be scheduled in a period if teacher is unavailable in this period.

Soft constraints used in this model are as follows.

1. Number of students in a course should be less than or equal to the room sitting capacity which is hosting it. Each student above capacity counts point of penalty.

2. Each course should be spread over minimum number of working days, each day below the minimum working days counts point of penalty.

3. Lessons of the same curriculum scheduled in the same day should be adjacent to each other. Each lesson not adjacent to others counts point of penalty.

4. All lessons of a course should be delivered in the same room. If more than one room is used for a given course, there will be penalty.

Mathematical model of curriculum based course timetabling problem can be written by using constraints (1),( 4),(3),( 2),( 34),( 15),( 38),( 23), [START_REF] Beyrouthy | Towards improving the utilisation of university teaching space[END_REF] of Chapter 3.

We can write objective function by using constraints ( 15), ( 38), ( 23), [START_REF] Beyrouthy | Towards improving the utilisation of university teaching space[END_REF], which will minimize the objective function value.

Number of students taking course c in a room r at period p should be less than or equal to the capacity of room r. Penalty can be counted by using this equation.

0      r c crp C c pr a s x u P p  , R r  (15)
For every course cC, this equation will be used in objective function to count minimum working days penalty.

    D d cd wc c u q min C c  (38)
For each class k  K, the timetable should be compact, empty periods between any two courses are not allowed.

kd y = 0 1 ) (         k j i k crp crp R r crp C c x x x K k  , D d  , d k j i P p p p    (23)
Where kd ijk y U  is the sum over all the periods i, j, k.

All the hours of a course c  C should be scheduled in the same room r  R, for whole timetable.

 

j j i i p cr p cr x x 1 c C, r r r j i    1 , P p p j i   (32)
But to calculate the penalty for single room use, we use this simple relation

c g = (  R r rc z ) -1 C c  Min z = f  C c c q + h pr R r P p u    , + i  C c c g + l      K k kd ijk D d y U
The failure to satisfy constraint type is measured by the non-negative variable

c q 0  , c g 0  , kd y 0  , 0  pr u
and is penalized via fixed parameters f, h, i, l respectively.

Constraints different from previous scenarios

These constraints are not the part of previously written scenarios. These constraints are the part of our generalized model and could be found in front mentioned articles.

1. Some courses have been pre assigned [START_REF] Aladag | A tabu search algorithm to solve a course timetabling problem[END_REF].

2. Courses will not be scheduled on its forbidden periods [START_REF] Aladag | A tabu search algorithm to solve a course timetabling problem[END_REF].

3. No course can attend more than a specific teaching hours a day [START_REF] Pasquale | A computational study of a cutting plane algorithm for university course timetabling[END_REF].

4. No course can attend less than specific teaching hours a day, if course is scheduled on that day [START_REF] Pasquale | A computational study of a cutting plane algorithm for university course timetabling[END_REF].

5. Define maximum load per day for every teacher [START_REF] Pongcharoen | Stochastic optimisation timetabling tool for university course scheduling[END_REF].

6. Each class have free period for lunch on a specific time interval [START_REF] Daskalaki | Efficient solutions for a university timetabling problem through integer programming[END_REF].

Constraints not found in the literature

These constraints are also part of our mathematical formulation but we could not find them in literature. We can not surely say that these constraints have been used in the literature or not.

But as far as we know we could not search them in any research work.

1. Room's timetable should be compact for every day. If any room is used in period i p and in period j p then it should be used for every period between i p and j p .

2.

In some rooms no course should be scheduled.

Timetable should maintain a gap between any two courses of a class on any day.

There are some periods which should not be scheduled. So these free periods should remain spare. [START_REF] Schaerf | A survey of automated timetabling[END_REF] In case of ( 33), [START_REF] Ross | Advances in Evolutionary Computing: Theory and Applications, topic: Genetic algorithms and timetabling[END_REF], [START_REF] Geiger | An application of the threshold accepting metaheuristic for curriculum based course timetabling, Practice and Theory of Automated Timetabling[END_REF] and (10) course would not be scheduled but reason to not schedule is different. Course [START_REF] Geiger | An application of the threshold accepting metaheuristic for curriculum based course timetabling, Practice and Theory of Automated Timetabling[END_REF] would not be scheduled on forbidden periods; this constraint is different from [START_REF] Schaerf | A survey of automated timetabling[END_REF] which expresses some periods are unavailable. Constraint [START_REF] Geiger | An application of the threshold accepting metaheuristic for curriculum based course timetabling, Practice and Theory of Automated Timetabling[END_REF] means that some periods are unavailable for course only but not for all courses.

Examination Timetabling Instances

Examination timetabling problem is widely studied problem of educational timetabling problem and a variety of different benchmark instances have been used by researchers for meaningful scientific comparisons and the exchange of research achievements [START_REF] Qu | A survey of search methodologies and automated system development for examination timetabling[END_REF]. Here we have discussed about the used constraints and their difference from other bench mark instances. We express that these constraints have been covered in our generalized model and these formulations are the subset of our generalized mathematical formulation. Most common and well known instances in literature are as follows.

University of Toronto Benchmark instances

Carter et al. [START_REF] Carter | Examination timetabling: Algorithmic strategies and applications[END_REF] introduced a set of 13 real world examination timetabling problems; three from Canadian highs schools, five from Canadian universities, one from American university, one from British university and one from a Saudi Arabian university. These have been widely used as standard in examination timetabling research. Hard constraints for this problem were to schedule all examinations without conflict. They defined conflict matrix C, where each element C ij = 1 if examination i conflicts with examination j (have common students), or C ij = 0 otherwise. The conflict density was the ratio between the number of elements of value "1" to the total number of elements in the conflict matrix. A student must not sit for more than one examination at any period was used as hard constraint. The objective function was to minimize the number of periods needed and the number of examinations of a student scheduled in the same day consecutively.

Burke et al. [START_REF] Burke | A memetic algorithm for university exam timetabling[END_REF] modified the Toronto benchmark instances by considering the maximum room capacity per period and objective was to minimize the students sitting into two consecutive examinations on the same day. They introduced new examination timetabling datasets coming from University of Nottingham. These were used later by a number of researchers to test different approaches and are called University of Nottingham Benchmarks.

Burke et al. [START_REF] Burke | Initialization strategies and diversity in evolutionary timetabling[END_REF] further modified the above problems by considering also consecutive examinations overnight.

University of Melbourne Benchmark instances

Merlot et al [START_REF] Merlot | A hybrid algorithm for the examination timetabling problem[END_REF] introduced examination timetabling datasets at the PATAT conference in 2002 coming from the University of Melbourne. The objective for these datasets was to minimize the number of occasions of students having two examinations consecutively either on the same day or overnight. For some of the examinations some periods were unavailable.

ITC-2007 Benchmark instance (Examination Timetabling Track)

The 2nd International Timetabling Competition (ITC2007) has three tracks; one on examination timetabling and two on course timetabling. We have discussed tracks on course timetabling in previous section (Section 5.1.2). Here we have described the examination timetabling track introduced as part of the competition [START_REF] Mccollum | Setting the research agenda in automated timetabling[END_REF]42].

These two constraints are used as required constraints in these instances. Required constraints meant that if solution did not satisfy these constraints, solution was rejected outright.

1. Every examination is assigned to at most one room.

2. Every examination is allocated to at most one period. These were the hard constraints for the given problem.

3. Every examination is assigned to at least one room and at least one period 4. The capacity of individual rooms is not exceeded at any time throughout the examination 5. Duration of examination scheduled in period should be less than or equal to the duration of period.

6. In any period, any student is taking at most one examination.

7. Precedence constraints between examinations should be satisfied.

8. Specified pair of examinations must be scheduled in the different period. 9. Specified pair of examinations must not be scheduled in the same period. 10. Some specified examinations must be the sole occupier; it means that if this type of examination is scheduled in any period, then any other examination can not be scheduled in this period. These constraints were used as soft constraints.

11. Two distinct examinations of a same student should not be scheduled in consecutive periods on same day.

12. Two distinct examinations in non-consecutive periods of a same student should not be scheduled on same day.

13. For every student any two of its examinations should be scheduled after a gap of g periods for every day.

14. In any period, all the examinations of same duration should be scheduled.

15. There are some rooms which administration wants to be spare. So these free rooms should not be scheduled.

16. There are some periods which should not be scheduled. So these free periods should remain spare.

These used constraints can be mathematically expressed by using these 14 equations (1),( 2),(3),( 4),( 5),( 6),( 7),( 8),( 9),( 10),( 12),( 13),( 14), [START_REF] Abdullah | Using a randomised iterative improvement algorithm with composite neighbourhood structures for the university course timetabling problem[END_REF] of our generalized examination timetabling formulation of Chapter 4. Constraints (1), ( 2) and (3) of this ITC-2007 track can be written by using equation (1) of our mathematical formulation.

Constraints different from previous benchmark instances

These constraints are different from previously written bench mark instances. We have written a reference in front of each constraint which shows that this constraint was included in mentioned article. This does not mean that this constraint was used only in that specific article, this constraint can be part of many other articles but for convenience we have mentioned only one reference. Some of these constraints were used exactly as we have used and some of them were used with little modification according to the scenario. These constraints are given as follows.

1. All the examinations of a class should be located in the same room on any day [START_REF] Ayob | Intelligent examination timetabling software[END_REF].

2. No class can attend more than a specific number of examinations in a day [START_REF] Sagir | Exam scheduling: Mathematical modeling and parameter estimation with the analytic network process approach[END_REF].

3. All the examinations of a class in a day must be scheduled either in the morning or in the afternoon session [START_REF] Boizumault | Constraint logic programming for examination timetabling[END_REF]. 4. Invigilators are not always available [START_REF] Sagir | Exam scheduling: Mathematical modeling and parameter estimation with the analytic network process approach[END_REF].

5. Number of students scheduled in a period p requiring room type x will be less than or equal to the capacity of rooms of type x available at period p [START_REF] Merlot | A hybrid algorithm for the examination timetabling problem[END_REF].

6. Every examination should be assigned required room type [START_REF] Merlot | A hybrid algorithm for the examination timetabling problem[END_REF].

7. Pre assigned examinations should be scheduled in their pre assigned periods [START_REF] Merlot | A hybrid algorithm for the examination timetabling problem[END_REF].

8. Some examinations should be scheduled on different days [START_REF] Boizumault | Constraint logic programming for examination timetabling[END_REF]. 9. A period can not host examinations more than maximum number of examination's limit for that period [START_REF] White | Using tabu search with longer-term memory and relaxation to create examination timetables[END_REF].

10. Sum of number of students taking examinations at period p should be less than or equal to the capacity allowed for that period p [START_REF] White | Using tabu search with longer-term memory and relaxation to create examination timetables[END_REF].

Constraints not found in the literature

These constraints may have been used in literature but we could not find them in literature as a part of any examination timetabling problem.

1. Examinations supervised by more than one invigilator scheduled in a same period should be assigned same room.

2. Time table should follow minimum and maximum load per day for a invigilator.

3. Invigilators should be given some free days. [START_REF] Duong | Generating complete university course timetables by using local search methods[END_REF]. No examination should be scheduled in the last period of the day. 5. Some examinations should be scheduled on the same day.

Conclusion and Discussion

In this Chapter, we have discussed different instances of course and examination timetabling problems which are sub part of our generalized course and examination timetabling problems.

We have written the mathematical models of these instances by using our generalized examination and course timetabling problem. We have discussed in detail curriculum based course timetabling problem of (ITC-2007) international timetabling competition held in 2007, because we use these competition datasets for our experimental work in forth coming (Chapter 7). We have also demonstrated post enrolment based course timetabling problem of the same competition. We have shown the main difference of this problem with our Chapter 6

PROPOSITION OF RESOLUTION METHODS

In this chapter we have proposed our algorithms which could produce effective solutions for generalized timetabling problems. We have proposed two population based alogorithms named memetic algorithm and honey bee mating algorithm. Memetic algorithm uses a local search to improve the quality of solutions. Neighbourhoods used by this local search are proposed in this chapter as well. We have explained the working procedure of these algorithms in detail and also have discussed the benefits of using different operators in these algorithms. We have highlighted different search space issues and have talked about the beneficial aspects of our chromosome representation. This chapter is arranged as follows. In Section 6.1, we have presented our chromosome representation used in both of our algorithms. We have spoken about search space issues. We have also expressed our ideas to arrange data and for the use of adequate chromosome representation to enhance the search space. In Section 6.2, we have demonstrated the procedure of making initial solution for algorithms. We have discussed different heuristics and repair strategies to construct these solutions. In Section 6.3, we have discussed our memetic algorithm. We have presented different genetic operators, infection and replacement procedures. In this section, we have also explained procedure of our proposed local search and memetic algorithm. Section 6.4 is devoted for honey bee mating algorithm. Section 6.5 is reserved for termination criteria of these algorithms and chapter is concluded in Section 6.6.

Solution representation of Algorithms

The timetable is a collection of each room timetable, where a room timetable is a two dimensional array as shown in Figure 6.1. If no lesson is booked in any period, it is called null booking which has value zero. Maximum one event can be assigned to any place in the matrix. Every timetable stores information that which lesson is placed in which room at what time on which day of the week, each booking (each cell in a matrix) is one gene. A time table has many fields to store information about its genetics, costs, number of violations of constraints. The timetable for an entire university is therefore a collection of room timetables, one for every room in the university as shown in Figure 6.2. A population is a collection of timetables, which also have many fields to store information about timetables like less costly timetable, most costly timetable, average cost, average number of violations of constraints and the total number of timetables in population. It contains a pointer to the least costly timetable in the population, (which has, in turn, a pointer to the next least costly). Timetables are ordered from least costly to most costly. A colony of creatures is therefore a singly-linked list of structured types (creatures) containing timetable data (genes) in a three dimensional array. Figure 6.3 shows the way in which a population is comprised of a linked list of timetables.

Mon

Reduction of search space

Now we shall discuss about our chromosome representation, search space issues and benefits to use this representation. We are using two-dimensional matrix (i.e. grid) representation for our chromosomes where each cell in this matrix is representing an empty slot or at most one event .Benefit of using this representation is that it reduced the search space significantly. If there are m events to schedule in t places then the total number of possible ways to schedule m events in t places is m t where t places means that total available slots which are total number of rooms multiplied by total number of periods (if rooms and periods are always available).

Now the claim of reduction of search space by using the method of this encoding can be proved in this way.

The number of ways to assign m events to t places as we have used in our representation are Where t is greater than m or equal to m always ( m t  ) .Because this is a necessary condition to get feasible solution otherwise feasible solution could not be achieved.

One benefit of this presentation is that double room booking clash can be simply finished. Double room booking means that to schedule more than one lesson in a room in a period. So by using this method on encoding one can avoid one important hard constraint.

We have tackled many other complication steps by using this representation which are helpful to speed up each of remaining procedures of algorithm. These steps involved some additional matrices.

Benefits of using this representation

By making use of a two-dimensional matrix representation in this thesis, now we shall explain how many matrices can be made by using this representation.

Event-Room Matrix

This matrix is used to indicate which event is suitable for which room. This is a Boolean matrix and can easily be calculated that which room r satisfies the conditions to host event e.

Thus if room r satisfies the conditions to host event e then the element (e,r) marks as true otherwise it marks as false. This matrix indicates class period relationships. One benefit of this matrix is to identify the position of class with respect to sessions. Because sometimes some classes should be scheduled in morning sessions and some should be scheduled in evening sessions. If class k can be assigned in period p then element (k,p) marks as true otherwise it marks as false.

Period-Teacher Matrix

This matrix would relate period and teacher requirement. Because some teachers are not available on certain periods so this requirement can be indicated by this matrix. If teacher t is available at period p then element (p,t)marks as true otherwise it marks as false. One can notice that this matrix is not equivalent to course-period matrix. For example, if a course is not available on a period then this does not mean that teacher of that course is not available. It is possible that teacher is available on that specific period to teach any other course.

Initial solution

Population based algorithms are generally used with an initial population. This initial population sometimes is generated randomly and sometimes by using special techniques to make a higher quality initial solutions for population. These techniques are used to give the algorithm a good start and speed up the process. For memetic algorithm, we have generated our initial solution randomly and then repaired it by our proposed repair strategies. For honey bee mating algorithm, we have used heuristics to make initial population of drones and queen. We shall divide the lessons into sets on the basis of their common properties to use them for proposed heuristics. In two step verification strategy, we fulfill two hard constraints.

Pre-processing or division of search space

(1) Every course should be assigned.

(2) The number of assignments of every course should be equal to its number of lessons.

Two step verification strategy

We can call our two step verification strategy as Guided Search strategy or guided two step verification strategy or heuristic.

Stage1

Repeat for every course Ci In first step we see if a course is assigned more than its number of lessons, we remove the extra assignments. In second step we see that if any course is missing or it has assigned less than its number of lessons, we find a new slot randomly and assign it. At the end of this two step verification strategy every course is assigned and its number of assignments is equal to its number of lessons. This is explained in Figure 6.5.

Set forming heuristics

We use the set forming heuristics to make initial solutions for population.

(H1) Make a list of courses in descending order with respect to the strength of course.

Strength of course means that how many students take this course.

(H2) Make a list of courses in ascending order according to their room availability. The course with less available rooms comes first in list.

(H3) Make a list of courses which have more lessons to schedule. This list is also in descending order.

We use these two heuristics (H4 and H5) for the assignment of slot to selected lesson.

(H4) We shall assign slot to these courses randomly.

(H5) We make a list of rooms in ascending order of their capacity.

Then we assign rooms to courses (already selected by a heuristic). For this assignment, we first choose the first room of our list. If the capacity of first room is greater or equal to the size of course, we assign this room to the course. Otherwise we move down in the list until we get the room of required capacity. By doing so, we can save the big capacity rooms for the larger classes in the later stage. In this way, the room capacity conflict can be reduced.

A lesson is chosen according to heuristic H2 and ties were broken by H1 and further ties with H3. Then to find a place for the lesson heuristic H5 was used and ties were broken by H4.

Memetic Algorithm

In this section, we propose our memetic algorithm. We discuss its different operators, initial solution method and local search which is integrated to improve the performance of the algorithm.

Classic genetic algorithm

First of all, algorithm initializes a population of individuals and evaluates the fitness of each member in that population. The procedure for applying these genetic operators is given as: This process repeats until the termination criterion is achieved.



Genetic operators

Evolutionary algorithms are good tools for a big space optimization problems but their performance depends a lot on the type of genetic operator used and the values of parameters such as mutation rate, crossover rate and population size. Mutation operators normally do the random alteration of genes. This is done during the process of copying a chromosome from one generation to the next. Crossover operator is used for exploration in these algorithms.

We used steady state algorithm and general memetic algorithm discussed in Chapter 1, Section 1.8 in our preliminary studies and then compared them. We found general memetic algorithm more efficient as compared to steady state algorithm in our case. Now we describe the three genetic operators and their types in detail.

1. Selection.

Cross over

3. Mutation

Selection

We have used these selection operators: elitism, roulette wheel selection and selecting one parent by elitism and the other parent by roulette wheel selection, after selecting parents, we apply breeding and mutation.

Cross over

We have used different types of crossover operators in our preliminary experiments for the breeding of two parents for proposed memetic algorithm.

1. one-point Crossover 2. two-point Crossover 3. Uniform crossover 4. Apply crossover to some percentage of population and not to all.

5.

No crossover at all.

The details of one-point crossover, two-point crossover and uniform crossover are given in Chapter 1, Section 1.8. We have used these crossover operators for our preliminary experiments but uniform crossover is performing better for our problem. For this purpose we generate a crossover mask randomly for each slot. In this way the child contains a mixture of genes from each parent and the procedure is explained in Figure 6.6. For every slot X1

Generate random mask bits {0,1} for the selected slot if (mask bit equals 1)

Find the information for the slot X1 in P1;

else if (mask bit equals 0)

Find the information for the slot X1 in P2;

end if

We have used two types of mutation for our algorithms. For memtic algorithm, we have used random mutation and for honey bee algorithm we have applied mutation by neighbourhood structures. These are explained in the following:

(i)

We have applied random mutation. The procedure for this mutation is explained in (ii) Many neighbourhood structures were tried within the iterative improvement algorithms; these were tested on post enrolment course timetabling problems (ITC 2007). This proposed approach found some of the good results. Based on their experiments, we have applied some neighbourhood structures within our algorithm. The detail of these neighbourhood structures is given in (Chapter 1, Section 1.6).

A mutation operator is used with a probability Pm. The mutation operator first randomly selects one from two neighbourhood structures N1 and N2 described in Chapter 1 in Section 1.6 (in Chapter 1, they are named N3, N10), and then makes a move within the selected neighbourhood structure. The procedure is given in Figure 6.8. The neighbourhood structures are described as follows:

N1: Neighbourhood defined by an operator that an event can be moved only if the corresponding slot is empty.

For each chromosome

For every gene of that chromosome Generate a random number r by U(0,1000).

If (r<Pm)

Swap current gene with a randomly chosen gene from the current timetable else keep the gene un-mutated.

endif Repair the timetable using two step verification N2: Neighbourhood defined by an operator that swaps the slots of two events.

We can apply mutation to some percentage of population and not to all. For this we can do mutation on 10% or 20 % of the members of the population. And for each member, we can mutate 1 to 20% of the lessons. Lessons are chosen at random from any slot and are reallocated to the next earliest possible slot.

Based on our preliminary tests, we observed that these percentage choices did not show any significant effect on mutation procedure so we did not implement them in our algorithm.

Infection

For memetic algorithm, we have used an infection in population at the chromosomes level instead of genes. It does not work in a deterministic way but it occurs randomly. For this we generate a parameter called number of infections by uniform distribution in (0, 10). These infections will take place after a random number of generations inf g . The value of inf g can be between 0 and maximum number of generations. By doing so, we kill a portion of randomly chosen timetables (m_inf ) of the population colony. Here we have taken m_inf equal to 10 % of the population. And then we restart memetic algorithm by exploiting infection results. The procedure is given in Figure 6.9.

For each chromosome

For every gene of that chromosome Generate a random number r by U(0,1000).

If (r<Pm)

Swap current gene with a gene chosen in the neighbourhood N1 or N2 from the current timetable else keep the gene un-mutated.

endif Repair the timetable using Two step Verification

Proposed Local search

The local search (LS) techniques in genetic algorithms are used for improving the quality of timetables. In our case, we take one or two courses randomly, and swap them by using our neighbourhoods defined below. If it improves the objective function, we accept it otherwise we reject it. If the fitness is adjusted, the chromosome which is the result of local search will be replaced with the primary chromosome; otherwise that primary chromosome is identified as the best solution in its neighbourhood and will remain unchanged. We have used these neighbourhoods for our local search. The pseudo code for the Local Search is described in After making an initial solution, we apply LS to every member created and then put it to population pool.

b)

After applying GA, apply LS to child before putting it to population pool.

We applied these two ways but in (a), the effect of LS is smaller as it applies only to initial solution while in (b), LS improves each generation and improves the quality of solution. So we have used (b) in our algorithms.

Pseudo code of memetic algorithm

In a conventional memetic algorithm, a hill climbing method is applied after the mutation. We propose a memetic algorithm that integrates a local search into the genetic algorithm for solving the university timetabling problem. This local search method uses its exploitive search ability to improve the explorative search ability of genetic algorithm. The pseudo code for proposed memetic algorithm is shown in Figure 6.11.

Figure 6.11: The pseudo code for memetic algorithm

Honey bee algorithm

There are two major types of Honey bee algorithms. First type is a honey bee colony algorithm which was mostly used to solve educational timetabling problems, second type is honey bee mating algorithm.

Honey bee colony Algorithm

Honey bee colony algorithm is about the food collection of the bees. It is a nature inspired algorithm. A colony of honey bees can extend itself over long distances (more than 10 km) and in multiple directions simultaneously to exploit a large number of food sources. A colony will be developed by deploying its foragers to good fields. The patches of flowers with plentiful amounts of nectar or pollen that can be collected with less effort will receive more bees and patches of flowers with less nectar or pollen should be visited by fewer bees.

The foraging process starts in a colony by scout bees being sent to search for promising flower patches. A colony employs a percentage of population as scout bees for exploration of the fields and these scout bees go randomly from one patch to another, when these scout bees come back in hive; they share information with other bees. This information helps the colony to send its bees to flower patches precisely. These information make the relative merit of different patches according to both the quality of the food they provide and the amount of energy needed to harvest it. Then these scout bees go back to flower patches with follower bees that were waiting inside the hive. More follower bees are sent to more promising fields. This helps the colony to gather food quickly and efficiently. The bees monitor food level of the flower patch, if patch is not good enough bees go back in hive and if the patch is still good enough as a food source, then it is advertised and more bees are recruited to that field.

Honey bee mating algorithm

In honey-bee colony, there is a queen(s) (best solution), drones (incumbent solutions), worker(s) (heuristic) and broods (trial solutions). The algorithm describes the natural mating behavior of the queen bee when she goes for mating with drones. Queen adds sperms of drones in her spermatheca during her visit after each successful mating. Queen spermatheca has a fixed size and when this fills up queen comes back in hive to start mating process. After mating process broods are produced which are then fed by worker (all new generated broods The solutions in the population are ranked according to the probability value i p .This can be calculated using equation ( 1).

( Elite drones, on the basis of their probability values. Here we divide the drones in a way that the elite drones have more chances to be improved as these solutions are considered the most promising solutions in the search space. In HBMO-ETP, they consider that all the drones are of the same type. .12), we describe the mating flights of the queen. In each mating flight, queen selects Nc-mat drones from the set of common drones and Ne-mat drones from the set of elite drones. Here we have eliminated the speed and energy parameters which were used in the original HBMO algorithm [START_REF] Abbass | A monogenous MBO approach to satisfiability[END_REF]. Instead we have selected drones via Roulette wheel selection and in a deterministic way. By doing so, we shall exploit the probabilistic nature of RWS to select more diverse solutions. In HBMO-ETP, they eliminated speed parameter but maintained energy parameter to initialize queen's energy for mating flights. This energy parameter defines the number of drones selected during a mating flight. While we have eliminated the speed and energy parameters and used the following two parameters Ncmat (number of common drones for mating during a flight) and Ne-mat (number of elite drones for mating during a flight). If the mating is successful (according to the probabilistic decision rule), the drone's sperm is added into the queen's spermatheca. This process continues until the queen spermatheca is filled.

Next, the queen starts breeding and two types of broods are formed by mating with common drones and elite drones via uniform cross over. While in HBMO-ETP, they applied haploid cross over. The reason for using uniform cross over is to explore the whole solution space and create more diverse broods. After that, the workers already defined for elite broods are applied (i.e. an improvement) to elite broods and the workers specific for the common broods are applied to common broods. We utilize different neighbourhood structures as the workers to grow the broods i.e. to improve the trial solutions. As in the original honey-bee mating optimization algorithm, the workers improve the brood produced from the breeding queen with the possibility of replacing the queen if the improved brood is better than the current queen.

Table 6.2 shows a summary of differences and similarities between our HBM and that of original algorithm [START_REF] Abbass | A monogenous MBO approach to satisfiability[END_REF] and its variant HBMO-ETP. Table 6.2: Differences and similarities between our HBM algorithm, HBMO [START_REF] Abbass | A monogenous MBO approach to satisfiability[END_REF] and HBMO-ETP [START_REF] Sabar | A honey-bee mating optimization algorithm for educational timetabling problems[END_REF] In HBM algorithm, we update the population of drones iteratively to avoid undeveloped convergence. In the original HBMO [START_REF] Abbass | A monogenous MBO approach to satisfiability[END_REF] all broods are killed and the new mating flight begins using the previous population. But we kill the older drones used in breeding process and replace them with the new mutated broods. So the next mating flight starts with fresh drones. This replacement guarantees that each drone's sperm can be used only one time which, we hope, helps in maintaining diversity and prevents immature convergence. During each mating flight, queen selects one elite drone from the set of elite drones in such a way that each elite drone will be selected at the end of mating flights. And queen chooses Nc-mat common drones via RWS from the set of common drones during each mating flight.

Lines 1-8 show the initialized values for the defined parameters. These are following: (i) the number of queens (ii) the queen's spermatheca size, which represents the maximum number of mating each queen performs in a single mating flight, thus also the number of broods that will be born after each single mating flight and (iii) the number of workers to improve common broods and elite broods. We use workers (heuristic Search) for our common broods and elite broods.

In lines 9 to 11, the drone population is generated by using heuristics described earlier. The status of queen Q is given to the fittest solution in lines 14 and 15. Lines 16-18 show the division of drones into two categories on the basis of their probability calculated using equation [START_REF] Zhipeng | Adaptive tabu search for course timetabling[END_REF]. In lines 19-22, we describe the mating flights of the queen. In each mating flight, queen selects Nc-mat drones from the set of common drones and Ne-mat drones from the set of elite drones. The accepted drones are added to the queen's spermatheca. Based on Eq. ( 1), the fitter drones have more chance of being selected. This procedure is repeated until the queen's maximum spermatheca size is reached.

Then, the breeding process starts from line 23. Two types of new broods are created. In lines 24-28 we use Uniform cross over for mating of queen and common drone. Then an already specified worker (Local search hybridized with heuristic) is recruited to grow this brood. In lines 29-32 queen mates with an elite drone by uniform cross over to produce another brood.

Then a worker specific for elite broods (Local search hybridized with heuristic) is recruited to grow this brood. The mating generates a new set of broods.

This hybridized local search starts with an initial solution (brood) and iteratively improves it by examining its neighbourhood. A neighbourhood of a given solution is obtained by moving one event from its current slot to another slot, which is selected by a heuristic. The solution is accepted, if the move does not violate any hard constraints and the quality of the neighbourhood solution is better than the incumbent solution. Otherwise, the solution is rejected and a new event is selected to generate a neighbourhood solution.

In our HBM algorithm, a chromosome is used to represent a candidate solution i s to the problem. We have used the same representation of chromosomes as we employed for our memetic algorithm. If the improved brood is better than the queen, the queen is replaced by the brood. Otherwise we keep the original queen as the best solution. The new broods will be modified using a mutation operator. In this work, we employed two neighbourhood structures (N1 and N2) for this purpose. These neighbourhoods are applied to each brood. The modified broods will replace the older drones for the next mating flight. This process is repeated until the stopping condition is satisfied. It may be time limit, number of iterations or allowed minimum value for objective function. In this algorithm, we take the time limit as stopping condition. As the time limit is reached, the fittest solution found is returned as queen. And this final queen is the solution of the given problem.

Termination criteria

This iterative process continues until one of the possible termination criteria is reached.

Different types of termination criteria can be used such as, getting optimal solution (in case of some easy datasets), obtaining acceptable solution, maximum number of generations, time limit and no improvement in objective function value during a certain number of generations.

We have used time limit or getting optimal solution as termination criteria for our problem which achieves first.

Conclusion

In this chapter we have proposed our algorithms for solving university course and examination timetabling problems. In any algorithm its solution representation plays a significant role for making its performance good. We have discussed in detail chromosome representation of our memetic algorithm. This matrix form representation has many benefits to evaluate violations of constraints and in reducing the search space. We have defined many matrices from this matrix representation which helps the algorithm for finding violations of constraints like room-period matrix, course-period matrix, class-period matrix, periodteacher matrix, event-room matrix and conflict matrix.

Our algorithms are population based algorithms. We have discussed to make initial solutions for population of these algorithms. We have explained in detail the procedure of making initial solutions for algorithms. We have used many ways to make initial solutions in our prerequisite experiments and have finally explained which procedures are producing good results for our experimental work. We have demonstrated the procedure of making initial solution by our proposed heuristics. We have also talked about the procedure of our cross over and mutation for memetic algorithm. How much different selection ways have been used generic university course timetabling problem [START_REF] Ahmad | Generic model for university course timetabling problem solved by genetic algorithm[END_REF]. But our new generalized model has more constraints than our previously used problem for genetic algorithm.

Our algorithm is a two phase algorithm which satisfies the soft constraint in the first phase.

Second phase is used to minimize the soft constraints while maintaining solution feasible. We hope that if we increase number of iterations of our algorithm, this will minimize the objective function value more.

Many authors had worked on this timetabling problem and produced very good solutions.

In this section we have generated data for our generalized problem and have solved these datasets with our proposed algorithms to compare their performance.

Description of the generalized course timetabling problem

In this section we have defined our generalized course timetabling problem having many constraints. Which constraint is used as hard and which constraint is used as soft is mentioned in below given tables (Table 7.5 and We have tried all constraints in preliminary experiments but excluded few of them in our experimental work. Because few constraints were contradicting each other so their use at a same time is not adequate and some constraints were making problem more complex. For example gap of specific periods in teacher courses, same class two courses should not be scheduled on consecutive periods and class can have maximum two consecutive courses can effect compactness constraints like room compactness, class compactness, course compactness. Some constraints like all the course of a class must be scheduled either in morning or afternoon session or course should not be scheduled in the last period of day was excluded to make search space little lenient because problem has already many constraints.

How we have generated our data for these problems, details of data generations are given as follows.

Total number of courses, classes, teachers, rooms, room types, days and number of periods per day are fixed. Each teacher has assigned at least one and at most two courses.

1. For each class, number of courses is randomly generated from 1 to 4; a course can be part of maximum 4 classes.

2. Number of students who attend a certain course is randomly chosen between 20 and 100.

3. For each course, we choose a random number 2 to 5 which shows the number of lessons of course.

4. For each course, it is required that it should not finish its lessons before a minimum number of days. We have taken randomly minimum number of day from 1 to 3.

5. Each room capacity is randomly generated from 30 to 120.

6. One lesson of each course is randomly pre assigned a period.

7.

For each course, it is required that it should not be scheduled after a fix maximum number of days. We have taken randomly maximum number of day from 3 to 5.

8. The maximum daily number of teaching hours allowed for any class is 4.

9. For each course, maximum limit on number of teaching hours per day is randomly taken from 1 to 5.

10. Every course needs a desired type of room to occur. We have specified number of room types. We have allocated a room type to a course randomly.

11. For each room, we generate an availability matrix. In this matrix, we make each room has 5-10% unavailability.

12. For each teacher, we have certain number of unavailabilities. We have generated these unavailable periods randomly. These periods are 10% of the total number of periods.

13. Each teacher has maximum working days and minimum working days. We have assigned these values randomly from 2 to 4 days for maximum working days and from 1 to 2 for minimum working days.

14. On the day, on which a teacher has a course to teach, there is a maximum load of teacher for that day. The maximum working load is defined here in terms of working hours. For each teacher, we take it 5, so this is a trivial condition.

15. Each course has its 12 % randomly chosen unavailable periods, where its scheduling is forbidden.

16. For each period, we have defined the maximum number of classes occurred is taken equal to the number of rooms available at this period. 17. We have generated randomly 5, 2, 1 precedence relations (one precedence relation means that we have chosen two courses and this precedence relation is between every lesson of these two courses) respectively for large, medium, small data in such a way that the generated data should not be contradictory. For example if lesson a is preceded by b and b is preceded by a then these two precedence constraints are contradictory.

We can find similar precedence relationship in real world problems when we have course consisting of theory and practical work, practical work should occur after the theory lecture (each theory lesson follows practical work lesson). This relationship should be followed for every occurrence of theory and practical work.

18. Five percent lessons (from non conflicting courses) are grouped into two or three lessons subsets randomly which should scheduled together in same period. Each lesson can be part of at most one sub set.

19. Three percent lessons are selected randomly, grouped into two or three lessons subsets randomly which should not be scheduled together in same period. Each lesson can be part of at most one sub set.

20. One period is chosen randomly to be free.

21. One day is randomly chosen free for a teacher.

working days. After running each problem dataset 5 times, we have given minimum cost, maximum cost, average cost, S.D. (standard deviation), total number of lessons (events) and percentage of used slots and seats.

Small size datasets have C=20, T=16, K=6, R=4, RT=1, P=5, D=5. Medium size problem datasets have C=70, T=56, K=40, R=12, RT=3, P=5, D=5 and similarly large size problem datasets have C=125, T=100, K=70, R=20, RT=3, P=5, D=5.

In this section, we have given results obtained by honey bee mating, memetic, gentic and tabu search algorithms across 5 runs on each of the 10 datasets of small, medium, large size problem. We have taken mutation rate 7, kill colony 20 percent, population size 100, time limit for small datasets 100 seconds, time limit for medium datasets 400 seconds and time limit for large datasets is fixed 600 seconds.

Memetic algorithm

In this section, we have given results (

Minimum cost Comparison of all algorithms

In this section, we have given comparison of minimum cost results obtained by all algorithms (Table 7.19, Table 7.20, Table 7.21). Results of Honey bee mating and memetic algorithms are same for small datasets, while results of genetic algorithms are better than tabu search algorithm.

For medium datasets, on some datasets honey bee mating algorithm is giving good results but for others memetic algorithm's performance is better. Memtic algorithm has given good results on 7 datasets while honey bee mating algorithm has given good results on 3 datasets.

Thus for medium datasets, memetic algorithm has performed better than honey bee mating algorithm. Genetic algorithm performance is better than tabu search algorithm but for one dataset genetic algorithm is exceptionally performing well.

For large datasets, honey bee mating algorithm's performance is far better than memtic algorithm. Honey bee mating algorithm results are better than memetic algorithm for 9 datasets out of total 10.

We think honey bee mating algorithm's performance is better due to its ability to explore and exploit the search space simultaneously by using probabilistically guided search by the queen's transition and by employing local search at each iteration. The queen (current fittest solution) is the best individual and every new brood is the composition of some parts of the drone's genotype with parts of the queen genotypes. So it is hoped that it will evolve superior solutions. Again genetic algorithm is performing better than tabu search algorithm.

Datasets

Average cost Comparison of all algorithms

In this section, we have given ccomparison of average cost results obtained by all algorithms (Table 7.25, Table 7.26, Table 7.27). Average cost for honey bee mating and memetic algorithms are almost same, average cost for tabu search algorithm is better than genetic algorithm for small dataset. For medium datasets, honey bee mating algorithm average cost is better than memetic algorithm for 6 datasets.

Average of genetic algorithm is better than tabu search algorithm. We have seen from our results that tabu search algorithm perform well for small datasets but its performance decreases as size of dataset increases comparing with genetic algorithm. For large datasets average cost of honey bee mating algorithm if far better than memetic algorithm and similarly genetic algorithm is far better than genetic algorithm for large size datasets. work we do not take different types of rooms as we take for course timetabling but these can also be added easily on the same lines like course timetabling problem Details of data generations are given as follows.

Total number of examinations, classes, rooms, days, number of periods per day is fixed.

1. For each class, number of examinations is randomly generated from 2 to 5; an examination can be part of maximum 25 different classes.

2. Number of students who take examination is randomly chosen between 5 and 100.

3. Each room capacity is randomly generated from 20 to 100.

4. Duration of each examination is randomly chosen from 1 to 4.

5. Duration of each period is also randomly generated from 1 to 4.

For large data

Here we present some more details about our data which are different for large, medium and small problems. 10. 2 periods are unavailable (chosen randomly).

11. Maximum examinations of a class per day limit is set 3.

12. Maximum examinations per room limit is set 3.

13. Allowed time for large problem is 400 seconds. 8. We have chosen 20 pairs of examinations which have coincidence relation to satisfy. 9. Two rooms are unavailable (chosen randomly).

10.One period is unavailable (chosen randomly).

11. Maximum examinations of a class per day limit is set 3.

12. Maximum examinations per room limit is set 2.

13. Allowed time for medium problem is 200 seconds.

For small data 1. Number of examinations for small problem are 20.

2. Number of clases for small problem is taken 6, these classes are generated randomly (each class has 2 to 5 examinations chosen randomly).

3. Total number of rooms is 2.

4. Number of days is 4.

5. Number of periods is also 4.

6.

Number of examination which should be the sole occupier of the roon is 2 (randomly chosen).

7. We have selected randomly 9 pairs of examinations which have precedence relation to satisfy.

8. We have chosen 4 pairs of examinations which have coincidence relation to satisfy. 9. One room is unavailable (chosen randomly).

10. One periods is unavailable (chosen randomly).

IV 2.5Ghz processor with 4GB RAM under a Windows operating system for these experiments (and indeed for all experiments described in this thesis).

The behavior of these algorithms with the small, medium and large datasets in our experiments is actually noticed different in each case. Algorithms performance is well across the set of small datasets and there is less difference of performance for these datasets. Our algorithms are two-stage algorithms, which operates by first constructing a population of fully feasible timetables, and then evolves these whilst always remaining in feasible areas of the search space.

Our initial motivations for designing an evolutionary algorithm were as follows:

(1) Even though many different types of metaheuristic algorithm were submitted to the International Timetabling Competition, interestingly none of the entrants chose to make use of any sort of evolutionary technique.

(2) The other purpose of this algorithm was to get a feasible timetable in relatively small amounts of time by using two phase procedure.

We therefore consider it interesting to develop an evolutionary algorithm to solve our generalized timetabling problem that can follow this two phase approach and we can check its performance.

Our preliminary tests show that existing bench mark datasets (of ITC 2007: curriculum based course timetabling problem) can be easily solved with this algorithm for obtaining feasible solutions (solution that satisfies the hard constraints only). We have generated some datasets for this purpose. We have observed that if we increase the killing rate it would decrease the speed of algorithm but it will decrease objective function value in less number of iterations.

Our population based algorithms are two phase algorithms. They eliminate hard constraints in first phase and try to satisfy soft constraints in second phase. The first phases take only 3-5 % of total time used. While the second phase takes the rest of the time.

Cost on y-axis and number of iterations on x-axis The local search based algorithm (Tabu search) performs in single phase. It try to satisfy hard and soft constraints simultaneously. In tabu search, we have taken length of tabu list equal to 5. Figure 7.1 shows that tabu search is performing worst. The possible reason can be that in this tabu search, we have not used aspiration criteria or any guided search strategy for neighbourhood moves. By doing so, the search process may loos some good solutions.

In our preliminary experiments, we found that solutions obtained with simple local search in start are better than genetic algorithm but after certain time local search may trap in local minima and genetic algorithm continues its improvement as number of iterations increases.

We think it is due to large number of population and the special genetic operators; these genetic operators provide diversity to genetic algorithm and also help to avoid from local minima. quickly but then it reduces the value slowly. Genetic algorithm starts with relatively small cost value but after few seconds memetic algorithm and honey bee mating algorithms reach genetic algorithm and perform better till end.

Our experiments on datasets have shown that tabu search and genetic algorithm performance is good on small datasets, it constructs good solutions in comparison with memetic and honey bee algorithms. But large datasets affect their performance and tabu search algorithm could not produce good results on these problems. Although genetic algorithm performs relatively well than tabu sarch algorithm. We have found best results with honey bee mating and memetic algorithms.

GENERAL CONCLUSION

In this thesis we have examined various algorithms for university and examination timetabling problems. We have given a general conclusion of thesis and future perspectives here.

In Chapter 1, we have given an introduction of educational timetabling problems and the approaches used to solve these problems. We have discussed different types of educational timetabling problems with different types of constraints which makes this type of problem really difficult. We have focused on different metaheuristics used in literature to solve timetabling problems like local search based and population based metaheuristics because we have proposed metaheuristics to solve timetabling problems.In Chapter 2, We have formulated two mathematical formulations of course timetabling problem which are the prototype of single-mode RCPSP, which are linear integer programming models and could be solved by using linear programming solvers.

We have given a generalized mathematical formulation for university course timetabling problem in Chapter 3. We have written many constraints of different university environments in their mathematical relations. For that purpose, we have defined sets, subsets, different parameters and decision variables needed for formulating this generic model. These constraints are classified in six sets namely, hard constraints, period related constraints, room related constraints, class related constraints, course related constraints and teacher related constraints. We have also discussed how different objective functions could be written from soft constraint relations by using this generic model. We have given a generic model for examination timetabling problem in Chapter 4.

We have discussed different instances of course and examination timetabling problems which are sub problems of our generalized course and examination timetabling problems in Chapter 5. We have shown that how mathematical models of these instances can be deduced from our generalized examination and course timetabling problem.

We have proposed our algorithms for solving university course and examination timetabling problems in Chapter 6. These are population based algorithms, namely, memetic and honey bee mating algorithm. We have explained their solution representations, their parameters and operators in detail. We have proposed a local search to use in memetic algorithm. We have discussed procedures to make initial solutions for these population based algorithms.

  REFERENCES ................................................................................

  Figure 1.1: a and b: Illustration of simple swap .......................................................................

  Figure 1.1: a and b: Illustration of simple swap .......................................................................

Figure 1 . 2 :

 12 Figure 1.2: Illustration of room swap neighborhood ...............................................................

Figure 1 . 3 :

 13 Figure 1.3: Illustration of time swap neighborhood .................................................................

Figure 1 . 4 :

 14 Figure 1.4: Kemp chain illustration ..........................................................................................

Figure 1 . 5 :

 15 Figure 1.5: Describing the relationship between the graph colouring problem and a simple timetabling problem (only considering lesson conflict constraint). .........................................

Figure 1 . 6 :

 16 Figure 1.6: Associated conflict graph of lessons ......................................................................

Figure 1 . 7 :

 17 Figure 1.7: Repair procedure for Course's conflict ..................................................................

Figure 1 . 8 :

 18 Figure 1.8: Repair procedure for teacher's conflict .................................................................

Figure 1 . 9 :

 19 Figure 1.9: Build procedure Lewis thesis [102] .......................................................................

Figure 1 . 10 :

 110 Figure 1.10: Picture expressing roulette wheel selection .........................................................

Figure 1 . 11 :

 111 Figure 1.11: Picture expressing one point crossover ................................................................

Figure 1 . 12 :

 112 Figure 1.12: Picture expressing two point crossover ...............................................................

Figure 1 . 13 :

 113 Figure 1.13: Picture expressing uniform crossover ..................................................................

Figure 1 . 14 :

 114 Figure 1.14: Original HBMO for SAT [68] .............................................................................

Figure 6 . 1 :

 61 Figure 6.1: Example of a single room timetable ....................................................................

Figure 6 . 2 :

 62 Figure 6.2: An entire university timetable .............................................................................

Figure 6 . 3 :

 63 Figure 6.3: Population of timetables ......................................................................................

Figure 6 . 4 :

 64 Figure 6.4: Procedure for room repair strategy ......................................................................

Figure 6 . 5 :

 65 Figure 6.5: Two step verification strategy (Repair procedure for violation of two hard constraints) .............................................................................................................................

Figure 6 . 6 :

 66 Figure 6.6: Procedure for crossover ......................................................................................

Figure 6 . 7 :

 67 Figure 6.7: Procedure for random mutation ...........................................................................

Figure 6 . 8 :

 68 Figure 6.8: Procedure for mutation by neighbourhood ..........................................................

Figure 6 . 9 :

 69 Figure 6.9: Infection ...............................................................................................................

Figure 6 . 10 :

 610 Figure 6.10: The pseudo code for Local Search .....................................................................

Figure 6 . 11 :

 611 Figure 6.11: The pseudo code for memetic algorithm ...........................................................

Figure 6 . 12 :

 612 Figure 6.12: Pseudo Code for Honey Bee Mating Algorithm ................................................

Figure 6 . 13 :Figure 7 . 1 :

 61371 Figure 6.13: The block diagram for the proposed algorithm .................................................

Figure 7 . 2 :

 72 Figure 7.2: Showing the comparison of different selection operators for memetic algorithm ................................................................................................................................................

Figure 7 . 3 :

 73 Figure 7.3: Time and cost comparison of all algorithms ........................................................

1 : 54 Table 3 . 1 : 81 Table 5 . 1 : 104 Table 5 . 2 :

 15431815110452 Lists papers related to course and examination timetabling problem ..................... Solution of timetabling example by CPLEX .......................................................... Score matrix ......................................................................................................... Rank matrix and mean ranks ................................................................................. 104 Table

  .................................................................................................................... 140 Table 6.3: Parameter settings for our HBM algorithm's computational experiments ........... 142 Table 7.1: Showing dataset number, dataset name, total number of rooms, total number of periods, total number of courses, the sum of their events in a week and the number of curricula. ................................................................................................................................. 149 Table

152 Table 7 . 5 :

 15275 : Our memetic algorithm's (Our MA) results (minimize objective function value) in comparison with some other used techniques for International timetabling competition datasets (ITC-2007). ............................................................................................................... Showing constraints for Problem.1 and provides details about every constraint whether it is used as hard or soft. If it is used as a soft constraint then it also tells about the amount of penalty used in case of violation. .......................................................................... 154

  search algorithms for small datasets. ...................................................................................... Table 7.20: Minimum cost comparison of honey bee mating, memetic, genetic and tabu search algorithms for medium datasets. ................................................................................. Table 7.21: Minimum cost comparison of honey bee mating, memetic, genetic and tabu search algorithms for large datasets. ...................................................................................... Table 7.22: Maximum cost comparison of honey bee mating, memetic, genetic and tabu search algorithms for small datasets. ...................................................................................... Table 7.23: Maximum cost comparison of honey bee mating, memetic, genetic and tabu search algorithms for medium datasets. ................................................................................. Table 7.24: Maximum cost comparison of honey bee mating, memetic, genetic and tabu search algorithms for large datasets. ...................................................................................... Table 7.25: Average cost comparison results of honey bee mating, memetic, genetic and tabu search algorithms for small datasets. ...................................................................................... Table 7.26: Average cost comparison results of honey bee mating, memetic, genetic and tabu search algorithms for medium datasets. ................................................................................. Table 7.27: Average cost comparison results of honey bee mating, memetic, genetic and tabu search algorithms for large datasets. ......................................................................................

  Maximise cost which is the measure of desirability of teachers or maximize the satisfaction degree of teachers  Maximize total sum of rooms and time slots preference values  Minimize the total number of non-assigned subjects  Minimize the weighted sum of penalties of soft constraints or minimize the violation of soft constraints  Minimize the assignment cost, the maximum total assignment at undesired time slots simultaneously  Timetable of each class should be compact These kinds of objective functions had been repeated in many articles. Most of the time composite objective function with the minimization of weighted sum of penalties of soft constraints had been used, so objective function would mainly depend upon these soft constraints.Some mostly used objective functions for examination timetabling problems are described as follows.

2 c and 2 c

 2 Figure 1.1: a and b: Illustration of simple swap

Figure 1 . 2 :

 12 Figure 1.2: Illustration of room swap neighborhood

Figure 1 . 3 :

 13 Figure 1.3: Illustration of time swap neighborhood

6 K

 6 swap one of the chains can be empty. Let us suppose that this empty kempchain is  {} . In this case kemp swap move generates into a single kemp chain interchange. It means that we have to move i p with )

  can notice that this double kemp chain is the generalization of single kemp chain interchange.

  The graph colouring solution is converted back into a valid timetable, where each colour represents a period.

Figure 1 . 5 :

 15 Figure 1.5: Describing the relationship between the graph colouring problem and a simple

Math 101 andFigure 1 . 6 :

 10116 Figure 1.6: Associated conflict graph of lessons

1. 8 . 2 . 1

 821 Local search based algorithms Metaheuristic methods are often classified as Local search based techniques and Population based techniques. Local search methods solve problems by searching from an incumbent solution to its neighbourhood. Different local search techniques can be distinguished by neighbourhood structures and moving operators within the search space. The search is guided by defined cost function, which is used to measure the quality of the generated solutions. The performance and efficiency depend a lot upon the parameters and search space properties. In this section, we shall talk about different local search based techniques and their variants used in literature to solve educational timetabling problem. We first start from tabu search algorithm.

Figure. 1

 1 how these repair functions work in evolutionary algorithms.

Figure 1 . 7 :Case 1 :Case 2 :

 1712 Figure 1.7: Repair procedure for Course's conflict

Figure 1 . 8 :

 18 Figure 1.8: Repair procedure for teacher's conflict

Figure 1 . 9 :

 19 Figure1.9: Build procedure Lewis thesis[START_REF] Lewis | Metaheuristics For University Course Timetabling[END_REF]

4 . 8 .

 48 Move e to p; 5. if (U =  ) end; Insert-Events (tt, U, r, len (tt));

  Figure 1.10.

Figure 1 . 10 :

 110 Figure 1.10: Picture expressing roulette wheel selection

  obtained organisms are the new children (as shown in Figure.1.11).

Figure 1 . 11 :

 111 Figure 1.11: Picture expressing one point crossover

Figure 1 . 12 :

 112 Figure 1.12: Picture expressing two point crossover

Figure 1 . 13 :

 113 Figure 1.13: Picture expressing uniform crossover

1 2 32 

 132 equal size ranges. So a binary string can be converted to a real number as follows:First we convert binary string of length 32 from base 2 to base 10.x* = ( (b31 b30....b0) )2 5 is the length of the domain. For example, a chromosome (11110011110010101001011110100111) is representing the number 0.476155032 in [0, 0.5] since * x = (11110011110010101001011110100111)2 = (4090140583)10 and the real number is x = (4090140583)

i c where 1 ≤

 1 i ≤ 10 and their corresponding real value i x on the interval [0, 0.5]. c1 = (01101110010010110001111111101001) x1 = 0.21541691 c2 = (11000000001100100111010011011111) x2 = 0.37538495 c3 = (11110011110010101001011110100111) x3 = 0.47615503 c4 = (10001100010110101011110101110100) x4 = 0.27412979 c5 = (10010100101100110001000010100000) x5 = 0.29042866 c6 = (10000110110110000100100000000000) x6 = 0.26336884 c7 = (01100101000110110101101011110000) x7 = 0.19747433 c8 = (11010110010111110111001010110111) x8 = 0.41869696 c9 = (01011001000010001110001110010111) x9 = 0.17389594 c10 = (11001010100101001111100010101010) x10 = 0.39566781 Objective function Here objective function obj for chromosomes is equal to the original function f, obj(c) = f(x) where x represents the corresponding real value and c represents the chromosomes.

j d , where 1 dj - 1 .

 11 =0 and  j d = 0. There are R renewable resource types. The availability of each resource type r in each time period t is rt a units, r = 1,…,R. Each activity j requires jr u units of resource r during each period of its duration wherer u 1 = 0,  jr u =0, r = 1,…, R.All parameters are assumed to be non-negative integer valued. There are precedence relations of the finish-start type with a zero parameter value (i.e., FS = 0) defined between the activities. In other words, activity i precedes activity j if j cannot start until i has been completed. The structure of a project can be represented by an activity-on-node network G = (V,A), where V is the set of activities and A is the set of precedence relationships. j F ( j P ) is the set of successors (predecessors) of activity j. It is The objective of the RCPSP is to find a schedule S of the activities, i.e., a set of starting times ( constraints are satisfied, such that the schedule duration T(S) =  j s is minimized.Our problem is based on non preemptive activities but in RCPSP activities could be preempted during processing at integer points in time, i.e., the fixed integer processing time j d of activity j may be split into j = 1, 2 , …, j d process units. Time windows can be specified for every activity, [EFj, LFj], which denote the earliest and latest finishing time for activity j, and [ESj, LSj] which denote the earliest and latest starting time for activity j. This problem specifies a minimal and maximal time lag between tasks. A minimal time lag specifies that an activity can only start or finish when the predecessor activity has already started (finished) for a certain time period. A schedule S is called feasible if in each time period t the total resource demand is less than or equal to the availability rt a of each resource type r, and the given precedence constraints are fulfilled. We call a problem of finding a feasible schedule with completion times Cj such that Cj ≤ T for j = 2,…, _ j -1 a search problem or feasibility problem. A search problem with threshold value T has a solution if and only if a schedule S exists such that the makespan ) thanT. The RCPSP is usually formulated as the problem of finding a feasible schedule which minimizes the makespan. Other important objective functions besides are based on cost functions ) (t f j for the activities. One has to find a feasible schedule which minimizes the

ra= 1 ES  1 EF 0 ,

 110 Constant room availability of room type r rt a = Availability of rooms of type r in period t jr u = Use of room type r per period by job j, which is always one p J =Set of lessons taught by teacher p r J = Set of lessons requiring rooms of type r r Y = Set of rooms of type r j ES = Earliest starting time of lesson j j LF = Latest finishing time of lesson j j P = Set of lessons which precede lesson j j F = Set of lessons which follow lesson j j d = Duration of an activity j Lesson 1 and lesson _ j are dummy lessons, which are called generally source and sink. To ease presentation, durations and resource usages for these lessons is considered zero. Earliest starting and latest finishing times can be obtained by a forward and backward pass respectively. Starting with  the forward pass calculates earliest starting and finishing times as follows. This is a set of lessons which are eligible to schedule for a period t. The latest finishing and earliest starting times correspond to time points delimiting periods. So it is important to clear difference of time period and time point for better understanding of the formulation. Two time points t and t+1 define the start and the end of period t+1 respectively. If earliest starting time of any lesson is j ES then the earliest time period for its execution could be 1  j ES .

cn=C=

  Number of teaching hours to be scheduled per week for every course c  C min c n = Minimum daily number of teaching hours (no less than min c n teaching hours have to be assigned to day d, if the course c is scheduled in day d) max c n = Maximum daily number of teaching hours (no less than max c n teaching hours have to be assigned to the day d, if the course c is scheduled in day d) d t = First period of the morning session in day d d l = First period of the afternoon session in day d k C  C = Set of the courses that class k should attend, for every class k. Unlike the School timetabling problem, some classes can be joined to attend the same courses, i.e.,  C = Subset of courses taught by teacher t for every teacher t t e = Maximum weekly number of teaching days allowed for the teacher t l g = Maximum gap between two teaching hours (lessons) of any teacher t max l = Maximum daily number of teaching hours allowed for any class max k l = Maximum daily number of teaching hours allowed for every class K k  min k l = Minimum daily number of teaching hours limit for every class K k  cd l max = Maximum daily number of teaching hours allowed for every course C c  cd l min = Minimum daily number of teaching hours allowed for every course C c  lt max = Maximum load per day for every teacher t lt min = Minimum load per day for every teacher t lp max = Maximum lessons scheduled per period p cp d = Desirability of scheduling the course c at period p, usually cp d measures the desirability of the period p for the teacher t (  c t C ) r P  P = Set of periods for which room r is available, for every R r  t P  P = Set of periods for which teacher t is available, for every T t  x C  C = Set of courses requiring rooms of type x, for every X x  x R  R = Set of rooms of type x, for every X x  xp m Number of rooms of type x available at period p, for every P p  and X x  c P  P = Set of pre assigned periods for course c, for every C c  d P  P = Set of periods for day d, for every Set of last periods of days A  C = Set of pre assigned courses c p _  P = Set of forbidden periods for course c, for every C c  k P  P = set of periods for which class k is unavailable, for every K k  F  C = set of courses for which periods are forbidden (all periods are not available) f R  R = set of rooms which should be free in timetable, it means that no course C c  should be scheduled in any period p P, in these rooms. t R  R = set of rooms, which are in the preference list of teacher t, for every T t  f P  P = set of periods which should be free in timetable, it means that no course C c  should be scheduled in any room r R, in these periods. wc min = Minimum working days for course c wc max = Maximum working days for course c c s = Number of students in course c r a = capacity of room r

  maximum number of scheduled lessons should be less than or equal to positive integer periods in which no lesson should be scheduled. So these free periods should

2

 2

  All the courses of a class k in the day d must be scheduled either in the morning or in the afternoon session. For example, if class k attends course i c in the morning session of day d

  should be assigned on the same day.

  should be assigned on different days.

1

 1

  is requirement that some courses should not be scheduled on the same period. This constraint is like class clash constraint where lessons of same class can not be scheduled in same period. Let us suppose which should be scheduled on the same period. Let us suppose should be scheduled on the same periods.

  course C c  can have less than cd l min teaching hours a day.

FF

  violations for minimum working days constraint for all courses sum of minimum rooms usage violations for all courses F(c,d) =     C c D d cd m = Total course compactness violations done by all courses over all days F(k,d) = class compactness violations done by all classes over all days violations of occurance of classes in the last period of the day G(k,d) =  violations by all classes over all days for more than two violations of scheduling single course of any class on any day Where

C 1 C 1 C 3 PTable 3 . 1 :

 11331 Set of the courses that the class k should attend, Set of courses requiring rooms of type x, = {1, 3}, 2 C = {2, 4} c P = Set of forbidden periods for course c, 1 P = {1,2,7}, 2 P ={3,4,6}, ={1,4} F= set of courses for which there exists forbidden periods, F = {1, 2, 3} xp m = Number of rooms of type x available at period p, for every p P cp d = Desirability of scheduling the course c at period p, usually cp d measures the desirability of the period p for the teacher t (c Solution of timetabling example by CPLEX Mathematical model of the problem can be written in this way.

  crp

,

  D = {1,…, d  }.

  First period of the morning session in day d d l = First period of the afternoon session in day d k E  E = set of the examinations that the class k should take so E  E = set of the examinations which are the sole occupier (means that these examinations will not share room and period with any other examination).

P

   P = set of forbidden periods for examination e, for every E e  F  E = set of examinations for which some periods are forbidden f R  R = set of rooms which should be free in timetable, it means that any examination E e 

xE

   E =set of examinations requiring rooms of type x, for every X x  x R  R = set of rooms of type x, for every X x  xp C = capacity of rooms of type x available in period p max k l = Maximum daily number of examinations allowed for every class K k  d P  P = set of periods for day d, for every D d  i E  E = subset of examinations supervised by invigilator i for every invigilator i i e = Maximum number of working days allowed for the invigilator i load per day for every invigilator i li min = Minimum load per day for every invigilator i r P  P = set of periods for which room r is available, for every R r  i P  P = set of periods for which invigilator i is available, for every I i  A  E = set of pre assigned examinations (pre assigned period) B  E = set of pre assigned examinations (pre assigned room) e p = Pre assigned period for examination e, for every A e  e r = Pre assigned room for examination e, for every B e  ' d P   P = set of last periods of days ep max = Maximum examinations scheduled per period p e s = Number of students in examination e r a = capacity of room r p a = capacity of period p

  e scheduled in period p should be less than or equal to the duration of period p.

6 )

 6 There are examinations which should be scheduled on the same period. Let us suppose which should be scheduled on same periods.

  examinations of a class k should not be scheduled in a row on each day

  of a class k  K scheduled in a day d  D should be located in the same room r  R. the examinations of a class k in the day d must be scheduled either in the morning or in the afternoon session. For example, if class k takes examination 1 e in the morning session of day d

1

 1

  examination e will not be scheduled in the last period of the day. examinations should be scheduled on different days. Let should be assigned on different days.

  of students taking examinations at period p should be less than or equal to the capacity allowed for that period p. B e  , examination e will be scheduled in its pre assigned room

  ): Chapter 3) which are used generally as hard constraint in course timetabling problem everywhere. Examination timetabling problems are different from course timetabling problems because each examination has a unique entity but in course timetabling each course has many lessons to schedule. In examination timetabling a teacher can supervise more than one examination at the same period and one room can host more than one examination at the same period, which is different from course timetabling problem.

5 . 1 . 1 , 5 . 1 . 2 ,

 511512 and 5.1.3. 1. Pasquale Avella and Andigor Vasil'ev model 2. Post enrollment based course timetabling 3. Curriculum based course timetabling problem 4. Original timetabling problem of Udine University There are some constraints in our generalized model which are the part of any other university problem different from previous scenarios. Their details could be found in Section 5.1.4. Some constraints which are the new addition in literature could be found in Section 5.1.5. Different instances which are the part of our generalized examination timetabling problem could be found in Section 5.2.1, 5.2.2, 5.2.3. Details of the used constraints different from previous instances and the list of newly added constraints in generalized model could be searched in Section 5.2.4, 5.2.5. The chapter is concluded in Section 5.3.

  of y can be 0 or 1. Intersection graph G (V, E) can be made by associating a node  to E iff columns i e and j e of A are not orthogonal. They also studied the polyhedral structures of the problem in according with set packing polytope, in this way two families of cutting planes clique and lifted odd hole inequalities were derived. Now we describe the constraints they used. They used the four hard constraints, these are the hard constraints which are used as hard almost in every institution. Numbering in bracket of the forth coming paragraph is representing the constraint number of our generalized formulation (Chapter 3) which shows that how the problem of Pasquale becomes sub problem of our generalized course timetabling problem of Chapter 3.

  Timetabling competition was sponsored by PATAT and WATT. This timetabling competition contained three tracks for competition. One track was about examination timetabling problem and other two were about course timetabling. From these two course timetabling, first was post enrolment based course timetabling and second was curriculum based course timetabling problem. Post enrolment based course timetabling means that firstly students are enrolled in courses and then all these courses are scheduled in such a way that all students can attend all their enrollments. But in curriculum based course timetabling scheduling is done on the basis of curricula published by university and not on the basis of enrolments of students. The third track was about examination timetabling. This Competition was organised and run by the Event Management and Planning Research Group (eventMAP) at Queen's University with partners from Cardiff University, Napier University, University of Nottingham and the University of Udine. Educational timetabling has become a part of competition and first timetabling competition (ITC-2002) was organized by International Metaheuristic Network, where 24 participants presented feasible solutions for presented datasets from all over the world. Information about definition, rules, datasets and solution evaluation are available on website: http://www.idsia.ch/Files/ttcomp2002/. A specific problem model was proposed for the competition and formulation of this model contained many characteristics found in certain Universities. Datasets to use for competition was generated artificially and now these datasets have become standard within the research area. Many researchers had used them in their scientific works [15, 16, 17, 18]. There is a positive effect of ITC-2002 for creating a ground for cross fertilization of ideas within researchers in the timetabling community. The Second International Timetabling Competition (ITC-2007) was started on 1st August 2007 and it was on the pattern of the first edition ITC-2002. It also added some more aspects and feature in it [42].

  of students enrolled in each event are as follows.

NextFigure 6 . 3 :Figure 6 . 4 :Figure 6 . 5 :

 636465 Figure 6.3: Population of timetables

Check

  If Num_ assigned > Numlects while (course_occurence = Numlects) do randomly remove an assignment endwhile Stage2 Repeat for every course Ci Check If Num_ assigned < Numlects while (course_occurence = Numlects) do Choose a room-time slot pair randomly Assigne this cours endwhile For every lesson assigned If (there is any room related hard constraint violation) Remove this assignment For all rooms If a room is available at period P Find a room for which (Size of class<= capacity of room) Assign the lesson to that room-period pair Endif End for



  Select the best-fit members for reproduction  Breed new members through crossover and mutation operations to give birth to children Evaluate the individual fitness of children  Replace least-fit members of population with children

Figure 6 . 6 : Procedure for crossover 6 . 3 . 2 . 3 Mutation

 666323 Figure 6.6: Procedure for crossover

Figure 6

 6 Figure 6.7.

Figure 6 . 7 :

 67 Figure 6.7: Procedure for random mutation

Figure 6 . 8 :

 68 Figure 6.8: Procedure for mutation by neighbourhood

Figure 6

 6 Figure 6.10.

Figure 6 . 10 :s selected from the population 2 : 3 :s

 61023 Figure 6.10: The pseudo code for Local Search

1 Where

 1 NS = total number of solutions in population i.e. population size, i f = fitness value of the ith solution. Next, we divide these drones into two categories: (1) Common drones and[START_REF] Burke | Decomposition, reformulation and diving in university course timetabling[END_REF]

Figure 6 . 12 :

 612 Figure 6.12: Pseudo Code for Honey Bee Mating Algorithm

6

 6

1 . 2 . 3 . 4 . 5 . 8 .

 123458 Number of examinations for large problem are 125. Number of classes for large problem is taken 70, these classes are generated randomly (each class has 2 to 5 examinations chosen randomly). Total number of rooms is 9. Number of days is 4. Number of periods is also 4. 6. Number of examination which should be the sole occupier of the room is 12 (randomly chosen). 7. We have selected randomly 70 pairs of examinations which have precedence relation to satisfy. We have chosen 35 pairs of examinations which have coincidence relation to satisfy. 9. 3 rooms are unavailable (chosen randomly).

For medium data 1 . 2 . 3 . 4 . 5 . 6 .

 123456 Number of examinations for medium problem are 70. Number of classes for medium problem is taken 40, these classes are generated randomly (each class has 2 to 5 examinations chosen randomly). Total number of rooms is 5. Number of days is 4. Number of periods is also 4. Number of examination which should be the sole occupier of the room is 7 (randomly chosen). 7. We have selected randomly 40 pairs of examinations which have precedence relation to satisfy.

Figure 7 . 1 :

 71 Figure 7.1: is showing the behaviour of the algorithms for medium sized dataset. These algorithms are run for 5000 iterations. X-axis represents number of iterations and Y-axis represents the cost at each iteration. The mutation rate is set to 7, kill colony 20 percent and population size 100.

In figure 7 . 2 ,Figure 7 . 3 :

 7273 Figure 7.3: Time and cost comparison of all algorithms

Table 7 .

 7 6: Showing additional constraints used for Problem.2 .............................................. 155

Table 7 .

 7 7: Numerical results for small datasets obtained by memetic algorithm .................. 159

Table 7 .

 7 8: Numerical results for medium datasets obtained by memetic algorithm .............. 160

Table 7 .

 7 9: Numerical results for large datasets obtained by memetic algorithm .................. 160

Table 7 .

 7 10: Numerical results for small datasets obtained by honey bee mating algorithm .. 161 xiv

Table 7 .

 7 11: Numerical results for medium datasets obtained by honey bee mating algorithm ................................................................................................................................................

Table 7 .

 7 12: Numerical results for large datasets obtained by honey bee mating algorithm ..

Table 7 .

 7 13: Numerical results for small datasets obtained by genetic algorithm...................

Table 7 .

 7 14: Numerical results for medium datasets obtained by genetic algorithm ..............

Table 7 .

 7 15: Numerical results for large datasets obtained by genetic algorithm ...................

Table 7 .

 7 [START_REF] Chiarandini | An effective hybrid approach for the university course timetabling problem[END_REF]: Numerical results for small datasets obtained by tabu search algorithm ............

Table 7 .

 7 17: Numerical results for medium datasets obtained by tabu search algorithm........

Table 7 .

 7 18: Numerical results for large datasets obtained by tabu search algorithm .............

Table 7 .

 7 [START_REF] Bonutti | Benchmarking curriculumbased course timetabling: formulations, data formats, instances, validation, visualization, and results[END_REF]: Minimum cost comparison of honey bee mating, memetic, genetic and tabu

Table 7 .

 7 28: Numerical results for large datasets obtained by memetic algorithm .................

Table 7 .

 7 29: Numerical results for large datasets obtained by honey bee mating algorithm ..

Table 7 .

 7 30: Constraints for examination timetabling problem...............................................

Table 7 .

 7 31: Minimum cost comparison of all algorithms for small datasets .........................

Table 7 .

 7 32: Minimum cost comparison of all algorithms for medium datasets .....................

Table 7 .

 7 33: Minimum cost comparison of all algorithms for large datasets ..........................

	xv

Table 7 .

 7 34: Maximum cost comparison of all algorithms for small datasets ........................

Table 7 .

 7 35: Maximum cost comparison of all algorithms for medium datasets ....................

Table 7 .

 7 36: Maximum cost comparison of all algorithms for large datasets .........................

Table 7 .

 7 37: Average cost comparison of all algorithms for small datasets ............................

Table 7 .

 7 38: Average cost comparison of all algorithms for medium datasets .......................

Table 7 .

 7 39: Average cost comparison of all algorithms for large datasets ............................

Table 7 .

 7 40: Standard deviation comparison of all algorithms for small datasets...................

Table 7 .

 7 41: Standard deviation comparison of all algorithms for medium datasets ..............

Table 7 .

 7 42: Standard deviation comparison of all algorithms for large datasets ...................

	xvi

Table 1 .

 1 leads the search process toward the searching space of good solutions. This algorithm has two phases of optimization. First phase use honey bees algorithm using neighborhood search and random search while second phase uses harmony search using memory consideration, random selection and pitch adjustment.Alzaqebah and Abdullah's algorithm[START_REF] Alzaqebah | The bees algorithm for examination timetabling problems[END_REF] starts with initial solution obtained from graph coloring heuristics and size of population is equal to the number of scout bees. Each scout bee evaluates the solution according to objective function. Highly ranked solutions are selected for local exploration by other bees (foragers) that are directed to the neighbourhood of the selected solutions by the scout bees. Then for each selected solution the number of foragers is allocated by this rule. If scout bee returns from one of the best solutions, performs the

	Nguyen et al. [46] presented a hybrid algorithm which combines honey bees algorithm and
	harmony search algorithm. The part of harmony search algorithm handles intensification and
	diversification. Diversification is handled by pitch adjustment and random selection which

While scout bees are those employed bees whose food source has been abandoned. Now these scout bees start to search a new food source randomly without any information. If they find new source of food where amount is more than the previous one in their memory they memorize the new source and forget the previous one. This algorithm employed local and global search methods simultaneously where local search method are used through employed bees and onlooker bees. While global search methods are carried out by onlooker bees and scout bees. The purpose of this combination is to have a balance between exploration and exploitation process. helps to retain good local search solutions. Random selection explores the search space more widely while pitch adjustment makes the new solution good enough to the existing good solutions. The intensification in Harmony search algorithm is controlled by memory consideration; this "waggle dance" this means that it recruits some specific amount of mates for local exploration. The scout bees that visit the elite solutions among the best sites recruit specific foragers for a neighbourhood search. The scout bees that visit the remaining solutions recruit a group of foragers for a neighbourhood search. Algorithm gives more tries for the elite solutions because elite solutions are the most promising solutions in the search space. 1: Lists papers related to course and examination timetabling problem

  to keep in mind that produced solution will be used ultimately by real people. So it is required by algorithm to be fast, reliable and can produce good solution according to the desires of the users.

Timetabling

problems related to educational institutions have discussed in detail with different types of constraints which make this type of problem really difficult. A lot of solution approaches used graph colouring heuristics to solve these problems, so we have discussed graph colouring problems in comparison with educational timetabling problems. Many metaheuristics have been used in literature to solve timetabling problems like local search based and population based metaheuristics. Our major focus is also metaheuristics because we have proposed metaheuristics to solve timetabling problems. Local search based metaheuristics need neighbourhood structures for its functioning so we have discussed these neighbourhood structures used in literature in detail.

A major part of this chapter covers different solution techniques used in literature. It is also worth mentioning that each technique has its own advantages and disadvantages, we can not decide that one technique is universally superior to any other one. Instead we can say that certain techniques are more appropriate to certain kind of problem-situations and certain types of user requirements. Thus it looks reasonable, when selecting a specific approach for one's own timetabling problem

  parameters and decision variables for model. Section 4.3 covers linear integer programming model of the generic model. Chapter is concluded in Section 4.4.

1, we have presented few mostly used constraints for examination timetabling problems. In Section 4.2 we have defined sets, sub sets,

Table 5 . 2

 52

	Dataset	1	2	3	4	5	6	Mean rank
	Solver 1	2	5	2	4.5	3	4	3.42
	Solver 2	7	7	4	6	6	6	6.00
	Solver 3	1	6	6	7	7	7	5.67
	Solver 4	3.5	4	5	4.5	5	5	4.50
	Solver 5	5	2.5	3	3	1	1.5	2.67
	Solver 6	6	1	1	1	3	3	2.50
	Solver 7	3.5	2.5	7	2	3	1.5	3.25

: Rank matrix and mean ranks

  It is done in two steps, in first step checking each lesson which appears more than once altered in such a way that it appears exactly once and in second step any lesson which did not appear is booked to spare spaces randomly. The benefit of this representation is that room must not be double booked and every lesson must be scheduled at once. In this chapter, we will explain in detail our algorithm for solving educational timetabling problem.

		Tues	Wed	Thu	Fri
	8:30	322 AQ 422 EN 513 MECH 228 PHY 0
	9:30 10:30 11:30 12:30 Figure 6.1: Example of a single room timetable 558 SO 515 HIS 259 FR … …. …. A university timetable stores information about what classes are booked in each room, at any 0 332 PR ….. …….. hour of the day, on any day of the week. Each of these bookings (or NULL bookings) is one gene. A timetable also has fields which describe (decode) some aspect of this genetic information. A timetable has a field which stores its cost. It also has fields which store the number of breaches of each type of hard constraint. A two stage verification strategy is used which ensures that each lesson of a course is scheduled exactly once. Figure 6.2: An entire university timetable

Table 6 .

 6 1: Differences and similarities between our HBM algorithm and previous population based algorithms. ''-'' means the method did not use the corresponding operator.

	Approa-	Application	Solution	Same		Initializati-	Initial	Crosso-	Mutation	Probl-	Exploitation
	ches		represent-	representati-	on method	solution	ver		ems	during
			ation	on	as						search
				HBMO	-
				ETP
	Our	improvement direct	no		heuristics	infeasible uniform	neighbourhood	exam	yes
	HBM								structures	and
	algorithm									course
	HBMO-	improvement direct	_		graph	feasible	haploid	shaking	exam	yes
	ETP [48]					colouring			procedure	and
										course
	GA [53]	constructive	direct	no		random	infeasible local	local search	exam	no
		+						search
		improvement
	ACO[54]	constructive	direct	no		graph	_	_	_	exam	no
						colouring
	GA [56]	improvement direct	no		graph	infeasible _	move operator	exam	no
						coloring
	GA [57]	improvement indirect	no		graph	feasible	one	_	exam	no
						colouring		point
	GA [52]	constructive	direct	no		GA	feasible	one	move operator	exam	no
		+						point
		improvement
	ACO[51]	constructive	direct	no		_	feasible	_	_	course	no
	GA [59]	improvement direct	no		random +	feasible	_	move operator	course	yes
						graph
						colouring
	GA [101]	improvement direct	yes		random	feasible	one	move operator	course	yes
								point
	GA+ GD	improvement direct	no		graph	feasible	_	Random swap	course	yes
	[58]					colouring
	EM+ GD	improvement direct	yes		graph	feasible	_	_	course	yes
	[60]					colouring

  32. If the fitness value of any of the brood created is f ( *

					S ) better than Queen's	f (Q)
					j
	33. Replace the queen with that brood
	34. Q=	* S and	f (Q) =	f ( * S )
		j			j
	35. Else add	* S to population
			j
	36. End For
	37. Mutate all broods by using random neighbourhood structures (N1 and N2)
	38. Kill the old drones and insert the new mutated broods into population
	39. End While
	40. Return the queen (Fittest solution found)

Table 6 .

 6 3: Parameter settings for our HBM algorithm's computational experiments Figure6.13 shows the block diagram for the proposed algorithm on university timetabling problems. It illustrates the process of our proposed algorithm. The algorithm starts by generating an initial solution via heuristics. Next, the improvement process (honey bee mating algorithm) is executed (as discussed earlier). Table6.3 represents the parameter settings for our HBM algorithm's computational experiments.

	Parameters

  These solutions can be seen from website [http://tabu.diegm.uniud.it/ctt/index.php]. Many ways were used to solve this curriculum based course timetabling problem including local search, tabu search, SAT based, Simulated annealing, mathematical programming, hybrid methods. If we look on the list of submitted results and proposed methods we will find only one author who used genetic algorithm to solve this problem[START_REF] Abdullah | An investigation of a genetic algorithm and sequential local search approach for curriculum-based course timetabling problems[END_REF]. Many authors constructed solutions for these datasets in last five years so some authors had good solutions on some

datasets and others had good solutions on any other datasets but in our point of view overall good results were produced by Andrea Schaerf [http://tabu.diegm.uniud.it/ctt/index.php, [

Table 7 .

 7 [START_REF] Zhou | Single-track train timetabling with guaranteed optimality: branch-and-bound algorithms with enhanced lower bounds[END_REF], if any constraint is used as a soft constraint then how much is the penalty value for its violation. We have solved this generalized timetabling problem to check the performance of our algorithms. Our generalized problem consists of two problems named Problem.1 and Problem.2.

	Problem.1 is the generalized problem used in Ahmad et al. [25]. Problem.1 has same
	constraints as used in previous mentioned article but has different data. Here we have
	generated new data to check the performance of our proposed algorithms which is more

difficult from previous data because of having more constraints and size of the problem datasets is also larger than previously mentioned data. Table

7

.5 is showing constraints for

Table 7

 7 .7, Table7.8, Table7.9) obtained by memetic algorithm. It is clear from results that small size problem is easy to solve in less amount of time than large problem. One can find near optimal solution with memetic algorithm in very short time.

	Problem	Minimum	Maximum	Average	S.D.	No.	of	%	of	%	of
	dataset	cost	cost	cost		events		used		used
								seats		slots
	1	0	0	0	0	68		66		68
	2	5	5	5	0	69		68		69
	3	5	7	6	0.81	79		70		79
	4	5	5	5	0	71		75		71
	5	5	5	5	0	67		74		67
	6	10	10	10	0	68		80		68
	7	0	0	0	0	65		84		65
	8	15	16	15.28	0.48	65		82		65
	9	10	10	10	0	63		87		63
	10	9	9	9	0	59		76		59

Table 7 .

 7 7: Numerical results for small datasets obtained by memetic algorithm

	Problem	Minimum	Maximum	Average	S.D.	No.	of	%	of	%	of
	dataset	cost	cost	cost		events		used		used
								seats		slots
	1	46	53	49	3.16	225		83
	2	26	35	31.75	4.27	254		81
	3	30	32	31.25	0.95	229		76
	4	45	53	48.75	3.30	243		83
	5	38	51	43.25	6.02	248		82
	6	38	46	41.75	3.30	243		75
	7	35	49	44.5	6.45	242		77
	8	47	53	50.25	3.20	231		72
	9	35	39	36.5	1.73	233		69
	10	56	62	59.5	2.51	250		81

Table 7 .

 7 8: Numerical results for medium datasets obtained by memetic algorithm

	Problem	Minimum	Maximum	Average	S.D.	No.	of	%	of	%	of
	dataset	cost	cost	cost		events		used		used
								seats		slots
	1	154	169	158.16	5.49	411		77
	2	144	162	153	6.85	426		78
	3	128	135	131.4	2.88	423		73
	4	121	126	123	2.16	421		78
	5	133	165	145.5	14.05	433		75
	6	145	164	154.5	9.39	412		76
	7	251	264	259.5	6.85	457		82
	8	169	183	178.25	6.39	463		75
	9	184	215	200	14.07	467		85
	10	130	163	144.25	13.72	409		80

Table 7 .

 7 9: Numerical results for large datasets obtained by memetic algorithm7.1.4.2 Honey bee mating algorithmIn this section, we have given results (Table7.10, Table7.11, Table7.12) obtained by honey bee mating algorithm. We take number of queens 1, number of drones 99, number of mating flights 4, Size of queen's spermatheca 5, number of elite drones 4, number of common drones 16, Ne-mat 1, Nc-mat 4. Honey bee mating algorithm is also taking more time to solve large size problem than small and medium size problems.

	Problem	Minimum	Maximum	Average	S.D.	No.	of	%	of	%	of
	dataset	cost	cost	cost		events		used		used
								seats		slots
	1	0	0	0	0	68		65
	2	5	5	5	0	69		67
	3	5	8	6.67	1.21	79		68
	4	5	5	5	0	71		76
	5	5	5	5	0	67		73
	6	10	10	10	0	68		77
	7	0	0	0	0	65		84
	8	15	15	15	0	65		83
	9	10	10	10	0	63		86
	10	9	9	9	0	59		77

Table 7 .

 7 10: Numerical results for small datasets obtained by honey bee mating algorithm

	Problem	Minimum	Maximum	Average	S.D.	No.	of	%	of	%	of
	dataset	cost	cost	cost		events		used		used
								seats		slots
	1	40	51	44.25	4.71	225		83
	2	29	35	32.25	3.20	254		81
	3	99	103	100.67	2.08	229		81
	4	46	49	47	1.73	243		83
	5	36	44	41	4.35	248		82
	6	36	40	38	2.0	243		76

Table 7 .

 7 11: Numerical results for medium datasets obtained by honey bee mating algorithm

	Problem	Minimum	Maximum	Average	S.D.	No.	of	%	of	%	of
	dataset	cost	cost	cost		events		used		used
								seats		slots
	1	150	158	153.25	3.94	411				82
	2	145	153	148.25	3.59	426				85

Table 7 .

 7 [START_REF] Pasquale | A computational study of a cutting plane algorithm for university course timetabling[END_REF]: Numerical results for small datasets obtained by genetic algorithm

	Problem	Minimum	Maximum	Average	S.D.	No.	of	%	of	%	of
	dataset	cost	cost	cost		events		used		used
								seats		slots
	1	427	460	440.25	14.08	225		70
	2	195	226	209.25	13.96	254		82
	3	110	116	113.75	2.63	229		82
	4	54	69	63.2	7.53	243		84
	5	43	66	52.4	8.96	248		82
	6	41	52	46.67	5.50	243		78
	7	47	50	48.25	1.50	242		80
	8	49	58	53.50	5.19	231		73
	9	35	46	39.5	4.79	233		73
	10	63	77	70.75	6.44	250		81

Table 7 .

 7 14: Numerical results for medium datasets obtained by genetic algorithm

	Problem	Minimum	Maximum	Average	S.D.	No.	of	%	of	%	of
	dataset	cost	cost	cost		events		used		used
								seats		slots
	1	1	1	1.0	0	68		67
	2	5	5	5.0	0	69		67
	3	11	14	13.0	1.73	79		67
	4	6	7	6.33	0.58	71		76
	5	6	6	6.0	0	67		73
	6	10	10	10.0	0	68		80
	7	0	0	0	0	65		85
	8	15	16	15.67	0.58	65		85
	9	10	10	10	0	63		87
	10	9	9	9	0	59		77

Table 7 .

 7 [START_REF] Chiarandini | An effective hybrid approach for the university course timetabling problem[END_REF]: Numerical results for small datasets obtained by tabu search algorithm

	Problem	Minimum	Maximum	Average	S.D.	No.	of	%	of	%	of
	dataset	cost	cost	cost		events		used		used
								seats		slots
	1	139	141	139.67	1.15	225		82
	2	295	355	314.5	27.63	254		79
	3	209	252	229.33	21.59	229		82
	4	149	220	181.33	35.92	243		82
	5	160	215	187.0	22.46	248		83
	6	119	157	138.25	18.13	243		76
	7	112	133	121.50	8.66	242		77
	8	80	83	81.67	1.50	231		73
	9	79	80	79.66	0.58	233		71
	10	310	358	335.33	24.11	250		81

Table 7 .

 7 17: Numerical results for medium datasets obtained by tabu search algorithm

	Problem	Minimum	Maximum	Average	S.D.	No.	of	%	of	%	of
	dataset	cost	cost	cost		events		used		used
								seats		slots
	1	437	493	475.50	25.92	411		77		82
	2	358	404	379.33	23.18	426		78		85
	3	239	266	249.67	14.36	423		73		84
	4	377	407	393.0	15.10	421		78		84
	5	328	393	364.33	33.17	433		74		86
	6	248	282	262.33	17.61	412		76		82
	7	946	1092	1002.0	67.97	457		80		91
	8	659	724	685.2	29.96	463		74		92
	9	957	1143	1036.75	88.92	467		83		93
	10	319	329	325.25	5.29	409		81		81

Table 7 .

 7 18: Numerical results for large datasets obtained by tabu search algorithm

Table 7 .

 7 [START_REF] Bonutti | Benchmarking curriculumbased course timetabling: formulations, data formats, instances, validation, visualization, and results[END_REF]: Minimum cost comparison of honey bee mating, memetic, genetic and tabu search algorithms for small datasets.

		1	2	3	4	5	6	7	8	9	10
	H.B.M.A 0	5	5	5	5	10	0	15	10	9
	M.A	0	5	5	5	5	10	0	15	10	9
	G.A	1	5	11	5	5	10	1	15	10	9
	T.S.A	1	5	11	6	6	10	0	15	10	9
	Datasets 1	2	3	4	5	6	7	8	9	10
	H.B.M.A 40	29	99	46	36	36	40	51	36	55
	M.A	46	26	30	45	38	38	35	47	35	36
	G.A	427	195	110	54	43	41	47	49	35	63
	T.S.A	139	295	209	149	160	119	112	80	79	310

Table 7 .

 7 20: Minimum cost comparison of honey bee mating, memetic, genetic and tabu search algorithms for medium datasets.

	Datasets 1	2	3	4	5	6	7	8	9	10
	H.B.M.A 150	145	123	112	129	134	205	167	174	120
	M.A	154	144	128	121	133	145	251	169	184	130
	G.A	288	235	180	252	185	188	437	317	369	226
	T.S.A	437	358	239	377	328	248	946	659	957	319

Table 7 .

 7 [START_REF] Burke | Applications to timetabling[END_REF]: Minimum cost comparison of honey bee mating, memetic, genetic and tabu search algorithms for large datasets.

	7.1.4.

6 Maximum cost Comparison of all algorithms

  In this section, we have given comparison of maximum cost results obtained by all algorithms (Table7.22, Table7.23, Table7.24). For small datasets, results of honey bee mating and memtic algorithms are same. Genetic algorithm has given more maximum cost values than tabu search algorithm. For medium datasets, honey bee mating and memtic algorithms results are almost same. Tabu search algorithm is giving more maximum cost values than genetic algorithm. This is opposite to small size instances where genetic algorithm costs are more.In our opinion, for complex, large size problem and over big span of time genetic algorithm's operators and its nature inspired behaviour giving it edge on local search based algorithm. For large datasets honey bee mating algorithm maximum cost is less than memetic algorithm for 9 datasets. Thus honey bee has produced better results than memetic algorithm for large instances in terms of both maxim and minimum cost comparison.

	Datasets 1	2	3	4	5	6	7	8	9	10
	H.B.M.A 0	5	8	5	5	10	0	15	10	9
	M.A	0	5	7	5	5	10	0	16	10	9
	G.A	4	7	13	7	8	13	4	16	10	9
	T.S.A	1	5	14	7	6	10	0	16	10	9

Table 7 .

 7 [START_REF] Brucker | Resource-constrained project scheduling: Notation, classification, models, and methods[END_REF]: Maximum cost comparison of honey bee mating, memetic, genetic and tabu search algorithms for small datasets.

	Datasets 1	2	3	4	5	6	7	8	9	10
	H.B.M.A 51	35	103	49	44	40	48	54	40	57
	M.A	53	35	32	53	51	46	49	53	39	62
	G.A	460	226	116	69	66	52	50	58	46	77
	T.S.A	141	355	252	220	215	157	133	83	80	358

Table 7 .

 7 [START_REF] Fleszar | Solving the resource-constrained project scheduling problem by a variable neighbourhood search[END_REF]: Maximum cost comparison of honey bee mating, memetic, genetic and tabu search algorithms for medium datasets.

	Datasets 1	2	3	4	5	6	7	8	9	10
	H.B.M.A 158	153	125	123	142	146	232	188	197	138
	M.A	169	162	135	126	165	164	264	183	215	163
	G.A	322	268	205	274	207	205	461	326	377	242
	T.S.A	493	404	266	407	393	282	1092 724	1143 329

Table 7 .

 7 24: Maximum cost comparison of honey bee mating, memetic, genetic and tabu search algorithms for large datasets.

Table 7 .

 7 25: Average cost comparison results of honey bee mating, memetic, genetic and tabu search algorithms for small datasets.

		1	2	3	4	5	6	7	8	9	10
	H.B.M.A 0	5	6.6	5	5	10	0	15	10	9
	M.A	0	5	6	5	5	10	0	15.2	10	9
	G.A	1.7	5.5	11.8	6.5	6	10.7	1.5	15.2	10	9
	T.S.A	1	5	13	6.3	6	10	0	15.6	10	9

We have also solved our datasets with tabu search algorithm, we may think to incorporate tabu search algorithm with memtic algorithm. Performance of algorithm may be improved by using sets of neighbourhood structures in form of a sequence during the searching process.

The tabu list can be used to control the selection of neighbourhood structures, for example if any neighbourhood structure is not improving the result after some specific attempts then algorithm would try next neighbourhood structure in sequence list.

A part of our thesis consists of linear integer programming. We may solve these problems by using lexicographical optimization with sub problems. Preference criterion of cost functions of these sub problems can give edge to prioritize the constraint satisfaction according to the requirements while having broader search space for more preferred objectives.

We have given a transformation of course timetabling to resource constrained project scheduling problem (RCPSP). The use of our memetic and honey bee mating algorithms could be adopted to solve these problems as well. We hope, solution representation of our timetabling algorithms can be converted for RCPSP by concentrating on the given transformation.

procedure. One can see rules to obey for competition on webpage: http://www.cs.qub.ac.uk/itc2007/.

Evaluation procedure for solutions

Now we shall describe how the solutions are evaluated. Let m be the total number of early and late datasets and k be the number of participants who are going to submit their solutions for all m datasets. Let ij X be the result of the participant i for dataset j. Each result ij X is given in form of pair (d, s) where d is the distance to feasibility and s is the score of the objective function. Firstly results were compared on the basis of the value of d but when competitors have same d value then results were compared on the basis of the objective function value.

Each participant results were transformed by using transformation matrix for each value of ij X . Then for dataset j supplied values will be kj j j X X X ... , 2 1 . All these values were compared with each other and rank 1 was given to the smallest observed value, rank 2 was given to second smallest observed value and so on up to the rank k. They used average ranks in case of ties.

Consider the following example where there are k = 7 participants and m = 6 datasets. Let X be the matrix of Table 5.1, the computed rank matrix R is reported in Table 5.2. By using these values, mean values of all participants was calculated and on the basis of mean value 5 finalists were selected with the lowest mean ranks. If there is a tie on last position then all the last participants of equal mean value were selected. In this case finalists can be more than five. In this example mean ranks can be seen in last column of the rank Table 5 Constraint [START_REF] Chiarandini | An effective hybrid approach for the university course timetabling problem[END_REF] expresses that class should not have more than two consecutive courses on each day; it means that two consecutive courses are allowed but constraint [START_REF] Kostuch | The university course timetabling problem with a three-phase approach[END_REF] explains that two courses of a class could not be scheduled together. These two constraint contradict each other so could not be taken in same timetabling problem.

Timetable should be compact for each class; empty periods between any two courses are not allowed. [START_REF] Fleszar | Solving the resource-constrained project scheduling problem by a variable neighbourhood search[END_REF] If one uses curriculum compactness [START_REF] Fleszar | Solving the resource-constrained project scheduling problem by a variable neighbourhood search[END_REF] then the constraints [START_REF] Ahmad | Generic model for university course timetabling problem solved by genetic algorithm[END_REF], [START_REF] Kostuch | The university course timetabling problem with a three-phase approach[END_REF], [START_REF] Chiarandini | An effective hybrid approach for the university course timetabling problem[END_REF] could not be used simultaneously, as these are against each other.

Some courses are taking place in one department and some others are taking place in any other department and distance between the buildings is long, so students or teachers could not reach on time after attending a course in one building to other building. So such type of courses should not be scheduled in consecutive periods.

Constraint [START_REF] Jacques | Exchanges procedures for timetabling problems[END_REF] will disturb curriculum compactness so when one is using curriculum compactness and there are also some long distance buildings, then compactness constraint could be dealt by any other way.

Course compactness [START_REF] Boland | New integer linear programming approaches for course timetabling[END_REF] can be used with curriculum compactness because each course is a part of any curriculum.

In [START_REF] Batenburg | A new exam timetabling algorithm[END_REF], [START_REF] Thompson | A robust simulated annealing based examination timetabling system[END_REF] some timetables rooms, periods, teachers are always available and some environments these are unavailable on some occasions but unavailability on some occasions is more general case.

Course will not be scheduled in period p at room r, if room r is not available. [START_REF] Burke | On a clique-based integer programming formulation of vertex colouring with applications in course timetabling[END_REF] Course will not be scheduled in period p, if teacher t is not available. [START_REF] Ross | Advances in Evolutionary Computing: Theory and Applications, topic: Genetic algorithms and timetabling[END_REF] Course will not be scheduled on its forbidden period. [START_REF] Geiger | An application of the threshold accepting metaheuristic for curriculum based course timetabling, Practice and Theory of Automated Timetabling[END_REF] generalized problem and how one can modify this problem to use our generalized mathematical model. We have also discussed different constraints of university timetabling problems which are contradicting with each other and hence can not be the part of a same problem instance. During our discussion we have highlighted the real world problem of Udine University from which curriculum based course timetabling problem was made. We have written the mathematical model of this problem from our generalized model as well. We have also discussed many constraints which are added by us in model. It means that we could not found them in literature.

We have also discussed different examination instances used in literature, which are part of our generalized examination timetabling problem in detail at the end of this chapter. We have shown that how mathematical models of these instances can be deduced from our generalized model. At the end we have presented some constraints which are added by us in this newly proposed generalized examination timetabling problem.

Conflicts Matrix

This matrix is very similar to adjacency matrix used for representing graphs. For our problem it indicates which pair of events have conflicts (so can not be scheduled in the same period).

For example if any two events ) in the matrix marks as true otherwise marks as false.

By using this encoding counting of violations is easy and inexpensive. To check violations are easy now, for example if one wants to check that each class should have at most one lesson in any period, it can be evaluated by checking each column whether this column is true more than one entry or not (rows of the matrix are classes). If one wants to check that proper room type r has been assigned to an event e in timetable, simply it can be verified by checking entry (e,r) is true in event-room matrix.

We have suggested some more matrices for our problem after following the suggestions of Carter [START_REF] Carter | A survey of practical applications of examination timetabling Algorithms[END_REF] (Chapter 1, Section 1.7).

Room-Period Matrix

This matrix indicates that room r is available at period p or not. If room r is available at period p then element (p,r)marks as true otherwise it marks as false because in our problem rooms are not always available.

Course-Period Matrix

This matrix shows the relationship between period and events because some events can not be scheduled in some periods. If event e can be scheduled in period p then element (e, p) will be marked true otherwise it will be marked false.

Class-Period Matrix

comprehensive meanings. Then each set of rooms (according to its type) is ordered by its capacity. This capacity ordering would be used in a heuristic in later stages. Each room has the following information: name, capacity and type. Where name indicates the name of room; capacity means the number of seats in the room and type means the kind of room, i.e.; lecture room, laboratory etc.

These three types of procedures have been used to construct initial solutions for initial population of our algorithms.

1.

Random initialization

2.

Repair strategies

Set forming heuristics

We describe these methods one by one in detail.

Random initialization

Individual solutions can be generated randomly to form an initial population. The size of population depends on the problem. It can contain several hundreds or thousands of possible solutions depending upon the problem nature. For our problem it varies from 50 to 100 because our preliminary experiments have found this range good results producing. The benefit of this strategy is that there would be a large diversity in solutions of search space.

Repair strategies

After getting the initial solution repairing is mainly done on violation of hard constraints. First of all know about the location of the offending slots and replace them iteratively with valid slots.

In our algorithm we have used room repair strategy and two step verification strategy which are given in Figure 6.4 and Figure 6.5.

In room repair strategy, we choose an assigned course which causes hard constraint violation of rooms. We delete this assignment and reassign it to another slot in a way that no violation of room related constraint occurs. The procedure for this strategy is explained in Fig. 6. 4. Figure 6.9: Infection

Replacement

After creating new children by using crossover and mutation operators a successor generation is made. As parents chromosomes are selected according to their fitness value, so it is hoped that the children go towards the good fitness value after each generation. This is the replacement procedure which decides about child survival or extinction.

The following replacement methods have been used in the literature: random replacement, replacement with elitism, replacement with worse population and steady-state replacement.

In random replacement, some specific percentage of members is randomly chosen in the The strength of this algorithm is to explore simultaneously and exploit problem search space. This is achieved by the queen's transition in the search space and employing a local search at each iteration. The queen (current fittest solution) is the best individual, so it is hoped that it will evolve superior solutions. This dominated solution stores different drone's genotypes in her mating pool. Some parts of these genotypes are used to make new broods by combining some parts of the drone's genotype with parts of the queen genotypes. These features of honey bee algorithms make it different from other population based algorithms those have been used for educational timetabling problems.

Proposed honey bee mating algorithm

We have proposed a honey bee mating optimization algorithm for educational timetabling problem. According to our knowledge, there are few articles on educational timetabling problems which use honey bee mating algorithm (Chapter 1, Section 1.8).

The honey-bee mating algorithm was used first time to solve educational timetabling problem by Sabar et al. [START_REF] Sabar | A honey-bee mating optimization algorithm for educational timetabling problems[END_REF]. They referred it as HBMO-ETP algorithm. In this work, we propose a variation of HBMO-ETP, which we call as HBM algorithm. The pseudo-code for our proposed HBM algorithm is shown in Figure 6.12. Now we describe our algorithm in detail.

Firstly, we select a number of honey-bees to create the population of the initial hive. In many cases, random generation methods may not necessarily guarantee a good quality solution.

Therefore, in this work, we employ heuristics which are described earlier in this chapter to make an initial population of drones.

At this stage, the solutions generated may or may not be feasible. For the moment we do not impose the feasibility condition in order to maintain the diversity. We choose the fittest solution in this population and make it queen. The other solutions of this initialization phase become the drones. Creation of new children by using crossover and mutation operators succeed towards a new generation. Thus it is important to select some population members, which will be replaced with new children. We have mentioned our replacement procedure. We have explained the procedure of our local search, its neighbourhood structures and the procedure of our proposed memetic algorithm which uses this local search for the improvement of the solution quality.

We have also proposed honey bee mating algorithm. This describes the natural mating behavior of the queen bee when she goes for the search of drones with her spermatheca which has a fixed capacity and when this fills up queen comes back in hive to start mating process.

Mating process produces broods fed by worker and finally if new fittest brood is better than queen, it replaces her. Initial population of hive is created by our heuristics. We have used probability function to rank population and to choose queen for hive. We have divided these drones into two categories common drones and elite drones on the basis of their probability values. We have described differences and similarities between our HBM algorithm and previous population based algorithms in detail.

Chapter 7

EXPIREMENTS AND RESULTS

In this chapter we have analysed results obtained by our proposed algorithms. We have discussed in detail reasons of obtaining good results and also shortcomings of the algorithms.

We have applied our algorithms on one benchmark timetabling problem, generelized educational timetabling problem and generalized examination timetabling problem. First of all we have applied our memetic algorithm on benchmark timetabling problem (Curriculum based course timetabling problem). This problem is a part of international timetabling competition problem 2007. This problem is discussed in detail in (Chapter 5, Section 5.1.2).

We have compared our results on benchmark instance with other algorithms used in literature.

Then we have generated data for both generalized course and examination timetabling problems and have solved these datasets with our algorithms. We have also solved these datasets with genetic and tabu search algorithms and compared results of these four algorithms while using same termination criteria.

Rest of the chapter is organised in this way. We have presented experimental work on course timetabling problem in Section 7.1. In this section, first we have compared our memtic algorithm performance with other timetabling approaches on benchmark problem. In this section we have generated datasets for our generalized problem and have solved them with our proposed algorithms. These datasets are also solved with genetic and tabu search algorithms. We give detail comparison of the performance of these four algorithms. In Section 7.2, we have discussed examination timetabling problem and have compared results obtained by algorithms. In Section 7.3, we have conducted an analysis of the obtained results.

Course timetabling problem

In this section, we have talked about course timetabling problem. We have discussed a benchmark and have compared results of our memetic algorithm with other algorithms on this particular benchmark.

We have also generated datasets for generalized university course timetabling problems. We have solved these problems with our memetic and honey bee algorithms. We have also solved the same datasets with genetic and tabu search algorithms and finally have given a comparison of all these four algorithms with respect to each other. Table 7.1: Showing dataset number, dataset name, total number of rooms, total number of periods, total number of courses, the sum of their events in a week and the number of curricula.

Benchmark solved by proposed memetic algorithm

Some more characteristics about datasets are given in Table 7.2. They are as follows:

frequency or the portion of period-room slots in use, utilisation in terms of used seats in percentage [START_REF] Beyrouthy | Towards improving the utilisation of university teaching space[END_REF], numbers of edges in conflict graphs (CG), density in conflict graphs (CG) with vertices representing courses rather than events [START_REF] Burke | On a clique-based integer programming formulation of vertex colouring with applications in course timetabling[END_REF] We have compared the performance our algorithm with respect to other seven reference algorithms. These seven algorithms include ITC 2007 organizer's algorithm which is developed by de Cesco et al. [START_REF] Bonutti | Benchmarking curriculumbased course timetabling: formulations, data formats, instances, validation, visualization, and results[END_REF], the algorithm of the winner of the competition Tomas Müller [START_REF] Müller | ITC2007 solver description: A hybrid approach[END_REF], the algorithm of Second position holder Zhipeng Lu and Jin-Kao Hao, the algorithm of third winner Mitsunori Atsuta et al. [START_REF] Zhipeng | Neighborhood analysis: A case study on curriculum based course timetabling[END_REF]42], the 4th place algorithm by Martin

Josef Geiger [START_REF] Geiger | An application of the threshold accepting metaheuristic for curriculum based course timetabling, Practice and Theory of Automated Timetabling[END_REF], the 5th place algorithm of Michael Clark et al. [START_REF] Clark | A repair-based timetable solver[END_REF] and the algorithm proposed by Abdullah and Turabieh [START_REF] Abdullah | An investigation of a genetic algorithm and sequential local search approach for curriculum-based course timetabling problems[END_REF].

Tomáš Müller used a Local search based algorithm using routines taken from the constraint solver library. He also used various neighborhood search algorithms to eliminate violations of hard and soft constraints. The important thing to note about Abdullah and Turabieh algorithm is that this is the only algorithm among many others which used evolutionary algorithm to solve this competition problem. So this is our motivation to use evolutionary algorithm to solve these datasets. Thus we have constructed an evolutionary algorithm for our generalized model.

All the algorithms used the same stopping criteria (timeout condition 600 seconds), which was required by ITC-2007 competition [START_REF] Gaspero | The second international timetabling competition (ITC-2007): curriculum-based course timetabling (Track 3)[END_REF][START_REF] Mccollum | A new model for automated examination timetabling[END_REF]. Table 12 shows our Memetic algorithm's results in comparison with some other used techniques.

We have solved these competition datasets with memetic algorithm which uses genetic algorithm with local search. This algorithm is given in detail in the previous chapter. Our results are good when we compare it with contestant of the competition results. We also solved these datasets with genetic algorithm but results were not as good as these are with memetic algorithm. Maximum allowed time to solve these datasets was ten minutes. Some of the datasets are solved within this time limit but for some datasets it takes more time. We have fixed number of iterations to solve these datasets which are fifteen thousand for each dataset. In our proposed algorithm, we have used population size 100, mutation rate 7 while using 20 % killing with a local search which makes it slow but if we use steady state memetic algorithm (in which one offspring is generated in each generation), algorithm works quickly but this decrease the performance of the algorithm. This means that in less time more iterations can be run but net objective function value would not be so good as with memetic algorithm. Our algorithm solves these datasets and produces good results but it takes more time to produce these results.

Dataset

Our MA Müller [START_REF] Müller | ITC2007 solver description: A hybrid approach[END_REF] Lü &Hao [START_REF] Zhipeng | Neighborhood analysis: A case study on curriculum based course timetabling[END_REF] Atsuta

Data generation for course timetabling problem

We have modelled a generalized educational timetabling problem. In this section we have generated data to check the performance of proposed methods for solution. For this purpose we have generated data where some sets and sub sets have fixed values and others have been chosen randomly. The purpose of this work is to make some datasets which have all these constraints and to solve them with proposed methods. Our proposed methods are two phase methods, so in first phase hard constraints are satisfied and these methods get feasible solution in first phase.

22. Five percent lessons are grouped into two or three lessons subsets randomly which should be scheduled together in same day. Each lesson can be part of at most one sub set.

23. Three percent lessons are selected randomly, grouped into two or three lessons subsets randomly which should not be scheduled together in same day. Each lesson can be part of at most one sub set.

Different constraints used in generalized problems are given in Tables 7.5 and 7.6. These tables provide details about constraint whether it is used as hard or soft. If it is used as a soft constrain then they also tell about the amount of penalty used in case of violation.

For these datasets, we have taken mutation rate 7, kill colony 20 percent, population size 100 because our preliminary experiments suggest that good results can be produced with these parameters. We allow 600 seconds for large problem datasets, 400 seconds for medium problem datasets and 100 seconds for small problem datasets.

We have generated certain data in terms of percentage. To obtain an integer value from its percentage, we use least integer function. For example if 5% of total lessons gives 6.4 lessons, so least integer function value of 6.4 be 7. The reason to do so is that in our problem values are in integers not in form of any real number. 6.4 lessons are unavailable for a period does not make any sense or teacher is unavailable for 5.2 periods. According to our data generation 5.2 unavailable periods mean 6 periods unavailability.

To check the performance and efficiency of the algorithms, we have firstly applied the algorithms on randomly generated datasets of Problem.1. We have generated 10 small, 10 medium and 10 large size problem datasets for this purpose. The program is coded in C and run on an Intel computer with 2.5 Ghz processor, 4GB RAM under windows operating system. We have run algorithm 5 times for each problem dataset to see its performance in detail.

Results of course timetabling Problem.1 datasets

These tables are showing results for small size, medium size and large size problem datasets.

In each

Results of course timetabling Problem.2 datasets

In this section, we have given results obtained by honey bee mating and memetic algorithms (Table 7.28, Table 7.29) across 5 runs on each of the 10 large size datasets of Problem.2. We have taken mutation rate 7, kill colony 20 percent, population size 100 and time limit for large datasets is fixed 600 seconds.

We have taken number of queens 1, number of drones 99, number of mating flights 4, Size of queen's spermatheca 5, number of elite drones 4, number of common drones 16, Ne-mat 1, Nc-mat 4 for honey bee mating algorithm. These all parameters and their values are same as are taken in Problem.1 in previous section. Datasets are also same but we have added some more constraints in these datasets.

We have not generated small and medium size instances for this problem because we want to see a glimpse of results for only large datasets as all size datasets have been discussed

thoroughly in previous section results. Our purpose for these results is that to see the behavior of our proposed algorithms for more generalized complex problem that is why, we have solved Problem.2 only with our memetic algorithm and honey bee algorithms for large datasets only.

Memetic algorithm

We were expecting that increase in constraints in problem will increase the value of objective Table 7.28: Numerical results for large datasets obtained by memetic algorithm

Honey bee mating algorithm

When one increases number of constraints in a dataset its difficulty level increases. These large size datasets are really good to analyze the performance of algorithms. In Problem.1, honey bee mating algorithm performance was better for 9 datasets but by adding more constraints in problem, now honey bee algorithm has produced better results for four datasets.

Similarly, there is a change in results for maximum cost of algorithms. Honey bee mating algorithm was better for 9 datasets in Problem.1 but now memetic algorithm has constructed better solutions for 9 datasets. However, performance of both algorithms is good.

Examination timetabling problem

We have also solved examination timetabling problem with our proposed algorithms. In this section, we have discussed our experimental work on this problem.

Data generation for Examination timetabling problem

In this section we have generated data for examination timetabling and have checked performance of proposed methods. For this purpose we have generated data where some sets and sub sets have fixed values and others have been chosen randomly. Examination timetabling problem is different from course timetabling so some sets and data pattern will be different from course timetabling problem.

In our mathematical model we have added invigilator and have added the constraints related to invigilator but in our experimental work we do not use them. One can add them to in the implementation phase on the same lines as we have added them for course timetabling problem but we have left them at the moment. The other reason is that in literature normally examination problem was dealt without invigilator inclusion. Similarly in this experimental 11. We do not put limit of maximum examinations of a class per day limit for small problem datasets because maximum available rooms for these problems are 2.

12. Maximum examinations per room limit is set 2.

13. Allowed time for small problem is 100 seconds. Many other constraints like pre assigned periods to examinations, examination on the same day, examination on the different days, specify any room for any examination, specified spread of examination, room types etc. can be added and solved easily in a similar way as these are dealt in course timetabling problem.

Results of examination timetabling problem datasets

In this section we have presented the results obtained from our algorithms by using above mentioned generated data. For large examination timetabling datasets, number of generated examinations is 125 and total number of used slots for this data is 86%, for medium date number of examinations is 70 and 87% slots are used and for small datasets number of examinations are 20 and percentage of used slots for these problems is 62%. The remaining parameters are the same as used for course timetabling problem.

Minimum cost comparison of all algorithms

Minimum cost results for small datasets have shown almost same performance for all algorithms. For medium datasets, honey bee mating algorithm has shown good performance than memetic algorithm for 3 datasets and memetic algorithm's performance is better for one dataset than honey bee mating algorithm but on remaining datasets their performance is same.

For large datasets, honey bee algorithm performance is better for 5 datasets than memetic algorithm while memtic algorithm is showing better performance on 4 datasets than honey bee mating algorithm. Genetic algorithm performance is lower than honey bee mating and memetic algorithms.

Standard deviation comparison of all algorithms

For small datasets, standard deviation is 0 for all algorithms. For medium datasets, honey bee mating algorithm is showing better results for 7 datasets while memetic algorithm is better on 3 datasets. Honey bee mating standard deviation is less for 5 datasets and on remaining 5 datasets memetic algorithm is showing less deviation value.

Discussion on Results and conclusion

We have used certain time limits on our algorithms during testing of our datasets and we consider this is fair for these sizes of problems. These are 100, 400 and 600 seconds of CPU time for the small, medium and large datasets respectively. We have used hardware Pentium Cost on y-axis and number of iterations on x-axis The figure (Figure 7.1) shows that memetic algorithm and honey bee mating algorithms are performing well. But Honey bee mating algorithm performance is better towards the end of iterations. We think that it is due to fixing one solution as queen for mating in the whole generation. This can reduce the diversity of solutions as compared to the memetic algorithm where we choose two different parents for each generation. We have run these algorithms once on one medium sized dataset. As in literature, normally ten to twenty runs are performed on one dataset. Then they get results for average cost of all the runs. But we have run these algorithms in our preliminary experiments during their construction and also for our small, medium and large datasets. Detail performance of these algorithms can be found from the results. We have drawn a graph of a medium sized dataset to show the general behaviour of these algorithms. We have analyzed results obtained by our proposed algorithms in Chapter 7. We have applied our memetic algorithm on one benchmark timetabling problem and have compared our results on benchmark instance with other algorithms used in literature. We have also tested our algorithms on generalized educational and examination timetabling problems. We have generated data for both generalized course and examination timetabling problems. We have also solved these datasets with genetic and tabu search algorithms alongside our algorithms and have compared results of these four algorithms while using same termination criteria.

Perspectives

Now, we round off this thesis with some general comments about this work and also give some suggestions for further research work.

We have proposed generic models for timetabling problem which contain many problems as its sub part. These are the problems coming from different departments and we have accumulated them in a single model. When we apply our proposed algorithms on these big size problems, scaling up issues give us clue for future research work. In real world timetabling sometimes, one department courses forms a distinct clump than the courses of other departments. This department may have only few or no common students, may use different campus and may have different set of rooms, with other departments. Thus we think that scheduling of this type of department has little bearing on other departments. So this kind of departments can be scheduled independently by using any relaxation technique while objective is to construct a timetable for whole university. In our opinion, by using this strategy search space can be relaxed and performance of algorithms can be enhanced.

Performance of algorithms may be improved by using any other solution construction processes. Behavior of the crossover operator may be changed by implying some sort of condition on it. For example, we may put restriction on our uniform crossover that it would change a gene only when by changing it timetable remains feasible. Our local search plays a vital role in algorithm and we may use some more grained neighbourhood structures to enhance the performance of algorithm. We have solved course and examination timetabling problems with honey bee mating algorithm. We think, by setting parameters such as population size, number of drones, number of mating flights, size of queen's spermatheca etc.

and by using some more sophisticated heuristics to make initial solution can improve performance of the algorithm.