A fundamental issue in warehouse operations is the storage location of the products it contains. Placing products intelligently within the system can allow for great reductions in order pick costs. This is essential because order picking is a major cost of warehouse operations. For example, a study by Drury conducted in the UK found that 63% of warehouse operating costs are due to order picking. When orders contain a single item, the COI rule of Heskett is an optimal storage policy. This is not true when orders contain multiple line items because no information is used about what products are ordered together. In this situation, products that are frequently ordered together should be stored together. This is the basis of the correlated storage assignment problem. Several previous researchers have considered how to form such clusters of products with an ultimate objective of minimizing travel time. In this dissertation, we focus on the alternate objective of minimizing multi-zone orders. We present a mathematical model and discuss properties of the problem. A Lagrangian relaxation solution approach is discussed. In addition, we both develop and adapt several heuristics from the literature to give upper bounds for the model. A cyclic exchange improvement method is also developed. This exponential size neighborhood can be efficiently searched in polynomial time. Even for poor initial solutions, this method finds solutions which outperform the best approaches from the literature. Different product sizes, stock splitting, and rewarehousing are problem features that our model can handle. The cyclic exchange algorithm is also modified to allow these operating modes. In particular, stock splitting is a difficult issue which most previous research in correlated storage ignores. All of our algorithms are implemented and tested on data from a functioning warehouse. For all data sets, the cyclic exchange algorithm outperforms COI, the standard industry approach, by an average of 15%.

No description available.

Lean distribution networks have been facing an increased exposure to the risk of unpredicted disruptions causing significant economic forfeitures. At the same time, the existing literature contains very few studies that examine the impact of fortification of facilities for improving network reliability. This dissertation presents three related classes of models that support the design of reliable distribution networks. The models extend the uncapacitated P-median and fixed-charge location models by considering heterogeneous facility failure probabilities, supplier backups, and facility fortification within a finite budget. The first class of models considers binary fortification via linear fortification functions. The second class of models extends binary fortification to partial (continuous) reliability improvement with linear fortification. This extension allows a more efficient utilization of limited fortification resources. The third class of models generalizes linear fortification to nonlinear to reflect the effect of diminishing marginal reliability improvement from fortification investment. For each of the models, we develop solution algorithms and demonstrate their computational efficiency. We present a detailed discussion on the novelty of the proposed models. The models are intended to support corporate decisions on the design of robust distribution networks using limited fortification resources.

In today's world, it is becoming increasingly important to be able to design high performance integrated circuits (ICs) and have them run at as low power as possible. Gate sizing and threshold voltage (Vt) assignment optimizations are one of the major contributors to such trade-offs for power and performance of ICs. In fact, the ever increasing design sizes and more aggressive timing requirements make gate sizing and Vt assignment one of the most important CAD problems in physical synthesis. A promising gate sizing optimization algorithm has to satisfy requirements like being scalable to tackle very large design sizes, being able to optimally utilize a large (but finite) number of possible gate configurations available in standard cell library based on different gate sizes and/or threshold voltages (Vt) and/or gate lengths (Lg), and also, being able to handle non-convex cell delays in modern cell libraries. The work in this thesis makes use of the research-oriented infrastructure made available as part of the ISPD (International Symposium on Physical Design) 2012 Gate Sizing Contest that addresses the issues encountered in modern gate sizing problems. We present a two-phase optimization approach where Lagrangian Relaxation is used to formulate the optimization problem. In the first phase, the Lagrangian relaxed subproblem is iteratively solved using a greedy algorithm, while in the second phase, a cell downsizing and Vt upscaling heuristic is employed to further recover power from the timing-feasible and power-optimized sizing solution obtained at the end of first phase. We also propose a multi-core implementation of the first-phase optimizations, which constitute majority of the total runtime, to take advantage of multi-core processors available today. A speedup of the order of 4 to 9 times is seen on different benchmarks as compared to serial implementation when run on a 2 socket 6-core machine. Compared to the winner of ISPD 2012 contest, we further reduce leakage power by 17.21% and runtime by 87.92%, on average, while obtaining feasible sizing solutions on all the benchmark designs. / text

