This work deals with timetabling problems at the Faculty of Information Technology of Brno University of Technology. The aim of this thesis is to design and implement new application to support manual timetable planning, that will offer some innovations in comparison with current state. Implemented application is based on client-server architecture, at which client and server communicate by means of REST interface. Application offers functions for preprocessing of input data, as well as functions for analysis of created timetables. Data can be exported in HTML format.

The diploma thesis deals with the issue of designing a part of the information system for passenger. The proposed system is aimed at providing clear information about driving a recreational-tourist train. The outcome is a web portal that processes data about the train ride and then presents it to potential customers.

Punctuality and reliability are important for travellers. Railway lines with heterogeneous and dense traffic have proved to be prone to generate delays. Faster services and increased traffic have to be counterbalanced with measures for increased reliability. Efficient timetable planning can improve the use of such lines. Usually, that aim is treated from either a capacity or a socio-economic point of view. Because both are important, this thesis aims to combine the fields. A new method to evaluate timetable alternatives is developed. Commonly used methods are combined in a novel way to reveal values for different variables as input for evaluation of alternatives. That enables the comparison of timetable strategies using relevant input data. The idea is to estimate the benefits of a timetable for a traveller by expressing them as a timetable performance index (TTPI). For this purpose, quality indicators and methods to reveal them are identified. In the next step, traditional valuations for relationships between the indicators are used to test different model configurations for evaluation of alternatives, for example alternative departures on the same line or different timetables.  To treat this multidisciplinary task, several case studies were performed on the Swedish Southern and Western Main lines. As part of a study focussing on methods to measure and evaluate capacity based on travellers’ valuations, the importance of delays was analysed in a questionnaire study and relationships between several variables describing the timetable were found. The other case studies aimed to identify relevant variables and use them to evaluate alternatives. Static and dynamic variables are distinguished. The static ones describe the timetable before operation, the dynamic ones the result of operation or estimated outcome revealed by means of, for example, simulation. Empirical delay data is used in one study, simulation with the microscopic tool RailSys in the others. In one of the studies, analysis is combined with the macroscopic timetabling tool TVEM (Lindfeldt, 2010). The case studies showed the characteristics of the analysed lines described by the chosen variables and which methods and variables are relevant to use for a comparison of timetable slots or evaluation of effects of changes in the timetable. An evaluation method was developed where simulation and timetable analysis reveal the variables. The idea is to construct an analytical function using traditional weights for relationships between the variables to convert the values of the variables into a performance index (PI). Based on a PI for each train slot (TSPI), the TTPI for the whole timetable is estimated. It describes the quality of a timetable in terms of timetable time, i.e. the resulting value is a time that is comparable to the scheduled travel time of one train departure, but includes additional information. With this method, complex timetables can be evaluated regarding their robustness to perturbations, which is valuable for socio-economic analysis of effects of measures applied on the railway system. As shown in a one of the case studies, quality in terms of punctuality and reliability is important for travellers, at the same time as the design of the timetable has significant impact on these aspects. Timetable analysis and simulation are relevant methods to reveal variables that describe these characteristics and evaluation with the presented method is recommended. The configuration of the TTPI is essential for the outcome whereas it is important to choose variables and parameters adequately. If this is taken into account, the approach can be an efficient way to adjust timetables and choose the best alternative, for instance if a train path or timetable change is to be chosen among several. / Punktlighet och tillförlitlighet är viktiga för resenärer. Järnvägar med heterogen och tät trafik har visat sig vara benägna att generera förseningar. Snabbare tåg och utökat trafikutbud måste uppvägas mot punktlighetsåtgärder. Effektiv tidtabellsplanering kan förbättra utnyttjandet av sådana linjer. Detta ändamål behandlas oftast utifrån antingen kapacitets eller samhällsekonomisk synvinkel. Eftersom bägge är viktiga syftar den här avhandlingen på att kombinera dessa områden. En metod för utvärdering av tidtabellsalternativ utvecklas. Befintliga metoder kombineras på ett nytt sätt för att ta fram värden för olika variabler som indata för en utvärdering av alternativen. Detta möjliggör en jämförelse av tidtabellsstrategier med relevant indata. Idén bygger på att bedöma en tidtabells nytta för resenären genom att uttrycka denna som ett prestationsindex (TTPI). För detta syfte identifieras kvalitetsindikatorer och metoder för att ta fram dessa. Traditionella valideringar för relationerna mellan indikatorerna används sedan för att testa olika konfigurationer av modellen för att utvärdera alternativ, till exempel alternativa avgångar på samma linje eller olika tidtabeller. För denna multidisciplinära uppgift har flera fallstudier på svenska Södra och Västra stambanan genomförts. Som del av en studie med fokus på metoder för att mäta och utvärdera kapacitet baserad på resenärers värderingar har förseningens värde analyserats med hjälp av en enkätundersökning och relationer mellan några variabler som beskriver tidtabellen hittats. De övriga fallstudierna syftade på att ta fram relevanta variabler och att använda dem för att utvärdera alternativ. Variablerna delades upp i statiska och dynamiska. De statiska beskriver tidtabellen innan den körs, de dynamiska det verkliga utfallet eller det estimerade resultatet framtaget med hjälp av exempelvis simulering. Empiriska försenings­data används i en studie, simulering med det mikroskopiska programmet RailSys i de andra. I en av studierna kombineras analysen med det makroskopiska tidtabellsverktyget TVEM (Lindfeldt, 2010). Fall­studierna visade de analyserade linjernas egenskaper beskrivna av de valda variablerna och vilka metoder och variabler som är relevanta för en jämförelse av olika tåglägen eller en utvärdering hur en ändring i tidtabellen påverkar. En utvärderingsmetod där simulering och tidtabellsanalys används för att ta fram variablerna utvecklades. Idén är att skapa en analytisk funktion med hjälp av traditionella vikter som beskriver sambanden mellan variablerna för att räkna om variablernas värden till en prestations­index (PI). Baserad på en PI för varje tågläge (TSPI) estimeras värdet för hela tidtabellen (TTPI). Detta index beskriver tidtabellens kvalitet som tidtabellstid, dvs. värdet är en tid som är jämförbar med den tidtabellslagda restiden för en avgång, men med ytterligare information inkluderat. Med hjälp av denna metod kan komplexa tidtabeller utvärderas med avseende på robusthet mot störningar vilket är värdefullt för samhällsekonomiska bedömningar av åtgärder i järnvägssystemet. Som en av fallstudierna visade är kvalitet i form av punktlighet och tillförlitlighet viktig för resenärer samtidigt som tidtabellens utformning har en signifikant påverkan på samma aspekter. Tidtabellsanalys och simulering är relevanta metoder för att ta fram variabler som beskriver dessa egenskaper och utvärdering med de visade metoderna rekommenderades. Modellens konfiguration är betydelsefull för resultatet vilket gör det viktigt att välja variabler och parametrar som är lämpliga. Om detta respekteras kan metoden vara effektiv för att anpassa tidtabeller och välja det bästa alternativet, till exempel när det gäller att välja mellan olika tåglägen eller justeringar i tidtabellen. / Pünktlichkeit und Zuverlässigkeit sind wichtig für Reisende. Stark belastete Eisenbahnlinien mit heterogenem Verkehr sind störungsanfällig. Zugleich besteht oft ein Bedarf an schnelleren und häufigeren Verbindungen, was jedoch mit potentiellen negativen Effekten auf die Kapazität aufgewogen werden muss. Effiziente Fahrplan­konstruktion kann die Nutzung solcher Linien verbessern. Dieses Ziel wird meist entweder aus der Sicht der Kapazitätsanalyse oder wirtschaftlichen Aspekten be­trachtet. Da beide Betrachtungsweisen wichtig sind, strebt diese Arbeit die Kombination beider Felder an. Eine Methode für die Auswertung verschiedener Fahrpläne wird entwickelt. Bewährte Methoden werden in neuer Weise kombiniert um Werte für verschiedene Variablen als Input für die Auswertung von Alternativen zu erhalten. Das ermöglicht es potentielle Änderungen im Fahrplan mithilfe relevanter Werte zu vergleichen. Die Idee basiert auf einem Leistungsindex (TTPI), der den Nutzen eines Fahrplans für die Reisenden ausdrücken soll. Zu diesem Zweck werden Qualitätsindikatoren gewählt und Methoden zur Berechnung und Bearbeitung der Indikatoren entwickelt. Traditionelle Werte für die Abhängigkeiten zwischen den Indikatoren dienen dann dem Test verschiedener Modelkonfigurationen sowie der Aus­wertung von Alternativen, z. B unterschiedlicher Trassen oder Fahrpläne. Für diese multidisziplinäre Aufgabe wurden mehrere Fallstudien für die südliche und westliche Hauptstrecke in Schweden durchgeführt. In einer Fragenbogenstudie mit den Schwerpunkten Mess- und Auswertungsmethoden wurde der Wert von Verspätungen für Reisende untersucht und Verhältnisse zwischen mehreren Indikatoren ermittelt. Die weiteren Fallstudien strebten das Finden relevanter Variablen und deren Anwendung zur Auswertung von Alternativen an. Statische und dyna­mische Variablen wurden unterschieden. Die statischen beschreiben den geplanten Fahrplan vor dem Betrieb, die dynamischen den wirklichen Ausfall oder das beispielsweise durch Simulation berechnete erwartete Resultat. In einer der Fall­studien wurde empirisches Datenmaterial für die Verspätungsdaten genutzt, in den weiteren das mikroskopische Simulationsprogramm RailSys. In einer der Studien wurde die Analyse mit dem makroskopischen Fahrplanungsprogramm TVEM (Lindfeldt, 2010) kombiniert. Die Eigenschaften der untersuchten Linien wurden mithilfe der gewählten Indikatoren analysiert. Weiterhin wurde die Relevanz verschiedener Methoden und Variablen für den Vergleich von Fahrten oder der Beurteilung von Änderungen in Fahrplänen beschrieben. Die gewählte Bewertungs­methode kombiniert Simulation und Fahrplananalyse um die benötigten Werte zu bestimmen. Mithilfe einer analytischen Funktion sollen die Variablen durch An­wen­den von traditionellen Werten für die Zusammenhänge in einen Leistungsindex (PI) umgewandelt werden. Basierend auf einem PI für jede geplante Fahrplantrasse (TSPI) kann der Wert für den gesamten Fahrplan (TTPI) bestimmt werden. Dieser Index übersetzt die Qualität des Fahrplans in Fahrtzeit, das heißt resultiert in einer Zeit, die mit der fahrplanmäßigen Fahrtzeit für eine Fahrt vergleichbar ist, aber zusätzliche Information enthält. Diese Methode ermöglicht es, komplexe Fahrpläne bezüglich Robustheit gegen Störungen auszuwerten, was wertvoll für die Berechnung der Wirtschaftlichkeit von Maßnahmen im Bahnnetz ist. Wie eine der Fallstudien gezeigt hat, ist die Qualität in Form von Pünktlichkeit und Zuverlässigkeit wichtig für die Reisenden. Gleichzeitig beeinflusst die Ausformung des Fahrplans diese Eigenschaften deutlich. Fahrplananalyse und Simulation sind geeignete Methoden um die Werte der Variablen, die diese Eigenschaften beschreiben, zu bestimmen. Auswertung auf diese Weise wird empfohlen. Die Konfiguration des Models beeinflusst das Ergebnis, weshalb es wichtig ist geeignete Variablen und Parameter zu benutzen. Wird das berücksichtigt, kann die entwickelte Methode effizient für das Verbessern von Fahrplänen angewandt werden und die Wahl der besten Alternative unterstützen, z.B. bei geplanten Änderungen im Fahrplan oder der Wahl zwischen unterschiedlichen Trassen. / <p>QC 20160902</p>

