Irregular cutting and packing problems, with convex and non-convex polygons, are found in many industries such as metal mechanics, textiles, of shoe making, the furniture making and others. In this thesis we study the two-dimensional version of these problems, where we want to allocate a set of items, without overlap, inside one or more containers, limited or unlimited, so as to optimize an objective function. In this document we study the knapsack problem, placement problem, strip packing problem, cutting stock problem and bin packing problem. For these problems, the heuristic methods and mathematical programming models are proposed and presented very promising results, surpassing in many cases the best results in the specialized literature. This thesis is organized as follows. In Chapter 1, we present a review of the studied problems, the value proposition for this thesis with the main contributions and ideas. In Chapter 2, we propose a metaheursitic for the strip packing problem with irregular items and circles. Then, in Chapter 3, we present a generic heuristic for the allocation of irregular items that may be weakly or strongly heterogeneous and will be allocated in a container (output maximization problems) or multiple containers (input minimization problems). In Chapter 4, we propose a solution method for the cutting stock problem with deterministic demand and stochastic demand. In Chapters 5 and 6, we present mathematical programming models for the strip packing problem. Finally, in Chapter 7, we present a conclusion and a concise direction for future works. / Os problemas de corte e empacotamento de itens irregulares, polígonos convexos e não convexos, são encontrado em diversas indústrias, tais como a metal-mecânica, a têxtil, a de calçados, a moveleira e outras. Nesta tese estudamos a versão bidimensional destes problemas, na qual desejamos alocar um conjunto de itens, sem sobreposição, no interior de um ou mais recipientes, limitados ou ilimitados, de modo a otimizar uma função objetivo. Neste trabalho estudamos o problema da mochila, o problema do assentamento, o problema empacotamento em faixa, o problema de corte de estoque e o problema de empacotamento de contêineres. Para estes problemas, os métodos heurísticos e modelos de programação matemática propostos e apresentam resultados muito promissores, ultrapassando em muitos casos os melhores resultados da literatura especializada. Esta tese esta organizada da seguinte maneira. No Capítulo 1, apresentamos uma revisão dos problemas estudados, a proposta de valor deste doutorado com as principais contribuições e ideias. No Capítulo 2, propomos uma meta-heurística para o problema de empacotamento em faixa para itens irregulares e círculos. Em seguida, no Capítulo 3 apresentamos uma heurística genérica para a alocação de itens irregulares que podem ser fracamente ou fortemente heterogêneos e serão alocados em um recipiente (problema de maximização de saída) ou de múltiplos recipientes (problemas de minimização de entrada). O Capítulo 4 propõem um método de solução para o problema de corte de estoque com demanda conhecida e demanda estocástica. Nos Capítulos 5 e 6 apresentamos modelos de programação matemática para o problema de corte de itens irregulares em faixa. Finalmente, no Capítulo 7, apresentamos a conclusão e uma sucinta direção para os trabalhos futuros.

Orientador: Cid Carvalho de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-19T00:16:31Z (GMT). No. of bitstreams: 1 Zilli_PetersonKatagiri_M.pdf: 1307926 bytes, checksum: 5fe0ddfca7cce84d9e26b66106d61e8b (MD5) Previous issue date: 2011 / Resumo: O Problema de Roteamento de Veículos (VRP, em inglês) foi proposto por Dantzig e Ramser em 1959 e, desde então, um grande número de artigos foi dedicado à solução de suas variantes. O problema original consiste em determinar rotas otimais que serão usadas por veículos de capacidade limitada para servirem a um conjunto de clientes. Neste trabalho focamos o estudo e a implementação dos modelos chamados de "ricos" na literatura, os quais englobam variantes complexas do VRP e conseguem representar situações mais próximas dos problemas logísticos encontrados em sistemas de distribuição reais. A principal motivação para esta pesquisa é uma aplicação prática referente ao problema de roteamento dos ônibus fretados pela UNICAMP para o transporte de seus funcionários, que se caracteriza como um modelo rico. O objetivo final é a otimização de tal processo através da minimização da distância total percorrida ou do número de veículos empregados, com a consequente redução dos gastos incorridos pela Universidade. Portanto, além do seu aspecto científico, esta dissertação produz resultados com chances reais de trazer benefícios à administração de uma instituição pública de ensino. Para que isto venha a ocorrer, as heurísticas desenvolvidas foram inseridas em um sistema de informações geográficas, que será usado pela universidade no processo de criação e otimização das rotas a serem licitadas publicamente / Abstract: The Vehicle Routing Problem (VRP) was first proposed by Dantzig and Ramser in 1959 and, since then, a large number of papers has been devoted to the solution of its variants. The original problem consists in determining an optimal set of routes to be used by vehicles of limited capacity that serve a set of customers. In this paper we focus on the study and implementation of models called "rich" in the literature, which include complex variants of the VRP that represent situations closer to the logistical problems encountered in real distribution systems. The main motivation for this research is a practical problem concerning the routing of buses chartered by UNICAMP for transporting a part of its employees, which is characterized as a rich model. The goal is to optimize this process by minimizing the total travel distance or the number of vehicles used, with a consequent reduction of the expenses incurred by the University. Therefore, in addition to its scientific aspect, this dissertation gives results with real chances to benefit the administration of a public university. For this to happen, the heuristics developed were entered into a geographic information system, which will be used by the university in the process of creation and optimization of routes to be publicly auctioned / Mestrado / Pesquisa Operacional / Mestre em Ciência da Computação

