To see the other types of publications on this topic, follow the link: University timetabling problem.
Dissertations / Theses on the topic 'University timetabling problem'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 23 dissertations / theses for your research on the topic 'University timetabling problem.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Bucco, Guilherme Brandelli. "Construção de um modelo de programação linear para o University Timetabling Problem." reponame:Biblioteca Digital de Teses e Dissertações da UFRGS, 2014. http://hdl.handle.net/10183/101491.
Full textAbstract:
A construção de grades horárias dos cursos de uma universidade é um problema que deve ser enfrentado no início de todos os semestres e, por mobilizar quantidades significativas de recursos, se constitui numa das mais importantes tarefas administrativas de uma universidade. Trata-se de um problema clássico, combinatório, que tem atraído atenção por conta da dificuldade de se encontrar boas soluções. É classificado, em termos de complexidade computacional, como NP-hard, o que implica grande exigência de capacidade de processamento. É modelado de maneiras muito diversas, no intuito de se obter adequação quanto ao contexto educacional do país, às regras específicas da instituição ou aos objetivos específicos dos gestores, entre outros. Foi feita uma revisão de literatura no intuito de apoiar a modelagem do problema, nesse trabalho, e de contribuir com a comunidade de pesquisadores sobre o tema ao agregar informações a respeito das pesquisas publicadas até então. O problema é modelado, neste trabalho, por meio de técnicas de Pesquisa Operacional com o objetivo de produzir grades horárias com aulas distribuídas uniformemente ao longo da semana, em uma primeira etapa, para que, na etapa seguinte, ao se atribuir salas de aula às turmas, a utilização dos espaços físicos da Universidade seja otimizada. Dados foram coletados de uma instituição federal de ensino superior para a implementação do modelo. Resultados obtidos no processamento com os dados reais mostraram que o modelo reduz consideravelmente a utilização de salas de aula.The timetabling construction for University courses is a problem that must be faced at each beginning of semester and, since it mobilizes significant amounts of resources, it constitutes in one of the most important administrative tasks in a University. It's a classic, combinatorial problem that has attracted attention due to its difficulty in finding good solutions. In terms of computational complexity, it's classified as NP-hard, which involves great processing capacity. It's modeled in a number of different ways, aimed to obtain adequacy to the educational context of the country, to the specific higher education institutional rules, or to the specific managers goals, amongst others. A literature review was performed, aimed to support, in this research, the problems modeling, and to contribute to the researchers community, adding the research information published so far. The problem is modeled, in this work, by means of Operations Research techniques, aiming to produce evenly distributed timetables along the week, in the first step, and to assign the classrooms to the groups of students in the next, in such a way that the physical spaces utilization of the University is optimized. Data was collected from a federal higher education institution in order to implement de model. Results obtained through its processing with this data showed that the model considerably reduces the classrooms utilization.
2
Andersson, Isabella, and Carl Petter Svensson. "Comparing Two-Phase Hybrid Metaheuristics for the University Course Timetabling Problem (UCTP)." Thesis, KTH, Skolan för elektroteknik och datavetenskap (EECS), 2019. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-259689.
Full textAbstract:
Timetabling is a time consuming and difficult task for large organizations. One popular research field is the university course timetabling problem (UCTP). UCTP is the NP-hard combinatorial problem of scheduling courses at a university while satisfying some constraints. In most definitions of the UCTP, there are hard constraints that defines what a valid timetable is and there are soft constraints that are only desired features of the timetable. In this research, a few different hybrid methods for solving the UCTP are tested and compared. The hybrids tested are combinations of the metaheuristics simulated annealing, tabu search and iterated local search. The approach is to first use one of these methods to find a valid timetable that is not breaking any hard constraint. Then, a second phase begins that is attempting to minimize the soft constraint violations. The results showed that simulated annealing was the fastest method for removing all hard constraint violations. Given a partial solution solved by simulated annealing, iterated local search was found to minimize soft constraint violations most successfully within the time limit for all tested sizes of problem instances. It was found that this hybrid in two phases could give better solutions than only using simulated annealing.Schemaläggning är en tidskrävande och svår uppgift för stora organisationer. Schemaläggningsproblemet UCTP är ett NP-svårt kombinatoriskt problem som går ut på att, med hjälp av en dator, lägga ett schema för ett universitet. Schemat måste också följa vissa regler och begränsningar för hur ett schema får se ut. I de flesta definitionerna av UCTP-problemet så finns det en uppdelning mellan hårda och mjuka begränsningar. För att ett schema ska vara giltigt så får det inte finnas några brott mot de hårda begränsningarna. De mjuka begränsningarna däremot är bara önskvärda egenskaper för ett schema. I denna rapport har vi jämfört olika hybridmetoder av metaheuristiker för att lösa UCTP. De hybrider som undersökts är olika kombinationer av simulerad härdning, itererad lokalsökning och tabusökning. Först används en av dessa algoritmer för att hitta en halvfärdig lösning som inte bryter mot några hårda begränsningar. Denna lösning ges sedan till en andra fas där olika metaheuristiker jämförs utifrån hur bra de begränsar brotten mot de mjuka begränsningarna. Resultaten visade att simulerad härdning var snabbast för att hitta en giltig lösning till UCTP. Givet en påbörjad lösning från simulerad härdning, så lyckades itererad lokalsökning minimera brotten mot svaga begränsningar mest framgångsrikt inom tidsgränsen för alla storlekar på probleminstanser som testades. Slutsatsen blev att en hybrid i två faser kunde ge bättre lösningar än att endast använda simulerad härdning för schemaläggningsproblemet UCTP.
3
Abdul, Rahim Siti Khatijah Nor. "Transformation of the university examination timetabling problem space through data pre-processing." Thesis, University of Nottingham, 2015. http://eprints.nottingham.ac.uk/28895/.
Full textAbstract:
This research investigates Examination Timetabling or Scheduling, with the aim of producing good quality, feasible timetables that satisfy hard constraints and various soft constraints. A novel approach to scheduling, that of transformation of the problem space, has been developed and evaluated for its effectiveness. The examination scheduling problem involves many constraints due to many relationships between students and exams, making it complex and expensive in terms of time and resources. Despite the extensive research in this area, it has been observed that most of the published methods do not produce good quality timetables consistently due to the utilisation of random-search. In this research we have avoided random-search and instead have proposed a systematic, deterministic approach to solving the examination scheduling problem. We pre-process data and constraints to generate more meaningful aggregated data constructs with better expressive power that minimise the need for cross-referencing original student and exam data at a later stage. Using such aggregated data and custom-designed mechanisms, the timetable construction is done systematically, while assuring its feasibility. Later, the timetable is optimized to improve the quality, focusing on maximizing the gap between consecutive exams. Our solution is always reproducible and displays a deterministic optimization pattern on all benchmark datasets. Transformation of the problem space into new aggregated data constructs through pre-processing represents the key novel contribution of this research.
4
Lehman, Jeffrey L. "An Extensible Markup Language (XML) Application for the University Course Timetabling Problem." NSUWorks, 2004. http://nsuworks.nova.edu/gscis_etd/666.
Full textAbstract:
The university course timetabling problem involves the assignment of instructors, courses, and course sections to meeting rooms, dates, and times. Timetabling research has generally focused on the algorithms and techniques for solving specific scheduling problems. The independent evaluation and comparison of timetabling problems and solutions is limited by the lack of a standard timetabling language. This dissertation created an Extensible Markup Language (XML) application, called Course Markup Language (CourseML), for the university course timetabling problem. CourseML addressed the need for a standardized timetabling language to facilitate the efficient exchange of timetabling data and provided a means for the independent evaluation and comparison of time tabling problems and solutions. A sample real-world university course timetabling problem was defined. CourseML was used to define the sample problem. CourseML was evaluated based on how well it captured the sample problem, including hard and soft constraints, and how well it represented a solution instance. The qualities that made CourseML a candidate for general use were identified. The set of characteristics that made XML an appropriate language for specifying university course timetabling problems and solutions were identified.
5
Chammas, Kristoffer, and Simon Sirak. "An Evaluation of the Great Deluge Algorithm in Course Timetabling : As Applied to the KTH-Inspired University Course Timetabling Problem." Thesis, KTH, Skolan för elektroteknik och datavetenskap (EECS), 2019. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-259907.
Full textAbstract:
The University Course Timetabling Problem (UCTP) can be loosely described as assigning events (e.g lectures) to rooms and timeslots in a way that results in a feasible timetable that is optimal according to some custom criteria. The problem has become increasingly relevant as more programs become available in universities. Due to the complexity of UCTP, the problem is usually solved approximately using heuristics. The KTH-inspired UCTP is a variant of the UCTP that is adapted to KTH Royal Institute of Technology. However, few heuristics have been implemented for this variant of UCTP. Therefore, this study introduces an implementation of The Great Deluge heuristic to the KTH-inspired UCTP, and compares it to a state-of-the-art solver for KTH-inspired UCTP. The Great Deluge implementation was compared against the state-of-the-art KTH-inspired UCTP solver for different time limits. For each time limit, the output timetable quality was recorded over several executions. The comparison was done on two problem instances of varying complexity. The results suggest a behavior that varies over time. For larger time limits, GD produced better timetables than the state-of-the-art and the overall quality of timetables was consistent over several executions. For smaller time limits, GD produced worse timetables than the state-of-the-art and the overall quality of timetables was inconsistent over several executions. A few potential causes for the improved performance during the later stages of execution were found through further analysis of the results. Perhaps the biggest potential cause was utilizing the greedy behavior obtained during the mid to late stages of execution.”The University Course Timetabling Problem” (UCTP) handlar i grova drag om att, baserat på ett antal kriterier, schemalägga föreläsningar, övningar och laborationer på ett optimalt sätt. Problemets relevans har ökat allt eftersom universitet utökar sina programutbud. På grund av komplexiteten hos UCTP löses problemet vanligtvis approximativt med hjälp av heuristiker. ”KTH-inspired UCTP” är en KTH-anpassad variant av UCTP för vilken endast ett fåtal heuristiker har implementerats. Denna variant har exempelvis inte lösts av en vanlig heuristik inom UCTP, ”The Great Deluge” (GD). Denna studie fokuserar därför på att applicera GD på ”KTH-inspired UCTP” och jämföra denna med äldre implementationer, med fokus på den bästa tillgängliga implementationen. GD-implementationen jämförs med den bästa tillgängliga implementationen för ”KTH-inspired UCTP” för olika tidsgränser. Kvaliteten hos de resulterande schemana evalueras och sparas sedan över flera körningar. Jämförelsen gjordes på två probleminstanser av olika komplexitet. Resultatet av jämförelsen föreslår att GD producerade bättre scheman för högre tidsgränser men sämre scheman för lägre tidsgränser. Vidare analys föreslår att denna förbättring beror på utnyttjandet av det giriga beteendet som vår GD-implementation uppvisar vid senare delar av exekvering.
6
Forsberg, Mikael. "Local search hybridization of a genetic algorithm for solving the University Course Timetabling Problem." Thesis, KTH, Skolan för elektroteknik och datavetenskap (EECS), 2018. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-229677.
Full textAbstract:
The University Course Timetabling Problem (UCTP) is the problem of assigning locations (lecture halls, computer rooms) and time slots (time and date) to a set of events (lectures, labs) while satisfying a number of constraints such as avoiding double-bookings. Many variants of problem formulations exist, and most realistic variants are thought to be NP-hard. A recent trend in solving hard scheduling problems lies in the application of hybrid metaheuristics, where improvements are often found by hybridizing a population-based approach with some form of local search. In this paper, an implementation of a Genetic Algorithm (GA) that solves the UCTP is hybridized with local search in the form of Tabu Search (TS). The results show significant improvements to the performance and scalability over the non-hybridized GA. Two application strategies for the TS are investigated. The first strategy performs a switch-over from the GA to the TS, while the second interleaves the two algorithms. The effectiveness of each application strategy is seen to depend on the characteristics of the individual algorithms.Schemaläggningsproblemet UCTP (University Course Timetabling Problem) består av problemet att tilldela platser (föreläsningssalar, laborationssalar) och tidpunkter (datum och klockslag) till en mängd tillställningar (föreläsningar, laborationer) under kravet att upprätthålla en mängd restriktioner, exempelvis att undvika dubbelbokningar. Det finns många varianter av problemformuleringen och de flesta realistiska formuleringer anses ge upphov till NP-svåra optimeringsproblem. En förhållandevis ny trend för lösningsmodeller till svåra schemaläggningsproblem ligger i tillämpningen av hybrida metaheuristiker, där förbättringar ofta ses när populationsbaserade algoritmer kombineras med någon typ av lokalsökning. I denna rapport undersöks en UCTP-lösning baserad på en Genetisk Algoritm (GA) som hybridiseratsmed en lokalsökning i form av en Tabusökning (TS). Resultaten visar på signifikanta förbättringar i prestanda och skalbarhet jämfört med den icke-hybridiserade GA:n. Två appliceringsstrategier för TS undersöks. Den första strategin utgörs av att byta algoritm från GA till TS, medan den andra utgörs av att sammanfläta de två algoritmerna. Appliceringsstrategiernas effektivitet ses bero av de individuella algoritmernas egenskaper.
7
Berggren, Robert, and Timmy Nielsen. "Investigating the Reliability of Known University Course Timetabling Problem Solving Algorithms with Updated Constraints." Thesis, KTH, Skolan för elektroteknik och datavetenskap (EECS), 2018. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-229695.
Full textAbstract:
Scheduling lectures, exams, seminars etc. for a university turns out to be a harder task than what it seems to be at first glance. This problem is known as the University Course Timetabling Problem (UCTP). The UCTP has been hosted for a number of competitions throughout the years by an organization called Practice and Theory of Automated Timetabling (PATAT). Because of these competitions, the problem has been given a standard description and set of constraints as well as standard problem instances for easier comparison of research and work on the subject. However, setting a standard like this have a major drawback; no variety is introduced since new research for finding the greatest method to solve the UCTP is forced to focus on a specific set of constraints, and algorithms developed will only be optimized with these constraints in consideration. In this research we compared five well known UCTP algorithms with the standard set of constraints to a different set of constraints. The comparisons showed a difference in the rank of performance between the algorithms when some constraints were changed to fit a certain need. The differences were not great but big enough to state that previous research declaring what algorithms are best for the UCTP problem cannot be relied upon unless you use close to identical sets of constraints. If the goal is to find the best algorithm for a new set of constraints then one should not rely on a single previously defined great algorithm but instead take two or three of the top performing ones for the greatest chance of finding the most optimized solution possible.Schemaläggning av föreläsningar, tentamen, seminarier etc. för ett universitet visar sig vara en svårare uppgift än vad det verkar vid första anblicken. Detta problem är känt som University Course Timetabling Problem (UCTP). UCTP har varit centralt i ett antal tävlingar genom åren av organisationen Practice and Theory of Automated Timetabling (PATAT). På grund av dessa tävlingar har problemet fått en standardbeskrivning och en uppsättning specifika begränsningar samt standard problemdata för enklare jämförelse av forskning och arbete i ämnet. Att sätta denna typ av standard har dock en stor nackdel; ingen variation tillförs då ny forskning för att hitta den bästa optimeringsmetoden inom UCTP tvingas att fokusera på en specifik uppsättning begränsningar och algoritmer som utvecklas kommer då endast att optimeras med dessa begränsningar i beaktande. I den här rapporten jämförde vi fem välkända UCTP algoritmer med standarduppsättningen av begränsningar mot en annan uppsättning begränsningar. Jämförelserna visade en skillnad i prestationsordningen mellan algoritmerna när vissa begränsningar ändrats för att passa ett visst behov. Skillnaderna var inte enorma men tillräckligt stora för att påvisa att tidigare forskning som förklarar vilka algoritmer som är bäst för UCTP-problemet ej är pålitlig om du inte använder nära till identiska uppsättningar av begränsningar. Om målet är att hitta den bästa algoritmen för en ny uppsättning begränsningar, bör man inte lita på en tidigare definierad effektiv algoritm utan istället använda sig utav två eller tre av de starkaste algoritmerna för den största chansen att hitta den mest optimerade lösningen.
8
Fredrikson, Rasmus, and Jonas Dahl. "A comparative study between a simulated annealing and a genetic algorithm for solving a university timetabling problem." Thesis, KTH, Skolan för datavetenskap och kommunikation (CSC), 2016. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-187158.
Full textAbstract:
The university timetabling problem is an NP-complete problem which schools all over the world face every semester. The aim of the problem is to schedule sets of events such as lectures and seminars into certain time slots without violating numerous specified constraints. This study aimed to automate this process with the help of simulated annealing and compare the results with a genetic algorithm. The input data sets were inspired by the Royal Institute of Technology in Stockholm. The results showed a great run time difference between the two algorithms where the simulated annealing performed much better. They also showed that even though the simulated annealing algorithm was better during all stages, the genetic algorithm had a much better performance in early stages than it had in latter. This led to the conclusion that a more optimized, hybrid algorithm could be created from the two algorithms provided that the genetic algorithm could benefit from the improvements suggested in previous research.Universitetsschemaläggningsproblemet är ett NP-fullständigt problem som skolor över hela världen måste hantera innan varje termin. Syftet med problemet är att schemalägga händelser, såsom föreläsningar och seminarier, utan att bryta flertalet fördefinierade villkor. Denna studie hade som mål att automatisera denna process med hjälp av algoritmkonstuktionsmetoden simulerad glödgning och sedan jämföra resultatet med en genetisk algoritm. De datamängder som användes är inspirerade av den verkliga situationen på KTH. Resultaten visar stora tidsmässiga skillnader där algoritmen baserad på simulerad glödgning går snabbare. De visar dock också att den genetiska algoritmen har en bättre prestanda i tidigare stadier än i senare. Detta ledde till slutsatsen att en mer optimerad hybridalgoritm kan skapas av de två algoritmerna, förutsatt att den genetiska algoritmen kan dra nytta av förbättringar som föreslagits i tidigare forskning.
9
Wang, Yuqiang. "Models and Algorithms for Some Combinatorial Optimization Problems: University Course Timetabling, Facility Layout and Integrated Production-Distribution Scheduling." Diss., Virginia Tech, 2007. http://hdl.handle.net/10919/28757.
Full textAbstract:
In this dissertation, we address three different combinatorial optimization problems (COPs), each of which has specific real-life applications. Owning to their specific nature, these problems are different from those discussed in the literature. For each of these problems, we present a mathematical programming formulation, analyze the problem to determine its useful, inherent structural properties, and develop an efficient methodology for its solution by exploiting these properties.
The first problem that we address is the course timetabling problem encountered at Virginia Tech. The course timetabling problem for a university is a difficult problem and has been studied by many researchers over the years. As a result, a plethora of models and approaches have been reported in the literature. However, most of these studies have focused on applications pertaining to course scheduling for a single or at most few departments of a university. The sheer size of the university-wide timetabling problem that we address, involving thousands of courses to be scheduled in hundreds of classrooms in each semester, makes it a challenging problem. We employ an appropriate decomposition technique that relies on some inherent structural properties of the problem both during the modeling and algorithmic development phases. We show the superiority of the schedules generated by our methodology over those that are currently being used. Also, our methodology requires only a reasonable amount of computational time in solving this large-size problem.
A facility layout problem involving arbitrary-shaped departments is the second problem that we investigate in this dissertation. We designate this problem as the arbitrary-shaped facility layout problem (ASFLP). The ASFLP deals with arranging a given set of departments (facilities, workstations, machines) within the confines of a given floor space, in order to optimize a desired metric, which invariably relates to the material handling cost. The topic of facility planning has been addressed rather extensively in the literature. However, a major limitation of most of the work reported in the literature is that they assume the shape of a department to be a rectangle (or even a square). The approach that relies on approximating an arbitrary-shaped department by a rectangle might result in an unattractive solution. The key research questions for the ASFLP are: (1) how to accurately model the arbitrary-shaped departments, and (2) how to effectively and efficiently determine the desired layout. We present a mixed-integer programming model that maintains the arbitrary shapes of the departments. We use a meta-heuristic to solve the large-size instances of the ASFLP in a reasonable amount of time.
The third problem that we investigate is a supply chain scheduling problem. This problem involves two stages of a supply chain, specifically, a manufacturer and one or more customers. The key issue is to achieve an appropriate coordination between the production and distribution functions of the manufacturer so as to minimize the sum of the shipping and job tardiness costs. We, first, address a single customer problem, and then, extend our analysis to the case of multiple customers. For the single-customer problem, we present a polynomial-time algorithm to solve it to optimality. For the multiple-customer problem, we prove that this problem is NP-hard and solve it by appropriately decomposing it into subproblems, one of which is solvable in polynomial time. We propose a branch-and-bound-based methodology for this problem that exploits its structural properties. Results of an extensive computational experimentation are presented that show the following: (1) our algorithms are efficient to use and effective to implement; and (2) significant benefits accrue as a result of integrating the production and distribution functions.Ph. D.
10
Broberg, Felix, and Emelie Eriksson. "Comparing MAX-MIN and Rank-based Ant Colony Optimization Algorithms for solving the University Course Timetabling Problem." Thesis, KTH, Skolan för elektroteknik och datavetenskap (EECS), 2018. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-229790.
Full textAbstract:
The University Course Timetabling Problem (UCTP) is a scheduling problem regarding courses, time slots and rooms, and is often accompanied by a set of feature requirements. As non-trivial instances of the UCTP are NP-hard, traditional computational methods are ineffective. A meta-heuristic alternative is the Ant Colony Optimization (ACO) algorithm, which has previously been proven to successfully solve the UCTP. This paper investigates the relative effectiveness of the MAX-MIN ACO variation to the Rank-based ACO variation on UCTP problem sets of varying difficulty. They are also compared when using a local-search help function and a path attractiveness heuristic. This study shows that the ACO variations perform similarly well for all problem difficulties when utilizing the path attractiveness heuristic. Utilizing both local search and the heuristic produces the best results across the difficulties and ACO variations. There is, however, a need for further investigation into the parameters for both ACO variations to ensure the validity of the conclusion.Det universitetsbaserade schemaläggningsproblemet (UCTP) avser schemaläggning av kurser till rum och tider där hänsyn till en mängd funktionella krav ofta måste tas. Traditionella beräkningsmetoder har visats vara ineffektiva då icke-triviala fall av problemet är NP-svåra. Myrkolonisystemsalgoritmen (ACO) är ett meta-heuristiskt alternativ som framgångsrikt har använts för att lösa UCTP. Denna rapport jämför effektiviteten mellan MAX-MIN ACO-variationen och den Rank-baserade ACO-variationen i att hitta lösningar till UCTP. Variationerna jämförs också vid använding av "local search" och en vägvalsheuristik. Rapporten visar att ACO-variationerna presterar likvärdigt vid användande av vägvalsheuristiken. Användandet av både "local search" och vägvalsheuristiken leder till bästa resultat för samtliga svårighetsgrader och ACO-variationer. Efterforskning krävs angående parametrarna för ACO-variationerna för att säkerställa giltigheten av slutsatserna.
11
Renman, Casper, and Hampus Fristedt. "A comparative analysis of a Tabu Search and a Genetic Algorithm for solving a University Course Timetabling Problem." Thesis, KTH, Skolan för datavetenskap och kommunikation (CSC), 2015. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-166276.
Full textAbstract:
This work implements a Tabu search (TS) algorithm for solving an instance of the University Course Timetabling Problem (UCTP). The algorithm is com- pared to a Genetic algorithm (GA) implemented by Yamazaki and Pertoft (2014) that solves the same instance. The purpose of the work is to explore how the approaches dier for this particular instance, and specifically inves- tigate whether a TS algorithm alone is sucient, considering the small size of the UCTP instance. The TS was based on the OpenTS library (Harder, 2001) and reuses parts from Yamazaki and Pertoft’s (2014) GA. The results show that the TS alone is too slow. Even in a small instance of the UCTP, the search space is too big for the TS to be fast. This confirms the state of the art, that a combination of TS and GA would perform better than either of them individually. Further improvements on the TS would involve reducing the number of moves generated each iteration.
12
Salman, Alzahraa, and Rouwayd Hanna. "A Comparative Study between Genetic Algorithm, Simulated Annealing and a Hybrid Algorithm for solving a University Course Timetabling Problem." Thesis, KTH, Skolan för elektroteknik och datavetenskap (EECS), 2018. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-229432.
Full textAbstract:
Every year, universities are faced with the problem of having to schedule events to various resources such as lecturers, classrooms and time slots while considering different constraints. The University Course Timetabling Problem is a NP-complete combinatorial optimization problem that, if solved manually, requires great investment in time and money. Thus finding an algorithm that automates this process would prove beneficial for society. The aim of this thesis is to compare the performance of a Genetic Algorithm-Simulated Annealing hybrid implementation with the performance of each of the algorithms individually for solving the University Course Timetabling Problem. The data sets used were inspired by the Royal Institute of Technology in Stockholm. The results showed that Simulated Annealing performed better than the other two algorithms, with respect to time consumption. However, the hybrid algorithm showed great promise of actually producing a feasible solution before terminating as the complexity of the problem increased, for example in the biggest data set tested.Varje år står universitetet inför problemet med att planera händelser till olika resurser, såsom föreläsare, klassrum och tidsluckor, med hänsyn till flertal fördefinierade villkor. Universitetsschemaläggningsproblemet är ett NP-fullständigt kombinatoriskt optimeringsproblem som kräver mycket tid och pengar om det löses manuellt. Att hitta en algoritm som automatiserar denna process skulle därför vara till nytta för samhället. Syftet med denna avhandling är att jämföra prestandan för en Genetisk Algoritm-Simulerad Glödning hybrid implementering med prestandan för var och en av algoritmerna individuellt för att lösa Universitetsschemaläggningsproblemet. Datamängderna som används är inspirerade av Kungliga Tekniska Högskolan i Stockholm. Resultaten visade att Simulerad Glödning presterade bättre än de andra två algoritmerna, med hänsyn till tidskonsumtion. Hybrid algoritmen visade dock ett stort potential att faktiskt ta fram en acceptabel lösning, innan den terminerar, när komplexiteten av datat ökade, till exempel i det största datasetet som testades.
13
Norgren, Eric, and Johan Jonasson. "Investigating a Genetic Algorithm-Simulated Annealing Hybrid Applied to University Course Timetabling Problem : A Comparative Study Between Simulated Annealing Initialized with Genetic Algorithm, Genetic Algorithm and Simulated Annealing." Thesis, KTH, Skolan för datavetenskap och kommunikation (CSC), 2016. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-186364.
Full textAbstract:
Every semester universities around the world have to create new schedules. This task can be very complex considering that a number of constraints has to be taken into account, e.g. there should not exist any timetable clashes for students and a room cannot be double-booked. This can be very hard and time-consuming for a human to do by hand, which is why methods to automate this problem, the University Course Timetabling Problem, has been researched for many years. This report investigates the performance of a hybrid consisting of Genetic Algorithm and Simulated Annealing when solving the University Course Timetabling Problem. An implementation by Yamazaki & Pertoft (2014) was used for the Genetic Algorithm. Simulated Annealing used the Genetic Algorithm as base for its implementation. The hybrid runs the Genetic Algorithm until some breakpoint, takes the best timetable and uses it as an initial solution for the Simulated Annealing. Our results show that our implementation of Simulated Annealing performs better than the hybrid and magnitudes better than the Genetic Algorithm. We believe one reason for this is that the dataset used was too simple, the Genetic Algorithm might scale better as the complexity of the dataset increases.
14
Abdullah, Salwani. "Heuristic approaches for university timetabling problems." Thesis, University of Nottingham, 2006. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.428959.
Full text
15
Naseem, Jat Sadaf. "Genetic algorithms for university course timetabling problems." Thesis, University of Leicester, 2012. http://hdl.handle.net/2381/10997.
Full textAbstract:
The university course timetabling problem is a difficult optimisation problem due to its highly-constrained nature. Finding an optimal, or even a high quality, timetable is a challenging task, especially when resources (e.g., rooms and time slots) are limited. In the literature, many approaches have been studied to solve this problem. In this thesis, we investigate genetic algorithms to solve the problem because they have been successfully used for a wide range of real-world problems. However, for university course timetabling problems, traditional genetic algorithms are not usually considered as efficient solvers. In this thesis, we investigate genetic algorithms to acquire good solutions for university course timetabling problems. Several ideas are introduced to increase the general performance of genetic algorithms on these problems. Local search strategies are introduced into the traditional genetic algorithm to enhance its performance for the university course timetabling problem. This differs from many works in the literature because it works on time slots of the timetable rather than events directly. A guided search approach is also introduced into genetic algorithms to produce high quality individuals into the population. In the guided search technique, the best parts of selected individuals from the current population are stored in an extra memory (or data structure) and are re-used to guide the generation of new individuals for subsequent populations. In addition to solving university course timetabling problems as a single-objective optimisation problem, we also tackle the multi-objective university course timetabling problem. We integrate the above proposed approaches into multi-objective evolutionary algorithms and propose a framework of multi-objective evolutionary algorithms based on local search and guided search strategies for the multi-objective university course timetabling problem. This framework is then instantiated into a set of multi-objective evolutionary algorithms for the multi-objective university course timetabling problem based on a set of multi-objective evolutionary algorithms that are typically used for general multi-objective optimisation problems. Computational results based on a set of well-known university course timetabling benchmark instances, show the effectiveness of the proposed approaches for both single- and multi-objective university course timetabling problems.
16
Farivar, Saeid. "An algorithm-independent platform to solve university timetabling problems." Thesis, California State University, Long Beach, 2013. http://pqdtopen.proquest.com/#viewpdf?dispub=1522628.
Full textAbstract:
Finding optimal solutions for large scale university timetabling problems that satisfy all operational needs and rules in an academic institution, while at the same time fulfill as many of the wishes and requirements of the lecturers and the students as possible, is an important but extremely difficult task for the staff involved. Hence, automating this entire process seems to be inevitable. As timetabling problems are in general NP-complete, several heuristic algorithms have been proposed and applied to solve the problem in the literature. But prior to implementation, it is not clear which would perform better for any specific timetabling problem. This triggers the need for developing an algorithm independent platform that could interface with all solver engines. The main objectives of this work are the following: i) Providing an algorithm-independent tool that can be used to define the resources needed to create and modify an academic schedule, ii) Automatically generate schedules that better fit the needs of both lecturers and students, and iii) Reduce the labor cost involved in the university timetabling problem process.
17
Arbaoui, Taha. "Modeling and solving university timetabling." Thesis, Compiègne, 2014. http://www.theses.fr/2014COMP2167/document.
Full textAbstract:
Cette thèse s’intéresse aux problèmes d’emploi du temps d’universités. Ces problèmes sont rencontrés chaque année par les utilisateurs. Nous proposons des bornes inférieures, des méthodes heuristiques et des modèles de programmation mixte en nombres entiers et de programmation par contraintes. Nous traitons le problème d’emploi du temps d’examens et celui d’affectation des étudiants. Nous proposons de nouvelles méthodes et formulations et les comparons aux approches existantes. Nous proposons, pour le problème d’emploi du temps d’examens, une amélioration d’un modèle mathématique en nombres entiers qui permettra d’obtenir des solutions optimales. Ensuite, des bornes inférieures, une formulation plus compacte des contraintes et un modèle de programmation par contraintes sont proposés. Pour le problème d’emploi du temps d’examens à l’Université de Technologie de Compiègne, nous proposons une approche mémétique. Enfin, nous présentons un modèle mathématique pour le problème d’affectation des étudiants et nous étudions sa performance sur un ensemble d’instances réellesThis thesis investigates university timetabling problems. These problems occur across universities and are faced each year by the practitioners. We propose new lower bounds, heuristic approaches, mixed integer and constraint programming models to solve them. We address the exam timetabling and the student scheduling problem. We investigate new methods and formulations and compare them to the existing approaches. For exam timetabling, we propose an improvement to an existing mixed integer programming model that makes it possible to obtain optimal solutions. Next, lower bounds, a more compact reformulation for constraints and a constraint programming model are proposed. For the exam timetabling problem at Université de Technologie de Compiègne, we designed a memetic approach. Finally, we present a new formulation for the student scheduling problem and investigate its performance on a set of real-world instances
18
Fealko, Daniel R. "Evaluating Particle Swarm Intelligence Techniques for Solving University Examination Timetabling Problems." NSUWorks, 2005. http://nsuworks.nova.edu/gscis_etd/513.
Full textAbstract:
The purpose of this thesis is to investigate the suitability and effectiveness of the Particle Swarm Optimization (PSO) technique when applied to the University Examination Timetabling problem. We accomplished this by analyzing experimentally the performance profile-the quality of the solution as a function of the execution time-of the standard form of the PSO algorithm when brought to bear against the University Examination Timetabling problem. This study systematically investigated the impact of problem and algorithm factors in solving this particular timetabling problem and determined the algorithm's performance profile under the specified test environment. Keys factors studied included problem size (i.e., number of enrollments), conflict matrix density, and swarm size. Testing used both real world and fabricated data sets of varying size and conflict densities. This research also provides insight into how well the PSO algorithm performs compared with other algorithms used to attack the same problem and data sets. Knowing the algorithm's strengths and limitations is useful in determining its utility, ability, and limitations in attacking timetabling problems in general and the University Examination Timetabling problem in pal1icular. Finally, two additional contributions were made during the course of this research: a better way to fabricate examination timetabling data sets and the introduction of the PSO-No Conflicts optimization approach. Our new data set fabrication method produced data sets that were more representative of real world examination timetabling data sets and permitted us to construct data sets spanning a wide range of sizes and densities.· The newly derived PSO-No Conflicts algorithm permitted the PSO algorithm to perform searches while still satisfying constraints.
19
Almay, Felix, and Oskar Strömberg. "Applicability of Constraint Solving and Simulated Annealing to Real-World Scale University Course Timetabling Problems." Thesis, KTH, Skolan för elektroteknik och datavetenskap (EECS), 2019. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-259761.
Full textAbstract:
The university course timetabling problem is the problem of creating a schedule for university courses under certain constraints. The decision variant of this optimisation problem is NP-complete. We have researched this problem and implemented the heuristic simulated annealing. This implementation has been compared with respect to time to the constraint solver CPSolver, based on iterative forward search. Our results show that CPSolver scales better for large problem instances. Simulated annealing as implemented by us is thus not suitable in itself for generating valid solutions to this problem on a real-world scale.Universitetsschemaläggningsproblemet går ut på att skapa ett schema för universitetskurser under vissa villkor. Beslutsversionen av detta optimeringsproblem är NP-fullständig. Vi har undersökt problemet och implementerat heuristiken simulerad härdning. Denna har jämförts med avseende på tid med villkorsprogrammeringslösaren CPSolver, som är baserad på iterativ framåtsökning. Våra resultat visar att CPSolver skalar bättre för stora probleminstanser. Simulerad härdning som implementerad av oss är därför inte i sig lämplig för att generera giltiga lösningar till verklighetstrogna probleminstanser.
20
Weng, De-rung, and 翁得榮. "University Timetabling Problem." Thesis, 2007. http://ndltd.ncl.edu.tw/handle/82477892784612792696.
Full textAbstract:
碩士國立高雄第一科技大學
運籌管理所
95
University timetabling problem considers various resource constraints on course scheduling at universities. It is a combinatorial problem by nature and belongs to the class of NP-Complete problems. In this study, we consider two types of constraints: hard and soft. Most hard constraints are regulations imposed by the school’s administration. These constraints cannot be violated under any circumstances. On the other hand, soft constraints, such as teachers’ or students’ schedule preferences, are more flexible and can be violated if necessary. However, the timetable maker should try to satisfy as many soft constraints as possible. The inclusion of soft constraints further complicates the already difficult timetabling problem. In this study, we developed an integer programming model for the university timetabling problem and tested it using real course scheduling data collected from the Department of Logistics Management at the National Kaohsiung First University of Science and Technology. The data was first entered into a Microsoft Access database, and then solved by AMPL/CPLEX codes we developed. Computational study indicates that our approach is very efficient and effective compared with the manual process in current practice.
21
Hahn-Goldberg, Shoshana. "Defining, modeling, and solving a real university course timetabling problem." 2007. http://link.library.utoronto.ca/eir/EIRdetail.cfm?Resources__ID=452884&T=F.
Full text
22
Jang, Shr Yu, and 張士宇. "Genetic Algorithm on the optimization framework of Timetabling problem for University." Thesis, 2009. http://ndltd.ncl.edu.tw/handle/43vup3.
Full textAbstract:
碩士國立臺北科技大學
土木與防災研究所
97
ABSTRACT Title：Genetic Algorithm on the optimization framework of Pages：100 Timetabling problem for University School：National Taipei University of Technology Time：July, 2009 Degree：Master Researcher：Shr Yu, Jang Advisor：Yu-Chi, Sung Keywords：Genetic Algorithms、School Timetabling Course scheduling is a complicated problem for University which makes administrative personnel feels puzzled in every term. This problem is limited by resource allocation, also belonging to the NP-Complete problem, there are such restrictions on resources as course, teacher, classroom, class, etc.Using administrative personnel to solve course scheduling problem in traditional method does not only waste time but also consume strength and can not satisfy all the teacher’s requires entirely, and need to coordination with the teachers. The thesis solves timetabling problem with Genetic Algorithm method, and set teacher''s school timetable as the chromosome gene to satisfy the teacher’s requirement and arrange classroom assigning problem, making the single course have a class in different classrooms to increase the option of course scheduling. This work constructs with C# and combines the database, it helps the users revise and maintain the data conveniently.
23
Hsiao, Jung-Ting, and 蕭榮亭. "A Study of Applying Multi-Agent System to the University Timetabling Problem." Thesis, 2005. http://ndltd.ncl.edu.tw/handle/80275717596582695325.
Full textAbstract:
碩士中原大學
資訊管理研究所
93
For each universities and colleges in Taiwan, the issue of constructing a semester-long timetabling of courses is not only one arduous task but also a taxing and thankless job. In addition to the reason that it is a complicated problem universities and colleges face each semester, how to produce a conflict-free semester-long timetabling of courses which matches with great majority teachers’ expectations will be one greater challenge. Based on the fundamental techniques of many-agent system (Multi-Agent System), this study aims to utilize the mechanism of Dutch auction in doing business trade on things, intending to solve teacher's satisfaction problems of timetabling of courses by exchanging each other’s time periods through the teachers. This study makes a comparison between the two types of offering order which are the “weak first” and “randomly arranging”. Besides, another Altruistic type of agent is added which is different from others and is able to be known on the premise of contributing to promoting all interests and losing its own personal interests. It is found that the teacher's satisfaction can be effective promoted after utilizing the Multi-Agent System auction mechanism and the result could be more effective if Altruistic type of agent is incorporated. However, there is no significant difference whether the auction bidder, auctioneer or both is Altruistic type of agent. Also, whether in auctioning is arranged randomly will not influence the result.