Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2011. / Cataloged from PDF version of thesis. / Includes bibliographical references (p. 185-188). / Maintenance scheduling is an integral part of many complex systems. For instance, without effective maintenance scheduling, the combined effects of preventative and corrective maintenance can have severe impacts on the availability of those systems. Based on current Air Force trends including maintenance manpower, dispersed aircraft basing, and increased complexity, there has been a renewed focus on preventative maintenance. To address these concerns, this thesis develops two models for preventative maintenance scheduling for complex systems, the first of interest in the system concept development and design phase, and the second of interest during operations. Both models are highly complex and intractable to solve in their original forms. For the first model, we develop approximation algorithms that yield high quality and easily implementable solutions. To address the second model, we propose a decomposition strategy that produces submodels that can be solved via existing algorithms or via specialized algorithms we develop. While much of the literature has examined stochastically failing systems, preventative maintenance of usage limited systems has received less attention. Of particular interest is the design of modular systems whose components must be repaired/replaced to prevent a failure. By making cost tradeoffs early in development, program managers, designers, engineers, and test conductors can better balance the up front costs associated with system design and testing with the long term cost of maintenance. To facilitate such a tradeoff, the Modular Maintenance Scheduling Problem provides a framework for design teams to evaluate different design and operations concepts and then evaluate the long term costs. While the general Modular Maintenance Scheduling Problem does not require maintenance schedules with specific structure, operational considerations push us to consider cyclic schedules in which components are maintained at a fixed frequency. In order to efficiently find cyclic schedules, we propose the Cycle Rounding algorithm, which has an approximation guarantee of 2, and a family of Shifted Power-of-Two algorithms, which have an approximation guarantee of 1/ ln(2) ~ 1.4427. Computational results indicate that both algorithms perform much better than their associated performance guarantees providing solutions within 15%-25% of a lower bound. Once a modular system has moved into operations, manpower and transportation scheduling become important considerations when developing maintenance schedules. To address the operations phase, we develop the Modular Maintenance and System Assembly Model to balance the tradeoffs between inventory, maintenance capacity, and transportation resources. This model explicitly captures the risk-pooling effects of a central repair facility while also modeling the interaction between repair actions at such a facility. The full model is intractable for all but the smallest instances. Accordingly, we decompose the problem into two parts, the system assembly portion and module repair portion. Finally, we tie together the Modular Maintenance and System Assembly Model with key concepts from the Modular Maintenance Scheduling Problem to propose an integrated methodology for design and operation. / by Eric Jack Zarybnisky. / Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2003. / Includes bibliographical references (p. 89-90). / The World Health Organization (WHO) is responsible for making annual vaccine strains recommendation to countries around the globe. However, various studies have found that the WHO vaccine selection strategy has not been effective in some years. This motivates the search for a better strategy for choosing vaccine strains. In this work, we use recent results from theoretical immunology to formulate the vaccine selection problem as a discrete-time stochastic dynamic program with a high-dimensional continuous state space. We discuss the techniques that were developed for solving this difficult dynamic program, and present an effective and robust heuristic policy. We compare the performance of the heuristic policy, the follow policy, and the no-vaccine policy and show that the heuristic policy is the best among the three. After taking the cost of implementation into account, however, we conclude that the WHO policy is a cost-effective influenza vaccine strain selection policy. / by Joseph T. Wu. / Ph.D.

