Search

The growing adoption of electric vehicles presents an opportunity to explore the numerous benefits to network operators. For example, aggregated electric vehicles can replace peaking power plants traditionally used to satisfy peak energy demands. However, unlike other distributed energy resources, electric vehicles do not have fixed locations within single- or multi-energy systems as they can be connected to any charging station. This makes optimally coordinating their charge/discharge operations challenging, compounded when uncertainties related to electric vehicles' characteristics, availability, and charging preferences are considered. Presented is a generalised mobile storage model representing successive electric vehicles' charge/discharge operations that will utilise a charging station. The model is not restricted to a fixed number of electric vehicles and can be used to analyse the different ways charging stations are utilised in residential, commercial, and public areas. The mobile storage model extends a generalised modelling framework primarily developed for predictive control applications. Modifications are made to the entire framework for application in stochastic predictive control. The effectiveness of the modified framework is demonstrated with three representative case studies. One illustrates how the model is incorporated into the generalised framework and implemented within a deterministic energy management scheme. Results show significant cost savings when exploiting successive electric vehicles utilising a charging station. The other is used to demonstrate how uncertainties are incorporated within the generalised framework and implemented within a stochastic energy management scheme. Results show significant cost savings compared to the deterministic scheme. Finally, the last case study has a varying number of charging stations. It is used to analyse the performance of a stochastic scheme whose optimisation problem is designed to consider charge/discharge power smoothing applications. This is done to prevent damage when electric vehicles are used for ancillary services such as peak demand management. Analyses presented show the challenges in implementing the stochastic scheme in different areas.

Scheduling refinery operation promises a big cut in logistics cost, maximizes efficiency, organizes allocation of material and resources, and ensures that production meets targets set by planning team. Obtaining accurate and reliable schedules for execution in refinery plants under different scenarios has been a serious challenge. This research was undertaken with the aim to develop robust methodologies and solution procedures to address refinery scheduling problems with uncertainties in process parameters. The research goal was achieved by first developing a methodology for short-term crude oil unloading and transfer, as an extension to a scheduling model reported by Lee et al. (1996). The extended model considers real life technical issues not captured in the original model and has shown to be more reliable through case studies. Uncertainties due to disruptive events and low inventory at the end of scheduling horizon were addressed. With the extended model, crude oil scheduling problem was formulated under receding horizon control framework to address demand uncertainty. This work proposed a strategy called fixed end horizon whose efficiency in terms of performance was investigated and found out to be better in comparison with an existing approach. In the main refinery production area, a novel scheduling model was developed. A large scale refinery problem was used as a case study to test the model with scheduling horizon discretized into a number of time periods of variable length. An equivalent formulation with equal interval lengths was also presented and compared with the variable length formulation. The results obtained clearly show the advantage of using variable timing. A methodology under self-optimizing control (SOC) framework was then developed to address uncertainty in problems involving mixed integer formulation. Through case study and scenarios, the approach has proven to be efficient in dealing with uncertainty in crude oil composition.

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 expansion of distributed energy resources (DER), demand response (DR), and virtual bidding in many power systems and energy markets are creating new challenges for unit commitment (UC) and economic dispatch (ED) techniques. Instead of a small number of traditionally large generators, the power system resource mix is moving to one with a high percentage of a large number of small units. These can increase the number of similar or identical units, leading to chattering (switching back and forth among committed units between iterations). This research investigates alternative and scalable ways of increasing the high penetration of these resources. First, the mathematical formulations for UC and ED models are reviewed. Then a new heuristic is proposed that takes advantage of the incremental nature of Lagrangian relaxation (LR). The heuristic linearizes and distributes the network transmission losses to appropriately penalize line flow and mitigate losses. Second, a mixed integer programming (MIP) is used as a benchmark for the proposed LR formulation. The impact of similar and identical units on the solution quality and simulation run time of UC and ED was investigated using the proposed formulation. Third, a system flexibility study is done using DR and a load demand pattern with a high penetration of renewables, creating a high daily ramp rate requirement. This work investigates the impact of available DR on spikes in locational marginal pricing (LMP). Fourth, two studies are done on improving LR computational efficiency. The first proposes a heuristic that focuses on trade-offs between solution quality and simulation run time. The heuristic iterates over lambda and energy marginal price while the convergence issue is handled using Augmented LR (ALR). The second study proposes a heuristic that penalizes transmission lines with binding line limits. The proposed method can reduce power flow in the transmission lines of interest, and considerably reduce the simulation time in optimization problems with a high number of transmission constraints. Finally, the effect of a large number of similar and identical units on simulation run time is considered. The proposed formulation scales linearly with the increase in system size.

In this dissertation, I will cover two distinct topics. In the first part, I will discuss the subgraph isomorphism problem which has a broad range of applications from pattern recognition and bioinformatics to compilers circuit design. In combinatorial problems such as these, symmetry, if unaccounted for, can confound standard solvers leading to significant amounts ofredundant work being done. I will introduce multiple approaches for dynamically exploiting this symmetry to accelerate solvers as well as to compactly characterize the set of solutions. I rigorously establish conditions under which from one subgraph isomorphism, potentially exponentially many more may be generated. I also demonstrate through empirical assessment that incorporating symmetry into subgraph search can provide significant reductions in search time and produce many more solutions. In the presence of these huge solution spaces, there still remains the work of determining the actual subgraph isomorphism of interest. In an approach inspired by active learning, I will introduce the problem of querying template vertices for more information to uniquely identify solutions. Multiple different strategies for querying vertices which also incorporate symmetry are established and assessed by rigorous analysis and comprehensive experiments. In the second part, I will discuss methods for formulating neural network constrained optimization problems. With the advent of machine learning, neural networks have been used as a surrogate for complicated physical models, and the incorporation of these networks into optimization problems is a challenge. I will present a direct embedding approach, a mixed integer program, and a nonlinear program with complementarity constraints as methods for formulating these problems to be used with standard optimization solvers. I establish key properties of each methods, and through experiments, I assess the advantages and disadvantages for each approach.

As exploration in space increases through the use of larger telescopes, more sophisticated structures, and physical exploration, the use of autonomous robots will become instrumental to build and maintain the infrastructures required for this exploration. These systems must be autonomous to deal with the infeasibility of teleoperation due signal delay and task complexity. The reality of using robots in the real world without direct human input will require the autonomous systems to have the capability of responding to errors that occur in an assembly scenario on their own. As such, a system must be in place to allow for the sequencing and allocation of tasks to the robotic workforce autonomously, giving the ability to re-plan in real world stochastic environments. This work presents four contributions towards a system allowing for the autonomous sequencing and allocation of tasks for in-space assembly problems. The first contribution is the development of the Stochastic Assembly Problem Definition (SAPD) to articulate all of the features in an assembly problem that are applicable to the task sequencing and allocation. The second contribution is the formulation of a mixed integer program to solve for assembly schedules that are optimal or a quantifiable measurement from optimal. This contribution is expanded through the development of a genetic algorithm formulation to utilize the stochastic information present in the assembly problem. This formulation extends the state-of-the-art techniques in genetic algorithms to allow for the inclusion of new constraints required for the in-space assembly domain. The third contribution addresses how to estimate a robot's ability to complete a task if the robot must be assigned to a task it was previously not expected to work on. This is accomplished through the development of four metrics and analyzed through the use of screw theory kinematics. The final contribution focuses on a set of metrics to guide the selection of a good scheduling method for different assembly situations. The experiments in this work demonstrate how the developed theory can be utilized and shows the scheduling systems producing the best or close to the best schedules for assemblies. It also shows how the metrics used to quantify and estimate robot ability are applied. The theory developed in this work provides another step towards autonomous systems that are capable of assembling structures in-space without the need for human input.

