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. (...)

Submitted by JOSIANE SANTOS DE OLIVEIRA (josianeso) on 2018-01-31T14:48:27Z No. of bitstreams: 1 Roberto da Silva Araujo_.pdf: 903723 bytes, checksum: ae702a685139c36126c0bfef5f707282 (MD5) / Made available in DSpace on 2018-01-31T14:48:27Z (GMT). No. of bitstreams: 1 Roberto da Silva Araujo_.pdf: 903723 bytes, checksum: ae702a685139c36126c0bfef5f707282 (MD5) Previous issue date: 2017-10-31 / Nenhuma / Neste trabalho é apresentado um Algoritmo Híbrido (AH) aplicado ao Problema de Roteamento de Veículos com Múltiplos Depósitos e Frota Heterogênea (PRVMDFH). Um conjunto de clientes é atendido por um número fixo de veículos de diferentes tamanhos, por múltiplos depósitos, sujeito a restrições da capacidade do veículo. As meta-heurísticas utilizadas na construção do AH são o Algoritmo Genético (AG) e a Busca Tabu (BT). O AG usa operadores de cruzamento Mapeado Parcialmente (PMX), Cromossomo de Duas Partes (TCX) e de Ordem (OX), o operador de mutação Troca e o Algoritmo de Busca Local (ABL). A BT usa os métodos de Troca, Retirada e Inserção e Deslocamento. São analisadas as políticas de diversificação no ABL e a intensificação com as estratégias de geração de vizinhança na BT. São utilizados conjuntos de dados padrões de problemas testes, para executar os algoritmos propostos. Os resultados obtidos, comparados a outros autores, apresentaram boas soluções para diferentes tamanhos de problemas testes. / This paper presents a Hybrid Algorithm (AH) applied to the Problem of Vehicle Routing with Multiple-Deposit and Heterogeneous Fleet (MDFHPRV). A number of customers are served with a fixed number of vehicles of different sizes by multi-depot, subject to capacity constraints of the vehicle. The meta-heuristics used in AH construction are Genetic Algorithm (GA) and Tabu Search (BT). The AG uses Partial Mapped Crossover (PMX), Two Part Chromosome Crossover (TCX) and Order Crossover (OX) operators, the Exchange mutation operator, and the Local Search Algorithm (ABL). BT uses the Exchange, Retrieve, and Insertion and Displacement methods. Diversification policies was analyzed in the ABL and the intensification with the neighborhood generation strategies in BT. Standard sets of test problems are used to execute the proposed algorithms. The obtained results, compared to other authors, presented good solutions for different sizes of test problems.

Submitted by JOSIANE SANTOS DE OLIVEIRA (josianeso) on 2018-04-12T13:49:50Z No. of bitstreams: 1 Deborah Luisa Detânico Vieira_.pdf: 1504339 bytes, checksum: 49a2adc770aff79d216c818e22dea099 (MD5) / Made available in DSpace on 2018-04-12T13:49:50Z (GMT). No. of bitstreams: 1 Deborah Luisa Detânico Vieira_.pdf: 1504339 bytes, checksum: 49a2adc770aff79d216c818e22dea099 (MD5) Previous issue date: 2017-05-17 / Nenhuma / Com a crescente demanda de serviços de voz e, principalmente, dados móveis se fez necessário o desenvolvimento das tecnologias de quarta geração (4G). O padrão Long Term Evolution (LTE), desenvolvido pela Third Generation Partnership Project (3GPP), foi escolhido pela International Telecommunications Union (ITU) como tecnologia para atender os requisitos da quarta geração de serviços móveis. Para as operadoras inserirem esta nova tecnologia em suas redes existentes, se faz necessário um estudo meticuloso de planejamento, muito embora, na prática, este planejamento seja desenvolvido de forma empírica. O problema de planejamento de redes é conhecido e bem estudado no ramo da computação, conhecido como problema de recobrimento de conjuntos e classificado, pela sua complexidade, como NP-difícil. Dadas as características diferenciadas da arquitetura da rede do LTE, este trabalho busca resolver o problema de planejamento de redes de quarta geração (4G), utilizando uma modelagem matemática aplicada a uma metaheurística híbrida, composta de Algoritmo Genético e Busca Tabu. Almejase resolver o problema de cobertura de uma determinada região, cobrindo a maior área possível com o menor número possível de Base Stations (BS), visando ao planejamento com maior assertividade e redução do custo de implantação da rede 4G. / With the constantly demand of voice services and mostly in mobile data, there was the need the development of the mobile services of fourth generation (4G). The pattern Long Term Evolution, developed by the Third Generation Partnership Project (3GPP) was chosen by the International Telecommunications Union (ITU) as technology to attend the requirements of the fourth generation of mobile services. For the mobile operators introduce and apply this new generation in their own existing networks, they need to do an extensive research and planning, even if, in practical means, it is applied using the empirical way. The network planning problem is widely known and studied in computing area as set-covering problem ans classified as NPhard. Due the unique characteristics of network architecture of LTE, this work aims to solve the mobile’s fourth generation planning problem using a mathematics modelling apply to a hybrid metaheuristics, composed with Genetic Algorithm and Tabu Search. It aims solve the coverage problem of a specific region, covering the largest area possible with the fewest number of Base Sations (BS) possible, seeking the best compliance and cost reduction of the LTE network deployment.

