Operations Research, Systems Engineering and Industrial Engineering Commons^™

Maximally Disjoint Solutions Of The Set Covering Problem, David J. Rader, Peter L. Hammer

Mathematical Sciences Technical Reports (MSTR)

This paper is concerned with finding two solutions of a set covering problem that have a minimum number of variables in common. We show that this problem is NP­ complete, even in the case where we are only interested in completely disjoint solutions. We describe three heuristic methods based on the standard greedy algorithm for set covering problems. Two of these algorithms find the solutions sequentially, while the third finds them simultaneously. A local search method for reducing the overlap of the two given solutions is then described. This method involves the solution of a reduced set covering problem. Finally, …

Study Of Human Factors Variables In Battle Outcome Prediction Models, David Andrew Glovier

Engineering Management & Systems Engineering Theses & Dissertations

Over time there have been many improvements in models that are used to predict the outcome of battles. Currently there is much supposition and speculation surrounding the use of human performance related factors as additional inputs to battle simulation models to improve their accuracy. However there is no conclusive scientific evidence which shows that these factors do make a significant difference. This study investigates the use of factors that may impact on the human performance directly or indirectly in battle prediction models. These factors consist of traditional human factors and external factors that may influence the human performance. The research …

Solving Geometric Knapsack Problems Using Tabu Search Heuristics, Christopher A. Chocolaad

Theses and Dissertations

An instance of the geometric knapsack problem occurs in air lift loading where a set of cargo must be chosen to pack in a given fleet of aircraft. This paper demonstrates a new heuristic to solve this problem in a reasonable amount of time with a higher quality solution then previously reported in literature. We also report a new tabu search heuristic to solve geometric knapsack problems.

A New Sequential Goodness Of Fit Test For The Three-Parameter Weibull Distribution With Known Shape Based On Skewness And Kurtosis, Jonathan C. Clough

Theses and Dissertations

The Weibull distribution finds wide applicability across a broad spectrum of disciplines and is very prevalent in reliability theory. Consequently, numerous statistical tests have been developed to determine whether sample data can be adequately modeled with this distribution. Unfortunately, the majority of these goodness-of-fit tests involve a substantial degree of computational complexity. The study presented here develops and evaluates a new sequential goodness-of-fit test for the three-parameter Weibull distribution with a known shape that delivers power comparable to popular procedures while dramatically reducing computational requirements. The new procedure consists of two distinct tests, using only the sample skewness and sample …

An Advanced Visualization Method For An Operations Research Analysis, Steven C. Oimoen

Theses and Dissertations

Visualizing multidimensional data using only two dimensions and conventional visualization techniques limits the understanding of the data set. Underlying structures or patterns within the data can easily go unnoticed. In order to gain additional insight into an analysis, incorporation of visualization and multidimensional graphics into the analysis results should be accomplished. The results must ensure that the information portrayed is not misleading or misunderstood. The integrity of the data must be preserved throughout the transformation. The primary objective of this research effort is to identify techniques to visualize multidimensional data and then develop a software tool to display the multidimensional …

An Alternative Method For Determining Adjusted Function Points As The Basis For Software Cost Estimating, William Alexander Eldred

Engineering Management & Systems Engineering Theses & Dissertations

As software costs become an increasingly higher percentage of total computer system costs, it becomes increasingly more important for software development managers to have the ability to predict development costs with reasonable accuracy early in the software development cycle. Software development cost estimates are based in large measure on software size. Function points are considered by many to be a de facto industry standard as a size metric. The function points technique, unlike lines-of-code, can be applied early in the software development cycle and is language independent. Critics claim that the function point “value adjustment factor,” which purports to capture …

Modeling And Comparison Of Wormhole Routed Mesh And Torus Networks, Ronald I. Greenberg, Lee Guan

Computer Science: Faculty Publications and Other Works

2D-mesh and torus networks have often been proposed as the interconnection pattern for parallel computers. In addition, wormhole routing has increasingly been advocated as a method of reducing latency. Most analysis of wormhole routed networks, however, has focused on the torus and the broader class of k-ary n-cubes to which it belongs. This paper presents a performance model for the wormhole routed mesh, and it compares the performance of the mesh and torus based on theoretical and empirical analyses.

An Improved Analytical Model For Wormhole Routed Networks With Application To Butterfly Fat-Trees, Ronald I. Greenberg, Lee Guan

Computer Science: Faculty Publications and Other Works

