Bicycle sharing systems (BSS) have emerged as a powerful stimulus to non- motorized travel, especially for short-distance trips. However, the imbalances in the distribution of bicycles in BSS are widely observed. It is thus necessary to reposition bicycles to reduce the unmet demand due to such imbalances as much as possible. This paper formulates a new mixed-integer linear programming model considering the dynamic nature of the demand to solve the repositioning problem, which is later validated by an illustrative example. Due to the NP-Hard nature of this problem, we seek for two heuristics (greedy algorithm and rolling horizon approach) and one exact solution method (Benders’ decomposition) to get an acceptable solution for problems with large instances within a reasonable computation time. We create four datasets based on real world data with 12, 24, 36, and 48 stations respectively. Computational results show that our model and solution methods performed well. Finally, this paper gives some suggestions on extensions or modifications that might be added to our work in the future. / text

A growing need for clean and sustainable energy is causing a significant shift in the electricity generation paradigm. In the electricity system of the future, integration of renewable energy sources with smart grid technologies can lead to potentially huge economical and environmental benefits ranging from lesser dependency on fossil fuels and improved efficiency to greater reliability and eventually reduced cost of electricity. In this context, microgrids serve as one of the main components of smart grids with high penetration of renewable resources and modern control strategies. This dissertation is concerned with developing optimal control strategies to manage an energy storage unit in a grid-connected microgrid under uncertainty of electricity demand and prices. Two methods are proposed based on the concept of rolling horizon control, where charge/discharge activities of the storage unit are determined by repeatedly solving an optimization problem over a moving control window. The predicted values of the microgrid net electricity demand and electricity prices over the control horizon are assumed uncertain. The first formulation of the control is based on the scenario-based stochastic conditional value at risk (CVaR) optimization, where the cost function includes electricity usage cost, battery operation costs, and grid signal smoothing objectives. Gaussian uncertainty is assumed in both net demand and electricity prices. The second formulation reduces the computations by taking a worst-case CVaR stochastic optimization approach. In this case, the uncertainty in demand is still stochastic but the problem constraints are made robust with respect to price changes in a given range. The optimization problems are initially formulated as mixed integer linear programs (MILP), which are non-convex. Later, reformulations of the optimization problems into convex linear programs are presented, which are easier and faster to solve. Simulation results under different operation scenarios are presented to demonstrate the effectiveness of the proposed methods. Finally, the energy management problem in network of grid-connected microgrids is investigated and a strategy is devised to allocate the resulting net savings/costs of operation of the microgrids to the individual microgrids. In the proposed approach, the energy management problem is formulated in a deterministic co-operative game theoretic framework for a group of connected microgrids as a single entity and the individual savings are distributed based on the Shapley value theory. Simulation results demonstrate that this co-operation leads to higher economical return for individual microgrids compared to the case where each of them is operating independently. Furthermore, this reduces the dependency of the microgrids on the utility grid by exchanging power locally. / Thesis / Master of Applied Science (MASc)

Energy management strategies for microgrids, containing energy storage, renewable energy sources (RES), and electric vehicles (EVs); which interact with the grid on an individual basis; are presented in Chapter 3. An optimization problem to reduce cost, formulated over a rolling time horizon, using predicted values of load demand, EV connection/disconnection times, and charge levels at time of connection, is described. The solution provides the on-site storage and EV charge/discharge powers. For the first time, both bidirectional and unidirectional charging are considered for EVs and a controller which accommodates uncertainties in EV energy levels and connection/disconnection times is presented. In Chapter 4, a stochastic chance constraints based optimization is described. It affords significant improvement in robustness, over the conventional controller, to uncertainties in system parameters. Simulation results demonstrate that the stochastic controller is at least twice as effective at meeting the desired EV charge level at specific times compared to the non-stochastic version, in the presence of uncertainties. In Chapter 5, a network of microgrids, containing RES and batteries, which trade energy among themselves and with the utility grid is considered. A novel distributed energy management system (EMS), based on a central EMS using a Multi-Objective (MO) Rolling Horizon (RH) scheme, is presented. It uses Alternating Direction Method of Multipliers (ADMM) and Quadratic Programming (QP). It is inherently more data-secure and resilient to communication issues than the central EMS. It is shown that using an EMS in the network provides significant economic benefits over MGs connected directly to the grid. Simulations demonstrate that the distributed scheme produced solutions which are very close to those of the central EMS. Simulation results also reveal that the faster, less memory intensive distributed scheme is scalable to larger networks -- more than 1000 microgrids as opposed to a few hundreds for the central EMS. / Thesis / Doctor of Philosophy (PhD)

