Hub and Spoke systems, is a important research area in localization theory. This occur, because of these systems are very used in logistics problems, e.g., telecommunication networks and transport of passenger and load.To serve the demand of each pair source destination, basically, the Hub and Spoke system replaces direct connections between the pairs for a hubs network. These hubs group the traffic sharing the transportation medium. To get the best hubs configuration is necessary efficient methods, because this problem, hubs allocation, is a NP-problem. In this work was developed an parallel implementation of the Benders Decomposition method for the uncapacitated multiple allocation hub location problem. In our implementation we use the Skorin- Kapov model. The parallel implementation of Benders Decomposition for hub and spoke problem is not known in literature. The results show that the parallel approach is applicable and more efficient that nonparallel one. The experiments reveals that the parallel algorithm had a time execution 70% minor when compared with the nonparallel one. / Sistemas do tipo eixo raio, tornaram-se uma importante área de pesquisa da teoria de localização nas últimas décadas. Esse destaque deve-se em grande parte ao sucesso de sua utilização em sistemas logísticos, tanto de transporte de passageiros quanto de cargas, e em redes de telecomunicações. Ao invés de servir cada par origem destino de demanda com uma conexão direta, sistemas do tipo eixo raio substituem essas conexões diretas por uma rede de concentradores. Esses concentradores permitem que o tráfego seja agrupado e transportado através de um meio de transporte compartilhado, para ser então entregue aos respectivos destinos. Sendo um problema NP, é necessário o uso de métodos eficientes para sua resolução. Neste trabalho, é desenvolvida uma implementação em paralelo do método de Decomposição de Benders para o problema de localização de concentradores de alocação múltipla não capacitados. A implementação em paralelo do método de Decomposição de Benders para o problema eixo raio não é conhecido na literatura, entretanto os bons resultados obtidos pelo algoritmo paralelo desenvolvido revelam que a abordagem paralela é aplicável e mais eficiente. Nos experimentos realizados, o algoritmo paralelo apresentou um tempo de resposta até 70% menor que o tempo de resposta do algoritmo seqüencial.

Submitted by Renata Lopes (renatasil82@gmail.com) on 2018-11-06T17:02:42Z No. of bitstreams: 1 marcelodesouzaaleixo.pdf: 2786878 bytes, checksum: dfbd57d9b8be2153917fe637209df9f0 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2018-11-23T13:19:16Z (GMT) No. of bitstreams: 1 marcelodesouzaaleixo.pdf: 2786878 bytes, checksum: dfbd57d9b8be2153917fe637209df9f0 (MD5) / Made available in DSpace on 2018-11-23T13:19:16Z (GMT). No. of bitstreams: 1 marcelodesouzaaleixo.pdf: 2786878 bytes, checksum: dfbd57d9b8be2153917fe637209df9f0 (MD5) Previous issue date: 2018-06-29 / Este trabalho apresenta uma metodologia para cálculo da reserva girante do sistema elétrico de potência. A proposta inclui a curva de capabilidade dos geradores bem como cenários de carga e de geração eólica bem como falhas no sistema de geração e transmissão. O fluxo de potência ótimo é utilizado para determinar as condições iniciais do sistema, caso base. A partir daí o problema é resolvido de forma interativa entre dois estágios em umaestruturamestreeescravo: Oproblemamestreutilizaprogramaçãolinearinteirapara determinar o número mínimo de unidades de geração disponíveis (ligadas); O problema escravo verifica se o número de unidades ligadas é suficiente para operação do sistema. Este problema corresponde ao Fluxo de Potência Ótimo com o objetivo de obter o mínimo corte de carga para cada condição operativa. O corte de Benders é produzido para cada cenário, altenativamente, será investigado a utilização da média dos cortes de Benders. O processo termina quando não ocorrer corte de carga. A metodologia é testada utilizando um sistema teste de 4 barras como exemplo tutorial e também aplicada nos sistemas IEEE 14, 39 e 118 barras. / This work presents a methodology for calculating the spinning reserve of the electric power system. The proposal includes the capability curve of the generators as well as errors of prediction of load, wind generation, failures in the system of generation and transmission. The optimal power flow is used to determine the initial conditions of the system, base case. From this point the problem is solved interactively between two stages in a master and slave structure: The first uses integer linear programming to determine the minimum number of available (turn on) generation units; The second corresponds to the Optimum Power Flow with the purpose of obtaining the minimum load shedding for each operative condition. The cut of Benders is produced for each scenario, alternatively, the use of the average of cuts will be investigated. The process ends when there is no load shedding. The methodology is tested using a 4-bar test system as a tutorial example and also applied in IEEE systems 14, 39 and 118 bars.

