This thesis focuses on task sequencing and manpower scheduling to develop robust schedules for an aircraft manufacturer. The production of an aircraft goes through a series of multiple workstations, each consisting of a large number of interactive tasks and a limited number of working zones. The duration of each task varies from operator to operator, because most operations are performed manually. These factors limit the ability of managers to balance, optimize, and change the statement of work in each workstation. In addition, engineers spend considerable amount of time to manually develop schedules that may be incompatible with the changes in the production rate. To address the above problems, the current state of work centers are first analyzed. Then, several deterministic mathematical programming models are developed to minimize the total production labour cost for a target cycle time. The mathematical models seek to find optimal schedules by eliminating and/or considering the effect of overtime on the production cost. The resulting schedules decrease the required number of operators by 16% and reduce production cycle time of work centers by 53% to 67%. Using these models, the time needed to develop a schedule is reduced from 36 days to less than a day. To handle the stochasticity of the task durations, a two-stage stochastic programming model is developed to minimize the total production labour cost and to find the number of operators that are able to work under every scenario. The solution of the two-stage stochastic programming model finds the same number of operators as that of the deterministic models, but reduces the time to adjust production schedules by 88%.

This thesis focuses on task sequencing and manpower scheduling to develop robust schedules for an aircraft manufacturer. The production of an aircraft goes through a series of multiple workstations, each consisting of a large number of interactive tasks and a limited number of working zones. The duration of each task varies from operator to operator, because most operations are performed manually. These factors limit the ability of managers to balance, optimize, and change the statement of work in each workstation. In addition, engineers spend considerable amount of time to manually develop schedules that may be incompatible with the changes in the production rate. To address the above problems, the current state of work centers are first analyzed. Then, several deterministic mathematical programming models are developed to minimize the total production labour cost for a target cycle time. The mathematical models seek to find optimal schedules by eliminating and/or considering the effect of overtime on the production cost. The resulting schedules decrease the required number of operators by 16% and reduce production cycle time of work centers by 53% to 67%. Using these models, the time needed to develop a schedule is reduced from 36 days to less than a day. To handle the stochasticity of the task durations, a two-stage stochastic programming model is developed to minimize the total production labour cost and to find the number of operators that are able to work under every scenario. The solution of the two-stage stochastic programming model finds the same number of operators as that of the deterministic models, but reduces the time to adjust production schedules by 88%.

Diplomová práce se zabývá stochastickým programováním a jeho aplikací na problém mísení kameniva z oblasti stavebního inženýrství. Teoretická část práce je věnována odvození základních přístupů stochastického programování, tj. optimalizace se zohledněním náhodných vlivů v modelech. V aplikované části je prezentována tvorba vhodných optimalizačních modelů pro mísení kameniva, jejich implementace a výsledky. Práce zahrnuje původní aplikační výsledky docílené při řešení projektu GA ČR reg. čís. 103/08/1658 Pokročilá optimalizace návrhu složených betonových konstrukcí a teoretické výsledky projektu MŠMT České republiky čís. 1M06047 Centrum pro jakost a spolehlivost výroby.

yes / This paper used different risk management indicators applied to the investment optimization performed by consumers in Distributed Generation (DG). The objective function is the total cost incurred by the consumer including the energy and capacity payments, the savings, and the revenues from the installation of DG, alongside the operation and maintenance (O&M) and investment costs. Probability density function (PDF) was used to model the price volatility in the long-term. The mathematical model uses a two-stage stochastic approach: investment and operational stages. The investment decisions are included in the first stage and which do not change with the scenarios of the uncertainty. The operation variables are in the second stage and, therefore, take different values with every realization. Three risk indicators were used to assess the uncertainty risk: Value-at-Risk (VaR), Conditional Value-at-Risk (CVaR), and Expected Value (EV). The results showed the importance of migration from deterministic models to stochastic ones and, most importantly, the understanding of the ramifications of every risk indicator.

In view of the current situation of fluctuating high crude oil prices, it is now more important than ever for petroleum refineries to operate at an optimal level in the present dynamic global economy. Acknowledging the shortcomings of deterministic models, this work proposes a hybrid of stochastic programming formulations for an optimal midterm refinery planning that addresses three factors of uncertainties, namely price of crude oil and saleable products, product demand, and production yields. An explicit stochastic programming technique is utilized by employing compensating slack variables to account for violations of constraints in order to increase model tractability. Four approaches are considered to ensure both solution and model robustness: (1) the Markowitz???s mean???variance (MV) model to handle randomness in the objective coefficients of prices by minimizing variance of the expected value of the random coefficients; (2) the two-stage stochastic programming with fixed recourse approach via scenario analysis to model randomness in the right-hand side and left-hand side coefficients by minimizing the expected recourse penalty costs due to constraints??? violations; (3) incorporation of the MV model within the framework developed in Approach 2 to minimize both the expectation and variance of the recourse costs; and (4) reformulation of the model in Approach 3 by adopting mean-absolute deviation (MAD) as the risk metric imposed by the recourse costs for a novel application to the petroleum refining industry. A representative numerical example is illustrated with the resulting outcome of higher net profits and increased robustness in solutions proposed by the stochastic models.