Thesis: Ph. D., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2017. / This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. / Cataloged from student-submitted PDF version of thesis. / Includes bibliographical references (pages 159-166). / This thesis is concerned with the design and analysis of new algorithms for sequential optimization problems with limited feedback on the outcomes of alternatives when the environment is not perfectly known in advance and may react to past decisions. Depending on the setting, we take either a worst-case approach, which protects against a fully adversarial environment, or a hindsight approach, which adapts to the level of adversariality by measuring performance in terms of a quantity known as regret. First, we study stochastic shortest path problems with a deadline imposed at the destination when the objective is to minimize a risk function of the lateness. To capture distributional ambiguity, we assume that the arc travel times are only known through confidence intervals on some statistics and we design efficient algorithms minimizing the worst-case risk function. Second, we study the minimax achievable regret in the online convex optimization framework when the loss function is piecewise linear. We show that the curvature of the decision maker's decision set has a major impact on the growth rate of the minimax regret with respect to the time horizon. Specifically, the rate is always square root when the set is a polyhedron while it can be logarithmic when the set is strongly curved. Third, we study the Bandits with Knapsacks framework, a recent extension to the standard Multi-Armed Bandit framework capturing resource consumption. We extend the methodology developed for the original problem and design algorithms with regret bounds that are logarithmic in the initial endowments of resources in several important cases that cover many practical applications such as bid optimization in online advertising auctions. Fourth, we study more specifically the problem of repeated bidding in online advertising auctions when some side information (e.g. browser cookies) is available ahead of submitting a bid. Optimizing the bids is modeled as a contextual Bandits with Knapsacks problem with a continuum of arms. We design efficient algorithms with regret bounds that scale as square root of the initial budget. / by Arthur Flajolet. / Ph. D.