El presente proyecto de fin de carrera propone implementar un algoritmo metaheurístico, cuckoo search, en el proceso de obtención de recompensas de juegos Gacha. El foco y objetivo de este estudio es el poder encontrar un equilibrio entre la satisfacción del usuario y el beneficio de la empresa, por lo cual se utilizaron dos tipos de usuario quienes abarcan las características de tiempo empleado en el juego y cuánto monto han invertido en éste. Para ello, se propuso una función objetivo en la cual abarca las variables relacionadas al usuario y la empresa, luego se adaptó el algoritmo propuesto al contexto planteado. Finalmente se implementó y aplicó en un prototipo de juego donde se compara el funcionamiento y desempeño de éste junto a un simulador; además de poder visualizar y simular el contexto de estar utilizando/jugando un juego Gacha. De los resultados, se pudo verificar un desempeño del algoritmo elegido frente al simulador. Con ello se logra cumplir con el objetivo inicial de poder equilibrar los valores representativos del usuario y el beneficio de la empresa. La meta propuesta es poder demostrar que el uso del cuckoo search en estos juegos es posible y en un futuro poder mejorarlo para su uso en estos tipos de juegos.

Organizações eficientes são aquelas que conseguem manter equilibradas as vertentes de qualidade, custo e tempo. Em relação ao último, existem várias etapas da cadeia produtiva nas quais o tempo deve ser monitorado. Quando a programação da produção nas indústrias não é priorizado, pode-se incorrer vários efeitos negativos. Um deles, é o atraso em relação à data de entrega, no qual a corporação pode sofrer penalidades financeiras, além de uma exposição negativa para a marca, a qual pode ter sua credibilidade contestada. Dessa forma, essa pesquisa tem por objetivo propor métodos construtivos, que minimize a medida de desempenho total tardiness (atraso total). Para aproximar o método à realidade vivenciada pelas indústrias, será considerada a restrição de manutenção preventiva. Além disso, o ambiente de estudo será o contexto de no-wait flowshop, no qual as tarefas são processados continuamente e sem que haja interrupções entre uma operação e outra de uma mesma tarefa. Além da proposição de métodos construtivos para a resolução do problema, apresenta-se uma metaheurística como forma de demostrar como pode-se aprimorar os resultados gerado pelos métodos construtivos. Experimentações computacionais foram elaboradas e realizadas para comparação dos algoritmos. Dentre as heurísticas construtivas a que apresentou melhor desempenho foi a \"EDD + NEH + LS1 + LS2\'\', na qual utiliza uma lógica de inserção. A metaheurística proposta é baseada no procedimento IG (iterated greedy), sendo que há melhora de resultado em relação as heurísticas construtivas. Assim, espera-se que essa pesquisa possa ser utilizada e aplicada pela indústria de manufatura para aumentar a efetividade da programação da produção. / Efficient organizations are those that manage to keep the quality, cost and time strands balanced. With respect to the variable time, there are several stages of the production chain in which it must be monitored. When scheduling in companies is not prioritized, several negative effects incur. One of them is the delay in relation to the due date, for which the corporation can suffer financial penalties, in addition to a negative exposure to the brand, which may have its credibility challenged. Therefore, this research aims to propose constructive methods, which minimizes the performance criterion of total tardiness. In order to approximate the method to the reality of the industries, preventive maintenance constraints will be considered. And the environment of the study will be the no-wait flowshop, in which jobs are processed continuously and without interruptions between one operation and another of the same job. In addition to proposing constructive methods to solve the problem, a metaheuristic is presented as a way of demonstrating how to improve the results generated by the constructive methods. Computational experiments were elaborated and performed for comparison of the algorithms. Among the constructive heuristics that presented the best performance was \"EDD + NEH + LS1 + LS2\", in which it uses an insertion logic. The proposed metaheuristic is based on the IG (iterated greedy) procedure, and there is an improvement of the result in relation to the constructive heuristics. Thus, it is expected that this research can be used and applied by the manufacturing industry to increase the effectiveness of scheduling.