This thesis seeks to understand the role of school timetables as an interface between policies that regulate or distribute forms of capital to schools, and their teaching and learning rhythms. By doing so, it proposes a mechanism for examining the reproduction of schooling practices, and how these are grounded in policy-regulated materiality. Two high schools with similar historic backgrounds, and operating under the same provincial government, were selected and closely studied for evidence of rhythms of practice and the correspondence of these rhythms to each school's timetable. The two schools now experience different access to resources, and have significant differences in teaching and learning rhythms, as well as school-leaving summative assessment results. The study develops an analytic framework for identifying policies that reach into schools through the timetable. Five key inputs are identified as necessary for constructing timetables, providing productive lines of inquiry as to which policies affect schooling rhythms and how. By asking who teaches whom, what, with what and where, systematic analysis is conducted on: how schools are staffed (who); who they enrol (whom); their interpretation of curriculum (what); what supplementary resources they can command (with what); and their infrastructural facilities and geographic (dis)advantages (where). The interaction between these different threads is examined as they tangle within each school's timetable. The enactment of the policies regulating each thread is then traced through the layers of governance of the South African education system: national, provincial and local (school-level). Timetables are conceptualised in this study as local representations of intended teaching and learning rhythm. Using Lefebvre's triad of timespace-conceived, timespace-perceived and timespace-lived, timetables (timespace-conceived) are brought into conversation with timespace-lived through daily teaching and learning activities. Bourdieu's theory of practice is used with Lefebvre to animate the ‘game' of schooling: what schools strive for, what forms of capital they can command to sustain or improve their field position, and how they reproduce their practices. Bourdieu and Lefebvre together generate a sociomaterial practice theory lens that foregrounds timetables and their legitimacy to govern rhythms of teaching and learning in timespace. Timetables emerge as a site of the production and reproduction of advantage (fortified schools) and/or disadvantage (exposed schools) in the game of schooling. In timetables, the policies that avail forms of capital interact in previously unconsidered ways, suggesting that collectively they potentially undergird inequality in the education system.