Thesis (S.M.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 1999. / Includes bibliographical references (leaves 107-111). / We develop various algorithms for solving mixed integer-quadratic problems. These problems exhibit exponential complexity resulting from the presence of integer variables. Traditional approaches that apply in pure integer programming are not very helpful, since the existence of continuous variables in our problems complicates their use. Vie develop relaxation and heuristic algorithms designed so as to provide tight lower and upper bounds to the optimal solution of the mixed combinatorial problem. In some cases the obtained range, in which the optimum lies, is small enough to be considered satisfactory by itself. This has been accomplished in problems with up to 150 variables. Exact algorithms have also been developed and guarantee the optimal solution upon termination. The idea of Branch and Bound enhanced with the use of lower and upper bounds obtained with the aforementioned methods is implemented for that purpose. Problems with up to 70 variables have been solved. Our ideas and algorithms are applied to the Problem of Index and Portfolio Replication with a limited number of assets. This problem arises in Finance, but, in its more general form, can find application in various areas ranging from Statistics to Optimal Control and Manufacturing. / by Constantine Nikolaos Tziligakis. / S.M.

Thesis: S.M., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2014. / 76 / Cataloged from PDF version of thesis. / Includes bibliographical references (pages 67-72). / In the event of a pandemic influenza outbreak, such as the 2009-2010 H1N1 "Swine Flu" episode, it is crucial to effectively allocate limited resources in order to minimize the casualties. Design of effective resource allocation strategies requires good understanding of the underlying contact network and of the propagation dynamics. In this thesis we develop a parameter estimation method that learns the network structure, among a family of graphs, and disease dynamics from the recorded infection curve, assuming that the disease dynamics follow an SIR process. We apply the method to data collected during the 2009-2010 H1N1 epidemic and show that the best-fit model, among a scale-free network and a small-world network, indicates the scale-free network. Given the knowledge of the network structure we evaluate different vaccination strategies. As a benchmark, we allow the vaccination decisions to depend on the state of the epidemic and we show that random vaccination (which is the current practice), does not efficiently halt the spread of influenza. Instead, we propose vaccine allocation strategies that exploit the underlying network structure and provide a reduction in the number of infections by over 6 times compared to the current practice. In addition, more realistic scenario involves random encounters between agents. To test this hypothesis, we introduced a dynamic network formation on top of the static network model. We apply the estimation method to the dynamic network model and show a small improvement in estimating the infection dynamics of the 2009-2010 H1N1 influenza. / by Louis Y. Kim. / S.M.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2011. / Cataloged from PDF version of thesis. / Includes bibliographical references (p. 203-208). / Planning and controlling production in a large make-to-order manufacturing network poses complex and costly operational problems. As customers continually submit customized orders, a centralized decision-maker must quickly allocate each order to production facilities with limited but flexible labor, production capacity, and parts availability. In collaboration with a major desktop manufacturing firm, we study these relatively unexplored problems, the firm's solutions to it, and alternate approaches based on mathematical optimization. We develop and analyze three distinct models for these problems which incorporate the firm's data, testing, and feedback, emphasizing realism and usability. The problem is cast as a Dynamic Program with a detailed model of demand uncertainty. Decisions include planning production over time, from a few hours to a quarter year, and determining the appropriate amount of labor at each factory. The objective is to minimize shipping and labor costs while providing superb customer service by producing orders on-time. Because the stochastic Dynamic Program is too difficult to solve directly, we propose deterministic, rolling-horizon, Mixed Integer Linear Programs, including one that uses recently developed affinely-adjustable Robust Optimization techniques, that can be solved in a few minutes. Simulations and a perfect hindsight upper bound show that they can be near-optimal. Consistent results indicate that these solutions offer several hundred thousand dollars in daily cost saving opportunities by accounting for future demand and repeatedly re-balancing factory loads via re-allocating orders, improving capacity utilization, and improving on-time delivery. / by Gareth Pierce Williams. / Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2012. / This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. / Cataloged from student-submitted PDF version of thesis. / Includes bibliographical references (p. 151-154). / We propose a tractable optimization framework for network Air Traffic Flow Management (ATFM) with an eye towards the future. The thesis addresses two issues in ATFM research: a) fairness and collaboration amongst airlines; and b) uncertainty inherent in capacity forecasts. A unifying attraction of the overall dissertation is that the Collaborative Decision-Making (CDM) paradigm, which is the current philosophy governing the design of new ATFM initiatives, is treated as the starting point in the research agenda. In the first part of the thesis, we develop an optimization framework to extend the CDM paradigm from a single-airport to a network setting by incorporating both fairness and airline collaboration. We introduce different notions of fairness emanating from a) First-Scheduled First-Served (FSFS) fairness; and b) Proportional fairness. We propose exact discrete optimization models to incorporate them. The first fairness paradigm which entails controlling number of reversals and total amount of overtaking is especially appealing in the ATFM context as it is a natural extension of Ration-By-Schedule (RBS). We allow for further airline collaboration by proposing discrete optimization models for slot reallocation. We provide empirical results of the proposed optimization models on national-scale, real world datasets that show interesting tradeoffs between fairness and efficiency. In particular, schedules close to the RBS policy (with single digit reversals) are possible for a less than 10% increase in delay costs. We utilize case studies to highlight the considerable improvements in the internal objective functions of the airlines as a result of slot exchanges. Finally, the proposed models are computationally tractable (running times of less than 30 minutes). In the second part, we address the important issue of capacity uncertainty by presenting the first application of robust and adaptive optimization in the ATFM problem. We introduce a weather-front based approach to model the uncertainty inherent in airspace capacity estimates resulting from the impact of a small number of weather fronts. We prove the equivalence of the robust problem to a modified instance of the deterministic problem; solve the LP relaxation of the adaptive problem using affine policies; and report extensive empirical results to study the inherent tradeoffs. / by Shubham Gupta. / Ph.D.

Thesis: S.M., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2016. / Cataloged from PDF version of thesis. / Includes bibliographical references (pages 49-52). / The rapid growth of the availability of wearable biosensors has created the opportunity for using physiological signals to measure worker performance. An important question is how to use such signals to not just measure, but actually predict worker performance on a task under stressful and potentially high risk conditions. Here we show that the biological signal known as galvanic skin response (GSR) allows such a prediction. We conduct an experiment where subjects answer arithmetic questions under low and high stress conditions while having their GSR monitored. Using only the GSR measured under low stress conditions, we are able to predict which subjects will perform well under high stress conditions with a median accuracy of 75%. If we try to make similar predictions without using any biometric signals, the median accuracy is 50%. Our results suggest that performance in high stress conditions can be predicted using signals obtained from GSR sensors in low stress conditions. / by Lee Carter Mundell. / S.M.

