Résumé indisponible. / In this thesis we have concerned ourselves with university timetabling problems both course timetabling and examination timetabling problems. Most of the timetabling problems are computationally NP-complete problems, which means that the amount of computation required to find solutions increases exponentially with problem size. These are idiosyncratic nature problems, for example different universities have their own set of constraints, their own definition of good timetable, feasible timetable and their own choice about the use of constraint type (as a soft or hard constraint). Unfortunately, it is often the case that a problem solving approach which is successfully applied for one specific problem may not become suitable for others. This is a motivation, we propose a generalized problem which covers many constraints used in different universities or never used in literature. Many university timetabling problems are sub problems of this generalized problem. Our proposed algorithms can solve these sub problems easily, moreover constraints can be used according to the desire of user easily because these constraints can be used as reference to penalty attached with them as well. It means that give more penalty value to hard constraints than soft constraint. Thus more penalty value constraints are dealt as a hard constraint by algorithm. Our algorithms can also solve a problem in two phases with little modification, where in first phase hard constraints are solved. In this work we have preferred and used two phase technique to solve timetabling problems because by using this approach algorithms have broader search space in first phase to satisfy hard constraints while not considering soft constraints at all. Two types of algorithms are used in literature to solve university timetabling problem, exact algorithms and approximation algorithms. Exact algorithms are able to find optimal solution, however in university timetabling problems exact algorithms constitute brute-force style procedures. And because these problems have the exponential growth rates of the search spaces, thus these kinds of algorithms can be applied for small size problems. On the other side, approximation algorithms may construct optimal solution or not but they can produce good practically useable solutions. Thus due to these factors we have proposed approximation algorithms to solve university timetabling problem. We have proposed metaheuristic based techniques to solve timetabling problem, thus we have mostly discussed metaheuristic based algorithms such as evolutionary algorithms, simulated annealing, tabu search, ant colony optimization and honey bee algorithms. These algorithms have been used to solve many other combinatorial optimization problems other than timetabling problem by modifying a general purpose algorithmic framework. We also have presented a bibliography of linear integer programming techniques used to solve timetabling problem because we have formulated linear integer programming formulations for our course and examination timetabling problems. We have proposed two stage algorithms where hard constraints are satisfied in first phase and soft constraints in second phase. The main purpose to use this two stage technique is that in first phase hard constraints satisfaction can use more relax search space because in first phase it does not consider soft constraints. In second phase it tries to satisfy soft constraints when maintaining hard constraints satisfaction which are already done in first phase. (...)

This thesis devote itself to use of information system for school agenda administration. Schools are forced to administer big amounts of informations, not only referred to their students. Broad issue is very extensive and disparate, so the most common types of data and demands on school information system operation are stated. The system for automatic generation of timetables is part of the school information system. At the first, basic conceptions of scheduling scope are defined and tied together with them are methods and algorithms for timetable creation problem solving. School timetabling is problem of scheduling lessons with certain limitative conditions. Further, thesis is engaged in design of school information system, data organization in such system and solving of system design problems. Designed information system accentuates on easy expandability and wide range of usage possibilities. Also suggested algorithm for solving of defined school timetabling is stated in this part of thesis.