The expansion of supply chains into global networks has drastically increased the distance travelled along shipping lanes in a logistics system. Inherently, the increase in travel distances produces increased carbon emissions from transport vehicles. When increased emissions are combined with a carbon tax or emissions trading system, the result is a supply chain with increased costs attributable to the emission generated on the transportation routes. Most traditional supply chain design models do not take emissions and carbon costs into account. Hence, there is a need to incorporate emission costs into a supply chain optimization model to see how the optimal supply chain configuration may be affected by the additional expenses. This thesis presents a mathematical programming model for the design of green supply chains. The costs of carbon dioxide (CO2) emissions were incorporated in the objective function, along with the fixed and transportation costs that are typically modeled in traditional facility location models. The model also determined the unit flows between the various nodes of the supply chain, with the objective of minimizing the total cost of the system by strategically locating warehouses throughout the network. The literature shows that CO2 emissions produced by a truck are dependent on the weight of the vehicle and can be modeled using a concave function. Hence, the carbon emissions produced along a shipping lane are dependent upon the number of units and the weight of each unit travelling between the two nodes. Due to the concave nature of the emissions, the addition of the emission costs to the problem formulation created a nonlinear mixed integer programming (MIP) model. A solution algorithm was developed to evaluate the new problem formulation. Lagrangian relaxation was used to decompose the problem by echelon and by potential warehouse site, resulting in a problem that required less computational effort to solve and allowed for much larger problems to be evaluated. A method was then suggested to exploit a property of the relaxed formulation and transform the problem into a linear MIP problem. The solution method computed the minimum cost for a complete network that would satisfy all the needs of the customers. A primal heuristic was introduced into the Lagrangian algorithm to generate feasible solutions. The heuristic utilized data from the Lagrangian subproblems to produce good feasible solutions. Due to the many characteristics of the original problem that were carried through to the subproblems, the heuristic produced very good feasible solutions that were typically within 1% of the Lagrangian bound. The proposed algorithm was evaluated through a number of tests. The rigidity of the problem and cost breakdown were varied to assess the performance of the solution method in many situations. The test results indicated that the addition of emission costs to a network can change the optimal configuration of the supply chain. As such, this study concluded that emission costs should be considered when designing supply chains in jurisdictions with carbon costs. Furthermore, the tests revealed that in regions without carbon costs it may be possible to significantly reduce the emissions produced by the supply chain with only a small increase in the cost to operate the system.

There is an increasing interest in sustainability and a growing debate about environmental policy measures aiming at the reduction of green house gas emissions across di erent economic sectors worldwide. The transportation sector is one major greenhouse gas emitter which is heavily regulated to reduce its dependance on oil. These regulations along with the growing customer awareness about global warming has led vehicle manufacturers to seek di erent technologies to improve vehicle e ciencies and reduce the green house gases emissions while at the same time meeting customer's expectation of mobility and exibility. Plug-in hybrid electric vehicles (PHEV) is one major promising solution for a smooth transition from oil dependent transportation sector to a clean electric based sector while not compromising the mobility and exibility of the drivers. In the medium term, plug-in hybrid electric vehicles (PHEV) can lead to signi cant reductions in transportation emissions. These vehicles are equipped with a larger battery than regular hybrid electric vehicles which can be recharged from the grid. For short trips, the PHEV can depend solely on the electric engine while for longer journeys the alternative fuel can assist the electric engine to achieve extended ranges. This is bene cial when the use pattern is mixed such that and short long distances needs to be covered. The plug-in hybrid electric vehicles are well-suited for logistics since they can avoid the possible disruption caused by charge depletion in case of all-electric vehicles with tight time schedules. The use of electricity and fuel gives rise to a new variant of the classical vehicle routing with time windows which we call the plug-in hybrid electric vehicle routing problem with time windows (PHEVRPTW). The objective of the PHEVRPTW is to minimize the routing costs of a eet of PHEVs by minimizing the time they run on gasoline while meeting the demand during the available time windows. As a result, the driver of the PHEV has two decisions to make at each node: (1) recharge the vehicle battery to achieve a longer range using electricity, or (2) continue to the next open time window with the option of using the alternative fuel. In this thesis, we present a mathematical formulation for the plug-in hybrid-electric vehicle routing problem with time windows. We solve this problem using a Lagrangian relaxation and we propose a new tabu search algorithm. We also present the rst results for the full adapted Solomon instances.

