Master of Science / Department of Industrial & Manufacturing Systems Engineering / Todd W. Easton / Integer programs (IP) are a commonly researched class of problems used by governments and businesses to improve decision making through optimal resource allocation and scheduling. However, integer programs require an exponential amount of effort to solve and in some instances a feasible solution is unknown even with the most powerful computers. There are several methods commonly used to reduce the solution time for IPs. One such approach is to generate new valid inequalities through lifting. Lifting strengthens a valid inequality by changing the coefficients of the variables in the inequality. Lifting can result in facet defining inequalities, which are the theoretically strongest inequalities. This thesis introduces the Cutting-plane Algorithm in Three Sets (CATS) that can help reduce the solution time of integer programs. CATS uses synchronized simultaneous lifting to generate a new class of previously undiscovered valid inequalities. These inequalities are based upon three sets of indices from a binary knapsack integer program, which is a commonly studied integer program. CATS requires quartic effort times the number of inequalities generated. Some theoretical results describe easily verifiable conditions under which CATS inequalities are facet defining. A small computational study shows CATS obtains about an 8.9% percent runtime improvement over a commercial IP software. CATS preprocessing time is fast and requires an average time of approximately .032 seconds to perform. With the exciting new class of inequalities produced relatively quickly compared to the solution time, CATS is advantageous and should be implemented to reduce solution time of many integer programs.

Master of Science / Department of Industrial & Manufacturing Systems Engineering / Shuting Lei / Polyglycolic acid (PGA) is an important polymer in the field of tissue engineering. It has many favorable properties such as biocompatibility, bioabsorbability, high melting point, low solubility in organic solvents, high tensile strength and is used in a variety of medical related applications. Currently there are various methods such felting, stitching, use of binder/adhesive for joining the non woven meshes of PGA polymer in order to make suitable three dimensional scaffolds. The existing methods for joining the non woven meshes of PGA polymer are usually time consuming and not very flexible. Thus there is a need for a better technique that would overcome the drawbacks of the existing methods. Laser welding offers potential advantages such as high welding rates, easy to automate, improved seam and single sided access such that welds can be performed under various layers of fabric. Therefore, the main objective of this research is to conduct a fundamental study on laser welding of non woven PGA scaffold felts. An experimental setup for spot welding is built that would assist in the formation of tubular structures. A factorial design of experiments is used to study the effects of the operating parameters such as laser power, beam diameter, time duration and pressure on the weld quality. The weld quality is assessed in terms of weld strength and weld diameter. Based on the parametric study, a regression analysis is carried out to form correlations between weld quality and the operating parameters, which could be used to select the optimal operating conditions. The successful welds obtained by the laser welding process have no discoloration and are stronger than the tensile strength of the original non woven sheets of PGA biofelt.

Master of Science / Department of Industrial & Manufacturing Systems Engineering / Todd W. Easton / Integer programs (IPs) are mathematical models that can provide organizations with the ability to optimally obtain their goals through appropriate utilization and allocation of available resources. Unfortunately, IPs are NP-complete in the strong sense, and many integer programs cannot be solved. Introduced by Gomory, lifting is a technique that takes a valid inequality and strengthens it. Lifting can result in facet defining inequalities, which are the theoretically strongest inequalities; because of this, lifting techniques are commonly used in commercial IP software to reduce the time required to solve an IP. This thesis introduces two new algorithms for exact simultaneous up lifting multiple sets into binary knapsack problems and introduces sequential simultaneous lifting. The Dynamic Programming Multiple Lifting Set Algorithm (DPMLSA) is a pseudopolynomial time algorithm bounded by O(nb) effort that can exactly uplift an arbitrary number of sets. The Three Set Simultaneous Lifting Algorithm (TSSLA) is a polynomial time algorithm bounded by O(n2) and can exact simultaneously up lift three sets. The simultaneously lifted inequalities generated by the DPMLSA and the TSSLA can be facet defining, and neither algorithm requires starting with a minimal cover. A brief computational study shows that the DPMLSA is fast and required an average of only 0.070 seconds. The computational study also shows these sequential simultaneously lifted inequalities are useful, as the solution time decreased by an overall average of 18.4%. Therefore, implementing the DPMLSA should be beneficial for large IPs.

Master of Science / Department of Industrial & Manufacturing Systems Engineering / Todd W. Easton / Epidemics have been modeled mathematically as a way to safely understand them. For many of these mathematical models, the underlying assumptions they make provide excellent mathematical results, but are unrealistic for practical use. This research branches out from previous work by providing a model of the spread of infectious diseases and a model of quarantining this disease without the limiting assumptions of previous research. One of the main results of this thesis was the development of a core simulation that rapidly simulates the spread of an epidemic on a contact network. This simulation can be easily adapted to any disease through the adjustment of many parameters. This research provides the first definition for a quarantine cut and an ellipsoidal geographic network. This thesis uses the ellipsoidal geographic network to determine what is, and what is not, a feasible quarantine region. The quarantine cut is a new approach to partitioning quarantined and saved individuals in an optimized way. To achieve an optimal quarantine cut, an integer program was developed. Although this integer program runs in polynomial time, the preparation required to execute this algorithm is unrealistic in a disease outbreak scenario. To provide implementable results, a heuristic and some general theory are provided. In a study, the heuristic performed within 10% of the optimal quarantine cut, which shows that the theory developed in this thesis can be successfully used in a disease outbreak scenario.

