Submitted by Reginaldo Soares de Freitas (reginaldo.freitas@ufv.br) on 2017-02-10T15:29:30Z No. of bitstreams: 1 texto completo.pdf: 2736980 bytes, checksum: f41dd8d979519bbcc7b9d7350c591432 (MD5) / Made available in DSpace on 2017-02-10T15:29:30Z (GMT). No. of bitstreams: 1 texto completo.pdf: 2736980 bytes, checksum: f41dd8d979519bbcc7b9d7350c591432 (MD5) Previous issue date: 2016-09-21 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / In this study we apply single-objective and bi-objective parallel heuristics to solve broad and realistic formulations of the travel planning problem. Given a travel time window and a set of destinations with their corresponding dwelling times, the goal of our single-objective approach is to find a route that produces a budget travel’s itinerary, involving flights, hotels and departure/arrival times. In turn, our bi-objective approach adds a complexity level in the problem’s formulation once we are seeking for a Pareto set of detailed travel itineraries, which are both cost and time efficient. When the sequence of cities is fixed, the single-objective version of the problem is commonly modeled in literature as a time-dependent network and the best itinerary is computed using shortest path algorithms. However, in this study, finding the order of cities that minimizes the total cost, and besides that, a set of good trade-off solutions, are also goals. Therefore, our single-objective formulation stands for a TDSPP (Time Dependent Shortest Path Problem) embedded in the TSP (Travel Salesman Problem) whereas our bi-objective formulation stands for a TDSPP embedded in a bi-objective TSP. On the first formulation we apply an ILS (Iterated Local Search) heuristic and on the second formulation we apply the NSGA-II (Nondominated Sorting Genetic Algorithm II) framework. For performance assessing, the results of both heuristics were compared to the results of corresponding exact methods with no time constraints. All test cases simulate realistic travel itineraries and run upon real-world travel data collected in advance, besides having to comply with an execution threshold of approximately 1 minute. For 285 single-objective test cases, our ILS heuristic was able to reach solutions in average less than 4.1% divergent from an exact implementation, besides reaching the optimal solution in about 30% of the test cases. In turn, for 180 bi-objective test cases, our NSGA-II implementation was able to reach an approximated solution in average up to 8% divergent from an exact implementation. / Nesse trabalho são aplicadas heurísticas paralelas mono-objetivas e bi-objetivas para solucionar formulações abrangentes e realistas do problema de planejamento de viagens. Dado o intervalo de tempo que uma viagem pode ocorrer e um conjunto de destinos com seus respectivos tempos de permanência, a abordagem mono-objetiva procura determinar um itinerário de baixo custo que compreenda voos, hotéis e horários de partida/chegada. Por sua vez, a abordagem bi-objetiva adiciona complexidade a formulação do problema, uma vez que pretende determinar o conjunto Pareto de itinerários de viagem capazes de equilibrar custo e tempo. Quando a sequência de cidades é fixa, a versão mono-objetiva do problema é comumente modelada na literatura como uma rede dependente do tempo e o melhor itinerário é calculado usando algoritmos de caminho míınimo. Contudo, nesse trabalho, determinar a ordem de visitação das cidades também é um objetivo. Portanto, a formulação mono-objetiva proposta representa um TDSPP (Time Dependent Shortest Path Problem) incorporado ao TSP (Travel Salesman Problem) e a formulação bi-objetiva representa um TDSPP incorporado em um TSP bi-objetivo. Na primeira formulação foi aplicada a heurística ILS (Iterated Local Search) e na segunda formulação o framework NSGA-II (Nondominated Sorting Genetic Algorithm II). Os resultados de ambas as heurísticas foram comparados com os resultados produzidos por métodos exatos executados sem restrições temporais. Todos os casos de teste simulam itinerários de viagem realistas e foram executados em um banco de dados de viagens e hospedagens coletadas com antecedência. Além disso, independentemente da abordagem utilizada, estabeleceu-se que o tempo de execução de cada caso deve ser de aproximadamente 1 minuto. A heurística ILS proposta para a versão mono-objetiva do problema foi executada em 285 instâncias e alcançou, em média, soluçõoes no máximo 4.1% divergentes de uma implementa ̧ao exata, além de atingir a melhor solução em cerca de 30% dos casos de teste. Por sua vez, o framework NSGA-II foi capaz de produzir soluções no máximo 8% divergentes da implementação exata para 180 instâncias.