Based on an initiative to increase the punctuality on Swedish railways in the short term, this study on potential for increased punctuality by adjustments in the train time schedule on The Western Main Line was initiated. This was done by examining alternatives with different adjustments based on today’s timetable. The goal with the study was to increase the punctuality for the highspeed trains on The Western Main Line by five percentage points. Additionally, the study had a purpose of testing if the Swiss concept of Taktfahrplan could be applicable on a Swedish railway. The adjustments of the timetable were based on three parameters that have impact on the robustness of a timetable; dwell time, allowance and headway between trains. Those were the parameters that were tested. Based on a literature study and data on today’s delays, punctuality and dwell times for the highspeed trains, the current situation could be analyzed. The analysis showed that the trains of today’s timetable departed densely in the mornings, the biggest amounts of trains were near the big cities, punctuality had improved from 2019 to 2020, problematic points with large delays existed around Hallsberg and Falköping and the performed dwell times were longer than the planned ones for every station. Based on the analysis of today’s situation, three case alternatives as well as an alternative for comparison were created. In case alternative 1, dwell times were extended for the highspeed trains stops, in alternative 2, allowance was added and in alternative 3, headway was extended at the start stations. Time schedules for the alternatives were created in RailSys and were then simulated on a selected stretch with a disturbance filter that was based on real distributions of delay. The results did not show considerable difference in punctuality for the case alternatives. However, alternative 1 and 2 showed improvement, while the punctuality was reduced in alternative 3. A fourth alternative was created, where the two cases that had led to improvement were combined. After simulation of alternative 4, it could be established that it was the case that provided the highest improvement in punctuality. A Taktfahrplan (regular departures and station meetings) was made in RailSys that showed how well such a timetable was applicable for the highspeed trains on The Western Main Line. The results turned out well because meeting spots for these trains, at half hour traffic and the selected stopping patterns, occurred most evidently at Katrineholm C, but also at Södertälje syd, Skövde C and Herrljunga. The conclusions of the study were that none of the alternatives led to a 5-percentage increase in punctuality. However, three cases led to increased punctuality, while one case produced decreased punctuality. The parameters that produced the highest increase in punctuality was the combination of dwell time and allowance adjustments. The consequences of the adjustments were longer planned driving times for the trains and lower capacity utilization on the track. Lastly, it was established that Taktfahrplan was applicable for the highspeed trains on The Western Main Line, but further analysis would be required before implementation, especially with consideration to planning for practical introduction.

