Timetable Scheduling Algorithm



Download 54.03 Kb.
View original pdf
Date01.11.2018
Size54.03 Kb.

Timetable Scheduling Algorithm
Ali Masri
Raef Mousheimish
Youssef Dergham
December 31, 2013 1
Introduction
The timetable problem is the process of scheduling a sequence of courses between teachers and students, in tendency to satisfying a set of constraints of various types, these constraints differ basing on the institutions involved, e.g. schools,
universities... The manual solution that still applied nowadays, is considered time and effort-consuming, where many persons and many days are required to build such schedule. Not to mention that the majority of the built schedules do not satisfy the constraints expressed before the building phase, e.g. a student may not be able to take the courses he/she wants because they are scheduled at the same time. For the aforementioned reason, a lot of researches, proposals,
and software are issued to transform this heavy manual scheduling to become an automatic one. and we can track the proposed solutions in this domain back to the 1963, begun by Gotlieb[4]. So the timetable scheduling problem has been a rich source for researchers and a challenging field for years. and since it is classi-
fied as an NP-Hard problem, it is addressed now by techniques belonging to the
Artificial Intelligence field, e.g. genetic algorithms, tabu search, and constraint satisfaction. Therefore, so many researchers provided many approaches to solve this problem each differs by the way of representing it and how it is projected on the used algorithm concept, more specifically the genetic algorithm, and each approach applies some modifications to speedup the solving process and make it more time feasible, as depending on genetic algorithms may consume a lot of time before finding a proper solution. In this report we will highlight some of these approaches, and discuss their characteristics, and then we tried to extend this survey to include our contribution. Benefiting from previous works, that we discussed in the corpus of this paper, we created anew algorithm, taking the preferences of the teacher and their priority into account. The priority of the teachers are determined basing on numbered criteria, e.g. age, gender, degree...
Borrowing the algorithms used in the multi-criteria analysis domain to define the weight of each instructor comparing to others. Then a table depicting the preferred periods of each teacher is taken into consideration, while generating the tables and applying our descent algorithm. So the paper will be divided into two sections. The first one will show the previous surveys, approaches and software, expressing the chromosomes looks, and the crossover mechanisms. and then stepping into the second section where our contribution is discussed.
1