In this dissertation, we address three different combinatorial optimization problems (COPs), each of which has specific real-life applications. Owning to their specific nature, these problems are different from those discussed in the literature. For each of these problems, we present a mathematical programming formulation, analyze the problem to determine its useful, inherent structural properties, and develop an efficient methodology for its solution by exploiting these properties. The first problem that we address is the course timetabling problem encountered at Virginia Tech. The course timetabling problem for a university is a difficult problem and has been studied by many researchers over the years. As a result, a plethora of models and approaches have been reported in the literature. However, most of these studies have focused on applications pertaining to course scheduling for a single or at most few departments of a university. The sheer size of the university-wide timetabling problem that we address, involving thousands of courses to be scheduled in hundreds of classrooms in each semester, makes it a challenging problem. We employ an appropriate decomposition technique that relies on some inherent structural properties of the problem both during the modeling and algorithmic development phases. We show the superiority of the schedules generated by our methodology over those that are currently being used. Also, our methodology requires only a reasonable amount of computational time in solving this large-size problem. A facility layout problem involving arbitrary-shaped departments is the second problem that we investigate in this dissertation. We designate this problem as the arbitrary-shaped facility layout problem (ASFLP). The ASFLP deals with arranging a given set of departments (facilities, workstations, machines) within the confines of a given floor space, in order to optimize a desired metric, which invariably relates to the material handling cost. The topic of facility planning has been addressed rather extensively in the literature. However, a major limitation of most of the work reported in the literature is that they assume the shape of a department to be a rectangle (or even a square). The approach that relies on approximating an arbitrary-shaped department by a rectangle might result in an unattractive solution. The key research questions for the ASFLP are: (1) how to accurately model the arbitrary-shaped departments, and (2) how to effectively and efficiently determine the desired layout. We present a mixed-integer programming model that maintains the arbitrary shapes of the departments. We use a meta-heuristic to solve the large-size instances of the ASFLP in a reasonable amount of time. The third problem that we investigate is a supply chain scheduling problem. This problem involves two stages of a supply chain, specifically, a manufacturer and one or more customers. The key issue is to achieve an appropriate coordination between the production and distribution functions of the manufacturer so as to minimize the sum of the shipping and job tardiness costs. We, first, address a single customer problem, and then, extend our analysis to the case of multiple customers. For the single-customer problem, we present a polynomial-time algorithm to solve it to optimality. For the multiple-customer problem, we prove that this problem is NP-hard and solve it by appropriately decomposing it into subproblems, one of which is solvable in polynomial time. We propose a branch-and-bound-based methodology for this problem that exploits its structural properties. Results of an extensive computational experimentation are presented that show the following: (1) our algorithms are efficient to use and effective to implement; and (2) significant benefits accrue as a result of integrating the production and distribution functions. / Ph. D.

This dissertation develops mathematical models to efficiently manage the inland waterway port operations while minimizing the overall supply chain cost. In the first part, a capacitated, multi-commodity, multi-period mixed-integer linear programming model is proposed capturing diversified inland waterway transportation network related properties. We developed an accelerated Benders decomposition algorithm to solve this challenging NP-hard problem. The next study develops a two-stage stochastic mixed-integer nonlinear programming model to manage congestion in an inland waterway transportation network under stochastic commodity supply and water-level fluctuation scenarios. The model also jointly optimizes trip-wise towboat and barge assignment decisions and different supply chain decisions (e.g., inventory management, transportation decisions) in such a way that the overall system cost can be minimized. We develop a parallelized hybrid decomposition algorithm, combining Constraint Generation algorithm, Sample Average Approximation (SAA), and an enhanced variant of the L-shaped algorithm, to effectively solve our proposed optimization model in a timely fashion. While the first two parts develop models from the supply chain network design viewpoint, the next two parts propose mathematical models to emphasize the port and waterway transportation related operations. Two two-stage, stochastic, mixed-integer linear programming (MILP) models are proposed under stochastic commodity supply and water level fluctuations scenarios. The last one puts the specific focus in modeling perishable inventories. To solve the third model we propose to develop a highly customized parallelized hybrid decomposition algorithm that combines SAA with an enhanced Progressive Hedging and Nested Decomposition algorithm. Similarly, to solve the last mathematical model we propose a hybrid decomposition algorithm combining the enhanced Benders decomposition algorithm and SAA to solve the large size of test instances of this complex, NP-hard problem. Both proposed approaches are highly efficient in solving the real-life test instances of the model to desired quality within a reasonable time frame. All the four developed models are validated a real-life case study focusing on the inland waterway transportation network along the Mississippi River. A number of managerial insights are drawn for different key input parameters that impact port operations. These insights will essentially help decisions makers to effectively and efficiently manage an inland waterway-based transportation network.

