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.

Cette thèse étudie le problème du routage des locomotives qui se pose à la Compagnie des chemins de fer nationaux du Canada (CN) - le plus grand chemin de fer au Canada en termes de revenus et de taille physique de son réseau ferroviaire. Le problème vise à déterminer la séquence des activités de chaque locomotive sur un horizon de planification donné. Dans ce contexte, il faut prendre des décisions liées à l'affectation de locomotives aux trains planifiés en tenant compte des besoins d'entretien des locomotives. D’autres décisions traitant l'envoi de locomotives aux gares par mouvements à vide, les déplacements légers (sans tirer des wagons) et la location de locomotives tierces doivent également être prises en compte. Sur la base d'une formulation de programmation en nombres entiers et d'un réseau espace-temps présentés dans la littérature, nous introduisons une approche par horizon roulant pour trouver des solutions sous-optimales de ce problème dans un temps de calcul acceptable. Une formulation mathématique et un réseau espace-temps issus de la littérature sont adaptés à notre problème. Nous introduisons un nouveau type d'arcs pour le réseau et de nouvelles contraintes pour le modèle pour faire face aux problèmes qui se posent lors de la division de l'horizon de planification en plus petits morceaux. Les expériences numériques sur des instances réelles montrent les avantages et les inconvénients de notre algorithme par rapport à une approche exacte. / This thesis addresses the locomotive routing problem arising at the Canadian National Railway Company (CN) - the largest railway in Canada in terms of both revenue and the physical size of its rail network. The problem aims to determine the sequence of activities for each locomotive over the planning horizon. Besides assigning locomotives to scheduled trains and considering scheduled locomotive maintenance requirements, the problem also includes other decisions, such as sending locomotives to stations by deadheading, light traveling, and leasing of third-party locomotives. Based on an Integer Programming formulation and a Time-Expanded Network presented in the literature, we introduce a Rolling Horizon Approach (RHA) as a method to find near-optimal solutions of this problem in acceptable computing time. We adapt a mathematical formulation and a space-time network from the literature. We introduce a new type of arcs for the network and new constraints for the model to cope with issues arising when dividing the planning horizon into smaller ones. Computational experiments on real-life instances show the pros and cons of our algorithm when compared to an exact solution approach.

This dissertation studies a framework in support electric vehicle (EV) charging station expansion and management decisions. In the first part of the dissertation, we present mathematical model for designing and managing electric vehicle charging stations, considering both long-term planning decisions and short-term hourly operational decisions (e.g., number of batteries charged, discharged through Battery-to-Grid (B2G), stored, Vehicle-to-Grid (V2G), renewable, grid power usage) over a pre-specified planning horizon and under stochastic power demand. The model captures the non-linear load congestion effect that increases exponentially as the electricity consumed by plugged-in EVs approaches the capacity of the charging station and linearizes it. The study proposes a hybrid decomposition algorithm that utilizes a Sample Average Approximation and an enhanced Progressive Hedging algorithm (PHA) inside a Constraint Generation algorithmic framework to efficiently solve the proposed optimization model. A case study based on a road network of Washington, D.C. is presented to visualize and validate the modeling results. Computational experiments demonstrate the effectiveness of the proposed algorithm in solving the problem in a practical amount of time. Finding of the study include that incorporating the load congestion factor encourages the opening of large-sized charging stations, increases the number of stored batteries, and that higher congestion costs call for a decrease in the opening of new charging stations. The second part of the dissertation is dedicated to investigate the performance of a collaborative decision model to optimize electricity flow among commercial buildings, electric vehicle charging stations, and power grid under power demand uncertainty. A two-stage stochastic programming model is proposed to incorporate energy sharing and collaborative decisions among network entities with the aim of overall energy network cost minimization. We use San Francisco, California as a testing ground to visualize and validate the modeling results. Computational experiments draw managerial insights into how different key input parameters (e.g., grid power unavailability, power collaboration restriction) affect the overall energy network design and cost. Finally, a novel disruption prevention model is proposed for designing and managing EV charging stations with respect to both long-term planning and short-term operational decisions, over a pre-determined planning horizon and under a stochastic power demand. Long-term planning decisions determine the type, location, and time of established charging stations, while short-term operational decisions manage power resource utilization. A non-linear term is introduced into the model to prevent the evolution of excessive temperature on a power line under stochastic exogenous factors such as outside temperature and air velocity. Since the re- search problem is NP-hard, a Sample Average Approximation method enhanced with a Scenario Decomposition algorithm on the basis of Lagrangian Decomposition scheme is proposed to obtain a good-quality solution within a reasonable computational time. As a testing ground, the road network of Washington, D.C. is considered to visualize and validate the modeling results. The results of the analysis provide a number of managerial insights to help decision makers achieving a more reliable and cost-effective electricity supply network.