Este trabalho trata do problema de programação de operações no ambiente flow shop com máquinas múltiplas, com seus tempos de preparação (setup) assimétricos e dependentes da seqüência de processamento das tarefas. Este ambiente de produção é comum em indústrias gráficas, químicas, têxteis, de papel e de tinta, caracterizadas por sistemas com amplo mix de produtos. Qualquer processo produtivo requer um gerenciamento eficaz por meio do Planejamento e Controle da Produção (PCP). Esta atividade inclui a programação da produção, ou seja, a alocação de recursos para a execução de tarefas em uma base de tempo. A atividade de programação é uma das tarefas mais complexas no gerenciamento de produção, pois há a necessidade de lidar com diversos tipos diferentes de recursos e atividades simultaneamente. Além disso, o número de soluções possíveis cresce exponencialmente em várias dimensões, de acordo com a quantidade de tarefas, operações ou máquinas, conferindo uma natureza combinatorial ao problema. No ambiente estudado neste trabalho as operações de cada tarefa são executadas em múltiplos estágios de produção, podendo variar a quantidade de máquinas em cada um deles. Cada operação é processada por apenas uma máquina em cada estágio. Os tempos de preparação das máquinas possuem uma variabilidade relevante em função da ordem de execução das tarefas nas máquinas. A função-objetivo considerada é a minimização da duração total da programação (makespan). Foram desenvolvidos quatro métodos heurísticos construtivos com base em algoritmos reportados na literatura para solução de problemas flow shop permutacional e máquinas paralelas no ambiente cujo tempo de setup é dependente da seqüência. Como não foram encontrados na literatura métodos para programação no ambiente tratado neste trabalho, os algoritmos construídos foram comparados entre si. O foco da pesquisa foi o estudo da influência da relação entre as ordens de grandeza dos tempos de processamento e de setup em cada método de solução. Os resultados obtidos na experimentação computacional foram analisados e discutidos com base na porcentagem de sucesso, desvio relativo (%), desvio-padrão do desvio relativo e tempo médio de computação / This work adressess the hybrid flow shop scheduling problem with asymmetric sequence dependent setup times. This environment of production system is common in graphical, chemical, fabric, paper and ink industries. It’s characterized by systems with large mix of products. Any productive process requires an efficient management by means of Production Planning and Control. This activity includes scheduling, i.e., the resources allocation for the execution of jobs in a time base. Scheduling is one of the tasks most complex in production management, since it deals simultaneously with different types of resources and activities. Moreover, the number of possible solutions grows exponentially in some dimensions, in accordance with the number of jobs, operations or machines, conferring a combinatorial nature to the problem. In the environment studied in this work, the operations of each job are processed in multiple production stages. The number of machines in each stage can be different. Each operation is processed by only one machine in each stage. The setup times have a significant variability in function of the sequence of job processing on the machines. The objective is minimizing the total time to complete the schedule (makespan). Four constructive heuristic methods were developed on the basis of algorithms reported in the literature for solving permutation flow shop and parallel machine problems with sequence dependent setup times. The proposed heuristic methods have been compared between themselves, since no constructive heuristics have been found in the literature for the scheduling problem considered in this work. The focus of the research was the study of the influence of the relations among the range of the times processing and setup times in each method. The statistics used in order to evaluate the heuristic performances were the percentage of success (in finding the best solution), relative deviation, standard deviation of relative deviation and average computation time. Results from computational experience are discussed