Submitted by William Justo Figueiro (williamjf) on 2015-07-08T20:56:12Z No. of bitstreams: 1 03b.pdf: 3126214 bytes, checksum: 0f98dbf86ae74816af91944aa7dec80f (MD5) / Made available in DSpace on 2015-07-08T20:56:12Z (GMT). No. of bitstreams: 1 03b.pdf: 3126214 bytes, checksum: 0f98dbf86ae74816af91944aa7dec80f (MD5) Previous issue date: 2013 / Nenhuma / A qualidade perceptual alcançada pelos codificadores de áudio depende diretamente da escolha de seus parâmetros. O codificador MPEG-4 AAC (Advanced Audio Coding), utilizado no Sistema Brasileiro de Televisão Digital (SBTVD), possui em sua estrutura uma etapa composta por um laço de iteração para escolher os parâmetros do codificador, de maneira dinâmica durante o processo de codificação. Este processo de escolha pode ser definido como um problema de Pesquisa Operacional, sendo um problema de Seleção de Partes, denominado como o Problema de Codificação AAC. A estrutura existente no codificador de referência, não resolve este problema de maneira ótima. Desta forma, este trabalho propõe o desenvolvimento e implementação de um modelo de uma estrutura de simulação, para encontrar os parâmetros do codificador de áudio MPEG-4 AAC, de maneira a otimizar a qualidade perceptual do áudio, para uma determinada taxa de bits (bit rate). A implementação da estrutura de otimização foi desenvolvida em linguagem C, utilizando as metaheurísticas Busca Tabu e Algoritmo Genético em uma estrutura híbrida. Através da minimização da métrica ANMR (Average Noise-to-Mask Ratio), o algoritmo procura identificar a melhor configuração dos parâmetros internos do codificador MPEG-4 AAC, de maneira que possa garantir uma qualidade perceptual para o sinal áudio. Os resultados obtidos utilizando a estrutura híbrida de otimização apresentaram valores menores para a métrica ANMR, ou seja, uma melhor qualidade perceptual de áudio, quando comparados com os resultados obtidos com o codificador de referência MPEG-4 AAC. / The perceptual quality achieved by audio encoders depends directly on the choice of its parameters. The MPEG-4 AAC (Advanced Audio Coding), used in the Brazilian Digital Television System (BDTS), has a step in its structure that consists in iteration loop to choose the parameters of the encoder dynamically during the encoding process. This selection process can be defined as a problem of Operational Research, being a Part Selection Problem, termed as AAC Encoding Problem. The structure in the reference encoder not solves this problem optimally. Thus, this paper proposes the development and implementation of a model simulation of a structure, to find the internal parameters of the MPEG-4 AAC audio encoder, so as to optimize the perceptual audio quality for a given bit rate. The implementation of the optimization framework was developed in ANSI C programming language, using the Tabu Search and Genetic Algorithm metaheuristics in a hybrid structure. Through the minimization of the ANMR (Average Noise-to-Mask Ratio) metric, the algorithm tries to identify the best configuration of internal parameters of the MPEG-4 AAC. The results obtained using the optimization hybrid structure achieve lower values for the ANMR metric, i.e., an better perceptual audio quality, compared with the obtained with the reference encoder MPEG-4 AAC.

