Dissertations / Theses on the topic 'Timetabling'
To see the other types of publications on this topic, follow the link: Timetabling.
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Timetabling.'
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
Weare, Rupert. "Automated examination timetabling." Thesis, University of Nottingham, 1995. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.282578.
Full text
2
Ismail, Zuhaimy H. "Aspects of computerised timetabling." Thesis, Loughborough University, 1994. https://dspace.lboro.ac.uk/2134/13825.
Full textAbstract:
This research considers the problem of constructing high school timetables using a computer. In the majority of high schools, termly or yearly timetables are still being produced manually. Constructing a timetable is a hard and time consuming task which is carried out repeatedly thus a computer program for assisting with this problem would be of great value. This study is in three parts. First. an overall analysis of the problem is undertaken to provide background knowledge and to identify basic principles in the construction of a school timetable. The characteristics of timetabling problems are identified and the necessary data for the construction of a timetable is identified. The first part ends with the production of a heuristic model for generating an initial solution that satisfies all the hard constraints embodied in the curriculum requirements. The second stage of the research is devoted to designing a heuristic model for solving a timetable problem with hard and medium constraints. These include constraints like the various numbers of common periods, double periods and reducing the repeated allocation of a subject within any day. The approaches taken are based on two recently developed techniques, namely tabu search and simulated annealing. Both of these are used and comparisons of their efficiency are provided. The comparison is based on the percentage fulfilment of the hard and medium requirements. The third part is devoted to one of the most difficult areas in timetable construction, that is the softer requirements which are specific to particular schools and whose satisfaction is not seen as essential. This section describes the development of an expert system based on heuristic production rules to satisfy a range of soft requirements. The soft requirements are studied and recorded as rules and a heuristic solution is produced for each of the general requirements. Different levels of rule are developed, from which the best possible solution to a particular timetable problem is expertly produced. Finally, possible extensions of the proposed method and its application to other types of the timetabling problem are discussed.
3
Hellkvist, Henning, and William Sjöstedt. "Toward Automated Timetabling at TekNat." Thesis, Uppsala universitet, Institutionen för informationsteknologi, 2012. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-169531.
Full textAbstract:
This is a report on our approach to use constraint programming to automatically solve the Uppsala University timetabling problem at the Faculty of Science and Technology (TekNat). The project has been successful as the program produced can quickly solve the problem of assigning courses to specific times and rooms. The task of scheduling the entire TekNat problem at once is in most cases unsuccessful, but the problem can be split up over multiple departments, each scheduled one by one. Scheduling an instance of roughly 40 courses whichis the size of the IT department takes less than a minute while solving data resembling the entire TekNat instance of about 200 courses takes about 5 minutes if successful. However, the model has only hard constraints and may disregard solutions that would be acceptable when reviewed by human scheduling officers. Therefore the program will not work in all problem instances, and no solution is ever guaranteed.The report contains a brief introduction on constraint programming in general as well as amore detailed overview of the specific parts we have utilized of the constraint programming library we choose to use for this task; Gecode. Furthermore we will present a fully functional prototype for a user interface we designed during the project that can benefit both teachers and schedulers alike. We present the mechanics of our program and discuss its advantages and drawbacks as well as outlining what areas a continuation of this project should focus on.
4
Murugan, Anandaraj Soundarya Raja. "University Timetabling using Genetic Algorithm." Thesis, Högskolan Dalarna, Datateknik, 2009. http://urn.kb.se/resolve?urn=urn:nbn:se:du-3792.
Full textAbstract:
The field of automated timetabling and scheduling meeting all the requirementsthat we call constraints is always difficult task and already proved as NPComplete. The idea behind my research is to implement Genetic Algorithm ongeneral scheduling problem under predefined constraints and check the validityof results, and then I will explain the possible usage of other approaches likeexpert systems, direct heuristics, network flows, simulated annealing and someother approaches. It is observed that Genetic Algorithm is good solutiontechnique for solving such problems. The program written in C++ and analysisis done with using various tools explained in details later.
5
Pendlebury, J. "A computer-aided timetabling system." Thesis, Lancaster University, 1989. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.277233.
Full text
6
Abdul, Rahman Syariza. "Search methodologies for examination timetabling." Thesis, University of Nottingham, 2012. http://eprints.nottingham.ac.uk/12709/.
Full textAbstract:
Working with examination timetabling is an extremely challenging task due to the difficulty of finding good quality solutions. Most of the studies in this area rely on improvement techniques to enhance the solution quality after generating an initial solution. Nevertheless, the initial solution generation itself can provide good solution quality even though the ordering strategies often using graph colouring heuristics, are typically quite simple. Indeed, there are examples where some of the produced solutions are better than the ones produced in the literature with an improvement phase. This research concentrates on constructive approaches which are based on squeaky wheel optimisation i.e. the focus is upon finding difficult examinations in their assignment and changing their position in a heuristic ordering. In the first phase, the work is focused on the squeaky wheel optimisation approach where the ordering is permutated in a block of examinations in order to find the best ordering. Heuristics are alternated during the search as each heuristic produces a different value of a heuristic modifier. This strategy could improve the solution quality when a stochastic process is incorporated. Motivated by this first phase, a squeaky wheel optimisation concept is then combined with graph colouring heuristics in a linear form with weights aggregation. The aim is to generalise the constructive approach using information from given heuristics for finding difficult examinations and it works well across tested problems. Each parameter is invoked with a normalisation strategy in order to generalise the specific problem data. In the next phase, the information obtained from the process of building an infeasible timetable is used. The examinations that caused infeasibility are given attention because, logically, they are hard to place in the timetable and so they are treated first. In the adaptive decomposition strategy, the aim is to automatically divide examinations into difficult and easy sets so as to give attention to difficult examinations. Within the easy set, a subset called the boundary set is used to accommodate shuffling strategies to change the given ordering of examinations. Consequently, the graph colouring heuristics are employed on those constructive approaches and it is shown that dynamic ordering is an effective way to permute the ordering. The next research chapter concentrates on the improvement approach where variable neighbourhood search with great deluge algorithm is investigated using various neighbourhood orderings and initialisation strategies. The approach incorporated with a repair mechanism in order to amend some of infeasible assignment and at the same time aiming to improve the solution quality.
7
Newall, James P. "Hybrid methods for automated timetabling." Thesis, University of Nottingham, 1999. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.285687.
Full text
8
Lindberg, Viktor. "Evaluation of School Timetabling Algorithms." Thesis, Umeå universitet, Institutionen för datavetenskap, 2016. http://urn.kb.se/resolve?urn=urn:nbn:se:umu:diva-128602.
Full textAbstract:
Most schools have the problem that they need to organise the meetings between students and teachers in lectures and place these lectures in a timetable. Four different algorithms that can be used to solve this problem will be evaluated in this thesis. The algorithms are Simulated Annealing, Particle Swarm Optimisation, Hyper-Heuristic Genetic Algorithm and Iterated Local Search. In this thesis a description of the algorithms will be given and then evaluated by running them on a set of different known timetabling problems and have their results compared with each other to find out which algorithm is best suited for use in a potential end-user application. Simulated Annealing combined with Iterated Local Search gave the best resultsin this thesis.
9
Jeřábková, Eva. "Timetabling - příprava rozvrhu pro školu." Master's thesis, Vysoká škola ekonomická v Praze, 2014. http://www.nusl.cz/ntk/nusl-198439.
Full textAbstract:
The aim of the thesis is to create a model of timetable for primary school for all teachers and classes so that the timetable is in compliance with all teaching plans, the conditions of the Ministry of Education, Youth and Sports (general education program), the school's needs and requirements of teachers. The timetable is created for a particular school, ZŠ nám. Svobody in Prague. The first part of the thesis is focused on the theoretical description of methods and procedures for dealing with the problem of timetable. The second part describes the elementary school, for which the timetable is made, it's classes, teachers and conditions of the tuition. It is also formulated and described a mathematical model of the problem that is solved by using the program Lingo.
10
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
11
Lewis, Rhydian M. R. "Metaheuristics for university course timetabling." Thesis, Edinburgh Napier University, 2006. http://researchrepository.napier.ac.uk/Output/2392.
Full textAbstract:
The work presented in this thesis concerns the problem of timetabling at universities – particularly course-timetabling, and examines the various ways in which metaheuristic techniques might be applied to these sorts of problems. Using a popular benchmark version of a university course timetabling problem, we examine the implications of using a “twostaged” algorithmic approach, whereby in stage-one only the mandatory constraints are considered for satisfaction, with stage-two then being concerned with satisfying the remaining constraints but without re-breaking any of the mandatory constraints in the process. Consequently, algorithms for each stage of this approach are proposed and analysed in detail. For the first stage we examine the applicability of the so-called Grouping Genetic Algorithm (GGA). In our analysis of this algorithm we discover a number of scaling-up issues surrounding the general GGA approach and discuss various reasons as to why this is so. Two separate ways of enhancing general performance are also explored. Secondly, an Iterated Heuristic Search algorithm is also proposed for the same problem, and in experiments it is shown to outperform the GGA in almost all cases. Similar observations to these are also witnessed in a second set of experiments, where the analogous problem of colouring equipartite graphs is also considered. Two new metaheuristic algorithms are also proposed for the second stage of the twostaged approach: an evolutionary algorithm (with a number of new specialised evolutionary operators), and a simulated annealing-based approach. Detailed analyses of both algorithms are presented and reasons for their relative benefits and drawbacks are discussed. Finally, suggestions are also made as to how our best performing algorithms might be modified in order to deal with further “real-world” constraints. In our analyses of these modified algorithms, as well as witnessing promising behaviour in some cases, we are also able to highlight some of the limitations of the two-stage approach in certain cases.
12
Placì, Simone. "Modelli per il Train Timetabling Problem." Master's thesis, Alma Mater Studiorum - Università di Bologna, 2019.
Find full textAbstract:
Il treno è uno dei principali mezzi di trasporto grazie al quale ogni giorno si spostano miliardi di persone. É fondamentale quindi che gli orari dei treni siano organizzati nel miglior modo possibile, aumentando la soddisfazione dei viaggiatori. In questa tesi, dopo aver analizzato il problema del Train Timetabling Problem, è stato sviluppato un modello matematico di Programmazione Lineare Intera per trovare la schedulazione ottima dei treni in una rete ferroviaria utilizzando dati reali che ci sono stati forniti dalle ferrovie olandesi (NS, Netherlands Railways).
13
Marte, Michael. "Models and Algorithms for School Timetabling." Diss., lmu, 2002. http://nbn-resolving.de/urn:nbn:de:bvb:19-9369.
Full text
14
Layfield, Colin J. "Investigations into the master timetabling problem." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1998. http://www.collectionscanada.ca/obj/s4/f2/dsk2/ftp01/MQ34973.pdf.
Full text
15
Autry, Brian M. "University course timetabling with probability collectives." Thesis, Monterey, Calif. : Naval Postgraduate School, 2008. http://bosun.nps.edu/uhtbin/hyperion-image.exe/08Mar%5FAutry.pdf.
Full textAbstract:
Thesis (M.S. in Computer Science)--Naval Postgraduate School, March 2008.Thesis Advisor(s): Squire, Kevin. "March 2008." Description based on title screen as viewed on April 24, 2008. Includes bibliographical references (p. 33-35). Also available in print.
16
Cartlidge, Christopher James. "Automated scheduling for timetabling of coursework /." Leeds : University of Leeds, School of Computer Studies, 2008. http://www.comp.leeds.ac.uk/fyproj/reports/0708/Cartlidge.pdf.
Full text
17
Koshich, P. A. "University course timetabling of meta-heuristics." Thesis, University of Oxford, 2006. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.433470.
Full text
18
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
19
Fang, Hsiao-Lan. "Genetic algorithms in timetabling and scheduling." Thesis, University of Edinburgh, 1995. http://hdl.handle.net/1842/30185.
Full textAbstract:
This thesis investigates the use of genetic algorithms (GAs) for solving a range of timetabling and scheduling problems. Such problems are very hard in general, and GAs offer a useful and successful alternative to existing techniques. A framework is presented for GAs to solve modular timetabling problems in educational institutions. The approach involves three components: declaring problem-specific constraints, constructing a problem-specific evaluation function and using a problem-independent GA to attempt to solve the problem. Successful results are demonstrated and a general analysis of the reliability and robustness of the approach is conducted. The basic approach can readily handle a wide variety of general timetabling problem constraints, and is therefore likely to be of great practical usefulness (indeed, an earlier version is already in use). The approach relies for its success on the use of specially designed mutation operators which greatly improve upon the performance of a GA with standard operators. A framework for GAs in job-shop and open-shop scheduling is also presented. One of the key aspects of this approach is the use of specially designed representations for such scheduling problems. The representations implicitly encode a schedule by encoding instructions for a schedule builder. The general robustness of this approach is demonstrated with respect to experiments on a range of widely-used benchmark problems involving many different schedule quality criteria. When compared against a variety of common heuristic search approaches, the GA approach is clearly the most successful method overall. An extension to the representation, in which choices of heuristic for the schedule builder are also incorporated in the chromosome, is found to lead to new best results on the makespan for some well known benchmark open-shop scheduling problems. The general approach is also shown to be readily extendable to rescheduling and dynamic scheduling.
20
Bradley, Matthew John. "Ultra-efficient Bus Rapid Transit timetabling." Thesis, Curtin University, 2010. http://hdl.handle.net/20.500.11937/75.
Full textAbstract:
Bus Rapid Transit (BRT) systems are increasingly used, particularly in the developing world, to provide low-cost, high-capacity urban mobility. An example of this trend is Bogotá’s TransMilenio BRT system, the test site for this thesis, which uses an homogeneous fleet of 18 metre long articulated buses to service 1,450,000 passenger trips per day, and which reaches a peak passenger load level of 45,000 passengers per hour per direction. The computational tools and techniques used to plan the timetables of such BRT systems are largely the same set of tools and techniques used to plan non-BRT transit systems.Unlike other transit systems, high-load BRT systems commonly run simultaneous express services, a situation that the tools developed to timetable non-BRT transit systems were not specifically designed for. Due to the running of simultaneous express services, the timetabling of highload BRT systems becomes a combinatorial problem, a far more complex class of problem than normal non-combinatorial timetabling. The thesis is advanced here that high-load BRT systems could be timetabled far more efficiently via a software tool built around a recognition of the problem’s combinatorial nature.This thesis is tested by building such a software tool, using that tool to develop an alternative timetable for the Américas Line of the TransMilenio BRT system, and then comparing that timetable’s performance to the performance of the existing timetable. Data used for the Américas Line was from the period Monday the 23rd to Friday the 27th of May 2005. The software tool developed to process this data changes express service stopping patterns as quickly as passenger load changes, leading to a great many express patterns over the course of a one day timetable. Due to this rapid tracking of passenger load, the resulting timetable is referred to as an “ultra-efficient timetable.”The ultra-efficient timetable produced for the Américas Line has 88 unique stopping patterns, compared to the existing timetable’s three, and is shown to be tracking passenger load far more precisely. Bus fleet size under the ultra-efficient timetable is 9% lower than for the existing timetable, indicating an estimated capital cost saving for the Américas Line of US$1.8 million. Bus kilometres travelled under the ultra-efficient timetable are 40% lower than for the existing timetable, indicating an estimated annual operating cost saving for the Américas Line of US$6 million.The ultra-efficient timetable delivering these performance improvements is shown to be approximately ten times more complex than could be reasonably deployed using paper timetables. Consequently, an ultra-efficient timetable would need to be deployed in conjunction with a fully-automated passenger information system. With this caveat, the thesis that high-load BRT systems can be far more efficiently timetabled using a combinatorial software tool is confirmed here. As an alternative to deploying ultra-efficient timetables, the combinatorial timetabling technology developed for this thesis could also be used to produce more efficient versions of normal paper-based BRT timetables.
21
Aizam, Nur Aidya Hanum. "Effective computational models for timetabling problem." Thesis, Curtin University, 2013. http://hdl.handle.net/20.500.11937/827.
Full textAbstract:
Timetabling is a table of information showing when certain events are scheduled to take place. Timetabling is in fact very essential in making sure that all events occur in the time and place required. It is critical in areas such as: education, production and manufacturing, sport competitions, transport and logistics. The difficulty in timetabling is satisfying all the restrictions and requirements. The restrictions relate to resources such as time and location as well as conflicts. The requirements relate to the preferences of customers and service providers. The problem is further complicated by the desire to optimize an objective function that usually relates to the cost or effectiveness of the schedule. The task of how to construct a high quality timetable which satisfies all requirements is definitely not an easy one. A further difficulty is the dynamic aspect of timetabling and the need to accommodate changes after the schedule has been announced. Our focus in this study is on university timetabling problems.Mathematically, the problem is to optimize an objective function that reflects the value of the schedule subject to a set of constraints that relate to various operational requirements and a range of resource constraints (lecturers, rooms, etc). The usual objective is to maximize the total preferences or to minimize the number of students affected by clashes. The problem can be conveniently expressed as an Integer Programming (IP) problem. The computational difficulty is due to the integer restrictions on the variables. Various computational models including both heuristics and exact methods have been proposed.The timetabling problem in universities courses has existed for a long time, but due to the complexity and its variation, many researchers are still trying to decipher the solution for this problem. Numerous methods have been developed over the years and most of them have been successful. However, according to McCollum (2006) based on the international review of Operational Research in the UK (Commissioned by the Engineering and Physical Sciences Research Council), a gap still exists between the theory and practice of timetabling. Additionally, Burke and Petrovic (2002) also mentioned that many methods that have succeeded in solving this problem are applicable to specific institutions where they are designed. Nevertheless, Benli and Botsali (2004) explained that there is no generalized model for this problem because of the variation present in each university. Moreover, the limited availability of facilities and growth of flexibility of the student’s choices of courses makes the problem even tighter.This thesis in whole outlines studies which gain a step in a pathway to develop a more general IP model for university course timetabling problem. We incorporate all important features of this problem which includes the hard constraints and the desirable soft constraints. AIMMS 3.11 mathematical software is employed as a tool to solve the models with CPLEX 12.1 as the solver.In the first study (Chapter 3), we aim to develop models for timetabling problems which are flexible in terms of the ability to be applied in various institutions. To achieve this, we gather the information obtained on features that are used in other studies, which is covered in the literature review (Chapter 2) of this thesis. From the information on the gathered features, we observed that some features are compulsory, being that they are always used in models to solve timetabling problems. These features therefore form a basic model of university course timetabling problem in this study. We then develop an extended model by incorporating additional features found from the literature. The extended model also contains a few more additional features which we generate that are significant to be included in a model for solving this problem.Different combinations of the features which form the extended model are extracted to produce a range of models. These models are useful to be used by any institutions which require some relevant features to solve their timetabling problem. These models are tested with a small randomly generated test problem. In the following chapter (Chapter 4), we apply the developed model into 3 case studies obtained from the literature. The objective of this is to test the efficiency of the developed models for application to larger problems. Appropriate variation models are used to solve each of the case studies. This application testing is further extended by including a number of additional features. This is to illustrate that the developed model is able to be applied in institutions even ivwhen changes of requirements occur. Results from these tests demonstrate successful outcomes from application of our developed models to the chosen case studies.In Chapter 5, we tested the application of the developed models application in a case study using a pre-assignment approach as a simplification in solving timetabling problem. In this approach, the core units are determined and prioritized to be assigned into prime time slots at the very beginning of the scheduling process. It then follows with the assignment of the remainder units subject to the university requirements. One case study which is applied in Chapter 4 is used for the purpose of testing the pre-assignment approach. From this testing, we show that the pre-assignment is a useful simplification tool in solving timetabling problem of the chosen case study using the developed model, especially in reducing the computational time. We believe that this approach can be applied in other case studies using the developed model.As an overview of the thesis, we believe that the developed models will be applicable to other problems apart from the ones tested.
22
Hederra, Francisco J. "Timetabling courses at the Naval Postgraduate School." Thesis, Monterey, Calif. : Springfield, Va. : Naval Postgraduate School ; Available from National Technical Information Service, 1994. http://handle.dtic.mil/100.2/ADA288398.
Full text
23
Ranson, David John. "Interactive Visualisations to Improve Exam Timetabling Systems." Thesis, University of Sussex, 2008. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.487898.
Full textAbstract:
This work explores the use of Interactive Visualisations to solve Exam Timetabling problems by making use of new graphical representations and interactions. Exam Timetabling is a. well researched topic in optimisation, however existing automated solutions are limited in terms of interactivity and generality. In cognitive science relevant literature shows how different representations can affect the outcome of problem solving tasks yet existing timetabling systems and research focus almost exclusively on automated approaches. not making use of available human abilities. These shortcomings of current approaches are addressed. raising the questions: Can effective representations be used to completely solve Exam Timetabling problems without use of computer automation and can such representations be effectively integrated with existing approaches? Previous research suggests that closely mapped expressive representations can be effective problem solving tools. In this research representational design methodologies were applied to develop two systems capable ofsolving complete problems. rather thanjust improving existing solutions. VAST (Visual Analysis and Scheduling for Tl1Detabling) provides interactive visualisations to solve Exam Timetabling Problems and introduces novel Cluster Group visualisations to simplify the problem faced by users. KNIGHT (Knowledge Interactive Guided Heuristic Timetabling) extends these interactive visualisations to include human in the loop interactivity integrated with existing automated heuristics. The application of mobilities to the domain of Exam Timeta~ling allow heuristic searches to be guided toward new solutions, expanding potential search neighbourhoods whilst excluding solutions that are perceived to be problematic. An evaluation of KNIGHT is presented which discusses this approach. The evaluation of VAST provides positive evidence for the use of interactive visualisation as an integral part of the problem solving process and our analysis shows the discovery of different user strategies that make use of these new interactions and representations. Whilst the use of exam clusters appears beneficial no significant benefits were found from allowing initial exam assignments.
24
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.
25
Tannahill, Samuel Coulter. "The school timetabling problem : a new formulation." Thesis, University of Strathclyde, 1993. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.250706.
Full text
26
DANTAS, VITOR CAVALCANTI. "ALGORITHMS FOR POST ENROLLMENT-BASED COURSE TIMETABLING." PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO, 2009. http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=13807@1.
Full textAbstract:
PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIROCOORDENAÇÃO DE APERFEIÇOAMENTO DO PESSOAL DE ENSINO SUPERIOR
Problemas de Programação de Horários (PPHs) tem sido amplamente estudados, dada a sua importância prática e teórica. A maioria das variações do problema pertence µa classe NP-Difícil. Em geral, trata-se da alocação de recursos materiais e humanos no espaço e no tempo, visando a otimização de um conjunto de objetivos definidos. Na Programação de Horários de Cursos Universitários, por exemplo, o objetivo pode ser a satisfação do corpo docente e o desempenho acadêmico dos alunos. Nos últimos anos, as formulações de PPHs propostas pela International Timetabling Competition (ITC) tem sido bastante utilizadas, sendo notável a predominância de métodos baseados em busca local e metaeurísticas entre as abordagens propostas recentemente. Este trabalho tem como objetivo propor algoritmos para o Problema de Programação de Horários Pós-Matrícula da ITC, focando principalmente em métodos heurísticos baseados em Programação Matemática. Entre os modelos de Programação Linear Inteira Mista que propomos para este problema, destaca-se o modelo baseado na Formulação de Representantes Assimétricos para o Problema de Coloração de Grafos. Abordamos a aplicação da heurística de Local Branching e propomos um esquema de resolução por Geração de Colunas, como forma de viabilizar o tratamento dos modelos propostos, uma vez que a complexidade de tais modelos representa um desafio para os resolvedores de Programação Linear Inteira Mista atualmente disponíveis.
Timetabling Problems have been widely studied, given its practical and theorical relevance. Most of its variations belong to the NP-Hard class of problems. In general, it is about allocation of material and human resources in time and space, aiming to optimize some set of defined objetives. In University Course Timetabling, for example, the objective might be the satisfaction of professors and the academic performance of students. In the last years, the formulations for timetabling problems proposed by the In- ternational Timetabling Competition (ITC) have been widely adopted. The predominance of meta-heuristics and local search-based methods is remark- able among the recently proposed approaches. The objetive of this thesis is to propose algorithms for the Post Enrolment-based Course Timetabling Problem of the ITC, focusing on Mathematical Programming-based heuris- tic methods. Among the Mixed Integer Linear Programming models that we propose for this problem, we highlight the one based on the Asymetric Representatives Formulation for the Graph Coloring Problem. We explore the application of the Local Branching heuristic and we propose a Column Generation solution procedure, as an attempt to handle the proposed models, given that the complexity of such models poses a challenge for currently available Mixed Integer Linear Programming solvers.
27
Qu, Rong. "Case-based reasoning for course timetabling problems." Thesis, University of Nottingham, 2002. http://eprints.nottingham.ac.uk/10020/.
Full textAbstract:
The research in this thesis investigates Case-Based Reasoning (CBR), a Knowledge-Based Reasoning technique that proved to be capable of providing good solutions in educational course timetabling problems. Following the basic idea behind CBR, experiences in solving previous similar timetabling problems are employed to find the solutions for new problems. A basic CBR system that is hierarchically organized with structured knowledge representations by attribute graphs is proposed in Chapter Four. The system is then further improved to solve a wider range of problems, which is described in Chapter Five. Evaluations on a large number of experiments indicate that this approach could provide a significant step forward in timetabling and scheduling research. This basic system works well on relatively small problems. To deal with this drawback a multiple-retrieval approach that partitions large timetabling problems into small solvable sub-problems is presented in Chapter Six. Good results are obtained from a wide range of experiments. In Chapter Seven, a new idea is introduced in CBR for solving timetabling problems by investigating the approach to select the most appropriate heuristic method rather than to employ it directly on the problem, in the attempt to raise the level of generality at which we can operate. All the evidence obtained from the first stage experiments indicates that there is a range of promising future directions. Finally in Chapter Eight the results of the work are evaluated and some directions for future work are present.
28
Joubert, Guillaume. "Periodic train timetabling with mesoscopic tracks assignment." Electronic Thesis or Diss., Compiègne, 2023. http://www.theses.fr/2023COMP2775.
Full textAbstract:
En qualité de Gestionnaire de l’Infrastructure ferroviaire nationale, SNCF Réseau a notamment pour mission de répartir annuellement les capacités de cette infrastructure, soit produire un ensemble d’intervalles de temps de réservation sur les voies pour permettre la circulation sécurisée de trains répondant à une demande des Autorités Organisatrices de Transports (AOT) : on parle d’ordonnancement de sillons. Ce projet de thèse s’inscrit dans une démarche d’aide à la décision pour les chargés d’études horaires produisant des sillons, dans un contexte où les demandes des AOT et l’état de l’infrastructure ferroviaire peuvent varier d’une année sur l’autre. Nous nous intéressons à une phase dite de structuration de la capacité, où le problème est de savoir si à partir d’une demande de sillons et d’une infrastructure connues, il existe un ordonnancement périodique répondant à cette demande de sillons et respectant les contraintes liées à l’exploitation ferroviaire. Nous proposons deux méthodes pour résoudre ce problème. La première méthode se base sur un modèle en Programmation Linéaire en Nombres Entiers inspiré de la littérature et que nous avons décomposé afin de faciliter sa résolution. La grille horaire est ainsi décidée en premier lieu, suivie de l’affectation des voies. Une fonction d’évaluation de conflits entre sillons sans utilisation de connaissance explicite sur l’affectation des voies permet d’effectuer le choix de la grille horaire tel qu’une affectation de voies est possible par la suite. Afin de résoudre des instances difficiles, nous proposons une heuristique constructive et une recherche tabou pour résoudre les conflits plus efficacement. La deuxième méthode s’appuie sur un modèle en Programmation Par Contraintes avec lequel nous optimisons les temps de retournement des rames stationnées en gares terminus. Nous avons développé des algorithmes de filtrage afin d’améliorer les algorithmes de maintien de consistance d’arc pour les contraintes de précédence et les contraintes disjonctives du problème, ayant toutes la particularité d’être périodiques. Nous proposons des bornes inférieures basées sur la contribution minimale de sous-ensembles de sillons à la fonction objective afin d’améliorer la preuve d’optimalité des solutions. Enfin, nous présentons des stratégies de branchement et une procédure de Branch-and-Check pour améliorer les performances de résolution. Ces approches sont testées sur différentes instances du problème, basées sur deux infrastructures fictives ainsi que sur l’Etoile de Savoie centrée autour de la gare de Chambéry - Challes-les-EauxAs the French railway Infrastructure Manager, SNCF Réseau produces train timetables on a yearly basis, by deciding a set of time intervals on tracks to allow safe trains circulation that fulfils a mobility demand from the Transport Organisation Authority (TOA): this is a periodic slot scheduling task. This PhD project aims at providing a decision-aid tool to the timetable planners, in a context where the mobility demand expressed by the TOA and the infrastructure state change from a year to another. We focus on a production phase said capacity structuring, where the problem is to decide whether from a known slots demand and infrastructure state, there is a periodic scheduling fulfilling this slots demand and satisfying the safety constraints arising from rail operations. We propose two methods to solve this problem. The first method is based on an Integer Linear Programming model inspired from the literature and that we decomposed to ease the solution search. The timetable determination is then made before the tracks assignment. A conflict evaluation function that does not require explicit tracks assignment knowledge is used to obtain conflict-free timetables for which a tracks assignment is reachable. In order to solve challenging instances, we propose a constructive heuristic and a tabu search framework to resolve conflicts moreefficiently. The second method relies on a Constraint Programming model that we use to optimise the turnover time of rolling stock at terminus stations. We developed filtering algorithms to improve algorithms that maintain the arc-consistency of precedence and disjunctive constraints of the problem, all having a periodic aspect. We propose lower bounds based on the minimal cost contribution of slots subsets to the objective function in order to improve the optimality proof of the solutions. Finally, we present branching strategies and a Branch-and-Check procedure to improve the resolution performance.These approaches are tested on different instances of the problem, based on two fictive infrastructures as well as on the Savoie area centred around Chambéry - Challes-les-Eaux station
29
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.
30
Aldogan, Deniz. "Memetic Algorithms For Timetabling Problems In Private Schools." Master's thesis, METU, 2005. http://etd.lib.metu.edu.tr/upload/3/12606218/index.pdf.
Full textAbstract:
The aim of this study is to introduce a real-world timetabling problem that exists in some private schools in Turkey and to solve such problem instances utilizing memetic algorithms.
Being a new type of problem and for privacy reasons, there is no real data available. Hence for benchmarking purposes, a random data generator has been implemented. Memetic algorithms (MAs) combining genetic algorithms and hill-climbing are applied to solve synthetic problem instances produced by this generator.
Different types of recombination and mutation operators based on the hierarchical structure of the timetabling problem are proposed. A modified version of the violation directed hierarchical hill-climbing method (VDHC), introduced by A. Alkan and E. Ozcan, coordinates the process of 12 different low-level hill-climbing operators grouped in two distinct arrangements that attempt to resolve corresponding constraint violations. VDHC is an adaptive method advocating cooperation of hill-climbing operators. In addition, MAs with VDHC are compared with different versions of multimeme algorithms and pure genetic algorithms.
Experimental results on synthetic benchmark data set indicate the success of the proposed MA.
31
Kraft, Christine R. "Planning, scheduling, and timetabling in a university setting." Connect to this title online, 2007. http://etd.lib.clemson.edu/documents/1193079304/.
Full text
32
Zhang, Lixi. "Solving the timetabling problem using constraint satisfaction programming." Access electronically, 2005. http://www.library.uow.edu.au/adt-NWU/public/adt-NWU20051104.155838/index.html.
Full text
33
Zibran, Minhaz Fahim, and University of Lethbridge Faculty of Arts and Science. "A multi-phase approach to university course timetabling." Thesis, Lethbridge, Alta. : University of Lethbridge, Faculty of Arts and Science, 2007, 2007. http://hdl.handle.net/10133/633.
Full textAbstract:
Course timetabling is a well known constraint satisfaction optimization (CSOP) problem,
which needs to be solved in educational institutions regularly. Unfortunately, this course
timetabling problem is known to be NP-complete [7, 39].
This M.Sc. thesis presents a multi-phase approach to solve the university level course
timetabling problem. We decompose the problem into several sub-problems with reduced
complexity, which are solved in separate phases. In phase-1a we assign lectures to professors,
phase-1b assigns labs and tutorials to academic assistances and graduate assistants.
Phase-2 assigns each lecture to one of the two day-sequences (Monday-Wednesday-Friday
or Tuesday-Thursday). In Phase-3, lectures of each single day-sequence are then assigned
to time-slots. Finally, in phase-4, labs and tutorials are assigned to days and time-slots.
This decomposition allows the use of different techniques as appropriate to solve different
phases. Currently different phases are solved using constraint programming and integer
linear programming. The multi-phase architecture with the graphical user interface allows
users to customize constraints as well as to generate new solutions that may incorporate
partial solutions from previously generated feasible solutions.ix, 117 leaves ; 29 cm
34
Mohmad, Kahar Mohd Nizam. "Heuristic approaches for real world examination timetabling problems." Thesis, University of Nottingham, 2013. http://eprints.nottingham.ac.uk/27677/.
Full textAbstract:
The examination timetabling (exam-timeslot-room assignment) problem involves assigning exams to a specific or limited number of timeslots and rooms, with the aim of satisfying the hard constraints and the soft constraints as much as possible. Most of the techniques reported in the literature have been applied to solve simplified examination benchmark datasets, available within the scientific literature. In this research we bridge the gap between research and practice by investigating a problem taken from the Universiti Malaysia Pahang (UMP), a real world capacitated examination timetabling problem. This dataset has several novel constraints, in addition to those commonly used in the literature. Additionally, the invigilator scheduling problem (invigilator assignment) was also investigated as it has not received the same level of research attention as the examination scheduling (although it is just as important to educational institutions). The formal models are defined, and constructive heuristics was developed for both problems in which the overall problems are solved with a two-phase approach which involves scheduling the exam to timeslot and room, and follows with scheduling the invigilator. During the invigilator assignment, we assume that there is already an examination timetable in place (i.e. previously generated). It reveals that the invigilator scheduling solution dependent on the number of rooms selected from the exam-timeslot-room assignment phase (i.e. a lesser number of used rooms would minimises the invigilation duties for staff), this encourages us to further improve the exam-timeslot-room timetable solution. An improvement on the result was carried out using modified extended great deluge algorithm (modified-GDA) and multi-neighbourhood GDA approach (that use more than one neighbourhood during the search). The modified-GDA uses a simple to understand parameter and allows the boundary that acts as the acceptance level, to dynamically change during the search. The propose approaches able to produce good quality solution when compared to the solutions from the proprietary software used by UMP. In addition, our solutions adhere to all hard constraints which the current systems fail to do. Finally, we extend our research onto investigating the Second International Timetabling Competition (ITC2007) dataset as it also contains numerous constraints much similar to UMP datasets. Our propose approach able to produce competitive solutions when compared to the solutions produced by other reported works in the literature.
35
Yang, Yong. "Solving examination timetabling problems by case based reasoning." Thesis, University of Nottingham, 2004. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.416893.
Full text
36
Saviniec, Landir. "Models and algorithms for high school timetabling problems." Universidade de São Paulo, 2017. http://www.teses.usp.br/teses/disponiveis/55/55134/tde-05022018-112623/.
Full textAbstract:
High school timetabling problems consist in assigning meetings between classes and teachers, with the goal of minimizing the violation of specific soft requisites. This category of problems has been extensively studied since the 1950s, mostly via mixed-integer programming and metaheuristic techniques. However, the computation of optimal or near-optimal solutions using mixed-integer programs or metaheuristics is still a challenge for most practical problems. In this thesis, we investigate new mixed-integer programming formulations, column generation approaches and parallel metaheuristic based algorithms to compute lower bounds and solutions for high school timetabling problems. Extensive computational experiments conducted with real-world instances demonstrate that our best formulations are competitive with best-known formulations, while our parallel algorithms present superior performance than the state-of-the-art methods.Problemas de horários escolares consistem em alocar encontros entre turmas e professores, com objetivo de minimizar violações a requisitos qualitativos específicos. Esta categoria de problemas tem sido largamente estudada desde 1950, particularmente via técnicas de programação linear inteira mista e metaheurísticas. Entretanto, a computação de soluções ótimas ou quase ótimas usando programas inteiro-mistos ou metaheurísticas ainda é um desafio na maioria dos problemas práticos. Nesta tese, nós investigamos novas formulações inteiro-mistas, decomposições por geração de colunas e algoritmos baseados em metaheurísticas paralelas para computar limitantes inferiores e soluções para problemas de horários escolares. Extensivos experimentos computacionais conduzidos com instâncias reais demonstram que nossas melhores formulações são competitivas com as melhores formulações existentes, enquanto nossos algoritmos paralelos são superiores em performance computacional quando comparados com métodos que são estado-da-arte.
37
Muklason, Ahmad. "Hyper-heuristics and fairness in examination timetabling problems." Thesis, University of Nottingham, 2017. http://eprints.nottingham.ac.uk/42912/.
Full textAbstract:
Examination timetabling is a challenging optimisation problem in operations research and artificial intelligence. The main aim is to spread exams evenly throughout the overall time period to facilitate student comfort and success; however, existing examination timetabling solvers neglect fairness by optimising the sum or average of the objective function value without considering its distribution among students or other stakeholders. The balance between quality of the overall timetable and fairness (global fairness and within a cohort) is a major concern, thus the latter is added as a new objective function and quality indicator of examination timetables. The objective function is also considered from the perspectives of multiple stakeholders of examination timetabling (i.e. students, invigilators, markers and estates), as opposed to viewing the objective function as an aggregate function. These notions make the problem become a multi-objective optimisation problem. We study sum of power rather than linear summation to enforce fairness and concurrently minimise the objective function, using some perturbation-based hyper- heuristics approaches to optimise the standard objective function. Secondly, multi-stage approach is studied (generating initial feasible solution, improving the standard quality of solution and then improving fairness), to improve the fairness objective function. Given that the standard objective function and fairness objective function conflict, we then studied several multi-objective algorithms employed within the framework of hyper-heuristics. The proposed hyper-heuristic algorithms mainly can be divided into two approaches: classical scalarisation technique-based weighted sum and Tchebyce↵; and population-based non-dominated sorting memetic algorithm II (NSMA-II) and artificial bee colony and strength pareto evolutionary 2 (SPEA2) hybrid (ABC-SPEA2). The experiments were conducted over two multi-objective examination timetabling problem formulations (i.e. with fairness and with multiple stakeholder perspectives), tested over problem instances from four different datasets: Carter, Nottingham, Yeditepe and ITC 2007. The experimental results over multi-objective examination timetabling problem with fairness showed that in terms of the standard objective function the proposed approach could produce results comparable with the best known solutions reported in the literature, whilst in the same time could be forced to be fairer that does or does not compensate on worsening the standard objective function. Fairness within a cohort could be improved much better than global fairness and treating as multi-objective problem could help the search for near-optimal standard objective function escape from local optima trap. The scalarisation technique based hyper-heuristics outperforms the population-based hyper-heuristic. The advantage of treating examination timetabling problem as multi-objective problem is that approximations of the Pareto optimal solutions give the optimal trade-o↵ between standard objective function, fairness among all students, and fairness within a cohort. In addition, the decision maker also can view the solution from multiple stakeholders view. We believe that by giving this more detailed information, the decision maker of examination timetable could make better decisions.
38
Srinivasan, Subhashini. "Modeling the Homeschool timetabling problem using Integer programming." VCU Scholars Compass, 2011. http://scholarscompass.vcu.edu/etd/2555.
Full textAbstract:
Home schooling has steadily been increasing in the past decade. According to a survey in 2007, about 2.5 million children were being home schooled in the US. Typically, parents provide education at the convenience of their home and in some cases an instructor is appointed for the same. The Home School Timetabling problem (HSTP) deals with assigning subjects, timeslots and rooms to every student. In doing so, there are certain hard and specialty constraints that are to be satisfied. Integer programming (IP) has been used in solving the HSTP as it has the advantage of being able to provide information about the relative significance of each constraint with respect to the objective. A prototype in the form of a GUI has been built such that the parent can enter each student’s name, his/her subjects, duration, days and time for each subject, availability times of the parent etc. This data is then fed into the IP model so that it can generate a feasible timetable satisfying all of the constraints. When a solution is found it is formatted to provide the weekly timetable for each student, individually, as well as a complete timetable for all students each day.
39
Silva, Jose, Noel Varela, Jesus Varas, Omar Lezama, José Maco, and Martín Villón. "Comparison of bioinspired algorithms applied to the timetabling problem." Springer Science and Business Media Deutschland GmbH, 2021. http://hdl.handle.net/10757/654075.
Full textAbstract:
The problem of timetabling events is present in various organizations such as schools, hospitals, transportation centers. The purpose of timetabling activities at a university is to ensure that all students attend their required subjects in accordance with the available resources. The set of constraints that must be considered in the design of timetables involves students, teachers and infrastructure. This study shows that acceptable solutions are generated through the application of genetic, memetic and immune system algorithms for the problem of timetabling. The algorithms are applied to real instances of the University of Mumbai in India and their results are comparable with those of a human expert.Revisión por pares
40
Chohan, Ossam. "University Scheduling using Genetic Algorithm." Thesis, Högskolan Dalarna, Datateknik, 2009. http://urn.kb.se/resolve?urn=urn:nbn:se:du-3791.
Full textAbstract:
The automated timetabling and scheduling is one of the hardest problem areas. This isbecause of constraints and satisfying those constraints to get the feasible and optimizedschedule, and it is already proved as an NP Complete (1) [1]. The basic idea behind this studyis to investigate the performance of Genetic Algorithm on general scheduling problem underpredefined constraints and check the validity of results, and then having comparative analysiswith other available approaches like Tabu search, simulated annealing, direct and indirectheuristics [2] and expert system. It is observed that Genetic Algorithm is good solutiontechnique for solving such problems and later analysis will prove this argument. The programis written in C++ and analysis is done by using variation in various parameters.
41
Kang, Le. "A logic approach to conflict resolution in university timetabling." Thesis, University of Ottawa (Canada), 1990. http://hdl.handle.net/10393/5767.
Full textAbstract:
A computerized timetabling system developed at University of Ottawa is presented. The system is built on a logic programming model which uses first order logic to define first order and second order constraints in timetabling. Information about courses, professors, and student programs is collected for each academic year and used in the process of constructing timetables. The time schedule produced by the system takes into account course conflicts, professor availability, professor teaching preferences, pre-assignments, classroom location choices, and many other important factors that affect its user satisfaction level. Along with the system's ability to include factors such as professor availability, professor teaching preferences and classroom location, the analysis of test results at the University of Ottawa shows a large improvement in the time utilization and seating usage of classrooms, compared to the corresponding timetables that are produced by the traditional manual processes. (Abstract shortened by UMI.)
42
Borges, Suzan Kelly. "Resoluçao de Timetabling utilizando algoritmos genéticos e evoluçao cooperativa." reponame:Repositório Institucional da UFPR, 2011. http://hdl.handle.net/1884/25068.
Full textAbstract:
Resumo: A produção de grades horárias em instituições de ensino é uma tarefa complexa e de difícil solução, pois, neste contexto, existem muitas restrições necessárias à validade e aplicabilidade das respostas produzidas. Na literatura, a produção de grades horárias e, na verdade, uma das variações de timetabling, o qual, em essência, é um problema de escalonamento de eventos em um periodo finito de tempo, sujeito a restrições, como por exemplo, tempo, recursos humanos disponíveis (professores), recursos físicos existentes (salas de aula) e atividades a serem desenvolvidas (exames, aulas, entre outros). Para solucionar esse problema e automatizar o processo, abordagens de Inteligência Artificial têm sido aplicadas com sucesso, mais especificamente, os métodos da Computação Evolutiva. A computação evolutiva define uma classe de algoritmos que modelam computacionalmente os conceitos da teoria da Evolução de Charles Darwin. Esses algoritmos aplicam operadores genéticos sobre populações de indivíduos, visando à produção de indivíduos mais aptos que os antigos. Como resultado, obtêm-se indivíduos ou soluções candidatas com um alto grau de aptidão para solucionar um problema específico. O objetivo principal deste trabalho é estudar e implementar uma solução para o problema de Geração de Grades Horárias, com base na Computação Evolutiva. O método evolutivo escolhido é denominado Algoritmo Coevolutivo Cooperativo. Esse método subdivide um problema complexo em problemas menores, sendo que cada um deles é representado por uma população pertencente ao dominio do problema. Cada uma dessas populações possui características individuais e, no processo, todas evoluem paralelamente, de maneira cooperativa, por meio de sucessivas aplicações de operadores genéticos. Ao final do processo, os representantes de cada uma das populações formam, em conjunto, uma solução completa. Para verificar a validade do método para a resolução do problema em estudo, implementou-se um algoritmo cooperativo. Os resultados dos experimentos mostraram que algoritmos cooperativos são ferramentas poderosas, capazes de resolver problemas complexos de otimização numérica sujeitos a restrições.
43
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.
44
Eckersley, Adam. "Novel knowledge based and heuristic approaches to university timetabling." Thesis, Nottingham Trent University, 2007. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.444607.
Full text
45
Hussin, Naimah Mohd. "Tabu search based hyper-heuristic for examination timetabling problem." Thesis, University of Nottingham, 2005. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.423286.
Full text
46
Andersson, Jerker. "Solving the Train Timetabling Problem by using Rapid Branching." Thesis, KTH, Optimeringslära och systemteori, 2016. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-181308.
Full textAbstract:
The topic of this thesis is the implementation of rapid branching to find an integer solution for the train timetabling problem. The techniques that rapid branching are based on are presented. The important aspect of rapid branching are discussed and then the algorithm is applied to some artificial problems. It is shown that rapid branching can be both faster and slower than a standard integer solver depending on the problem instance. For the most realistic set of the examined instances, rapid branching turned out to be faster than the standard integer solver and produce satisficingly high quality solutions.Den här uppsatsen handlar om en implementering av rapid branching för att hitta en heltalslösning till optimeringsproblemet vid tidtabelläggning för järnvägar. Rapid branching är en algoritm skapad för att fungera bra på storskaliga heltals-optimeringsproblem. I uppsatsen beskrivs några sätt att skapa egen tidtabelläggnings problem och sedan jämförs rapid branching med en vanlig heltalslösare för de problemen. Genom att göra detta visas att algoritmen rapid branching kan vara både snabbare och långsammare än att använda en konventionell heltalslösare. För den mest realistiska instansen av tidtabelläaggning problemet visade det sig att rapid branching var snabbare än heltalslösaren samt att den funna lösningen var av satisfierande hög kvalitet.
47
Asmuni, Hishammuddin. "Fuzzy methodologies for automated University timetabling solution construction and evaluation." Thesis, University of Nottingham, 2008. http://eprints.nottingham.ac.uk/10514/.
Full textAbstract:
This thesis presents an investigation into the use of fuzzy methodologies for University timetabling problems. The first area of investigation is the use of fuzzy techniques to combine multiple heuristic orderings within the construction of timetables. Different combinations of multiple heuristic ordering were examined, considering five graph-based heuristic orderings - Largest Degree, Saturation Degree, Largest Enrolment, Largest Coloured Degree and Weighted Largest Degree. The initial development utilised only two heuristic orderings simultaneously and subsequent development went on to incorporate three heuristic orderings simultaneously. A central hypothesis of this thesis is that this approach provides a more realistic scheme for measuring the difficulty of assigning events to time slots than the use of a single heuristic alone. Experimental results demonstrated that the fuzzy multiple heuristic orderings (with parameter tuning) outperformed all of the single heuristic orderings and non-fuzzy linear weighting factors. Comprehensive analysis has provided some key insights regarding the implementation of multiple heuristic orderings. Producing examination timetables automatically has been the subject of much research. It is generally the case that a number of alternative solutions that satisfy all the hard criteria are possible. Indeed, there are usually a very large number of such feasible solutions. Some method is required to permit the overall quality of different solutions to be quantified, in order to allow them to be compared, so that the best may be selected. In response to that demand, the second area of investigation of this thesis is concerned with a new evaluation function for examination timetabling problems. A novel approach, in which fuzzy methods are used to evaluate the end solution quality, separate from the objective functions used in solution generation, represents a significant addition to the literature. The proposed fuzzy evaluation function provides a mechanism to allow an overall decision in evaluating the quality of a timetable solution to be made based on common sense rules that encapsulate the notion that the timetable solution quality increases as both the average penalty and the highest penalty decrease. New algorithms to calculate what is loosely termed the lower limits and upper limits of the proximity cost function for any problem instance are also presented. These limits may be used to provide a good indication of how good any timetable solution is. Furthermore, there may be an association between the proposed lower limit and the formal lower bound. This is the first time that lower limits (other than zero) have been established for proximity cost evaluation of timetable solutions.
48
Andrén, Axel. "Graphical User Interface for Timetabling at TekNat with Standardised Output." Thesis, Uppsala universitet, Institutionen för informationsteknologi, 2016. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-275105.
Full textAbstract:
Uppsala University's "Vetenskapsområdet för teknik och naturvetenskap" (Disciplinary Domain of Science and Technology), or just TekNat, has been moving towards automating their scheduling process for several years. This project has been part of that effort, and had the goal of showing that requirements could be gathered for a scheduling interface that satisfied both scheduling staff and teachers, as well as showing that these requirements could then be implemented. Human-Computer Interaction, or HCI, was used to aid in these tasks, as it is a field concerned with how to design effectively for intended end users, and has a variety of techniques and methods to aid in accomplishing this. Some requirements were known beforehand, such as the interface needing to have a standard format for its output, while most were gathered using HCI methods such as semi-structured interviews and paper prototyping. The final requirements specified what was desired for the interface to improve on the current system and be faster, easier, more enticing to use. A functional GUI was implemented that followed these requirements, with some reservations, and improved after feedback from three rounds of testing with the staff.
49
Dornelles, Arton Pereira. "A matheuristic approach for solving the high school timetabling problem." reponame:Biblioteca Digital de Teses e Dissertações da UFRGS, 2015. http://hdl.handle.net/10183/140451.
Full textAbstract:
A geração de quadros de horários escolares é um problema clássico de otimização que tem sido largamente estudado devido a sua importâncias prática e teórica. O problema consiste em alocar um conjunto de aulas entre professor-turma em períodos de tempo pré-determinados, satisfazendo diferentes tipos de requisitos. Devido a natureza combinatória do problema, a resolução de instâncias médias e grandes torna-se uma tarefa desafiadora. Quando recursos são escassos, mesmo uma solução factível pode ser difícil de ser encontrada. Várias técnicas tem sido propostas na literatura científica para resolver o problema de geração de quadros de horários escolares, no entanto, métodos robustos ainda não existem. Visto que o uso de métodos exatos, como por exemplo, técnicas de programação matemática, não podem ser utilizados na prática, para resolver instâncias grandes da realidade, meta-heurísticas e meta-heurísticas híbridas são usadas com frequência como abordagens de resolução. Nesta pequisa, são desenvolvidas técnicas que combinam programação matemática e heurísticas, denominadas mateheurísticas, para resolver de maneira eficiente e robusta algumas variações de problemas de geração de quadros de horários escolares. Embora neste trabalho sejam abordados problemas encontrados no contexto de instituições brasileiras, os métodos propostos também podem ser aplicados em problemas similares oriundo de outros países.The school timetabling is a classic optimization problem that has been extensively studied due to its practical and theoretical importance. It consists in scheduling a set of class-teacher meetings in a prefixed period of time, satisfying requirements of different types. Given the combinatorial nature of this problem, solving medium and large instances of timetabling to optimality is a challenging task. When resources are tight, it is often difficult to find even a feasible solution. Several techniques have been developed in the scientific literature to tackle the high school timetabling problem, however, robust solvers do not exist yet. Since the use of exact methods, such as mathematical programming techniques, is considered impracticable to solve large real world instances, metaheuristics and hybrid metaheuristics are the most used solution approaches. In this research we develop techniques that combine mathematical programming and heuristics, so-called matheuristics, to solve efficiently and in a robust way some variants of the high school timetabling problem. Although we pay special attention to problems arising in Brazilian institutions, the proposed methods can also be applied to problems from different countries.
50
Bukenberger, Jesse Paul. "A Set Union Based Formulation for Course Scheduling and Timetabling." DigitalCommons@CalPoly, 2014. https://digitalcommons.calpoly.edu/theses/1250.
Full textAbstract:
The Course Timetabling Problem is a widely studied optimization problem where a number of sections are scheduled in concert with the assignment of students to sections in order to maximize the desirability of the resulting schedule for all stakeholders. This problem is commonly solved as a linear program with variables for each student or group of students with identical schedules. In this paper we explore an alternative formulation that aggregates binary student variables into integer variables denoting the number of students enrolled in a course. Our solution method assumes decomposition of the general schedule into time blocks, and applies a unique set theory based, integer linear programming formulation that seeks to maximize the total number of students enrolled in their desired sections across the time blocks. Once the problem has been solved, the simpler problem of disaggregating the solution is resolved. This approach can be used to find exact solutions, given sufficient computing power, or simplified to quickly find solutions within calculable bounds of optimality. Case studies with a local elementary school and a local high school show that the new formulation is significantly faster and can be made to be reasonably accurate.