Timetable Scheduling AlgorithmAli 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 diﬀer basing on the institutions involved, e.g. schools, universities... The manual solution that still applied nowadays, is considered time and eﬀort-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 ﬁeld for years. and since it is classi- ﬁed as an NP-Hard problem, it is addressed now by techniques belonging to the Artiﬁcial Intelligence ﬁeld, e.g. genetic algorithms, tabu search, and constraint satisfaction. Therefore, so many researchers provided many approaches to solve this problem each diﬀers by the way of representing it and how it is projected on the used algorithm concept, more speciﬁcally the genetic algorithm, and each approach applies some modiﬁcations to speedup the solving process and make it more time feasible, as depending on genetic algorithms may consume a lot of time before ﬁnding 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. Beneﬁting 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 deﬁne 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 ﬁrst 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 diﬀerent 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 ﬁrst 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 (ﬁtness) 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 ﬁgure 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 diﬀerent 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 ﬁtness score fora chromosome, the ﬁtness 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 satisﬁed. 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 diﬀerent teacher. Each one of the teachers prefers to teach in one of the available time slots the classrooms has (they all prefer diﬀerent time slots)[10]. 4 Dedicated Software Moving into the application ﬁeld, many developers took the wheel with implementing signiﬁcant software that deals with the scheduling problem. In this section we will introduce some of them that claim a high rank in this ﬁeld. 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 ﬁeld 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 beneﬁt from the speed of parallel mating to speedup the processing speed of the program. We extended the idea from Shimon’s Project-Genetic AlgorithmTime Tabling to include more precise preference table. 5.1 Teacher’s Weight Since some conﬂicts 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 beneﬁt 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 ﬁlls 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 conﬂict 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 ﬁtness function to take into consideration the conﬂict and the preference percentage of the generated table. In order to make it more clear and to separate concepts we introduced two ﬁtness functions (fConﬂict and fPreference). Where fConﬂict is the function that calculate the ﬁtness of each table according to the period conﬂicts, and fPreference is the function that calculates the degree of teacher’s satisfaction on the generated table. fConﬂict Nothing new to deﬁne here, the ﬁtness function adopted from Abramson et al.[1] does all the work. It calculates the ﬁtness of each table according to the conﬂict level between periods. fPreference This function calculates how many teacher is satisﬁed according to his preferences and the generated timetable. The tolerated degree of satisfaction of teachers is a predeﬁned 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 ﬁnished we check if the value is above the satisfaction threshold - a predeﬁned value - we add one to the fPreference value to denote a newly satisﬁed teacher. We iterate overall teachers to calculate the ﬁnal 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 deﬁned below. Generate a random timetable. Create a thread for each mating process. Wait till mating complete. Mutate children. Calculate the ﬁtness value (fConﬂict) of each child. Collect the new population from the old one having the best ﬁtness function. Iterate over each population element. Check if the ﬁtness value (fConﬂict) is above the threshold. If yes, iterate through each conﬂict and assign a period that best ﬁt the teacher’s preferences. Calculate the ﬁtness 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 ﬁnally 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 ﬂow 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 ﬁeld 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 oﬃcial website http://www.asctimetables.com [3] Prime Table oﬃcial 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 ﬁnal project for Introduction to Artiﬁcial 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:** |