VTechWorks Repository :: Browsing by Author "Boisen, Monte B. Jr."

Browsing by Author "Boisen, Monte B. Jr."

Now showing 1 - 20 of 27

Bond length and bonded radii variations in nitride molecules and crystals
Buterakos, Lewis A. (Virginia Tech, 1990-08-09)
Molecular Orbital calculations on 31 H3:e_mxm+N:e hydronitride molecules containing 3-, 4-, and 6-coordinate X-cations from rows 1-4 of the periodic table yield minimum energy bond lengths, Rt(XN), which reproduce observed bond lengths, Ro(XN), in crystalline nitrides to within o.O₃A, on average. A linear regression analysis of In[Rt(XN)] vs. In(p) with p = air, where a is the Pauling bond strength and r is the row number of the X -cation in the periodic table, gives the equation R(XN) = 1.47p-O.2\ which is shown to reproduce the observed XN bond lengths of Baur (1987) to within o.o9A, on average. This equation is statistically identical to the equation R( XN) 1.49p-O.22, derived from a linear regression analysis ofln[Ro{XN)] vs. In(p), and is similar in form to those obtained for the oxides (R(XO) = 1.39p-O.22) and the sulfides (R(XS) = 1.83p-O.21).
Bonding properties of coordinated polyhedra in molecules and crystals
Hill, Frances Cull (Virginia Tech, 1995-12-05)
Force constants and electron density distributions in coordination polyhedra in molecules and crystals are modeled using Hartree-Fock molecular orbital methods. Model bond-stretching force constants calculated for coordination polyhedra in a series of nitride, oxide and sulfide molecules are ~ 10-20% larger than obtained with spectroscopic methods. Well-developed correlations obtain between the force constants and minimum energy bond lengths, effective nuclear charges and polyhedral compressibilities of molecules and crystals. Model electron density distributions calculated for a large number of molecules with MOn (n = 1, 2,3,4 or 6) coordination polyhedra show that the MO bonds of a given type vary in a regular way with the value of the electron density at bond critical points, bonded radii and the curvatures of the electron density. The bonded interactions in the polyhedra are examined in terms of criteria set forth by Bader and Essen (1984) and Cremer and Kraka (1984).
Cell design in a cellular system using guard channels, call queueing and channel borrowing
Jain, Nikhil (Virginia Tech, 1993-12-05)
This dissertation develops an analytic framework to undertake cell design in a cellular system. The cell is modeled in a broader sense than ever done before. In our analytical model, we incorporated the use of guard channels, queueing of new calls, and hybrid channel allocation. A numerically stable and efficient solution to a queueing system with two arrival streams having reserved and borrowable servers has been developed. This queueing system is used to model the cell behavior. The model provides valuable insights into the behavior of the cell, and this in turn has been used to devise an efficient stochastic optimization algorithm for determining the minimum number of channels required by the cell. Our techniques are stable, easy to implement for practical systems and produce optimized solutions quickly. This is particularly useful because we expect that future designs of cellular systems may execute such algorithms on cell-site processors.
Computational Alchemy: The Rational Design of New Superhard Materials
Teter, David Michael (Virginia Tech, 1998-06-29)
First--principles electronic structure calculations have been performed to help identify and direct the synthesis of new superhard compounds. An improved figure of merit for hardness is identified and used to show that carbon nitrides are not likely to be harder than diamond.
The Creation of Algorithms Designed for Analyzing Periodic Surfaces of Crystals and Mineralogically Important Sites in Molecular Models of Crystals: Understanding the Electron Density Function Through Visual Examinations of the Curvature and Shape of the Equi-Value Laplacian Surfaces
Beverly, Lesa Lynn (Virginia Tech, 2000-07-21)
The goals of the research presented in this dissertation were to create algorithms that produce images of complex phenomena, to study the efficacy of the algorithms, and to apply these algorithms to important mineralogical problems. The algorithms that were created include the Sphere Projection method, the Chicken Wire method, and methods for calculating the curvature at any point on a surface. The Sphere Projection method is best applied to roughly spherical surfaces. A theorem about the "fit" to a sphere determines the accuracy of the model in this special case and gives some insight into the limitations of this method. The Chicken Wire method was developed to model those surfaces for which the Sphere Projection method was ineffective. The effectiveness of the Chicken Wire method was also determined. The algorithms were used to produce images of equi-value surfaces of the Laplacian of the electron density function in selected molecules. The water molecule, H2O, was studied to demonstrate that these new methods are capable of reproducing known features. The disiloxane molecule, H6Si2O7, was studied because it serves as a model for bonding in quartz and other important silicates. Lastly, the molecule NaLi2Si2OF9 was examined as a molecular model for low albite. A new discovery suggests that these algorithms will be an important tool in mineralogy.
Designing a statically typed actor-based concurrent object-oriented programming language
Lee, Keung Hae (Virginia Tech, 1990)
The research reported in this dissertation investigates extending the power and flexibility of an object-oriented language with inheritance, Static typing, and concurrency. A language supporting inheritance, static typing, and concurrency offers a significant leverage in software development. However, when these features are provided together, the benefits of the features are significantly reduced due to the interaction among them. The challenge for the designer of an object-oriented language lies in the difficulty of reconciling the conflicts among these features. This thesis discusses two issues: combining static typing with inheritance and combining concurrency with inheritance. A new model of type and inheritance, called HANA, is presented. The HANA model integrates multiple inheritance, multiple representation, method exclusion, and method name overloading with static typing. The contribution of HANA is that it extends other existing models of type and inheritance with enhanced expressive power, increased reusability, and improved program efficiency. Combining concurrency with inheritance is investigated in the framework of the actor computation model. A language design based on the actor model of concurrent computation faces a serious problem arising from the interference between concurrency and inheritance. A similar problem also occurs in other concurrent object-oriented languages. The problem of concurrency-inheritance conflict is described and a solution based on a concept called behavior abstraction is presented.
Determining intrinsic scene characteristics from images
Pong, Ting-Chuen (Virginia Polytechnic Institute and State University, 1984)
Three fundamental problems in computer vision are addressed in this dissertation. The first deals with the problem of how to extract and assemble a rich symbolic representation of the gray level intensity changes in an image. Results show that the facet model based feature extraction scheme proposed here is superior to the other existing techniques. The second problem addressed deals with the interpretation of the resulting structures as three-dimensional object surfaces. The three different shape modules described in this dissertation are found to be useful in the recovery of intrinsic scene characteristics. Finally, mechanisms for interaction among different sources of information obtained from different shape modules are studied. It is demonstrated that interactions among shape modules can enhance the data acquired by different means.
The electronic structure of galena and hematite surfaces: applications to the interpretations of STM images, XPS spectra and heterogeneous surface reactions
Becker, Udo (Virginia Tech, 1995-11-07)
Scanning tunneling microscopy (STM) images and scanning tunneling spectroscopy (STS) spectra of galena (PbS) and hematite (a-Fe203) were calculated using ab-initio methods in order to interpret experimental images and spectra that were taken in previous studies. These calculations have helped to understand which states of the mineral surfaces were imaged depending on the bias voltage and tip-sample separation. The computational results also gave insight in electron transfer processes that take place during surface adsorption/oxidation/reduction processes. In this context, different oxidation (using O₂ and ferric iron as oxidants) and gold adsorption/reduction mechanisms on galena were evaluated at an atomic level. On hematite, the main emphasis was determining the differences in the local electronic structure of specific sites above the surface and the electronic structure of the bulk. Hereby, step sites turned out to have an increased local density of states at certain electron binding energies that are absent on flat surfaces. states can explain the highly increased reactivity of step sites as compared to terraces. X-ray photoelectron spectra (XPS) were calculated to compare the photoelectron peaks of the calculated specific surface structures (that do not have a bulk equivalent) with experimentally obtained XPS spectra. Most of the calculated peak chemical shifts coincided with those that were found in experiments and that were previously interpreted in terms of known bulk structures. Therefore, it can be inferred that the conventional way of interpreting XPS spectra might be incomplete if specific surface structures are neglected. In order to understand step velocities on a gypsum (010) surface, step energies of different step directions were calculated using an ab-initio approach. An approximately linear relationship was found between the calculated step energies and the experimentally determined step velocities.
Error directed execution history analysis: an approach to automatic debugging
Okie, Edward Graham (Virginia Polytechnic Institute and State University, 1989)
Execution history (EH) analysis is a major unexplored area in the development of debugging technology. In this dissertation we develop a theoretical foundation for incorporating EH analysis into the process of automatically debugging programs written in imperative, strongly typed, procedure oriented languages. This foundation includes the construction of a model for EH representation, an analysis of run time errors within the model, and the development of an approach to the use of EH analysis in automatic debugging. The model represents an execution history as a sequence of state vectors. Each vector contains both the values of program variables at a particular point in a computation and additional information that is used in the debugging process. Within this model, run time errors are classified by their effect on program termination, and characterized by their appearance within the EH. Based on this classification and characterization, techniques for detecting errors within an EH are presented. These techniques form the basis of an approach to automatic debugging in which a deterministic analysis locates errors in the execution history and, based on the results of this search, heuristic techniques perform automatic fault Localization.
The Exit Time Distribution for Small Random Perturbations of Dynamical Systems with a Repulsive Type Stationary Point
Buterakos, Lewis Allen (Virginia Tech, 2003-08-04)
We consider a stochastic differential equation on a domain D in n-dimensional real space, where the associated dynamical system is linear, and D contains a repulsive type stationary point at the origin O. We obtain an exit law for the first exit time of the solution process from a ball of arbitrary radius centered at the origin, which involves additive scaling as in Day (1995). The form of the scaling constant is worked out and shown to depend on the structure of the Jordan form of the linear drift. We then obtain an extension of this exit law to the first exit time of the solution process from the general domain D by considering the exit in two stages: first from the origin O to the boundary of the ball, for which the aforementioned exit law applies, and then from the boundary of the ball to the boundary of D. In this way we are able to determine for which Jordan forms we can obtain a limiting distribution for the first exit time to the boundary of D as the noise approaches 0. In particular, we observe there are cases for which the exit time distribution diverges as the noise approaches 0.
Exploring the powers of stacks and queues via graph layouts
Pemmaraju, Sriram V. (Virginia Tech, 1992)
In this dissertation we employ stack and queue layouts of graphs to explore the relative power of stacks and queues. Stack layout and queue layouts of graphs can be examined from several points of view. A stack or a queue layout of a graph can be thought of as an embedding of the graph in a plane satisfying certain constraints, or as a graph linearization that optimizes certain cost measures, or as a scheme to process the edges of the graph using the fewest number of stacks or queues. All three points of view permeate this research, though the third point of view dominates. Specific problems in stack and queue layouts of graphs have their origin in the areas of VLSI, fault-tolerant computing, scheduling parallel processes, sorting with a network of stacks and queues, and matrix computations. We first present two tools that are useful in the combinatorial and algorithmic analysis of stack and queue layouts as well as in determining bounds on the stacknumber and the queuenumber for a variety of graphs. The first tool is a formulation of a queue layout of a graph as a covering of its adjacent matrix with staircases. Not only does this formulation serve as a tool for analyzing stack and queue layouts, it also leads to efficient algorithms for several problems related to sequences, graph theory, and computational geometry. The connection between queue layouts and matrix covers also forms the basis of a new scheme for performing matrix computations on a data driven network. Our analysis reveals that this scheme uses less hardware and is faster than existing schemes. The second tool is obtained by considering separated and mingled layouts of graphs. This tool allows us to obtain lower bounds on the stacknumber and the queuenumber of a graph by partitioning the graph into subgraphs and simply concentrating on the interaction of the subgraphs. These tools are used to obtain results in three areas. The first area is stack and queue layouts of directed acyclic graphs (dags). This area is motivated by problems of scheduling parallel processes. We establish the stacknumber and the queuenumber of classes of dags such as trees, unicylic graphs, outerplanar graphs, and planar graphs. We then present linear time algorithms to recognize 1-stack dags and leveled-planar dags. In contrast, we show that the problem of recognizing 9-stack dags and the problem of recognizing 4-queue dags are both NP-complete. The second area is stack and queue layouts of partially ordered sets (posets). We establish upper bounds on the queuenumber of a poset in terms of other measures such as length, width, and jumpnumber. We also present lower bounds on the stacknumber and on the queuenumber of certain classes of posets. We conclude by showing that the problem of recognizing a 4-queue poset is NP-complete. The third area is queue layouts of planar graphs. While it has been shown that the stacknumber of the family of planar graphs is 4, the queuenumber of planar graphs is unknown. We conjecture that a family of planar graphs—the stellated triangles—has unbounded queuenumber; using separated and mingled layouts, we demonstrate significant progress towards that result.
First-principles study of several hypothetical silica framework structures
Teter, D. M.; Gibbs, Gerald V.; Boisen, Monte B. Jr.; Allan, D. C.; Teter, M. P. (American Physical Society, 1995-09-15)
Several hypothetical silica structures have been generated using a simulated-annealing strategy with an ab initio based covalent-bonding potential. First-principles total-energy pseudopotential methods have been used to examine several. promising hypothetical structures and to compare their structural parameters, cohesive energies, and bulk moduli with those of low quartz;, low cristobalite, silica sodalite, and stishovite. The cohesive energies of these hypothetical structure types are found to be equivalent to those of low quartz, low cristobalite, and silica sodalite, and significantly lower than that of stishovite.
Groups, Graphs, and Symmetry-Breaking
Potanka, Karen Sue (Virginia Tech, 1998-04-16)
A labeling of a graph G is said to be r-distinguishing if no automorphism of G preserves all of the vertex labels. The smallest such number r for which there is an r-distinguishing labeling on G is called the distinguishing number of G. The distinguishing set of a group Gamma, D(Gamma), is the set of distinguishing numbers of graphs G in which Aut(G) = Gamma. It is shown that D(Gamma) is non-empty for any finite group Gamma. In particular, D(D_n) is found where D_n is the dihedral group with 2n elements. From there, the generalized Petersen graphs, GP(n,k), are defined and the automorphism groups and distinguishing numbers of such graphs are given.
Librational displacements of silicate tetrahedra in response to temperature and pressure
Downs, Robert T. (Virginia Tech, 1992-12-05)
Recently it has been concluded that the SiO₄ silicate tetrahedra in crystals behave as rigid bodies. This conclusion is based on analyses of the atomic displacement factors of Si and O atoms obtained from single crystal diffraction experiments wherein the amplitudes of atomic vibrations are ascribed to translational, librational and screw-correlated modes of motion for the entire SiO₄ group. If the displacement ellipsoids are considered to represent time averaged quadratic surfaces of equal configurational potential energy about the mean position of an atom, then an analysis of the these displacements should provide detailed information about the SiO₄ group and the crystal. The apparent SiO bond lengths recorded for silicates over a range of temperatures are typically either invariant or exhibit a contraction with increasing temperature. A rigid-body thermal analysis was completed for the tetrahedra in nine silicates whose structures have been determined over a range of temperatures from 15 K to 1250 K and whose tetrahedra seem to behave as rigid units. The coordinates provided by the analysis yield bond lengths and polyhedral volumes corrected for the librational motion of each silicate tetrahedron. The bond lengths and volumes estimated for tetrahedra with four bridging oxygens seem to increase with temperature at a faster rate than those with four nonbridging oxygen atoms. Those for tetrahedra with two or three nonbridging oxygen atoms tend to increase at an intermediate rate. An analysis of the rigid-body motion of coordinated polyhedra yields a simple but accurate expression for correcting bond lengths for thermal vibrations. Observed anisotropic displacement parameters for Si and O atoms indicate that the SiO₄ tetrahedra in quartz behave as rigid bodies. A configurational potential energy curve, constructed from the librational components of the rigid body motion of the tetrahedra, shows a double well for α quartz and a single well for β quartz when plotted as a function of the displacement of the O atom with temperature. The configurational energetics of α and β quartz are examined with a theoretical potential energy function based on parameters obtained from molecular orbital calculations. The calculations indicate that the temperature behavior of a quartz is governed by the energetics of the SiOSi angle, in contrast to β quartz which is governed by the energetics of the SiO bond. The mechanism of the α ⇌ β transition is examined in terms of the experimental and modeled configurational potential energy curves. Evidence for the proposal that π bonding is the driving mechanism for the transition is lacking. Structural and volume compressibility data for α-cristobalite were determined by single crystal X-ray diffraction methods for pressures up to ~1.6 GPa, where cristobalite undergoes a reversible phase transition. The bulk modulus was determined to be 11.5(7) GPa with a pressure derivative of 9(2). The SiOSi angle shows a greater decrease than observed for quartz and coesite while the SiO bond lengths and the OSiO angles remain essentially unchanged. The responses of V/V₀ and SiOSi angle to pressure for the silica polymorphs are compared and it is found that the percentage decrease in the volume is linearly correlated with the percentage decrease in the SiOSi angle, regardless of the framework structure type. A mathematical modeling of the energies of the structural changes that are induced by pressure suggests that the contribution to the total energy ascribed to Si0Si angle bending terms is the same in quartz and cristobalite.
Mathematical Models of the Alpha-Beta Phase Transition of Quartz
Moss, George W. (Virginia Tech, 1999-07-27)
We examine discrete models with hexagonal symmetry to compare the sequence of transitions with the alpha-inc-beta phase transition of quartz. We examine a model by Parlinski which employs interactions of nearest and next-nearest neighbor atoms. We numerically determine the configurations which lead to minimum energy for a range of parameters. We then use Golubitsky's results on systems with hexagonal symmetry to derive the bifurcation diagram for Parlinski's model. Finally, we study a large class of modifications to Parlinski's model and show that all such modifications have the same bifurcation picture as the original model.
Minimal PMU placement for graph observability: a decomposition approach
Brueni, Dennis J. (Virginia Tech, 1993-12-06)
This thesis explores the PMU placement problem, that is, the placement of a minimal number of Phase Measurement Units (PMUs) on the nodes of a power system graph such that the entire graph is observed. The NP-completeness of PMU placement for planar bipartite graphs is shown. PMU placement algorithms are developed for graphs of bounded tree width, such as trees and outer planar graphs. Graph decompositions are used to develop efficient algorithms that produce minimal PMU covers. These algorithms are developed, analyzed, and compared theoretically. Algorithm animations were used in the study to develop insight into the problem and to understand algorithm behavior.
Modeling reconfiguration algorithms for regular architecture
DeBrunner, Linda Sumners (Virginia Tech, 1991-07-05)
Three models are proposed to evaluate and design distributed reconfigurable systems for fault tolerant, highly reliable applications. These models serve as valuable tools for developing fault tolerant systems. In each model, cells work together in parallel to change the global structure through a series of separate actions. In the Local Supervisor Model (LSM), selected cells guide the reconfiguration process. In the Tessellation Automata Model (TAM), each cell determines its next state based on its state and its neighbors' states, and communicates its state information to its neighbors. In the Interconnected Finite State Machine Model (IFS:MM:), each cell determines its next state and outputs based on its state and its inputs. The hierarchical nature of the TAM and IFSMM provides advantages in evaluating, comparing, and designing systems. The use of each of these models in describing systems is demonstrated. The IFSMM: is emphasized since it is the most versatile of the three models. The IFSMM: is used to identify algorithm weaknesses and improvements, compare existing algorithms, and develop a novel design for a reconfigurable hypercube.
Modeling the properties of silicates
Bartelmehs, Kurt Lane (Virginia Tech, 1993-02-18)
Assuming a simple force field involving only short range Non-Coulombic molecular energy terms along with P1 symmetry, a variation of the SQLOO model (Boisen and Gibbs, 1993) successfully generates the structure types of both α and β1 quartz along with at least five alternative structure types of silica not yet observed to our knowledge. These structure types are identified by the existence of symmetry elements represented in the optimized atomic coordinates and cell parameters that define a minimizer in the model. A family of minimizers is discovered through the combined use of Monte Carlo simulated annealing followed by quasi-Newton minimization techniques. The results are in contrast with the assertion made by Tse et al. (1992) that new structure types of SiO₂ can only be arrived at by Molecular Dynamic methods. By varying the parameters used in the minimization process, different families of structure types are discovered. Several structure types were found to have high symmetries. These results are in contrast with the findings by Kramer et aL (1991) that the stability of high symmetry structures of silica are stabilized in part by ionicity. The results reported here are for calculations involving Z = 3 and 6 formula units. This strategy may be useful in the prediction of possible high silica zeolite structure types. An examination of the atomic displacement parameters (ADPs) obtained for TO₄ tetrahedra (T = Si, Al) suggest rigid TO bonds are more common in non-framework than in framework silicates. Correlated motion is found among the ADPs that is consistent with TLS rigid body motion. For these data, the translational motion is represented by the ADPs of the central T atom while both the librational and translational motion is contained in those of the surrounding O atoms. The libration angle for rigid tetrahedra is linearly dependent on the difference between the isotropic equivalent displacement parameter of the T and O atoms, B(T) and B(O), respectively. The value of B(O) is on average twice that of B(T) with a maximum value of ~ 2.0Å². Variations in the SiO bond lengths of rigid tetrahedra in the silica polymorphs is related only to f_s(O). Rigid TO and OO bonds are a necessary but not sufficient condition for rigid body motion. Nonrigid tetrahedra may represent crystals containing disorder or problems with the refinement. The computer program EXCALIBR (Bloss and Riess, 1973; Bloss, 1981, p. 202) has been rewritten and markedly improved. Like EXCALIBR, EXCALIBR II solves optical extinction data, as determined with a spindle stage, and determines the optic axial angle 2V and the orientation of the crystal’s optical indicatrix. EXCALIBR II uses a modification to Joel’s equation as a means of obtaining the optic axes of a crystal. Furthermore, EXCALIBR II successfully solves extinction data where one optic axis of a biaxial crystal is 90° to the spindle axis, an orientation that had thwarted its predecessor. EXCALIBR II also accurately determines the optical indicatrix orientation for uniaxial crystals. After solving extinction data for several different wavelengths and/or temperatures, EXCALIBR II calculates the angular change of each optic direction with wavelength and/or temperature along with the error on the angle. Using a simple t-test, it then computes a p-value to aid in the decision as to whether the optical direction truly exhibits dispersion. This is a more valid and sensitive procedure than the χ² test used by EXCALIBR, particularly because the covariance in each optic vector’s coefficients are taken into consideration and the results are invariant to the vector’s orientation.
An object-oriented database system for efficient information retrieval applications
Chen, QiFan (Virginia Tech, 1992-03-16)
This dissertation deals with the application of object-oriented database techniques to the problem of storage and access of information retrieval (IR) data, especially data that can be organized as a graph, such as a thesaurus encoded in semantic networks, or hypertext collections. Even traditional IR models can use graph representations of documents and concepts. This dissertation reports the development of an object-oriented model called the LEND (Large External object-oriented Network Database) model. This model contains not only features found in a typical object-oriented model but also those that specifically are designed for graph-structured data. A query language is provided facilitating the specification of graph-oriented queries. A prototype LEND system has been implemented to test the model on realistic graph-structured data. It adopts an open system architecture and design, and is easily extensible, like the LEND model itself. The research result of suitable data structures and algorithms (a class of minimal perfect hashing functions) for the efficient implementation of the LEND model is also reported. These data structures and algorithms enable retrieval of a node or a set of nodes in an optimal fashion. Placement of a large graph on a disk is studied as well. The method developed permits efficient traversal of graphs.
The polyhedral structure of certain combinatorial optimization problems with application to a naval defense problem
Lee, Youngho (Virginia Tech, 1992-06-05)
This research deals with a study of the polyhedral structure of three important combinatorial optimization problems, namely, the generalized upper bounding (GUS) constrained knapsack problem, the set partitioning problem, and the quadratic zero-one programming problem, and applies related techniques to solve a practical combinatorial naval defense problem. In Part I of this research effort, we present new results on the polyhedral structure of the foregoing combinatorial optimization problems. First, we characterize a new family of facets for the GUS constrained knapsack polytope. This family of facets is obtained by sequential and simultaneous lifting procedures of minimal GUS cover inequalities. Second, we develop a new family of cutting planes for the set partitioning polytope for deleting any fractional basic feasible solutions to its underlying linear programming relaxation. We also show that all the known classes of valid inequalities belong to this family of cutting planes, and hence, this provides a unifying framework for a broad class of such valid inequalities. Finally, we present a new class of facets for the boolean quadric polytope, obtained by applying a simultaneous lifting procedure. The strong valid inequalities developed in Part I, such as facets and cutting planes, can be implemented for obtaining exact and approximate solutions for various combinatorial optimization problems in the context of a branch-and-cut procedure. In particular, facets and valid cutting planes developed for the GUS constrained knapsack polytope and the set partitioning polytope can be directly used in generating tight linear programming relaxations for a certain scheduling polytope that arises from a combinatorial naval defense problem. Furthermore, these tight formulations are intended not only to develop exact solution algorithms, but also to design powerful heuristics that provide good quality solutions within a reasonable amount of computational effort. Accordingly, in Part ll of this dissertation, we present an application of such polyhedral results in order to construct effective approximate and exact algorithms for solving a naval defense problem. tn this problem, the objective is to schedule a set of illuminators in order to strike a given set of targets using surface-to-air missiles in naval battle-group engagement scenarios. The problem is conceptualized as a production floor shop scheduling problem of minimizing the total weighted flow time subject to time-window job availability and machine-downtime unavailability side constraints. A polynomial-time algorithm is developed for the case when ail the job processing times are equal (and unity without loss of generality) and the data are all integer. For the general case of scheduling jobs with unequal processing times, we develop three alternative formulations and analyze their relative strengths by comparing their respective linear programming relaxations. The special structures inherent in a particular strong zero-one integer programming model of the problem enable us to derive some classes of strong valid inequalities from the facets of the GUB constrained knapsack polytope and the set-packing polytope. Furthermore, these special structures enable us to construct several effective approximate and exact algorithms that provide solutions within specified tolerances of optimality, with an effort that admits real-time processing in the naval battle-group engagement scenario. Computational results are presented using suitable realistic test data.

Browsing by Author "Boisen, Monte B. Jr."

Results Per Page

Sort Options