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.

Modelos de simulação usados para representar uma malha ferroviária com a circulação de trens percorrendo nela um ciclo fechado, estão sujeitos a diversas interferências. Essas interferências são representadas pela circulação de outros trens, bem como pelas filas que são formadas junto aos terminas de carga e descarga, que alteram a programação inicialmente idealizada. A validação desses modelos de simulação é prejudicada por essas interferências, e a busca por um correto procedimento de validação deve ter como base o adequado direcionamento e alocação dos trens. A carência de estudos sobre a validação de simulações aplicadas a sistemas ferroviários, que considerem a característica especifica de trens de ciclo e as interferências citadas, possibilitou a elaboração desta tese, a qual sinaliza que o desenvolvimento de algoritmos que representam o processo de movimentação dos trens em nível de detalhe suficiente, e a adoção de um método de direcionamento adequado, permitem a validação do modelo para esse tipo de sistema. Das três alternativas avaliadas para representar o direcionamento: escolha aleatória entre diversos pontos de carregamento para atender um destino final ou realizado por rotina com a mesma finalidade inserida no próprio simulador, e por modelo otimizador acessado externamente pelo simulador, foi selecionada a segunda opção por permitir uma validação do modelo mais próxima da realidade e realizar experimentos com menor tempo computacional. Uma vez programado o modelo de simulação com o direcionamento de trens escolhido, foi possível conduzir experimentos para medir a sensibilidade com relação as principais variáveis que permitem o dimensionamento de sistemas ferroviários brasileiros. / The rail network simulation models considering trains on closed loop may have many disturbances. These disturbances are caused by the railnet traffic, or queues at the load/unload stations, that changes the movement previously planned. The validation of these simulation models can be problematic because of these disturbances, and the search for the right validation procedure must count with a good train destination choosing process. The lack of studies about the validation of simulations applied to rail networks, considering the specific features of the closed loop trains and the disturbances, have leaded this thesis development, which proves that the development of algorithms that represent the movement process of the trains under sufficient detailing level, and the adoption of a correct destination choosing process, reaches the model validation. From the three options evaluated to represent this destination choosing procedure: random choosing between many loading points to one unloading point, or an internal model routine to do this same task, or an external optimization model called from the simulation model, was choosen the second option, because it validates the model and runs the simulation experiment faster. Once prepared the model with the destination choosing process selected, was possible to conduct experiments to measure the model sensitivity to the main parameters at the design of brazilian rail networks.

A presente pesquisa buscou resolver o problema de planejamento de operações submarinas através das perspectivas de programação de tarefas e dimensionamento de frota. O problema consistiu em estabelecer a melhor sequência de tarefas a serem atendidas por embarcações levando em consideração sua compatibilidade, regras de sequenciamento e o tamanho da frota. O problema é uma extensão do modelo clássico de roteirização com janelas de tempo com o objetivo de minimizar os custos associados à roteirização e as perdas econômicas associadas às interrupções de produção. A resolução do trabalho concentrou-se no curto e longo prazo, utilizando como principal método de solução a heurística Simulated Anneling por meio de um algoritmo de simulação-otimização. / This research aimed at solving the problem of planning underwater operations that involves job scheduling and fleet sizing decisions. The problem consisted in establish the best sequence of tasks to be atended by vessels taking into account compatibility constraints, sequencing rules and the size of the fleet. The problem is an extension of the classical vehicle routing problem with time windows. The objective is to minimize the routing costs and the economic losses associated with production losses. The solution procedure focused on short and long-term decisions based on the heuristic Simulated Anneling through a simulation-optimization algorithm.

Recent empirical findings suggest that firms might not always engage in economically optimal tax planning. We conduct a series of four laboratory experiments with 223 students and 62 tax professionals to examine whether decision biases offer a behavioral explanation for tax outcomes. We find that individuals overestimate the importance of tax rates relative to the tax base when facing time pressure in tax-planning decisions. This systematic decision bias results in suboptimal choices. In line with the theory of rational inattention, we observe that increasing tax-burden differences between two tax-planning strategies weakly mitigate the decision bias. However, tax-planning behavior is unaffected by the level of experience: students and highly experienced tax professionals are similarly prone to biased decision-making. Overall, our findings suggest that overestimating the implications of salient tax-rate information can cause decision biases and contribute to heterogeneity in tax outcomes. / Series: WU International Taxation Research Paper Series

