Genetic algorithms and application in examination scheduling

JOURNAL OF SCIENCE OF HNUE 2011, Vol. 56, N◦. 1, pp. 40-49 GENETIC ALGORITHMS AND APPLICATION IN EXAMINATION SCHEDULING Vu Dinh Hoa(∗) and Dang Xuan Tho Hanoi National University of Education (∗)E-mail: hoavd@fpt.com.vn Abstract. Examination Scheduling is an optimization problem with con- straints, a scheduling problem is one of the NP-hard problems, there is no algorithm that can solve them in polynomial time. Genetic algorithm is an algorithm for finding approximate optimal test of the global optimization problems. Application of genetic algorithms on the specific problem is not trivial; encoding the solution of the problem, identifying the mutation and crossover operator and fitness function of the solutions of the specific prob- lem. In this paper we have developed a way of encoding the solutions of examination scheduling in order to apply genetic algorithm. Keywords: Genetic Algorithms, Scheduling Problems, Examination Scheduling. 1. Introduction Examination scheduling is a part of a general scheduling problem. It deals with the satisfactory allocation of resources over time to achieve organizations tasks. It is a decision-making process with the intention of optimizing one or more objectives. As we already knew, a general scheduling problem is a NP-complete problem. So the question is that what if examination scheduling is a NP-complete problem or not? It is very difficult to prove that a problem is a NPC problem. We have some papers from several prestigious magazines said that examination scheduling problems is a NPC problem (see [1,2,3,4]). 2. Content 2.1. The Examination scheduling Problems The examination scheduling is a difficult problem, one of the NP - complete problems. 40 Genetic algorithms and application in examination scheduling 2.1.1. The set of hard and soft constraints In the examination scheduling problem, available resources are lecturers, classes, courses, classrooms, and sections. A solution must group these resources together to create a timetable that satisfies the constraints. There are two types of constraints: hard constraints and soft constraints. - Each classroom must be booked with two lecturers. - A lecturer not to be assigned more than one classroom at the same time. - Each course must be booked to a classroom that is large enough to hold students of that course. - Lecturers can require some busy working-sessions. - A classroom cannot be booked for more than one course at the same time. - A class cannot be tested more than one course at a time. - A course cannot be booked twice. - Two courses of a class must be separated by at least two days. 2.1.2. The related works on examination scheduling problems Examination scheduling is a NP-Complete problem that has generated hun- dreds of papers and thousands of researchers who have attempted to solve the prob- lem. Here are some of the primary approaches: - Sequential methods. - Cluster methods. - Constraint based methods. - Meta-heuristic methods. + Simulated annealing. + Tabu search. + Genetic algorithms. + Hybrid approaches. 2.2. Genetic Algorithms Genetic algorithms (GAs) was invented by John Holland in the 1960s and were developed by Holland, his students and colleagues at the University of Michigan in the 1960s and the 1970s. Outline of the Basic Genetic Algorithm [5] is presented in Figure 1. We add one more operator: reproduce in step 4. We will select two individuals which have the best fitness value and keep them in the next generation. So we can make sure that the future generations have better or equal fitness value than the former generations. 41 Vu Dinh Hoa and Dang Xuan Tho 1. [Start] Generate random population of n chromosomes (suitable solutions for the problem). 2. [Fitness] Evaluate the fitness f(x) of each chromosome x in the population. 3. [New population] Create a new population by repeating following steps until the new population is complete. a. [Selection] Select two parent chromosomes from a population accord- ing to their fitness (the better fitness, the bigger chance to be selected). b. [Crossover] With a crossover probability cross over the parents to form a new offspring (children). If no crossover was performed, offspring is an exact copy of parents. c. [Mutation] With a mutation probability mutate new offspring at each locus. d. [Accepting] Place new offspring in a new population. 4. [Replace] Use new generated population for a further run of algorithm. 5. [Test] If the end condition is satisfied, stop, and return the best solution in current population. 6. [Loop] Go to step 2. Figure 1. The Basic Genetic Algorithm 2.2.1. Encoding of a Chromosome The chromosome can be represented in many ways of encoding depending on the solved problem. The most widely used way of encoding is as a binary string. The chromosome will look like [6]: Chromosome 1: 1010001010011 Chromosome 2: 1100110110101 Each chromosome has one binary string. Each bit in this string can represent some characteristic of the solution. 2.2.2. Crossover Crossover selects genes from parent chromosomes and creates a new offspring. The simplest way is choosing some crossover point randomly and everything before this point is copied from a first parent and then everything after a crossover point is copied from the second parent [5,6]. Crossover will look like: Chromosome 1: 10100 01010011 Chromosome 2: 11001 10110101 Offspring 1: 10100 10110101 Offspring 2: 11001 01010011 42 Genetic algorithms and application in examination scheduling 2.2.3. Mutation Mutation changes the new offspring randomly. For binary encoding we can switch a few randomly chosen bits from 1 to 0 or from 0 to 1. Mutation will look like [5,6]: Chromosome 1: 1010001010011 Offspring 1: 1000001010011 2.2.4. Parameters of GAs - Crossover probability. Crossover probability dictates how often the crossover will be performed. If there is no crossover, offspring is exact copy of parents. If there is a crossover, offspring is made from parts of parents’ chromosome [6]. - Mutation probability. Mutation probability says how often parts of chromosome will be mutated. If there is no mutation, offspring is taken after crossover (or copy) without any change. If mutation is performed, part of the chromosome is changed [6]. - Population size. Population size dictates how many chromosomes are in population (in one generation). If there are too few chromosomes, GAs has a few possibilities to perform crossover and only a small part of search space is explored. On the other hand, if there are too many chromosomes, GA slows down [6]. 2.3. The application in examination scheduling The application displays the information examination scheduling of a faculty in the university, in this paper that is The Faculty of Information Technology at Hanoi National University of Education. The system is built based on the genetic algorithms with the combination of some technologies, for example Visual C# .NET 2008, Microsoft SQL server 2008, LINQ to SQL 2008. 2.3.1. Project overview The examination scheduling system project server for the purpose of making an examination timetable easily that satisfies all conditions. The system includes three major modules: G1. Input data for the entire system, the information about teachers, classes, classrooms and courses examination. 43 Vu Dinh Hoa and Dang Xuan Tho G2. Implementation genetic algorithms (GAs) functions, in- put parameters for implementa- tion of gas, then run the function implementation GAS. G3. Users request to display the results, the system returns the results output to the screen for the user. Includes examination timetable on statistics teachers, classes, courses and save the re- sults into excel file. G4, G5 and G6. The func- tions automatically connect to the database. Figure 2. The systems functions outline 2.3.2. The proposed genetic algorithms Figure 3. High level representation of the proposed genetic algorithm 44 Genetic algorithms and application in examination scheduling This section presents the proposed genetic algorithm that includes genetic rep- resentations, processes to create constraint data, evaluate fitness function, crossover, and mutate chromosomes. - Chromosomes. A chromosome is a solution, in our case it is an examination timetable of the university. The timetable contains a number of sub-timetables of classrooms. Figure 4. A chromosome - Fitness function. F (x) = n∑ i=1 wici(x) where: n is the number of constraints, wi is the penalty cost of each constraint, x is a chromosome, a timetable, ci(x) is the number of conflicted i. - Operators of GA. + Reproduce: Select two individuals which have the best fitness value and keep them in the next generation; Ensure that the future generations have better or equal fitness value than the former generations. + Crossover: Two chromosomes from a population are chosen at random as mother and fa- ther. A new offspring is generated by creating an empty chromosome, then inserting alternate genes (sections) from the mother and father, as illustrated in Figure 5. 45 Vu Dinh Hoa and Dang Xuan Tho Figure 5. Crossover + Mutation: A new offspring that has just been created by crossover will be mutated with a mutation rate. This is done via the following process: go through each gene and swap its content with another gene in the same chromosome. As mentioned in the previ- ous section, a course has to be scheduled to successive section, so we have to swap the successive section booked for a course with other successive section. To facil- itate this, we choose all sections of a working session to swap with those of another, as illustrated in Figure 6. Figure 6. Mutation 2.4. Experimental Results 2.4.1. Manage information of lecturers, classes, courses and classrooms Short name: Manage information. The purpose: Manage all information which has a connection with lecturers, classes, courses and classrooms. Allow the users to be able to insert, delete, edit and update lecturers, classes, courses or classrooms. This function is an input of the function executing genetic algorithms. 46 Genetic algorithms and application in examination scheduling Figure 7. Manage classrooms and lecturers Figure 8. Manage classes and courses 2.4.2. Manage all conflicts of the examination scheduling problem Figure 9. Conflicts of lectures and classrooms Short name: Manage conflicts. The purpose: Manage all conflicts of the examination scheduling problem, concrete include all conflicts which has a connection with the busy days of lecturers, the busy days of classes and conflicts of classrooms. Allow the users to be able to update, edit, insert, delete any conflicts. 47 Vu Dinh Hoa and Dang Xuan Tho 2.4.3. Implement genetic algorithms Short name: Implement. The purpose: Implement genetic algorithms using all information of lec- turers, classes, courses, classrooms and all conflicts which were added before. This function will calculate and implement all operations of genetic algorithms and out- put of it is examination timetables. Figure 10. Implement genetic algorithms 2.4.4. Display the statistics in courses, classes and lecturers Short name: Display. The purpose: Display the final examination timetables that satisfy all conflicts for the users. Figure 11. Display the statistics 2.4.5. Save the results into Excel file Short name: Excel. The purpose: Export the results, the examination timetables into excel file so that the manager examination scheduling can edit easily. This function is very 48 Genetic algorithms and application in examination scheduling important for the manager. Figure 12. Display the results. 3. Conclusion We concentrated on studying examination scheduling problem which is the optimization problems with constraints and one of the NP-hard problems, we also constructed a way to encode solution to the problem, identify the mutation, crossover operator and fitness function of the solutions of the problem in order to apply genetic algorithms. All the functions of the system have been completed and tested. The results of the examination scheduling system are very good and feasible for practical use for the Faculty of Information Technology at Hanoi National University of Education. REFERENCES [1] E. Burke, K. Jackson, J. H. Kingston and R. Weare, 1997. Automated University Timetabling: The State of the Art. Oxford Journals. The Computer Journal, Vol. 40, No .9, pp. 65-571. [2] Bernd Bullnheimer, 1998.An examination scheduling model to maximize students study time. Springer Berlin, pp. 78-91. [3] Burak Bilgin, Ender zcan and Emin Erkan Korkmaz, 2006. An Experimental Study on Hyper-heuristics and Exam Timetabling. Springer Berlin, pp. 394-412. [4] Fn Zhaohui, 2000. Heuristics for the exam scheduling problem. Vancouver, British Columbia, Canada, ictai, pp.0172, 12th IEEE International Conference on Tools with Artificial Intelligence. [5] Sam Hsiung and James matthews, 2008 An Introduction to Genetic Algorithms, by (July 2008) [6] Darrell Whitley, 1994. A Genetic Algorithm Tutorial, Computer Science Depart- ment, Colorado State University, Fort Collins, CO 80523 49