O trabalho apresentado nesta dissertação é referente ao estudo da evacuação de pessoas, mais especificamente, a evacuação predial faseada. O objetivo é determinar, para instâncias de até 25 andares, os instantes de liberação de cada grupo de pessoas, a fim de minimizar o tempo total de evacuação do edifício. No entanto, a determinação destes instantes deve considerar o risco ao qual os diferentes grupos estão submetidos, priorizando a evacuação do andar afetado. Além disso, os conflitos de diferentes grupos por espaço nas rotas de evacuação também devem ser evitados, já que, são nessas situações que acontecem grande parte dos acidentes. Para atingir tal objetivo, foi elaborado um modelo matemático de programação linear inteira. Devido à alta complexidade do modelo, fez-se necessária a aplicação de métodos heurísticos para a obtenção de soluções. Dessa maneira, foram desenvolvidas uma heurística de busca baseada em GRASP e uma heurística lagrangeana. Apesar da heurística lagrangeana atestar a qualidade da solução (a partir da comparação do resultado obtido com o limitante inferior), a heurística de busca mostrou-se mais adequada para o problema, pois forneceu resultados de qualidade com pouco esforço computacional. / This dissertation studies the evacuation of people, more specifically, building phased evacuation. The objective of this study is to determine, for buildings of up to 25 floors, in which instants each group of people has to be released, in order to minimize the total evacuation time. Furthermore, the determination of these instants has to consider the risk to which each group of people is submitted, thus the affected floor has to be the first group to be released. In addition, conflicts for space between groups should be avoided, since such situations increase the occurrences of accidents. To achieve this goal, an integer linear programming model was designed. Due to the high complexity of the model, it was necessary to apply heuristics to obtain solutions for some instances. Therefore, a search heuristic based on GRASP and a lagrangian heuristic were developed. Despite the fact that the lagrangian heuristic attests to the quality of the solution (when it is compared to the lower bound), the search heuristic was considered more suitable for this problem because it provided quality results with lower computational efforts.

Neste trabalho foi desenvolvido um modelo de programação linear inteira mista para localização das instalações da rede logística do biodiesel no Brasil, de forma a que se possa, com sua aplicação, avaliar o potencial de produção de oleaginosas no país, assim como identificar as zonas mais promissoras para a localização dos diversos elos da cadeia do biodiesel, a partir da demanda gerada pela mistura de um percentual de biodiesel ao diesel fóssil. O modelo incorpora quatro elos da cadeia produtiva (fase agrícola, extração de óleo, produção de biodiesel e pontos de demanda). Os parâmetros do modelo foram estimados com base em informações reais de mercado disponíveis (base de dezembro/2007). Obteve-se com a aplicação do modelo a diversos cenários, os municípios mais indicados para produção das oleaginosas, as oleaginosas utilizadas, o volume de produção em cada local e, por fim, a localização e porte das fábricas de óleo e das usinas de biodiesel. Análises de sensibilidade de alguns parâmetros foram executadas para verificação do comportamento do modelo face a incertezas. O trabalho incorpora sugestões e recomendações para aprimoramento do modelo. / In this research a mixed integer linear programming model was developed to locate facilities related to the biodiesel supply chain in Brazil, making possible to evaluate the oleaginous production potential, as well as the most promising regions to became the location of the several levels of the biodiesel chain, in accordance to the biodiesel future demand. The model incorporates four levels of the productive chain (agricultural phase, extraction of oil, biodiesel production and demand points). The model parameters were estimated based on market information available (base of december/2007). The application of the model to several sceneries led to the indication of the most promising regions for production of the oleaginous, the used oleaginous ones, the volume of production in each place and, finally, the location and scale of oil and biodiesel factories. Sensibility analyses were conducted to verify the results related to parameters uncertainty. The research contains suggestion and recommendations for improvement of the model.