Disinformation has become a more common weapon amidst growing social media platforms and users, targeting consumer behavior to affect physical infrastructure. Understanding how disinformation could attack a multi-commodity network and how to minimize its spread will help alleviate stress on systems during attacks. This research integrates an epidemiological model (SIR) with a mixed integer programming (MIP) model to minimize weighted shortage across commodities, evaluating the change over time dependent on disinformation spread β and recovery γ. It is then applied to a multi-commodity Swedish railway network carrying 14 goods over 200 nodes. Results demonstrated how different spread and recovery rates change the degree and timing of shortage.

There are many factors such as, space constraint, service level, and nursing personnel satisfaction that makes the hospital supply chain more complex than the traditional supply chain. Effective inventory management can contribute to a significant amount of cost reduction. This thesis proposed a new multiple Kanban card system for hospital nursing units that will replace the two-bin system into the multiple Kanban card system. The new system helps to reduce the overall inventory cost. For the new system, along with restocking cost, inventory holding cost, and shortage cost, an additional Kanban cards retrieve cost is included. A mixed-integer programming model is developed for the new system. To validate the model, both small-scale and large-scale problems are solved using solving constraint integer programs (SCIP) solver with AMPL software. A comparison is made between the two Kanban card system and the multiple Kanban card system in terms of overall inventory cost. The result showed that 25% cost reduction possible for multiple Kanban card system. The characteristics of the objective function of this model are further analyzed by varying the service level. The result showed that using the multiple Kanban card system, a high service level can be achieved at a minimum cost that is 27% lower than the cost for using two Kanban card system.

Over the last two decades, large-scale disaster events have significantly increased in frequency and intensity, causing tremendous loss of lives and property. A large number of relief organizations rely on their volunteers to respond to many disasters around the globe, serving people and communities in need. While their contributions are priceless, turnover among disaster volunteers has become a significant problem for these relief organizations. Work environment factors, such as volunteers being mismatched with tasks, unsuitable workloads, and conflict within groups of volunteers may give rise to turnover intentions, which may in turn lead to actual turnover. The link between work environment factors and volunteer turnover intentions in these situations has not yet received considerable attention in terms of quantitative research. Therefore, the purpose of this dissertation is to develop quantitative models that consider the factors that may cause turnover or turnover intentions. The goal of these models is to help decision makers for non-governmental organizations (NGOs) better manage their disaster volunteers during relief efforts, with the aim of satisfying community needs and improving volunteer retention rates. The first study addresses a gap in volunteer staff planning and scheduling where volunteer training is first presented, with volunteer turnover represented as a percentage of volunteer–task mismatch. We have developed a mixed-integer programming model for assigning optimal volunteer assignments based on a range of possible short- and long-term community need scenarios. The objective is to minimize the costs of unmet community needs, volunteer attrition due to mismatch assignments, and volunteer expenses. Under different demand scenarios, the optimum solution of volunteer assignment is to allow unskilled volunteers to start training early so that they can help skilled volunteers when a peak of long-term skilled task demand is expected. The second study investigates the effects of work environment factors on the satisfaction level and turnover intentions of disaster volunteers. Using an online survey, data from 386 disaster volunteers are collected and analyzed. Confirmatory factor analysis (CFA) and structural equation modeling are used to test the measurement model and answer research questions focused on volunteer behavior. After assessing and confirming the measurement model, we use the structural model to test the hypotheses and provide prediction equations. Job-fit, training, workload, volunteer group, and supervisor are the key work environment factors considered in this study. The findings suggest that these work environment factors have a positive significant relationship with satisfaction and a negative significant relationship with turnover intentions. The last study focuses on developing a simulation modeling approach that considers a volunteer’s satisfaction and turnover intentions in relation to management decisions of an NGO during a relief event. We use a survey to gather information from disaster volunteer managers about how they manage their volunteer teams and use this information and the findings from the second study to model a realistic relief event. We develop a hybrid simulation model, agent based and discrete event (AB-DE), that handles volunteer task and location assignments, as well as workload. Using data analysis from the surveys, we also introduce a group conflict variable within the simulation model. We evaluate the impact of different management decisions on unmet community needs, as well as on volunteer satisfaction and turnover intentions from the organization. This study uses a numerical example based on the survey data. Considering the scenario in which disaster volunteer managers do not assign heavy workload to disaster volunteers, the results of this study suggest that as a surplus of available volunteers’ increases, the overall satisfaction increases while the turnover intention decreases due to dissatisfaction with a non-essential workload as well as from group conflict. In contrast, when the number of volunteers is less than what is needed, disaster volunteers’ satisfaction and turnover intentions were not affected even if there is high group conflict due to the positive effect of the workload that offsets the negative impact of the group conflict.

The main focus of the dissertation is to develop decision-making support tools that address nonlinearity and uncertainty appearing in real-world applications via mixed integer programming (MIP) approaches. When making decisions under uncertainty, knowing the accurate probability distributions of the uncertain parameters can help us predict their future realization, which in turn helps to make better decisions. In practice, however, it is oftentimes hard to estimate such a distribution precisely. As a consequence, if the estimated distribution is biased, the decisions thus made can end up with disappointing outcomes. To address this issue, we model uncertainty in the decision-making process through a distributionally robust optimization (DRO) approach, which aims to find a solution that hedges against the worst-case distribution within a pre-defined ambiguity set, i.e., a collection of probability distributions that share some distributional and/or statistical characteristics in common. The role of the ambiguity set is crucial as it affects both solution quality and computational tractability of the DRO model. In this dissertation, we tailor the ambiguity sets based on the available historical data in healthcare operations and energy systems, and derive efficient solution approaches for the DRO models via MIP approaches. Through extensive numerical studies, we show that the DRO solutions yield better out-of-sample performance, and the computational performance of the proposed MIP approaches is encouraging. Finally, we provide some managerial insights into the operations of healthcare and energy systems.

The issue considered in this research involves a customer order scheduling problem examined in the case of a retailer delivering orders for online sales that take place in multiple marketplaces. In this setting, the goal of the company is to gain market share, by attaining high levels of customer retention, by registering good buyer reviews to improve conversion rate and to improve search engine results pages performance. Therefore, the goal of the scheduler is to maximize overall customer satisfaction and effectiveness in multiple periods. Customer satisfaction is defined as a factor of number of orders delivered before their due date, the average tardiness of all orders and the maximum tardiness of orders in the system during a period, and how long an order stays in the system on average. The effectiveness is defined by overall costs that dictate the competitiveness of company prices. In the listing phase, to maximize market coverage, the retailer determines which marketplaces the products can be listed on with profit, under the constraints of promised delivery time, shipping cost and resale prices. The optimal supplier and courier are then determined for cost minimization. Under these predetermined conditions, orders are placed, and items arrive to the retailer, a math model searches for optimal schedule of shipments to maximize overall customer satisfaction with the end goal of increased future sales. The results are compared to a priority rule combination.