A performance model for wormhole routed interconnection networks is presented and applied to the butterfly fat-tree network. Experimental results agree very closely over a wide range of load rate. Novel aspects of the model, leading to accurate and simple performance predictions, include (1) use of multiple-server queues, and (2) a general method of correcting queuing results based on Poisson arrivals to apply to wormhole routing. These ideas can also be applied to other networks.

A Synthesized Methodology For Eliciting Expert Judgment For Addressing Uncertainty In Decision Analysis, Richard W. Monroe

Engineering Management & Systems Engineering Theses & Dissertations

This dissertation describes the development, refinement, and demonstration of an expert judgment elicitation methodology. The methodology has been developed by synthesizing the literature across several social science and scientific fields. The foremost consideration in the methodology development has been to incorporate elements that are based on reasonable expectations for the human capabilities of the user, the expert in this case.

Many methodologies exist for eliciting assessments for uncertain events. These are frequently elicited in probability form. This methodology differs by incorporating a qualitative element as a beginning step for the elicitation process. The qualitative assessment is a more reasonable way …

A Comparison Of Circular Error Probable Estimators For Small Samples, Charles E. Williams

Theses and Dissertations

Several previous studies investigated the performance of competing circular error probable (CEP) estimators for small samples. This estimation is important in ICBM analysis because, due to expense, there are a limited number of ICBM test launches. In the most recent previous study (1993), Tongue considered five CEP estimators in a simulation test, attempting to determine the behavior of these estimators for populations of various bias, ellipticity, correlation, and sample size. In this paper, we build on Tongue's findings in three ways: (1) The number of estimators compared is expanded to eight. (2) Different factors and factor levels are used. (3) …

Experiments In Aggregating Air Ordnance Effectiveness Data For The Tacwar Model, James E. Parker

Theses and Dissertations

