=Paper=
{{Paper
|id=Vol-1819/edudm2017-paper4
|storemode=property
|title=
|pdfUrl=https://ceur-ws.org/Vol-1819/edudm2017-paper4.pdf
|volume=Vol-1819
|authors=Manoj Bahel,Ani Thomas
|dblpUrl=https://dblp.org/rec/conf/indiaSE/BahelT17
}}
====
https://ceur-ws.org/Vol-1819/edudm2017-paper4.pdf
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.