Motivated by the necessity to reduce GHG emissions by commuting vehicles and improve users’ convenience, this thesis is dedicated to proposing an optimal network and management of Electric Vehicle (EV) charging stations on campus making the most of the zero tailpipe emissions of EVs. The problem has been decomposed with identified critical components to construct a basic Mixed Integer Programming (MIP) model maximizing the convenience benefits and minimizing the construction costs. Moreover, an expanded model has been proposed in accordance with another sub-objective of gaining greater environmental benefits. Two models are solved by CPLEX in Python with necessary inputs from several sources. Last but not least, the validity of the models has been verified by linearized relaxation, sensitivity analysis, and scenario analysis, which prove the enormous applicability and capability of two models.

The airline industry has a long lasting history of using operations research for complex problems like crew scheduling, crew pairing, and aircraft tail assignment. However, the use of the optimization and operations research on crew vacation planning is not widespread. One of the most popular ways of assigning vacations currently is to let crew members bid for vacations using a heuristic preferential bidding system (PBS). This report will overview the existing problems in the crew vacation allocation domain. Then, it will introduce and compare an optimization based vacation allocation algorithm, an improved heuristic PBS model, and the original heuristic PBS model. Models will be compared using three performance measures as the number of unassigned vacation blocks, the number of crew members without any assigned vacation blocks, and the rank order of the preferences that are awarded to the crew members. This report also conducts a sensitivity analysis for the improved PBS model using the same performance measures

Regression analysis fits predictive models to data on a response variable and corresponding values for a set of explanatory variables. Often data on the explanatory variables come at a cost from commercial databases, so the available budget may limit which ones are used in the final model. In this dissertation, two budget-constrained regression models are proposed for continuous and categorical variables respectively using Mixed Integer Nonlinear Programming (MINLP) to choose the explanatory variables to be included in solutions. First, we propose a budget-constrained linear regression model for continuous response variables. Properties such as solvability and global optimality of the proposed MINLP are established, and a data transformation is shown to signicantly reduce needed big-Ms. Illustrative computational results on realistic retail store data sets indicate that the proposed MINLP outperforms the statistical software outputs in optimizing the objective function under a limit on the number of explanatory variables selected. Also our proposed MINLP is shown to be capable of selecting the optimal combination of explanatory variables under a budget limit covering cost of acquiring data sets. A budget-constrained and or count-constrained logistic regression MINLP model is also proposed for categorical response variables limited to two possible discrete values. Alternative transformations to reduce needed big-Ms are included to speed up the solving process. Computational results on realistic data sets indicate that the proposed optimization model is able to select the best choice for an exact number of explanatory variables in a modest amount of time, and these results frequently outperform standard heuristic methods in terms of minimizing the negative log-likelihood function. Results also show that the method can compute the best choice of explanatory variables affordable within a given budget. Further study adjusting the objective function to minimize the Bayesian Information Criterion BIC value instead of negative log-likelihood function proves that the new optimization model can also reduce the risk of overfitting by introducing a penalty term to the objective function which grows with the number of parameters. Finally we present two refinements in our proposed MINLP models with emphasis on multiple linear regression to speed branch and bound (B&B) convergence and extend the size range of instances that can be solved exactly. One adds cutting planes to the formulation, and the second develops warm start methods for computing a good starting solution. Extensive computational results indicate that our two proposed refinements significantly reduce the time for solving the budget constrained multiple linear regression model using a B&B algorithm, especially for larger data sets. The dissertation concludes with a summary of main contributions and suggestions for extensions of all elements of the work in future research.

Mass electrification of the residential and commercial heating sector using heat pumps and thermal energy storage is a crucial step towards the development and operation of smart grids. An aggregation of heat pumps can provide an alternate source of frequency regulation by generating flexibility on the demand side as opposed to inefficient natural gas generators that are a source of supply side flexibility. This in turn can facilitate greater incorporation of power generated from clean but intermittent sources of energy such as wind and solar. To this end, a hierarchical control scheme is introduced that will enable an aggregator to tap into the inherent flexibility associated with a portfolio of variable speed heat pump/thermal storage subsystems. This work concentrates on the development of a model based predictive controller operating on the subsystem level and its integration into the global control architecture. Additionally, the value of formulating the performance cost optimization function and the system dynamics equation as a mixed integer program is explored. The aforementioned formulation facilitates the use of simplified, yet comprehensive, dynamic heat pump performance models and at the same time addresses the problem of heat pump operation in the compressor dead-band range. The simulations also highlight the power-tracking functionality of the developed controller when it is integrated with higher level controllers in the hierarchical control scheme. Index Terns: Variable Speed Heat Pump, Thermal Energy Storage, Frequency Regulation, Economic Model Predictive Control, Mixed Integer Programming

This thesis uses a mixed integer program to minimize the transport and storage cost of delivering spent microbial biomass (SMB), a bio-coproduct resulting from the production of 1,3-propanediol, to farm fields as a soil amendment and fertilizer substitute. The case study examines focuses on a bioprocessing facility and corn production in East Tennessee. The results indicate on-farm storage of SMB minimizes transport and storage costs of the material. A one percent decrease in the moisture content of SMB results in less than five percent decrease in the total transport and storage costs. Future research should investigate farmers' willingness to adopt the practice, cost sharing design, and to apply SMB to other crop production.

Obtaining upper and lower bounds on the optimal value of a stochastic integer program can require solution of multiple-scenario problems, which are computationally expensive or intractable using off-the-shelf integer-programming software. Additionally, optimal solutions to a two-stage problem whose second stage spans long time horizons may be optimistic, due to the model's inappropriate ability to plan for future periods which are not known in practice. To that end, we present a framework for optimizing system design in the face of a restricted class of policies governing system operation, which aim to model realistic operation. This leads to a natural decomposition of the problem yielding upper and lower bounds which we can compute quickly. We illustrate these ideas using a model that seeks to design and operate a microgrid to support a forward operating base. Here, designing the microgrid includes specifying the number and type of diesel generators, PV systems, and batteries while operating the grid involves dispatching these assets to satisfy load at minimum cost. We extend our approach to solve the same problem under load and photovoltaic uncertainty, and propose a method to generate appropriately correlated scenarios by simulating building occupancy via a bottom-up approach, then using the occupancy levels to inform environmental control unit loads on the base. Finally, in a separate line of work, we optimize the design of the strata for a stratified sampling estimator to reduce variance. We extend this method to the multivariate setting by optimizing the strata for a nonuniform Latin hypercube estimator. We then present empirical results that show that our method reduces the variance of the estimator, compared to one using equal-probability strata.

This dissertation presents optimization models to aid with the sustainable design and management of biopower (biomass cofiring) supply chains. We address three main challenges associated with today’s biopower projects: i) high cost of biomass collection, storage and delivery, ii) inefficiency of the mechanisms used to incentivize biomass usage for generating electricity, and iii) lack of clear understanding about the trade-offs between economic and environmental impacts of biopower supply chains. In order to address the high cost of delivering biomass, we present a novel mixed integer nonlinear program that integrates production and transportation decisions at power plants. Proposed model captures the loss in process efficiencies from using biomass, in-vestment and operational costs associated with cofiring, and savings due to production tax credit (PTC), a major governmental incentive to support biopower. We develop a La-grangian relaxation approach to provide upper bounds, and two linear approximations to provide lower bounds for the problem. An important finding is that the one-size-fits-all approach of PTC is not effective in motivating plants to utilize biomass and there is a need for sophisticated incentive schemes. In order to address the second issue, we propose alter-natives for the existing PTC incentive. The proposed flexible alternatives are functions of plant capacity and biomass cofiring ratio. We use a resource allocation framework to model and analyze the profit-earning potentials and fairness of the proposed incentive schemes. Finally, in order to address the last challenge, we propose a stochastic biobjective optimiza-tion model to analyze the economic and environmental impacts of biopower supply chains. The economic objective function maximizes the potential profits in the supply chain and the environmental objective function minimizes the life cycle greenhouse gasses (GHG). We use a life cycle assessment (LCA) approach to derive the emission factors for this objective function. We capture uncertainties of biomass quality and supply via the use of chance constraints. The results of this dissertation work are useful for electric utility companies and policy makers. Utility companies can use the proposed models to identify ways to improve biopower production, have better environmental performance, and make use of the existing incentives. Policy makers would gain insights on designing incentive schemes for a more efficient utilization of biomass and a fairer distribution of tax-payers money.