Η παρούσα μεταπτυχιακή εργασία πραγματεύεται το πρόβλημα του σχεδιασμού του ωρολογίου προγράμματος μαθημάτων ενός εκπαιδευτικού ιδρύματος και πιο συγκεκριμένα ενός πανεπιστημίου. Λόγω της πολυπλοκότητας και της ύπαρξης πολυάριθμων μεταβλητών και παραμέτρων το πρόβλημα ανήκει στην κατηγορία των NP-complete προβλημάτων, γεγονός που κάνει την εξεύρεση της βέλτιστης λύσης μία πολύ δύσκολη υπόθεση. Η βιβλιογραφική ανασκόπηση έδειξε ότι έχουν προταθεί και εφαρμόζονται πολλές και διαφορετικές μεθοδολογίες επίλυσης του προβλήματος. Οι τεχνικές προέρχονται από πολλούς και διαφορετικούς τομείς όπως για παράδειγμα το μαθηματικό προγραμματικό, τον ακέραιο γραμμικό προγραμματισμό, τις μετα-ευρετικές μεθόδους, αλλά και από τον χώρο της Τεχνητής Νοημοσύνης. Η μέθοδος επίλυσης, που προτείνεται από την παρούσα εργασία, είναι η πολυκριτηριακή ανάλυση βασιζόμενη στον συναινετικό προγραμματισμό (compromise programming). Η εφαρμογή της μεθόδου σε δεδομένα προβλημάτων ωρολογίου προγραμματισμού, είχε πολύ ικανοποιητικά αποτελέσματα, καθώς προεκύψαν ποιοτικά ωρολόγια προγράμματα, που ικανοποιούσαν όλους τους περιορισμούς. / The timetabling problem constists in scheduling a sequence of lectures between teachers and students in a prefixed period of time, satisfying a set of constraints of various type. Due to the complexity and the existence of many variables and parameters, the problem belongs in the category of NP-complete problems, fact that makes the discovery of an optimal solution, a very difficult affair. The bibliographic search, showed that have been proposed and are applied many and different solving techniques, which are based on Mathematical programming (Integer Linear Programming), on Graph Colouring, on Meta-Heuristics Methods, on Multicriteria approaches, on Case-based approaches, but also belonging to Artificial Intelligence. In this paper, the multicriteria approach based on Compromise programming is suggested. The application of technique in timetable data of an educational institute, had very good results, and provided qualitative timetables, satisfying all constraints.

