This thesis aims to implement a combination of Linear Programming Column Generation and a Large Neighbourhood Search heuristic to solve scheduling problems. The resulting method is named Integer Programming Column Search (IPCS). For computational evaluation, the IPCS method is applied to the problem Prize-Collecting Job Sequencing with One Common and Multiple Secondary Resources generalised to parallel identical machines. The interest of combining exact procedures with heuristic approaches is quickly growing since scheduling problems have many and complex real-world applications. Most of these problems are NP-hard and therefore very challenging to solve. By using a combination of heuristic strategies and exact procedures, it can be possible to find high-quality solutions to such problems within an acceptable time horizon. The IPCS method uses a greedy integer programming column generating problem introduced in a previous work. This problem is designed to generate columns that are useful in near-optimal integer solutions. A difference to previously introduced method is that we here build a master problem, an Integer Programming Column Search Master (IPCS-Master). This is used to update the dual solution that is provided to the greedy integer programming column generating problem. The computational performance of the IPCS method is evaluated on instances with 60, 70, 80, 90 and 100 jobs. The result shows that the combined design encourage the generation of columns that benefit the search of near-optimal integer solutions. The introduction of an IPCS-Master, which is used to update the dual variable values, generally leads to fewer pricing problem iterations than when no master problem is used.

Road traffic dominates in domestic Swedish transportation and is highly dependent on fossil fuels, petrol and diesel. Currently, the use of renewable fuels in transportation accounts for less than 6% of the total energy use in transport. The demand for bioethanol to fuel transportation is growing and cannot be met through current domestic production alone. Lignocellulosic ethanol derived from agricultural crop residues may be a feasible alternative source of ethanol for securing a consistent regional fuel supply in Swedish climatic conditions.  This licentiate thesis focuses on regional transport fuel supply by considering local small-scale ethanol production from straw. It presents the results of investigations of regional transport fuel supply with respect to minimising regional CO2 emissions, cost estimates for transport fuel supply, and the availability of lignocellulosic resources for small-scale ethanol production. Regional transport fuel demand between the present and 2020 is also estimated. The results presented here show that significant bioethanol can be produced from the straw and Salix available in the studied regions and that this is sufficient to meet the regions’ current ethanol fuel demand.  A cost optimisation model for regional transport fuel supply is developed and applied for two cases in one study region, one when the ethanol production plant is integrated with an existing CHP plant (polygeneration), and one with a standalone ethanol production plant. The results of the optimisation model show that in both cases the changes in ethanol production costs have the biggest influence on the cost of supplying the regional passenger car fleet with transport fuel, followed by the petrol price and straw production costs.  By integrating the ethanol production process with a CHP plant, the costs of supplying regional passenger car fleet with transport fuel can be reduced by up to a third. Moreover, replacing petrol fuel with ethanol can cut regional CO2 emissions from transportation by half.

We define an order cutoff for a retailer as a time in the day such that orders sent to the depot before this point will be delivered by tomorrow, and orders submitted after will be delivered by the day after tomorrow. The later a retailer’s cutoff, the sooner it receives its orders which helps it to maintain ideal inventory levels. Generally, not all retailers in a supply chain can have the latest cutoff since transportation takes a significant amount of time. This thesis tries to assign optimal order cutoffs to retailers. We call this an order cutoff assignment problem and we solve it using three different mathematical programming approaches. The approaches are exhaustive route generation and selection, a series of mixed integer programs, and branch-and-price. 60 sample problems were solved and results showed that branch-and-price is often the most effective method.

We define an order cutoff for a retailer as a time in the day such that orders sent to the depot before this point will be delivered by tomorrow, and orders submitted after will be delivered by the day after tomorrow. The later a retailer’s cutoff, the sooner it receives its orders which helps it to maintain ideal inventory levels. Generally, not all retailers in a supply chain can have the latest cutoff since transportation takes a significant amount of time. This thesis tries to assign optimal order cutoffs to retailers. We call this an order cutoff assignment problem and we solve it using three different mathematical programming approaches. The approaches are exhaustive route generation and selection, a series of mixed integer programs, and branch-and-price. 60 sample problems were solved and results showed that branch-and-price is often the most effective method.

In this dissertation, several essays in the field of bio-security are presented. The estimation of the probability of an FMD outbreak by type and location of premises is important for decision making. In Essay I, we estimate and predict the probability/risk of an FMD outbreak spreading to the various premises in the study area. We first used a Poisson regression model with adjustment dispersion associated with random simulation results from the AusSpead model to estimate the parameters of the model. Our estimation and prediction show that large cattle loss could be concentrated in three counties-Deaf Smith, Parmer, and Castro. These results are based on approximately 70% of the feedlots with over 10,000 cattle located in the three counties previously mentioned. In Essay II, our objective is to determine the best mitigation strategies in minimizing animal loss based on AusSpead simulation model. We tested 15 mitigation strategies by using multiple comparison. The results show that the best mitigation strategies for all four scenarios are regular surveillance, slaughter of the infected animals, and early detection. We then used the Mixed Integer Programming to estimate costs of disposing of animal carcasses and transportation. Results show that the unit disposal cost will vary with carcass scale and the unit transportation cost also varies with the distribution of the infected premises and disposal locations. FMD seems to have varying impacts on equity markets. In Essay III, we studied returns at three different levels of the stock market. We determined results in a structural break, and then estimated the impact of the announcement of confirmed cases of FMD disease on the volatility of stock market returns by using a GARCH-Mean model. Our results show that the structure break occurs on the day with the largest number of confirmed cases for meat product firms rather than the day of the first confirmed case. We found that the conditional volatilities over the FMD period are higher than those over the sample period. The announcement of confirmed cases had the largest marginal impact on meat products. Investors may always consider maintaining a portfolio consisting of index funds or hedge funds.

In this thesis, we propose a hierarchical level decision support system for workforce planning in medical equipment maintenance services. In strategic level, customer clusters and the total number of field engineers is determined via a mixed integer programming and simulation. In MIP, we aim to find the minimum number of field engineers. Afterwards, we analyze service measures such as response time via simulation. In tactical level, quarterly training program for the field engineers is determined via mixed integer programming and the results are interpreted in terms of service level via simulation.

The focus of this dissertation is the advancement of theory and computation related to exact precision mathematical programming. Optimization software based on floating-point arithmetic can return suboptimal or incorrect resulting because of round-off errors or the use of numerical tolerances. Exact or correct results are necessary for some applications. Implementing software entirely in rational arithmetic can be prohibitively slow. A viable alternative is the use of hybrid methods that use fast numerical computation to obtain approximate results that are then verified or corrected with safe or exact computation. We study fast methods for sparse exact rational linear algebra, which arises as a bottleneck when solving linear programming problems exactly. Output sensitive methods for exact linear algebra are studied. Finally, a new method for computing valid linear programming bounds is introduced and proven effective as a subroutine for solving mixed-integer linear programming problems exactly. Extensive computational results are presented for each topic.

This dissertation is a collection of previously-published manuscript and conference papers. In this dissertation, we will deal with a stochastic unit commitment problem with cooling systems for gas generators, a robust unit commitment problem with demand response and uncertain wind generation, and a power grid vulnerability analysis with transmission line switching. The latter two problems correspond to our theoretical contributions in two-stage robust optimization, i.e., how to efficiently solve a two-stage robust optimization, and how to deal with mixed-integer recourse in robust optimization. Due to copyright issue, this dissertation does not include any methodology papers written by the author during his PhD study. Readers are referred to the author's website for a complete list of publications.

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. / text

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. / text