SOARES, Joel Cruz. O problema da atribuição conexa. 2016. 96 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-11T20:06:15Z No. of bitstreams: 1 2016_dis_jcsoares.pdf: 739371 bytes, checksum: 4e1d4ee45a126992e8308bc1b1333469 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2017-01-12T12:52:08Z (GMT) No. of bitstreams: 1 2016_dis_jcsoares.pdf: 739371 bytes, checksum: 4e1d4ee45a126992e8308bc1b1333469 (MD5) / Made available in DSpace on 2017-01-12T12:52:08Z (GMT). No. of bitstreams: 1 2016_dis_jcsoares.pdf: 739371 bytes, checksum: 4e1d4ee45a126992e8308bc1b1333469 (MD5) Previous issue date: 2016 / We present a problem with application in resource allocation in mobile networks, that we name Connected Assignment in Arrays (CAA). This problem has as input a set of symbols $I=\{1,2,\dots,M\}$, an array $v$ indexed by $J=\{1,2,\dots,N\}$, and a gain value $\rho_{ij}$ of allocating $i \in I$ to position $j$ of $v$. We want to find an assignment of symbols to positions so as to maximize the gain, under the constraint that repeated symbols are adjacent in the array. We demonstrate that CAA is an NP-Hard problem by a reduction from the Convex Path Recoloring Problem (CPR). We present an approximate algorithm for a particular case of this problem ($k$-CAA). We propose three ILP formulations and theoretically compare their linear relaxation. We study the polyhedron $\mathcal{P}$ associated with the tightest formulation. We determine all facet-defining inequalities with right-hand side equal to 1 and show that they suffice, together with the non-negativeness constraints, to describe $\mathcal{P}$ when $M=2$ or $N=2$. We generalize this class of valid inequalities while keeping the property of being facet inducing. Finally, we propose 5 heuristics for the problem and compare them by results of computational experiments. / Apresentamos um problema com aplicação em alocação de recursos em redes de comunicações móveis, que denominamos de Problema da Atribuição Conexa em Vetores (ACV). Este problema tem como entrada um conjunto de símbolos $I=\{1,2,\dots,M\}$, um vetor $v$ indexado por $J=\{1,2,\dots,N\}$, e um valor de ganho $\rho_{ij}$ ao alocar $i \in I$ à posição $j$ de $v$. Desejamos encontrar uma atribuição dos símbolos ao vetor que tenha o maior ganho possível, sob a restrição de que símbolos repetidos sejam adjacentes no vetor. Demonstramos que ACV é um problema NP-Difícil a partir de uma redução do Problema de Recoloração Convexa de Caminhos (RCC). Apresentamos um algoritmo aproximativo para um caso particular deste problema ($k$-ACV). Propomos três formulações de Programação Inteira e comparamos teoricamente suas relaxações lineares. Estudamos o poliedro $\mathcal{P}$ associado à formulação mais forte. Determinamos todas as desigualdades indutoras de facetas com lado direito igual a 1 e mostramos que elas, junto com as restrições de não-negatividade, descrevem $\mathcal{P}$ quando $M=2$ ou $N=2$. Generalizamos essa classe de desigualdades válidas, mantendo a propriedade de que induzem facetas. Ao final, propomos 5 heurísticas para o problema e as comparamos através de resultados de experimentos computacionais.