The space of compile-time transformations and or run-time options which can improve the performance of a given code is usually so large as to be virtually impossible to search in any practical time-frame. Thus, heuristics are leveraged which can suggest good but not necessarily best configurations. Unfortunately, since such heuristics are tightly coupled to processor architecture performance is not portable; heuristics must be tuned, traditionally manually, for each device in turn. This is extremely laborious and the result is often outdated heuristics and less effective optimisation. Ideally, to keep up with changes in hardware and run-time environments a fast and automated method to generate heuristics is needed. Recent works have shown that machine learning can be used to produce mathematical models or rules in their place, which is automated but not necessarily fast. This thesis proposes the use of active machine learning, sequential analysis, and active feature acquisition to accelerate the training process in an automatic way, thereby tackling this timely and substantive issue. First, a demonstration of the efficiency of active learning over the previously standard supervised machine learning technique is presented in the form of an ensemble algorithm. This algorithm learns a model capable of predicting the best processing device in a heterogeneous system to use per workload size, per kernel. Active machine learning is a methodology which is sensitive to the cost of training; specifically, it is able to reduce the time taken to construct a model by predicting how much is expected to be learnt from each new training instance and then only choosing to learn from those most profitable examples. The exemplar heuristic is constructed on average 4x faster than a baseline approach, whilst maintaining comparable quality. Next, a combination of active learning and sequential analysis is presented which reduces both the number of samples per training example as well as the number of training examples overall. This allows for the creation of models based on noisy information, sacrificing accuracy per training instance for speed, without having a significant affect on the quality of the final product. In particular, the runtime of high-performance compute kernels is predicted from code transformations one may want to apply using a heuristic which was generated up to 26x faster than with active learning alone. Finally, preliminary work demonstrates that an automated system can be created which optimises both the number of training examples as well as which features to select during training to further substantially accelerate learning, in cases where each feature value that is revealed comes at some cost.

Escalonamento de processos é um tipo de problema de otimização combinatória no qual devemos alocar máquinas à tarefas por períodos específicos de tempo. A literatura contém diversos estudos propondo técnicas para resolver modelos de escalonamento de processos como o job shop e o open shop. Esses modelos permitem que os passos no processo produtivo sejam ou completamente ordenados ou sem ordenação alguma. Com o aumento da complexidade das aplicações industriais no encontramos, mais recentemente, diversos trabalhos que propõe problemas de escalonamento de processos mais gerais para modelar mais precisamente os processos produtivos. O mixed shop, group shop e partial shop são exemplos de tais modelos. Nesse trabalho nós propomos uma busca tabu iterada para o partial shop, que é um modelo geral que inclui diversos modelos mais restritivos. Os componentes novos mais importantes da técnica são o gerador de solução inicial, a vizinhança e o limite inferior para a vizinhança. Em experimentos computacionais nós conseguimos demonstrar que a heurística genérica e única é capaz de competir, e as vezes superar, as técnicas de estado de arte desenvolvidas especificamente para partial, open, mixed e group shop. Algumas vezes uma máquina é o gargalo de um processo produtivo, e é replicada. Na literatura o caso das máquinas paralelas foi incluído em diversas extensões de problemas de escalonamento de processos. Nessa tese nós também propomos uma técnica para escalonar as máquinas paralelas, sem incluí-las explicitamente na representação do problema. Nós usamos técnicas gerais para os casos sem máquinas paralelas para produzir uma busca heurística tabu rápida, e estado da arte, para o caso do job shop com máquinas paralelas. / Shop scheduling is a combinatorial optimization type of problem in which we must allocate machines to jobs for specific periods time. A set of constraints defines which schedules are valid, and we must select one that minimizes or maximizes an objective function. In this work we use the makespan, which is the time the last job finishes. The literature contains several studies proposing techniques to solve shop problems such as the job shop and open shop. These problems allow the steps of the production processes to be either fully ordered or not ordered at all. With increasing complexity and size of industrial applications we find, more recently, several works which propose more general shop problems to model the production processes more accurately. The mixed shop, group shop and partial shop are examples of such problems In this work we propose an iterated tabu search for the partial shop, which is a general problem and includes several other more restrictive shop problems. The most important novel components of the solver are the initial solution generator, the neighbourhood, and the lower bound for the neighbourhood. In computational experiments we were able to show that the general partial shop solver is able to compete with, and sometimes surpass, the state-of-the-art solvers developed specifically for the partial, open, mixed and group shops. Sometimes a machine is a bottleneck in the production process, and is replicated. In the literature the parallel machines case has being included in several extensions of shop problems. In this thesis we also propose a technique to schedule the parallel machines heuristically, without including them explicitly in the representation of the problem. We use general techniques for the non-parallel machine cases to produce a fast tabu search heuristic results for the job shop with parallel machines.