Submitted by Silvana Teresinha Dornelles Studzinski (sstudzinski) on 2016-06-10T15:26:09Z No. of bitstreams: 1 Joel da Silva Gonçalves Júnior_.pdf: 1935811 bytes, checksum: 2c6b67ad91c1de26271d67142ef7721b (MD5) / Made available in DSpace on 2016-06-10T15:26:09Z (GMT). No. of bitstreams: 1 Joel da Silva Gonçalves Júnior_.pdf: 1935811 bytes, checksum: 2c6b67ad91c1de26271d67142ef7721b (MD5) Previous issue date: 2016-03-07 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / O transporte marítimo mercante desempenha um papel fundamental para a economia de uma nação, ligando a produção ao consumo. No cenário de expansão do transporte marítimo, a utilização de contêineres para organização das cargas confere maior facilidade, segurança e rapidez ao transporte, aumentando, assim, a produtividade dos terminais e dos navios. No entanto, a operação de navios porta-contêineres possui limitações de movimentação e de estabilidade que impactam no custo operacional de um terminal portuário. Como os guindastes só podem acessar as pilhas de contêineres a partir do topo, a realização de remoções desnecessárias de contêineres bloqueantes gera um custo adicional de movimentação e de tempo nas operações de carga e descarga. Desta forma, faz-se necessária a elaboração de um plano de estiva eficiente para estas atividades, minimizando tanto os remanejamentos quanto a instabilidade da embarcação. Este estudo propõe uma abordagem híbrida, elaborada através da combinação das metaheurísticas Algoritmo Genético e Busca Tabu, utilizando a codificação da solução baseada em regras, a fim de elaborar uma ferramenta computacional que faça a gestão do número de remanejamentos e da instabilidade da embarcação, que são objetivos conflitantes. Nos experimentos, as metaheurísticas puras foram comparadas ao algoritmo híbrido e os resultados comprovaram que a aplicação hibridizada apresenta uma eficiência maior do que as metaheurísticas puras. As diferentes configurações de regras assumidas mostraram que a proposta de um número maior de regras, em complemento àquelas propostas na literatura, implica em melhores resultados. Através da aplicação da abordagem com múltiplos objetivos, foi possível observar a importância de considerar a movimentação e a estabilidade no plano de estiva. Com os resultados obtidos, demonstrou-se que o uso da abordagem proposta gera soluções melhores que as encontradas até o momento na literatura. / The merchant shipping perform a fundamental role in the economy of a nation, by linking production to consumption. In shipping expansion scenario, the use of containers for cargo organizing provides greater facility, safety and velocity, thus increasing the productivity of terminals and ships. However, the use of container ships has handling and stability limitations that affect the operating cost of a port terminal. As the cranes can only access the container stacks from the top, carrying out unnecessary removals of blocking containers generates an additional cost of handling and time in loading and unloading operations. Thus, it is necessary to elaborate an efficient stowage plan for loading and unloading operations, minimizing both the shifting and the instability of the vessel. This study proposes an hybrid approach developed by the combination of Genetic Algorithms and Tabu Search metaheuristics, using a rules-based encoding for solution representation, in order to create a computational tool that manage both the rehandling and instability, which are conflicting. In the experiments, pure metaheuristics were compared to the hybrid algorithm and the results demonstrate that the hybridization presents greater efficiency than the pure metaheuristics. The different rules configuration have proven that the proposal of a greater number of rules, in addition to those proposed in the literature, implies better results. The application of a multiple objectives approach has proven the importance of considering the handling and stability in the stowage plan. With the results, it was showed that the use of the proposed approach produces better solutions than those found in the literature.

