FERREIRA, Mardson da Silva. Problema do arranjo linear mínimo. 2016. 69 f. Dissertação (Mestrado em Ciência da Computação)-Universidade Federal do Ceará, Fortaleza, 2016. / Submitted by Anderson Silva Pereira (anderson.pereiraaa@gmail.com) on 2017-01-10T20:22:09Z No. of bitstreams: 1 2016_dis_msferreira.pdf: 1134504 bytes, checksum: 8ad24fa36a9ff4306ff861c7a5b40f12 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2017-01-11T15:39:52Z (GMT) No. of bitstreams: 1 2016_dis_msferreira.pdf: 1134504 bytes, checksum: 8ad24fa36a9ff4306ff861c7a5b40f12 (MD5) / Made available in DSpace on 2017-01-11T15:39:52Z (GMT). No. of bitstreams: 1 2016_dis_msferreira.pdf: 1134504 bytes, checksum: 8ad24fa36a9ff4306ff861c7a5b40f12 (MD5) Previous issue date: 2016 / Let G = (V, E) be a simple and undirected graph of set of vertices V and set of edges E. Given an assignment of distinct labels in {1, · · · , |V |} to the vertices of G, for every edge uv ∈ E, we define its weight as the absolute difference of labels given to its end nodes. The minimum linear arrangement problem (MinLA) consists in finding a labeling of the vertices of G such that the sum of the weights of its edges is minimized. MinLA is an NP-Hard problem whose corresponding polyhedron has a factorial number of extreme points. In this work, we investigate a recent quadratic model for the MinLA presenting O(|V |² ) variables and O(|V |² ) constraints. This model has the smallest number of variables and constraints among all models in the literature for the problem. We present some theoretical results for the quadratic model, and show how to obtain a mixed linear model whose optimal solution is the same of the quadratic one. We also present valid inequalities for the proposed models. We discuss two heuristics for the problem and propose a column generation algorithm and a specialized Branch and Bound for MinLA. Computational experiments show that the new quadratic and mixed linear models performed better than existing ones in the literature for new and benchmark instances of this problem. / Seja G = (V, E) um grafo simples e não orientado de conjunto de vértices V e conjunto de arestas E. Dada uma atribuição de rótulos distintos em {1, · · · , |V |} aos vértices de G, para cada aresta uv ∈ E, definimos seu peso como sendo a diferença absoluta entre os rótulos atribuídos às suas extremidades. O problema do arranjo linear mínimo (MinLA) é encontrar uma rotulação dos vértices de G de modo que a soma dos pesos de suas arestas seja mínima. MinLA é um problema NP-Difícil cujo poliedro correspondente tem um número fatorial de pontos extremos. Neste trabalho, investigamos um recente modelo quadrático para o MinLA com O(|V |² ) variáveis e O(|V |² ) restrições. Esse modelo apresenta o menor número de variáveis e restrições dentre todos os modelos da literatura para o problema. Apresentamos alguns resultados teóricos para o modelo quadrático, bem como mostramos como obter um modelo linear misto cuja solução ótima é a mesma do modelo quadrático. Propomos igualmente desigualdades válidas para os modelos propostos. Apresentamos duas heurísticas para o problema. Implementamos um algoritmo de geração de colunas e um Branch and Bound especializado. Experimentos computacionais mostram que o novo modelo teve desempenho superior aos demais modelos conhecidos.

