Reformulações e relaxação Lagrangiana para o problema de dimensionamento de lotes com várias plantas

Pós-graduação em Matemática - IBILCE

Formulações fortes para o problema de dimensionamento de lotes com várias plantas

This paper considers the multi-plant lot sizing problem. Each item can be produced in any plant and it is possible to meet the demand of a particular plant with production from one (or several) other plants, in this case, incurs a transfer cost. The objective is todevelop strong formulations for this problem. Reformulations that based on the shortest path problem and facility location problem are investigated. Finally, some computational results are presented comparing all the proposed formulations.

Decentralized or centralized production : impacts to the environment, industry, and the economy

Since product take-back is mandated in Europe, and has effects for producers worldwide including the U.S., designing efficient forward and reverse supply chain networks is becoming essential for business viability. Centralizing production facilities may reduce costs but perhaps not environmental impacts. Decentralizing a supply chain may reduce transportation environmental impacts but increase capital costs. Facility location strategies of centralization or decentralization are tested for companies with supply chains that both take back and manufacture products. Decentralized and centralized production systems have different effects on the environment, industry and the economy. Decentralized production systems cluster suppliers within the geographical market region that the system serves. Centralized production systems have many suppliers spread out that meet all market demand. The point of this research is to help further the understanding of company decision-makers about impacts to the environment and costs when choosing a decentralized or centralized supply chain organizational strategy. This research explores; what degree of centralization for a supply chain makes the most financial and environmental sense for siting facilities; and which factories are in the best location to handle the financial and environmental impacts of particular processing steps needed for product manufacture. This research considered two examples of facility location for supply chains when products are taken back; the theoretical case involved shoe resoling and a real world case study considered the location of operations for a company that reclaims multiple products for use as material inputs. For the theoretical example a centralized strategy to facility location was optimal: whereas for the case study a decentralized strategy to facility location was best. In conclusion, it is not possible to say that a centralized or decentralized strategy to facility location is in general best for a company that takes back products. Each company’s specific concerns, needs, and supply chain details will determine which degree of centralization creates the optimal strategy for siting their facilities.

Problemas geométricos de localización

En esta memoria estudiamos problemas geométricos relacionados con la Localización de Servicios. La Localización de Servicios trata de la ubicación de uno o más recursos (radares, almacenes, pozos exploradores de petróleo, etc) de manera tal que se optimicen ciertos objetivos (servir al mayor número de usuarios posibles, minimizar el coste de transporte, evitar la contaminación de poblaciones cercanas, etc). La resolución de este tipo de problemas de la vida real da lugar a problemas geométricos muy interesantes. En el planteamiento geométrico de muchos de estos problemas los usuarios potenciales del servicio son representados por puntos mientras que los servicios están representados por la figura geométrica que mejor se adapta al servicio prestado: un anillo para el caso de radares, antenas de radio y televisión, aspersores, etc, una cuña si el servicio que se quiere prestar es de iluminación, por ejemplo, etc. Estas son precisamente las figuras geométricas con las que hemos trabajado. En nuestro caso el servicio será sólo uno y el planteamiento formal del problema es como sigue: dado un anillo o una cuña de tamaño fijo y un conjunto de n puntos en el plano, hallar cuál tiene que ser la posición del mismo para que se cubra la mayor cantidad de puntos. Para resolver estos problemas hemos utilizado arreglos de curvas en el plano. Los arreglos son una estructura geométrica bien conocida y estudiada dentro de la Geometría Computacional. Nosotros nos hemos centrado en los arreglos de curvas de Jordán no acotadas que se intersectan dos a dos en a lo sumo dos puntos, ya que estos fueron los arreglos con los que hemos tenido que tratar para la resolución de los problemas. De entre las diferentes técnicas para la construcción de arreglos hemos estudiado el método incremental, ya que conduce a algoritmos que son en general más sencillos desde el punto de vista de la codificación. Como resultado de este estudio hemos obtenido nuevas cotas que mejoran la complejidad del tiempo de construcción de estos arreglos con algoritmos incrementales. La nueva cota Ο(n λ3(n)) supone una mejora respecto a la cota conocida hasta el momento: Ο(nλ4(n)).También hemos visto que en ciertas condiciones estos arreglos pueden construirse en tiempo Ο(nλ2(n)), que es la cota óptima para la construcción de estos arreglos. Restringiendo el estudio a curvas específicas, hemos obtenido que los arreglos de n circunferencias de k radios diferentes pueden construirse en tiempo Ο(n2 min(log(k),α(n))), resultado válido también para arreglos de elipses, parábolas o hipérbolas de tamaños diferentes cuando las figuras son todas isotéticas.---ABSTRACT--- In this work some geometric problems related with facility location are studied. Facility location deals with location of one or more facilities (radars, stores, oil wells, etc.) in such way that some objective functions are to be optimized (to cover the maximum number of users, to minimize the cost of transportation, to avoid pollution in the nearby cities, etc.). These kind of real world problems give rise to very interesting geometrical problems. In the geometric version of many of these problems, users are represented as points while facilities are represented as different geometric objects depending on the shape of the corresponding facility: an annulus in the case of radars, radio or TV antennas, agricultural spraying devices, etc. A wedge in many illumination or surveillance applications. These two shapes are the geometric figures considered in this Thesis. The formal setting of the problem is the following: Given an annulus or a wedge of fixed size and a set of n points in the plane, locate the best position for the annulus or the wedge so that it covers as many points as possible. Those problems are solved by using arrangements of curves in the plane. Arrangements are a well known geometric structure. Here one deals with arrangements of unbounded Jordan curves which intersect each other in at most two points. Among the different techniques for computing arrangements, incremental method is used because it is easier for implementations. New time complexity upper bounds has been obtained in this Thesis for the construction of such arrangements by means of incremental algorithms. New upper bound is Ο(nλ3(n)) which improves the best known up to now Ο(nλ4(n)). It is shown also that sometimes this arrangements can be constructed in Ο(nλ2(n)), which is the optimal bound for constructing these arrangements. With respect to specific type of curves, one gives an Ο(n2 min(log(k),α(n))), algorithm that constructs the arrangement of a set of n circles of k different radii. This algorithm is also valid for ellipses parabolas or hyperbolas of k different sizes when all of them are isothetic.