Master of Science / Department of Industrial & Manufacturing Systems Engineering / Todd W. Easton / With the present threat of bioterrorist attacks and new natural disease strains developing, efficient and effective countermeasures must be in place in case of an epidemic outbreak. The best strategy is to stop the attack or natural phenomenon before it happens, but governments and individual citizens must have measures in place to limit the spread of a biological threat or infectious disease if it is ever introduced into society. The objective of this research is to know, before an outbreak, the best quarantine areas. Quarantines force similar individuals together and can be mathematically modeled as clustering people into distinct groups. In order to effectively determine the clustering solution to use as a quarantine plan, this research developed a simulation core that is highly adaptable to different disease types and different contact networks. The input needed for the simulation core is the characteristics of the disease as well as the contact network of the area to be modeled. Clustering is a mathematical problem that groups entities based on their similarities while keeping dissimilar entities in separate groups. Clustering has been widely used by civilian and military researchers to provide quality solutions to numerous problems. This research builds a mathematical model to find clusters from a community’s contact network. These clusters are then the preplanned quarantine areas. To find quality clusters a Clustering Heuristic using Integer Programming (CHIP) is developed. CHIP is a large neighborhood, hill-climbing heuristic and some computational results verify that it quickly generates good clustering solutions. CHIP is an effective heuristic to group people into clusters to be used as quarantine areas prior to the development of a disease or biological attack. Through a small computational study, CHIP is shown to produce clustering solutions that are about 25% better than the commonly used K-means clustering heuristic. CHIP provides an effective tool to combat the spread of an infectious disease or a biological terroristic attack and serves as a potential deterrent to possible terrorist attacks due to the fact that it would limit their destructive power. CHIP leads to the next level of preparation that could save countless lives in the event of an epidemic.

Master of Science / Department of Industrial & Manufacturing Systems Engineering / Chih-Hang Wu / The recent economic crisis has been partially blamed on the decline in the housing market. This decline in the housing market resulted in an estimated 87% decline in value of collateralized debt obligations (CDOs) between 2007 and 2008. This drastic decline in home values was sudden and unanticipated, thus it was incomprehensible for many investors how this would affect CDOs. This shows that while analytical techniques can be used to price CDOs, these techniques cannot be used to demonstrate the behavior of CDOs under radically different economic circumstances. To better understand the behavior of CDOs under different economic circumstances, numerical techniques such as Monte Carlo simulation can be used instead of analytical techniques to price CDOs. Andersen et al (2005) proposed a method for calculating the probability of defaults that could then be used in the Monte Carlo simulation to price the collateralized debt obligation. The research proposed by Andersen et al (2005) demonstrates the process of calculating correlated probability of defaults for a group of obligors. This calculation is based on the correlations between the obligors using copulas. Using this probability of default, the price of a collateralized debt obligation can be evaluated using Monte Carlo simulation. Monte Carlo simulation provides a more simple yet effective approach compared to analytical pricing techniques. Simulation also allows investors to have a better understanding of the behaviors of CDOs compared to analytical pricing techniques. By analyzing the various behaviors under uncertainty, it can be observed how a downturn in the economy could affect CDOs. This thesis extends on the use of copulas to simulate the correlation between obligors. Copulas allow for the creation of one joint distribution using a set of independent distributions thus allowing for an efficient way of modeling the correlation between obligors. The research contained within this thesis demonstrates how Monte Carlo simulation can be used to effectively price collateralized debt obligations. It also shows how the use of copulas can be used to accurately characterize the correlation between obligor defaults for pricing collateralized debt obligations. Numerical examples for both the obligor defaults and the price of collateralized debt obligations are presented to demonstrate the results using Monte Carlo simulation.

Master of Science / Department of Industrial & Manufacturing Systems Engineering / Todd W. Easton / Integer programming (IP) is a powerful technique used by many companies and organizations to determine optimal strategies for making decisions and managing resources to achieve their goals. One class of IP problems is the multiple knapsack (MK) problem. However, MK and other IP problems, are extremely complicated since they are ${\cal NP}$-hard problems. Furthermore, there exist numerous instances that can not be solved. One technique commonly used to reduce the solution time for IP problems is lifting. This method, introduced by Gomory, takes an existing valid inequality and strengthens it. Lifting has the potential to form facet defining inequalities, which are the strongest inequalities to solve an IP problem. As a result, lifting is frequently used in integer programming applications. This research takes a broad approach to simultaneous lifting and provides its theoretical background for. The underlying hypergraphic structure for simultaneous lifting in an MK problem is identified and called a constellation. A constellation contains two hypercliques and multiple hyperstars from various conflict hypergraphs. Theoretical results demonstrate that a constellation induces valid inequalities that could be obtained by simultaneous lifting. Moreover, these constellation inequalities can be facet defining. The primary advancements, constellations and the associated valid inequalities, of this thesis are theoretical in nature. By providing the theory behind simultaneous lifting, researchers should be able to apply this knowledge to develop new algorithms that enable simultaneous lifting to be performed faster and over more complex integer programs.