Previous Surveys
There exist so many surveys concerning the timetable problem, we list some of them:
• Schmidt and Strohlein (1979)[5] provide an annotated bibliography including more than 200 entries.
• Junginger (1986)[6] describes the research in Germany on the school timetabling problem. In particular, he describes the various software products imple- mented.
• De Werra (1985)[7] states the various problems in a formal way, and provides different formulations for them.
• Corne et al. (a provide a survey of the application of genetic algorithms to timetabling.
3
Related Work
3.1
Abramson et al.
Abramson et al. introduced their approach to solve -with a faster way- our problem by taking advantage of parallel algorithms. Abramson et al. represented the problem by a chromosome consisting of periods such that each period contains collection of tuples (Class,Teacher,Room). The goal here is obvious,
no element of the tuples in the same period clashes. Figures 1 and 2 shows the representation of tuples and periods respectively.
The contribution here
Figure 1: Tuples was in using the power of parallel algorithm to speedup generations reproduction. Since each mating process is independent from the other, the authors assign a worker thread for each mating process. And by this surely the speed of reproduction was increased and the results made were promising.
3.2
Yao-Te Wang et al.
In this approach, the proposed solution is divided into two stages, the first one consists of data mining techniques to retrieve the courses preferred by students,
2

Figure 2: Periods then the second and the more important stage is the automatic generation of the schedule, using the genetic algorithm. Included in this approach, a separation of the constraints, between hard and soft constraints. Hard ones must be respected,
and if not the solution is considered unsatisfactory, but there is more tolerance concerning the soft constraints. The chromosomes in the approach are the class period (the time and place. the genes are the courses. when a course is assigned to a class period, a cost (fitness) function is calculated. Cost function = CC+ CC. Where C is the Cost of constraints, i.e. the cost to violate the soft constraints. C is the Teacher’s preferences, i.e. a teacher’s willingness to teach in a particular class period. C is the Frequency at which a teacher taught in a particular class period, i.e. the teacher’s former habit in class period arrangement. and C is the Student’s learning performance, i.e. class periods when students had better learning performance. The automatic process can be depicted in figure Figure 3: The automatic course scheduling procedure
3


3.3
Shimon’s Project-Genetic Algorithm Time Tabling
The purpose of this project is to explore, from the grounds up, the behaviors that genetic algorithms exhibit and the phenomena that manifest during the evolutionary process. For that purpose, a Java application was designed that lets the user observe the different states of the population over the course of the evolutionary process. A timetabling problem, as considered in this project, is composed of:
• A set of classrooms, where each classroom has a certain capacity, certain available study aids and an availability timetable (see Figure 6). Each classroom also has a unique id and a unique name.
• A set of teachers, where each teacher has an availability timetable (the same as mentioned above, a unique id and a unique name (see Figure A set of courses. Each course is comprised of a set of lectures.The scheduling times for lectures that belong to the same course must not overlap, it is intended for students of the course to participate in them all.[10]
Fitness Function
In order to come up with a fitness score fora chromosome, the fitness operator goes overall the hours of all the lectures the solution entails and sums up penalties for violated constraints, using the following formula[10]:
4

Where hard is the set of all violated hard constraints encountered, and soft is the set of all soft ones, w(s) is the weight associated with a soft constraints (see note below, and is zero until hard is empty. Meaning we do not account for soft constraints until all hard ones have been satisfied. This mechanism ensures satisfying many soft constraints never comes at the expense of violating even a single hard one[10].
Case Study
There is a single classroom with only 8 available study periods. There is 1 course with 8 lectures, each taught by a different teacher. Each one of the teachers prefers to teach in one of the available time slots the classrooms has (they all prefer different time slots)[10].
4
Dedicated Software
Moving into the application field, many developers took the wheel with implementing significant software that deals with the scheduling problem. In this section we will introduce some of them that claim a high rank in this field.
4.1
aSc Timetables
The award winning software the ”aSc Timetables provides a very user friendly interface with high usability. It provides both manual and automatic timetable generation. All what the user does is to enter some details and constraints on courses, classes, and teachers, and the software will automatically generates the feasible timetable. No such information about the implemented algorithm is given by the developers. But we cannot ignore that this program is a hit in the
field of timetable generation. Figure 4 shows the interface of the program.
5

Figure 4: aSc Timetables Application
4.2
Prime Timetable
Prime Timetable is also one powerful software that enables also manual and automatic generation of the timetable. The interface is elegant and friendly and gives the user more control and more settings to be applied on the generation phase. Figure 5 shows the interface of the program.
6

Figure 5: Prime Timetable Application
5
Our Contribution
In our contribution we decided to get the best of each previous algorithm. We chose our gene and chromosome representation based on Abramson et al.[1], and benefit from the speed of parallel mating to speedup the processing speed of the program. We extended the idea from Shimon’s Project-Genetic Algorithm
Time Tabling to include more precise preference table.
5.1
Teacher’s Weight
Since some conflicts may persist in the generated timetable, it is important to know which teacher to satisfy most. The ranking of each teacher depends on a multi-criteria analysis. By taking benefit of the AHP and WSM algorithms[11][12],
we may give each teacher a rank that represent his priority comparing with other teachers. The below table shows a sample of a multi-criteria decision table of teachers. The table maybe extended for more possible criteria.
Teacher/Criteria
Age
Degree
Marital Status
Gender
Teacher Teacher Teacher n
7

Teachers Preference Table
For each teacher we represent a table that describes his preferences, such that a teacher fills this table with a value for each entry representing his acceptance to take this period. The value rages from 0 to 10. 0 is the least acceptable value,
and 10 is the most acceptable one.
Period/Day
Monday
Tuesday
Wednesday
Thursday
Friday
P1
P2
P3
P4
P5
P6 Fitness Function
Generating a timetable without conflict alone is not the case here. We must check if the generated timetable matches our teacher’s preferences or not. Our idea here is to extend the fitness function to take into consideration the conflict and the preference percentage of the generated table. In order to make it more clear and to separate concepts we introduced two fitness functions (fConflict and fPreference). Where fConflict is the function that calculate the fitness of each table according to the period conflicts, and fPreference is the function that calculates the degree of teacher’s satisfaction on the generated table.
fConflict
Nothing new to define here, the fitness function adopted from Abramson et al.[1]
does all the work. It calculates the fitness of each table according to the conflict level between periods.
fPreference
This function calculates how many teacher is satisfied according to his preferences and the generated timetable. The tolerated degree of satisfaction of teachers is a predefined number that changes according to user preferences. We calculate it by collecting the teacher’s given hours in the generated time table,
and add the value at this entry in the teacher’s preference table to the total satisfaction value. After finished we check if the value is above the satisfaction threshold - a predefined value - we add one to the fPreference value to denote a newly satisfied teacher. We iterate overall teachers to calculate the final value of fPreference. The below pseudo code clarify the idea more.
begin fPreferenceValue = 0
while(teachers.hasNext()) do teacher = teachers.next()
8

periods = getPeriods(teacher)
value = 0
while(periods.hasNext()) do period = period.next()
value = value + teacher.preferenceTable(period)
end if value > threshold then fPreferenceValue++
end end
5.4
Algorithm
The overall algorithm of our timetable generation algorithm is defined below. Generate a random timetable. Create a thread for each mating process. Wait till mating complete. Mutate children. Calculate the fitness value (fConflict) of each child. Collect the new population from the old one having the best fitness function. Iterate over each population element. Check if the fitness value (fConflict) is above the threshold. If yes, iterate through each conflict and assign a period that best fit the teacher’s preferences. Calculate the fitness value (fPreference) of each population element. If value above threshold, solution found. Else goto 2 9


6
Conclusion
Genetic algorithms area search technique inspired by evolutionary biology. A
population of solutions is maintained and managed through the use of genetic operators selecting some solutions that are better than others, combining them and modifying them. The process is executed in a continuous iterative manner,
and as time progresses better solutions are found.
Genetic algorithms are often used when dealing with hard optimization problems and are widely applied with the timetabling problem, mainly due to their ability to traverse sparse search spaces, the likes of which the TT problem has.
In this survey we introduced some articles that deals with GA to solve the timetabling problem and we introduced as well some software that are proposed to solve the timetabling dilemma. and finally we end it up by introducing our own algorithm to solve the timetabling problem but with taking the teachers preferences and weights into account, and integrate these aspects more deeply and more importantly into the work flow of our solution.
The question that might arise at this stage is what is the best solution. In our future attempts, this is what we will try to address, implementations and evaluations of our approach against other approaches will be a field of our interests.
10

References D.Abramson, J.Abela: A Parallel Genetic Algorithm for Solving the School
Timetabling Problem, High Performance Computation Project Division of
Information Technology aSc Timetables official website http://www.asctimetables.com
[3] Prime Table official website http://www.primetimetable.com
[4] CC. Gotlieb. The construction of class-teacher timetables. In CM. Pop- plewell, editor, IFIP congress 62, pages 73-77. North-Holland, 1963.
[5] G. Schmidt and T. Strohlein. Timetable construction - an annotated bibliography. The Computer Journal, 23(4):307-316, 1979.
[6] W. Junginger. Timetabling in Germany - a survey. Interfaces, 16:66-74,
1986.
[7] D. de Werra. An introduction to timetabling. European Journal of Operational Research, 19:151-162, 1985.
[8] D. Corne, P. Ross, and H.-L. Fang. Evolutionary timetabling practice,
prospects and work in progress. In UK Planning and Scheduling SIG Workshop Yao-Te Wang, Yu-Hsin Cheng, Ting-Cheng Chang, and S.M.JEN. On the
Application of Data Mining Technique and Genetic Algorithm to an Automatic Course Scheduling System. CIS/IEEE (2008)
[10] Shimon.Genetic Algorithm Time Tabling final project for Introduction to
Artificial Intelligence”.HUJI March 2010
[11] Wikipedia http://en.wikipedia.org/wiki/Analytic hierarchy process Wikipedia http://en.wikipedia.org/wiki/Weighted sum model
11



Share with your friends:


The database is protected by copyright ©userg.info 2017
send message

    Main page

bosch
camera
chevrolet
epson
fiat
Honda
iphone
mitsubishi
nissan
Panasonic
Sony
volvo
yamaha