Scheduling a Burn-In Oven with Non-Agreeable Release Times and Due Dates

We consider the problem of scheduling semiconductor burn-in operations, where burn-in ovens are modelled as batch processing machines. Most of the studies assume that ready times and due dates of jobs are agreeable (i.e., ri < rj implies di ≤ dj). In many real world applications, the agreeable property assumption does not hold. Therefore, in this paper, scheduling of a single burn-in oven with non-agreeable release times and due dates along with non-identical job sizes as well as non-identical processing of time problem is formulated as a Non-Linear (0-1) Integer Programming optimisation problem. The objective measure of the problem is minimising the maximum completion time (makespan) of all jobs. Due to computational intractability, we have proposed four variants of a two-phase greedy heuristic algorithm. Computational experiments indicate that two out of four proposed algorithms have excellent average performance and also capable of solving any large-scale real life problems with a relatively low computational effort on a Pentium IV computer.

Computer-Aided Reliability Analysis of Complicated Networks

A computer-aided procedure is described for analyzing the reliability of complicated networks. This procedure breaks down a network into small subnetworks whose reliability can be more readily calculated. The subnetworks which are searched for are those with only two nodes; this allows the original network to be considerably simplified.

Computer-Aided Reliability Analysis of Complicated Networks

A computer-aided procedure is described for analyzing the reliability of complicated networks. This procedure breaks down a network into small subnetworks whose reliability can be more readily calculated. The subnetworks which are searched for are those with only two nodes; this allows the original network to be considerably simplified.

Variable Granularity Access Tracking Scheme for Improving the Performance of Software Transactional Memory

Software transactional memory (STM) has been proposed as a promising programming paradigm for shared memory multi-threaded programs as an alternative to conventional lock based synchronization primitives. Typical STM implementations employ a conflict detection scheme, which works with uniform access granularity, tracking shared data accesses either at word/cache line or at object level. It is well known that a single fixed access tracking granularity cannot meet the conflicting goals of reducing false conflicts without impacting concurrency adversely. A fine grained granularity while improving concurrency can have an adverse impact on performance due to lock aliasing, lock validation overheads, and additional cache pressure. On the other hand, a coarse grained granularity can impact performance due to reduced concurrency. Thus, in general, a fixed or uniform granularity access tracking (UGAT) scheme is application-unaware and rarely matches the access patterns of individual application or parts of an application, leading to sub-optimal performance for different parts of the application(s). In order to mitigate the disadvantages associated with UGAT scheme, we propose a Variable Granularity Access Tracking (VGAT) scheme in this paper. We propose a compiler based approach wherein the compiler uses inter-procedural whole program static analysis to select the access tracking granularity for different shared data structures of the application based on the application's data access pattern. We describe our prototype VGAT scheme, using TL2 as our STM implementation. Our experimental results reveal that VGAT-STM scheme can improve the application performance of STAMP benchmarks from 1.87% to up to 21.2%.

Optimum Load Shedding Through Programming Techniques

This paper obtains a new accurate model for sensitivity in power systems and uses it in conjunction with linear programming for the solution of load-shedding problems with a minimum loss of loads. For cases where the error in the sensitivity model increases, other linear programming and quadratic programming models have been developed, assuming currents at load buses as variables and not load powers. A weighted error criterion has been used to take priority schedule into account; it can be either a linear or a quadratic function of the errors, and depending upon the function appropriate programming techniques are to be employed.

Decision tree design and applications in speech processing

The design and operation of the minimum cost classifier, where the total cost is the sum of the measurement cost and the classification cost, is computationally complex. Noting the difficulties associated with this approach, decision tree design directly from a set of labelled samples is proposed in this paper. The feature space is first partitioned to transform the problem to one of discrete features. The resulting problem is solved by a dynamic programming algorithm over an explicitly ordered state space of all outcomes of all feature subsets. The solution procedure is very general and is applicable to any minimum cost pattern classification problem in which each feature has a finite number of outcomes. These techniques are applied to (i) voiced, unvoiced, and silence classification of speech, and (ii) spoken vowel recognition. The resulting decision trees are operationally very efficient and yield attractive classification accuracies.

Computer-aided analysis of high-speed protective relays

Most of the modern distance relays are designed to avoid overreaching due to the transient d.c. component of the fault current, whereas a more likely source of transients in e.h.v. systems is the oscillatory discharge of the system charging current into the fault. Until now attempts have not been made to reproduce these transients in the laboratory. This paper describes an analogue and an accurate digital simulation of these harmonic transients. The dynamic behaviour of a typical polarised mho-type relay is analysed, and results are presented. The paper also advocates the use of active filters for filtering the harmonics associated with e.h.v. system, and hence, to improve the speed of response and accuracy of the protective relays.

Computer simulation of liquid crystals