Over the last decade, the semiconductor industry has witnessed a steady increase in its complexity based on improvements in manufacturing processes and equipment. Progress in the technology used is no longer the key to success, however. In fact, the semiconductor technology has reached such a high level of complexity that improvements appear at a slow pace. Moreover, the diffusion of technology among competitors shows that traditional approaches based on technological advances and innovations are not sufficient to remain competitive. A recent crisis in the semiconductor field in the summer 2001 made it even clearer that optimizing the operational control of semiconductor wafer fabrication facilities is a vital key to success. Operating research-oriented studies have been carried out to this end for the last 5 years. None of them, however, suggest a comprehensive model and solution to the operational control problem of a semiconductor manufacturing facility. Two main approaches, namely mathematical programming and dispatching rules, have been explored in the literature so far, either partially or entirely dealing with this problem. Adapting the Shifting Bottleneck (SB) procedure is a third approach that has motivated many studies. Most research focuses on optimizing a certain objective function under idealized conditions and thus does not take into consideration system disruptions such as machine breakdown. While many papers address the adaptations of the SB procedure, the problem of re-scheduling jobs dynamically to take disruptions and local disturbances (machines breakdown, maintenance...) into consideration shows interesting perspectives for research. Dealing with local disturbances in a production environment and analyzing their impact on scheduling policies is a complex issue. It becomes even more complex in the semiconductor industry because of the numerous inherent constraints to take into account. The problem that is addressed in this thesis consists of studying dynamic scheduling in a job-shop environment where local disturbances occur. This research focuses on scheduling a large job shop and developing re-scheduling policies when local disturbances occur. The re-scheduling can be applied to the whole production horizon considered in the instance, or applied to a restricted period T that becomes a decision variable of the problem. The length of the restricted horizon T of re-scheduling can influence significantly the overall results. Its impact on the general performance is studied. Future extensions can be made to include constraints that arise in the semiconductors industry, such as the presence of parallel and batching machines, reentrant flows and the lot dedication problem. The theoretical results developed through this research will be applied to data sets to study their efficiency. We hope this methodology will bring useful insights to dealing effectively with local disturbances in production environments. / Master of Science

As air traffic congestion grows, air traffic flow management (ATFM) is becoming a great concern. ATFM deals with air traffic and the efficient utilization of the airport and airspace. Air traffic efficiency is heavily influenced by unanticipated factors, or uncertainties, which can come from several sources such as mechanical breakdown; however, weather is the main unavoidable cause of uncertainty. Because weather is unpredictable, it poses a critical challenge for ATFM in current airport and airspace operations. Convective weather results in congestion at airports as well as in airspace sectors. During times of congestion, the decision as how and when to send aircraft toward an airspace sector in the presence of weather is difficult. To approach this problem, we first propose a two-stage stochastic integer program by emphasizing a given single sector. By considering ground delay, cancellation, and cruise speed for each flight on the ground in the first stage, as well as air holding and diversion recourse actions for each flight in the air in the second stage, our model determines how aircraft are sent toward a sector under the uncertainty of weather. However, due to the large number of weather scenarios, the model is intractable in practice. To overcome the intractability, we suggest a rolling horizon method to solve the problem to near optimal. Lagrangian relaxation and subgradient method are used to justify the rolling horizon method. Since the rolling horizon method can be solved in real time, we can apply it to actual aircraft schedules to reduce the costs incurred on the ground as well as in airspace. We then extend our two-stage model to a multistage stochastic program, which increases the number of possible weather realizations and results a more efficient schedule in terms of costs. The rolling horizon method as well as Lagrangian relaxation and subgradient method are applied to this multistage model. An overall comparison among the previously described methodologies are presented.