Orientador: Silvio Alexandrede Araujo / Banca: Bernardo Sobrinho Simões de Almada Lobo / Banca: Franklina Maria Bragion Toledo / Resumo: O problema de dimensionamento de lotes é um problema de otimização da produção, em que o objetivo é planejar a quantidade de itens a ser produzida em várias, ou única, máquinas em cada período ao longo do horizonte de tempo, de modo a tender uma demanda e otimizar uma função objetivo. Este trabalho aborda o problema de dimensionamento de lotes em um único estágio em um ambiente com máquinas paralelas distintas. Cada item pode ser produzido em qualquer máquina, acarretando um tempo de preparação que é gasto antes de começar a produção. O objetivo do trabalho consiste em obter limitantes inferiores de boa qualidade para este problema. Para tanto, é desenvolvido um método de solução baseado numa reformulação do problema a e na relaxação lagrangiana de um conjunto de restrições. Alguns resultados computacionais são apresentados algumas propostas futuras para a continuidade do trabalho. / Abstract: The lot-sizing problem is a production optimization problem, where the objective is to plan the quantity of items to be produced in multiple, or single, machines in each period over a time horizon, in order to satisfy a demand and optimize an objective function. This work addresses the single stage parallel machine lot-sizing problem. Each item can be produced on any machine, and incur a setup time before to start the production. The objective of this work is to lower bounds of good quality for this problem. A solution method is developed based on a reformulation of the problem and the Lagrangian relaxation of a set of constrainsts. Some computational results are presented comparing the proposed method with a method from the literature, and, some future researches are proposed. / Mestre

Ferramentas de projeto de circuitos integrados (do inglˆes, electronic design automation, ou simplesmente EDA) tˆem um papel fundamental na crescente complexidade dos projetos de circuitos digitais. Elas permitem aos projetistas criar circuitos com um n´umero de componentes ordens de grandezas maior do que seria poss´ıvel se os circuitos fossem projetados `a m˜ao como nos dias iniciais da microeletrˆonica. Neste trabalho, dois importantes problemas em EDA ser˜ao abordados: dimensionamento de portas e posicionamento detalhado dirigido a desempenho. Para dimensionamento de portas, uma nova metodologia de relaxac¸ ˜ao Lagrangiana ´e apresentada baseada em informac¸ ˜ao de temporarizac¸ ˜ao locais e propagac¸ ˜ao de sensitividades. Para posicionamento detalhado dirigido a desempenho, um conjunto de movimentos de c´elulas ´e criado usando uma formac¸ ˜ao ´otima atenta `a forc¸a de alimentac¸ ˜ao para o balanceamento de cargas. Nossos resultados experimentais mostram que tais t´ecnicas s˜ao capazes de melhorar o atual estado-da-arte. / Electronic design automation (EDA) tools play a fundamental role in the increasingly complexity of digital circuit designs. They empower designers to create circuits with several order of magnitude more components than it would be possible by designing circuits by hand as was done in the early days of microelectronics. In this work, two important EDA problems are addressed: gate sizing and timing-driven detailed placement. They are studied and new techniques developed. For gate sizing, a new Lagrangian-relaxation methodology is presented based on local timing information and sensitivity propagation. For timing-driven detailed placement, a set of cell movement methods are created using drive strength-aware optimal formulation to driver/sink load balancing. Our experimental results shows that those techniques are able to improve the current state-of-the-art.

