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 107-109). / In the study of queueing systems, a question of significant current interest is that of large scale behavior, where the size of the system increases without bound. This regime has becoming increasingly relevant with the rise of massive distributed systems like server farms, call centers, and health care management systems. To minimize underutilization of resources, the specific large scale regime of most interest is one in which the work to be done increases as processing capability increases. In this thesis, we characterize the behavior of two such large scale queueing systems. In the first part of the thesis we consider a Join the Shortest Queue (JSQ) policy in the so-called Halfin-Whitt heavy traffic regime. We establish that a scaled process counting the number of idle servers and queues of length two weakly converges to a two-dimensional reflected Ornstein-Uhlenbeck process, while processes counting longer queues converge to a deterministic system decaying to zero in constant time. This limiting system is similar to that of the traditional Halfin-Whitt model in its basic performance measures, but there are key differences in the queueing behavior of the JSQ model. In particular, only a vanishing fraction of customers will have to wait, but those who do will incur a constant order waiting time. In the second part of the thesis we consider a widely studied so-called "supermarket model" in which arriving customers join the shortest of d randomly selected queues. Assuming rate n[lambda]n Poisson arrivals and rate 1 exponentially distributed service times, our heavy traffic regime is described by [lambda]n 1 as n --> [infinity]. We give a simple expectation argument establishing that queues have steady state length at least i* = logd 1/1-[lambda]n with probability approaching one as n [infinity] 8. Our main result for this system concerns the detailed behavior of queues with length smaller than i*. Assuming [lambda]n converges to 1 at rate at most [square root of]n, we show that the dynamics of such queues does not follow a diffusion process, as is typical for queueing systems in heavy traffic, but is described instead by a deterministic infinite system of linear differential equations, after an appropriate rescaling. / by Patrick Clark Eschenfeldt. / Ph. D.

Thesis: Ph. D., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2016. / 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 215-220). / Optimization in the presence of uncertainty is at the heart of operations research. There are many approaches to modeling the nature of this uncertainty, but this thesis focuses on developing new algorithms, software, and insights for an approach that has risen in popularity over the last 15 years: robust optimization (RO), and its extension to decision making across time, adaptive optimization (AO). In the first chapter, we perform a computational study of two approaches for solving RO problems: "reformulation" and "cutting planes". Our results provide useful evidence for what types of problems each method excels in. In the second chapter, we present and analyze a new algorithm for multistage AO problems with both integer and continuous recourse decisions. The algorithm operates by iteratively partitioning the problem's uncertainty set, using the approximate solution at each iteration. We show that it quickly produces high-quality solutions. In the third chapter, we propose an AO approach to a general version of the process flexibility design problem, whereby we must decide which factories produce which products. We demonstrate significant savings for the price of flexibility versus simple but popular designs in the literature. In the fourth chapter, we describe computationally practical methods for solving problems with "relative" RO objective functions. We use combinations of absolute and relative worst-case objective functions to find "Pareto-efficient" solutions that combine aspects of both. We demonstrate through three in-depth case studies that these solutions are intuitive and perform well in simulation. In the fifth chapter, we describe JuMPeR, a software package for modeling RO and AO problems that builds on the JuMP modeling language. It supports many features including automatic reformulation, cutting plane generation, linear decision rules, and general data-driven uncertainty sets. / by Iain Robert Dunning. / 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. 129-137). / In this thesis, we propose new mixed integer optimization (MIO) methods to ad- dress problems in machine learning. The first part develops methods for supervised bipartite ranking, which arises in prioritization tasks in diverse domains such as information retrieval, recommender systems, natural language processing, bioinformatics, and preventative maintenance. The primary advantage of using MIO for ranking is that it allows for direct optimization of ranking quality measures, as opposed to current state-of-the-art algorithms that use heuristic loss functions. We demonstrate using a number of datasets that our approach can outperform other ranking methods. The second part of the thesis focuses on reverse-engineering ranking models. This is an application of a more general ranking problem than the bipartite case. Quality rankings affect business for many organizations, and knowing the ranking models would allow these organizations to better understand the standards by which their products are judged and help them to create higher quality products. We introduce an MIO method for reverse-engineering such models and demonstrate its performance in a case-study with real data from a major ratings company. We also devise an approach to find the most cost-effective way to increase the rank of a certain product. In the final part of the thesis, we develop MIO methods to first generate association rules and then use the rules to build an interpretable classifier in the form of a decision list, which is an ordered list of rules. These are both combinatorially challenging problems because even a small dataset may yield a large number of rules and a small set of rules may correspond to many different orderings. We show how to use MIO to mine useful rules, as well as to construct a classifier from them. We present results in terms of both classification accuracy and interpretability for a variety of datasets. / by Allison An Chang. / Ph.D.