CoordenaÃÃo de AperfeiÃoamento de Pessoal de NÃvel Superior / No problema do Caminho MÃnimo com RestriÃÃo ProbabilÃstica de Atraso MÃximo visamos considerar o fator tempo no projeto de rotas de transporte de cargas em malhas viÃrias a custo mÃnimo, atentando à crescente incerteza nos tempos de percurso dessas rotas em malhas reais, e observÃ-lo tendo em mente estratÃgias de qualidade de serviÃo, de forma a obtermos um compromisso entre o custo de percurso e a conformidade ao prazo de chegada ao destino. Realizamos um estudo de problemas relacionados na literatura da Ãrea de otimizaÃÃo em redes de transporte, de forma a tentarmos conhecer melhor o problema a ser estudado, sobre o qual nÃo tomamos conhecimento de trabalhos existentes. Desenvolvemos um esquema para enumeraÃÃo de partiÃÃes do espaÃo de soluÃÃes do problema, que utiliza uma decomposiÃÃo em L para selecionar partiÃÃes de forma inteligente, e que à auxiliado por soluÃÃes de relaxaÃÃes do problema de forma a obter cotas para o custo Ãtimo. AlÃm disso, desenvolvemos algumas estratÃgias de ramificaÃÃo e de poda para um esquema de Branch-and-Bound, com uma fase de prÃ-processamento, de forma a tentar resolver o problema diretamente. Os resultados computacionais obtidos demonstram que somos competitivos com a ferramenta comercial utilizada para comparaÃÃo em instÃncias de menor porte para o problema. Para as demais instÃncias, essa ferramenta se mostrou mais eficiente quanto ao tempo necessÃrio para a resoluÃÃo. / In the Probabilistic Delay Constrained Shortest Path problem we aim to consider the time factor in the design of cargo routing paths in road networks at minimum cost, considering the increasing uncertainty in travel times of these routes in real networks, and keeping in mind strategies of quality of service, in order to obtain a compromise between the travel costs and the compliance of the arrival time at the destination. We conducted a study of related problems in the literature of transport networks optimization, in order to better understand the problem to be addressed, about which we are not aware of existing works. We developed a scheme for enumerating partitions of the solution space of this problem, which uses an L decomposition to select these partitions wisely, and is aided by solutions to relaxations of the problem to obtain bounds for the optimal cost. In addition, we developed some branching and pruning strategies for a Branch-and-Bound scheme, with a pre-processing phase, in order to try and solve the problem directly. The computational results show that we are competitive with the commercial tool used for comparison in the smaller instances. For the remaining instances, this tool is more efficient in the time required for solving the problem.

CoordenaÃÃo de AperfeiÃoamento de Pessoal de NÃvel Superior / O presente trabalho propÃe uma forma de apresentaÃÃo aos alunos do ensino bÃsico alguns conceitos associados ao conjunto dos nÃmeros inteiros tais como, divisibilidade, MDC,MMC, congruÃncias e somas de quadrados de uma maneira mais pragmÃtica e menos abstrata. Apresentando-os atravÃs de formas visuais ou de problemas contextualizados com nossa realidade fÃsica mais imediata, favorecendo o melhor entendimento dos axiomas, operaÃÃes e propriedades por aqueles alunos como tambÃm novos mÃtodos de conduta para os professores a fim de que suas tarefas nos processos ensino-aprendizagem se tornem mais fÃceis. / This paper proposes a way of presenting to primary pupils some concepts associated with the set of integers such as divisibility, GCD, LCM, congruences and sums of squa-res in a more pragmatic and less abstract way. Presenting them through visual forms or contextualized problems with our physical reality more immediate, favoring a better understanding of the axioms, operations and properties for those students as well as new methods of conduct for teachers so that their work processes teaching become easier.

O problema de programaÃÃo de caminhÃes à um tema de grande relevÃncia na gestÃo de frota das empresas. Estas enfrentam dificuldades em gerenciar seus veÃculos devido Ãs diversas variÃveis inerentes ao processo, tais como o tamanho ideal da frota, os diversos tipos de caminhÃes disponÃveis, a capacidade de carga do caminhÃo, as informaÃÃes tÃcnicas do cliente e o agendamento das viagens. No que se refere ao transporte de derivados de petrÃleo, existem diversas caracterÃsticas operacionais que dificultam a programaÃÃo de caminhÃes. Embora a literatura sobre a programaÃÃo de veÃculos seja vasta, as abordagens para a programaÃÃo de caminhÃes para este tipo de transporte ainda à limitada. O presente trabalho tem como objetivo desenvolver um modelo de programaÃÃo inteira para a otimizaÃÃo da programaÃÃo de veÃculos de mÃltiplos tipos para o transporte de derivados de petrÃleo para obras de construÃÃo de rodovias. Dados reais sobre uma empresa de transporte desse setor foram coletados. Foi desenvolvido um modelo que buscasse a minimizaÃÃo da frota de caminhÃes disponÃveis. Como conclusÃes, pode-se ressaltar que a metodologia empregada serviu para minimizar a frota necessÃria no perÃodo analisado. O desenvolvimento de indicadores de desempenho permitiu avaliar a qualidade das soluÃÃes geradas. / The truck scheduling problem is an important topic in the companiesâ fleet management. Many companies face difficulties to manage their vehicles due to several variables inherent to the management process, such as the optimal fleet size, multiple types of trucks available, trucks capacity, the technical information from the clientâs construction site and trips scheduling. In terms of the transportation of oil products, there are many operational characteristics that make the truck scheduling difficult. Despite the extensive literature about vehicle scheduling, truck scheduling for this type of transport is limited. The purpose of this research study was to develop an Integer Programming model to optimize the multi-type truck scheduling for the transportation of oil products for road construction sites. Data from a real company were gathered. A model that aimed to minimize the truck fleet available was developed. The method used has minimized the available fleet in the period under review. The development of key performance indicators allows to evaluate the quality of the solutions created.