Submitted by Rosivalda Pereira (mrs.pereira@ufma.br) on 2017-06-23T20:42:44Z No. of bitstreams: 1 CesarCasteloBranco.pdf: 11257769 bytes, checksum: 911c33f2f0ba5c1c0948888e713724f6 (MD5) / Made available in DSpace on 2017-06-23T20:42:44Z (GMT). No. of bitstreams: 1 CesarCasteloBranco.pdf: 11257769 bytes, checksum: 911c33f2f0ba5c1c0948888e713724f6 (MD5) Previous issue date: 2016-12-12 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPQ) / This work proposes new methodologies to optimize the choice of the parameters of the proportionate normalized least-mean-square (PNLMS) adaptive algorithms. The proposed approaches use procedures based on two optimization methods, namely, the golden section and tabu search methods. Such procedures are applied to determine the optimal parameters in each iteration of the adaptation process of the PNLMS and improved PNLMS (IPNLMS) algorithms. The objective function for the proposed procedures is based on the a posteriori estimation error. Performance studies carried out to evaluate the impact of the PNLMS and IPNLMS parameters in the behavior of these algorithms shows that, with the aid of optimization techniques to choose properly such parameters, the performance of these algorithms may be improved in terms of convergence speed for the identification of plants with high sparseness degree. The main goal of the proposed methodologies is to improve the distribution of the adaptation energy between the coefficients of the PNLMS and IPNLMS algorithms, using parameter values that lead to the minimal estimation error of each iteration of the adaptation process. Numerical tests performed (considering various scenarios in which the plant impulse response is sparse) show that the proposed methodologies achieve convergence speeds faster than the PNLMS and IPNLMS algorithms, and other algorithms of the PNLMS class, such as the sparseness controlled IPNLMS (SC-IPNLMS) algorithm. / Neste trabalho, novas metodologias para otimizar a escolha dos parâmetros dos algoritmos adaptativos LMS normalizados proporcionais (PNLMS) são propostas. As abordagens propostas usam procedimentos baseados em dois métodos de otimização, a saber, os métodos da razão áurea e da busca tabu. Tais procedimentos são empregados para determinar os parâmetros ótimos em cada iteração do processo de adaptação dos algoritmos PNLMS e PNLMS melhorado (IPNLMS). A função objetivo adotada pelos procedimentos propostos é baseada no erro de estimação a posteriori. O estudo de desempenho realizado para avaliar o impacto dos parâmetros dos algoritmos PNLMS e IPNLMS no comportamento dos mesmos mostram que, com o auxílio de técnicas de otimização para escolher adequadamente tais parâmetros, o desempenho destes algoritmos pode ser melhorado, em termos de velocidade de convergência, para a identificação de plantas com elevado grau de esparsidade. O principal objetivo das metodologias propostas é melhorar a distribuição da energia de ativação entre os coeficientes dos algoritmos PNLMS e IPNLMS, usando valores de parâmetros que levam ao erro de estimação mínimo em cada iteração do processo de adaptação. Testes numéricos realizados (considerando diversos cenários nos quais a resposta impulsiva da planta é esparsa) mostram que as metodologias propostas alcançam velocidades de convergência superiores às dos algoritmos PNLMS e IPNLMS, além de outros algoritmos da classe PNLMS, tais como o algoritmo IPNLMS com controle de esparsidade (SCIPNLMS).

La localisation des personnes et des objets à l’intérieur des bâtiments basée sur les réseaux WLAN connaît un intérêt croissant depuis quelques années ; ce système peut être un parfait complément pour fournir des informations de localisation statique ou dynamique dans des environnements où les techniques de positionnement telles que GPS ne sont pas efficaces. Le manuscrit de thèse propose une nouvelle approche pour définir un système WLAN de positionnement indoor (WLAN-IPS) comme un problème d'optimisation combinatoire afin de garantir à la fois une qualité de communication et une minimisation de l'erreur de positionnement via le réseau. Cette approche est caractérisée par plusieurs questions difficiles que nous abordons en trois étapes.Dans un premier temps, nous avons conçu un réseau WLAN-IPS et mis en œuvre une plateforme de test. Nous avons examiné la performance du système sous diverses contraintes expérimentales et nous nous sommes penchés sur l'analyse des relations entre l'erreur de positionnement et les facteurs environnementaux externes. Ces relations ont permis de proposer des indicateurs pour évaluer l'erreur de positionnement. Ensuite nous avons proposé un modèle physique qui définit tous les paramètres majeurs rencontrés en WLAN-IPS à partir de la littérature. L'objectif initial des infrastructures WLAN étant de fournir un accès radio de qualité au réseau, nous avons introduit un objectif supplémentaire qui est de minimiser l'erreur de localisation dans le contexte IPS. Deux indicateurs principaux ont été définis afin d'évaluer la qualité de service (QoS) et l'erreur de localisation pour LBS (Location-Based Services). Enfin après avoir défini la formulation mathématique du problème d'optimisation et les indicateurs clés de performance, nous avons proposé un algorithme mono-objectif et un algorithme multicritère basés sur Tabu Search et Variable Neighborhood Search pour fournir des bonnes solutions en temps raisonnable. Les simulations montrent que ces deux algorithmes sont très efficaces pour le problème d'optimisation que nous avons posé. / Indoor Positioning Systems (IPS) using the existing WLAN have won growing interest in the last years, it can be a perfect supplement to provide location information of users in indoor environments where other positioning techniques such as GPS, are not much effective. The thesis manuscript proposes a new approach to define a WLAN-based indoor positioning system (WLAN-IPS) as a combinatorial optimization problem to guarantee the requested communication quality while optimizing the positioning error. This approach is characterised by several difficult issues we tackled in three steps.At first, we designed a WLAN-IPS and implemented it as a test framework. Using this framework, we looked at the system performance under various experimental constraints. Through these experiments, we went as far as possible in analysing the relationships between the positioning error and the external environmental factors. These relationships were considered as evaluation indicators of the positioning error. Secondly, we proposed a model that defines all major parameters met in the WLAN-IPS from the literature. As the original purpose of the WLAN infrastructures is to provide radio communication access, we introduced an additional purpose which is to minimize the location error within IPS context. Two main indicators were defined in order to evaluate the network Quality of Service (QoS) and the positioning error for Location-Based Service (LBS). Thirdly, after defining the mathematical formulation of the optimisation problem and the key performance indicators, we proposed a mono-objective algorithm and a multi-objective algorithm which are based on Tabu Search metaheuristic to provide good solutions within a reasonable amount of time. The simulations demonstrate that these two algorithms are highly efficient for the indoor positioning optimization problem.