This dissertation studies two important problems in the field of biomass supply chain network. In the first part of the dissertation, we study the pre-disaster planning problem that seeks to strengthen the links between the multi-modal facilities of a biomass supply chain network. A mixed-integer nonlinear programming model is developed to determine the optimal locations for multi-modal facilities and bio-refineries, offer suggestions on reliability improvement at vulnerable links, production at bio-refineries, and make transportation decision under both normal and disrupted scenarios. The aim is to assist investors in determining which links’ reliability can be improved under specific budget limitations so that the biouel supply chain network can prevent possible losses when transportation links are disrupted because of natural disasters. We used states Mississippi and Alabama as a testing ground for our model. As part of numerical experimentation, some realistic hurricane scenarios are presented to determine the potential impact that pre-investing may have on improving the bio-mass supply chain network’s reliability on vulnerable transportation links considering limited budget availability. In the second part of the dissertation, we study the impact of feedstock supply uncertainty on the design and management of an inbound biomass coiring supply chain network. A two-stage stochastic mixed integer linear programming model is developed to determine the optimal use of multi-modal facilities, biomass storage and processing plants, and shipment routes for delivering biomass to coal plants under feedstock supply uncertainty while considering congestion into account. To represent a more realistic case, we generated a scenario tree based on the prediction errors obtained from historical and forecasted feedstock supply availability. We linearized the nonlinear problem and solved with high quality and in a time efficient manner by using a hybrid decomposition algorithm that connects a Constraint generation algorithm with Sample average approximation algorithm and enhanced Progressive hedging algorithm. We used states Mississippi and Alabama as a testing ground for our study and conducted thorough computational experiments to test our model and to draw managerial insights.

The scheduling of the converter aisle of a nickel smelting plant is a non-trivial task with significant consequences to plant profitability and production. An optimization-based scheduling formulation is developed using a continuous-time paradigm to accurately represent event timings. The formulation accounts for environmental restrictions on sulfur dioxide emissions using event timing constraints. The formulation includes novel semi-continuous modeling to represent flash furnaces which operate with a continuous inlet flow and intermittent discrete material removal, as well as, a novel sequencing and symmetry-breaking scheme to account for identical units operating in parallel. A rolling horizon feature is included in the formulation to accommodate multi-period optimization. Tightening constraints are developed and used to improve the computational performance of the optimization and demonstrate the capacity of the proposed methodology to function as a real-time decision-support tool. A solution procedure is presented where an aggregate model is used to bound the objective function of the master problem in a two layer optimization scheme. Finally, a novel multi-tiered procedure is presented to enhance the optimization solution by re-optimizing for objectives of decreasing priority in order to minimize task start times and penalize deviations in the furnace flow rate. To address the closed-loop properties of scheduling, a reactive scheduling mechanism is included to allow for rescheduling to account the impact of process disturbances on the operating schedule. A methodology for reducing radical scheduling changes due to the optimization during reactive scheduling is presented. The reactive scheduling algorithm utilizes a tiered optimization approach that progressively increases the degrees of freedom available, as required, in order to achieve a feasible production schedule. The use of the reactive scheduling algorithm demonstrates the ability to reject disturbances and transition plant operation in an agile manner. / Thesis / Master of Applied Science (MASc)

Tabletop games have within recent years evolvedto become more and more complex, such as through the useof dynamic rules, permanently changing how the game worksafter a playthrough, and players playing different roles in thegame. This leads to unique challenges for Artificial Intelligence.A Tabletop Games Framework (TAG) is a framework intended topromote research within general AI for modern tabletop games.Rolling Horizon Evolutionary Algorithms (RHEA) are a typeof algorithms that have been applied to games with successin the past. By implementing a RHEA agent we can studyhow it compares to other types of agents such as Monte CarloTree Search and Random Mutation Hill Climbing agents. Ofparticular interest is the game Pandemic (2008), as the existingagents are unable to win at it.

