Abstract. Examination Scheduling is an optimization problem with constraints, 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 problem. In this paper we have developed a way of encoding the solutions of
examination scheduling in order to apply genetic algorithm
10 trang |
Chia sẻ: thanhle95 | Lượt xem: 384 | Lượt tải: 0
Bạn đang xem nội dung tài liệu Genetic algorithms and application in examination scheduling, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
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