<p>Forest management involves numerous stochastic elements. To sustainably manage forest resources, it is crucial to acknowledge these sources as uncertainty or risk, and incorporate them in adaptive decision-making. Here, I developed several stochastic programming models in the form of passive or active adaptive management for natural mixed-species hardwood forests in Indiana. I demonstrated how to use these tools to deal with time-invariant and time-variant natural disturbances in optimal planning of harvests.</p> <p> Markov decision process (MDP) models were first constructed based upon stochastic simulations of an empirical forest growth model for the forest type of interest. Then, they were optimized to seek the optimal or near-optimal harvesting decisions while considering risk and uncertainty in natural disturbances. In particular, a classic expected-criterion infinite-horizon MDP model was first used as a passive adaptive management tool to determine the optimal action for a specific forest state when the probabilities of forest transition remained constant over time. Next, a two-stage non-stationary MDP model combined with a rolling-horizon heuristic was developed, which allowed information update and then adjustments of decisions accordingly. It was used to determine active adaptive harvesting decisions for a three-decade planning horizon during which natural disturbance probabilities may be altered by climate change.</p> <p> The empirical results can be used to make some useful quantitative management recommendations, and shed light on the impacts of decision-making on the forests and timber yield when some stochastic elements in forest management changed. In general, the increase in the likelihood of damages by natural disturbance to forests would cause more aggressive decisions if timber production was the management objective. When windthrow did not pose a threat to mixed hardwood forests, the average optimal yield of sawtimber was estimated to be 1,376 ft³/ac/acre, while the residual basal area was 88 ft²/ac. Assuming a 10 percent per decade probability of windthrow that would reduce the stand basal area considerably, the optimal sawtimber yield per decade would decline by 17%, but the residual basal area would be lowered only by 5%. Assuming that the frequency of windthrow increased in the magnitude of 5% every decade under climate change, the average sawtimber yield would be reduced by 31%, with an average residual basal area slightly around 76 ft²/ac. For validation purpose, I compared the total sawtimber yield in three decades obtained from the heuristic approach to that of a three-decade MDP model making <i>ex post</i> decisions. The heuristic approach was proved to provide a satisfactory result which was only about 18% lower than the actual optimum.</p> These findings highlight the need for landowners, both private and public, to monitor forests frequently and use flexible planning approaches in order to anticipate for climate change impacts. They also suggest that climate change may considerably lower sawtimber yield, causing a concerning decline in the timber supply in Indiana. Future improvements of the approaches used here are recommended, including addressing the changing stumpage market condition and developing a more flexible rolling-horizon heuristic approach.

Le service des urgences est un important service de soins qui représente le goulot d'étranglement de l'hôpital. Les urgences sont souvent confrontées à des problèmes de tension dans de nombreux pays à travers le monde. L'une des causes de la tension dans les urgences est l'interférence permanente entre trois types de patients : les patients déjà programmés, les patients non programmés et les patients non programmés urgents. Le but de cette thèse est de contribuer à l'étude et au développement d'un système d’aide à la décision pour améliorer la prise en charge des patients aussi bien en mode de fonctionnement normal qu’en mode tension. Deux principaux processus ont été développé. Un processus d’ordonnancement à horizon glissant en utilisant un algorithme mimétique avec l’intégration des opérateurs génétiques contrôlés pour déterminer un calendrier optimal de passage des patients. Le deuxième processus d’orchestration dynamique, à base d’agents communicants, tient compte de la nature dynamique et incertaine de l'environnement des urgences en actualisant continuellement ce calendrier. Cette orchestration pilote en temps réel le workflow du parcours patient, améliore pas à pas les indicateurs de performance durant l'exécution. Grâce aux comportements des agents et aux protocoles de communication, le système proposé a établi un lien direct en temps réel entre les performances requises sur le terrain et les actions afin de diminuer l'impact de la tension. Les résultats expérimentaux, mis en œuvre au CHRU de Lille, indiquent que l’application de nos approches permet d’améliorer les indicateurs de performance grâce aux pilotage par les agents du workflow en cours exécution. / The emergency department is an important care service that represents the hospital's bottleneck. Emergencies often face overcrowding problems in many countries worldwide. One of the causes of the emergency department overcrowding is the permanent interference between three types of arriving patients: already programmed patients, non-programmed patients and urgent non-programmed patients. The aim of this thesis is to contribute to the study and development a decision support system to improve patient management in both normal and overcrowding situation. Two main processes have been developed. A rolling-horizon scheduling process using a memetic algorithm with the integration of controlled genetic operators to determine an optimal schedule for patient. The second dynamic orchestration process, based on communicating agents, takes into account the dynamic and uncertain nature of the emergency environment by continually updating this schedule for patient. This orchestration monitoring in real time the workflow of the patient pathway improves step by step the performance indicators during the execution. Through agent behaviors and communication protocols, the proposed system has established a direct real-time link between the required performances and the effective actions in order to decrease the overcrowding impact. The experimental results in this thesis, implemented at the Regional University Hospital Center (RUHC) of Lille, justify the interest of the application of our approaches to improve the performance indicators thanks to the agents driven patient pathway workflows during their execution.

This thesis examines the optimal scheduling of a hydroelectric power plant with cascaded reservoirs each with multiple generating units under uncertainty after testing three linearization methods. These linearization methods are Successive Linear Programming, Piecewise Linear Approximations, and a Hybrid of the two together. There are two goals of this work. The first goal of this work aims to replace the nonconvex mixed-integer nonlinear program (MINLP) with a computationally efficient linearized mixed-integer linear program (MILP) that will be capable of finding a high quality solution, preferably the global optimum. The second goal is to implement a stochastic approach on the linearized method in a pseudo-rolling horizon method which keeps the ending time step fixed. Overall, the Hybrid method proved to be a viable replacement and performs well in the pseudo-rolling horizon tests. / Thesis / Master of Applied Science (MASc)