1. 研究目的与意义（文献综述包含参考文献）

文献综述1. 前言 (Introduction)The manual system of preparing time table in schools, colleges and universities with large number of students is very time consuming and usually ends up with various classes clashing either at same room or with same teachers having more than one class at a time. To overcome all these problems, we propose to make an automated timetable generation system. It helps to provide an optimal solution. The methodology we used is genetic algorithm. The software requirements are Windows 7, XAMP Server, and My SQL 5.6 and the languages we will for this application are html, bootstrap,css for frontend and java for backend.2. 当前研究现状(Related Work)Time Table Scheduling is an NP-hard problem and hence polynomial time verifiable using genetic algorithms[1]. It a typical scheduling problem that appears to be a tedious job in every academic institute once or twice a year. In earlier days, time table scheduling was done manually with a single person or some group involved in task of scheduling it manually, which takes a lot of effort and time. Planning timetables is one of the most complex and error-prone applications[2].Timetabling is the task of creating a timetable while satisfying some constraints[3]. There are basically two types of constraints, soft constraints and hard constraints. Soft constraints are those if we violate them in scheduling, the output is still valid, but hard constraints are those which if we violate them; the timetable is no longer valid[4]. The search space of a timetabling problem is too vast, many solutions exist in the search space and few of them are not feasible. Feasible solutions here mean those which do not violate hard constraints and as well try to satisfy soft constraints[5]. We need to choose the most appropriate one from feasible solutions[6]. Most appropriate ones here mean those which do not violate soft constraints to a greater extent. In this project hard-constraints have been taken care of strictly and it has been ensured that soft-constraints are as well followed as much as possible.Soft-constraints (flexible): More or less equal load is given to all faculties Required time (hours per week) is given to every BatchHard-constraints (rigid): There should not be any single instance of a faculty taking two classes simultaneously A class group must not have more than one lectures at the same time参考文献：(Reference)[1] Enrique Alba. Parallel Met heuristics: A New Class of Algorithms. Wiley- Interscience, 2005.[2] D. Abramson. Constructing school timetables using simulated annealing: sequential and parallel algorithms. Manage. Sci., 37(1):98113, January 1991.[3] David Abramson and J Abela. A parallel genetic algorithm for solving the school timetabling problem. In 15 Australian Computer Science Conference, 1992[4] Odim, M. O., B. O. Oguntunde, and O. O. Alli. "On the Fitness Measure of Genetic Algorithm for Generating Institutional Lecture Timetable." Journal of Emerging Trends in Computing and Information Sciences 4.4 (2013).[5] Thakare, Shraddha. Automated Timetable Generation using Genetic Algorithm. International Journal of Engineering Research and V9, 2020/08/04.[6] Mosaic Space Blog, The Practice and Theory of Automated Timetabling PATAT 2010, Mosaic Space Blog, University and college planning and management retrieved, from http://mosaicd.com/blog, 2011, Last accessed date 21st January 2012.[7] D. G. Maere, (2010). How Working Group Automated Timetabling was founded, retrieved from http://www.asap.ac.nott.ac.uk/, 2010, Last accessed date 9th December 2011.[8] Akshay Puttaswamy, H M Arshad Ali Khan, Chandan S.V, Parkavi.A Department Of Computer Science And Engineering, A Study On Automatic Timetable Generator. International Journal of Science and Innovative Engineering Technology May 2018 Issue Volume 5[9] Saritha et al., International Journal of Advanced Research in Computer Science and Software Engineering 7(5), May- 2017, pp. 204-211.[10] P. Ross, D. Corne, Applications of Genetic Algorithms, Department of Artificial Intelligence, University of Edinburgh, 2003. Retrieved from www.citeseerx.ist.psu.edu/viewdoc/download?doc =10.1.1.31.8.42. Last accessed date 26th February 2012.[11] H. Nemati, Genetic Algorithm. Information Systems and Operations Management, Department of the University of North Carolina at Greensboro retrieved from www.uncg.edu/ism/ism611.genetic.pdf. Last accessed date 22nd January 2012.[13] P. Ross, D. Corne, Applications of (GA) Genetic Algorithms, Department of Artificial Intelligence, University of Edinburgh, 2003. Retrieved from www.citeseerx.ist.psu.edu/viewdoc/download? [14] Sayed PE, Ahmed A, Amir A, Zaeem A. Automated Timetable Generator. International Journal for Innovative Research in Science Technology Volume 1Issue 11April. 2015.[15] Ambhore S, Walke P, Ghundgrudkar R, Alone A, Khedkar A. Automatic Timetable Generator. International Journal of Scientific Engineering Research Volume 9, Issue 4, April-2018

