With the drastic increase in the demand for air travel, taxiway aircraft traffic scheduling is becoming increasingly important in managing air traffic. In order to reduce traffic congestion on taxiways, this thesis proposes a tool for air traffic controllers to use in decision making: a taxiway air traffic model developed using Mixed Integer Programming (MIP) that can be applied to a rolling time horizon. The objective of this model is to minimize the total taxi time, and the output is a schedule and route for each aircraft. This MIP model assumes that only the origin and destination of each aircraft is fixed; due to some uncertain factors in the air arrival and departure process, it allows for the departure time and arrival time to vary within a certain time window. This MIP model features aircraft type, and also incorporates runway crossings and runway separations. The model is programmed using C++ and Solved in CPLEX 12.1. Runways 26R and 26L of George Bush International Airport are used to find solutions. The author presents a rolling horizon method by dividing the large scheduling issue into smaller time interval problems according to the scheduled times of departure or arrival. A bound is also proposed based on the discretized time interval problems. By using partial data from George Bush International Airport (IAH), solutions are obtained. The results are compared with the bound and show fairly high optimality. Compared with the previous research, this thesis presents a model with more flexibility by considering different operations. By using the rolling horizon method, the problem is broken into smaller units that can be solved efficiently without losing much optimality.

This dissertation explores mathematical programming optimization models and algorithms for routing and scheduling ships in a maritime transportation system. Literature surveyed on seaborne transportation systems indicates that there is a scarcity of research on ship routing and scheduling problems. The complexity and the overwhelming size of a typical ship routing and scheduling problem are the primary reasons that have resulted in the scarcity of research in this area. The principal thrust of this research effort is focused at the Kuwait Petroleum Corporation (KPC) Problem. This problem is of great economic significance to the State of Kuwait, whose economy has been traditionally dominated to a large extent by the oil sector. Any enhancement in the existing ad-hoc scheduling procedure has the potential for significant savings. A mixed-integer programming model for the KPC problem is constructed in this dissertation. The resulting mathematical formulation is rather complex to solve due to (1) the overwhelming problem size for a typical demand contract scenario, (2) the integrality conditions, and (3) the structural diversity in the constraints. Accordingly, attempting to solve this formulation for a typical demand contract scenario without resorting to any aggregation or partitioning schemes is theoretically complex and computationally intractable. Motivated by the complexity of the above model, an aggregate model that retains the principal features of the KPC problem is formulated. This model is computationally far more tractable than the initial model, and consequently, it is utilized to construct a good quality heuristic solution for the KPC problem. The initial formulation is solved using CPLEX 4.0 mixed integer programming capabilities for a number of relatively small-sized test cases, and pertinent results and computational difficulties are reported. The aggregate formulation is solved using CPLEX 4.0 MIP in concert with specialized rolling horizon solution algorithms and related results are reported. The rolling horizon solution algorithms enabled us to handle practical sized problems that could not be handled by directly solving the aggregate problem. The performance of the rolling horizon algorithms may be enhanced by increasing the physical memory, and consequently, better solutions can be extracted. The potential saving and usefulness of this model in negotiation and planning purposes strongly justifies the acquisition of more computing power to tackle practical sized test problems. An ad-hoc scheduling procedure that is intended to simulate the current KPC scheduling practice is presented in this dissertation. It is shown that results obtained via the proposed rolling horizon algorithms are at least as good, and often substantially better than, results obtained via this ad-hoc procedure. / Ph. D.

The factors limiting the performance of computer software periodically undergo sudden shifts, resulting from technological progress, and these shifts can have profound implications for the design of high performance codes. At the present time, the speed with which hardware can execute a single stream of instructions has reached a plateau. It is now the number of instruction streams that may be executed concurrently which underpins estimates of compute power, and with this change, a critical limitation on the performance of software has come to be the degree to which it can be parallelised. The research in this thesis is concerned with the means by which codes for linear programming may be adapted to this new hardware. For the most part, it is codes implementing the simplex method which will be discussed, though these have typically lower performance for single solves than those implementing interior point methods. However, the ability of the simplex method to rapidly re-solve a problem makes it at present indispensable as a subroutine for mixed integer programming. The long history of the simplex method as a practical technique, with applications in many industries and government, has led to such codes reaching a great level of sophistication. It would be unexpected in a research project such as this one to match the performance of top commercial codes with many years of development behind them. The simplex codes described in this thesis are, however, able to solve real problems of small to moderate size, rather than being confined to random or otherwise artificially generated instances. The remainder of this thesis is structured as follows. The rest of this chapter gives a brief overview of the essential elements of modern parallel hardware and of the linear programming problem. Both the simplex method and interior point methods are discussed, along with some of the key algorithmic enhancements required for such systems to solve real-world problems. Some background on the parallelisation of both types of code is given. The next chapter describes two standard simplex codes designed to exploit the current generation of hardware. i6 is a parallel standard simplex solver capable of being applied to a range of real problems, and showing exceptional performance for dense, square programs. i8 is also a parallel, standard simplex solver, but now implemented for graphics processing units (GPUs).