Thesis: Ph. D., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2018. / Cataloged from PDF version of thesis. / Includes bibliographical references (pages 233-241). / Motivated by applications in Revenue Management (RM), this thesis studies various problems in sequential decision-making and demand learning. In the first module, we consider a personalized RM setting, where items with limited inventories are recommended to heterogeneous customers sequentially visiting an e-commerce platform. We take the perspective of worst-case competitive ratio analysis, and aim to develop algorithms whose performance guarantees do not depend on the customer arrival process. We provide the first solution to this problem when there are both multiple items and multiple prices at which they could be sold, framing it as a general online resource allocation problem and developing a system of forecast-independent bid prices (Chapter 2). Second, we study a related assortment planning problem faced by Walmart Online Grocery, where before checkout, customers are recommended "add-on" items that are complementary to their current shopping cart (Chapter 3). Third, we derive inventory-dependent priceskimming policies for the single-leg RM problem, which extends existing competitive ratio results to non-independent demand (Chapter 4). In this module, we test our algorithms using a publicly-available data set from a major hotel chain. In the second module, we study bundling, which is the practice of selling different items together, and show how to learn and price using bundles. First, we introduce bundling as a new, alternate method for learning the price elasticities of items, which does not require any changing of prices; we validate our method on data from a large online retailer (Chapter 5). Second, we show how to sell bundles of goods profitably even when the goods have high production costs, and derive both distribution-dependent and distribution-free guarantees on the profitability (Chapter 6). In the final module, we study the Markovian multi-armed bandit problem under an undiscounted finite time horizon (Chapter 7). We improve existing approximation algorithms using LP rounding and random sampling techniques, which result in a (1/2 - eps)- approximation for the correlated stochastic knapsack problem that is tight relative to the LP. In this work, we introduce a framework for designing self-sampling algorithms, which is also used in our chronologically-later-to-appear work on add-on recommendation and single-leg RM. / by Will (Wei) Ma. / Ph. D.

This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. / Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2006. / Includes bibliographical references (p. 155-164). / (cont.) We first address the complexity of finding an optimal minimum cost solution to a congestion game. We consider both network and general congestion games, and we examine several variants of the problem concerning the structure of the game and its associated cost functions. Many of the problem variants are NP-hard, though we do identify several versions of the games that are solvable in polynomial time. We then investigate existence and the price of anarchy of pure Nash equilibria in k-splittable congestion games with linear costs. A k-splittable congestion game is one in which each player may split its flow on at most k different paths. We identify conditions for the existence of equilibria by providing a series of potential functions. For the price of anarchy, we show an asymptotic lower bound of 2.4 for unweighted k-splittable congestion games and 2.401 for weighted k-splittable congestion games, and an upper bound of 2.618 in both cases. / In this thesis we examine four network flow problems arising in the study of transportation, communication, and water networks. The first of these problems is the Integer Equal Flow problem, a network flow variant in which some arcs are restricted to carry equal amounts of flow. Our main contribution is that this problem is not approximable within a factor of 2n(1-epsilon]), for any fixed [epsilon] > 0, where n is the number of nodes in the graph. We extend this result to a number of variants on the size and structure of the arc sets. We next study the Pup Matching problem, a truck routing problem where two commodities ('pups') traversing an arc together in the network incur the arc cost only once. We propose a tighter integer programming formulation for this problem, and we address practical problems that arise with implementing such integer programming solutions. Additionally, we provide approximation and exact algorithms for special cases of the problem where the number of pups is fixed or the total cost in the network is bounded. Our final two problems are on the topic of congestion games, which were introduced in the area of communications networks. / by Carol Meyers. / Ph.D.