Os processos industriais de produção exigem uma programação da produção efetiva. Essa atividade consiste da alocação dos recursos produtivos, a fim de executar tarefas determinadas por um período de tempo definido. Programar a produção é uma das atividades mais complexas do Planejamento da Produção, pois existem diferentes tipos de recursos a serem administrados simultaneamente. E também a quantidade de possíveis soluções aumenta exponencialmente com o aumento da quantidade de tarefas e máquinas presentes no sistema. A proposta deste trabalho é apresentar um método heurístico construtivo para a solução de problemas flow shop permutacional. A função-objetivo utilizada é a minimização do tempo total da programação (makespan). O algoritmo foi desenvolvido com base no melhor algoritmo construtivo presente na literatura, e os resultados obtidos são discutidos e analisados com base na porcentagem de sucesso, desvio relativo médio e tempo médio de computação. / Industrial productive processes demand an effective production scheduling. These activities consist in allocating the productive resources in order to execute determined jobs for a established period of time. Scheduling the production is one of the most complex activities involved in Planning the Production because there are different kinds of resources to be managed simultaneously. Furthermore, the amounts of feasible solutions increase exponentially as the number of jobs and machines in large systems. This dissertation presents a constructive heuristic method to solve the permutational flow shop problem. The evaluation criterion is the total production elapsed time (makespan). The developed algorithm was based on the best algorithm found in the literature, the results are analysed based on the success rate, mean relative deviation and computing time.

A teoria de programação da produção preocupa-se em fornecer diretrizes e métodos eficientes para a utilização dos recursos nas atividades produtivas. Este trabalho investiga o problema de programação da produção em ambientes flow shop com máquinas múltiplas e tempos de preparação das máquinas assimétricos e dependentes da seqüência de execução das tarefas. A atividade de programação da produção constitui uma das várias funções executadas pelo planejamento e controle da produção, que tem como objetivo comandar e gerenciar o processo produtivo, e caracteriza uma das atividades mais complexas no gerenciamento dos sistemas produtivos. A programação da produção preocupa-se com a alocação de recursos sobre o tempo para executar um conjunto de tarefas. No ambiente estudado neste trabalho as operações de cada tarefa são executadas em múltiplos estágios de produção, podendo variar a quantidade de máquinas em cada um deles. Cada operação é processada por apenas uma máquina em cada estágio. Os tempos de preparação das máquinas possuem uma variabilidade relevante em função da ordem de execução das tarefas nas mesmas. A função-objetivo considerada é a minimização do tempo médio de fluxo. Foram desenvolvidos quatro métodos heurísticos construtivos com base em algoritmos reportados na literatura para solução do problema flow shop permutacional e máquinas paralelas cujo tempo de setup é dependente da seqüência de execução das tarefas. Como não foram encontrados na literatura métodos de solução para o problema investigado neste trabalho, os algoritmos propostos foram comparados entre si. Foi efetuado um estudo da influência da relação entre as ordens de grandeza dos tempos de processamento das tarefas e do setup das máquinas em cada método de solução. Os resultados obtidos na experimentação computacional foram analisados e discutidos com base na porcentagem de sucesso, desvio relativo, desvio-padrão do desvio relativo e tempo médio de computação. / Scheduling theory attempts to provide guidelines and efficient methods to the use of the resources in the productive activities. This study investigates the hybrid flow shop problem with asymmetric sequence dependent setup times. The activity of production scheduling constitute is one of the several functions carried by production planning and control, which has as the objective command and management the production system, and characterize is one of the tasks most complex in production management. This activity of the scheduling aims within the allocation of the resources for the execution of jobs in a time base. In the environment studied in this work, the operations of each job are processed in multiple production stages. The number of machines in each stage can be different. Each operation is processed by only one machine in each stage. The setup times have a significant variability in function of the sequence of job processing on the machines. The objective is minimizing the mean flow time. Four constructive heuristic methods were proposed on the basis of algorithms reported in the literature for solving permutation flow shop and parallel machine problems with sequence dependent setup times. The proposed heuristic methods will have compared between themselves, since no constructive heuristics have been found in the literature for the scheduling problem considered in this work. It was carried out the study of the influence of the relations among the range of the times processing and setup times in each method. The statistics used in order to evaluate the heuristic performances were the percentage of success (in finding the best solution), relative deviation, standard deviation of relative deviation and average computation time. Results from computational experience are discussed.

