Orientador: Pedro Sergio de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-07-20T09:57:07Z (GMT). No. of bitstreams: 1 Cavalcante_VictorFernandes_M.pdf: 2124078 bytes, checksum: 931a0a025284734a0bdaf335669442c5 (MD5) Previous issue date: 1995 / Resumo: Times Assíncronos consistem numa nova técnica para solução aproximada de problemas que tem sido aplicada com sucesso a problemas de Otimização Combinatória. Esta técnica faz uso de diversos algoritmos heurísticos que cooperam entre si e conseguem encontrar soluções que não seriam encontradas pelos mesmos algoritmos quando executados isoladamente. Este trabalho tem como objetivo averiguar a adequabilidade de Tunes Assíncronos como metodolqgia para solução do problema de escalonamento de tarefas conhecido por Job Shop Scheduling Problem (JSP). Este problema é considerado um dos mais complexos dentro da Otimização Combinatória e tem recebido crescente atenção nas últimas décadas devido, principalmante, à sua aplicabilidade a processos industriais. Especificamente, o cerne do presente trabalho foi a elaboração de TImes A"síncronos centrados fundamentalmente em heurísticas de construção para oJob Shop Scheduling Problem. Foram concebidas e testadas novas heurísticas para o ISP e novos fluxos de dados que podem ser facilmente acoplados à arquitetura de um Time Assíncrono. Os Times Assíncronos desenvolvidos foram submetidos a diversas instâncias do JSP. Os bons resultados obtidos, não somente atestaram a viabilidade da nova técnica como ferramenta para solução do ISP, como revelaram a competitividade destes resultados com aqueles produzidos por outros métodos aproximados para o problema. / Abstract: Asynchronous Teams (or A-Teams) are a new problem resolution technique that has been succesfully applied to Combinatorial Optimization problems. This technique uses several heurisJic algorithms that cooperate simultaneously with each other and find solutions that would not be found through isolated algorithms. The objective of this work is to verify the suitability of Asynchronous Teams methodology solving the combinatorial problem known by Job Shop Scheduling Problem (JSP). This problem has been appointed as one of the most complex problem of Combinatorial Optimization and has been received special attention due to your industrial applicability. Specifically, the kemel of this work was the implementation of A-Teams based on construction heuristics for the Job Shop Scheduling Problem. New heurisncs for the JSP were developed and new data flows that can be easily incorporated in an A-Team architecture were elaborated.. Several JSP instances were used to test the A-Teams developed.. The good results obtained by these A-Teams not onIy showed the feasibility of such technique solving the JSP, but also revealed that this results are competitive with others one obtained by good aproximated approachs for the JSP. / Mestrado / Mestre em Ciência da Computação

Orientador : Flavio Rocha Gorini / Dissertação (mestrado) - Universidade Estadual de Campinas. Instituto de Matematica, Estatistica e Computação Científica / Made available in DSpace on 2018-07-17T01:32:59Z (GMT). No. of bitstreams: 1 Cortes_MariaBernadetedeSouza_M.pdf: 864652 bytes, checksum: 73f21c803bc6f68207a9fcd7ad9c7ca6 (MD5) Previous issue date: 1982 / Resumo: Nesta tese lidamos com o seguinte jogo de Blotto: Dois políticos devem alocar, secretamente, seus recursos igualmente entre um número de eleitores. Cada eleitor vota no político que lhe der mais recursos. Nós apresentaremos soluções assintoticamente ótimas para esse jogo / Abstract: In this thesis we deal with the following Blotto Games: Two politicians must allocate secutly, their resources equally among a number of voters. Each voter votes for the politician that gives him more resources. The politician that receives more votes win the game. We give asymptotically optimal soluctions for this game / Mestrado / Mestre em Matemática