The study aims to provide information on efficiency opportunities on SCA's northbound cassettes. It has been made by examining the capacity utilization rate on the northbound cassettes on SCA's vessels for a period of two weeks. The cargo loaded in the ports of Rotterdam and Sheerness consists of external cargo of varying shape. The cargo is shipped northbound to Holmsund and Sundsvall. Measurements have been made on the cargo to the final destinations Sundsvall, Holmsund and Finland. The measurements have been used in a mathematical optimization model created to optimize the loading of the cassettes. The model is based on placing boxes in a grid where the boxes that are placed representing the cargo and the grids representing the cassettes. The aim of the model is to reduce the number of cassettes and thereby increase the capacity utilization rate. The study resulted in an increase in capacity utilization rate for both area and volume to all destinations. The overall improvement for all cassettes examined resulted in an increase in the area capacity utilization rate by 9.02 percentage points and 5.72 percentage points for the volume capacity utilization rate. It also resulted in a decrease of 22 cassettes in total on the four voyages that were examined which indicate that there are opportunities to improve the capacity utilization rate. The study also shows that the model can be used as a basis for similar problems.

In recent years, the importance of incorporating uncertainty into planning models for logistics and transportation systems has been widely recognized in the Operations Research and transportation science communities. Maritime transportation, as a major mode of transport in the world, is subject to a wide range of disruptions at the strategic, tactical and operational levels. This thesis is mainly concerned with the development of robustness planning strategies that can mitigate the effects of some major types of disruptions for an important class of optimization problems in the shipping industry. Such problems arise in the creation and negotiation of long-term delivery contracts with customers who require on-time deliveries of high-value goods throughout the year. In this thesis, we consider the disruptions that can increase travel times between ports and ultimately affect one or more scheduled deliveries to the customers. Computational results show that our integrated solution procedure and robustness planning strategies can generate delivery plans that are both economical as well as robust against uncertain disruptions.

Sugar mills represent significant capital investments. To maintain appropriate returns on their investment, sugar companies seek to run the mills at capacity over the sugarcane harvest season. Because the sugar content of cane degrades considerably once it is cut, maintaining inventories of cut cane is undesirable. Instead, mills want to coordinate the arrival of cut cane with production. We present exact solution approaches exploiting special structure of the sugarcane harvest logistics problem in Brazil and the United States.

The United State’s renewable portfolio standards call for a large increase of renewable energy and improved conservation efforts over today’s current system. Wind will play a ma jor role in meeting the renewable portfolio standards. As a result, the amount of wind capacity and generation has been growing exponentially over the past 10 to 15 years. The proposed unit commitment method integrates wind energy into a scheduable resource while keeping the formulation simple using mixed integer programming. A reserve constraint is developed and added to unit commitment giving the forecasted wind energy an effective cost. The reserve constraint can be scaled based on the needs of the system: cost, reliability, or the penetration of wind energy. The results show that approximately 24% of the load can be met in the given test system, while keeping a constant reliability before and after wind is introduced. This amount of wind will alone meet many of the renewable portfolio standards in the United States.

No description available.

In this thesis we study how to solve some nonconvex optimization problems by using methods that capitalize on the success of Linear Programming (LP) based solvers for Mixed Integer Linear Programming (MILP). A common aspect of our solution approaches is the use, development and analysis of small but strong extended LP/MILP formulations and approximations. In the first part of this work we develop an LP based branch-and-bound algorithm for mixed integer conic quadratic programs. The algorithm is based on a lifted polyhedral relaxation of conic quadratic constraints by Ben-Tal and Nemirovski. We test the algorithm on a series of portfolio optimization problems and show that it provides a significant computational advantage. In the second part we study the modeling of a class of disjunctive constraints with a logarithmic number of variables. For specially structured disjunctive constraints we give sufficient conditions for constructing MILP formulations with a number of binary variables and extra constraints that is logarithmic in the number of terms of the disjunction. Using these conditions we introduce formulations with these characteristics for SOS1, SOS2 constraints and piecewise linear functions. We present computational results showing that they can significantly outperform other MILP formulations. In the third part we study the modeling of non-convex piecewise linear functions as MILPs. We review several new and existing MILP formulations for continuous piecewise linear functions with special attention paid to multivariate non-separable functions. We compare these formulations with respect to their theoretical properties and their relative computational performance. In addition, we study the extension of these formulations to lower semicontinuous piecewise linear functions. Finally, in the fourth part we study the strength of MILP formulations for LPs with Probabilistic Constraints. We first study the strength of existing MILP formulations that only considers one row of the probabilistic constraint at a time. We then introduce an extended formulation that considers more than one row of the constraint at a time and use it to computationally compare the relative strength between formulations that consider one and two rows at a time.

Master of Agribusiness / Department of Agricultural Economics / Jason S. Bergtold / Technical support for products after the sale is commonplace in today’s businesses. Original Equipment Manufacturers (OEMs) provide technical support to their dealer channel for resolution of complex product issues. Technical support staffing levels can vary by product type, product complexity, and production volumes, and case volumes. This research seeks a better understanding of appropriate staffing levels between three product lines for one OEM. The objective of this paper is to develop a model for monthly and weekly average case volumes for the three product lines, based off of historical case volume data. This data is used to predict a product line’s (platform’s) workload based off the month of the year. The output of each platform’s monthly case volume is then used in an optimization model to determine optimal staffing levels for each platform, based off the time of the year. The models developed for each platform use a linear relationship which regresses workload on a set of binary variable for the months of the year. Each of the models developed provided statistically significant coefficients for months which contain the platform’s highest workload. The outputs from these models are used in a mixed integer nonlinear programming optimization model to determine staff level of full time equivalent (FTE) employees at each platform. Each of the three scenarios utilized in this research provide similar trends and staffing levels for each of the three product lines. Results of this research are of interest for the management of technical support staffing.