La thèse porte sur la proposition de méthodes d’optimisation (modèles mathématiques et métaheuristique) et leur couplage avec un modèle de simulation pour la résolution de problèmes de livraison collecte incluant la planification des horaires des chauffeurs. L’originalité de ces travaux porte sur la diversité des ressources (véhicule, chauffeur, quai de chargement, de déchargement, contenant, ligne de production, aire de nettoyage) et des contraintes (incompatibilité véhicule/contenant, date de début au plus tôt, date de fin souhaitée, planning…) à prendre en compte. L’objectif est de proposer une organisation permettant de réaliser l’ensemble des transports tout en minimisant les retards et les heures supplémentaires. La première partie s’intéresse au transport d’un seul type de produit. Le problème est modélisé comme un RCPSP avec profil de demande en ressources variable. Les transports à vide sont modélisés comme des temps de montage dépendant de la séquence. Deux programmes linéaires en nombres entiers sont proposés. La seconde partie concerne le transport de plusieurs types de produit. Le problème présente une double complexité qui est résolue par le couplage d’une recherche locale itérée avec un modèle de simulation. Le modèle de simulation permet de répondre à la complexité structurelle et fonctionnelle, notamment en raison de la diversité des ressources. La troisième partie intègre la définition des horaires de travail des chauffeurs. Une approche itérative incluant un modèle de simulation, un programme linéaire en nombres entiers et le couplage précédemment présenté est proposée. Ce problème est traité dans un contexte hospitalier pour le transport de contenants propres ou sales (repas, linge, médicaments) entre sites de consommation et sites de production. Chaque partie fait l’objet d’une expérimentation avec des données réelles. / The thesis focuses on the proposed optimization methods (metaheuristics and mathematical models) and their coupling with a simulation model to solve problems of collection including delivery scheduling drivers. The originality of this work focuses on the diversity of resources (vehicle, driver, dock loading, unloading, container production line, cleaning area) and constraints (incompatibility vehicle / container, start date earlier desired end date, planning ...) to take into account. The objective is to provide an organization to achieve all transport while minimizing delays and overtime. The first part focuses on the transport of a single type of product. The problem is modeled as a demand profile RCPSP with variable resources. Empty transports are modeled as time-dependent assembly sequence. Two integer linear programs are proposed. The second part concerns the transport of several types of product. The problem has a double complexity that is determined by the coupling of an iterated local search with a simulation model. The simulation model allows to meet the structural and functional complexity, mainly because of the diversity of resources. The third part includes the definition of working hours of drivers. An iterative approach including a simulation model, an integer linear program and previously presented coupling is proposed. This problem is treated in a hospital setting for transporting containers clean or dirty (food, clothes, medicine) between sites of consumption and production sites. Each party is subject to an experiment with real data.