Master of Science / Department of Industrial & Manufacturing Systems Engineering / David H. Ben-Arieh / In present competitive market, there is growing concern for ascertaining and fulfilling the individual customer’s wants and needs. Therefore, the focus of manufacturing has been shifting from mass production to mass customization, which requires the manufacturers to introduce an increasing number of products with shorter life span and at a lower cost. Also, another challenge is to manage the variety of products in an environment where demands are stochastic and the lead times to fulfill those demands are short. The focus of this thesis is to develop and investigate platform based production strategies, as opposed to producing each product independently, which would ensure the economic production of the broader specialized products with small final assembly time and under demand uncertainty. The thesis proposes three different platform based production models. The first model considers the economic production of products based on a single platform and with forecasted demands of the products. The model is formulated as a general optimization problem that considers the minimization of total production costs. The second model is the extension of the first model and considers the production of products based on multiple platforms and considers the minimization of total production costs and the setup costs of having multiple platforms. The third model is also an extension of the first model and considers the demands of the products to be stochastic in nature. The model considers the minimization of total production costs and shortage costs of lost demands and holding cost of surplus platforms under demand uncertainties. The problem is modeled as a two stage stochastic programming with recourse. As only the small instances of the models could be solved exactly in a reasonable time, various heuristics are developed by combining the genetic evolutionary search approaches and some operations research techniques to solve the realistic size problems. The various production models are validated and the performances of the various heuristics tailored for the applications are investigated by applying these solution approaches on a case of cordless drills.

Master of Science / Department of Industrial & Manufacturing Systems Engineering / Todd W. Easton / Integer programming (IP) has been and continues to be widely used by industries to minimize cost and effectively manage resources. Faster computers and innovative IP techniques have enabled the solution to many large-scale IPs. However, IPs are NP-hard and many IPs require exponential time to solve. Lifting is one of the most widely used techniques that helps to reduce computational time and is widely applied in today's commercial IP software. Lifting was first introduced by Gomory for bounded integer programs and a theoretical and computationally intractible technique to simultaneously lift sets of variables was introduced by Zemel in 1978. This thesis presents a new algorithm called the Maximal Simultaneous Lifting Algorithm (MSLA), to simultaneously uplift sets of binary integer variables into a cover inequality. These lifted inequalities result in strong inequalities that are facet defining under fairly moderate assumptions. A computational study shows that this algorithm can find numerous strong inequalities for random Knapsack (KP) instances. The pre-processing time observed for these instances is less than 1/50th of a second, which is negligible. These simultaneously lifted inequalities are easy to find and incorporating these cuts to KP instances reduced the solution time by an average of 41%. Therefore, implementing MSLA should be highly beneficial for large real-world problems.

Master of Science / Department of Industrial & Manufacturing Systems Engineering / Malgorzata J. Rys / Emergency Medical Systems (EMS) are designed to handle emergencies. Fortunately, most emergencies faced have only one patient. The every day system is not designed to respond to emergencies in which there are many casualties. Due to natural disasters and terrorist attacks that have occurred over the past decade, mass-casualty disaster response plans have become a priority for many organizations, including EMS. The resources available for constructing such plans are limited. Physical simulations or practices of the plan are often performed; however, it is not until a disaster strikes that the capabilities of the plan are truly realized. In this paper, it is proposed that discrete-event simulations are used as part of the planning process. A computer simulation can test the capability of the plan under different settings and help planners in their decision making. This paper looks at the creation of a discrete-event simulation using ARENA software. The simulation was found to accurately simulate the response to the Greensburg tornado that occurred May of 2008. A sensitivity analysis found that the simulation results are dependent upon the values assumed for Volunteer Injury Rate, Injury Level, Information Dissemination Rate and Transportation Decision variables. When a disaster occurs, the local resources are overwhelmed and outside aide must be called in. Decision rules for when to request more outside ambulances and when to release them to send them home are evaluated. The more resources that are made available, the quicker patients receive medical care. However, when outside ambulances are called in, they are putting their home area at risk because it no longer has complete (or any) ambulance coverage. As the percent of coverage decreases, the amount of time that victims spend waiting for ambulances also decreases. Many decision rules were evaluated, resulting in various combinations of ambulance wait times and average percent coverage. It is up to Disaster Planners to determine how much of an additional wait can be assumed by the disaster victims to prevent outside districts from taking on unwarranted risk of low coverage.