The thesis focuses on optimization of inbound and outbound truck scheduling with thegoal of minimizing total operation time of cross docking. A model of cross docking isdeveloped; two different methods are applied on the model in order to find an optimaldocking sequence for receiving and shipping trucks and their assignment to receiving andshipping docks, and product routing from receiving to shipping trucks.The two methods used were mathematical modeling and heuristic algorithm. For the firstmethod, a mixed integer programming model was developed to minimize total operationtime; AMPL modeling language is used for the mathematical modeling for small sizedproblems. For the second method, a heuristic algorithm was developed to find nearoptimal solutions fast and was used for problems of larger size. In order to examine theperformance of heuristic algorithm, small problems were solved by both mathematicalmodel and the heuristic algorithm.The results from the mathematical model and the heuristic algorithm are very close withslight differences in receiving and shipping truck docking sequence, and in productrouting between these two methods. In addition, the heuristic algorithm also calculatesnumber of products transferring from receiving trucks to the temporary storage as well asthe number of products transferring from the temporary storage to shipping truck incontrary to the mathematical model. Total number of units of products passing throughthe temporary storage calculated by heuristic algorithm is presented and it can be seenthat the heuristic algorithm transfers to the temporary storage as few products as possible.Furthermore, in cases that receiving and shipping trucks are divided into groups orclusters in the cross docking operation, heuristic algorithm can be used to calculateoptimal number of receiving and shipping docks based on preferences of total operationtime or total number of products passing through the temporary storage.Another issue which is focused on is the problem of dock door assignment. Closeshipping docks to each receiving dock are determined and the percentage of productstransferred from a receiving dock to its close shipping docks is calculated as a method tomeasure the performance of the dock assignment solution.