Submitted by Reginaldo Soares de Freitas (reginaldo.freitas@ufv.br) on 2016-04-26T17:01:30Z No. of bitstreams: 1 texto completo.pdf: 6402016 bytes, checksum: 2ad43c5bb42a77cb19379857a960b47d (MD5) / Made available in DSpace on 2016-04-26T17:01:30Z (GMT). No. of bitstreams: 1 texto completo.pdf: 6402016 bytes, checksum: 2ad43c5bb42a77cb19379857a960b47d (MD5) Previous issue date: 2015-12-08 / Fundação de Amparo à Pesquisa do Estado de Minas Gerais / O Problema do Caixeiro Viajante Preto e Branco (PCV-PB) é uma generalização do Problema do Caixeiro Viajante (PCV), definido sobre um grafo onde os vértices são classificados como pretos ou brancos. Assim como o clássico PCV, o objetivo do PCV-PB é encontrar um ciclo hamiltoniano de custo mínimo, entretanto, duas restrições adicionais são consideradas. Enquanto que a restrição de cardinalidade restringe o número de vértices brancos entre dois vértices pretos consecutivos, a restrição de comprimento restringe a distância máxima entre os mesmos. Apli- cações do PCV-PB podem ser observadas no escalonamento de aeronaves e em configurações de redes de telecomunicações. A proposta deste estudo é analisar diferentes estratégias heurísticas aplicadas para o PCV-PB. Heurísticas construtivas da literatura foram aperfeiçoadas e uma nova estratégia para a construção da solução foi apresentada. Neste contexto foi utilizado métodos como Lin kernighan e Inserção Específica de Brancos. Além disso, foram propostas abordagens heurísticas baseadas nas metaheurísticas GRASP, VND, ILS e SA. Diversos experimentos computacionais foram realizados para comparar a eficácia das abordagens. Os resultados garantem a aplicabilidade dos algoritmos propostos para o problema. / The Black and White Traveling Salesman Problem (TSP-BW) is a generalization of the Travelling Salesman Problem (TSP), set on a graph where the vertices are classified as black or white. As in the classical PCV, a solution of the TSP-BW is a Hamiltonian cycle of minimal cost. However, two additional constraints are considered. While the cardinality constraint limits the number of white vertices between two consecutive black vertices, the length constraint restricts the maximum distance therebetween. Applications of TSP-BW can be observed in aircraft scheduling and telecommunications network settings. The purpose of this study is to analyze different heuristic strategies applied to TSP-BW. Literature constructive heuristics have been improved and a new strategy for building the solution was presented. In this context it used methods such as Lin Kernighan and Inserção Específica de Brancos. Also, it has been proposed heuristic approaches based on metaheuristics GRASP, VND, ILS and SA. Several computational experiments were performed to compare effectiveness of approa- ches. The results ensure the applicability of the proposed algorithms to the problem.

Submitted by Marco Antônio de Ramos Chagas (mchagas@ufv.br) on 2016-05-20T10:07:57Z No. of bitstreams: 1 texto completo.pdf: 1339770 bytes, checksum: 7dd1c4a83b676fbbc188832448791a81 (MD5) / Made available in DSpace on 2016-05-20T10:07:57Z (GMT). No. of bitstreams: 1 texto completo.pdf: 1339770 bytes, checksum: 7dd1c4a83b676fbbc188832448791a81 (MD5) Previous issue date: 2011-08-03 / O presente trabalho trata o problema de sequenciamento de tarefas em máquinas paralelas não relacionadas. No problema abordado, é oonsiderado tanto o tempo de preparação das máquinas, o qual depende da sequência de produção, quanto o tempo de processamento das tarefas, que dependem das máquinas. Cada tarefa possui uma data de entrega que deve ser comprida, caso contrário uma penalidade é aplicada. O objetivo do problema é minimizar a soma de penalidades por atraso e adiantamento das tarefas. Em termos praticos, as penalidades por adiantamento são consequências de custos gerados pela necessidade de estocagem, enquanto as penalidades por atraso das tarefas são originadas de multas contratuais. Primeiramente é utilizado um modelo matemático de programação linear inteira mista (PLIM) para representar o problema. Este modelo é resolvido pelo software de otimização CPLEX 12.0. Em seguida é utilizado um algoritmo baseado no método Greedy Randomized Adaptive Search Procedure (GRASP) com o objetivo de determinar soluções aproximadas de boa qualidade. Após isso, o método GRASP é hibridizado com o procedimento de intensificação Path Relink- mg (PR) e o método Iterated Local Search (ILS), resultando nas heurísticas híbridas GRASP+ILS, GRASP+PR e GRASP+ILS+PR. As heurísticas foram testadas em conjuntos de instâncias de pequeno, médio e grande porte. Os resultados obtidos pelas heurísticas utilizadas são comparados entre si. A análise dos resultados obtidos mostra que a hibridização da heurística GRASP faz com que o desempenho do procedimento melhore. / This work deals with the problem of sequencing jobs on parallel unrelated machines. In the addressed problem, it was considered both the setup time of the ma- chines, which depends on the job sequence and the processing time of the jobs, which depends on the machines. Each job has a due date which should finish processing, oth- erwise a penalty is applied. The objective of the problem is to minimize the sum of job penalties for tardiness and earliness. Practically, penalties for earliness are consequence of cost generated by storage while penalties for tardiness are originated from contrac- tual fines. First, it was used a mathematical model, mixed integer linear programming (MILP), to represent the problem. Such model was solved by the optimization soft- ware GPLEX 12.0. Following, an algorithm based on the Greedy Randomized Adaptive Search Procedure (GRASP) was utilized in order to determine approximate solutions of good quality. After this, the procedure was hybridized with the intensification pro- cedure Path Relinking (PR) and the Iterated Local Search (ILS) heuristic, resulting in the hybrid heuristics GRASP + ILS, GRASP+PR and GRASP+ILS+PR. These heuristics were tested on sets of instances of small, medium and large size. Results ob- tained though the heuristics were compared among themselves. Obtained results show that the hybridization of GRASP heuristic can increase the procedure’s performance. / Dissertação antiga