Todo início de período letivo, gestores de instituições de ensino se deparam com um típico problema: montar as grades horárias das turmas, segundo as demandas de aulas de suas disciplinas e considerando as restrições de disponibilidade horária de todos os envolvidos. Conhecido na literatura como School Timetabling Problem (STP), este típico problema de otimização combinatória é reconhecidamente complexo por conta do seu elevado número de variáveis e restrições. Devido à dependência das regras do sistema educacional de cada país, o STP pode ter inúmeras variantes, cada uma com o seu próprio conjunto de particularidades. Este trabalho se propõe a oferecer um modelo para o STP considerando o sistema educacional brasileiro, visando alocar não apenas professores, mas também determinando que disciplina cada professor deve ministrar e alocando os locais de aula. O modelo proposto, baseado na meta-heurística simulated annealing, foi concebido para que cada instituição de ensino usuária tenha liberdade para definir a penalidade de cada tipo possível de inconformidade ou restrição, de modo que o algoritmo empregado possa encontrar uma solução com o menor custo possível. / Every beginning of term, educational institution managers face a typical problem: planning the classes' timetable, according to their lesson demands for each subject, considering, furthermore, the schedule constrains of all actors. Known as school timetabling problem (STP), this typical combinatorial optimization problem is remarkably complex due to the high number of variables and constraints. Owing to the rules of each country's educational system, STP can have uncountable variants, each one with their own set of features. This dissertation searches to offer a model to STP considering the Brazilian Educational System, focusing on allocating not only the teachers but also determining which subject each teacher should teach and allocating classrooms, laboratories and the like. The propesed model, based on the metaheuristic simulated annealing, was conceived so that each educational institution using this model has the freedom to define which penalty will be applied to each possible kind of noncomformity and constraint, in order for the applied algorithm to find a solution at the lowest cost as possible.