The thesis deals with the algorithms for two-stage stochastic programs. The first chapter considers the basic properties and theory. Specifically, we introduce the properites of the feasibility region and the objective function. Further, optimality conditions are discussed. In the second chapter we present algoritms which can be used to solve two-stage linear programs with fixed recourse. In the first section the basic L-shaped method is described in detail. The second section provides an explanation of the Stochastic Decomposition algorithm with the inclusion of a regularization term. The last chapter presents computational results. Three practical examples are provided both with a brief description of the problem and solutions by the studied algorithms.

In view of the current situation of fluctuating high crude oil prices, it is now more important than ever for petroleum refineries to operate at an optimal level in the present dynamic global economy. Acknowledging the shortcomings of deterministic models, this work proposes a hybrid of stochastic programming formulations for an optimal midterm refinery planning that addresses three factors of uncertainties, namely price of crude oil and saleable products, product demand, and production yields. An explicit stochastic programming technique is utilized by employing compensating slack variables to account for violations of constraints in order to increase model tractability. Four approaches are considered to ensure both solution and model robustness: (1) the Markowitz’s mean–variance (MV) model to handle randomness in the objective coefficients of prices by minimizing variance of the expected value of the random coefficients; (2) the two-stage stochastic programming with fixed recourse approach via scenario analysis to model randomness in the right-hand side and left-hand side coefficients by minimizing the expected recourse penalty costs due to constraints’ violations; (3) incorporation of the MV model within the framework developed in Approach 2 to minimize both the expectation and variance of the recourse costs; and (4) reformulation of the model in Approach 3 by adopting mean-absolute deviation (MAD) as the risk metric imposed by the recourse costs for a novel application to the petroleum refining industry. A representative numerical example is illustrated with the resulting outcome of higher net profits and increased robustness in solutions proposed by the stochastic models.

Při práci s úlohami stochastického programování se často setkáváme s optimalizačními problémy, které jsou příliš rozsáhlé na to, aby byly zpracovány pomocí rutinních metod matematického programování. Nicméně, v některých případech mají tyto problémy vhodnou strukturu, umožňující použití specializovaných dekompozičních metod, které lze použít při řešení rozsáhlých optimalizačních problémů. Tato práce se zabývá dvěma třídami úloh stochastického programování, které mají speciální strukturu, a to dvoustupňovými stochastickými úlohami a úlohami s pravděpodobnostním omezením, a pokročilými dekompozičními metodami, které lze použít k řešení problému v těchto dvou třídách. V práci popisujeme novou metodu pro tvorbu “warm-start” řezů pro metodu zvanou “Generalized Benders Decomposition”, která se používá při řešení dvoustupňových stochastických problémů. Pro třídu úloh s pravděpodobnostním omezením zde uvádíme originální dekompoziční metodu, kterou jsme nazvali “Pool & Discard algoritmus”. Užitečnost popsaných dekompozičních metod je ukázána na několika příkladech a inženýrských aplikacích.

Two-stage stochastic programming problem with PDE constraint, specially elliptic equation is formulated. The computational scheme is proposed, whereas the emphasis is put on approximation techniques. We introduce method of approximation of random variables of stochastic problem and utilize suitable numerical methods, finite difference method first, then finite element method. There is also formulated a mathematical programming problem describing a membrane deflection with random load. It is followed by determination of the acceptableness of using stochastic optimization rather than deterministic problem and assess the quality of approximations based on Monte Carlo simulation method and the theory of interval estimates. The resulting mathematical models are implemented and solved in the general algebraic modeling system GAMS. Graphical and numerical results are presented.