Orientadores : Luis Gimeno Latre, Maria Tereza Moreira Rodrigues / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica / Made available in DSpace on 2018-07-18T15:57:34Z (GMT). No. of bitstreams: 1 Campos_MarcioFranciscoDutrae_M.pdf: 6234968 bytes, checksum: 4db64f154811bdce943bc133fc0d44bb (MD5) Previous issue date: 1993 / Resumo: O flow-shop, assim como a grande maioria dos problemas de scheduling, é un problema cuja complexidade computacional cresce exponencialmente com a sua dimensão. Para diminuir esta complexidade, geralmente são feitas hipóteses que simplificam o modelo da planta mediante o relaxamento de restrições. Grande parte destas hipóteses dizem respeito aos instantes de tempo em que as tarefas devem ser alocadas e às disponibilidades dos recursos compartilhados. Entrentanto, na indústria de processos químicos, que é a principal área de aplicação do fIow-shop, estas restrições não podem ser relaxadas, porque o alto custo dos produtos que são produzidos exige que as instalações disponíveis sejam utilizadas da melhor maneira possível. Além do mais, o atendimento rápido aos clientes é o principal objetivo, o qual só é alcançado se as restrições temporais impostas pelo processo produtivo e pela demanda do mercado são obedecidas. Neste trabalho propõe-se uma estratégia de solução para o problema de fIow-shop que não admite a relaxação das restrições sobre os recursos compartilhados e sobre os instantes de tempo em que as tarefas devem ser alocadas. A estratégia proposta combina técnicas de Inteligência Artificial (IA), que têm por objetivo satisfazer as restrições do problema, com a técnica Branch-and-Bound (BAB) clássica da Pesquisa Operacional (PO), que permite alcançar o objetivo do problema que é minimização do tempo de conclusão das tarefas, através da maximização da utilização dos recursos compartilhados. As técnicas de IA utilizadas são a análise e propagação de restrições que, juntamente com heurísticas de aIocação de tarefas, permitem uma redução significativa do espaço de soluções e de busca do problema. O uso conjunto do BAB com propagação de restriçõese heurísticas resulta em um algoritmo de busca em árvore eficiente, no sentido de que ele geralmente consegue obter soluções ótimas sem precisar pesquisar um elevado número de nós / Abstract: Not informed. / Mestrado / Mestre em Engenharia Elétrica