O problema de escalonamento num flow shop (ou flow shop scheduling problem, FSSP) é um modelo de sistemas de produção muito comum que é bem estudado na literatura. No entanto, quase toda a literatura foca-se em escalonamentos permutacionais, desconsiderando soluções ótimas e quase ótimas que são escalonamentos não-permutacionais. Além disso, a prática comum padroniza os tempos de processamento de cada operação, mesmo que estes tempos variem dependendo das diferentes capacidades dos operadores das máquinas, cuja diversidade deve ser considerada no processo de escalonamento quando seja significativa, e.g., em centros de emprego para deficientes (CEDs). Nesta tese, propomos métodos para resolver o FSSP não-permutacional, usando o mesmo tempo e esforço que os métodos do estado da arte usam para o FSSP permutacional, e produzindo escalonamentos não-permutacionais com melhor qualidade do que escalonamentos permutacionais e não-permutacionais produzidos por métodos do estado da arte. Também propomos métodos para resolver o problema combinado de designação de trabalhadores heterogêneos e escalonamento de tarefas num flow shop (ou heterogeneous workforce assignment and flow shop scheduling problem, Het-FSSP), produzindo soluções que compensam as diferentes capacidades e deficiências dos trabalhadores com pequenas perdas nos objetivos da produção. Além do mais, a designação de trabalhadores heterogêneos pode ser integrada em outros problemas de escalonamento, como fizemos com o problema combinado de designação de trabalhadores heterogêneos e escalonamento de tarefas num job shop (ou heterogeneous workforce assignment and job shop scheduling problem, Het-JSSP). / The flow shop scheduling problem (or FSSP) is a very common model of production systems that is well studied in the literature. However, almost all the literature focuses on the permutation FSSP, disregarding optimal and near optimal solutions that are non-permutation schedules. Besides, common practice standardizes the processing times of each operation, even when those times may vary depending on different capabilities of the machine operators, whose diversity must be considered in the scheduling process when it is significant, e.g., in Sheltered Work centers for Disabled (SWDs). In this thesis, we propose methods to solve the non-permutation FSSP, using the same time and effort as state-of-the-art methods for the permutation FSSP, and producing non-permutation schedules with better quality than permutation and non-permutation schedules produced by state-of-the-art methods. We also propose methods to solve the combined heterogeneous workforce assignment and flow shop scheduling problem (or Het-FSSP), producing solutions that compensate the different capabilities and disabilities of the workers with minor or null losses in the productivity objectives. Moreover, the heterogeneous workforce assignment may be integrated into other shop scheduling models, as we did with the heterogeneous workforce assignment and job shop scheduling problem (or Het-JSSP) with similar results.