The research is a study of the efficiency and robustness of genetic algorithm to instances of both discrete and continuous global optimization problems. We developed genetic algorithm based heuristics to find the global minimum to problem instances considered. In the discrete category, we considered two instances of real-world space allocation problems that arose from an academic environment in a developing country. These are the university timetabling problem and hostel space allocation problem. University timetabling represents a difficult optimization problem and finding a high quality solution is a challenging task. Many approaches, based on instances from developed countries, have been reported in the literature. However, most developing countries are yet to appreciate the deployment of heuristics and metaheuristics in handling the timetabling problem. We therefore worked on an instance from a university in Nigeria to show the feasibility and efficiency of heuristic method to the timetabling problem. We adopt a simplified bottom up approach in which timetable are build around departments. Thus a small portion of real data was used for experimental testing purposes. As with similar baseline studies in literature, we employ genetic algorithm to solve this instance and show that efficient solutions that meet stated constraints can be obtained with the metaheuristics. This thesis further focuses on an instance of university space allocation problem, namely the hostel space allocation problem. This is a new instance of the space allocation problems that has not been studied by metaheuristic researchers to the best of our knowledge. The problem aims at the allocation of categories of students into available hostel space. This must be done without violating any hard constraints but satisfying as many soft constraints as possible and ensuring optimum space utilization. We identified some issues in the problem that helped to adapt metaheuristic approach to solve it. The problem is multi-stage and highly constrained. We first highlight an initial investigation based on genetic algorithm adapted to find a good solution within the search space of the hostel space allocation problem. Some ideas are introduced to increase the overall performance of initial results based on instance of the problem from our case study. Computational results obtained are reported to demonstrate the effectiveness of the solution approaches employed. Sensitivity analysis was conducted on the genetic algorithm for the two SAPs considered to determine the best parameter values that consistently give good solutions. We noted that the genetic algorithms perform well specially, when repair strategies are incorporated. This thesis pioneers the application of metaheuristics to solve the hostel space allocation problem. It provides a baseline study of the problem based on genetic algorithms with associated test data sets. We report the best known results for the test instances. It is a known fact that many real-life problems are formulated as global optimization problems with continuous variables. On the continuous global optimization category therefore, we focus on improving the efficiency and reliability of real coded genetic algorithm for solving unconstrained global optimization, mainly through hybridization with exploratory features. Hybridization has widely been recognized as one of the most attractive approach to solving unconstrained global optimization. Literatures have shown that hybridization helps component heuristics to taking advantage of their individual strengths while avoiding their weaknesses. We therefore derived three modified forms of real coded genetic algorithm by hybridizing the standard real-coded genetic algorithm with pattern search and vector projection. These are combined to form three new algorithms namely, RCGA-PS, RCGA-P, and RCGA-PS-P. The hybridization strategy used and results obtained are reported and compared with the standard real-coded genetic algorithm. Experimental studies show that all the modified algorithms perform better than the original algorithm.

No description available.

A geração de grades horárias de qualidade é um fator crítico em qualquer instituição de ensino, tanto em escolas de ensino fundamental/médio como em universidades. Este problema é considerado complexo, pois devem ser relacionados e otimizados diversos recursos, tais como horários, disciplinas, professores e alunos. Em grande parte das instituições de ensino, a geração de grades horárias é realizada manualmente, o que vem a tornar este processo custoso e sujeito a falhas. Diversas abordagens são também encontradas na literatura para resolução deste problema, nas quais foram aplicados métodos de busca estocástica, devido à sua inerente complexidade. As estratégias de busca formuladas e comparadas no presente trabalho foram baseadas no uso de algoritmos genéticos e de sistemas imunológicos artificiais. Tais técnicas foram capazes de fornecer soluções de qualidade para o problema de geração automática de grades horárias. Neste trabalho foram desenvolvidos dois sistemas de apoio à decisão, nos quais foram combinadas técnicas heurísticas aos algoritmos genéticos e ao algoritmo de seleção clonal. O propósito desta investigação é realizar uma análise comparativa entre as duas técnicas a fim de verificar qual delas apresenta resultados mais promissores para a resolução do problema de geração automática de grades horárias. / The generation of timetables with good quality is a critical factor in any educational institution. This is considered a complex problem because it involves several types of information, such as schedules, course subjects, teachers and students. Several search strategies have been applied to solve timetabling problems, whose constraints may vary from one educational institution to another. Most educational institutions still prepare their timetables manually, which is a highly time-consuming process and subjected to errors. Several approaches to solve this problem are also found in technical studies, which use stochastic search methods due to the problems complexity. The search optimization methods used in this work to solve the timetabling problem are genetic algorithms and the clonal selection algorithm, whose satisfactory results when applied to optimization problems are reported in the literature. Two decision support systems were developed in this work, combining heuristic techniques with the genetic algorithms and the clonal selection algorithm. The purpose of this research is to make a comparative analysis of these two techniques in order to determine which one offers the most promising results for solving the timetabling problem.