Logística operacional: alocação de bases operacionais em distribuição de energia elétrica.

Ser eficiente é um requisito para a sustentabilidade das empresas concessionárias de distribuição de energia elétrica no Brasil. A busca pela eficiência deve estar em harmonia com a melhoria contínua da qualidade, da segurança e da satisfação dos consumidores e das partes envolvidas. O desafio de atender múltiplos objetivos requer que as empresas do setor desenvolvam soluções inovadoras, com a mudança de processos, tecnologia, estrutura e a capacitação das pessoas. Desenvolver um modelo operacional eficiente e uma gestão rigorosa dos custos são fatores-chave para o sucesso das empresas, considerando o contexto regulatório de revisão tarifária que incentiva a melhoria do desempenho. O modelo operacional é definido a partir da organização logística dos recursos para atendimento da demanda de serviços, que define também os custos fixos e variáveis de pessoal (salário, horas extras, refeições), infraestrutura (manutenção de prédios, ferramentas e equipamentos) e deslocamentos (manutenção de veículos, combustível), por exemplo. A melhor alocação e o melhor dimensionamento de bases operacionais possibilitam a redução dos custos com deslocamento e infraestrutura, favorecendo o aproveitamento da força de trabalho em campo, a melhoria do atendimento dos clientes e da segurança dos colaboradores. Este trabalho apresenta uma metodologia de otimização de custos através da alocação de bases e equipes operacionais, com o modelamento matemático dos objetivos e restrições do negócio e a aplicação de algoritmo evolutivo para busca das melhores soluções, sendo uma aplicação de Pesquisa Operacional, no campo da Localização de Instalações, em distribuição de energia elétrica. O modelo de otimização desenvolvido possibilita a busca pelo ponto de equilíbrio ótimo que minimiza o custo total formado pelos custos de infraestrutura, frota (veículos e deslocamentos) e pessoal. O algoritmo evolutivo aplicado no modelo oferece soluções otimizadas pelo melhoramento de conjuntos de variáveis binárias com base em conceitos da evolução genética. O modelo de otimização fornece o detalhamento de toda a estrutura operacional e de custos para uma determinada solução do problema, utilizando premissas de produtividade e deslocamentos (velocidades e distâncias) para definir as abrangências de atuação das bases operacionais, recursos (equipes, pessoas, veículos) necessários para atendimento da demanda de serviços, e projetar todos os custos fixos e variáveis associados. A metodologia desenvolvida neste trabalho considera também a projeção de demanda futura para a aplicação no estudo de caso, que evidenciou a efetividade da metodologia como ferramenta para a melhoria da eficiência operacional em empresas de distribuição de energia elétrica.

Ages and isotopic signatures of peat cores from a boreal landscape, Interior Alaska