Made available in DSpace on 2016-08-29T15:39:01Z (GMT). No. of bitstreams: 1 tese_7557_Leonardo Rogério Binda da Silva.pdf: 4189335 bytes, checksum: 9b77cb2bc79d6f88555dd532f0f4d83a (MD5) Previous issue date: 2014-03-14 / O petróleo é atualmente o combustível mais utilizado no mundo. Recuperá-lo com a maior viabilidade econômica possível é uma busca incessante das companhias produtoras. Nesse cenário, a simulação numérica de reservatórios utilizando computadores paralelos de memória distribuída (clusters) desponta como uma importante ferramenta. Esses aplicativos manipulam malhas de pontos discretizados que representam o domínio do reservatório de petróleo. Uma etapa importante da simulação utilizando clusters é o particionamento dessa malha para que cada um dos nós processadores possa executar seus cálculos sobre uma porção da mesma. As malhas de domínio podem ser representadas por grafos. Particionar malhas, então, torna-se um problema de particionamento de grafos. Caso o número de vértices do grafo que representa a malha seja muito elevado, particionadores seriais podem apresentar problemas de desempenho. Particionadores de grafos utilizando clusters surgem como alternativas interessantes nessa situação, minimizando os tempos gastos nos particionamentos. Trata da implementação de um particionador paralelo de grafos para ser utilizado em clusters baseado nas Heurísticas de particionamento propostas e implementadas de maneira serial por Bonatto (2010). O particionador paralelo foi desenvolvido utilizando a linguagem de programação Java e a biblioteca de passagem de mensagens MPJ Express. Tipos abstratos de dados eficientes foram propostos e implementados para que o desempenho fosse otimizado. O particionador de grafos paralelo realizou o corte de diversos grafos, obtendo em sua grande maioria cortes menores do que os encontrados pelo particionador serial de Bonatto (2010) e por programas como o METIS e o CHACO. Melhorias ao particionador serial de Bonatto (2010) foram propostas. Análises de speedup e eficiência paralela foram realizadas para constatar os ganhos de tempos obtidos com a paralelização das heurísticas.