O ambiente produtivo denominado job shop representa empresas manufatureiras com características como: alta variedade de produtos, volume baixo de produção e uma fábrica dividida em áreas funcionais. O problema abordado neste trabalho trata da determinação do programa de produção (scheduling) de cada lote de produtos no ambiente job shop, com a premissa de que cada produto a ser elaborado surge através de um pedido realizado pelo cliente com especificações e particularidades próprias. O objetivo do trabalho é apresentar e examinar de forma detalhada as formulações matemáticas do tipo linear inteira mista (PLIM), encontradas na literatura para o ambiente que consideram a função objetivo do makespan. Além disso, se estabelece uma nova formulação matemática que auxilia a simulação do ambiente. Todas as formulações foram comparadas através de suas dimensões e testes computacionais. Adicionalmente são apresentadas três diferentes estratégias de resolução que permitem a exploração de soluções obtidas através de diferentes metodologias. A primeira estratégia estabelece para cada instância uma solução inicial que promove uma redução do número de combinações a serem avaliadas pelo software, a segunda estratégia combina duas formulações tornando uma formulação unificada, e a terceira estratégia, estabelece um processo que utiliza duas formulações de forma consecutiva compondo um procedimento sistemático. Experimentos computacionais indicam que a formulação com melhor desempenho para o problema de job shop é a formulação de Manne (1960) por obter o melhor limitante superior (upper bound). A formulação proposta apresenta o melhor limitante inferior (lower bound). Todas as formulações melhoram seus resultados através do uso das estratégias propostas. / The operational job shop environment, represents manufacturing companies with high product variety, low volume production and an organization divided into functional areas. The problem addressed in this work determines the production schedule of each batch production, with the premise that each product results from a request made by the client with specifications and its own particularities. The main objective here is to present and to examine in detail the mathematical integer - linear program formulations (MILP) from the literature for the job shop classic environment, which considers the makespan objective. Furthermore, a new mathematical formulation is provided to help with the simulation of the environment. All the formulations were compared by mathematical dimensions and computational tests. In addition, three different strategies are presented to promote the exploration of solutions obtained from new methodologies. The first strategy defines an initial solution for each problem and promotes a reduction of the combination number to be evaluated by the software. The second strategy considers the combination of two mathematical formulations under one objective function. The third strategy establishes a procedure in which two mathematical formulations are used consecutively, creating a systematic procedure. Computational experiments demonstrate that the best formulation for the job shop problem is the Manne (1960) formulation, since it obtains the best upper bound. The proposal formulation obtains the best lower bound. All of the formulations improve their results through the use of the proposed strategies.

Nesse trabalho, estudamos um problema de otimização combinatorial conhecido por Problema da Mochila Compartimentada, que é uma extensão do clássico Problema da Mochila. O problema consiste em determinar as capacidades adequadas de vários compartimentos que podem vir a ser alocados em uma mochila e como esses compartimentos devem ser carregados, respeitando as restrições de capacidades dos compartimentos e da mochila. Busca-se maximizar o valor de utilidade total. O problema é muito pouco estudado na literatura, apesar de surgir naturalmente em aplicações práticas. Nesse estudo, propomos uma modelagem matemática não linear para o problema e verificamos algumas heurísticas para sua resolução. / In this work, we studied a combinatorial optimization problem called the Clustered Knapsack Problem, that is an extension of the standard Knapsack Problem. The problem is to determine the right capacities of several clusters which can be allocated in a knapsack and how these clusters should be placed so as to respect the constraints on the capacities of the clusters and the knapsack. The objective is to maximize a total utility value. The problem has seldom been studied in the literature, even though it appears naturally in practical applications. In this study, we propose a non-linear model for the problem and we insert some heuristics for its resolution.