To determine the influence of fire and thermokarst in a boreal landscape, we investigated peat cores within and adjacent to a permafrost collapse feature on the Tanana River Floodplain of Interior Alaska. Radioisotope dating, diatom assemblages, plant macrofossils, charcoal fragments, and carbon and nitrogen content of the peat profile indicate ~600 years of vegetation succession with a transition from a terrestrial forest to a sedge-dominated wetland over 100 years ago, and to a Sphagnum-dominated peatland in approximately 1970. The shift from sedge to Sphagnum, and a decrease in the detrended tree-ring width index of black spruce trees adjacent to the collapse coincided with an increase in the growing season temperature record from Fairbanks. This concurrent wetland succession and reduced growth of black spruce trees indicates a step-wise ecosystem-level response to a change in regional climate. In 2001, fire was observed coincident with permafrost collapse and resulted in lateral expansion of the peatland. These observations and the peat profile suggest that future warming and/or increased fire disturbance could promote permafrost degradation, peatland expansion, and increase carbon storage across this landscape; however, the development of drought conditions could reduce the success of both black spruce and Sphagnum, and potentially decrease the long-term ecosystem carbon storage.

Algorithmic Background of the Host Recommendation in the Adaptive Distributed Multimedia Server

Partial support of the Hungarian State Eötvös Scholarship, the Hungarian National Science Fund (Grant No. OTKA 42559 and 42706) and the Mobile Innovation Center, Hungary is gratefully acknowledged.

Az ellátási láncban elfoglalt pozíció és a szolgálatosodás – üzleti modellek Európában (Supply chain position and servitization – business models in Europe)

A szerzők célja, hogy megvizsgálják, milyen kölcsönhatásban áll az ellátási láncban elfoglalt pozíció, valamint a szolgálatosodás szintje az európai termelővállalatoknál. Vizsgálatuk azt mutatja, hogy a globalizáció és a termelés nemzetközivé válása mindkét tényezőt jelentős mértékben befolyásolja. A termelés globalizációs trendjeinek megfelelően így a kelet-európai (fejlődő), illetve a nyugat-európai (fejlett) országokban eltérő üzleti modellek válnak dominánssá, amelyek különböző ellátásilánc-pozícióval és más-más szintű szolgáltatásnyújtással jellemezhetőek. A domináns üzleti modellek mellett természetesen más üzleti modellek is működőképesnek bizonyulhatnak a két vizsgált régióban. A létesítmények elhelyezésére, valamint az üzleti eredményességre vonatkozó mutatók elemzésbe történő bevonásával cikkük az Európában működő üzleti modellek kialakításának okára, valamint jövőbeli fenntarthatóságára is megpróbál választ adni. __________ The objective of this paper is to examine the relationship between supply chain position and level of servitization in European manufacturing companies. The analysis shows that globalization and internationalization of production has dramatic impact on both phenomena. Due to the globalization trends different business models became dominant in the less developed Eastern-European and the more developed Western European countries, which can be characterized by different supply chain position and servitization level. Certainly other business models can also be successful in the two regions. Involving facility location motivations and business performance indicators the article shed light on the reasons of why these business models came alive and how sustainable they can be.

Cross-country and inter-temporal analysis of Supply Chain Integration (SCI): China, Hungary and the Netherlands - changes in SCI from 1996 to 2008

Using plant level data from a global survey with multiple time frames, one begun in the late 1990s, this paper introduces measures of supply chain integration and discusses the dynamic relationship between the level of integration and a set of internal and external performance measurements. Specifically, data from Hungary, The Netherlands and The People’s Republic of China are used in the analyses. The time frames considered range from the late 1990s till 2009, encompassing major changes and transitions. Our results seem to indicate that SCI has an underlying structure of four sets of indicators, namely: (1) delivery frequency from the supplier or to the customer; (2) sharing internal processes with suppliers; (3) sharing internal processes with buyers and (4) joint facility location with partners. The differences between groups in terms of several performance measures proved to be small, being mostly statistically insignificant - but looking at the ANOVA table we can conclude that in this sample of companies those having joint location with their partners seem to outperform others.

A Study of Some Centrality Measures in Graphs

Centrality is in fact one of the fundamental notions in graph theory which has established its close connection with various other areas like Social networks, Flow networks, Facility location problems etc. Even though a plethora of centrality measures have been introduced from time to time, according to the changing demands, the term is not well defined and we can only give some common qualities that a centrality measure is expected to have. Nodes with high centrality scores are often more likely to be very powerful, indispensable, influential, easy propagators of information, significant in maintaining the cohesion of the group and are easily susceptible to anything that disseminate in the network.

Distributed optimization in transportation and logistics networks

Many important problems in communication networks, transportation networks, and logistics networks are solved by the minimization of cost functions. In general, these can be complex optimization problems involving many variables. However, physicists noted that in a network, a node variable (such as the amount of resources of the nodes) is connected to a set of link variables (such as the flow connecting the node), and similarly each link variable is connected to a number of (usually two) node variables. This enables one to break the problem into local components, often arriving at distributive algorithms to solve the problems. Compared with centralized algorithms, distributed algorithms have the advantages of lower computational complexity, and lower communication overhead. Since they have a faster response to local changes of the environment, they are especially useful for networks with evolving conditions. This review will cover message-passing algorithms in applications such as resource allocation, transportation networks, facility location, traffic routing, and stability of power grids.