Alors que l’informatique en brouillard amène les ressources de traitement et de stockage à la périphérie du réseau, il existe un besoin croissant de placement automatisé (c.-à-d. La sélection de l'hôte) pour déployer des applications distribuées. Un tel placement doit être conforme aux besoins en ressources des applications dans une infrastructure de brouillard hétérogène et dynamique, et traiter la complexité apportée par les applications Internet des objets (IoT) liées aux capteurs / actionneurs. Cette thèse présente un modèle, une fonction objective et des heuristiques pour résoudre le problème de la mise en place d'applications IoT distribuées dans le brouillard. En combinant les heuristiques proposées, notre approche est capable de gérer les problèmes à grande échelle et de prendre efficacement des décisions de placement adaptées à l'objectif - en optimisant les performances des applications placées. L'approche proposée est validée par une analyse de complexité et une simulation comparative avec des tailles et des applications de tailles variables. / As fog computing brings processing and storage resources to the edge of the network, there is an increasing need of automated placement (i.e., host selection) to deploy distributed applications. Such a placement must conform to applications' resource requirements in a heterogeneous fog infrastructure, and deal with the complexity brought by Internet of Things (IoT) applications tied to sensors and actuators. This paper presents four heuristics to address the problem of placing distributed IoT applications in the fog. By combining proposed heuristics, our approach is able to deal with large scale problems, and to efficiently make placement decisions fitting the objective: minimizing placed applications' average response time. The proposed approach is validated through comparative simulation of different heuristic combinations with varying sizes of infrastructures and applications.

Este trabalho aborda o problema de programação da produção em um flexible flow line com tempos de setup. De acordo com a literatura, este ambiente pode ser considerado como um caso especial do Flow Shop com múltiplas máquinas, onde as tarefas podem saltar estágios. Neste estudo, foram analisados dois problemas: o primeiro, com tempos de setup independentes da sequência, e o segundo, com setup dependente da sequência de tarefas. Além disso, o setup das máquinas para as tarefas pode ser antecipado ou não. No primeiro caso, as máquinas de um estágio podem ser preparadas para o processamento de uma tarefa antes do seu término no estágio anterior. Se o setup não pode ser antecipado, a tarefa deve esperar o seu término no estágio de produção anterior. Este ambiente produtivo pode ser encontrado em um vasto número de indústrias tais como química, eletrônica, automotiva e têxtil. A medida de desempenho dos problemas é a duração total da programação (makespan). Este é um critério apropriado para sistemas de produção com grandes cargas de trabalho e em que a utilização dos recursos produtivos em longo prazo deve ser otimizada. O exame da literatura mostrou que há poucos estudos abordando a programação em flexible flow line. Considerando este aspecto, este trabalho apresenta heurísticas construtivas originais para a obtenção de programações apropriadas ao problema mencionado. Uma extensiva experimentação computacional foi executada para avaliar o desempenho relativo das heurísticas. Os resultados experimentais foram analisados e discutidos. / This work addresses the job scheduling on a flexible flow line with separate setup times. According to the literature, this scheduling problem can be considered as a special case of the Flow Shop with multiple machines, where the jobs may skip stages. Two modeled problems have been studied. In the first scheduling problem the setup times are sequence independent, and in the second one these times are sequence dependent. Moreover, the machine setup task can be either anticipatory or non-anticipatory. In the first case, a k-stage machine may be prepared for a job processing before its completion on the k-1 production stage. Otherwise, the setup task must wait for the job completion on the former production stage. This production environment can be found in a number of industries such as chemicals, electronics, automotive, and textiles. The performance measure of the production schedules is the makespan, that is, the total time to complete the schedule. This is an appropriate performance criterion for production systems with large workloads, and where the utilization of productive resources in the long term should be optimized. The literature examination has shown that there is a small number of studies dealing with flexible flow line scheduling. Having this in mind, this work introduces original constructive heuristics in order to obtain suitable schedules for the aforementioned scheduling problem. An extensive computational experience has been carried out in order to evaluate the relative performance of the heuristics. Experimental results are discussed.

O problema de empacotamento de itens irregulares com balanceamento da carga é encontrado no carregamento de aviões, caminhões e navios. O objetivo é empacotar itens irregulares utilizando o menor número de recipientes possível de forma que os recipientes estejam balanceados, que os itens não se sobreponham e estejam inteiramente contidos no recipiente. Neste trabalho, propomos três heurísticas bases com três variações cada para o problema com recipientes retangulares e irregulares. As heurísticas utilizam abordagens diferentes para representar os itens e para fazer o balanceamento. Uma das heurísticas utiliza malha para representação dos itens e faz o balanceamento dividindo o recipiente em quadrantes e revezando a alocação dos itens entre eles de forma que o balanceamento é feito de forma indireta. Tal heurística resolve o problema tanto para recipientes retangulares quanto irregulares. A segunda heurística utiliza a representação dos itens por polígonos e impossibilita a sobreposição de itens utilizando a técnica do nofit polygon. A heurística constrói a solução item por item, sem posições fixas e a cada item alocado, os itens são deslocados em direção ao centro de gravidade desejado do recipiente. Esta heurística resolve apenas problemas com recipientes retangulares. A última heurística é uma adaptação da heurística anterior para a resolução do problema com recipientes irregulares, de forma que o problema é resolvido em duas fases. Cada heurística base possui três variações cada, totalizando nove heurísticas. As heurísticas foram comparadas com outro trabalho da literatura e conseguiram melhorar os resultados para nove das dezenove instâncias testadas. / The irregular bin packing problem with load balancing is found in the loading of airplanes, trucks and ships. The aim is to use as few bins as possible to pack all the items so that all bins are balanced, items do not overlap and are fully contained in the bin. In this work, we propose three base heuristics with three variations each for the problem with rectangular and irregular bin. The three heuristics use different approaches to represent the items and to balance the bin. One of the heuristics uses a grid to represent the items and does the balancing by dividing the container into quadrants and alternating the allocation of items between them so that the balancing is done indirectly. Such heuristic solves the problem for both rectangular and irregular bins. The second heuristic uses the representation of items by polygons and uses the nofit polygon technique. The heuristic constructs the solution item by item, with no fixed positions and with each item allocated, the items are shifted towards the desired center of gravity of the bin. This heuristic only solves problems with rectangular bins. The last heuristic is an adaptation of the previous one to solve the problem with irregular bins, so that the problem is solved in two phases. Each base heuristic has three variations, totaling nine heuristics. The heuristics were compared with other work in the literature and managed to improve the results for nine of the nineteen instances tested.