本研究以單一汽車貨運業者的角度，評估當運輸需求大於自有車輛服務能力時，考量車種、時窗、貨物量等因素，以最小化成本為目標進行途程規劃，利用運輸水平整合、協同合作的概念，將未能滿足之需求任務委外給其他同業進行。 本研究主要分為兩階段，第一階段先確認是否需要委外，以禁忌搜尋法找出最節省成本之配送途程以及委外任務，解決業者選擇以自有車輛運送或委外給其他運輸業者服務的問題；而第二階段則是在確定委外的任務後，決定委外的對象，不僅考量對方出價，也評估對方的營運能力、商譽、風險管理、服務品質等因素，建構一多準則決策模式，透過網路程序分析法(ANP)決定評選準則權重，再利用VIKOR排序法決定各個方案之排序，希望能在不遺失客戶訂單及信任的期許下，決定最適合的委外對象。 / From the perspective of trucking carriers, concerning transport horizontal integration and collaboration, when the vehicles are insufficient to meet the demand of transport, carrier could seek for other carrier’s help. In this study, we consider vehicle types, capacity, time windows, and the objective of minimum cost, to do vehicle route planning, and also decide which tasks should be outsoursed. There are two phases in this study. First, after checking the insufficiency of own trucks, we use Tabu search to solve Vehicle Routing Problem with a Private fleet and a Common carrier (VRPPC) in order to find out the route of own vehicles and the tasks to be outsourced. In second phase, we will select the carrier to do those tasks. We not only consider the price of outsourcing, but also evaluate the capacity, service quality, risk management, and the goodwill of the company. We use Analytic Network Process (ANP) to decide the weight of each criterion, and VIKOR to rank each case and select the best one.

本論文針對多廠區訂單分配（Multi-plant order allocation）問題進行探討，此問題模式下企業擁有多間製造不同產品之工廠，且生產成本、產能、運送成本等也各自不同，因此這些因素都必須納入訂單分配時的考量。研究中同時考量三個目標：製造成本、配送前置時間和工廠平均產能利用率之均衡性，利用層級分析法（AHP）將三者進行結合，以達到多目標規劃。除了提出此模型架構外，並以基因演算法（Genetic Algorithm）結合層級分析法進行問題的求解，以達到最佳的分配方式，而為了加強求解的品質與效率，利用禁忌搜尋法（Tabu Search）來改善演化過程中，對於產生不可行解的處理方式。在研究最後，將計算結果與過去研究成果作比較，顯示採用基因演算法混合禁忌搜尋法，在求解多廠區訂單分配問題時，可以得到較佳的結果。

By definition, all projects are unique / however R&amp / D projects have specific characteristics that make them harder to manage. The project management methodology applied to R&amp / D projects may show differences due to the categorization of them. But if there exists a categorization of projects, one can analyze the properties of the project classes and then manage similar projects similarly. In this study, the R&amp / D projects of a main military electronics company of Turkey, are analyzed. Tun&ccedil / (2004) has developed a methodology for clustering the projects of this electronics company. Continuing from his studies, a methodology for determining the class of a new project of this electronics company is developed. For defining the projects in a project space, a Project Identification Card (PIC) is developed. The measurement scale of the PIC is constructed by using the absolutemeasurement Analytic Hierarchy Process. A clustering Tabu Search algorithm is generated for using in the sensitivity analyses of the clusters to projects. And a methodology for determining the cluster of a new project is developed.