Thesis (S.M.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2012. / Cataloged from PDF version of thesis. / Includes bibliographical references (p. 155-156). / The U.S. military considers Unmanned Underwater Vehicles (UUVs) a critical component of the future for two primary reasons - they are effective force multipliers and a significant risk-reducing agent. As the military's technology improves and UUVs become a reliable mission asset, the vehicle's ability to make intelligent decisions will be crucial to future operations. The thesis develops various algorithms to solve the UUV Mission-Planning Problem (UUVMPP), where the UUV must choose which tasks to perform in which sequence in a stochastic mission environment. The objective is to find the most profitable way to execute tasks with restrictions of total mission time, energy, time-restricted areas, and weather conditions. Since the UUV accumulates navigation error over time while maneuvering underwater, the UUV must occasionally halt operations to re-orient itself via a navigation fix. While a navigation fix takes time and increases the likelihood of exposing the vehicle's position to potential adversaries, a reduction in navigation error allows the UUV to perform tasks and navigate with a greater amount of certainty. The algorithms presented in this thesis successfully incorporate navigation fixes into the mission-planning process. The thesis considers Mixed-Integer Programming, Exact Dynamic Programming, and an Approximate Dynamic Programming technique known as Rollout to determine the optimal a priori route that meets operational constraints with a specified probability. The thesis then shows how these formulations can solve and re-solve the UUVMPP on-line. In particular, the Rollout Algorithm finds task route solutions on average 96% of the optimal solution a priori and 98% of the optimal solution on-line compared to exact algorithms; with a significant reduction in computation run time, the Rollout Algorithm permits the solving of increasingly complex mission scenarios. / by Brian A. Crimmel. / S.M.

Thesis (S.M.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2008. / Includes bibliographical references (p. 79-80). / This thesis describes the design and implementation of an optimization model to manage inventory at Dell's American factories. Specifically, the model is a mixed integer program which makes routing decisions on incoming monitors (a bulky item which incurs great shipping costs) from Asia to Dell's factories in America as well as inventory transfer decisions from factory to factory. The optimization model approaches the inventory allocation problem by minimizing inventory routing costs plus shortage costs across all sites subject to constraints which define the specifics of Dell's supply chain. Shortage costs are assessed using a per part per day back order penalty, however a more precise assessment of shortage costs using actual costs from a combined MIT/Dell study is also presented. The software implementation of the optimization model has been field tested and validated and is now being adopted on a global level for use in balancing supply to all of Dell's factories worldwide. The software design as well as the implementation results are discussed within this thesis. Also, an adaptation of the model to a global scale is presented. This extension of the model, which assumes a "global warehouse" upstream in the supply chain, allocates inventory from the China to regional facilities throughout the world subject to supply chain constraints and the understanding that regional teams will tend to balance out their own region's inventory using intraregional balancing decisions. / by John William Foreman. / S.M.

Thesis: S.M., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2014. / Cataloged from PDF version of thesis. / Includes bibliographical references (pages 73-74). / In the face of large increases in the number of passengers and flights, busy airports worldwide have been trying to optimize operating efficiency and throughput and minimize congestion on a daily basis. In the case of departures, measures can be taken at the gate, on the taxiway system or at the runway queue to minimize departure delays and/or the cost of unavoidable delays. This cost includes needless fuel consumption and noxious emissions. In this thesis, we focus primarily on runway queue optimization. The first part of this work consists of designing a generic simulation which models specific days of operations at an airport. Using as input the schedule of operations specific to the modeled airport, the simulation processes all departures and stores the characteristic times of the process for each departing aircraft. The quantities of interest are either incrementally computed by the simulation or modeled using probability distributions derived from airport-specific data. We then present a dynamic programming approach to sequencing departing aircraft at the runway queue. Two algorithms are presented based on the idea of Constrained Position Shifting, which maintains a high level of fairness in the order in which aircraft gain access to runways, while also improving efficiency by comparison to First Come First Served sequencing. The objective of the first algorithm is to minimize makespan, and that of the second to minimize delays. We then focus on a specific airport, which has been experiencing one of the fastest growth rates in the industry. We analyze the output of our simulation as applied to this airport and accumulate insights about congestion at the departure runways. We next apply this sequencing algorithm to this specific airport using multiple demand profiles that represent both the current traffic levels, as well as anticipated future ones that would result in more congestion. We give quantitative arguments to confirm the positive impact of the optimization on the airport's operations. We also emphasize the importance of the aircraft mix on the techniques' performance and show that the sequencing algorithms provide higher benefits (in terms of reducing delays) as the mix becomes more heterogeneous. / by Alexandre Paul Sahyoun. / S.M.

Thesis: Ph. D., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2018. / 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 175-182). / Container terminals, where containers are transferred between different modes of transportation both on the seaside and landside, are crucial links in intercontinental supply chains. The rapid growth of container shipping and the increasing competitive pressure to lower rates result in demand for higher productivity. In this thesis, we design new models and methods for the combinatorial optimization problems representing storage yard operations in maritime container terminals. The goal is to increase the efficiency of yard cranes by decreasing unproductive container moves (also called relocations). We consider three problems with applicability to real-time operations. First, we study the container relocation problem that involves finding a sequence of container moves that minimizes the number of relocations needed to retrieve all containers, while respecting a given order of retrieval. We propose a new binary integer program model, perform an asymptotic average case analysis, and show that our methods can apply to other storage systems where stacking occurs. Second, we relax the assumption that the full retrieval order of containers is known in advance and study the stochastic container relocation problem. We introduce a new model, compare it with an existing one, and develop two new algorithms for both models based on decision trees and new heuristics. We show that techniques in this chapter apply more generally to finite horizon stochastic optimization problems with bounded cost functions. Third, we consider the integrated container relocation problem and yard crane scheduling problem to find an optimal sequence of scheduled crane moves that perform the required container movements. Taking into account practical constraints, we present a new model, propose a binary integer program using a network flow-type formulation, and design an efficient heuristic procedure for real-time operations based on properties of our mathematical formulation. We relate this problem to pick-up and delivery problems with a single vehicle and capacities at every node. In all three chapters, the efficiency of all our algorithms are shown through extensive computational experiments on available problem instances from the literature and/or on real data. / by Virgile Galle. / Ph. D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2007. / This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. / Includes bibliographical references (p. 175-182). / In the context of patient care for life-threatening illnesses, the presence of uncertainty may compromise the quality of a treatment. In this thesis, we investigate robust approaches to managing uncertainty in radiation therapy treatments for cancer. In the first part of the thesis, we study the effect of breathing motion uncertainty on intensity-modulated radiation therapy treatments of a lung tumor. We construct a robust framework that generalizes current mathematical programming formulations that account for motion. This framework gives insight into the trade-off between sparing the healthy tissues and ensuring that the tumor receives sufficient dose. With this trade-off in mind, we show that our robust solution outperforms a nominal (no uncertainty) solution and a margin (worst-case) solution on a clinical case. Next, we perform an in-depth study into the structure of different intensity maps that were witnessed in the first part of the thesis. We consider parameterized intensity maps and investigate their ability to deliver a sufficient dose to the tumor in the presence of motion that follows a Gaussian distribution. We characterize the structure of optimal intensity maps in terms of certain conditions on the problem parameters. / (cont.) Finally, in the last part of the thesis, we study intensity-modulated proton therapy under uncertainty in the location of maximum dose deposited by the beamlets of radiation. We provide a robust formulation for the optimization of proton-based treatments and show that it outperforms traditional formulations in the face of uncertainty. In our computational experiments, we see evidence that optimal robust solutions use the physical characteristics of the proton beam to create dose distributions that are far less sensitive to the underlying uncertainty. / by Timothy Ching-Yee Chan. / Ph.D.

Thesis (Ph.D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2001. / Includes bibliographical references (leaves 141-146). / Can airline Yield Management strategies be used to generate additional revenue from spare capacity in telecom networks? Pundits believe "yes", based on several analogies between the industries such as, for instance, perishable inventory and negligible marginal cost of usage. However, no one has yet described how, one of the chief difficulties being the vastly different nature of airlines products and telecom services. Motivated to show how Operations Research can play a role in structuring this area, we: (i) argue that telecom Yield Management should be based on 'innovative' services explicitly designed to use only spare capacity, (ii) propose, borrowing from airlines, a framework to simplify related decision modeling, and (iii) demonstrate both our argument and the framework by articulating several 'innovative' telecom services and modeling them to varying degrees of depth. This thesis focuses only on the decision-making that will be required within a large infrastructure for operating new 'Yield Management' services. For each service, several decision variables can be considered to maximize revenue from available capacity, e.g. pricing, capacity limits and admission control, among others. Incorporating all such decisions in a single model usually leads to complicated formulations. A framework that decouples the decisions from each other to obtain simpler, more insightful models is therefore immensely helpful. We propose using the airlines modeling framework to separate the decisions involved in the operation of each new service. This framework classifies models into forecasting, over-booking, seat-inventory control, pricing and market segmentation to reduce the complexity of the system-wide problem. To make this framework useful for telecom, we provide a detailed interpretation of each category in the telecom context. . Finally, the majority of this thesis is the six service ideas that illustrate our argument and the models that demonstrate how the framework might be used. For each service we propose, we discuss possible markets and practical issues. We then formulate a model for one of the decisions resulting from the framework. These models are analyzed to varying depths to demonstrate the operating rules one can discover for revenue maximization. The contributions of this work are at multiple levels. In addition to our argument and examples of services proposed for telecom Yield Management, it structures the modeling questions in a coherent manner, exploiting more than only the high-level connections between airlines and telecom. Finally, the models themselves are useful and their contributions are at the analytical level. This thesis makes clear several connections between airline and telecom Yield Management that people have found difficult to establish in the past. / by Salal Humair. / Ph.D.

Thesis: S.M., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2014. / This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. / 36 / "June 2014." Cataloged from student-submitted PDF version of thesis. / Includes bibliographical references (pages 95-97). / In this thesis, we develop methods to address airlift scheduling, and in particular the problem of scheduling military aircraft capacity to meet ad hoc demand. Network optimization methods typically applied to scheduling problems do not sufficiently capture all necessary characteristics of this problem. Thus, we develop a new method that uses integer linear programming (IP) with column generation to make the problem more tractable while incorporating the relevant characteristics. In our method, we decompose the problem into two steps: generating feasible aircraft routes, and solving the optimization model. By ensuring that routes are feasible with respect to travel time, ground time, crew rest, and requirement restrictions when we build them, we do not need to encode these characteristics within the IP optimization model, thus reducing the number of constraints. Further, we reduce the number of decision variables by generating only the fraction of feasible aircraft routes needed to find near-optimal solutions. We propose two methods for generating routes to include in the IP model: explicit column generation and selective column generation. In explicit column generation, all aircraft routes that we could potentially consider including in the model are generated first. Starting with a subset of these routes, we iteratively use reduced cost information obtained by solving a relaxed version of the IP model to choose more routes to add from the original set of routes. In selective column generation, we first generate a small set of feasible aircraft routes. Starting with this set of routes, we iteratively generate more routes by solving a relaxed version of the IP model and then combine routes in the solution together and add those that are feasible to the route set. In both methods, we iterate until there are either no other routes to include or the solution stops improving. Last, we solve the IP model with the final set of routes to obtain an integer solution. We test the two approaches by varying the number of locations in the network, the number of locations that are wings, and the number of requirements. We show that selective column generation produces a solution with an objective value similar to that of explicit column generation in a fraction of the time. In our experiments, we solve problems with up to 100 requirements using selective column generation. In addition, we test the impact of integrating lines of business while scheduling airlift and show a significant improvement over the current process. / by Mark J. Williams. / S.M.