Evolving construction heuristics for curriculum university course timetabling

A novel hybrid swarm based approach for curriculum based course timetabling problem Neighborhood Search for a Real-World Curriculum-Based University Timetabling
Dr.HenryJohnson Profile Pic
Published Date:04-12-2017
Your Website URL(Optional)
Abstract Timetabling is an active area of research and used in a wide range of applications. As the development of most of these applications is on its way towards automation, the need for automated timetabling increases. Despite many years of research and development of auto- mated approaches, solving NP-hard problems such as timetabling problems remains a challenge. Metaheuristic-based approaches to these problems are constantly being refined and further de- veloped as the complexity of these applications increases. But despite the increase in complexity, the time it takes for these algorithms to solve these problems is constantly being challenged. While this thesis covers the fundamentals in metaheuristic approaches to the problem of timetabling, its main focus is to compare how two known metaheuristic algorithms, Tabu Search and Simulated Annealing, perform across different scales of resources that are to be scheduled. To attempt fairness, similar implementations of these two algorithms were made in order to eliminate systematic biases. For each set of resources the algorithms solves a timetabling prob- lem under a limited amount of time and computational capacity. The collective quality of all the produced timetables were compared. The results show that Simulated Annealing perform slightly better in the majority of the instances but with little margin for the collective quality of all tables. Despite trying to set a common ground for the these similar metaheuristic approaches, the underlying difficulties in comparing algorithms are discussed. 11 Introduction Automated resource planning has a wide range of applications in areas such as universities, high schools, sports, employment, hospitals etc. Anywhere where there is a need for order and structure in both aspects of time and space, a desire for a well-thought planning is most relevant. More resources have to be spent if the planning fails to execute at the right time and place than the cost of planning itself. This is why having a reliable and accurate planning is desired. While the essence of planning has been somewhat static over time, the areas in which this planning is needed have become more complex. But with an increasing computation power of today’s computer and the development of sophisticated algorithms, one can hope that this complexity can be handled in a reasonable way. While resource planning is used in a wide range of applications, the purpose of planning can be many. For instance, hospitals is in need for resource planning when scheduling the resources of human workflow, both for employees but also for the flow of patients. Resource planning is also used within companies when constructing a timetable for employers and their working schedule. And having an automated planning system could help to handle salaries of each em- ployee since the system keeps track of how many hours each employer works. For universities a timetable for all students has to be created at least once every year. While this is still man- ually done in many universities, ways of trying to automate this work has long been an active subject 1. Over the past decades there have been a large interest in applying metaheuristic algorithms to university timetabling 2. Metaheuristic approaches are in their nature general- purpose algorithms which can be applied to problems which have a great deal of variation such as timetabling. Timetabling problems can be regarded as high-dimensional, non-Euclidean, multiconstraint combinatorial optimization problems 3. But despite of knowing what types of categories these problems fall into, they still lack a formal definition. This is because it is difficult to have a general formulation that suits all cases. Institutions have their own definition of the problem depending on the area of investigation and the nature of the problem. This makes the field of resource planning hard to systematically develop further 4. But it should not be retained from evaluating and comparing metaheuristics to gain a better understanding of how algorithms that solve these problems perform under various conditions and restrictions. Efforts in standardizing timetable problems through International Timetabling Competitions (ITC) confirms that there is an awareness in the community for such needs 4. The aim for these competitions has been to create a common ground for comparing algorithms on standardized benchmarking tests. Formulating problems which covers the fundamentals in timetabling has been one way of setting a common ground in this area. Benchmarking results which compare metaheuristic approaches shows which algorithm perform well in specific tests, but not always in varying circumstances. Projects aiming to focus on comparing and analyzing performances in varying conditions such as Metaheuristic Network (MN) has put efforts in creating a common ground for comparisons 5. Analyzing metaheuristics under these conditions and exposing them to different environments rather than to static standardized tests only might help to understand the key factors of when and why some algorithms perform better than others. 52 Background In essence, timetabling problems consists of assigning a number of events, each having their own features, to a limited number of resources subject to certain constraints 6. The solution strongly depends on these constraints since they define the outlines of the problem. Verifying that a timetable indeed solves the problem requires one to understand how the constraints reflects upon the involving resources. Different constraints give rise to different conclusions regarding which approach to the problem is the best one. This is why making comparisons between solutions regarding efficiency and accuracy for problems with different constraints may give different results if the problems are defined on equal terms. 2.1 Curriculum-based course timetabling Timetabling within universities can be divided into two categories depending on the course en- rollment system. In some universities students are obligated to pick their own courses and in others universities there are curriculums which have predetermined courses that the students enroll. The two different systems is characterized as Course-Based Timetabling (CTT) and Curriculum-Based Course Timetabling (CB-CTT) respectively. Despite the enrollment system, there is a great need for automated timetabling systems in both cases 1. While some uni- versities already have automation in their work, there is still a need for manual aid in order to construct a high quality table. The main problems with automated systems is that they must be able to generate high-quality timetables despite the huge variation in constraints and resources that schedulers use to construct a table 7. They must be easy to use and include all functions needed to generate high-quality timetables. Since each university have their own constraints to satisfy, that may vary over time, and different resources to schedule, both commercial packages and self-developed automated systems often fail to provide all the required functions to have a fully automated timetabling system. 2.2 Timetabling at the Royal Institute of Technology The Royal Institute of Technology (KTH) falls under the category of CB-CTT. A timetable is created for each semester and is based on the courses each curriculum offer their students. Typically there are twenty possible events each week for a curriculum to schedule their classes, two before noon and two after, each being 2 hours long and having fixed starting hours. The classes start at 8 am, 10 am, 1 pm and 3 pm. Some classes such as laboratories require more than 2 hours but still start at the same fixed starting hours. The courses that are scheduled after 5 pm are considered evening courses and is often outside the portfolio of the mandatory courses offered by curriculums. Each course mainly consists of theoretical lectures and practical classes. Occasionally some courses have laboratories, tests or seminaries. These special events usually bring about addi- tional constraints since they require that the students has been taught the material beforehand. Therefore they cannot be scheduled as any other event and has to be handled with caution. The rooms in which the classes are held in varies depending on the type of class. Bigger halls that have the capacity to fit all students for a given course is used for theoretical classes. 6Professor give theoretical lectures and because his or her time is valued and they are a limited resource to universities, theoretical classes are never divided into smaller groups. On the other hand, practical classes are usually divided into smaller groups and require more classrooms for each class. Here students from a higher academic year often acts as teachers and give the practical classes. Two timetables are constructed each year, one for each semester. A large set of courses which is acquired through a database is used as a foundation to the upcoming timetable. Addi- tional information for each course may be found in this database which often has to be handled manually. Information such as different types examination modules, requests and preferences from the lecturer and in general how the structure of the course is thought to be given. These requests vary a lot from course to course and is one of the reasons why scheduling at KTH with a fully automated timetabling system is still not yet in use 7. Bigger universities often have a more complex scheduling system since more instances are involved and hence making it more challenging. But despite the size of universities, there are some features and constraints that almost always are present in timetabling problems. 2.3 Constraints Constraints can be divided into two parts, hard constraints and soft constraints. If a hard con- straint is violated, the timetable cannot be accepted as a feasible solution. This is because the constraints are usually physically impossible to ignore and must therefore be highly prioritized. The soft constraints are less forbidding and will therefore be less prioritized but ideally you want to violate as few constraints as possible in order to find the best possible solution. Soft constraints usually arise as preferences from different resources that are to be scheduled. Soft constraints may be defined in such a way that they work against each other. One has to then specify which constraint impacts the quality of the timetable more and optimize the timetable in that regard. 2.4 Metaheuristic algorithms Metaheuristic algorithms may be applied to a wide variety of problems since they are not prob- lem specific. Their successful comes from the fact they cleverly generate solutions to prob- lems that are often hard to solve for exact solutions. They combine heuristic methods aiming to efficiently and effectively explore the solution space of a problem. The solution space for timetabling problems consists of the set of all possible combinations one can make in order to construct a table. The shape of the solution space depends on an objective function which has to be defined for each problem. This function determines the quality of the tables and affects how metaheuristics explore the solution space. The generation of new solutions is done either by exploring the solutions space locally or constructing a solution from scratch by adding components until a complete table is generated. These ways of finding solutions are referred as local search and constructive methods respec- tively. Some local search methods starts to explore the solution space from an initial solution which is often generated randomly or in a greedy way. Algorithms which uses this approach are classified as trajectory based. While these approaches may quickly generate approximate 7solutions, accuracy is traded for speed. But since methods of finding exact solutions are hard to construct due to the complexity of the problem, metaheuristics are often a good first approach to these problems. Intensification and diversification are two terms often used in the fields of metaheuristics. Intensification is often referred to as the ability to avoid getting trapped in confined areas in the solution space. And diversification is referred as the ability to explore new areas and quickly identify regions of the solution space which bring about high quality solutions. While both aspects are vital to these algorithms, they may sometimes work against each other 8. It is therefore of importance to find a balance between them to achieve optimal performance. 2.5 State of the art There are many approaches to the problem of timetabling and methods has been hybridized to optimize the solution method of specific timetabling problems. New approaches to metaheuris- tic algorithms has in recent time been developed to specific timetabling problems and shown promising results. Generic algorithms which has its inspiration from Darwinian evolution has been a hot topic to researches in the field of timetabling. These algorithms represent the timetable in a long en- coded string just as DNA encoding. Mutations are done on these strings in the form of operators to find better timetables. These operators come in a variety of forms and has long been studied to optimize specific problems. These operators bring diversity into the generation of new solution and has increased the adaptiveness in many applications. Today they successfully timetables courses at the University of Edinburgh, the Harvard Business School, Kingston University and several other institutions 1. Although metaheuristic algorithms such as generic algorithms has shown to perform well in standardized benchmarking tests such as tests at ITC, other approaches has also made it to the spotlight. For problems which have many constraints that has to be handled, boolean sat- isfiability (SAT) if a preferred way of solving them. For problems where the resources can be divided into smaller groups and assigned independently from each other, a two-stage Integer Linear Programming (ILP) has shown to perform well 9. Other popular algorithms being used in today’s benchmarking tests are Memetic Algorithms, Constraint Logic Programming (CLP), Tabu Search (TS) and Simulated Annealing (SA) to name a few. 2.6 Complexity theory Timetabling has long been known to belong to the complexity class of problems called NP- hard (None-deterministic Polynomial time hard) 9. Deterministic problems (P-problems) are characterized as such; if a solution is given, one can check (in determined polynomial time) if this solution is a valid one. Also algorithms that finds these solutions are also well understood. NP-problems are characterized as being easy to check the validity of a solution if one is given, just as P-problems, but algorithms that find these solutions are hard to formulate. Finally NP- hard problems are both hard to both check the validity of a solution and finding algorithms that finds these solutions. Algorithms which is used to solve NP-hard problems has not yet been 8formulated such that a solution is found in a reasonable (polynomial) amount of time. Would such formulation be found, it could solve most NP problems since the essence of these problems can in a mathematical sense be translated into one another. The question if P-problems really are the same as NP-problems has been asked for decades and is known as the P vs. NP problem. This problem is still one of the unsolved Millennium problems. 3 Problem description Curriculum-based course timetabling problems consists of constructing a timetable by assigning classes from each course given by curriculums to specific events. While the problem at first sounds simple, many aspects has to be considered which quickly complicates the problem. The solution to timetabling problems is a timetable where every class has been assigned an event with no violations to hard constraints. A synthetic timetabling problem was approached by using two different metaheuristic al- gorithms. The algorithms that were studied were Tabu Search and Simulated Annealing. The aim of this investigation were to compare how well these algorithms solved for timetables under certain conditions. A standard setting of the resources were defined as an anchor point for the problem and parameters that both scaled up and increased the difficulty of the problem was var- ied. The algorithms solve for timetables under these varying conditions under a fixed amount of time and computational capacity. The purpose of this problem was to see how these algorithms performed at various scales and difficulties under restricted limitations. The restrictions were set to 10 minutes or 10000 iterations. These restrictions were set to see how good these algorithms solved for harder and harder problems. Many metaheuristic algorithms solve optimization problems in very different ways, which can make comparisons between them biased. TS and SA are two metaheuristics that share many similarities. For instance, they both search locally in the solution space and are both trajectory based. In this way, much of the same processes surrounding the problem were used for both algorithms to make the comparison less biased. The structure of the timetabling problem was inspired from the timetables used at KTH. But the resources used was ultimately synthetically crafted to easier manage the variations that were to be made. 4 Method 4.1 Definitions and notations Since there is no general formulation of timetabling problems, definitions and notations often vary. To make this problem self-contained, definitions and notations of the problem had to be specified. Throughout this problem the following notations and definitions were used: Timeslot -T denotes the set of all timeslots. A timeslot is a time period of two hours and each weekday contain four of them. The timeslots starts at fixed times throughout the day, beginning at 8 am, another one at 10 am, 1 pm and the last one at 3 pm. A whole week of 9school therefore consists of 20 timeslots where any class can be scheduled on. The size of this set is denoted T . Room -R denotes the set of all rooms. Each class has to take place in a room. All rooms are regarded as equally fit for any class to be scheduled in. Logistics features such as distances between rooms and maximum capacities were not considered in this problem. The size of this set is denoted R. Event -E denotes the set of all events. An event is the composition of a timeslot and a room. The size of this set is therefore T R. Every class are to be scheduled to one element in this set. Curriculum -C denotes the set of all curriculums. Each curriculum has a total of 4 courses 1 and 2 teachers, responsible for 2 courses each. The size of this set is denoted C . 1 Course -C denotes the set of all courses. Each course consists of classes which are to be 2 scheduled at different timeslots. Each course has one assigned teacher. Since parameters that scale the problem were to be varied, the number of classes for each course were set to vary with it to keep the workload for each curriculum constant throughout each week. The size of this set is denoted C . 2 Class -C denotes the set of all classes. Each class has a duration of two hours, matching a 3 timeslot exactly. Classes come in two different types; theoretical classes and practical classes. There is no difference in the way these classes are taught, but used as a feature for this set. The size of this set is C . 3 Teacher -P denotes the set of all teachers. Each teacher is responsible for 2 courses which belong to the same curriculum. Teachers may have other matters to attend and therefore have timeslots which they cannot give classes on. The size of this set is denoted P. Quantities measuring the ratio of different parameters of this problem was defined to get a better overview of the structure of the timetable being scheduled. Ratios such as Attendance level r - The attendance level is a measure of how many classes any given curricu- lum is supposed to give each week. To balance the workload for all students each week, r is simply defined as the number of classes each week per curriculum. Unavailability level s - The unavailability level is a measure of how often each teacher is unavailable. This ratio was simply defined as the amount of unavailable timeslots per week per teacher. Event compactness W - The event compactness of a timetable was defined as the ratio between scheduled and unscheduled events. Since every class was to be scheduled, the ratio could be defined asW= C =E. 3 Unavailability compactness z - The unavailability compactness is similar tos but normalized with the number of timeslots each week. The ratio was defined asz =s=20. z = 0 means teachers are always available andz = 1 means they can never teach class. 10Class compactness h - The class compactness is similar tor but normalized with the number of timeslots each week. The ratio was defined as h =r=20. h = 0 means there are no classes for any student. h = 1 means students have no empty timeslot throughout the timetable. 4.2 Quality of timetables In order to say something about the quality of the timetables that these algorithms construct, one has to specify what a good and bad timetable means. Assuming tables do not violate any of the hard constraints, the table with the lowest cost is the one regarded as the most feasible solution. For this task a cost function was used to determine the quality of each table. The cost function considered all constraints and evaluated how many constraints were violated for a given table. Since violating different constraints have different impacts on the quality of the table, cost parameters,l , were associated to constraint c to differentiate their impact. A higher c cost parameter would contribute with a higher cost if violated and thus favoring this timetable less. The cost function was defined as C(x)= l L (x) (1) c c å c where L (x) is the total number of violations against constraint c and l is the corresponding c c weight of that constraint. The output of the cost function was thus a weighted linear sum of the cost from each constraint and used as a measure of quality. This way of defining the objective function for timetabling problems is one of the more common approaches 2. While the relation between the cost parameters for both hard and soft constraints affects the construction of the timetable, little efforts ware spent to tune these parameters. Higher costs were set to the hard constraints so that these constraints would be prioritized more often than the soft constraints which were given low costs. 4.2.1 Hard constraints A solution was regarded as feasible if there were no violations towards any of the hard con- straints. This is the reason for a high cost parameter for each hard constraint. The hard con- straints used in this timetabling problem were the following: H1: Classes of the same curriculum cannot be scheduled at different rooms at the same times- lot. Violation to this constraint would give the table a cost ofl = 100 for each class that H1 were scheduled on the same timeslot. H2: Two classes of the same type, of the same course, cannot occur more than once each day. Time for the students to prepare for new material is needed and is the reason for this constraint. Each class that violated this constraint would contribute to the cost with l = 75. H2 11H3: Each teacher has unavailable timeslots where classes cannot be given. Each scheduled class which violated this constraint would contribute with a cost ofl = 100. H3 H4: Obey the maximum amount of classes of each type per week for each course. This con- straint considered the students workload and evened out the load over the whole week uniformly. Violation of this constraint contributed with a cost ofl = 100. H4 H5: All classes must be scheduled at a distinct time and room. This constraint was automat- ically met since the initiation process of an each table made sure that all classes were scheduled somewhere in the table. H6: Two classes cannot be scheduled to the same room at the same timeslot. This constraint was automatically met since each room at any timeslot could only have one class sched- uled at a time because of the implementation of the problem. 4.2.2 Soft constraints The soft constraints are the ones that should be violated first if any. Ideally a solution should not violate any constraint but these solutions are often impossible to construct and violations will therefore occur. The soft constraints used in this timetabling problem were the following: S1: Minimize consecutive classes of the same type for each course. Theoretical and practical classes should be taught at the same phase. For each pair of classes that violated this constraint, a cost ofl = 2 was added to the cost function. S1 S2: For each course of the same type, prefer to schedule for the same room. Students often prefer to have classes of the same type in the same room. The number of different rooms used for a course of the same type of class were used as the value of the cost. This constraint therefore had a weight of onlyl = 1. S2 S3: For each teacher, minimize consecutive classes in any given day. Since each teacher has more than one course, this could happen and lecturing for long hours is tiring. For each consecutive class scheduled, a cost ofl = 2 was added to the cost function. S3 S4: For each curriculum, even out the classes throughout the week over morning- and evening timeslots. Classes starting at 8 am and 3 pm contributed equally much in the opposite direction. The same was done for classes given at 10 am and 1 pm. The difference in the number of classes of these two time periods contributed to the cost function. Classes at 10 am and 1 pm contributed withl = and classes scheduled at 8 am and 3 pm contributed S4 with 2l . S4 4.3 Tabu Search Tabu Search (TS) is a local search metaheuristic algorithm that utilizes a list called the tabu list which contains previously visited tables. When exploring the solution space, the list is used to make sure that already visited tables are not revisited repeatedly. This is the diversification 12feature of the algorithm since it prevents the algorithm from being stuck in the same area in the solution space. The length of the tabu list may vary depending on the implementation. Common dependencies are the cost of the current timetable or the number of iterations performed, but sometimes it has no dependency at all 6.The length of the list will determine how soon the algorithm may cross an old path later on. Since the size of the list affects the algorithm (con- sider the limiting cases such as no length and infinite length), an optimal size can be determined depending on the problem 12. Determination of an optimal length of the list was left outside the scope of this report and set to a maximum length of 100. A pseudo code of the algorithm is shown below. Algorithm 1: Pseudo code of Tabu Search 01 xBest Initial table 02 tabuList null 03 04 while (not stop condition met) 05 06 x0 null 07 for (x in NeighborhoodsOf(xBest)) 08 if ( x not in tabuList and costFunction(x) costFunciton(x0) ) 09 x0 x 10 end 11 end 12 13 14 if (costFunction(x0) costFunction(xBest)) 15 xBest x0 16 end 17 18 put x0 in tabuList 19 if (size of tabuList allowed size) 20 remove first element in tabuList 21 end 22 23 end 24 return xBest 4.4 Simulated Annealing Simulated annealing (SA) has a thermodynamic analogy where feasible solutions are regarded as states of a system. The system in this case is a piece of imperfect material often thought of as a composite metal. The goal is to reduce the defects in this material by minimizing the internal energy. This is done by heating it up, and overcoming potential barriers in the microscopic structure and then cooling it down to find lower, more stable energy states. This process is controlled by the temperature of the system and repeated until desired property of the metal is reached. Energy in this analogy is the cost of a state and a state is a scheduled timetable. The analogy to the heating process is when the algorithm may accept worse solutions when exploring the solution space. This is the diversification feature of SA and can be seen on line 11 of the pseudo code of Simulated Annealing below. 13Algorithm 2: Pseudo code of Simulated Annealing 01 xBest Initial table 02 iterations 0 03 while (not stop condition met) 04 05 T Temperature(iterations) 06 bestCandidate null 07 for (x in NeighborhoodsOf(xBest)) 08 if (costFunction(x) costFunction(xBest)) 09 xBext = x 10 else 11 if (A(x, xBest, T) RandomInteger from 0 to 1) 12 xBext = x 13 end 14 end 15 end 16 iterations iterations + 1 17 end 18 19 return xBest 4.4.1 Acceptance function The acceptance function determines if a worse timetable should be accepted in the process of finding the best solution. This function was defined as to be dependent on the temperature and also by the cost of the tables which were considered. Other implementations vary the depen- dency, sometimes being independent of the costs of the tables considered 3. The acceptance function in this timetabling problem was defined as C(x)C(x ) DC 0 T T SA SA A(x;x ;T )= e = e : (2) 0 SA where C(x) is the cost function, x is the current solution, x is the candidate solution and T is 0 SA the temperature (see 4:4:2 an informative description of the temperature). Since (2) is only used when a worse candidate is found, the cost difference in the exponent is strictly positive, ensuring that 0 A 1. The structure of this acceptance function has its origins from statistical mechanics. (2) can be viewed as the ratio between two Boltzmann factors. These factors depend on the energy of a particular state and determines the probability that a system is found in that particular state. 4.4.2 Temperature While SA explores the solution space in a similar way as TS, it makes instead use of a parameter often referred to as the temperature, T , rather than a list. T is a parameter which decreases SA SA in value as the iterations of the algorithm increases. The temperature may also be implemented as to rapidly increase in value to at certain times or iterations, mimicking the process of cooling and reheating. The function that defines the temperature has therefore a significant impact in the efficiency of the algorithm depending on implementation 11. Much efforts in finding an optimal temperature function was not spent since it was not the intentions of this report. Instead, the temperature was defined the following way mi T (i)= T e (3) SA 0 14where T and m are constants and i is the iteration count. These constants were determined by 0 considering probabilities in accepting worse tables in situations regarding the soft constraints. Initially, the algorithm should accept worse solutions more frequently. And as the cost of the current timetable decreases, the algorithm should have a lower probability of moving away from the minimum it is approaching in the solution space. Considering an arbitrary increase in the cost between two neighboring tables regarding only soft constraints, a typical increase was observed to beDC 10. A probability of 10 % was set to be the threshold of accepting worse solutions in the beginning. Thus, calculating backwards one could compute the constant T to 0 be DC DC m0 T 0 T = T e = T 0:1= e T =  4:3 (4) SA 0 0 0 ln(0:1) The same was done form but now considering the probability of accepting worse solutions when i= i . Setting an acceptance probability of 1 %, one would get a similar result max DC DC T (i ) max SA 0:01= e T (i )= : (5) SA max ln(0:01) And by using equation (3) with i = 10000 as argument, we get max DC ln(0:01)T mi 0 5 max T (i )= T e m = ln( )6:83 10 : (6) SA max 0 i max Havingm 0 insured that the temperature decreased as the iteration count increased. 4.5 The standard setting The timetabling problem was to be solved for various conditions, it was therefore necessary to define a standard setting which would act as an anchor point. The standard setting was defined as:  240 timeslots. This corresponded to 60 days of scheduling  6 curriculums  6 available rooms  12 classes per week for each curriculum  4 unavailable timeslots per week for each teacher 15Through these values the ratios defined in section 4:1 for the standard settings could be computed as shown in the table below Ratio r s W z h Value 12 4 0:6 0:2 0:6 Table 1: Ratio quantities for the standard setting of the timetabling problem. Note that C = R= 6. This was intentional since each curriculum can only take up 1 room at 1 any given timeslot. But sinceh is less than 1.0, all 20 timeslots of a week for every curriculum will not be occupied and thus scheduling for R C was possible and preferred in an economical 1 point of view. 4.6 Variation of parameters Variations in four different parameters of this timetabling problem were made. T and R scaledE which scaled the problem in size. r ands scaled the difficulty in finding a solution. Increasing r meant more classes to handle while increasing s meant fewer possibilities to where assign classes. The parameters and their variations is presented in the table below: Parameter minimum maximum interval step T 120 360 40 R 4 8 1 r 10 20 2 s 2 6 1 Table 2: The table shows the variations in each parameter. These parameters were the num- ber of timeslots T , the number of available rooms R, the number of classes per week for each curriculumr and the number of unavailable timeslots per week for each teachers. Although the number of timeslots were varied, it was easier to represent this as variations in days. This variation corresponded to 30 days of scheduling up to 90 days with an interval step of 10 days. Also, in the upper limit when varyingr, critical ratios such asz =W= 1 were reached. These corresponded to a completely full timetable. 4.7 Initialization Because both algorithms are trajectory based, an initial timetable had to be generated. This generation were a mapping betweenC andE . It was done by randomly assigning classes to 3 events without any consideration to the hard or soft constraints. The process only made sure that every element inC had a mapping to an element inE . This made sure that constraint H5 was 3 met. 164.8 Finding neighboring timetables While there are many ways of bringing about neighboring tables, only one operation that handled the findings of these neighboring tables was implemented. By randomly picking two distinct elements inE a swap was made between their mappings toC . Two outcomes could occur. In 3 some cases one element lost its mapping to the other and in other case they would mutually swap classes. 4.9 Implementation The problem was implemented in Java and run on a PC with an Intel Core 3.10 GHz. Both algorithms were implemented and for each execution when varying parameters, relevant data were extracted. Each algorithm was set to solve for a timetable 8 times for a given instance. Stop conditions were set to i = 10000 iterations or a maximum time limit of t = 600 s. max max 5 Evaluation The first complication that were observed which can be seen in figure 1-4 were that the hard constraints were violated in almost every instance. Stop conditions in both computational ca- pacity limit and time limit were set to see if they solved the problems in a limited amount of time or iterations which they did not. Despite this, comparisons of the performance between these algorithms could still be performed. 176000 5000 5000 4000 4000 3000 3000 2000 2000 1000 1000 0 0 30 40 50 60 70 80 90 30 40 50 60 70 80 90 Days Days TS SA 700 12000 600 10000 500 8000 400 6000 300 4000 200 2000 100 0 0 30 40 50 60 70 80 90 30 40 50 60 70 80 90 Days Days Figure 1: The graphs show the mean values of different instances taken when varying the number of days. The top left graph shows the mean total cost of the timetables that were constructed for each variation. The top right graph shows the mean hard constraint costs of the timetables that were constructed. The bottom left graph shows the total time elapsed in seconds and the bottom right shows the total amount of iterations for each variation. The red horizontal line indicates the limit set in this timetabling problem. Figure 2 indicates that there were no difference with respect to the cost of the tables when varying the number of rooms. Although there were some fluctuations in the cost, it may have been because of the randomness in the process of generating solutions. Each bar represents the mean value of 8 runs which might were not enough to eliminate deviations of these kinds. 18 Total cost Time elapsed s Iterations Hard constraint costs1600 700 1400 600 1200 500 1000 400 800 300 600 200 400 100 200 0 0 4 5 6 7 8 4 5 6 7 8 Rooms Rooms TS SA 700 12000 600 10000 500 8000 400 6000 300 4000 200 2000 100 0 0 4 5 6 7 8 4 5 6 7 8 Rooms Rooms Figure 2: The graphs show the mean values of different instances taken when varying the number of available rooms. The top left graph shows the mean total cost of the timetables that were constructed for each variation. The top right graph shows the mean hard constraint costs of the timetables that were constructed. The bottom left graph shows the total time elapsed in seconds and the bottom right shows the total amount of iterations for each variation. The red horizontal line indicates the limit set in this timetabling problem. 19 Total cost Time elapsed s Iterations Hard constraint costs

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.