Orientador: Regiane Máximo de Souza / Banca: Enzo Barberio Mariano / Banca: Reinaldo Morabito Neto / Resumo: Vários Sistemas de Atendimento Emergenciais (SAE's) sofrem com as variações diárias da demanda e da disponibilidade das ambulâncias. Nesses sistemas pode haver flutuação do desempenho ao longo do dia devido, por exemplo, a mudança no número de servidores e nas taxas de chegada, levando à necessidade de considerar explicitamente tais variações em uma extensão ao modelo hipercubo ainda não explorada na literatura. Como ocorre em alguns SAE's, as ambulâncias melhor equipadas são reservadas para o atendimento exclusivo de chamados com risco de vida. Dessa maneira, a política de despacho pode ser diferenciada com a finalidade de reservar totalmente o atendimento de alguns servidores para certas gravidades de ocorrências. Além disso, somam-se à natureza aleatória desses sistemas, como por exemplo, as incertezas da disponibilidade das ambulâncias, a chegada de um novo chamado e sua localização. Nesse contexto, os objetivos do presente estudo são: (i) estender o modelo hipercubo de filas para reserva total de capacidade, dependendo do tipo do chamado; (ii) estender o modelo hipercubo de filas para torná-lo mais eficiente computacionalmente, sem haver perda de precisão durante a modelagem e resolução; e (iii) propor uma abordagem baseada no modelo hipercubo não-estacionário para organização do trabalho das ambulâncias em qualquer momento do dia. Para verificar a viabilidade e a aplicabilidade dessas abordagens, é realizado um estudo de caso no SAMU da cidade de Bauru (SAMU-Bauru) que,... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: Many Emergency Service Systems face daily variations on demand and ambulance availability. These systems may suffer, for example, performance fluctuations throughout the day, changes on the number of servers and on arrival rates, leading to the need to explicitly consider such variations in a hypercube model extension not yet explored in the literature. As occurs in some SAMU's, which reserve their best equipped ambulances to exclusively serve life-threating requests. Therefore, the dispatch policy can be differentiated in order to completely reserve the service of some ambulances to more severe requests. These problems add up to the random nature of these systems with uncertainties upon ambulance availability or the arrival of a new request and its location. Thus, this study aims to: (i) extend the hypercube queueing model to be able to capture the complete capacity reservation of advanced ambulances, depending on the request classification; (ii) extend the hypercube model in order to make it more computationally efficient, without losing any information during modeling and resolution. (iii) propose an approach based on nonstationary hypercube queueing model to organize the operation of ambulances at any time of the day. To verify the feasibility of these approaches, a case study is carried out on the SAMU from Bauru city (SAMU-Bauru), which, in addition to the advanced ambulance reservation for life-threating requests, is affected by daily variations in demand and ambulance availability. In addition to the original configuration of SAMU-Bauru, studied on a two-step approach, we studied a total of four alternative scenarios that exploited important matters as: the impact of average demand increase on the congestion peak; mitigation of this impact by including a new ambulance; changing the schedule of daily breaks; and the... (Complect abstract electronic acess below) / Mestre

Este trabalho detalha o problema de programação de atividades de desenvolvimento de poços marítimos (PPADPM), cujo objetivo é definir o uso de sondas e navios, de forma a otimizar a produção de óleo dos poços marítimos. São apresentados cinco modelos baseados em programação linear-inteira mista (MILP) e um modelo gerado via programação por restrições (PR) para este problema. Concluiu-se que, dentre os modelos MILP, aquele baseado em variáveis que definem a ordem de execução das atividades apresenta os melhores resultados, tanto em termos de qualidade de soluções quanto em termos de tamanho do modelo. O aumento do tamanho da instância (em número de poços e/ou em número de recursos) traz como consequência um menor número de nós analisados dentro de um tempo limite de execução do modelo, ao mesmo tempo em que se observa que as estratégias de escolha de variáveis, de escolha de nós e de uso de solução inicial nos modelos MILP tornam-se ineficientes. Na comparação entre modelos MILP e o modelo baseado em PR, constatou-se que este último obteve as melhores soluções em mais de 90% dos casos analisados e, consistentemente, obteve mais soluções viáveis para cada instância. Entretanto, por não fornecer informações sobre a qualidade da solução, o modelo baseado em PR somente obtém a solução ótima ao analisar todo o espaço de busca do modelo; desta forma, este apenas chegou à solução ótima em instâncias com até quatro poços, enquanto alguns dos modelos MILP obtiveram a solução ótima para instâncias com até treze poços. / This work details the offshore wells activities on specialized resources scheduling problem, focusing on the optimization of the total oil production. A Constraint Programming (CP) model and five Mixed-Integer Linear Programming (MILP) models were studied. Among the linear models, those based on activities order variables are smaller, and led to the better solutions for almost all of the instances analyzed. As far as the size of the instances (number of wells and/or number of resources) increases, the number of branched nodes in a limited time decreases and, consequently, the influence of B&B nodes and variable selection strategies and of the initial guesses on the MILP model solution gets less efficient. Comparing best solutions for each instance, the CP model outperformed MILP models in 90% of the studied cases. In addition, the CP based model consistently found more solutions per instance than the MILP based models did. However, because the CP model does not give information on the quality of a solution (gap), it was only able to obtain optimal solutions for instances with up to four wells, while MILP based models found optimal solutions for instances up to thirteen wells.

Made available in DSpace on 2016-08-10T10:40:26Z (GMT). No. of bitstreams: 1 Jorge Marques dos Anjos.pdf: 2030461 bytes, checksum: ec18f62531488f96521dca090db82990 (MD5) Previous issue date: 2012-09-14 / This dissertation investigates ways to reduce waste of wood panels of furniture industries by order and that already use optimizing cutting plans by commercial software. The characteristics of these industries are the low volume per batch and almost absence of exact standards of measures of the cut pieces. This set of factors favor the generation of significant leftovers, even when cutting planes are optimized. This research consists in grouping of historical leftovers in two-dimensional classes, then, checks the possibility of using these leftovers in each class. Larger leftovers than the pieces immediately below are lower limits of each class are reusable scraps in the future and the leftover who minor that this pieces are losses. If there isnt a demand to the scrap to be reused, it is also classified as loss. An algorithm for select and quantify the leftovers and pieces in two-dimensional classes and check the usable scrap that was developed and tested. The results obtained in the test indicate to the reduction of 27% of losses compared with the present number of the company searched. This represents the equivalent of two plates utilization in 100 units cut out. / A presente dissertação de mestrado investiga formas de reduzir desperdícios de painéis de madeira em indústrias moveleiras por encomenda e que já tenham seus planos de corte otimizados por softwares comerciais. As características desta indústria são o baixo volume por lote e a quase inexistência de padrões exatos de medidas das peças cortadas. Este conjunto de fatores favorece a geração significativa de sobras mesmo quando os planos de corte são otimizados. A presente pesquisa consiste em agrupar as sobras históricas em classes bidimensionais e, depois, verificar a possibilidade de aproveitamento destas sobras em demandas futuras de peças. Sobras maiores que as peças classificadas imediatamente abaixo dos limites inferiores de cada classe são retalhos passíveis de serem futuramente utilizados e as sobras menores são perdas. Se não houver demanda para que um retalho seja aproveitado, este também é classificado como perda. Um algoritmo para selecionar e quantificar as sobras e peças em classes bidimensionais e também apurar o os retalhos aproveitáveis foi desenvolvido e testado. Os resultados obtidos no teste apontam para a redução de 27% de perdas em comparação com os números atuais da empresa pesquisada. Isso representa o aproveitamento equivalente a 2 chapas em cada 100 unidades cortadas.

O propósito desse trabalho é composto por cinco objetivos distintos: (1) modelar o problema de admissão de pacientes em hospitais eletivos por programação dinâmica aproximada; (2) resolver o modelo formulado utilizando um algoritmo de estimação adaptativa do valor de funções côncavas; (3) estabelecer métricas de qualidade para a solução obtida pela solução do modelo; (4) realizar uma análise comparativa entre os resultados obtidos quando modelado por processo markoviano de decisão e por programação dinâmica aproximada; (5) fazer uma análise de sensibilidade automatizada, para análise de impacto da alteração dos parâmetros do modelo nos resultados, em modelos de programação dinâmica aproximada. A razão de se controlar o processo de admissão de pacientes é promover a utilização mais eficiente dos recursos hospitalares pela diminuição de sua ociosidade ou de sua utilização excessiva. O problema de planejamento de admissão de pacientes eletivos como um modelo de programação dinâmica aproximada, apresenta uma diminuição no espaço de estados e ações reduzindo assim a alta dimensionalidade das instâncias reais do problema, o que determina um custo computacional bastante reduzido quando comparado à solução da modelagem do problema por processo markoviano de decisão. Os resultados obtidos pela solução da modelagem do problema via programação dinâmica aproximada, para o caso da Rede de Hospitais Sarah de Brasília, demonstraram que foi possível obter uma política de decisão mais eficiente, com menor tempo de processamento e maior robustez (pela análise de sensibilidade efetuada). Espera-se que ao final da leitura desse trabalho, o leitor conheça como a programação dinâmica aproximada opera, suas principais diferenças em relação aos métodos exatos e a contribuição que estabelece no processo de solução de problemas dinâmicos e estocásticos de alta dimensão.

Neste trabalho nós aplicamos resultados recentes na área de rotinas ótimas de inspeção sob deterioração estocástica ao problema do estabelecimento de uma rotina de testes clínicos a que deve submeter toda uma população visando detectar tão cedo quanto possível a eventual presença de um certo tipo de vírus em cada elemento dessa população. Aqui nós consideramos a existência de dois tipos de exames laboratoriais. O primeiro é mais barato, porém menos confiável, pois pode gerar falsos resultados positivos ou falsos resultados negativos. Sempre que esse exame gera um resultado positivo usamos um segundo tipo de exame, mais caro e mais preciso, para verificar se tal resultado é verdadeiro ou falso. Se verdadeiro, submete -se o sistema a um tratamento para evitar a condição de quebra (falha, morte) do mesmo. Com uma estrutura de custos que considera custos de: examina, falsos resultados positivos; detecção do vírus e ficar doente, nós apresentamos uma equação que pode se usada para calcular o valor presente do custo esperado total sob uma determinada rotina de exames. A incorporação da possibilidade de um falso resultado negativo é a maior contribuição teórica deste trabalho.Usando dados reais, o modelo é aplicado ao problema da detecção do vírus da AIDS em países como o Brasil ou os Estados Unidos, onde a doença se manifesta de maneira semelhante. O resultado principal é a obtenção da freqüência de inspeções que minimiza o valor presente do custo esperado total.

Considera-se uma versão do problema de reparo de máquinas com um número finito de máquinas diferentes nas linhas de produção, um numero finito de máquinas de reservas diferentes e uma estação de reparo com um número finito de servidores diferentes. Nos instantes de decisão (instatnes de término de reparo e de quebra de máquinas), os servidores ativos podem ser escolhidos baseando-se no tamanho da fila de reparo. A estrutura de custos inclui custos de perda de produção, custos de espera, custos de reparo e custos de ativar e desativar servidores. O Algoritmo de Iteração de Valores é utilizada para obter a política ótima de controle que minimiza o custo médio esperado por unidade de tempo. Alguns resultados numéricos são apresentados, inclusive com a determinação do número ótimo de máquinas de reserva.

Este estudo investiga soluções de massa (volume) mímina para estruturas unidimensionais excitadas harmonicamente, utilizando técnicas de controle ótimo. Tais soluções apresentam forte dependência entre frequência de excitação e frequências naturais da estrutura, ocorrendo geralmente, na ausência de amortecimento, regiões viáveis disjuntas e, em consequência, vários mínimos locais. São buscadas soluções para frequencias de excitação menores que a primeira frequência natural, e frequências de excitação entre a primeira e a segunda frequências naturais de vibração. Estudam-se aqui dois tipos de problema: (1) determinação do perfil de área de uma barra em balanço, excitada axialmente por uma força variando harmonicamente, aplicada na extremidade livre. São consideradas restrições de área mínima e tensão máxima ao longo da barra. (2) determinação do perfil de área de uma viga em balanço de seção retangular, com raio de giração da seção constante, excitada transversalmente na extremidade livre por uma força harmônica. São impostos vínculos de tensão de flexão máxima e área de seção mínima. São introduzidas, quando necessário, concentrações pontuais de massa não estrutural. Utilizam-se métodos indiretos na solução dos problemas de controle ótimo.