Location-routing problems of semi-obnoxious facilities: approaches and decision support

A presente tese resulta de um trabalho de investigação cujo objectivo se centrou no problema de localização-distribuição (PLD) que pretende abordar, de forma integrada, duas actividades logísticas intimamente relacionadas: a localização de equipamentos e a distribuição de produtos. O PLD, nomeadamente a sua modelação matemática, tem sido estudado na literatura, dando origem a diversas aproximações que resultam de diferentes cenários reais. Importa portanto agrupar as diferentes variantes por forma a facilitar e potenciar a sua investigação. Após fazer uma revisão e propor uma taxonomia dos modelos de localização-distribuição, este trabalho foca-se na resolução de alguns modelos considerados como mais representativos. É feita assim a análise de dois dos PLDs mais básicos (os problema capacitados com procura nos nós e nos arcos), sendo apresentadas, para ambos, propostas de resolução. Posteriormente, é abordada a localização-distribuição de serviços semiobnóxios. Este tipo de serviços, ainda que seja necessário e indispensável para o público em geral, dada a sua natureza, exerce um efeito desagradável sobre as comunidades contíguas. Assim, aos critérios tipicamente utilizados na tomada de decisão sobre a localização destes serviços (habitualmente a minimização de custo) é necessário adicionar preocupações que reflectem a manutenção da qualidade de vida das regiões que sofrem o impacto do resultado da referida decisão. A abordagem da localização-distribuição de serviços semiobnóxios requer portanto uma análise multi-objectivo. Esta análise pode ser feita com recurso a dois métodos distintos: não interactivos e interactivos. Ambos são abordados nesta tese, com novas propostas, sendo o método interactivo proposto aplicável a outros problemas de programação inteira mista multi-objectivo. Por último, é desenvolvida uma ferramenta de apoio à decisão para os problemas abordados nesta tese, sendo apresentada a metodologia adoptada e as suas principais funcionalidades. A ferramenta desenvolvida tem grandes preocupações com a interface de utilizador, visto ser direccionada para decisores que tipicamente não têm conhecimentos sobre os modelos matemáticos subjacentes a este tipo de problemas.

Business micro-location: factors, preferences and indicators to assess the influence factors

The paper presents a study on business micro-location behaviour as well as corresponding factors of influence, conducted in two metropolitan areas, Bucharest-Ilfov (Romania) and Greater Porto (Portugal). By business micro-location we refer to a specific site such as a building or facility, accommodating a business within a small, compact geographical area (e.g. metropolitan area). At this geographical scale, the macroeconomic layer factors were excluded, applicable when discern between regions or countries. The factors derived from location theory and previous empirical studies were surveyed, completing a cross-sectional analysis in order to find out the specific weights of the location factors and preferences, by region and by industry. Based on already established firms’ feedback on location, the specific weights were granted by each industry to the main location factors, types of areas, and types of accommodation facilities. The authors also suggested a model to integrate these results into a Geographical Information System (GIS).

Consensus strategies for signed profiles on graphs

The median problem is a classical problem in Location Theory: one searches for a location that minimizes the average distance to the sites of the clients. This is for desired facilities as a distribution center for a set of warehouses. More recently, for obnoxious facilities, the antimedian was studied. Here one maximizes the average distance to the clients. In this paper the mixed case is studied. Clients are represented by a profile, which is a sequence of vertices with repetitions allowed. In a signed profile each element is provided with a sign from f+; g. Thus one can take into account whether the client prefers the facility (with a + sign) or rejects it (with a sign). The graphs for which all median sets, or all antimedian sets, are connected are characterized. Various consensus strategies for signed profiles are studied, amongst which Majority, Plurality and Scarcity. Hypercubes are the only graphs on which Majority produces the median set for all signed profiles. Finally, the antimedian sets are found by the Scarcity Strategy on e.g. Hamming graphs, Johnson graphs and halfcubes

A branch-and-price approach to p-median location problems

This paper describes a branch-and-price algorithm for the p-median location problem. The objective is to locate p facilities (medians) such as the sum of the distances from each demand point to its nearest facility is minimized. The traditional column generation process is compared with a stabilized approach that combines the column generation and Lagrangean/surrogate relaxation. The Lagrangean/surrogate multiplier modifies; the reduced cost criterion, providing the selection of new productive columns at the search tree. Computational experiments are conducted considering especially difficult instances to the traditional column generation and also with some large-scale instances. (C) 2004 Elsevier Ltd. All rights reserved.