Este trabalho aborda o problema de dimensionamento portas lógicas e assinalamento de Vt para otimização de potência, área e temporização em circuitos integrados modernos. O fluxo proposto é aplicado aos conjuntos de circuitos de teste dos Concursos do International Symposium on Physical Design (ISPD) de 2012 e 2013. Este fluxo também é adapatado e avaliado nos estágios pós posicionamento e roteamento global em projetos industriais de circuitos integrados, que utilizam uma ferramenta precisa de análise estática de temporização. As técnicas propostas geram as melhores soluções para todos os circuitos de teste do Concurso do ISPD 2013 (no qual foi a ferramenta vencedora), com em média 8% menos consumo de potência estática quando comparada com os outros concorrentes. Além disso, após algumas modificações nos algoritmos, nós reduzimos o consumo em mais 10% em média a pontência estáticas com relação aos resultados do concurso. O foco deste trabalho é desenvolver e aplicar um algoritmo estado-da-arte de seleção portas lógicas para melhorar ainda mais projetos industriais de alto desempenho já otimizados após as fases de posicionamento e roteamento do fluxo de projeto físico industrial. Vamos apresentar e discutir vários problemas encontrados quando da aplicação de técnicas de otimização global em projetos industriais reais que não são totalmente cobertos em publicações encontradas na literatura. Os métodos propostos geram as melhores soluções para todos os circuitos de referência no Concurso do ISPD 2013, no qual foi a solução vencedora. Considerando a aplicação industrial, as técnicas propostas reduzem a potência estática em até 18,2 %, com redução média de 10,4 %, sem qualquer degradação na qualidade de temporização do circuito. / This work addresses the gate sizing and Vt assignment problem for power, area and timing optimization in modern integrated circuits (IC). The proposed flow is applied to the Benchmark Suites of the International Symposium on Physical Design (ISPD) 2012 and 2013 Contests. It is also adapted and evaluated in the post placement and post global routing stage of an industrial IC design flow using a sign-off static timing analysis engine. The proposed techniques are able to generate the best solutions for all benchmarks in the ISPD 2013 Contest (in which we were the winning team), with on average 8% lower leakage with respect to all other contestants. Also, after some refinements in the algorithms, we reduce leakage by another 10% on average over the contest results. The focus of this work is to develop and apply a state-of-the-art cell selection algorithm to further improve already optimized high-performance industrial designs after the placement and routing stages of the industrial physical design flow. We present the basic concepts involved in the gate sizing problem and how earlier literature addresses it. Several problems found when applying global optimization techniques in real-life industrial designs, which are not fully covered in publications found in literature, are presented and discussed. Considering the industrial application, the proposed techniques reduce leakage power by up to 18.2%, with average reduction of 10.4% without any degradation in timing quality.

Este trabalho aborda o problema de dimensionamento portas lógicas e assinalamento de Vt para otimização de potência, área e temporização em circuitos integrados modernos. O fluxo proposto é aplicado aos conjuntos de circuitos de teste dos Concursos do International Symposium on Physical Design (ISPD) de 2012 e 2013. Este fluxo também é adapatado e avaliado nos estágios pós posicionamento e roteamento global em projetos industriais de circuitos integrados, que utilizam uma ferramenta precisa de análise estática de temporização. As técnicas propostas geram as melhores soluções para todos os circuitos de teste do Concurso do ISPD 2013 (no qual foi a ferramenta vencedora), com em média 8% menos consumo de potência estática quando comparada com os outros concorrentes. Além disso, após algumas modificações nos algoritmos, nós reduzimos o consumo em mais 10% em média a pontência estáticas com relação aos resultados do concurso. O foco deste trabalho é desenvolver e aplicar um algoritmo estado-da-arte de seleção portas lógicas para melhorar ainda mais projetos industriais de alto desempenho já otimizados após as fases de posicionamento e roteamento do fluxo de projeto físico industrial. Vamos apresentar e discutir vários problemas encontrados quando da aplicação de técnicas de otimização global em projetos industriais reais que não são totalmente cobertos em publicações encontradas na literatura. Os métodos propostos geram as melhores soluções para todos os circuitos de referência no Concurso do ISPD 2013, no qual foi a solução vencedora. Considerando a aplicação industrial, as técnicas propostas reduzem a potência estática em até 18,2 %, com redução média de 10,4 %, sem qualquer degradação na qualidade de temporização do circuito. / This work addresses the gate sizing and Vt assignment problem for power, area and timing optimization in modern integrated circuits (IC). The proposed flow is applied to the Benchmark Suites of the International Symposium on Physical Design (ISPD) 2012 and 2013 Contests. It is also adapted and evaluated in the post placement and post global routing stage of an industrial IC design flow using a sign-off static timing analysis engine. The proposed techniques are able to generate the best solutions for all benchmarks in the ISPD 2013 Contest (in which we were the winning team), with on average 8% lower leakage with respect to all other contestants. Also, after some refinements in the algorithms, we reduce leakage by another 10% on average over the contest results. The focus of this work is to develop and apply a state-of-the-art cell selection algorithm to further improve already optimized high-performance industrial designs after the placement and routing stages of the industrial physical design flow. We present the basic concepts involved in the gate sizing problem and how earlier literature addresses it. Several problems found when applying global optimization techniques in real-life industrial designs, which are not fully covered in publications found in literature, are presented and discussed. Considering the industrial application, the proposed techniques reduce leakage power by up to 18.2%, with average reduction of 10.4% without any degradation in timing quality.