Programa de Pós-Graduação em Ciência da Computação. Departamento de Ciência da Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto. / Submitted by Oliveira Flávia (flavia@sisbin.ufop.br) on 2014-11-20T16:36:46Z No. of bitstreams: 2 license_rdf: 22190 bytes, checksum: 19e8a2b57ef43c09f4d7071d2153c97d (MD5) DISSERTAÇÃO_PrinsMatheurísticaProblemas.pdf: 1066532 bytes, checksum: 4feb1b525e8f414603c45698cea9f6ea (MD5) / Approved for entry into archive by Gracilene Carvalho (gracilene@sisbin.ufop.br) on 2014-11-20T16:39:12Z (GMT) No. of bitstreams: 2 license_rdf: 22190 bytes, checksum: 19e8a2b57ef43c09f4d7071d2153c97d (MD5) DISSERTAÇÃO_PrinsMatheurísticaProblemas.pdf: 1066532 bytes, checksum: 4feb1b525e8f414603c45698cea9f6ea (MD5) / Made available in DSpace on 2014-11-20T16:39:12Z (GMT). No. of bitstreams: 2 license_rdf: 22190 bytes, checksum: 19e8a2b57ef43c09f4d7071d2153c97d (MD5) DISSERTAÇÃO_PrinsMatheurísticaProblemas.pdf: 1066532 bytes, checksum: 4feb1b525e8f414603c45698cea9f6ea (MD5) Previous issue date: 2014 / Uma importante técnica para resolver problemas de otimização é por meio de Programação Inteira Mista (MIP, do inglês Mixed Integer Programming). Uma formulação MIP de um problema envolve um conjunto de variáveis, um conjunto de restrições sobre estas variáveis, um conjunto de restrições de integralidade e uma função objetivo linear a otimizar. Aplicações em otimização inteira são encontradas em diversas àreas do conhecimento, incluindo-se roteamento de veículos, alocação de enfermeiros, programação de horários, entre outros. O uso de métodos heurísticos tem sido empregado na resolução de problemas MIP como uma forma de acelerar o processo de busca na árvore de branching. Este trabalho propõe uma adaptação da heurística MIP Relaxation Induced Neighborhood Search (RINS), que explora a ideia de fixar variáveis de mesmo valor na solução inteira e fracionária corrente. O método proposto, denominado pRINS, explora explicitamente técnicas de pré-processamento, procurando sistematicamente por um número ideal de fixações, visando a produzir sub-problemas de tamanho controlado. As variáveis a fixar são organizadas por meio de um vetor de prioridade, sendo propostas três maneiras de escolha destas variáveis, cada uma delas dando origem a uma variante do método. Em seguida, os problemas são criados e resolvidos de modo semelhante ao método Variable Neighborhood Descent até que um critério de parada seja satisfeito. Os resultados das variantes do método foram comparados com os do resolvedor COIN-OR e CBC stand-alone e com o método RINS original. Pelos resultados obtidos, o método proposto se mostrou com desempenho superior a essas duas técnicas. ______________________________________________________________________________________________ / ABSTRACT: An important technique for solving optimization problems is Mixed Integer Programming (MIP). A MIP formulation for a problem involves a set of variables, a set of constraints on these variables, a set of integrality constraints and a linear objective function to optimize. Applications in integer programming are found in many areas of knowledge, including vehicle routing, traveling salesman problem, nurse scheduling and school timetabling. Heuristic methods have been employed in solving MIP problems as a way to accelerate the search process in the branching tree. This dissertation proposes an adaptation of the MIP heuristic Relaxation Induced Neighborhood Search (RINS), which explores the idea of fixing variables with same value in integer and fractional current solutions. The proposed method, named pRINS, explicitly explores pre-processing techniques, systematically searching for the ideal number of fixations to produce sub-problems of controlled size. Candidate variables to be fixed are ranked and three different strategies to select among them were evaluated. Then, problems are created and solved similarly to the Variable Neighborhood Descent method until a stopping criterion is met. The results of the variants were compared to the COIN-OR CBC stand-alone solver and the original RINS method. The results indicate that pRINS presents a better heuristic behavior than other techniques.