No description available.

Logic-based Benders decomposition (LBBD) is a strategy for solving discrete optimisation problems. In LBBD, the optimisation problem is divided into a master problem and a subproblem and each part is solved separately. LBBD methods that combine mixed-integer programming and constraint programming have been successfully applied to solve large-scale scheduling and resource allocation problems. Such combinations typically solve an assignment-type master problem and a scheduling-type subproblem. However, a challenge with LBBD methods that have feasibility subproblems are that they do not provide a feasible solution until an optimal solution is found.  In this thesis, we show that feasible solutions can be obtained by finding and combining feasible parts of an infeasible master problem assignment. We use these insights to develop an acceleration technique for LBBD that solves a series of subproblems, according to algorithms for constructing a maximal feasible subset of constraints (MaFS). Using a multiprocessor scheduling problem as a benchmark, we study the computational impact from using this technique. We evaluate three variants of LBBD schemes. The first uses MaFS, the second uses irreducible subset of constraints (IIS) and the third combines MaFS with IIS. Computational tests were performed on an instance set of multiprocessor scheduling problems. In total, 83 instances were tested, and their number of tasks varied between 2794 and 10,661. The results showed that when applying our acceleration technique in the decomposition scheme, the pessimistic bounds were strong, but the convergence was slow. The decomposition scheme combining our acceleration technique with the acceleration technique using IIS showed potential to accelerate the method.

With the rise of online retailer giants like Amazon, and enhancements in internet and mobile technologies, online shopping is becoming increasingly popular. This has lead to new opportunities in online price optimization. The overarching motivation and theme of this thesis is to review these opportunities and provide methods and models in the context of retailers' online pricing decisions. In Chapter 2 a multi-period revenue maximization and pricing optimization problem in the presence of reference prices is formulated as a mixed integer nonlinear program. Two algorithms are developed to solve the optimization problem: a generalized Benders' decomposition algorithm and a myopic heuristic. This is followed by numerical computations to illustrate the effciency of the solution approaches as well as some managerial pricing insights. In Chapter 3 a data-driven quadratic programming optimization model for online pricing in the presence of customer ratings is proposed. A new demand function is developed for a multi-product, nite horizon, online retail environment. To solve the optimization problem, a myopic pricing heuristic as well as exact solution approaches are introduced. Using customer reviews ratings data from Amazon.com, a new customer rating forecasting model is validated. This is followed by several analytical and numerical insights. In Chapter 4 a multinomial choice model is used for customer purchase decision to find optimal personalized price discounts for an online retailer that incorporates customer locations and feedback from their reviews. Closed form solutions are derived for two special cases of this problem. To gain some analytical insights extensive numerical experiments are carried followed by several analytical and numerical insights. / Thesis / Doctor of Philosophy (PhD) / The increase in online retail and the improvements in mobile technologies has lead to advantages and opportunities for both customers and retailers. One of these advantages is the ability to keep and efficiently access records of historical orders for both customers and retailers. In addition, online retailing has dramatically decreased the cost of price adjustments and discounts compared to the brick and mortar environment. At the same time, with the increase in online retailing we are witnessing proliferations of online reviews in e-commerce platforms. Given this availability of data and the new capabilities in an online retail environment, there is a need to develop pricing optimization models that integrate all these new features. The overarching motivation and theme of this thesis is to review these opportunities and provide methods and models in the context of retailers' online pricing decisions.