In this article we review the current status in the modelling of both thermotropic and lyotropic Liquid crystal. We discuss various coarse-graining schemes as well as simulation techniques such as Monte Carlo (MC) and Molecular dynamics (MD) simulations.In the area of MC simulations we discuss in detail the algorithm for simulating hard objects such as spherocylinders of various aspect ratios where excluded volume interaction enters in the simulation through overlap test. We use this technique to study the phase diagram, of a special class of thermotropic liquid crystals namely banana liquid crystals. Next we discuss a coarse-grain model of surfactant molecules and study the self-assembly of the surfactant oligomers using MD simulations. Finally we discuss an atomistically informed coarse-grained description of the lipid molecules used to study the gel to liquid crystalline phase transition in the lipid bilayer system.

Impact-Angle-Constrained Suboptimal Model Predictive Static Programming Guidance of Air-to-Ground Missiles

A nonlinear suboptimal guidance law is presented in this paper for successful interception of ground targets by air-launched missiles and guided munitions. The main feature of this guidance law is that it accurately satisfies terminal impact angle constraints in both azimuth as well as elevation simultaneously. In addition, it is capable of hitting the target with high accuracy as well as minimizing the lateral acceleration demand. The guidance law is synthesized using recently developed model predictive static programming (MPSP). Performance of the proposed MPSP guidance is demonstrated using three-dimensional (3-D) nonlinear engagement dynamics by considering stationary, moving, and maneuvering targets. Effectiveness of the proposed guidance has also been verified by considering first. order autopilot lag as well as assuming inaccurate information about target maneuvers. Multiple munitions engagement results are presented as well. Moreover, comparison studies with respect to an augmented proportional navigation guidance (which does not impose impact angle constraints) as well as an explicit linear optimal guidance (which imposes the same impact angle constraints in 3-D) lead to the conclusion that the proposed MPSP guidance is superior to both. A large number of randomized simulation studies show that it also has a larger capture region.

Null Dereference Verification via Over-approximated Weakest Pre-conditions Analysis

Null dereferences are a bane of programming in languages such as Java. In this paper we propose a sound, demand-driven, inter-procedurally context-sensitive dataflow analysis technique to verify a given dereference as safe or potentially unsafe. Our analysis uses an abstract lattice of formulas to find a pre-condition at the entry of the program such that a null-dereference can occur only if the initial state of the program satisfies this pre-condition. We use a simplified domain of formulas, abstracting out integer arithmetic, as well as unbounded access paths due to recursive data structures. For the sake of precision we model aliasing relationships explicitly in our abstract lattice, enable strong updates, and use a limited notion of path sensitivity. For the sake of scalability we prune formulas continually as they get propagated, reducing to true conjuncts that are less likely to be useful in validating or invalidating the formula. We have implemented our approach, and present an evaluation of it on a set of ten real Java programs. Our results show that the set of design features we have incorporated enable the analysis to (a) explore long, inter-procedural paths to verify each dereference, with (b) reasonable accuracy, and (c) very quick response time per dereference, making it suitable for use in desktop development environments.

An (O)over-bar(m(2)n) randomized algorithm to compute a minimum cycle basis of a directed graph

We consider the problem of computing a minimum cycle basis in a directed graph G. The input to this problem is a directed graph whose arcs have positive weights. In this problem a {- 1, 0, 1} incidence vector is associated with each cycle and the vector space over Q generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for its cycle space. A cycle basis where the sum of weights of the cycles is minimum is called a minimum cycle basis of G. The current fastest algorithm for computing a minimum cycle basis in a directed graph with m arcs and n vertices runs in O(m(w+1)n) time (where w < 2.376 is the exponent of matrix multiplication). If one allows randomization, then an (O) over tilde (m(3)n) algorithm is known for this problem. In this paper we present a simple (O) over tilde (m(2)n) randomized algorithm for this problem. The problem of computing a minimum cycle basis in an undirected graph has been well-studied. In this problem a {0, 1} incidence vector is associated with each cycle and the vector space over F-2 generated by these vectors is the cycle space of the graph. The fastest known algorithm for computing a minimum cycle basis in an undirected graph runs in O(m(2)n + mn(2) logn) time and our randomized algorithm for directed graphs almost matches this running time.

Trade determination in multi-attribute exchanges

Electronic exchanges are double-sided marketplaces that allow multiple buyers to trade with multiple sellers, with aggregation of demand and supply across the bids to maximize the revenue in the market. Two important issues in the design of exchanges are (1) trade determination (determining the number of goods traded between any buyer-seller pair) and (2) pricing. In this paper we address the trade determination issue for one-shot, multi-attribute exchanges that trade multiple units of the same good. The bids are configurable with separable additive price functions over the attributes and each function is continuous and piecewise linear. We model trade determination as mixed integer programming problems for different possible bid structures and show that even in two-attribute exchanges, trade determination is NP-hard for certain bid structures. We also make some observations on the pricing issues that are closely related to the mixed integer formulations.