The importance of the transmission network for supplying electricity demand is undeniable, and Transmission Expansion Planning (TEP) studies is key for a reliable power system. Due to increasing sources of uncertainty such as more intermittent energy resources, mobile and controllable demands, and fast technology improvements for PVs and energy storage devices, the need for using systematic ways for solving this complex problem is increased. One of the main barriers for deploying optimization-based TEP studies is computationally intractability, which is the main motivation for this research. The aim of this work is to investigate the computational challenges associated with systematic TEP studies for large-scale problems, and develop algorithms to improve computational performance. In the first step, we investigate the impact of adding security constraints (as NERC standard requirement) into TEP optimization problem, and develop the Variable Contingency List (VCL) algorithm to pre-screen security constraints to only add those that may affect the feasible region. It significantly decreases the size of the problem compared to considering all security constraints. Then, we evaluate the impact of the size of candidate lines list (number of binary variables) on TEP, and developed a heuristic algorithm to decrease the size of this list. In the next step, we integrate uncertainties into the TEP optimization problem and formulate the problem as a two-stage stochastic program. Adding uncertainties increases the size of the problem significantly. It leads us to develop a three-level filter that introduces important scenario identification index (ISII) and similar scenario elimination (SSE) technique to decrease the number of security constraints in stochastic TEP in a systematic and tractable way. We then investigate the scalability of the stochastic TEP formulation. We develop a configurable decomposition framework that allows us to decompose the original problem into subproblems that can be solved independently and in parallel. This framework can benefit from using both progressive hedging (PH) and Benders decomposition (BD) algorithms to decompose and parallelize a large-scale problem both vertically and horizontally. We have also developed a bundling algorithm that improves the performance of PH algorithm and the overall performance of the framework. We have implemented our work on a reduced ERCOT network with more than 3000 buses to demonstrate the practicality of the proposed method in this work for large-scale problems.

Given the increasing popularity of local foods and the desire to reduce shipping costs and carbon footprint, Tennessee-based dairy product producers are showing interest in sourcing fluid milk locally. Based on dairy farmer surveys, discussions with industry leaders, shipping distances, and transportation costs estimates, a mixed integer linear programming model is used to determine the optimal location of an in-state milk condensing plant. The objective is to minimize the total transportation costs of shipments of fluid milk from farms to the condensing plant plus the transportation cost of shipments of condensing plant products to further in-state processing. Twelve scenarios of the model were analyzed with Rutherford County consistently being found as the optimal, transportation cost-minimizing location.

Abstract: Low dose rate (LDR) brachytherapy is a minimally invasive form of radiation therapy, used to treat prostate cancer, and it involves permanent implantation of radioactive sources (seeds) inside of the prostate gland. Treatment planning in brachytherapy involves a decision making process for the placement of radioactive sources in order to deliver an effective dose of radiation to cancerous tissue in the prostate while sparing the surrounding healthy tissue. Such a decision making process can be modeled as a mixed-integer linear programming (MILP) problem. In this thesis, we initially introduce a novel MILP optimization model for interstitial LDR prostate brachytherapy that attempts to mimic the qualities of treatment plans produced manually by expert planners. Our approach involves incorporating a unique set of clinically important constraints, called spatial constraints, into our models. These constraints are combined with several proposed data processing techniques, and collectively these methods enable us to capture the fundamental aspects of the planning style present at a local cancer clinic. While this represents the primary clinical challenge to overcome in this thesis, the engineering challenge involves producing clinically acceptable treatment plans in a matter of seconds to minutes with our automated planning system. Such a goal initially presents itself to be a difficult one to accomplish, as our large-scale models exhibit tendencies of intractability while using high-resolution data sets. We introduce pseudo high-resolution data sets and constraint-violating feasibility-based modelling in order to overcome these issues related to solution performance of our model. Through the synergistic effects of these two modelling techniques, we demonstrate the ability to produce treatment plans with solution times suitable for pre-operative and intra-operative planning, which constitute the two main forms of treatment planning in LDR brachytherapy. Specifically speaking, our solution times range from less than a minute to roughly five minutes for prostates of varying shapes and sizes (volume-wise, the tested prostates range from 20.4 cc to 63.1 cc). Finally, with the help of a radiation oncologist, we verify the clinical acceptability of our automated plans through a pilot study involving data from twenty patients. Therefore, through this study we also confirm the clinical suitability of the several concepts introduced in this thesis; namely, these are spatial constraints, pseudo high-resolution data sets and constraint-violating feasibility-based modelling. Following these results, we consequently identify three main areas of improvements for our automated system: avoiding placement of strands outside of the prostate and seeds in the bladder, as well as lowering dose to the organs-at-risk. Moving forward, we suggest branching out and examining the clinical performance of our automated planning system in intra-operative planning, as the results obtained in thesis reflect the performance of our approach within pre-operative planning. In summary, through this thesis we demonstrate the ability to uniquely capture the planning style of expert planners at a local clinic in a fraction of the time that it currently takes expert planners to produce treatment plans.

Taxi ride sharing is one of the most promising solutions to urban transportation issues, such as traffic congestion, gas insufficiency, air pollution, limited parking space and unaffordable parking charge, taxi shortage in peak hours, etc. Despite the enormous demands of such service and its exciting social benefits, there is still a shortage of successful automated operations of ride sharing systems around the world. Two of the bottlenecks are: (1) on-time delivery is not guaranteed; (2) matching and scheduling drivers and passengers is a NP-hard problem, and optimization based models do not support real time scheduling on large scale systems. This thesis tackles the challenge of timely delivery of passengers in a large scale ride sharing system, where there are hundreds and even thousands of passengers and drivers to be matched and scheduled. We first formulate it as a mixed linear integer programming problem, which obtains the theoretical optimum, but at an unacceptable runtime cost even for a small system. We then introduce our greedy agglomeration and Monte Carlo simulation based algorithm. The effectiveness and efficiency of the new algorithm are fully evaluated: (1) Comparison with solving optimization model is conducted on small ride sharing cases. The greedy agglomerative algorithm can always achieve the same optimal solutions that the optimization model offers, but is three orders of magnitude faster. (2) Case studies on large scale systems are also included to validate its performance. (3) The proposed greedy algorithm is straightforward for parallelization to utilize distributed computing resources. (4) Two important details are discussed: selection of the number of Monte Carlo simulations and proper calculation of delays in the greedy agglomeration step. We find out from experiments that the sufficient number of simulations to achieve a “sufficiently optimal solution” is linearly related to the product of the number of vehicles and the number of passengers. Experiments also show that enabling margins and counting early delivery as negative delay leads to more accurate solutions than counting delay only.