Orientador: Vinicius Amaral Armentano / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-10T01:09:54Z (GMT). No. of bitstreams: 1 Fonseca_SaraLuisadeAndrade_M.pdf: 1363535 bytes, checksum: aa7c01c779a21ea25aa3b603425c92fe (MD5) Previous issue date: 2007 / Resumo: Em 1958, Gomory propôs uma desigualdade válida ou corte a partir do tableau do método simplex para programação linear, que foi utilizado no primeiro método genérico para resolução de problemas de programação inteira. Em 1960, o corte foi estendido para problemas de programação inteira mista. Em 1973, Chvátal sugeriu um corte derivado da formulação original do problema de programação inteira, e devido à equivalência com o corte de Gomory, este passou a ser chamado de corte de Chvátal-Gomory. A importância do corte de Gomory só foi reconhecida em 1996 dentro do contexto do método branch-and-cut para resolução de problemas de programação inteira e programação inteira mista. Desde então, este corte é utilizado em resolvedores comerciais de otimização. Recentemente, diversos cortes novos derivados do corte de Chvátal-Gomory foram propostos na literatura para programação inteira. Este trabalho trata do desenvolvimento de algoritmos para alguns destes cortes, e implementação computacional em um contexto de branch-and-cut, no ambiente do resolvedor CPLEX. A eficácia dos cortes é testada em instâncias dos problemas da mochila multidimensional, designação generalizada e da biblioteca MIPLIB. / Abstract: In 1958, Gomory proposed a valid inequality or cut from the tableau of the simplex method for linear programming, which was used in the first generic method for solving integer programming problems. In 1960, the cut was extended to handle mixed integer programming problems. In 1973, Chvátal suggested a cut that is generated from the original formulation of an integer programming problem, and due to the equivalence with the Gomory cut, it was named Chvátal-Gomory cut. The importance of the Gomory cut was recognized only in 1996 in the context of the branch-and-cut method for solving (mixed) integer programming problems. Today, such a cut is utilized in optimization commercial solvers. Recently, several new cuts derived from the Chvátal-Gomory cut have been proposed in the literature for integer programming. This work deals with the development of algorithms and computational implementations for some of the new proposed cuts, in a context of the branch-and-cut method, by using the CPLEX solver. The efficiency of the cuts is tested on instances of the multi-dimensional knapsack, generalized assignment problems, and instances from the MIPLIB library. / Mestrado / Automação / Mestre em Engenharia Elétrica