Todo início de período letivo, gestores de instituições de ensino se deparam com um típico problema: montar as grades horárias das turmas, segundo as demandas de aulas de suas disciplinas e considerando as restrições de disponibilidade horária de todos os envolvidos. Conhecido na literatura como School Timetabling Problem (STP), este típico problema de otimização combinatória é reconhecidamente complexo por conta do seu elevado número de variáveis e restrições. Devido à dependência das regras do sistema educacional de cada país, o STP pode ter inúmeras variantes, cada uma com o seu próprio conjunto de particularidades. Este trabalho se propõe a oferecer um modelo para o STP considerando o sistema educacional brasileiro, visando alocar não apenas professores, mas também determinando que disciplina cada professor deve ministrar e alocando os locais de aula. O modelo proposto, baseado na meta-heurística simulated annealing, foi concebido para que cada instituição de ensino usuária tenha liberdade para definir a penalidade de cada tipo possível de inconformidade ou restrição, de modo que o algoritmo empregado possa encontrar uma solução com o menor custo possível. / Every beginning of term, educational institution managers face a typical problem: planning the classes' timetable, according to their lesson demands for each subject, considering, furthermore, the schedule constrains of all actors. Known as school timetabling problem (STP), this typical combinatorial optimization problem is remarkably complex due to the high number of variables and constraints. Owing to the rules of each country's educational system, STP can have uncountable variants, each one with their own set of features. This dissertation searches to offer a model to STP considering the Brazilian Educational System, focusing on allocating not only the teachers but also determining which subject each teacher should teach and allocating classrooms, laboratories and the like. The propesed model, based on the metaheuristic simulated annealing, was conceived so that each educational institution using this model has the freedom to define which penalty will be applied to each possible kind of noncomformity and constraint, in order for the applied algorithm to find a solution at the lowest cost as possible.

Todo início de período letivo, gestores de instituições de ensino se deparam com um típico problema: montar as grades horárias das turmas, segundo as demandas de aulas de suas disciplinas e considerando as restrições de disponibilidade horária de todos os envolvidos. Conhecido na literatura como School Timetabling Problem (STP), este típico problema de otimização combinatória é reconhecidamente complexo por conta do seu elevado número de variáveis e restrições. Devido à dependência das regras do sistema educacional de cada país, o STP pode ter inúmeras variantes, cada uma com o seu próprio conjunto de particularidades. Este trabalho se propõe a oferecer um modelo para o STP considerando o sistema educacional brasileiro, visando alocar não apenas professores, mas também determinando que disciplina cada professor deve ministrar e alocando os locais de aula. O modelo proposto, baseado na meta-heurística simulated annealing, foi concebido para que cada instituição de ensino usuária tenha liberdade para definir a penalidade de cada tipo possível de inconformidade ou restrição, de modo que o algoritmo empregado possa encontrar uma solução com o menor custo possível. / Every beginning of term, educational institution managers face a typical problem: planning the classes' timetable, according to their lesson demands for each subject, considering, furthermore, the schedule constrains of all actors. Known as school timetabling problem (STP), this typical combinatorial optimization problem is remarkably complex due to the high number of variables and constraints. Owing to the rules of each country's educational system, STP can have uncountable variants, each one with their own set of features. This dissertation searches to offer a model to STP considering the Brazilian Educational System, focusing on allocating not only the teachers but also determining which subject each teacher should teach and allocating classrooms, laboratories and the like. The propesed model, based on the metaheuristic simulated annealing, was conceived so that each educational institution using this model has the freedom to define which penalty will be applied to each possible kind of noncomformity and constraint, in order for the applied algorithm to find a solution at the lowest cost as possible.