Cotutelle avec l'Université de Toulouse 3 - Paul Sabatier, France. Laboratoire d'accueil: Laboratoire de recherche de l'École Nationale de l'Aviation Civile (ENAC), équipe OPTIM, Toulouse, France. / Dans le contexte d'une augmentation soutenue du trafic aérien et d'une faible marge d'expansion des capacités aéroportuaires, la pression s'accroît sur les aéroports les plus fréquentés pour une utilisation optimale de leur infrastructure, telle que les pistes, reconnues comme le goulot d'étranglement des opérations aériennes. De ce besoin opérationnel est né le problème d'ordonnancement des atterrissages d'avions, consistant à trouver pour les avions se présentant à un aéroport la séquence et les heures d'atterrissage optimales par rapport à certains critères (utilisation des pistes, coût total des retards, etc) tout en respectant des contraintes opérationnelles et de sécurité. En réponse à ce besoin également, depuis les années 1990 aux États-Unis et en Europe, des outils d'aide à la décision ont été mis à la disposition des contrôleurs aériens, afin de les assister dans leur tâche d'assurer la sécurité et surtout la performance des flux d'arrivée. Un certain nombre de travaux de recherche se sont focalisés sur le cas déterministe et statique du problème d'atterrissage d'avions. Cependant, le problème plus réaliste, de nature stochastique et dynamique, a reçu une attention moindre dans la littérature. De plus, dans le cadre du projet européen de modernisation des systèmes de gestion de trafic aérien, il a été proposé d’étendre l’horizon opérationnel des outils d’aide à la décision de manière à prendre en compte les avions plus loin de l'aéroport de destination. Cette extension de l'horizon opérationnel promet une meilleure gestion des flux d'arrivées via un ordonnancement précoce plus efficient. Néanmoins, elle est inévitablement accompagnée d'une détérioration de la qualité des données d'entrée, rendant indispensable la prise en compte de leur stochasticité. L’objectif de cette thèse est l’ordonnancement des arrivées d’avions, dans le cadre d'un horizon opérationnel étendu, où les heures effectives d'arrivée des avions sont incertaines. Plus précisément, nous proposons une approche basée sur la programmation stochastique à deux étapes. En première étape, les avions sont pris en considération à 2-3 heures de leur atterrissage prévu à l'aéroport de destination. Il s'agit de les ordonnancer à un point de l'espace aérien aéroportuaire, appelé IAF (Initial Approach Fix). Les heures effectives de passage à ce point sont supposées suivre des distributions de probabilité connues. En pratique, cette incertitude peut engendrer un risque à la bonne séparation des avions nécessitant l'intervention des contrôleurs. Afin de limiter la charge de contrôle conséquente, nous introduisons des contraintes en probabilité traduisant le niveau de tolérance aux risques de sécurité à l'IAF après révélation de l'incertitude. La deuxième étape correspond au passage effectif des avions considérés à l'IAF. Comme l'incertitude est révélée, une décision de recours est prise afin d'ordonnancer les avions au seuil de piste en minimisant un critère de deuxième étape (charge de travail des contrôleurs, coût du retard, etc). La démonstration de faisabilité et une étude numérique de ce problème d'ordonnancement des arrivées d'avions en présence d'incertitude constituent la première contribution de la thèse. La modélisation de ce problème sous la forme d’un problème de programmation stochastique à deux étapes et sa résolution par décomposition de Benders constituent la deuxième contribution. Finalement, la troisième contribution étend le modèle proposé au cas opérationnel, plus réaliste où nous considérons plusieurs points d’approche initiale. / Airport operations are well known to be a bottleneck in the air traffic system, which puts more and more pressure on the world busiest airports to optimally schedule landings, in particular, and also – but to a smaller extent – departures. The Aircraft Landing Problem (ALP) has arisen from this operational need. ALP consists in finding for aircraft heading to a given airport a landing sequence and landing times so as to optimize some given criteria (optimizing runway utilization, minimizing delays, etc) while satisfying operational constraints (safety constraints mainly). As a reply to this operational need, decision support tools have been designed and put on service for air traffic controllers since the early nineties in the US as well as in Europe. A considerable number of publications dealing with ALP focus on the deterministic and static case. However, the aircraft landing problem arising in practice has a dynamic nature riddled with uncertainties. In addition, operational horizon of current decision support tools are to be extended so that aircraft are captured at larger distances from the airport to hopefully start the scheduling process earlier. Such a horizon extension affects the quality of input data which enlarges the uncertainty effect. In this thesis, we aim at scheduling aircraft arrivals under uncertainty. For that purpose, we propose an approach based on two-stage stochastic programming. In the first stage, aircraft are captured at a large distance from the destination airport. They are to be scheduled on the same initial approach fix (IAF), a reference point in the near-to-airport area where aircraft start their approach phase preparing for landing. Actual IAF arrival times are assumed to be random variables with known probability distributions. In practice, such an uncertainty may cause loss of safety separations between aircraft. In such situations, air traffic controllers are expected to intervene to ensure air traffic safety. In order to alleviate the consequent air traffic control workload, chance constraints are introduced so that the safety risks around the IAF are limited to an acceptable level once the uncertainty is revealed. The second stage corresponds to the situation where aircraft are actually close to the IAF. In this stage, the uncertainty is revealed and a recourse decision is made in order to schedule aircraft on the runway threshold so that a second-stage cost function is minimized (e.g., air traffic control workload, delay cost, etc). Our first contribution is a proof of concept of the extended aircraft arrival management under uncertainty and a computational study on optimization parameters and problem characteristics. Modeling this problem as a two-stage stochastic programming model and solving it by a Benders decomposition is our second contribution. Finally, our third contribution focuses on extending our model to the more realistic case, where aircraft in the first stage are scheduled on several IAFs.