Diversas pesquisas e estudos científicos mostram que uma grande porcentagem das pessoas com deficiência é excluída do mercado de trabalho, sobretudo em países em desenvolvimento. Com o intuito de alterar essa realidade, destacam-se, entre outras medidas, a criação de Centros de Trabalho para Deficientes (CTDs). Tais organizações empregam trabalhadores com deficiência em vários setores empresariais, dando-lhes oportunidades iniciais e preparando-os para que possam, mais tarde, ser inseridos no mercado de trabalho convencional. Vários destes centros operam linhas de produção, principal objeto de estudo desta tese. Nosso estudo é situado em uma etapa idealmente posterior aos CTDs, referente à inserção de trabalhadores com deficiência em linhas de produção convencionais. A demanda por estudos neste contexto tem crescido nos últimos anos, devido sobretudo a políticas corporativas de responsabilidade social e exigências legislativas, como a \"Lei das Cotas\", presentes em diversos países. O planejamento da operação de linhas de produção na presença de trabalhadores com deficiência envolve uma série de desafios, devido à heterogeneidade entre trabalhadores, que faz com que o tempo de execução das tarefas seja dependente de cada indivíduo. Nos deparamos, assim, com um problema de dupla alocação, em que as variáveis de decisão determinam as tarefas a serem inseridas em estações e a alocação de trabalhadores para as mesmas, de modo a otimizar alguma medida de eficiência. O balanceamento de linhas de produção convencionais com uma parcela de trabalhadores com deficiência é denominado problema de balanceamento de linhas de produção e integração de trabalhadores (ALWIBP, do inglês: assembly line worker integration and balancing problem), sendo um caso particular do problema de balanceamento de linhas de produção e designação de trabalhadores (ALWABP, do inglês: assembly line worker assignment and balancing problem), cuja ocorrência é mais comum em linhas de CTDs. Nosso objetivo consiste em estudar formas eficientes de proporcionar a integração de trabalhadores com deficiência em linhas convencionais. Para tanto, abordamos variações do ALWIBP que consideram: (i) minimização de diferentes funções objetivo (número de estações ou tempo de ciclo); (ii) linha de produção com leiautes distintos (simples ou em U); (iii) incertezas quanto ao tempo de execução de cada tarefa (abordagem robusta); (iv) estratégias de rotação de tarefas ou alocação de trabalhadores com deficiência na linha com espaçamento regular. Para cada uma destas extensões, foram desenvolvidos formulações matemáticas, métodos de resolução e novos conjuntos de instâncias teste. Experimentos computacionais indicam possibilidades de adaptação de linhas de produção convencionais à inserção de trabalhadores com deficiência, a custos adicionais baixos ou quase nulos. Portanto, este trabalho oferece alternativas para uma maior flexibilidade na integração de pessoas com deficiência, tornando-os tão eficientes quanto qualquer outro trabalhador denominado \"convencional\". / A number of studies show that a large percentage of disabled people are excluded from the labor market, in particular in developing countries. In order to deal with this problem, one can highlight the importance of Sheltered Work Centers for Disabled (SWDs). These organizations employ disabled workers in various corporate sectors, giving them initial opportunities and preparing them so that they can be later integrated into the conventional labor market. Many of these centers operate assembly lines, the main object of study of this thesis. Our study considers an ideally later stage of SWDs, related with the insertion of disabled workers in conventional assembly lines. The demand for studies in this field has grown over the years, due to corporate social responsibility policies and legal requirements such as \"quotas legislations\", present in many countries. Planning the operation of assembly lines with disabled workers involves a series of challenges due to the heterogeneity among workers, which are reflected in task times being worker dependent. This results in a double allocation problem, where decisions must determine both the tasks and the workers to be assigned to the stations, in order to optimize some efficiency measure. The conventional assembly line balancing with a parcel of disabled workers is known as the assembly line worker integration and balancing problem (ALWIBP), being a particular case of the assembly line worker assignment and balancing problem (ALWABP), which occurance is more common in SWDs. Our goal consists in studying efficient ways to promote the integration of people with disabilities in conventional assembly lines. For that, we address ALWIBP variants that consider: (i) minimization of different objective functions (number of stations or cycle time); (ii) different assembly line layouts (simple or U-shaped); (iii) uncertainties on task execution times (robust approach); (iv) job rotation strategies or allocation of disabled workers in the line with regular spacing. For each of these extensions, we develop mathematical formulations, solution methods and new sets of benchmark instances. Computational experiments indicate possibilities for adapting conventional assembly lines to the insertion of disabled workers, at low or close to null additional costs. Therefore, this study offers alternatives ways of increasing exibility in the integration of people with disabilities, making them as efficient as any other conventional worker.

Pessoas com deficiências possuem muitas dificuldades em participar do mercado de trabalho, possuindo uma taxa de desemprego bem maior do que a média populacional. Isso motiva o estudo de novos modos de produção que permitam incluir essas pessoas com baixo custo operacional. Neste trabalho é feito um estudo sobre a inclusão de pessoas com deficiências em flow shops com o objetivo de minimizar o makespan. Como flow shops normalmente possuem poucas máquinas, o foco do estudo é na inserção de um e dois trabalhadores. O problema é definido, são propostos modelos matemáticos e uma solução heurística para resolvê-lo, assim como instâncias de teste realistas. Nos testes computacionais a performance dos modelos e da heurística é avaliada e a utilidade prática deste modelo de inclusão é analisada. Nós concluímos que o problema pode ser resolvido de forma satisfatória e que a inclusão de trabalhadores com deficiêcia emn flow shops é economicamente viável. / Persons with disabilities have severe problems participating in the job market and their unemployment rate is usually much higher than the average of the population. This motivates the research of new modes of production which allow to include these persons at a low overhead. In this work we study the inclusion of persons with disabilities into flow shops with the objective of minimizing the makespan. Since flow shops usually have only a few machines, we focus on the inclusion of one and two workers. We define the problem, propose mathematical models and a heuristic solution, as well as realistic test instances. In computational tests we evaluate the performance of the models and the heuristic, and assess the utility of such a model of inclusion. We conclude that the problem can be solved satisfactorily, and that including workers with disabilities into flow shops is economically feasible.