A geração de grades horárias de qualidade é um fator crítico em qualquer instituição de ensino, tanto em escolas de ensino fundamental/médio como em universidades. Este problema é considerado complexo, pois devem ser relacionados e otimizados diversos recursos, tais como horários, disciplinas, professores e alunos. Em grande parte das instituições de ensino, a geração de grades horárias é realizada manualmente, o que vem a tornar este processo custoso e sujeito a falhas. Diversas abordagens são também encontradas na literatura para resolução deste problema, nas quais foram aplicados métodos de busca estocástica, devido à sua inerente complexidade. As estratégias de busca formuladas e comparadas no presente trabalho foram baseadas no uso de algoritmos genéticos e de sistemas imunológicos artificiais. Tais técnicas foram capazes de fornecer soluções de qualidade para o problema de geração automática de grades horárias. Neste trabalho foram desenvolvidos dois sistemas de apoio à decisão, nos quais foram combinadas técnicas heurísticas aos algoritmos genéticos e ao algoritmo de seleção clonal. O propósito desta investigação é realizar uma análise comparativa entre as duas técnicas a fim de verificar qual delas apresenta resultados mais promissores para a resolução do problema de geração automática de grades horárias. / The generation of timetables with good quality is a critical factor in any educational institution. This is considered a complex problem because it involves several types of information, such as schedules, course subjects, teachers and students. Several search strategies have been applied to solve timetabling problems, whose constraints may vary from one educational institution to another. Most educational institutions still prepare their timetables manually, which is a highly time-consuming process and subjected to errors. Several approaches to solve this problem are also found in technical studies, which use stochastic search methods due to the problems complexity. The search optimization methods used in this work to solve the timetabling problem are genetic algorithms and the clonal selection algorithm, whose satisfactory results when applied to optimization problems are reported in the literature. Two decision support systems were developed in this work, combining heuristic techniques with the genetic algorithms and the clonal selection algorithm. The purpose of this research is to make a comparative analysis of these two techniques in order to determine which one offers the most promising results for solving the timetabling problem.

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.

No description available.

Η παρούσα διπλωματική εργασία πραγματοποιήθηκε κατά το διάστημα 2012-2013 στο Εργαστήριο Συστημάτων Υπολογιστών (CSL) του Πανεπιστημίου Πατρών. Στόχος της εργασίας είναι η επίλυση ενός συνόλου προβλημάτων χρονοπρογραμματισμού εξετάσεων (ETP, Carter Dataset), με χρήση πληροφορημένου γενετικού αλγορίθμου. Στην εργασία αυτή θα παρουσιαστούν, τα βασικά μοντέλα λειτουργίας των γενετικών αλγορίθμων, του ETP καθώς και παρουσίαση βασικών εννοιών των παράλληλων συστημάτων. Τέλος παρουσιάζεται ο σειριακός κώδικας που υλοποιήθηκε σε ANSI-C και στην συνέχεια γίνεται σύγκριση με τον παράλληλο κώδικα που υλοποιήθηκε με MPI-C και παρουσιάζονται τα αποτελέσματα της σύγκρισης μεταξύ των δύο. / The Aim of this thesis which was completed during the 2012/2013 academic year at the Computer Systems Laboratory (CSL) at the University of Patras is to solve a set of Examination Timetabling Problems (Carter Dataset,ETP) with the aid of an informed genetic algorithm. I will present the basic model under which the genetic algorithms operate and some information about the ETP and general parallel systems. To conclude we will present our serial ANSI-C code and compare it with the parallel MPI-C code that we build and compare the two results.

Η παρούσα μεταπτυχιακή εργασία πραγματεύεται το πρόβλημα του σχεδιασμού του ωρολογίου προγράμματος μαθημάτων ενός εκπαιδευτικού ιδρύματος και πιο συγκεκριμένα ενός πανεπιστημίου. Λόγω της πολυπλοκότητας και της ύπαρξης πολυάριθμων μεταβλητών και παραμέτρων το πρόβλημα ανήκει στην κατηγορία των 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.