Este trabalho apresenta um estudo sobre a razão assintótica de pior caso para alguns algoritmos aproximados utilizados para solucionar o problema de Bin Packing unidimensional ( BPP). Este é um problema clássico de otimização combinatória que serve de modelo para uma série de problemas que ocorrem no mundo real. No BPP, dada uma lista com n itens de tamanhos no intervalo (0,

Segmentação de mercado é um elemento de marketing essencial em países industrializados, visto que, para se produzir e vender um determinado bem, é preciso considerar as necessidades dos consumidores e reconhecer a heterogeneidade presente nessas necessidades. Segmentação de mercado consiste na tarefa de agrupar consumidores, para a qual uma grande variedade de métodos está disponível, sendo que os métodos de geração de agrupamentos estão dentre os mais utilizados. Uma grande questão na utilização dos métodos de geração de agrupamentos é a determinação do número ideal de agrupamentos. A segmentação de mercado e o posicionamento de produto são diretamente relacionados, uma vez que os compradores e vendedores buscam a acomodação mútua da oferta de produto/serviço que melhor satisfaça os objetivos de preferência dos consumidores e retorno das firmas. Existem diferentes modelos na literatura de design de engenharia, marketing e economia para lidar com o problema de posicionamento e design de produtos e linhas de produtos, e essas várias perspectivas de modelagem utilizam termos em comum que algumas vezes são usados com ambigüidade por diferentes autores. Os objetivos deste trabalho são estudar modelos de segmentação de mercado e posicionamento de produtos e, também, propor um novo método matemático de geração de agrupamentos. No método proposto, o número de agrupamentos é determinado automaticamente, sem necessitar nenhuma avaliação subjetiva do pesquisador. Como ilustração, aplicou-se o método de segmentação proposto, a partir de utilidades obtidas por análise conjunta, a uma categoria de veículos de passeio a fim de segmentar o mercado e determinar os perfis ótimos de novos produtos. Após a obtenção dos modelos de preferências individuais, os consumidores foram agrupados em função de semelhantes preferências e os perfis ótimos de novos produtos foram determinados utilizando três diferentes métodos: o método k-médias, o método proposto e o método de segmentação passo a passo. Após a determinação dos perfis ótimos de novos produtos, suas estimativas de fatia de mercado foram obtidas. O método proposto de geração de agrupamentos se mostrou interessante por não necessitar nenhum critério subjetivo para determinar o número ideal de agrupamentos e também por demandar menos esforço por parte do analista do que outros métodos tradicionais. Outra característica apresentada pelo método foi a tendência a privilegiar a homogeneidade interna ao agrupar observações. O método proposto apresenta como ponto fraco o fato de ser um problema de otimização combinatória, fazendo com que sua resolução usando programação inteira se torne ineficiente e inviável para grandes problemas.

Aborda-se neste trabalho um problema de seqüenciamento de padrões denominado Problema de Minimização de Pilhas Abertas, o qual visa aprimorar o processo de produção de corte de objetos e que possui grande aplicação industrial. Além da aplicação direta, o tratamento do problema é interessante devido ao alto nível de dificuldade para determinação sua solução por métodos computacionais e à sua versatilidade, pois pode-se utilizá-lo para modelar vários outros problemas tanto práticos quanto mais teóricos. Propõe-se uma heurística construtiva que usa um procedimento de geração de permutações de partes de uma solução e uma regra de melhoria baseada na antecipação do fechamento de pilhas. Além disso, são propostas e discutidas a utilização de pré-processamento dos dados de entrada do problema e a simplificação de um dos métodos de solução da literatura baseado em teoria dos grafos para geração de uma solução inicial. Os resultados dos experimentos computacionais extensivos realizados demonstram a eficiência das idéias propostas tanto isoladamente quanto em conjunto, frente aos métodos da literatura para lhe servir de comparação. A heurística proposta é uma alternativa competitiva para a solução do problema abordado.

Este trabalho tem por objetivo possibilitar a utilização do modelo paramétrico ASFM na presença de restrições aos pesos. O modelo proposto permite também que se encontre uma solução com fronteira distinta da esférica, caso à última se mostre inviável. A partir da aplicação do método proposto a um conjunto de dados reais sobre a alocação justa da emissão de dióxido de carbono será mostrado que, Por meio da introdução de restrições aos pesos, o mesmo pode aproximar a sua solução à de outro método da literatura.

Material transportation is one of the most important aspects of open-pit mine operations. The problem usually involves a truck dispatching system in which decisions on truck assignments and destinations are taken in real-time. Due to its significance, several decision systems for this problem have been developed in the last few years, improving productivity and reducing operating costs. As in many other real-world applications, the assessment and correct modeling of uncertainty is a crucial requirement as the unpredictability originated from equipment faults, weather conditions, and human mistakes, can often result in truck queues or idle shovels. However, uncertainty is not considered in most commercial dispatching systems. In this thesis, we introduce novel truck dispatching systems as a starting point to modify the current practices with a statistically principled decision making methodology. First, we present a stochastic method using Time-Dependent Markov Decision Process (TiMDP) applied to the truck dispatching problem. In the TiMDP model, travel times are represented as probabilistic density functions (pdfs), time-windows can be inserted for paths availability, and time-dependent utility can be used as a priority parameter. In order to minimize the well-known curse of dimensionality issue, to which multi-agent problems are subject when considering discrete state modelings, the system is modeled based on the introduced single-dependent-agents. Based also on the single-dependent-agents concept, we introduce the Genetic TiMDP (G-TiMDP) method applied to the truck dispatching problem. This method is a hybridization of the TiMDP model and of a Genetic Algorithm (GA), which is also used to solve the truck dispatching problem. Finally, in order to evaluate and compare the results of the introduced methods, we execute Monte Carlo simulations in a example heterogeneous mine composed by 15 trucks, 3 shovels, and 1 crusher. The uncertain aspect of the problem is represented by the path selection through crusher and shovels, which is executed by the truck driver, being independent of the dispatching system. The results are compared to classical dispatching approaches (Greedy Heuristic and Minimization of Truck Cycle Times - MTCT) using Student's T-test, proving the efficiency of the introduced truck dispatching methods.

Este trabalho sugere um algoritmo para ambiente distribuído que determina as K-melhores soluções para o problema da mochila unidimensional. O algoritmo baseia-se no trabalho de Yanasse, Soma e Maculan (1995), que trata da mesma questão para ambiente serial. Entretanto, convém ressaltar que a versão distribuída do algoritmo possui profundas modificações em relação à versão serial. Primeiramente, o algoritmo serial foi estudado e totalmente implementado. A segunda etapa do trabalho foi o desenvolvimento do algoritmo distribuído. Parte desta tarefa tratou da escolha de uma abordagem de implementação no ambiente distribuído. Duas abordagens foram levadas em consideração e os respectivos algoritmos foram implementados e testados. O paradigma divide and conquer para algoritmos paralelos foi o que prevaleceu. Quanto ao ambiente operacional, o algoritmo serial foi desenvolvido, na sua fase inicial, sobre a plataforma 486/Windows e linguagem de programação C++. Posteriormente, portou-se a aplicação para o ambiente RISC/UNIX. O algoritmo distribuído foi desenvolvido em linguagem de programação C++ aliada às funções da biblioteca PVM, Parallel Virtual Machine (Máquina Paralela Virtual), em uma rede de estações UNIX. Resutaldos computacionais são apresentados.

A decisao para selecao de projetos de Pesquisa e Desenvolvimento (P&D) pode ser classificada como um exemplo particular do problema gerencial mais geral da alocacao de recursos, cujos retornos sao multidimensionais, incertos e vagos. A Analise Hierarquica Difusa, proposta por Buckley e uma extensao do Processo de Hierarquia Analítica (PHA) de Saaty, onde sao utilizados coeficientes difusos em lugar dos coeficientes exatos. O objetivo deste trabalho e explorar detalhadamente o metodo da Analise Hierarquica Difusa e aplica-lo ao problema particular da selecao de projetos de P&D, criticando-o e identificando suas potencialidades elimitacoes. Observa-se que o metodo da Analise Hierarquica Difusa e uma generalizacao do Processo de Hierarquia Analítica (PHA)tradicional. Neste metodo, aceita-se tanto valores exatos comodifusos na atribuicao dos valores dos coeficientes de comparacao, porem, a metodologia de ordenacao de numeros difusos, ainda em fase de amadurecimento, tem influencia significativa na operacionalizacao do metodo como ferramenta gerencial, devido a dificuldade de distinguir a prioridade ou preferencia entre duas alternativas. A implementacao do metodo e facilmente conseguida de forma amigavel ao usuario, de maneira que a interface grafica com o usuario permita uma visualizacao simples e intuitiva das funcoes de pertinencia pelo decisor, contudo, a sua utilizacao no mundo real depende ainda da eliminacao das limitacoes constatadas neste trabalho.

Este trabalho utiliza o problema subset-sum (SSP) como estudo de caso, com o objetivo de analisar a complexidade de paralelização em Unidades de Processamento Gráficas (GPU). O SSP foi escolhido por pertencer à classe dos problemas NP-Completo, possuir grande necessidade de memória e não ter cálculo de ponto flutuante, além de ser amplamente estudado na área acadêmica devido a sua importância prática e teórica. Estas características representam um desafio para paralelização em GPUs, pelo fato de serem especialistas em cálculos de ponto flutuante e por possuir pouca quantidade de memória em relação ao grande número de núcleos. Basicamente, são apresentados 3 novos algoritmos, implementados em linguagem CUDA C, com baixo consumo de memória: somente , onde , é a capacidade da mochila e é a quantidade de itens, ao invés de do paradigma de Bellman, referentes aos algoritmos do estado da arte implementados na mesma arquitetura. Esta característica permite um ganho significativo na quantidade de instâncias solucionáveis, além do melhor tempo computacional. Para uma variedade de benchmarks, obteve-se bons valores de speed-up em relação aos melhores resultados práticos conhecidos até agora. Isto foi possível graças a um novo método para a solução do SSP, permitindo sua computação em tempo e mesmo espaço, caso processadores sejam utilizados.

Esta tese é sobre otimização combinatória e nela aborda-se o problema de minimização de pilhas abertas. São apresentados dois novos métodos heurísticos simples para solução deste problema, baseados em algoritmos básicos da teoria de grafos aos quais associam-se duas simples regras de melhoria gulosas. Para aferição da qualidade dos métodos propostos, estes são comparados com os dois métodos que são o estado da arte do problema objeto de estudo, sendo um exato e outro, heurístico. Para que os experimentos computacionais fossem abrangentes, foram utilizados três conjuntos de instâncias: o primeiro, adotado amplamente pela comunidade acadêmica; o segundo, mais recente e de maior nível de dificuldade e o terceiro novo conjunto de instâncias, proposto neste mesmo trabalho, possuidor de problemas com maiores instâncias e nível de dificuldade maior que os dois anteriores. Os resultados reportados mostram que as duas heurísticas - HBF2r e Lookahead, superam o método heurístico de melhor desempenho da literatura em qualidade da solução e em regularidade. Ainda, Lookahead obtém grande quantidade de soluções ótimas, baixos índices de erros e soluções de qualidade próxima às soluções geradas pelo método exato nos três conjuntos de instâncias considerados, não obstante o fato de se tratar de uma heurística. Os tempos computacionais são considerados muito baixos em termos práticos. Espera-se que as contribuições aqui realizadas possam auxiliar uma maior compreensão do problema.

Consideramos nesta dissertação um problema, NP-difícil, de seqüenciamento de padrões, vizando minimizar o número máximo de pilhas abertas em torno de uma máquina industrial de corte. Estamos interessados em métodos frugais, os quais, seguindo à terminologia de Halldórson (91), são aqueles - métodos - que além de utilizar poucos recursos computacionais - tempo e espaço - possuem idéias de implementações simples. A modelagem do problema pela Teoria dos Grafos foi a escolhida para obtenção de tais métodos, na tentativa de se identificarem aspectos estruturais que, porventura, pudessem emergir e auxiliar na sua resolução. A partir daquela modelagem, descobrimos ser o grafo complementar bastante esparso e possuidor de um conjunto independente maximal surpreendentemente grande, se comparado ao número de vértices do grafo. Através da informação adicional, fornecida por estes dois aspectos estruturais encontrados no grafo modelada, um método geral, baseado no clique maximal, foi desenvolvido. A frugalidade do método está no uso de uma conhecida heurística gulosa, de tempo linear no número de vértices, para detecção de conjuntos independentes. A partir do método geral, duas heurísticas puderam ser desenvolvidas: a primeira, de detecção de circuitos hamiltonianos, obtidos através de uma versão do algoritmo extensão-rotação para grafos randônicos, com o circuito inicial composto pelos vértices do clique maximal; e a segunda, de contratação recursiva de cliques. Realizamos testes computacionais comparando as nossas heurísticas com aquelas pertencentes ao estado da arte encontrado na literatura. Os resultados demonstram que as duas heurísticas desenvolvidas através do método proposto são competitivas, tanto em termos de tempo e espaço como de erro médio, além da facilidade de implementação.