Submitted by Patricia Barros (patricia.barros@ufes.br) on 2016-05-13T17:16:07Z No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Rotas Tecnológicas para o aproveitamento de resíduo agrícola - otimização estrutural e tecnológica pelo método heurístico.pdf: 1501845 bytes, checksum: b8c8c82e53301f42548d2113d2626e0f (MD5) / Approved for entry into archive by Patricia Barros (patricia.barros@ufes.br) on 2016-05-13T17:16:26Z (GMT) No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Rotas Tecnológicas para o aproveitamento de resíduo agrícola - otimização estrutural e tecnológica pelo método heurístico.pdf: 1501845 bytes, checksum: b8c8c82e53301f42548d2113d2626e0f (MD5) / Made available in DSpace on 2016-05-13T17:16:26Z (GMT). No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Rotas Tecnológicas para o aproveitamento de resíduo agrícola - otimização estrutural e tecnológica pelo método heurístico.pdf: 1501845 bytes, checksum: b8c8c82e53301f42548d2113d2626e0f (MD5) / CAPES / A avaliabilidade de resíduos agrícolas para geração de bioenergia vem se destacar como interesse recente por parte do setor de agroenergia. Para essa finalidade, esse trabalho de dissertação realiza-se um estudo bibliográfico de caracterização de resíduos da casca do cacau, coco e café; para adequação às tecnologias de biodigestão anaeróbia, pirólise e combustão direta. Avalia-se as possibilidades de rotas tecnológicas para a transformação do potencial energético inerente à composição dos resíduos de fruta em energia elétrica. O objetivo é direcionado à síntese estrutural de processos químicos pela representação do problema por meio de árvores de estado. A partir da combinação dos elementos de estudo envolvidos: resíduos frutíferos, tecnologias de beneficiamento da biomassa e tecnologias de conversão química; são propostas as possibilidades de rotas tecnológicas para composição dos ramos das árvores de estado. A etapa de otimização estrutural é direcionada à aplicação do método heurístico em relação ao problema de síntese. Dessa forma, é selecionada a rota tecnológica mais promissora de aproveitamento energético de cada resíduo. Como resultado, a biodigestão anaeróbia em reator do tipo batelada se mostrou a rota química mais promissora para o resíduo da casca de cacau. Para o resíduo da casca de coco, a rota química adequada foi a combustão direta, realizada em caldeira de grelha fixa; e para o resíduo da casca de café, a rota de conversão termoquímica do tipo pirólise precedida de peletização se mostrou mais promissora. Como contribuição, cabe destacar a possibilidade de valoração energética de resíduos frutíferos até então considerados inúteis para o setor energético. A representação do problema pela sistemática de árvores de estado e posterior resolução pela aplicação de regras heurísticas demonstra a originalidade do trabalho proposto. / The availability of agricultural waste for bioenergy generation come to propose the recent interest by agroenergy sector. For this goal, this dissertation show a bibliografic study for waste characterization of cocoa bark, coconut bark and coffee bark in according to bioenergy technologies: anaerobic digestion, pyrolisys and direct combustion. Its made analysis of technology route possibilities for transform the energy potencial from fruit waste composition in electric energy. The objective its towards the structural synthesis of chemical process by problem representation with process state trees. From the combination of elements of study: fruit waste, biomass processing technology and chemical conversion technologies; its proposed the possibilities of technology routes for elaborate the branches of state trees. The step of structural optimization its based in applied the heuristics method towards the syntesys problem. Thus, its selected the most promised technology route of energetic use of each waste. As a result, the anaerobic digestion in batch reactor was the better option for cocoa bark. For a coconut bark, the chemistry route more adequated was the direct combustion, realized in boiled fixed grid; and for a coffee bark, the thermochemical pyrolysis conversion preceded by pelletization compactation showed more promised. As contribution from this work of dissertation stands out the possibility of energetic valorization of fruit waste untill then considered useless for energetic sector. The problem representation by systematic of state trees and after applied solution by heuristics rules show the originality from this proposed work.

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-07T16:35:24Z No. of bitstreams: 2 license_rdf: 20592 bytes, checksum: 0c9b9c579af4cbbcf785ca803bd18d4b (MD5) DISSERTAÇÃO_AlgoritmoBaseadoMetaheurística.pdf: 2705222 bytes, checksum: fd00f5395b864397a2989217cec92430 (MD5) / Approved for entry into archive by Gracilene Carvalho (gracilene@sisbin.ufop.br) on 2014-11-07T16:52:21Z (GMT) No. of bitstreams: 2 license_rdf: 20592 bytes, checksum: 0c9b9c579af4cbbcf785ca803bd18d4b (MD5) DISSERTAÇÃO_AlgoritmoBaseadoMetaheurística.pdf: 2705222 bytes, checksum: fd00f5395b864397a2989217cec92430 (MD5) / Made available in DSpace on 2014-11-07T16:52:21Z (GMT). No. of bitstreams: 2 license_rdf: 20592 bytes, checksum: 0c9b9c579af4cbbcf785ca803bd18d4b (MD5) DISSERTAÇÃO_AlgoritmoBaseadoMetaheurística.pdf: 2705222 bytes, checksum: fd00f5395b864397a2989217cec92430 (MD5) Previous issue date: 2014 / Este trabalho trata um problema particular de planejamento de lavra de uma mineradora localizada no quadrilátero ferrífero do Estado de Minas Gerais, Brasil. Neste problema há um conjunto de frentes de lavra, um conjunto de equipamentos de carga de diferentes produtividades, um conjunto de caminhões de diferentes capacidades e um conjunto de pontos de descarga para o material lavrado. Cada frente de lavra é subdividida em blocos, os quais, por sua vez, são subdivididos em sub-blocos. Cada sub-bloco pode conter um dentre quatro tipos de material: hematita, canga, itabirito e estéril. Além disso, cada sub-bloco somente pode ser lavrado se os sub-blocos precedentes tiverem sido totalmente lavrados. A cada ponto de descarga está associada uma meta de produção e uma qualidade de material a ser atendida. O objetivo é determinar a alocação das carregadeiras aos blocos e o número de viagens que cada caminhão deve fazer a cada sub-bloco, saindo de um determinado ponto de descarga, de forma a atender as metas de produção e qualidade estabelecidas para cada descarga. Para resolvê-lo foi desenvolvido um algoritmo heurístico baseado nas metaheurísticas Greedy Randomized Adaptive Search Procedures (GRASP) e Late Acceptance Hill-Climbing (LAHC). O algoritmo explora o espaço de soluções usando busca locais autoadaptativas. Experimentos computacionais comparam os resultados do algoritmo proposto com aqueles do otimizador LINGO aplicado a um modelo de programação linear inteira mista e mostram a efetividade da proposta. ________________________________________________________________________________________________ / ABSTRACT: This work deals with a particular problem of mine planning at a mining company located in the Iron Quadrangle of Minas Gerais, Brazil. In this problem there is a set of pit mining, a set of loader equipment of different yields, a set of trucks of different capacities and a set of delivery points for the discharge of materials. Each pit is subdivided into blocks, which, in turn, are subdivided into sub-blocks. Each sub-block can contain one of four types of material: hematite, canga, itabirito and waste. Furthermore, each sub-block can only be drawn up if the preceding sub-blocks have been fully drawn up. Every point of discharge is associated with a production and quality targets of material to be answered. The objective is to determine the allocation of loaders to blocks and the number of trips that each truck must do for each sub-block, leaving a certain point of discharge in order to meet production and quality targets requirements for each discharge. A heuristic algorithm, based on the metaheuristics Greedy Randomized Adaptive Search Procedures and Late Acceptance Hill-Climbing, was developed in order to solve this problem. The algorithm explores the solution space using self-adaptive local search. Computational experiments compare the results of the proposed algorithm with those of the optimizer LINGO model applied to a mixed integer linear programming and show its effectiveness.