In this work, we address a variety of problems with applications to `ethanol production from biomass', `agile manufacturing' and `mass customization' domains. Our motivation stems from the potential use of biomass as an alternative to non-renewable fuels, the prevalence of `flexible manufacturing systems', and the popularity of `mass customization' in today's highly competitive markets. Production scheduling and design and optimization of logistics network mark the underlying topics of our work. In particular, we address three problems, Biomass Logistics Problem, Hybrid Flow Shop Scheduling Problem, and Stochastic Demand Assembly Job Scheduling Problem. The Biomass Logistics Problem is a strategic cost analysis for setup and operation of a biomass supply chain network that is aimed at the production of ethanol from switchgrass. We discuss the structural components and operations for such a network. We incorporate real-life GIS data of a geographical region in a model that captures this problem. Consequently, we develop and demonstrate the effectiveness of a `Nested Benders' based algorithm for an efficient solution to this problem. The Hybrid Flow Shop Scheduling Problem concerns with production scheduling of a lot over a two-stage hybrid flow shop configuration of machines, and is often encountered in `flexible manufacturing systems'. We incorporate the use of `lot-streaming' in order to minimize the makespan value. Although a general case of this problem is NP-hard, we develop a pseudo-polynomial time algorithm for a special case of this problem when the sublot sizes are treated to be continuous. The case of discrete sublot sizes is also discussed for which we develop a branch-and-bound-based method and experimentally demonstrate its effectiveness in obtaining a near-optimal solution. The Stochastic Demand Assembly Job Scheduling Problem deals with the scheduling of a set of products in a production setting where manufacturers seek to fulfill multiple objectives such as `economy of scale' together with achieving the flexibility to produce a variety of products for their customers while minimizing delivery lead times. We design a novel methodology that is geared towards these objectives and propose a Lagrangian relaxation-based algorithm for efficient computation. / Doctor of Philosophy / In this work, we organize our research efforts in three broad areas - Biomass Supply Chain, Hybrid Flow Shop, and Assembly Job Shop, which are separate in terms of their application but connected by scheduling and logistics as the underlying functions. For each of them, we formulate the problem statement and identify the challenges and opportunities from the viewpoint of mathematical decision making. We use some of the well known results from the theory of optimization and linear algebra to design effective algorithms in solving these specific problems within a reasonable time limit. Even though the emphasis is on conducting an algorithmic analysis of the proposed solution methods and in solving the problems analytically, we strive to capture all the relevant and practical features of the problems during formulation of each of the problem statement, thereby maintaining their applicability. The Biomass Supply Chain pertains to the production of fuel grade ethanol from naturally occurring biomass in the form of switchgrass. Such a system requires establishment of a supply chain and logistics network that connects the production fields at its source, the intermediate points for temporary storage of the biomass, and bio-energy plant and refinery at its end for conversion of the cellulosic content in the biomass to crude oil and ethanol, respectively. We define the components and operations necessary for functioning of such a supply chain. The Biomass Logistics Problem that we address is a strategic cost analysis for setup and operation of such a biomass supply chain network. We focus our attention to a region in South Central Virginia and use the detailed geographic map data to obtain land use pattern in the region. We conduct survey of existing literature to obtain various transportation related cost factors and costs associated with the use of equipment. Our ultimate aim here is to understand the feasibility of running a biomass supply chain in the region of interest from an economic standpoint. As such, we represent the Biomass Logistics Problem with a cost-based optimization model and solve it in a series of smaller problems. A Hybrid Flow Shop (HFS) is a configuration of machines that is often encountered in the flexible manufacturing systems, wherein a particular station of machines can execute processing of jobs/tasks simultaneously. In our work, we approach a specific type of HFS, with a single machine at the first stage and multiple identical machines at the second stage. A batch or lot of jobs/items is considered for scheduling over such an HFS. Depending upon the area of application, such a batch is either allowed to be split into continuous sections or restricted to be split in discrete sizes only. The objective is to minimize the completion time of the last job on its assigned machine at the second stage. We call this problem, Hybrid Flow Shop Scheduling Problem, which is known to be a hard problem in literature. We aim to derive the results which will reduce the complexity of this problem, and develop both exact as well as heuristic methods in order to obtain near-optimal solution to this problem. An Assembly Job Shop is a variant of the classical Job Shop which considers scheduling a set of assembly operations over a set of assembly machines. Each operation can only be started once all the other operations in its precedence relationship are completed. Assembly Job Shop are at the core of some of the highly competitive manufacturing facilities that are principled on the philosophy of Mass Customization. Assuming an inherent nature of demand uncertainty, this philosophy aims to achieve ‘economy of scale’ together with flexibility to produce a variety of products for the customers while minimizing the delivery lead times simultaneously. We incorporate some of these challenges in a concise framework of production scheduling and call this problem as Stochastic Demand Assembly Job Scheduling Problem. We design a novel methodology that is geared towards achieving the set objectives and propose an effective algorithm for efficient computation.

[pt] No Brasil, as três principais fontes renováveis de energia elétrica são eólica, pequenas centrais hidrelétricas (PCHs) e biomassa. A comercialização da energia proveniente dessas fontes ocorre majoritariamente no ambiente de contratação regulada (ACR), através de leilões, em detrimento do ambiente de contratação livre (ACL). Isso devido ao fato de seus recursos naturais serem sazonais, estabelecendo o risco de preço-quantidade no ACL, em que o excesso ou déficit de energia gerada em relação à quantidade contratada é liquidado ao preço de liquidação de diferenças (PLD), uma variável sistêmica e altamente volátil. Contudo, a complementaridade dessas fontes permite reduzir esses riscos quando a energia é comercializada de forma conjunta, através de um fundo de energia que gera aumento do valor do portfólio com relação à comercialização individual. Esta dissertação utiliza a teoria de jogos cooperativos para analisar formas de repartir o benefício gerado, através da alocação de quotas financeiras. O conjunto de soluções onde o resultado individual das fontes no fundo é maior do que o resultado individual em qualquer subcoalisão define o núcleo do jogo. Assim, a complexidade de encontrar uma solução dentro do núcleo depende do número de subcoalizões, que cresce exponencialmente com o número de jogadores. Nesse contexto, este trabalho se propôs a apresentar: (i) um modelo de portfólio que incentiva a participação de fontes renováveis no ACL; (ii) um modelo de programação linear que busca o núcleo do jogo; (iii) uma metodologia eficiente baseada em decomposição de Benders, capaz de suprimir a questão da explosão combinatória do problema. / [en] In Brazil, the three main sources of renewable energy are wind, small run-of-river hidros (SH) and biomass. The energy sale of such sources occurs mainly in the Regulated Trading Environment (RTE), through auctions, with shy occurrences in the Free Trading Environment (FTE). This is due to the fact that their natural resources are seasonal, establishing the so-called price-quantity risk in the FTE, as the surplus or deficit of energy generated relative to the contracted amount is settled at the market’s spot price, a systemic and highly volatile variable. However, the complementary nature of these sources allows risk reduction if their energy are trade jointly, through an energy hedge pool that increases the value of the portfolio in comparison to individual strategies. This work makes use of cooperative games theory to analyze ways of sharing the generated benefit, through financial quotas allocation. The set of solutions where the individual sources results in the pool are greater than its results at any possible subcoalition defines the core of the game. Thus, the challenge of finding a solution inside the core depends on the number of subcoalitions, which grows exponentially with the number of players. In this context, this work proposes to present: (i) a model of portfolio that encourages the penetration of renewable sources in the FTE; (ii) a linear programming model that pursuits the game’s core; (iii) an efficient methodology based on Benders decomposition that is capable of suppress the problem of combinatorial explosion, typical of cooperative games with many players.

This thesis study focuses on transmission expansion planning (TEP) problem for restructured power systems and addresses challenges specifically in countries where electricity market is in developing phase after liberalization of power industry for establishing a competitive market, like Turkey. A novel multi-year TEP approach is developed which considers generation investment cost and transmission congestion level in the planning horizon. The model assesses the impact of generation investments on TEP problem. Benders decomposition methodology is utilized successfully to decompose the complex mixed-integer programming TEP problem into a master problem and two subproblems. Security subproblem assesses single-contingency criteria. Transmission congestion cost is considered within operational subproblem given that congestion level is a proper criterion for measuring competitiveness level of an electricity market. The proposed approach is applied to the Turkish power system. The proposed approach could be utilized to provide indicative plans, which might be quite necessary particularly during development of a competitive market. However, there is no guarantee that independent power producers (IPPs) will follow those plans which concern the maximization of social-welfare. Given the necessity of coordinating monopoly transmission and decentralized generator investment decisions, the proposed approach is improved further to include promoting decentralized generator investments through incentive payments. Such incentives might be necessary to trigger IPPs earlier than their projections, as illustrated by numerical examples including IEEE 30-bus system.