An integrated production and distribution planning problem was modeled, inspired by a consumer goods manufacturing company specialized in food processing. A specific mixed integer linear programming formulation was developed and it's performance tested with an industry sized data set(excess of 150 thousand variables and 100 thousand constraints). A generous use of integer variables instead of continuous variables, considered typically harder to solve, was accommodated to provide realistic solutions and infeasibility issues were addressed using penalty variables. Feasible solutions, reasonably close to optimality were obtained by leveraging powerful off the shelf optimization solvers instead of building decomposition techniques or heuristics in the formulation. Potential logistics cost savings in the range of 7 to 15 % were demonstrated using multiple trials. A framework for automating a large portion of the optimization process was built using a combination of tools such as Gurobi,R and excel spreadsheets. A future road map for potential improvements in the model and the automation framework were also summarized.

Medical residency is a requirement for medical professionals to practice medicine. Residency programs in internal medicine lasts 3 years and require residents to undergo a series of supervised rotations in elective, inpatient, and ambulatory units. Typically a team of chief residents develops a yearly rotational schedule that assigns residents to various departments for each week of the year, and for each day of the week. Scheduling resident rotations is complex as it needs to consider various academic, managerial, and legal restrictions while ensuring that the resulting schedules facilitate patient care and are balanced in terms of resident educational experience, workload, and resident satisfaction. This study proposes: (1) a multi-objective optimization approach for generating year-long resident rotation schedules; (2) an AHP (Analytical Hierarchy Process) model to compare schedules across multiple criteria and facilitate their adoption and implementation; (3) a methodology for studying the interaction between weekly and daily resident rotation schedules.; (4) an optimization based approach for ensuring continuity of care at outpatient clinics; and, (5) a methodology for evaluating resident assignment policies to outpatient clinics.

The United States, Great Britain, Denmark, Canada and many other countries have accepted home visitation (HV) as a promising strategy for interventions for infants after births and for their mothers. Prior HV studies have focused on theoretical foundations, evaluations of programs, cost/benefit analysis and cost estimation by using hospital/payer/insurance data to prove its effectiveness and high cost. As governments and private organizations continue to fund HVs, it is an opportune time to develop and formulate operations research (OR) models of HV coverage, quality and cost so they might be used in program implementation as done for adult home healthcare (HHC) and home care (HC). This dissertation introduces a new modeling approach and proposes a solution methodology which helps to determine the schedules of follow-up nursing care providers (NCP) to visit discharged patients in order to minimize total follow-up cost at the planning and operational level, and to improve the quality of care. The model improves the quality of treatment of infants and mothers during pregnancy, after birth and discharge from the hospital by maximizing the quality of assignment of the right NCP with the right skill, nurse type and years of experience to the right patient with the specific health need. The modeling approach is based on a mixed-interger programming (MIP) formulation that represents the dynamics of the system comprising aspects such as visit schedules and total program’s cost while satisfying a variety of requirements modeled as constraints. The model is tested and validated with real life data. Computational results for the formulation for real life instances of the problem with the Nurse Family Partnership Program (NFP) obtained using IBM CPLEX optimization Studio version 12.6.1 are presented. The intent is to enhance the administrative and deployment process of HV programs, minimize risks, allow planners to explore the best scenarios under different conditions related to cost, treatment and coverage requirements, and highlight the best course of action when assigning NCPs to clients. Results show significant cost savings and enhanced quality treatment in several cases studied and tested. Finally, the study identifies and presents fertile avenues for future research for this field.

In healthcare delivery systems, proper coordination between patient visits and the health care resources they rely upon is an area in which important new planning capabilities are very valuable to provide greater value to all stakeholders. Managing supply and demand, while providing an appropriate service level for various types of care and patients of differing levels of urgency is a difficult task to achieve. This task becomes even more complex when planning for (i) stochastic demand, (ii) multi-class customers (i.e., patients with different urgency levels), and (iii) multiple services/visit types (which includes multi-visit itineraries of clinical care and/or clinical research visits that are delivered according to research protocols). These complications in the demand stream require service waiting times and itineraries of visits that may span multiple days/weeks and may utilize many different resources in the organization (each resource with at least one specific service being provided). The key objective of this dissertation is to develop planning models for the optimization of capacity allocation while considering the coordination between resources and patient demand in these multi-class stochastic queueing networks in order to meet the service/access levels required for each patient class. This control can be managed by allocating resources to specific patient types/visits over a planning horizon. In this dissertation, we control key performance metrics that relate to patient access management and resource capacity planning in various healthcare settings with chapters devoted to outpatient services, and clinical research units. The methods developed forecast and optimize (1) the access to care (in a medical specialty) for each patient class, (2) the Time to First Available Visit for clinical research participants enrolling in clinical trials, and (3) the access to downstream resources in an itinerary of care, which we call the itinerary flow time. We also model and control how resources are managed, by incorporating (4) workload/utilization metrics, as well as (5) blocking/overtime probabilities of those resources. We control how to allocate resource capacity along the various multi-visit resource requirements of the patient itineraries, and by doing so, we capture the key correlations between patient access, and resource allocation, coordination, and utilization.

This dissertation is concerned with the design of branch-and-cut algorithms for a variety of nonconvex nonlinear problems pertaining to power systems operations and planning. By understanding the structure of specific problems, we can leverage powerful commercial optimization solvers designed for convex optimization and mixed-integer programs. The bulk of the work concerns the Alternating Current Optimal Power Flow (ACOPF) problem. The ACOPF problem is to find a minimum cost generation dispatch that will yield flows that can satisfy demand as well as various engineering constraints. A standard formulation can be posed as a nonconvex Quadratically Constrained Quadratic Program with complex variables. We develop a novel spatial branch-and-bound algorithm for generic nonconvex QCQP with bounded complex variables that relies on a semidefinite programming (SDP) relaxation strengthened with linear valid inequalities. ACOPF-specific domain reduction or bound tightening techniques are also introduced to improve the algorithm's convergence rate. We also introduce second-order conic valid inequalities so that any SDP can be outer-approximated with conic quadratic cuts and test the technique on ACOPF. Another application is the incorporation of convex quadratic costs in unit commitment, which is a multi-period electric generation scheduling problem. We show that conic reformulation can both theoretically and practically improve performance on this mixed-integer nonlinear problem. We conclude with methods for approximating a mixed-integer convex exponential constraint. Applications include capital budgeting, the system reliability redundancy problem, and feature subset selection for logistic regression.

In workforce allocation, gaps between workers available and workers needed at various operations result in production delays and a loss of profitability for the manufacturer. These gaps can be reduced by overtime assignments of workers from other shifts. However, for a multiple shift planning horizon, a mix of cross-training of workers over different tasks along with overtime assignments may be a good strategy. This work develops an industry-motivated cross-training framework that identifies workers and operations for normal, overtime, and training assignments. A mixed integer programming model that integrates all three assignment tasks is formulated and solved. The production scenario consists of skill level based qualifications for workers that need to be assigned to operations in every shift. Factory floor conditions such as limits on worker levels at specific operations, scheduling restrictions and worker training protocols are also considered. The data taken into account includes parameters such as man-machine ratio, tool count, and limits on skill qualifications for workers. The output of the model provides a cross-training schedule and an assignment schedule that can be used by floor managers on a shift-by-shift basis. The MIP model is implemented in C# using the .NET framework and the IBM ILOG CPLEX Optimizer.

