The literature review will focus on the introduction of the exam timetabling system that has been used in universities and timetabling that use in other field and their problem. Educational timetabling optimization is a major administrative activity for a wide variety of institutions. A timetabling optimization problem can be defined as assigning a number of events into a limited number of time periods to optimize the result in the timetable to save cost, time, space or other thing that can be save.
This report also reviews the technique that can be used in optimizing the unused class in exam timetabling.
2.1 PROBLEM DOMAIN
"A.Wren(1996) defines 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 (Burke & Petrovic,2002).
Many researchers has contribution in timetabling problems in several years later due to the fact that timetabling problems are often over-constrained, dynamic, and optimization criteria are hard to define. Some of the contributions from those researchers are including graph coloring, integer programming from Operations Research, simulated annealing, tabu search, genetic algorithms, and constraint logic programming from Artificial Intelligence (Alashwal & Deris, 2007).
Timetabling is produced by the scheduling problem and it can be shown in many different forms. Timetabling is very important to Business Company, organization, or even to individual. With timetable the work will become more systematic and efficient. Timetabling is ongoing and continuous process. A process of updating timetables is required consideration of a significant number of objects and constraints. As increasing a number of students, an updated to the current traditional timetabling system should be done from time to time to make the feasible scheduling to students. Therefore, it takes a lot of time such as several days or even weeks to complete scheduling timetables manually by human.
A timetabling problem is about an assigning of a set of activities, actions or events at specific time slot for example: work shifts, duties, classes to a set of resources. Timetabling problems is related to problems on allocation resources to specific timeliness which there are specific constraints must be considered. The resources such as groups and subjects are allocated to a time slot of classrooms as long as it was satisfying their constraints (Norberciak, 2006).
This project main goal is to produce a best result of assigning student to a class that will optimize the used classes. The difficulty is due to the great complexity of the construction of timetables for exams, due the scheduling size of the examinations and the high number of constraints and criteria of allocation, usually circumvented with the use of little strict heuristics, based on solutions from previous years. The objective of this work is the examination schedules. The main purpose is to allocate each final exam paper to the best class based on the number of student taking the paper, automatically by using computers.
The people facing these difficulties is the people who in charge of assigning these exam manually. The variable is the date of the exam, time of the exam, subjects, exam papers, number of student taking the exam paper and the available class. They need to group this exam in exam date and time of the exam which is in morning or evening. After that they will assign each exam paper to an available class that fitted to the number of student taking the exam. These steps will continue until all the exam papers have their classes.
2.2 TECHNIQUE THAT CAN BE USED IN THE PROJECT
There are many intelligent techniques or method of optimization that has been tried throughout the decades since the first attempts of automating the examination timetabling process such as Particle Swarm Optimization (PSO), Artificial Immune Algorithm, Graph Coloring Method and Genetic Algorithm.
2.2.1 PARTICLE SWARM OPTIMIZATION (PSO)
Goldberg, Davis and Cheng says that PSO is different from other methodologies that use natural evolution as the architecture while PSO is based on social behavior of evolution (S.C.Chu,Y.T.Chen&J.H.Ho, 2006). PSO use self-organization and division of labor for distributed problem solving similar to the collective behavior of insect colonies, bird flocks and other animal societies (D.R.Fealco, 2005).
According to Kennedy and Eberhart (2001), PSO relatively new stochastic GO which is known as Global Optimization member if the Broader Swarm intelligence field for solving optimization problem (D.R.Fealco, 2005).
PSO using population of particle process to search the system then each particle is updated by following two best values in every iteration (S.C.Chu,Y.T.Chen&J.H.Ho, 2006). Optimization problem in PSO is done by assigning direction vectors and velocities to each point in a multi-dimensional search space and Each point then 'moves' or 'flies' through the search space following its velocity vector, which is influenced by the directions and velocities of other points in its neighborhood to localized iterations of potential solution (C.Jacob&N.Khemka,2004).
The PSO algorithm works simultaneously maintaining several candidate solution in the search space. PSO algorithm consist of seven step (C.Jacob&N.Khemka,2004). Which is
Initialize the population - locations and velocities.
Evaluate the fitness of the individual particle (pBest).
Keep track of the individuals highest fitness (gBest).
Modify velocities based on pBest and gBest position.
Update the particles position.
Terminate if the condition is meet.
Go to Step 2.
The detail of the PSO algorithm is shown in Figure 2.1.
Figure 2.1: The process of PSO
2.2.2 ARTIFICIAL IMMUNE ALGORITHM
Artificial Immune Algorithm also known as AIS are stimulated from nature of human immune system. Dasgupta, Ji and Gonzalez mention that feature extraction, pattern recognition, memory and its distributive nature provide rich metaphor for its artificial counterpart are the powerful capabilities of the immune system (H.Yulan,C.H Siu&M.K Lai). Timmis & Jonathan (2000) describe the AIS used natural immune system as the metaphor as the approach for solving computational problem (M.R.Malim,A.T.Khadir&A.Mustafa). Anomaly detection, pattern recognition, computer security, fault tolerance, dynamic environments, robotic, data mining optimization and scheduling are the main domain application of AIS (M.R.Malim, A.T.Khadir & A.Mustafa).
Some preliminary biological terms in order to understand the AIS are immune cells B-cells and T-cells are two major group of immune cell and it help in recognizing an almost limitless range of anti genes pattern and antigens (AG) is the disease-causing element, it has two type s of antigens which is self and non-self where non-self antigens are disease-causing elements and self anti-genes are harmless to the body (R.Agarwal, M.K.Tiwari, S.K.Mukherjee, 2006).
There are two main application domain in AIS which is antigen and antibody. Antigen is the target or the solution for the problem, while the antibody is the reminder of the data. Occasionally, there are more than one antigen at a certain time and there are frequently large number of antibodies present at once. Generic steps of artificial immune system (AIS) :
Step 1: Define problem specific objective function and set the algorithm
parameter. Set iter=0; counter for number of iterations. Generate initial
feasible random solutions. (Here solution represents operation priority
number corresponding to each activity).
Step 2 : Randomly choose an antigen and expose to all antibodies. Calculate the
affinity of all antigens and create affinity vector Af. (In our case to
calculate affinity, first optimal/near optimal schedules of activities are
determined with the help of priority number as give in Section 3.3
thereafter; its make span value is calculated).
Step 3 : Select Pc highest affinity antibodies. Generate the set of clones for the
Step 4 : For each generated clone do inverse mutation (select a portion of clone
string and invert) with a probability and calculate the affinity of the new
solution formed. If affinity (new solution)>affinity (clone) then clone=new
solution; else do pair wise interchange mutation (select any two location
and inter- change elements). Calculate the affinity of the new solution
formed if affinity (new solution)>affinity (clone) then clone=new solution;
Step 5 : Expose the new denizens of the society (i.e.,clones) to the antigens. Check
for feasibility and calculate affinity.
Step 6 : Replace the Ps lowest affinity antibodies with the Ps best clones
generated. Iter=iter+1; if(iter<iter_max) goto step 2 else Give the best
antibody as the output.
The AIS flowchart is shown in Figure 2.2.
Figure 2.2: AIS flowchart
2.2.3 GRAPH COLORING METHOD
It is well known that the examination timetabling problem, when considering only the examination conflicts constraint, maps into an equivalent graph coloring problem (Kiaer & Yellen, 1992), which is NP-complete (Burke, Elliman, & Weare, 1993; Willemen, 2002). The graph coloring problem is an assignment of colors to vertices in such a manner that no two adjacent vertices have the same color. Therefore, a solution to the graph coloring problem represents a solution to the core examination timetabling problem, where graph vertices correspond to exams, graph edges indicate that the connected vertices have an examination conflict, and colors represent unique time slots (Welsh & Powell, 1967). The graph coloring problem in turn is solved using one of the graph coloring heuristics (e.g., Largest Degree), usually with backtracking (Burke, Newall, & Weare, 1998; Carter, Laporte, & Chinneck, 1994).
Graph coloring is a special case of graph labeling. It is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges share the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color (DR Hussein & K.E.Sabri, 2006).
Graph coloring is one of the most functional models in graph theory. It has been used to solve many problems such as in school timetabling, computer register allocation, electronic bandwidth allocation, and many other applications (Dr Hussein & K.E.Sabri, 2006). Dr Hussein and K.E.Sabri also mention that Greedy Graph Coloring is one of the sequential techniques for coloring a graph. They stated that the technique focuses on cautiously select the next vertex to be colored. In their report they explain two common algorithm which is first fit and degree based ordering techniques.
First fit : First Fit algorithm is the easiest and fastest technique of all greedy coloring heuristics. The algorithm sequentially assigns each vertex the lowest legal color. This algorithm has the advantage of being very simple and fast and can be implemented to run in O(n).
Degree based ordering : It provides a better strategy for coloring a graph. It uses a certain selection criterion for choosing the vertex to be colored. This strategy is better than the First Fit which simply picks a vertex from an arbitrary order. Some strategies for selecting the next vertex to be colored have been proposed such as:
Largest degree ordering (LDO): It chooses a vertex with the highest number of neighbors. Intuitively, LDO provides a better coloring than the First Fit. This heuristic can be implemented to run in O(n2).
Saturation degree ordering (SDO): The saturation degree of a vertex is defined as the number of its adjacent differently colored vertices. Intuitively, this heuristic provides a better coloring than LDO as it can be implemented to run in O(n3).
Incidence degree ordering (IDO): A modification of the SDO heuristic is the incidence degree ordering. The incidence degree of a vertex is defined as the number of its adjacent colored vertices. This heuristic can be implemented to run in O(n2).
2.2.4 GENETIC ALGORITHM
The genetic algorithms distinguish themselves in the field of methods of optimization and search for the assimilation of the Darwinian paradigm of the evolution of species.
The genetic algorithms are processes of convergence (Queirós, 1995). Its structure is governed by import laws of the theory of evolution of species and concreteness in two fundamental concepts: selection and reproduction. The confrontation between genetic algorithms and the real problems is promoted by the need for optimization. It follows a space of enormous dimensions, in which each point represents a potential solution to the problem. In this maze of solutions, only a few, if not only one, fully satisfy the list of constraints that give shape to the problem.
The problems of optimization, usually associated with the satisfaction of constraints, define a universe of solutions, leaving the genetic algorithm to determine the overall solution, or a solution acceptable as a limitation on the time of action of the algorithm.
The genetic algorithms are search algorithms based on mechanisms of natural selection and genetics. Usually used to solve optimization problems, where the space of search is great and conventional methods is inefficient (R. Lewis and B. Paechter,2005).
The terminology they are associated to translate the import of essential concepts of genetics and guesses the importance attributed to the interaction of these concepts. The concept of population, like number of individuals of the same species, is extended to artificial species. Individuals are normally represented by sequences of numbers: the genotype. The numbers, or rather, a collection of numbers, is the genetic heritage of the individual, determining their characteristics, that is, its phenotype. The genetic algorithms differ from traditional methods of research and optimization, mainly in four aspects:
Work with a codification of the set of parameters and not with their own parameters.
Work with a population and not with a single point.
Uses information from or gain cost and not derived or other auxiliary knowledge.
Uses rules of transition probability and not deterministic.
The solutions interact, mix up and produce offspring (children) hoping that retaining the characteristics "good" of their ascending (parents), which may be seen as a local search, but widespread. Not only is the neighborhood of a simple solution exploited, but also the neighborhood of a whole population.
The members of the population are called individuals or chromosomes. As in natural evolution, the chromosomes are the base material (virtual, in this case) of heredity. It currently uses a function of evaluation that associates each individual, a real number that translates to adaptation.
Then, in a manner directly proportional to the value of their adaptation, are selected pairs of chromosomes that will cross themselves. Here, can be considered the selection with elitism, or ensure that the best solution is part of the new generation.
His crossing is the result of artificial selection, considering more adapted those that best meet the specific conditions of the problem. The crossing of the numerical sequences promotes the emergence of new sequences, formed from the first. With a probability established, after crossing, a mutation can happen, where a gene of chromosome changes.
These new individuals are the second generation of individuals and mark the end of cycle of the genetic algorithm. The number of cycles to perform depends on the context of the problem and the level of quality (partial or full satisfaction of the restrictions), which is intended for the solution.
184.108.40.206 A SIMPLE GENETIC ALGORITHM DESCRIBES THE FOLLOWING CYCLE
There are eight step in genetic algorithm cycle which is :
Generation of random n chromosomes that form the initial population.
Assessment of each individual of the population.
Verification of the termination criteria.
If verify termination criterion - cycle ending.
Selection of n/2 pairs of chromosomes for crossover.
Reproduction of chromosomes with recombination and mutation.
New population of chromosomes called new generation.
Go back to step 2.
The cycle described above is illustrated in Figure 2.1.
Fig. 2.1. Basic structure of the genetic algorithm
Initially many individual solutions are randomly generated to form an initial population. The population size depends on the nature of the problem, but typically contains several hundreds or thousands of possible solutions. Traditionally, the population is generated randomly, covering the entire range of possible solutions (the search space). Occasionally, the solutions may be seeded in areas where optimal solutions are likely to be found (R. Lewis and B. Paechter,2005).
During each successive generation, a proportion of the existing population is selected to breed a new generation. Individual solutions are selected through a fitness-based process, where fitter solutions (as measured by a fitness function) are typically more likely to be selected. Certain selection methods rate the fitness of each solution and preferentially select the best solutions. Other methods rate only a random sample of the population, as this process may be very time-consuming (R. Lewis and B. Paechter,2005).
Most functions are stochastic and designed so that a small proportion of less fit solutions are selected. This helps keep the diversity of the population large, preventing premature convergence on poor solutions. Popular and well-studied selection methods include roulette wheel selection and tournament selection (R. Lewis and B. Paechter,2005).
The next step is to generate a second generation population of solutions from those selected through genetic operators: crossover (also called recombination), and/or mutation.
For each new solution to be produced, a pair of "parent" solutions is selected for breeding from the pool selected previously. By producing a "child" solution using the above methods of crossover and mutation, a new solution is created which typically shares many of the characteristics of its "parents". New parents are selected for each new child, and the process continues until a new population of solutions of appropriate size is generated. Although reproduction methods that are based on the use of two parents are more "biology inspired", some research suggests more than two "parents" are better to be used to reproduce a good quality chromosome(R. Lewis and B. Paechter,2005).
These processes ultimately result in the next generation population of chromosomes that is different from the initial generation. Generally the average fitness will have increased by this procedure for the population, since only the best organisms from the first generation are selected for breeding, along with a small proportion of less fit solutions, for reasons already mentioned above.
This generational process is repeated until a termination condition has been reached (R. Lewis and B. Paechter,2005). Common terminating conditions are:
A solution is found that satisfies minimum criteria.
Fixed number of generations reached.
Allocated budget (computation time/money) reached.
The highest ranking solution's fitness is reaching or has reached a plateau such that successive iterations no longer produce better results.
Combinations of the above.
2.3 RELATED WORK
Genetic Algorithm is the best algorithm in timetabling problem. The results in GAs are better optimized than the traditional method based on try-check principles on scheduling system. Some researcher had different opinion on the advantages and disadvantages of these algorithms. Although there are new method on optimizing result, GAs is still the chosen method in timetabling problem.