Η εργασία πραγματέυεται τη δημιουργία βοηθητικών εργαλείων για την χρήση δεδομένων από αρχεία xml και την επεξεργασία τους με αλγορίθμους σμήνους για την εξαγωγή συμπερασμάτων. / The current post graduate thesis addresses the issue of school timetabling problem through the usage of PSO algorithms. In order to achieve greater efficiency complementary tool have been designed and developed.

El presente trabajo muestra la implementación de metodologías basadas en modelos de optimización para resolver el problema de programación de horarios de clases y asignación de salas para la Facultad de Ingeniería de la Universidad Diego Portales. Los métodos utilizados en este trabajo integran la programación de los horarios de las clases de cátedra y de las clases auxiliares de todos los cursos de jornada diurna que se dictan en la Facultad, con su respectiva asignación de salas. Para resolver el problema se implementaron tres metodologías basadas en modelos de programación lineal entera. La primera metodología consiste en un modelo único que pretende resolver el problema completo, cumpliendo con todas las condiciones impuestas por la Facultad, basando sus decisiones en la asignación de cada una de las clases a algún bloque horario y a una sala disponible. La segunda metodología consiste en dos modelos: el primero, para resolver la programación de horarios de clases y el segundo, para resolver la asignación de salas. Ambos modelos operan en forma secuencial, basando sus decisiones en la asignación de cada una de las clases a algún bloque horario y a una sala disponible. La tercera metodología utiliza el concepto de grupos de bloques horarios, que consiste en conjuntos de uno, dos o tres bloques horarios de la semana. Esta metodología se basa en un modelo único que resuelve la problemática completa basando sus decisiones en la asignación de todas las clases de cátedra o auxiliares de un curso a un grupo de bloques horarios y a una sala disponible. Las metodologías segunda y tercera se pretenden utilizar en semestres posteriores para llevar a cabo esta labor de manera automática y evitar ineficiencias de la actual programación manual. Los resultados obtenidos se resumen como una programación de horarios que cumple con todos los requerimientos exigidos y una asignación de salas que cumple con los requisitos de capacidad de cada curso. El tiempo de resolución del problema es inferior a una hora.

No description available.

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.

- / The main topic of this thesis is the combination of metaheuristics and other methods for solving combinatorial optimization problems (COPs). In particular, focus is given in a special category of COPs known as timetabling problems. Timetabling problems belong in general to the class of NP-hard problems meaning that exact methods are usually unable to solve problem instances with sizes of practical importance. In the first three chapters optimization problems are analyzed and four major disciplines regarding optimization approaches are examined: Mathematical Programming, Artificial Intelligence, Computational Intelligence and Metaheuristics. Borders are not always clear between them while a recent trend is to hybridize approaches originating from the same or different disciplines. Even with the progress in optimization that occurred during the last decades programming successful optimization application still is an intricate mission. Nevertheless, software developing techniques, open source software and exploitation of the processing power of modern hardware can assist in constructing applications that are expected to be of much benefit for their users. Key ideas of achieving this are described in Chapter 4. The first application, presented in Chapter 5, is a pump scheduling system for a water distribution network. The objective is to achieve a way of operation for the pumps of each reservoir that results in diminished electricity cost. A model of the problem was constructed and the metaheuristic technique of genetic algorithms with the addition of several heuristics solved the problem. The second application, presented in Chapter 6, is the examination timetabling problem for Universities. Educational timetabling problems in general attract much interest from the scientific community. Our approach targeted various models of the examination timetabling problem and constituted by two major phases: construction and improvement. A number of metaheuristics were hybridized (Simulated Annealing, GRASP, VNS, Taboo Search and others) while certain sub-problems were solved using exact methods (Integer Programming). The results that we achieved in known datasets for evaluating the performance of such methods were most promising. In particular, for the publicly available datasets of the second International Timetabling Competition our approach achieved the best published score for 6 out of 8 datasets. The third application, presented in Chapter 7, is the construction of timetables for Greek high schools. A model of the problem that had publicly available problem instances and published results was used. Better results were able to be obtained by reformulating the problem and subsequently using a branch and cut approach implemented using entirely open source software. In summary, successful results of our approaches suggest that metaheuristics and hybridized metaheuristics with other metaheuristic or exact methods appears to be a promising research direction for handling complex combinatorial optimization problems.

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.

Rail track operators have traditionally used manual methods to construct train timetables. Creating a timetable can take several weeks, and so the process usually stops once the first feasible timetable has been found. It is suspected that this timetable is often far from optimal. Existing methods schedule track maintenance once the best train timetable has been determined and allow little or no adjustments to the timetable. This approach almost certainly produces suboptimal integrated solutions since the track maintenance schedule is developed with the imposition of the previously constructed train timetable. The research in this thesis considers operationally feasible methods to produce integrated train timetables and track maintenance schedules so that, when evaluated according to key performance criteria, the overall schedule is the best possible. This research was carried out as part of the Cooperative Research Centre for Railway Engineering and Technologies. We developed a method that uses a local search meta-heuristic called 'problem space search'. A fast dispatch heuristic repeatedly selects and moves a track possessor (train or maintenance task) through the network; this results in a single integrated schedule. This technique generates a collection of alternative feasible schedules by applying the dispatch heuristic to different sets of randomly perturbed data. The quality of the schedules is then evaluated. Thousands of feasible solutions can be found within minutes. We also formulated an integer programming model that selects a path for each train and maintenance task from a set of alternatives. If all possible paths are considered, then the best schedule found is guaranteed to be optimal. To reduce the size of the model, we explored a reduction technique called 'branch and price'. The method works on small example problems where paths are selected from a predetermined set, but the computation time and memory requirements mean that the method is not suitable for realistic problems. The main advantages of the problem space search method are generality and speed. We are able to model the operations of a variety of rail networks due to the representation of the problem. The generated schedules can be ranked with a user-defined objective measure. The speed at which we produce a range of feasible integrated schedules allows the method to be used in an operational setting, both to create schedules and to test different scenarios. A comparison with simulated current practice on a range of test data sets reveals improvements in total delay of up to 22%.