Este trabalho aborda o problema de programação de tarefas, a partir de um caso específico, conhecido como Flow Shop com buffer zero. O problema consiste em programar n tarefas em m máquinas no ambiente Flow Shop permutacional. Com o aumento do nível de exigência dos clientes, pesquisas que buscam o atendimento das datas de entrega têm se tornado de extrema importância em ambientes de manufatura. Este trabalho analisa o problema de minimização do atraso total no ambiente Flow Shop onde não existe a possibilidade de armazenagem das tarefas entre estágios de produção sucessivos (buffer zero), tendo como consequência o bloqueio de máquinas. A Heurística Evolutiva Clustering Search foi proposta e analisada para a obtenção de soluções de altíssima qualidade para o problema. Finalmente, uma extensa experimentação computacional foi realizada. Quando comparado com o melhor método reportado na literatura, o método proposto apresentou qualidade superior. / This work deals with the Flow Shop scheduling problem. The objective is scheduling n jobs on m machines in the Permutation Flow Shop environment. With the increasing customer demand level, researches that aims the attendance of due dates have become extremely important in manufacturing process. This work studies the total tardiness minimization problem in the flow shop environment where there is no buffer storage between machines, resulting in the machine block. The Heuristic Evolutionary Clustering Search was proposed and analyzed to obtain high quality solutions to the problem. Finally, an extensive computational experiment was performed. When compared to the best method reported in the literature, the proposed method showed high quality.

Esse trabalho de investigação visa a realização de uma análise sistemática, integrada e iterativa da utilização de algoritmos heurísticos aplicados aos problemas de estimativa de parâmetros e detecção multiusuário, sob o ponto de vista do compromisso desempenho × complexidade. O sistema considera topologias do tipo CDMA com exploração de diversidade multidimensional, ou seja, que utilizam uma ou mais técnicas de diversidade, considerando a diversidade de código, tempo, frequência e espaço, entre outras, sujeitos a desvanecimentos multipercurso. A solução integrada para os problemas de estimativa de parâmetros e detecção multiusuário consiste no uso recorrente de técnicas heurísticas. Além disso, estabelece-se uma análise comparada e sistêmica de convergência e de complexidade computacional da técnica de detecção proposta com alguns outros métodos, heurísticos ou determinísticos, relatados na literatura, considerando como métrica de desempenho o número de operações computacionais que cada estratégia requer para a detecção simultânea da informação de todos os usuários ativos no sistema. Por fim, e mais importante, considera-se como a principal contribuição deste trabalho a sistematização da utilização dos algoritmos heurísticos no processo de otimização dos problemas já citados, caracterização de limiares de desempenho e análise de complexidade destas técnicas, trazendo à comunidade científica parâmetros suficientes que devem ser respeitados na configuração dos algoritmos para garantia de resultados satisfatórios quando da utilização destes métodos em problemas de detecção multiusuário com diversidade multidimensional e estimativa de parâmetros. / This work will perform a systematic, integrated and iterative research of heuristic algorithms applied to parameter estimation and multiuser detection problems, considering the performance × complexity tradeoff. The CDMA systems with multidimensional diversity exploitation, i.e., with one or more diversity techniques, code diversity, frequency, time and space, among other, in multipath fading channel scenarios are considered. The integrated solution for parameter estimation and multiuser detection problem uses heuristic techniques in recurrent form. In addition, we intend to establish a systemic and comparative analysis of convergence and computational complexity of the proposal detection technique with some other methods, heuristic or deterministic, reported in the literature, considering the number of computational operations that each strategy requires for simultaneous detection from all active users as a performance metrics. Finally, and most importantly, this work systematizes the heuristic algorithms approach in the optimization problems process already mentioned, considering the thresholds for performance and complexity of these techniques, bringing the scientific community enough configuration parameters that must be respected in the setup algorithms step to guarantee satisfactory results when using these methods to multiuser detection with multidimensional diversity and parameter estimation problems.

Inicialmente este problema é enquadrado no contexto mais amplo de Corte e Empacotamento e uma forma exata de resolver o problema é apresentada. O problema é NP-'Arduo no sentido forte e extremamente difícil de ser resolvido na prática, por isso uma atenção especial aos algoritmos aproximativos e seus desempenhos, não poderia ser omitida. Como resultado, uma classe de algoritmos aproximativos (heurísticas e meta-heurísticas) foi desenvolvida e seus desempenhos avaliados com relação às heurísticas famosas. O procedimento para o preenchimento dos itens dentro dos bins utiliza o bem conhecido princípio da alocação em pontos de cantos. Os critérios para a estabilidade estática dos itens dentro dos bins são apresentados com detalhes. Uma abordagem distribuída também foi usada como forma de resolver o problema, com o intuito de diminuir o tempo de execução computacional dos algoritmos aproximativos que levam em conta a estabilidade estática dos itens dentro dos bins. Grande quantidade de experimentos computacionais são apresentados para problemas com até 90 itens (com e sem estabilidade estática) e os resultados são comparados com aqueles obtidos da literatura. Por último, foi sugerida algumas idéias para o direcionamento das futuras pesquisas sobre o problema.