Programa de Pós-Graduação em Ciência da Computação. Departamento de Ciência da Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto. / Submitted by Maurílio Figueiredo (maurilioafigueiredo@yahoo.com.br) on 2015-01-13T18:37:57Z No. of bitstreams: 2 license_rdf: 22190 bytes, checksum: 19e8a2b57ef43c09f4d7071d2153c97d (MD5) DISSERTAÇÂO_NovosAlgoritimos.pdf: 1337200 bytes, checksum: 1e210fd648c651e8b6990d8ededc6a2c (MD5) / Approved for entry into archive by Gracilene Carvalho (gracilene@sisbin.ufop.br) on 2015-01-15T17:28:11Z (GMT) No. of bitstreams: 2 license_rdf: 22190 bytes, checksum: 19e8a2b57ef43c09f4d7071d2153c97d (MD5) DISSERTAÇÂO_NovosAlgoritimos.pdf: 1337200 bytes, checksum: 1e210fd648c651e8b6990d8ededc6a2c (MD5) / Made available in DSpace on 2015-01-15T17:28:11Z (GMT). No. of bitstreams: 2 license_rdf: 22190 bytes, checksum: 19e8a2b57ef43c09f4d7071d2153c97d (MD5) DISSERTAÇÂO_NovosAlgoritimos.pdf: 1337200 bytes, checksum: 1e210fd648c651e8b6990d8ededc6a2c (MD5) Previous issue date: 2014 / Este trabalho trata o Problema de Sequenciamento em Máquinas Paralelas Não- Relacionadas com Tempos de Preparação Dependentes da Sequência (UPMSPST, do inglês Unrelated Parallel Machine Scheduling Problem with Setup Times), objetivando minimizar o makespan. Para resolvê-lo foram desenvolvidos três algoritmos heurísticos e um algoritmo híbrido. O primeiro algoritmo heurístico, denominado HIVP, tem uma solução inicial gerada por um procedimento construtivo parcialmente guloso baseado no método Heuristic-Biased Stochastic Sampling e na regra Adaptive Shortest Processing Time { ASPT. Essa solução e, posteriormente, refinada pelo procedimento Iterated Local Search { ILS, tendo o Random Variable Neighborhood Descent como método de busca local. Além disso, periodicamente a busca é intensificada e diversificada por meio de um procedimento Path Relinking { PR. No segundo algoritmo heurístico, denominado GIAP, a solução inicial é criada por um procedimento inspirado no Greedy Randomized Adaptive Search Procedures. Nesse segundo algoritmo, a solução é refinada por um procedimento ILS que utiliza como método de busca local o procedimento Adaptive Local Search { ALS. A busca _e também intensificada e diversificada por meio de um procedimento PR. O terceiro e último algoritmo heurístico, denominado AIRP, tem sua solução inicial gerada por um procedimento construtivo guloso baseado na regra ASPT. Essa solução é refinada por um procedimento ILS que tem como busca local um procedimento chamado RIV. De forma análoga aos algoritmos anteriores, a busca também passa por uma intensificação ao e diversificação periodicamente por meio de um procedimento PR. O algoritmo híbrido, denominado AIRMP, tem o funcionamento similar ao do algoritmo heurístico AIRP, diferindo deste por acrescentar um módulo de programação linear inteira mista. Para a aplicação desse módulo são selecionados um par de máquinas e subconjuntos de tarefas nessas máquinas. Esses subconjuntos são combinados e passam por uma busca local que consiste em acionar um resolvedor de programação matemática aplicado a melhor das formulações de programação matemática dentre aquelas estudadas e desenvolvidas. Pelos experimentos computacionais foi possível concluir que o AIRP obteve os melhores resultados dentre os algoritmos heurísticos propostos, conseguindo superar vários outros algoritmos da literatura. Também foram realizados experimentos para comparar os algoritmos AIRMP e AIRP. Como o AIRMP necessita de um tempo maior para acionar o módulo de programação matemática, esses experimentos utilizaram um tempo maior de execução. Observou-se, no entanto, que a adição do módulo de programação matemática não melhorou o desempenho do AIRMP no tempo testado e na estrutura utilizada de subconjuntos de tarefas. Esses testes também mostraram que aumentando-se o tempo de processamento do AIRP, o algoritmo e capaz de encontrar melhores soluções. __________________________________________________________________________________________________________________________ / ABSTRACT: This paper deals with the Unrelated Parallel Machine Scheduling Problem with Setup Times { UPMSPST, having as goal to minimize the makespan. In order to solve it, three heuristic algorithms and a hybrid algorithm were developed. The first heuristic algorithm, called HIVP, has an initial solution generated by a greedy constructive procedure based on the Heuristic-Biased Stochastic Sampling and on the Adaptive Shortest Processing Time { ASPT rule. This solution is then refined by the Iterated Local Search { ILS procedure, having the Random Variable Neighborhood Descent as local search method. Moreover, the search is periodically intensified and diversified by a Path Relinking { PR procedure. In the second algorithm, called GIAP, the initial solution is created by a procedure inspired on the Greedy Randomized Adaptive Search Procedures. This solution is then refined by an ILS procedure that uses the procedure Adaptive Local Search { ALS as local search method. The search is also intensified and diversified by a PR procedure. The third and final heuristic algorithm, called AIRP, has its initial solution generated by a greedy constructive procedure based on ASPT rule. This solution is then refined by the ILS, having as local search a procedure called RVI. Analogously to the previous algorithms, the search also applies periodically an intensification and diversification strategy based on the PR procedure. The hybrid algorithm, named AIRMP, is similar to the AIRP heuristic algorithm, differing from it by adding a module of mixed integer linear programming. To apply this module one pair of machines are selected and subsets of jobs of these machines. These subsets are combined and they pass through a local search that consists in running a mathematical programming solver applied to the best formulation among the studied and developed ones. By computational experiments it was concluded that the AIRP algorithm obtained the best results among the proposed heuristic algorithms, outperforming several other algorithms from the literature. Experiments were also conducted to compare the AIRMP and AIRP algorithms. As the AIRMP needs more time to execute the mathematical programming module, these experiments utilized a higher runtime. It was observed, however, that the addition of the mathematical programming module does not improved the performance of the AIRMP algorithm in the tested time and in the used structure of subsets of jobs. These tests also showed that increasing the processing time of the AIRP, the algorithm is able to find better solutions.

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnologico / Made available in DSpace on 2016-01-08T15:22:42Z (GMT). No. of bitstreams: 1 108630.pdf: 2538675 bytes, checksum: cab6d8b3105b4bc04dc8773ff7eccada (MD5) Previous issue date: 1986 / Este trabalho foi elaborado com o objetivo de dar ao Método de Planejamento e Programação Espaço-Tempo um modelo de programação matemática que permita otimizar tempos e custos de obras de construção civil lineares através do uso de computadores. Nele estão formuladas todas as considerações matemáticas que, com o uso de Programação Linear Inteira possibilitam a caracterização da totalidade dos projetos lineares que se apresentam na prática. Com a finalidade de facilitar a implementação computacional do método foi elaborado um programa que gera a partir de dados básicos de projetos as variáveis, restrições e função objetivo no formato compatível com o pacote para solução de programação matemática utilizado. A título de ilustração das técnicas propostas, são resolvidos dois exemplos de obras de porte médio.

Submitted by Haroudo Xavier Filho (haroudo.xavierfo@ufpe.br) on 2015-05-19T18:34:24Z No. of bitstreams: 1 DISSERTAÇÃO MESTRADO ECONOMIA 2015 LUIZ FIGUEIREDO.pdf: 3213365 bytes, checksum: ec667ad5beeadd422176038941b9eaac (MD5) / Made available in DSpace on 2015-05-19T18:34:24Z (GMT). No. of bitstreams: 1 DISSERTAÇÃO MESTRADO ECONOMIA 2015 LUIZ FIGUEIREDO.pdf: 3213365 bytes, checksum: ec667ad5beeadd422176038941b9eaac (MD5) Previous issue date: 2015-03-03 / O presente estudo tem como objetivo estimar as curvas de demanda da água para irrigação dos perímetros irrigados localizados no Submédio do Rio São Francisco. A metodologia utilizada foi à programação matemática positiva, que consiste em um modelo em três estágios para a obtenção dos valores econômicos dá água para diversos cenários de disponibilidade desse recurso (100% até 60%). A partir dos valores econômicos obtidos, foi possível estimar as curvas de demanda da água para a irrigação e os custos de escassez do recurso para os perímetros públicos irrigados. Ademais, diversos cenários de elasticidades de oferta das culturas (de 0.2 até 2.0) e variações no mix de cultura observado em cada perímetro foram propostos com o intuito de verificar os respectivos impactos na demanda de água para irrigação estimada e nos custos de escassez. Os resultados obtidos demonstram o efeito positivo da redução da disponibilidade da água sobre os valores econômicos do recurso em todos os perímetros, obtendo dessa forma, curvas de demanda negativamente inclinadas. Além disso, foi possível verificar variações negativas nos valores econômicos estimados em relação ao valor da elasticidade de oferta das culturas indicada e, também, o impacto do mix de cultura na curva de demanda da água estimada para os perímetros irrigados. Esses resultados podem auxiliar futuros modelos hidroeconômicos a serem aplicados na região.

Made available in DSpace on 2014-06-12T17:35:55Z (GMT). No. of bitstreams: 2 arquivo7268_1.pdf: 1049218 bytes, checksum: ae17b566babf354fdba29edd90d9ecda (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2007 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Desde tempos imemoriais, o homem tem aprendido a lidar com a incerteza na busca de dirimir perdas advindas de fatores imprevisíveis. Várias teorias de probabilidade surgiram na busca de evoluir nesse aprendizado, sendo a teoria de probabilidade proposta por Kolmogorov a mais utilizada. No entanto ela deixa de atender a uma serie de situações. Muito tem sido desenvolvido para trabalhar essas situações nas quais a probabilidade clássica falha como, por exemplo, a capacidade de Choquet, a teoria da evidência de Dampster-Shafer, probabilidades superiores e inferiores, entre outras. Este trabalho continua o desenvolvimento do modelo de representação e cálculo da incerteza introduzido em Campello de Souza (1993), baseado em programação linear, cujos últimos resultados estão em Campello de Souza (2007). O modelo usa famílias de distribuições de probabilidade para representar e quantificar a incerteza. Algumas aplicações do modelo na edução do conhecimento de especialistas foram feitas e um novo indicador para medir a habilidade inferencial dos especialistas foi proposto. O modelo foi utilizado para trabalhar a inferência estatística quando os dados são escassos, trabalhando-se as estimativas de médias de distribuições de probabilidade, as quais foram comparadas com o método da freqüência relativa. O construto Decidabilidade foi usado para medir a associação entre duas variáveis aleatórias. Foi verificado que tal construto é linearmente correlacionado com a correlação de Pearson

Orientador: Jose C. Geromel / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica / Made available in DSpace on 2018-07-21T04:03:45Z (GMT). No. of bitstreams: 1 Oliveira_MauricioCarvalhode_M.pdf: 6359919 bytes, checksum: 960400e58c19c10ffb1d99e0fee0a904 (MD5) Previous issue date: 1996 / Resumo: Esta dissertação é dedicada ao estudo dos mecanismos dos algoritmos de pontos interiores aplicados à resolução de problemas lineares sujeitos a restrições dadas na forma de desigualdades matriciais lineares. Abordam-se tanto aspectos teóricos quanto práticos. De aspecto teórico, encontram-se presentes análises de convergência e complexidade para diversos algoritmos seguidores de trajetória, primais-duais e projetivos, aliados às análises de alguns procedimentos críticos, como a resolução dos problemas de mínimos quadrados e a determinação do passo ótimo, aspectos eminentemente práticos. A título de ilustração, apresenta-se uma série de exemplos de problemas comumente encontrados em programação matemática e, em especial, problemas da área de controle ótimo formulados como LMI / Abstract: The subject of this thesis is the study of the interior point machinery applied to linear problems constrained by linear matrix inequa.lities (LMI). Both theoretical and practical issues are addressed. Of theoretical fiavor, convergence and complexity of several path following, primal-dual and projective algorithms are analyzed; the analysis of some critical procedures, as solving mean-square problems and calculating the optimal step length, stand for the practica.l issues. For the sake of illustration, many mathematical programs and problems from optimal control theory are formulated as LMI / Mestrado / Telecomunicações e Telemática / Mestre em Engenharia Elétrica

Orientador: Paulo Morelato França / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-07-26T23:25:56Z (GMT). No. of bitstreams: 1 Milanez_EduardoMedeiros_M.pdf: 3118600 bytes, checksum: 0d8f4ba53c2cf46dcb543bd1b00ae12d (MD5) Previous issue date: 2000 / Resumo: Uma das etapas da cadeia de fornecimento de produtos derivados de aves como frangos e perus diz respeito ao processo de coleta dos lotes no campo e seu transporte para o abatedouro. Durante este processo, as aves são submetidas a condições extremas de desgaste fisico. Para se reduzir os custos referentes às perdas de peso decorrentes do estresse é necessário minimizar o tempo médio de espera para abate. A programação do serviço de coleta deve, além de perseguir tal objetivo, atender condicionantes próprios do processo tais como coleta ininterrupta das cargas, capacidade de abate das linhas de pendura, estoques de segurança na plataforma de desembarque e tamanho de frota disponível para o transporte. As restrições do problema e sua natureza combinatorial dificultam sua solução. Os programadores da coleta geralmente dispõem de simuladores determinísticos, ferramentas de simulação visual interativa, que os auxiliam na determinação dos horários iniciais de coleta dos lotes que constam dos planos diários de abate. Para garantir soluções de estoque mínimo de segurança em tempo hábil foi desenvolvido uma heurística de construção que implementa uma política de sincronização dos fluxos de chegada e abate. Este procedimento heurístico, objeto central deste trabalho, foi posteriormente incorporado a um simulador atualmente em uso em diversas plantas. A eficácia da heurística na geração de soluções de estoque mínimo é ilustrada através de um estudo de caso. A comparação é feita com soluções otimizadas, obtidas através de programação matemática. Para isto, um modelo do tipo MILP é implementado / Abstract: One of the crucial processes of the poultry industry supply chain involves flocks catching and their transportation to the slaughter house. During the process the birds undergo extreme physical stress. In arder to reduce the costs that relate to stress induced weight loss it is necessary to minimize the average waiting time from arrival to hanging. The catching schedule of the flocks must pursue that goal. It also must take into account specific process constraints such as continuous trucks loading, the hanging lines capacities, the safety stocks requirements and the truck fleet size. These constraints and the combinatorial nature of the problem make it a hard one to solve. The catching schedulers usually make use of deterministic simulators. These interactive visual simulation tools allow them to determine the catching start time for alI flocks in the daily slaughtering plano A constructive heuristic was developed to find a minimum stock solution in a reasonable time. It enforces a sincronization policy for the arrival and hanging birds flows. This procedure was later embedded in a simulator that is currently in use in several plants. The efficacy on generating minimum stock solutions is shown in a case study. Heuristic solutions for small instances were compared to optimized solutions obtained by MILP models / Mestrado / Automação / Mestre em Engenharia Elétrica

Orientador : Arnaldo Vieira Moura / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-02T15:30:06Z (GMT). No. of bitstreams: 1 Yunes_TallysHoover_M.pdf: 6565656 bytes, checksum: 4ef3637ed1584172d24419ae96564bcc (MD5) Previous issue date: 2000 / Resumo: Este trabalho de mestrado procurou estudar e resolver um problema real de escalonamento de mão-de-obra oriundo da operação diária de uma empresa de ônibus urbanos da cidade de Belo Horizonte. Por questões de complexidade, este tipo de problema é normalmente dividido em dois subproblemas, a saber: crew scheduling, que trata a alocação diária de viagens a duplas de funcionários (motorista e cobrador), e crew rostering, que parte da solução do subproblema anterior e constrói uma escala de trabalho de mais longo prazo, e.g. um mês. Cada um desses subproblemas foi abordado utilizando-se técnicas de Programação Matemática e Programação por Restrições. Para o problema de crew scheduling, em particular, desenvolveu-se também um algoritmo híbrido de geração de colunas combinando as duas técnicas mencionadas e cujo desempenho foi significativamente melhor que o dos métodos isolados. Em geral, os modelos matemáticos resultantes de problemas dessa natureza são de grande porte. No caso aqui tratado, a matriz de coeficientes do programa linear associado a algumas instâncias dos problemas chega a conter dezenas de milhões de colunas. Todos os algoritmos propostos para a solução do problema foram implementados e testados sobre dados reais obtidos junto à empresa em questão. A análise dos resultados computacionais mostra que foi possível obter soluções de excelente qualidade em um tempo de computação adequado para as necessidades da empresa. Em particular, para o subproblema de scheduling, foi possível comprovar que as soluções obtidas são ótimas / Abstract: This dissertation aimed at studying and solving a real world crew management problem. The problem considered arises from the daily operation of an urban transit bus company that serves the metropolitan area of the city of Belo Horizonte, in Brazil. Due to its intrinsic complexity, the problem is usualIy divided in two distinct subproblems, namely: crew scheduling, that deals with the daily alIocation of trips to crews, and crew rostering, which takes the solution of the first subproblem and extends the scheduling to a longer planning horizon, e.g. a month. We have tackled each one of these subproblems using Mathematical Programming (MP) and Constraint Logic Programming (CLP) approaches. Besides, we also developed a hybrid column generation algorithm for solving the crew scheduling problem, combining MP and CLP, which performed much better than the two previous approaches when taken in isolation. Real world crew management problems typicalIy give rise to large scale mathematical models. In our case, the coefficient matrix of the linear program associated with some instances of the problem contains tens of millions of columns. AlI the proposed algorithms have been implemented and tested over real world instances obtained from the aforementioned company. The analysis of our experiments indicates that it was possible to find high quality solutions within computational times that are suitable for the company's needs. In particular, we were able to find provably optimal solutions for the crew scheduling problem / Mestrado / Mestre em Ciência da Computação

Orientador : Akebo Yamakami / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-03T03:54:02Z (GMT). No. of bitstreams: 1 Cantao_LuizaAmaliaPinto_D.pdf: 1186821 bytes, checksum: eda2d926b3c608ecd9a61ff5c43bb7ec (MD5) Previous issue date: 2003 / Doutorado