This thesis investigates the use of local search methods in solving constraint problems. Such problems are very hard in general and local search offers a useful and successful alternative to existing techniques. The focus of the thesis is to analyze the techniques of invariants used in local search. The use of invariants have recently become the cornerstone of local search technology as they provide a declarative way to specify incremental algorithms. We have produced a series of program libraries in C++ known as the One-Way-Solver. The One-Way-Solver includes the implementation of incremental data structures and is a useful tool for the implementation of local search. The One-Way-Solver is applied to two challenging constraint problems, the Boolean Satisfiability Testing (SAT) and university course timetabling problems.

Rail track operators have traditionally used manual methods to construct train timetables. Creating a timetable can take several weeks, and so the process usually stops once the first feasible timetable has been found. It is suspected that this timetable is often far from optimal. Existing methods schedule track maintenance once the best train timetable has been determined and allow little or no adjustments to the timetable. This approach almost certainly produces suboptimal integrated solutions since the track maintenance schedule is developed with the imposition of the previously constructed train timetable. The research in this thesis considers operationally feasible methods to produce integrated train timetables and track maintenance schedules so that, when evaluated according to key performance criteria, the overall schedule is the best possible. This research was carried out as part of the Cooperative Research Centre for Railway Engineering and Technologies. We developed a method that uses a local search meta-heuristic called 'problem space search'. A fast dispatch heuristic repeatedly selects and moves a track possessor (train or maintenance task) through the network; this results in a single integrated schedule. This technique generates a collection of alternative feasible schedules by applying the dispatch heuristic to different sets of randomly perturbed data. The quality of the schedules is then evaluated. Thousands of feasible solutions can be found within minutes. We also formulated an integer programming model that selects a path for each train and maintenance task from a set of alternatives. If all possible paths are considered, then the best schedule found is guaranteed to be optimal. To reduce the size of the model, we explored a reduction technique called 'branch and price'. The method works on small example problems where paths are selected from a predetermined set, but the computation time and memory requirements mean that the method is not suitable for realistic problems. The main advantages of the problem space search method are generality and speed. We are able to model the operations of a variety of rail networks due to the representation of the problem. The generated schedules can be ranked with a user-defined objective measure. The speed at which we produce a range of feasible integrated schedules allows the method to be used in an operational setting, both to create schedules and to test different scenarios. A comparison with simulated current practice on a range of test data sets reveals improvements in total delay of up to 22%.

A construção de grades horárias dos cursos de uma universidade é um problema que deve ser enfrentado no início de todos os semestres e, por mobilizar quantidades significativas de recursos, se constitui numa das mais importantes tarefas administrativas de uma universidade. Trata-se de um problema clássico, combinatório, que tem atraído atenção por conta da dificuldade de se encontrar boas soluções. É classificado, em termos de complexidade computacional, como NP-hard, o que implica grande exigência de capacidade de processamento. É modelado de maneiras muito diversas, no intuito de se obter adequação quanto ao contexto educacional do país, às regras específicas da instituição ou aos objetivos específicos dos gestores, entre outros. Foi feita uma revisão de literatura no intuito de apoiar a modelagem do problema, nesse trabalho, e de contribuir com a comunidade de pesquisadores sobre o tema ao agregar informações a respeito das pesquisas publicadas até então. O problema é modelado, neste trabalho, por meio de técnicas de Pesquisa Operacional com o objetivo de produzir grades horárias com aulas distribuídas uniformemente ao longo da semana, em uma primeira etapa, para que, na etapa seguinte, ao se atribuir salas de aula às turmas, a utilização dos espaços físicos da Universidade seja otimizada. Dados foram coletados de uma instituição federal de ensino superior para a implementação do modelo. Resultados obtidos no processamento com os dados reais mostraram que o modelo reduz consideravelmente a utilização de salas de aula. / The timetabling construction for University courses is a problem that must be faced at each beginning of semester and, since it mobilizes significant amounts of resources, it constitutes in one of the most important administrative tasks in a University. It's a classic, combinatorial problem that has attracted attention due to its difficulty in finding good solutions. In terms of computational complexity, it's classified as NP-hard, which involves great processing capacity. It's modeled in a number of different ways, aimed to obtain adequacy to the educational context of the country, to the specific higher education institutional rules, or to the specific managers goals, amongst others. A literature review was performed, aimed to support, in this research, the problems modeling, and to contribute to the researchers community, adding the research information published so far. The problem is modeled, in this work, by means of Operations Research techniques, aiming to produce evenly distributed timetables along the week, in the first step, and to assign the classrooms to the groups of students in the next, in such a way that the physical spaces utilization of the University is optimized. Data was collected from a federal higher education institution in order to implement de model. Results obtained through its processing with this data showed that the model considerably reduces the classrooms utilization.