This dissertation focuses on specific aspects of the technical design and operation of a `smart' distribution system incorporating new technology in the design process. The main purpose of this dissertation is to propose new algorithms in order to achieve a more reliable and economic distribution system. First, a general approach based on Mixed Integer Programming (MIP) is proposed to formulate the reconfiguration problem for a radial/weakly meshed distribution network or restoration following a fault. Two objectives considered in this study are to minimize the active power loss, and to minimize the number of switching operations with respect to operational constraints, such as power balance, line ow limits, voltage limit, and radiality of the network. The latter is the most challenging issue in solving the problem by MIP. A novel approach based on Depth-First Search (DFS) algorithm is implemented to avoid cycles and loops in the system. Due to insufficient measurements and high penetration of controllable loads and renewable resources, reconfiguration with deterministic optimization may not lead to an optimal/feasible result. Therefore, two different methods are proposed to solve the reconfiguration problem in presence of load uncertainty. Second, a new pricing algorithm for residential load participation in demand response program is proposed. The objective is to reduce the cost to the utility company while mitigating the impact on customer satisfaction. This is an iterative approach in which residents and energy supplier exchange information on consumption and price. The prices as well as appliance schedule for the residential customers will be achieved at the point of convergence. As an important contribution of this work, distribution network constraints such as voltage limits, equipment capacity limits, and phase balance constraints are considered in the pricing algorithm. Similar to the locational marginal price (LMP) at the transmission level, different prices for distribution nodes will be obtained. Primary consideration in the proposed approach, and frequently ignored in the literature, is to avoid overly sophisticated decision-making at the customer level. Most customers will have limited capacity or need for elaborate scheduling where actual energy cost savings will be modest.

Branch and bound based algorithms are used by many commercial mixed integer programming solvers for solving complex optimization problems. In a branch and bound based method, a feasible region is divided into smaller sub-problems. This is called branching and various branching strategies have been developed to improve the performance of branch and bound based algorithms. However, their performance has primarily been studied on general mixed integer programs. Thus, in the first phase of this thesis, we study the performance of these branching strategies on a specific, structured mixed integer program, the capacitated multi-commodity fixed charge network flow (MCFCNF) problem. We also develop new branching strategies using the pool of available feasible solutions for solving the mixed integer program for MCFCNF. We present the computational results for testing various branching rules with four different variants of the network design problem studied with SCIP and GLPK mathematical solvers.

Amusement parks are a huge business. Guest experiences determine the success or failure for an amusement park. This report suggests an approach to improve guest experience by managing guest flow. The guest happiness optimization problem is formulated into a visitor routing management model. The constraints for this model include attraction attributes and guest behavior. To build the attraction constraints, their information is first gathered from internet, field studies and surveys, and then input into simulation software. Constraints on guest behavior are set up with a literature study and a guest survey. A two phase heuristic is developed to solve this problem with constraints. Candidate routes are generated with a route construction algorithm in the first phase. Visitor distribution and selection on these candidate routes are determined in the second phase using a mixed integer programming solver. Visitor routes are then recommended to the park’s operator side, for them to distribute to guests visiting on their vacations. Data from Disney Epcot are collected and applied in the case study to implement the methodology in this report. Attraction operations capability is maintained at the current level with no additional cost for the project, while guest satisfaction is improved by ensuring the number and type of attractions they visit. In addition, average waiting time for visitors is reduced by at least 70% in the recommended operation strategy.

Home healthcare has been a growing sector of the economy over the last three decades with roughly 23,000 companies now doing business in the U.S. producing over $56 billion in combined annual revenue. As a highly fragmented market, profitability of individual companies depends on effective management and efficient operations. This dissertation aims at reducing costs and improving productivity for home healthcare companies. The first part of the research involves the development of a new formulation for the therapist routing and scheduling problem as a mixed integer program. Given the time horizon, a set of therapists and a group of geographically dispersed patients, the objective of the model is to minimize the total cost of providing service by assigning patients to therapists while satisfying a host of constraints concerning time windows, labor regulations and contractual agreements. This problem is NP-hard and proved to be beyond the capability of commercial solvers like CPLEX. To obtain good solutions quickly, three approaches have been developed that include two heuristics and a decomposition algorithm. The first approach is a parallel GRASP that assigns patients to multiple routes in a series of rounds. During the first round, the procedure optimizes the patient distribution among the available therapists, thus trying to reach a local optimum with respect to the combined cost of the routes. Computational results show that the parallel GRASP can reduce costs by 14.54% on average for real datasets, and works efficiently on randomly generated datasets. The second approach is a sequential GRASP that constructs one route at a time. When building a route, the procedure tracks the amount of time used by the therapists each day, giving it tight control over the treatment time distribution within a route. Computational results show that the sequential GRASP provides a cost savings of 18.09% on average for the same real datasets, but gets much better solutions with significantly less CPU for the same randomly generated datasets. The third approach is a branch and price algorithm, which is designed to find exact optima within an acceptable amount of time. By decomposing the full problem by therapist, we obtain a series of constrained shortest path problems, which, by comparison are relatively easy to solve. Computational results show that, this approach is not efficient here because: 1) convergence of Dantzig-Wolfe decomposition is not fast enough; and 2) subproblem is strongly NP-hard and cannot be solved efficiently. The last part of this research studies a simpler case in which all patients have fixed appointment times. The model takes the form of a large-scale mixed-integer program, and has different computational complexity when different features are considered. With the piece-wise linear cost structure, the problem is strongly NP-hard and not solvable with CPLEX for instances of realistic size. Subsequently, a rolling horizon algorithm, two relaxed mixed-integer models and a branch-and-price algorithm were developed. Computational results show that, both the rolling horizon algorithm and two relaxed mixed-integer models can solve the problem efficiently; the branch-and-price algorithm, however, is not practical again because the convergence of Dantzig-Wolfe decomposition is slow even when stabilization techniques are applied.

Abstract: Scientific and technology advances in electrical engineering and increasing demand for electrical energy have led to extensive research in power industry and formation of new markets for electrical energy. These developments have brought about interest and demand for power. In response to the increase in demand, the research focus is on upgrading the current infrastructure to higher capacity power transmission networks. Nevertheless, building new generating stations and transmission facilities is precluded by some environmental, social, and economic regulations. Therefore, the only feasible solution to deal with the energy requirement is to increase and optimize the capacity of existing power generation and transmission equipment. The current thesis proposes an optimization method based on the Mixed Integer Linear Programming technique to maximize the usage of the capacity of power transmission facilities. The method employs weather-based dynamic thermal ratings, costs of power generation, and power generation constraints such as cost of start-up/shut-down and generation ramp up/down limits. The method's accuracy is increased by incorporating a spatially resolved, high-resolution thermal model of the transmission system. By utilizing this extension, the thermal limits and temperature-dependent losses of the system are identified and dynamically used in calculations. Load forecasting is used in dispatch centers to improve generator scheduling and minimize the costs of the entire system. The multi-snapshot characteristic of the model, which is proposed in this thesis, provides the model with the ability to consider the load and meteorological data's forecasts, further improving the model's accuracy. The performance of the model is tested by simulating a year of data from Newfoundland and Labrador Hydro power generation and transmission system, and for the weather conditions the North American Regional Reanalysis (NARR) historical dataset is used. The simulation results show that the overall costs of the system can be reduced by incorporating dynamic capacity of transmission lines and optimizing the power generation and transmission. The temperature and resistance variability of the transmission network is also analyzed and the results are provided.

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.

We consider inventory control problems with stochastic demand in which a specific service level must be met. We assume that demand and cost distributions over the planning horizon are finite, discrete and non-stationary. We formulate this problem as a chance-constrained program, whose deterministic equivalent is a large-scale mixed-integer program (MIP). We study the structure of the formulations and develop methods for solving them efficiently. We add mixing cuts to tighten these formulations and propose new valid inequalities. We also decompose these large-scale mixed integer programs using Benders decomposition technique and branch-and-price-and-cut method, both of which could incorporate mixing cuts to improve their performance.

This research examines a complex surgical case scheduling problem for a publicly-funded hospital in the Midwest United States. Publicly-funded hospitals are typically under tight budget constraints and these hospitals strive to maximize the utilization of their resources such as beds, staff, equipment, operating rooms, etc. These resources are relatively fixed for a publically funded hospital. A manual scheduling approach followed by this hospital does not guarantee optimal solutions and consequently has led to large variation in the utilization of resources. This real-world problem is described in this research as a multi-day, multi-resource, and patient-priority-based surgical case scheduling problem with the objective of maximizing the weighted sum of surgical case priorities. The surgical case scheduling problem herein is conceptualized as an unequal-sized multi-dimensional multi-bin dual bin-packing problem. A mixed integer programming model is proposed to generate implementable schedules. For each surgical case, the solution obtained will provide detail information about the start time and day of the surgery, the operating room to perform the surgery, and the surgeon's name. Resource availability, patient priorities, and surgical time of the surgeons are key features included in the model. However, the combinatorial nature of this problem limited the MIP model to solving only small problem instances. Consequently, an efficient First Fit Decreasing based heuristic is proposed and its performance is benchmarked against the MIP model. The benefit of pooling surgical cases over the commonly used First Come First Serve scheduling policy is also demonstrated. Results quantify the extent to which pooling can increase the number of high priority surgeries performed.

The polyhedral structure of the convex hull of the 0-1 mixed knapsack polytope defined by a knapsack inequality with continuous and binary variables with upper bounds is investigated. This polytope arises as subpolytope of more general mixed integer problems such as network flow problems, facility location problems, and lotsizing problems. Two sets of valid inequalities for the polytope are developed. We derive the first set of valid inequalities by adding a new subset of variables to the flow cover inequalities. We show that, under some conditions, this set is facet defining. Computational results show the effectiveness of these inequalities.The second set of valid inequality is generated by sequence independent lifting of the flow cover inequalities. We show that computing exact lifting coefficients is NP-hard. As a result, an approximate lifting procedure is developed. We give computational results that show the effectiveness of the valid inequalities and the lifting procedure.

There is currently a national push to create a smarter electric grid; introducing new technologies that will create a more controllable and flexible grid is part of the smart grid concept and integral to its success. The full control of transmission assets are not currently built into electric energy dispatch optimization models. Optimal transmission switching is a straightforward way to leverage grid controllability: to make better use of the existing system and meet growing demand with existing infrastructure. Previous research has shown that transmission switching as a corrective mechanism can help relieve line overloading, voltage violations, etc. However, there has been limited focus on the use of transmission switching as a means to improve the economic efficiency of the network by incorporating the control of transmission assets into the overall economic dispatch problem. This research discusses the ways that the modeling of flexible transmission assets can benefit the multi-trillion dollar electric industry. It presents and analyzes novel formulations by which the operator can incorporate this flexibility into the economic dispatch formulation. This research focuses on modeling transmission assets so that they can be temporarily taken out of service, i.e., by opening breakers, or kept in service, i.e., by keeping the breakers closed. By incorporating this control into the network optimization problem, this provides the ability for the operator to consider the state of a transmission line as a decision variable instead of treating it as a static asset, which is the current practice today. The possible benefits demonstrated from this research indicate that the benefits to society are substantial. On the contrary, the benefits to individual market participants are uncertain; some will benefit and other will not. Consequently, this research also analyzes the impacts that optimal transmission switching may have on market participants as well as the policy implications. Methods to improve the solution time of this difficult problem are discussed as well.

This dissertation focuses on the resource requirements and scheduling problem for logistic systems. We investigate solutions to this problem in two different logistic systems: logistic system of the health care facilities during emergency evacuations and delivery and distribution system of production industries. All hospitals must have an evacuation plan to ensure the safety of patients and prevent the loss of life. However, hospital operators have not been able to quantify how resource availability, the cost of acquiring those resources, and evacuation completion time are related. This research addresses this problem and contributes two methodologies to solve this problem. In the first methodology, we propose a mixed integer programming for identifying resource requirements, as well as the scheduling of these requirements, within a pre-specified period while minimizing cost. Also, we suggest a tailored solution approach that relaxes certain complicating integer constraints in an effort to find feasible, quality solutions. This model assumes that there exists no probabilistic event in the evacuation process of the hospitals. The second proposed methodology accounts for uncertainties in the evacuation process. We present a stochastic model via simulation and employ a simulation-optimization approach to solve the same problem. The resource requirements and scheduling problem is also a critical issue for the companies in the production industry as most of them have limited resources and need to make their tactical and operational plans with the consideration of this issue. As the focus of this dissertation is logistic operations, we consider this problem only for the logistic system of these companies and contribute methodologies to solve this problem. With the use of same structure of the formulation, used in mixed integer programming proposed for the evacuation problem, we propose models to solve this problem for two different production environments: when there is no limitation on resources and when there are limited resources. The models proposed for the restricted production environment also enables the companies to select the most profitable set of customers. We also suggest tailored solution approaches for each model with the use of the same techniques used for evacuation planning problem.

Many decision-making problems in practice can be formulated as Mixed Integer Programming (MIP) problems, which are NP-hard in their general form. Over the past few decades, an enormous amount of research has been carried out to develop the theory and algorithms for solving MIP problems. Valid inequalities are a crucial part of these developments since they can be added to the MIP problem as cutting planes to tighten the feasible region of its linear programming relaxation toward the convex hull of its MIP solutions. Mixed Integer Rounding (MIR) is a fundamental approach to generating cutting planes for general MIP problems. Recently, MIR has received special attention from several researchers. MIR inequalities are obtained from facets of certain simple mixed integer sets (MIR facets). A significant contribution in this context has been the work by Dash and Gunluk (2006) who introduced the 2-step MIR inequalities. The work of Dash and Günlük is also one of the recent advancements in the area of valid inequalities related to Gomory's group problems. These problems are of special significance in the context of MIP because facets of their corresponding polyhedra are sources for generating valid inequalities for MIP problems. In this dissertation, we generalize the concept of MIR valid inequalities. Based on this generalization, we develop new families of MIR inequalities for general MIP problems and show that they define (new) facets for the finite and infinite group polyhedra, and hence are potentially strong cuts. More specifically, the contributions of this research are as follows: First, we show that MIR facets are not limited to 1-step or 2-step facets, but for any positive integer n, n facets of a certain (n+1)-dimensional mixed integer set can be obtained through a process which includes n consecutive applications of MIR. The last of these facets is of special importance and we call it the n-step MIR facet. As a result, we generate an infinite number of MIR facets (one for each n), which we then use to generate valid inequalities for MIP problems. Second, we develop a procedure which, for any n, uses the n-step MIR facet to generate a family of valid inequalities for the feasible set of a general MIP constraint. We refer to these as the n-step MIR inequalities. The well-known Gomory Mixed Integer Cut and the 2-step MIR inequality of Dash and Gunluk are simply the first two families corresponding to n=1,2, respectively. The n-step MIR inequalities are easily produced using closed-form periodic functions, which we call the n-step MIR functions. None of these functions dominates the other on its whole period. Third, we establish a significant connection between the n-step MIR functions and facets of Gomory's group polyhedra. We prove that for any n, the n-step MIR inequalities define new families of facets for the finite and the infinite group polyhedra, and hence are potentially strong cuts. Many of these facets are new facets that have not been introduced in the literature before.

In this dissertation we focus on the development of exact and inexact (i.e., heuristic) algorithms for the q-mode problem. The exact algorithms are based on integer programming models for the q-mode problem. We discuss the theoretical properties of an existing IP model and propose several enhancements. We also propose a new IP model for the problem and investigate these models through a comprehensive computational experiment. The experiment reveals that, in practice, the IP models are more effective for instances with strong natural clusters but less effective for instances containing weak natural clusters. We also propose exact algorithms based on the Benders decomposition for one of the IP models. The heuristic algorithm that we propose for the q-mode problem is a local improvement algorithm that is based on a very large scale neighborhood structure. We evaluate the algorithm through a computational experiment and empirically demonstrate its effectiveness.

The facility layout problem (FLP) is one of the most important and challenging problems in both the operations research and industrial engineering research domains. In FLP research, the continuous-representation-based FLP can consider all possible all-rectangular department solutions. Given this flexibility, this representation has become the representation of-choice in FLP research. Much of this research is based on a methodology of mixed integer programming (MIP) models. However, these MIP-FLP models can only solve problems with a limited number of departments to optimality due to a large number of binary variables used in the models to prevent departments from overlapping. Our research centers around the sequence-pair representation, a concept that originated in the Very Large Scale Integration (VLSI) design literature. We show that an exhaustive search of the sequence-pair solution space will result in finding the optimal layout of the MIP-FLP and that every sequence-pair solution is binary-feasible in the MIP-FLP. Based on this fact, we propose a methodology that combines the sequence-pair and MIP-FLP model to efficiently solve large continuous-representation-based FLPs. Our heuristic approach searches the sequence-pair solution space and then use the sequence-pair representation to simplify and solve the MIPFLP model. Based on this methodology, we systematically study the different aspects of the FLP throughout this dissertation. As the first contribution of this dissertation, we present a genetic algorithm based heuristic, SEQUENCE, that combines the sequence-pair representation and the most recent MIPFLP model to solve the all-rectangular-department continuous-representation-based FLP. Numerical experiments based on different sized test problems from both the literature and industrial applications are provided and the solutions are compared with both the optimal solutions and the solutions from other heuristics to show the effectiveness and efficiency of our heuristic. For eleven data sets from the literature, we provide solutions better than those previously found. For the FLP with fixed departments, many sequence-pairs become infeasible with respect to the fixed department location and dimension restrictions. As our second contribution, to address this difficulty, we present a repair operator to filter the infeasible sequence-pairs with respect to the fixed departments. This repair operator is integrated into SEQUENCE to solve the FLP with fixed departments more efficiently. The effectiveness of combining SEQUENCE and the repair operator for solving the FLP with fixed departments is illustrated through a series of numerical experiments where the SEQUENCE solutions are compared with other heuristics' solutions. The third contribution of this dissertation is to formulate and solve the FLP with an existing aisle structure (FLPAL). In many industrial layout designs, the existing aisle structure must be taken into account. However, there is very little research that has been conducted in this area. We extend our research to further address the FLPAL. We first present an MIP model for the FLPAL (MIP-FLPAL) and run numerical experiments to test the performance of the MIP-FLPAL. These experiments illustrate that the MIP-FLPAL can only solve very limited sized FLPAL problems. Therefore, we present a genetic algorithm based heuristic, SEQUENCE-AL, to combine the sequence-pair representation and MIP-FLPAL to solve larger-sized FLPAL problems. Different sized data sets are solved by SEQUENCE-AL and the solutions are compared with both the optimal solutions and other heuristics' solutions to show the effectiveness of SEQUENCE-AL. The fourth contribution of this dissertation is to formulate and solve the FLP with non-rectangular-shaped departments. Most FLP research focuses on layout design with all rectangular-shaped departments, while in industry there are many FLP applications with non-rectangular-shaped departments. We extend our research to solve the FLP with nonrectangular-shaped departments. We first formulate the FLP with non-rectangular-shaped departments (FLPNR) to a MIP model (MIP-FLPNR), where each non-rectangular department is partitioned into rectangular-shaped sub-departments and the sub-departments from the same department are connected according to the department's orientation. The effect of different factors on the performance of the MIP-FLPNR is explored through a series of numerical tests, which also shows that MIP-FLPNR can only solve limited-sized FLPNR problems. To solve larger-sized FLPNR problems, we present a genetic algorithm based heuristic, SEQUENCE-NR, along with two repair operators based on the mathematical properties of the MIP-FLPNR to solve the larger-sized FLPNR. A series of numerical tests are conducted on SEQUENCE-NR to compare the SEQUENCE-NR solutions with both the optimal solutions and another heuristic's solutions to illustrate the effectiveness of SEQUENCE-NR. As the first systematic research study on a methodology that combines the sequence-pair representation and the MIP-based FLP, this dissertation addresses different types of continuous-representation based facility layout design problems: from block layout design with and without fixed departments to re-layout design with an existing aisle structure, and from layout design with all-rectangular-shaped departments to layout design with arbitrary non-rectangular-shaped departments. For each type of layout design problem, numerical experiments are conducted to illustrate the effectiveness of our specifically designed family of sequence-pair and MIP-based heuristics. As a result, better solutions than those previously found are provided for some widely used data sets from the literature and some new datasets based on both the literature and industrial applications are proposed for the first time. Furthermore, future research that continues to combine the sequence-pair representation and the MIP-FLP model to solve the FLP is also discussed, indicating the richness of this research domain.

Layout design has been studied for more than three decades. It is a very practical problem in that industry has relied, and will continue to rely, on good layout design to reduce production costs and improve facility efficiency. The static facility layout problem (SFLP) is concerned with generating a single block layout with the total flow cost as low as possible. The dynamic facility layout problem (DFLP) is concerned with generating a string of layouts, one for each period in the planning horizon, such that the total discounted flow and department relocation cost is as low as possible. Unless some restrictive assumptions are made, both SFLP and DFLP are very difficult to solve optimally. Therefore, heuristic algorithms are often developed. In this dissertation, we first used directed graphs and simulated annealing to develop a heuristic algorithm for solving mixed-integer-programming (MIP) based SFLP. Next, we took advantage of MIP to enhance our algorithm, making it capable of handling some common requirements in real-world layout design. Then, a new MIP-based DFLP was proposed which suggested that the department relocation costs remain almost the same regardless the area or distance change. Based on the enhanced algorithm for SFLP, a heuristic algorithm for the new DFLP was obtained. The successful development of such an algorithm for DFLP was the ultimate goal of our research. The effectiveness of our algorithms were demonstrated in three ways. First, we compared our solutions with optimal solutions to small SFLPs and DFLPs. Second. we compared our algorithms with other algorithms on a number of SFLPs chosen from the literature. And third. some problems were created to test our algorithm for DFLP. Most of the time, our algorithms for SFLP significantly outperformed others, and our algorithm for the new DFLP obtained reasonably good solutions.