2. 研究的基本内容、问题解决措施及方案

1. 拟研究或解决的问题Normally timetable generation done manually. As we know all organizations have its own timetable, managing and maintaining these will not be difficult. Considering workload with this scheduling will make it more complex. As mentioned, when timetable generation is being done, it should consider the maximum and minimum workload that is in a college. In those cases timetable generation will become more complex. Also it is time consuming process.2. 拟采用的研究手段（途径）Before we can use a genetic algorithm to solve a problem, a way must be found of encoding any potential solution to the problem. This could be as a string of real numbers or, as is more typically the case, a binary bit string. We will refer to this bit string from now on as the chromosome. A typical chromosome may look like this:10010101110101001010011101101110111111101At the beginning of a run of a genetic algorithm a large population of random chromosomes is created. Each one, when decoded will represent a different solution to the problem at hand. Let's say there are N chromosomes in the initial population. Then, the following steps are repeated until a solution is found Test each chromosome to see how good it is at solving the problem at hand and assign a Fitness Score accordingly. The fitness score is a measure of how good that chromosome is at solving the problem to hand. Select two members from the current population. The chance of being selected is proportional to the chromosomes fitness. Roulette Wheel Selection is a commonly used method. Dependent on the Crossover rate crossover the bits from each chosen chromosome at a randomly chosen point. Step through the chosen chromosomes bits and flip dependent on the Mutation rate. Repeat step 2, 3, 4 until a new population of N members has been created. Keep repeating until required fitness is achieved.Objects of Time Table Scheduler Students GroupThe StudentGroup class has the ID, name of the student group, number of subjects, array of subject names and hours of study required for each subject per week. It also contains the id of teachers who will teach those subjects.TeacherIt is a class to hold the faculty information. It has an id, name of faculty, subject that he/she teaches and an in assigned which represents the no. of batches assigned to the teacher.SlotA slot here is the most basic unit of Genetic algorithm. It represents a single characteristic of a Gene. Time TableThis class object holds an array of Slot. This is basically a class to generate new slots initially for each Student group. GeneIt is the main constituent of a Chromosome and is made up of a sequence of slot numbers. It represents a Time table of a single class group ChromosomeA chromosome here is a collection or an array of Genes. It is the main class of algorithm and it undergoes crossover and mutation to furnish fitter individuals. UtilityIt is basically for testing purpose only. It contains some mehods like printSlots() which help to keep track of algorithm through console. InputdataThis is a class mainly to fetch the input from user either through text file or through form and provide it to the working classes of the algorithm SchedulerMainThis is the main class of the algorithm which invokes other classes and calls methods for crossover, mutation , selection etc.Terminologies involved Permutation Encoding encoding Value encoding tree Encoding. ElitismA practical variant of the general process of constructing a new population is to allow the best organism(s) from the current generation to carry over to the next, unaltered. This strategy is known as elitist selection and guarantees that the solution quality obtained by the GA will not decrease from one generation to the next. Roulette Wheel SelectionIt is a selection procedure in which the possibility of selection of a chromosome is directly proportional to its fitness. Single Point CrossoverIt is that type of crossover between two chromosomes in which the chromosomes are broken at a single point and then crossed. When single point crossover happens in this project, it is made sure that chromosome is not so cut that it intersects the timetable of any student group. Swap MutationIt is the type of mutation technique in which the chromosomes are so mutated that two portions of the chromosome get exchanged resulting in a new chromosome.