An interactive MS Access&trademark; based application that aggregates the output of the SABSEL model for input into the TACWAR model is developed. The application was developed following efforts to create a functional approximation of the SABSEL data using neural networks, statistical networks, and traditional statistical techniques. These approximations were compared to a look-up table methodology on the basis of accuracy, (RMSE

The Effects Of Human-Computer Communication Mode, Task Complexity, And Desire For Control On Performance And Discourse Organization In An Adaptive Task, Cristina Bubb-Lewis

Psychology Theses & Dissertations

The present study examined how different communication patterns affected task performance with an adaptive interface. A Wizard-of-Oz simulation (Gould, Conti, & Hovanyecz, 1983) was used to create the impression of a talking and listening computer that acted as a teammate to help participants interact with a computer application.

Four levels of communication mode were used which differed in the level of restriction placed on human-computer communication. In addition, participants completed two sets of tasks (simple and complex). Further, a personality trait, Desire for Control (DC), was measured and participants were split into high and low groups for analysis. Dependent measures …

Exploring Knowledge Processes For Technology Assimilation, Rochelle K. Young

Engineering Management & Systems Engineering Theses & Dissertations

In the emerging knowledge society, the ability to make the experience and expertise of those involved in and affected by new technology unconditionally available to all members of an organization is becoming increasingly important. One of the problems in developing such knowledge processes for technology assimilation is that current social structures do not easily accommodate unconditional participation. Since the implementation of modern information technology is changing the workplace and the nature of work itself, alternative social structures are needed. This research takes as given that deep questions concerning knowledge processes and social transformation are in principle undecidable; and, only questions …

Automatic Pcb Inspection Algorithms: A Survey, Madhav Moganti, Fikret Ercal, Cihan H. Dagli, Shou Tsunekawa

Computer Science Faculty Research & Creative Works

The importance of the inspection process has been magnified by the requirements of the modern manufacturing environment. In electronics mass-production manufacturing facilities, an attempt is often made to achieve 100% quality assurance of all parts, subassemblies, and finished goods. A variety of approaches for automated visual inspection of printed circuits have been reported over the past two decades. In this survey, algorithms and techniques for the automated inspection of printed circuit boards are examined. A classification tree for these algorithms is presented and the algorithms are grouped according to this classification. This survey concentrates mainly on image analysis and fault …

Randomized Approximation Of The Constraint Satisfaction Problem, Hoong Chuin Lau, Osamu Watanabe

Research Collection School Of Computing and Information Systems

We consider the Weighted Constraint Satisfaction Problem (W-CSP) which is a fundamental problem in Artificial Intelligence and a generalization of important combinatorial problems such as MAX CUT and MAX SAT. In this paper, we prove non-approximability properties of W-CSP and give improved approximations of W-CSP via randomized rounding of linear programming and semidefinite programming relaxations. Our algorithms are simple to implement and experiments show that they are run-time efficient.

Combinatorial Approaches For Hard Problems In Manpower Scheduling, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

Manpower scheduling is concerned with the construction of a workers' schedule which meets demands while satisfying given constraints. We consider a manpower scheduling Problem, called the Change Shift Assignment Problem(CSAP). In previous work, we proved that CSAP is NP-hard and presented greedy methods to solve some restricted versions. In this paper, we present combinatorial algorithms to solve more general and realistic versions of CSAP which are unlikely solvable by greedy methods. First, we model CSAP as a fixed-charge network and show that a feasible schedule can be obtained by finding disjoint paths in the network, which can be derived from …

On The Complexity Of Manpower Shift Scheduling, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

We consider the shift assignment problem in manpower scheduling, and show that a restricted version of it is NP-hard by a reduction from 3SAT. We then present polynomial algorithms to solve special cases of the problem and show how they can be deployed to solve more complex versions of the shift assignment problem. Our work formally defines the computational intractibility of manpower shift scheduling and thus justifies existing works in developing manpower scheduling systems using combinatorial and heuristic techniques.

A Robust Method Of Solving Nonlinear Boundary Value Problems Via Modified Compromise Programming, John L. Zornick

Theses and Dissertations

This study is an extension of Ng's previous work in which goal programming was used to determine an approximate solution to a boundary value problem. This approach follows the same basic approach developed by Ng in which the method of collocation was recast as a compromise programming model. Hence, instead of solving a system of simultaneous nonlinear equations, one seeks a compromise solution which minimizes (in a weighted residual sense) a vector norm of the differential equation residuals. A difference in this approach is that it makes use of a genetic algorithm as the optimizing engine as opposed to the …

Knowledge Acquisition And Structuring By Multiple Experts In A Group Support Systems Environment, Bernard Lee Lewis

Engineering Management & Systems Engineering Theses & Dissertations

This study addresses the impact of Group Decision Support Systems (GDSS) on expert system development by multiple Domain Experts. Current approaches to building expert systems rely heavily on knowledge acquisition and prototyping by a Knowledge Engineer working directly with the Domain Expert. Although the complexity of knowledge domains and new organizational approaches demand the involvement of multiple experts, standard procedures limit the ability of the Knowledge Engineer to work with more than one expert at a time.

Group Decision Support Systems offer a networked computerized environment for group work activities, in which multiple experts may express their ideas concurrently and …

Predicting Utility Bills For Air Combat Command A Study Of Forecasting Techniques, William L. Luthie

Engineering Management & Systems Engineering Theses & Dissertations

Many companies use forecasting techniques as a tool in managing their assets. Trends in such items as sales, population and inventory levels have all been determined at one time or another using forecasting, yet research indicates that these tools have not been utilized to predict utility budgets. This research was conducted to determine if such techniques could be applied to the specific task of predicting the utility bill at an Air Force base. Three quantitative models were chosen, the Moving Average, Exponential Smoothing and Regression, to determine their applicability to the task at hand. One base within Air Combat Command, …

Response Surface Methodology As A Sensitivity Tool In Decision Analysis, David A. Meyers

Theses and Dissertations

The purpose of this study is to evaluate response surface methodology as a sensitivity analysis tool in the area of decision analysis. The advent of low-cost personal computer software, such as DPLTM, has created an accessible tool with the ability to frame and solve influence diagrams for decision problems. This study provides a comparison of current sensitivity analysis techniques vs those made possible through response surface methodology (RSM). Sensitivity analysis alternatives are demonstrated on a decision problem concerning the evaluation of force structure options for the Department of Defense. Sensitivity analysis is performed on both one-way and two-way perturbations of …

The Effect Of Repeatedly Sampling An Embedded Metamodel On The Simulation Response, John Kent Patterson

Theses and Dissertations

This study investigated the effect on simulation output of repeatedly sampling an embedded metamodel. A metamodel is said to be embedded within a simulation if it is used to replace a submodule of that simulation. Replacing a deterministic module with an embedded deterministic metamodel poses no apparent mathematical problems. However, using a deterministic metamodel to replace a stochastic simulation component could require additional corrective actions. This research was performed in two phases. The first phase dealt with a set of tandem queues. It was shown that as each queue was sequentially replaced with a metamodel, the total system variance was …

A New Goodness-Of-Fit Test For The Gamma Distribution Based On Sample Spacings From Complete And Censored Samples, Huseyin Duman

Theses and Dissertations

This thesis studies a new goodness-of-fit test for the gamma distribution with known shape parameter. This test statistic, Z*, is based on spacings from complete or censored samples. The size of samples varied between 5 and 35. The critical value tables were generated for the Z* test statistic for complete and censored samples. The critical values were obtained for five different significance levels: 0.20 0.15, 0.10, 0.05, and 0.01. An extensive power study, containing 50,000 Monte Carlo runs was conducted using nine alternative distributions, H_a. It was observed that the Z* test statistic was more powerful against certain …

Estimation Of The Captive-Carry Survival Function For The Advanced Medium Range Air-To-Air Missile (Amraam), David R. Denhard

Theses and Dissertations

This thesis considers the problem of estimating the survival function of an item (probability that the item functions for a time greater than a given time t) from sampling data subject to partial right censoring (a portion of the items in the sampling data have not yet been observed to fail). Specifically the thesis describes several parametric and non-parametric statistical models that can be used when the sampling data is subject to partial right censoring. These models are applied to the case of estimating the captive-carry survival function of the AIM-120A Advanced Medium Range Air-to-Air Missile (AMRAAM).

Comparing Traditional Statistical Models With Neural Network Models: The Case Of The Relation Of Human Performance Factors To The Outcomes Of Military Combat, William Oliver Hedgepeth

Engineering Management & Systems Engineering Theses & Dissertations

Statistics and neural networks are analytical methods used to learn about observed experience. Both the statistician and neural network researcher develop and analyze data sets, draw relevant conclusions, and validate the conclusions. They also share in the challenge of creating accurate predictions of future events with noisy data.

Both analytical methods are investigated. This is accomplished by examining the veridicality of both with real system data. The real system used in this project is a database of 400 years of historical military combat. The relationships among the variables represented in this database are recognized as being hypercomplex and nonlinear.

The …

Transplanting Manufacturing Power: Observations From Five Years At Fujitsu, Steven M. Miller

Research Collection School Of Computing and Information Systems

Within a factory, what are the underpinnings of manufacturing power? During my thirty-month residency at Fujitsu's factory in Oyama, Japan, I constantly reflected on this question. The standard view of a factory structure provided by an organization chart was inadequate for summarizing my observations.

Multicriteria Mission Route Planning Using A Parallel A* Search, Michael S. Gudaitis

Theses and Dissertations

The Mission Route Planning (MRP) Problem falls into the general class of multicriteria path search problems. Multiple criteria are evaluated to select an optimal aircraft mission route through a hostile environment. Criteria for distance travelled and radar exposure are combined into a single cost function for route evaluation. Radar calculations are performed dynamically. The A* search algorithm is applied to the MRP problem, and a parallel implementation is developed and tested. A unique combination of distributed OPEN lists with a global CLOSED list strategy produced fast execution times on the Paragon. Test cases for scenarios with 15 radars took less …

How Effective Has The Air Force Been In Eliminating Its Dependence On Ozone Depleting Chemicals?, L. Susan Willard

Theses and Dissertations

This research was undertaken to determine how effectively the Air Force had eliminated its dependence on Ozone Depleting Chemicals. The research was limited to analyzing the impact of ODCs on major acquisition programs. Results indicated existing variables which may be impeding full implementation. Also identified were lessons learned which could be applied to future environmental legislation with potential impact on acquisition programs. In- depth telephonic interviews were conducted with Program Directors responsible for the development and fielding of major Air Force acquisition programs. Analysis revealed that ODCs substantially impacted the acquisition programs to the extent that many programs had classified …

Optimum Symbol-By-Symbol Detection Of Uncoded Digital Data Over The Gaussian Channel With Unknown Carrier Phase, Pooi Yuen Kam, Seng Siew Ng, Tock Soon Ng

Research Collection School Of Computing and Information Systems

A theory of optimum receiver design for symbol-by-symbol detection of an uncoded digital data sequence received over the Gaussian channel with unknown carrier phase is presented. Linear suppressed-carrier modulation is assumed. The work here aims at laying a conceptual foundation for optimum symbol-by-symbol detection, and rectifies existing approaches to the problem. The optimum receiver structure is obtained explicitly for an arbitrary carrier phase model, but its computational requirements are too heavy in general for any practical implementation. In one important special case, namely, the case in which the carrier phase can be treated as a constant over some K+1 symbol …

Automated Manpower Rostering: Techniques And Experience, C. M. Khoong, Hoong Chuin Lau, L. W. Chew

Research Collection School Of Computing and Information Systems

We present ROMAN, a comprehensive, generic manpower rostering toolkit that successfully handles a wide spectrum of work policies found in service organizations. We review the use of various techniques and methodologies in the toolkit that contribute to its robustness and efficiency, and relate experience gained in addressing manpower rostering problems in industry.