[ES] Con la globalización de los mercados y el aumento de la competitividad, la coordinación se ha convertido en un punto estratégico en la gestión de la cadena de suministro. De hecho, cada actor de la cadena de suministro ya no debe tomar decisiones sin considerar todos los eslabones, sean proveedores, proveedores de proveedores o clientes y estos internos o externos a la organización. Las cadenas de suministro son cada vez más complejas y distribuidas, compuestas por múltiples organizaciones con diferentes objetivos y políticas. La coordinación se puede lograr utilizando uno de estos dos enfoques para la toma de decisiones coordinadas: centralizada o descentralizada con un mecanismo de coordinación. Pero, las empresas son reacias a compartir información, ya sea por la confidencialidad de los datos o porque los modelos centralizados resultantes son de gran complejidad que dificultan su manejo y actualización. Además, aquellas empresas que buscan tomar decisiones en tiempo real requieren de modelos ligeros y ágiles, que, con toda la información local y coordinada con el resto, permitan tomar decisiones rápidas. Las empresas interesadas en la coordinación descentralizada con un mecanismo de coordinación esperan obtener mejores resultados con respecto a la no coordinación, aunque deberían asumir tener peores resultados que con la coordinación centralizada. Para ello en esta tesis, se han estudiado los distintos mecanismos de coordinación para la toma de decisiones descentralizada, dentro de un entorno del procedimiento de horizontes rodantes y con herramienta de planificación y programación de las operaciones basada en el concepto de stroke, que extiende el concepto de lista de materiales más allá de las estructuras tradicionales. Estos permiten desarrollar la formulación de la programación matemática y los mecanismos de coordinación necesarios para resolver los problemas de planificación de operaciones. Esta tesis se presenta como una secuencia de capítulos, con el objeto de analizar y presentar la propuesta de mecanismo de coordinación distribuido con unos recursos compartidos. Los distintos capítulos han servido de base para la preparación de artículos científicos. Estos artículos han sido presentados en congresos de la materia y remitidos a revistas científicas. / [CA] Amb la globalització dels mercats i l'augment de la competitivitat, la coordinació s'ha convertit en un punt estratègic en la gestió de la cadena de subministrament. De fet, cada actor de la cadena de subministrament ja no ha de prendre decisions sense considerar totes les baules, siguen proveïdors, sub-proveïdors o clients i aquests interns o externs a l'organització. Les cadenes de subministrament són cada vegada més complexes i distribuïdes, compostes per múltiples organitzacions amb diferents objectius i polítiques. La coordinació es pot aconseguir utilitzant un d'aquests dos enfocaments per a la presa de decisions coordinades: centralitzat o descentralitzat amb un mecanisme de coordinació. Però, les empreses són poc inclinades a compartir informació, ja siga per la confidencialitat de les dades o perquè els models centralitzats resultants són de gran complexitat que dificulten el seu maneig i actualització. A més, aquelles empresa que busquen prendre decisions en temps real requereixen de models lleugers i àgils, que, amb tota la informació local i coordinada amb la resta, permeten prendre decisions ràpides. Les empreses interessades en la coordinació descentralitzada amb un mecanisme de coordinació esperen obtindre millors resultats respecte de la no coordinació encara que haurien d'assumir tindre pitjors resultats que amb la coordinació centralitzada. Per a això en aquesta tesi, s'han estudiat els diferents mecanismes de coordinació per a la presa de decisions descentralitzada, dins d'un entorn d'horitzons rodant i amb eines de planificació i programació de les operacions basada en el concepte de stroke, que estén el concepte de llista de materials més enllà de les estructures tradicionals. Aquests permeten desenvolupar la formulació de la programació matemàtica i els mecanismes de coordinació necessaris per a resoldre els problemes de planificació d'operacions. Aquesta tesi es presenta com una seqüència de capítols, a fi d'analitzar i presentar la proposta de mecanisme de coordinació distribuït amb uns recursos compartits. Els diferents capítols han servit de base per a la preparació d'articles científics. Aquests articles han sigut presentats en congressos de la matèria i remesos a revistes científiques. / [EN] With the globalization of markets and the increase of competitiveness, coordination has become a strategic point in the management of the supply chain. In fact, each actor in the supply chain must no longer make decisions without considering all the links, whether suppliers, sub-suppliers or customers and those internal or external to the organization. Supply chains are increasingly complex and distributed, composed of multiple organizations with different objectives and policies. Coordination can be achieved using one of these two approaches to coordinate decision making: centralized or decentralized with a coordination mechanism. However, companies are reluctant to share information, either because of the confidentiality of the data or because the resulting centralized models are of great complexity that make their management and update them. In addition, those companies that seek to make decisions in real time require lightweight and agile models, which, with all the local information and coordinated with the rest, allow quick decisions. Companies interested in decentralized coordination with a coordination mechanism expect to obtain better results regarding non-coordination although they should assume to have worse results than with centralized coordination. To this end, in this thesis, the different coordination mechanisms for decentralized decision making have been studied, within an environment of rolling horizons and with tools for planning and scheduling operations based on the concept of stroke, which extends the concept of list of materials beyond traditional structures. These allow to develop the formulation of the mathematical programming and the coordination mechanisms necessary to solve the operations planning problems. This thesis is presented as a sequence of chapters, in order to analyse and present the proposal of distributed coordination mechanism with shared resources. The different chapters have served as the basis for the preparation of scientific articles. These articles have been presented at congresses of the subject and submitted to scientific journals. / Rius Sorolla, GV. (2019). Modelos y Algoritmos de Coordinación para la Planificación de Operaciones basadas en el concepto Stroke en Redes de Suministro distribuidas y con alternativas [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/134017

