INNOVATIVE EVOLUTIONARY ALGORITHM APPROACH FOR CLASS-TEACHER TIMETABLING PROBLEM Manoj Bahel Dr. (Mrs.) Ani Thomas Research Scholar, Professor, Dept. of Computer Applications, Bhilai Institute of Technology, Bhilai Institute of Technology, DURG (C.G.), INDIA, DURG (C.G.), INDIA, bahel.manoj@gmail.com tpthomas22@yahoo.com ABSTRACT algorithm is a general and optimization algorithms inspired This paper presents the application of genetic algorithms by the processes of natural selection. It can be used as (GAs) as a means of inducing solutions to the Class- techniques for solving complex problems and for searching Teacher Timetabling Problem (CTTP). Timetabling of large problem spaces. Unlike many heuristic schemes, problem in almost all research focus on solving the hard which have only one optimal solution at any time, Genetic constraints. This is an attempt to satisfy as many soft algorithms maintain many individual solutions in the form constraints as possible, as soft constraints are varying in of population. Individuals (parents) are chosen from the nature. Initially the population is created depending on the population and are then mated to form a new individual number of rooms and distribution of subjects with no (child). The child is further mutated to introduce diversity clashes of a particular professor. The application of genetic into the population. Rather than starting from a single point algorithm to this domain is divided into 3-phases, which within the search space, GA is initialized to the population provide timetables that meet the hard constraints during the of guesses. These are usually random and will be spread first phase. In the next phase different sets, which represent throughout the search space. A typical algorithm then uses population satisfying single soft constraints from group of three operators, selection, crossover and mutation, to direct soft constraints is created and in the last phase we obtain the population toward convergence at global optimum. the desired timetable by applying different soft constraints in the form of Set Operations. This provides flexibility in 2. LITERATURE REVIEW adding or removing soft constraints easily. Few research papers and articles published in prestigious journals, on Genetic Algorithms and Resource-Constrained CCS Concepts Scheduling were surveyed and analyzed, Lin-Yu Tseng and •CCS → computing methodologies → Machine learning Shih-Chieh Chen [5] presented a paper on two-phase → Machine learning approaches → Bio-inspired genetic local search algorithm for the multimode resource- approaches → Genetic algorithms constrained project scheduling problem, in which authors studied, the resource-constrained project scheduling problem with multiple execution modes for each activity. Keywords This paper aims to find a schedule of activities such that the Genetic Algorithm, Timetabling, Set Operations, Time make span of the schedule is minimized subject to the Slot, Hard Constraints, Soft Constraints precedence and resource constraints. A two phase genetic local search algorithm that combines the genetic algorithm 1. INTRODUCTION and the local search method to solve this problem is used. Timetabling problems are optimization problems and can The first phase aims to search globally for promising areas, be thought of as a subset of scheduling problems. However, and the second phase aims to search more thoroughly in it is far more complicated than general scheduling as it these promising areas. A set of elite solutions is collected involves teachers, students, classrooms, and courses. From during the first phase, and this set, which acts as the a broader perspective, course arrangement includes many indication of promising areas, is utilized to construct the interrelated issues, such as exams, meetings, administrative initial population of the second phase. By suitable allocation. Conventionally, course timetabling has been applications of the mutation with a large mutation rate, the conducted manually. Due to the large variety of constraints, restart of the genetic local search algorithm, and the resource limitations and complicated human factors collection of good solutions in the elite set, the strength of involved, course timetabling often takes a lot of time and intensification and diversification can be properly adapted manpower. Using computers to perform course timetabling, and the search ability retained in a long term. Jorge however, can not only consolidate the preferences of the Magalhaes and Mendes [6] presented a paper on a people concerned but can also enable achievement of high comparative study of crossover operators for genetic satisfaction in spite of the many constraints. Obviously, this algorithms to solve the job shop scheduling problem. To results in saving a lot of time and thus manpower. Genetic standardized the results of experiments, GA is applied to algorithms are among those that can be used to find the job shop scheduling problem (JSSP) which is based on approximate solutions of timetabling problems. Genetic a decision support system (DSS).In job shop scheduling problem There are a set of jobs j = 1,, n, a set of Copyright © 2017 for the individual papers by the papers’ authors. machines M=1,, m, and a set of operations O = o0, Copying permitted for private and academic purposes. This volume o1,oij,onm,onm+1 Set O contains all the operations of is published and copyrighted by its editors. each job. Each job has m operations. Each machine can process at most one operation at time. The JSSP is to find a constraints to generate it we will remove the schedule which minimizes the make span (Cmax), that is, fittest population representing timetable from the the finish time of the last operation completed in the population and move it to the selected list. Now schedule, taking into account the precedence constraints. we apply cross-over and mutation operator on Equal opportunity is given to all the operators to compare remaining population and we continue this the abilities of different crossover operators. The genetic process till user defined number of times and in crossover operators are tested on a set of standard instances the second phase different sets representing taken from the literature. The make span is the measure particular soft constraint from the group of soft used to evaluate the genetic crossover operators. In the constraints is created and in third and final phase sense of Jorge Magalhaes and Mendes authors the main different Set Operations are used to generate the conclusion is that there is a crossover operator having the final timetable. best average performance on a specific set of solved instances.Umut Besikcia, Umit Bilgea, Gunduz Ulusoyb[7]  The genetic algorithm implemented in all the presented a paper on multi-mode resource constrained three phases uses domain specific knowledge, in multi-project scheduling and resource portfolio problem, in the form of heuristics, to guide the evolutionary this work authors introduced a multi-project problem process. environment which involves multiple projects with assigned due dates; activities that have alternative resource 4. CONCLUSION usage modes; a resource dedication policy that does not The timetabling problem has become a current area of allow sharing of resources among projects throughout the research as it becomes difficult to manage the uniformity of planning horizon; and a total budget. The dedication of subjects taught and clash management of rooms and resources reduces the scheduling of the projects' activities professors. A proper and well organized scheduling to a multi-mode resource constrained project scheduling approach for solving Timetabling problem is necessary. problem (MRCPSP) for each individual project. In this Adding or removing soft constraints much more flexible paper, this multi-project environment is modeled in an and we can generate different instances of time table with integrated fashion and designated as the Resource Portfolio less computational time. Crossover and Mutation policies Problem. A two-phase and a monolithic genetic algorithm can be enhanced in future work, thus generating a precise are proposed as two solution approaches, each of which and accurate time table generation equalizing to the employs a new improvement move designated as the intelligence of human brain. combinatorial auction for resource portfolio and the combinatorial auction for resource dedication. 5. ACKNOWLEDGMENTS This work was supported by Research and Development Laboratory, Department of Computer Science and 3. METHODOLOGY Engineering at Bhilai Institute of Technology, Durg, The Class-Teacher Timetabling Problem (CTTP) concerns Chhattisgarh, India, awaiting sponsorship from suitable scheduling teachers and classes over a set of periods, funding agencies. typically covering five or six week days depending upon the institutional policy [8]. The basic constraints that must 6. REFERENCES [1] Salvatore D. Abramson 1991. Constructing school be satisfied are i)professors can only be in one class at any timetables using simulated annealing: sequential and given time ii) classrooms need to be big enough to host the parallel algorithms. Management Science, 37:98:113. class iii) Classrooms can only host one class at any given [2] S. Daskalaki, 2004. An integer programming time. This classical version of the CTTP was shown to be formulation for a case study in university timetabling. NP-Complete [9]. The manual construction of timetables in European Journal of Operational Research, educational institutions is often a very time-taking task. 153:117:135. Besides the basic constraints, a good timetable should [3] L.A. Wolsey, 1975. Faces for a linear inequality in 0-1 consider many other requirements, such as institutional, variables. Mathematical Programming, pedagogical and personal (staff related) needs [8].In fact, [4] G. B. Dantzig and P. Wolfe, 1960. Decomposition quality of timetable generated depends upon the specific principle for linear programs. Operations Research. educational system. However some common assumptions [5] Lin-Yu Tseng and Shih-Chieh Chen 2009, Two-Phase are made in most works like there should be gap of at least Genetic Local Search Algorithm For The Multimode one period after two consecutive periods. The solution Resource-Constrained Project Scheduling Problem, space definition, specified by the hard constraints, usually ieee transactions on evolutionary computation, VOL. does not include many other constraints besides the above 13 NO. 4, mentioned basic constraints. Another very common type of [6] Jorge Magalhaes and Mendes 2013, A Comparative soft constraint is the number of lectures required by the Study Of Crossover Operators For Genetic Algorithms professor that basically depends upon type of subject taught To Solve The Job Shop Scheduling Problem WSEAS by the professor. Heuristic methods are effective in practice TRANSACTIONS on COMPUTERS, Volume 12. for solving timetabling problem as exact methods require [7] Umut Besikcia, Umit Bilgea, Gunduz Ulusoyb 2014, large amount of processing time on most timetabling Multi-Mode Resource Constrained Multi-Project variants. These methods include meta heuristics such as Scheduling and Resource Portfolio Problem, European Simulated Annealing [1], Evolutionary Algorithms [2], Journal of Operational Research. Tabu Search [2,3,4,5] and some of their hybrids. The [8] Haroldo Gambini Santos,Eduardo Uchoa, Luiz Satoru approach taken in this study differs from previous studies Ochi and Nelson Maculan 2010, Strong bounds with applying genetic algorithms to this domain as follows: cut and column generation for class-teacher  A three-phased approach is taken to the problem. timetabling Annals of Operations Research April In the first phase a genetic algorithm is employed 2012, Volume 194, Issue 1, pp 399–412 to produce timetables that do not violate any hard [9] A. Hertz, 1991. Tabu search for large scale timetabling problems. European Journal or Operational Research, 54:39-47.