Hoy en día, de los costos de logística de las empresas, más de la mitad corresponden a costos de transporte, siendo uno de los problemas importantes a resolver el del ruteo de vehículos (VRP), que consiste en determinar las mejores rutas para entregar – desde una bodega - productos o servicios a los clientes quienes están dispersos geográficamente. Existen muchos programas comerciales que lo resuelven, pero son de un alto precio, sobre todo para las pymes. Es así que se hace necesario entregar una solución de bajo costo, por ejemplo a través del reuso de componentes de software. Uno de los enfoques más usados son los frameworks, que son una arquitectura de software incompleta que el desarrollador adapta a las necesidades del problema específico. En este trabajo se desarrolló un framework orientado a objetos para el problema de ruteo de vehículos, a partir de diversos esquemas UML que se implementaron. El mecanismo de desarrollo fue similar al de un software sólo que siempre había que tener en mente que se debía abstraer a un problema VRP lo más genérico posible. En específico se desarrolló un completo diagrama de clases del problema, que comprende los métodos de resolución del problema. En esta tesis se estudiaron en específico las heurísticas que son el enfoque más difundido. También se desarrolló un mecanismo de mapeo entre métodos de solución y problemas, que permite asociar un problema específico con una heurística específica que lo resuelve. Para comprobar el funcionamiento del framework se desarrolló un software que lo instanciara. Con este software se realizaron algunas pruebas con problemas aleatorios e instancias conocidas del VRP, obteniendo buenos resultados. Finalmente se hizo un análisis costo-beneficio que mostró que el reuso de software es una alternativa viable económicamente, en comparación con desarrollar múltiples programas. Como trabajo futuro queda comprobar que otros desarrolladores puedan usar el framework de manera fácil, y para el dominio que aquí se definió. Por otro lado sería interesante desarrollar frameworks para otros problemas de gestión de operaciones como: asignación de tripulación o ubicación de instalaciones.

Problemas de escalonamento ocorrem com freqüência, principalmente em empresas de manufatura. Entretanto, na maioria das vezes, ferramentas matemáticas de apoio à decisão são pouco utilizadas, pois requerem profissionais capacitados, softwares caros e computadores muito potentes. Esta dissertação tem como objetivo mostrar uma heurística capaz de reduzir a quantidade de fôrmas na indústria calçadista. Inicialmente, foram comparadas as soluções fornecidas pela heurística com as soluções obtidas a partir do modelo matemático de programação linear, com a finalidade de verificar o quão próximas estão ambas as respostas. Em seguida, foram comparadas a solução fornecida pela heurística e a solução presentemente adotada por uma empresa de calçados denominada de Empresa de Calçados X. Os principais resultados obtidos foram: a) o resultado fornecido pela heurística apresenta menos de 10% de acréscimo no número de pares de fôrmas em relação ao resultado fornecido pelo modelo matemático de programação linear inteira tipo 0/1; b) a solução fornecida pela heurística reduz, em média, 23,4% a quantidade de fôrmas necessárias, podendo chegar próximo a 40%. Isto pode trazer uma estimativa de redução anual na ordem de R$ 288.100,00; c) o percentual de redução na quantidade de pares de fôrmas é variável, dependendo de cada caso.