Neste trabalho, estudamos o problema de corte bidimensional multiperíodo com sobras aproveitáveis, que consiste em cortar objetos grandes visando a produção de um conjunto de itens menores. Supomos um horizonte de planejamento finito com uma quantidade finita de períodos entre os tempos inicial e final. Primeiramente consideramos uma versão determinística em que conhecemos, à priori, os itens solicitados em uma ordem de trabalho e o custo dos objetos a cada período. Algumas das sobras geradas durante o processo de corte dos itens solicitados em um período podem ser utilizadas como objetos no futuro. As sobras que podem ser usadas no futuro são denominadas sobras aproveitáveis. De forma geral, uma sobra é considerada aproveitável se possui dimensões iguais ou superiores as de algum item de uma lista pré-definida para o período. O objetivo é minimizar o custo total dos objetos utilizados para satisfazer a ordem de trabalho dos itens solicitados de todo o horizonte considerado. Havendo soluções com o mesmo custo, desejamos encontrar aquela que, no fim do horizonte de tempo considerado, maximize o valor das sobras aproveitáveis remanescentes. Apresentamos uma modelagem matemática do problema usando uma formulação em dois níveis, que é transformada em um modelo de programação linear inteira mista, devido às características do problema. Considerando a dificuldade em resolver o modelo desenvolvido, apresentamos uma proposta de uma abordagem heurística baseada em Programação Dinâmica Aproximada (PDA) para lidar com o problema proposto. Outras opções baseadas em estratégias do tipo horizonte rolante e relax-and-fix também são consideradas. Consideramos também o cenário onde não conhecemos de antemão os itens da ordem de trabalho e o custo dos objetos, mas temos informações das distribuições de probabilidade de ambos. Nesse caso, apresentamos uma abordagem baseada em programação dinâmica aproximada para estimar a melhor estratégia a ser seguida em cada período. Comparamos os resultados obtidos pela PDA com os resultados encontrados por um método guloso. Em cenários adequados, os resultados mostram que a PDA consegue soluções superiores ao método guloso. / In this research, we study the multi-period two-dimensional cutting problem with usable leftover, which consists of cutting objects to produce a set of items. We assume a finite planning horizon with a finite amount of periods between the initial and final times. First we consider a deterministic version in which we know, a priori, the set of ordered items and the cost of the objects at each period. Some of the leftovers generated during the cutting process of the ordered items in a period may be used as objects in the future. The leftovers that can be used in the future are called usable leftovers. In general, a leftover is considered usable if it has dimensions equal to or greater than that of some item from a predefined list for the period. The goal is to minimize the total cost of the objects used to cut the set of ordered items of the entire considered horizon. If there are solutions with the same cost, we wish to find one that, at the end of the considered time horizon, maximizes the value of the remaining usable leftovers. We present a mathematical model of the problem using a bilevel formulation, which is transformed into a mixed integer linear programming model, due to the characteristics of the problem. Considering the difficulty in solving the developed model, we propose a heuristic approach based on approximate dynamic programming (ADP) to deal with the proposed problem. Other options based on the rolling horizon and relax-and-fix strategies are also considered. We also consider the scenario where we do not know in advance the set of ordered items and the cost of the objects, but we have information about the probability distributions of both. In this case, we present an approach based on approximate dynamic programming to estimate the best strategy to be followed at each period. We compared the results obtained by the ADP with the results found by a greedy method. In suitable scenarios, the results show that the ADP achieves superior solutions to the greedy method.