Real-World Extensions To Scheduling Algorithms Based On Lagrangian Relaxation

Recently, efficient scheduling algorithms based on Lagrangian relaxation have been proposed for scheduling parallel machine systems and job shops. In this article, we develop real-world extensions to these scheduling methods. In the first part of the paper, we consider the problem of scheduling single operation jobs on parallel identical machines and extend the methodology to handle multiple classes of jobs, taking into account setup times and setup costs, The proposed methodology uses Lagrangian relaxation and simulated annealing in a hybrid framework, In the second part of the paper, we consider a Lagrangian relaxation based method for scheduling job shops and extend it to obtain a scheduling methodology for a real-world flexible manufacturing system with centralized material handling.

Phase Equilibria in the System $Al_{2}O_{3}-CaO-CoO$ and Gibbs Energy of Formation of $Ca_{3}CoAl_{4}O_{10}$

The floating-zone method with different growth ambiences has been used to selectively obtain hexagonal or orthorhombic DyMnO3 single crystals. The crystals were characterized by x-ray powder diffraction of ground specimens and a structure refinement as well as electron diffraction. We report magnetic susceptibility, magnetization and specific heat studies of this multiferroic compound in both the hexagonal and the orthorhombic structure. The hexagonal DyMnO3 shows magnetic ordering of Mn3+ (S = 2) spins on a triangular Mn lattice at T-N(Mn) = 57 K characterized by a cusp in the specific heat. This transition is not apparent in the magnetic susceptibility due to the frustration on the Mn triangular lattice and the dominating paramagnetic susceptibility of the Dy3+ (S = 9/2) spins. At T-N(Dy) = 3 K, a partial antiferromagnetic order of Dy moments has been observed. In comparison, the magnetic data for orthorhombic DyMnO3 display three transitions. The data broadly agree with results from earlier neutron diffraction experiments, which allows for the following assignment: a transition from an incommensurate antiferromagnetic ordering of Mn3+ spins at T-N(Mn) = 39 K, a lock-in transition at Tlock-in = 16 K and a second antiferromagnetic transition at T-N(Dy) = 5 K due to the ordering of Dy moments. Both the hexagonal and the orthorhombic crystals show magnetic anisotropy and complex magnetic properties due to 4f-4f and 4f-3d couplings.

Implicit and multigrid procedures for steady-state computations with upwind algorithms

A computational study for the convergence acceleration of Euler and Navier-Stokes computations with upwind schemes has been conducted in a unified framework. It involves the flux-vector splitting algorithms due to Steger-Warming and Van Leer, the flux-difference splitting algorithms due to Roe and Osher and the hybrid algorithms, AUSM (Advection Upstream Splitting Method) and HUS (Hybrid Upwind Splitting). Implicit time integration with line Gauss-Seidel relaxation and multigrid are among the procedures which have been systematically investigated on an individual as well as cumulative basis. The upwind schemes have been tested in various implicit-explicit operator combinations such that the optimal among them can be determined based on extensive computations for two-dimensional flows in subsonic, transonic, supersonic and hypersonic flow regimes. In this study, the performance of these implicit time-integration procedures has been systematically compared with those corresponding to a multigrid accelerated explicit Runge-Kutta method. It has been demonstrated that a multigrid method employed in conjunction with an implicit time-integration scheme yields distinctly superior convergence as compared to those associated with either of the acceleration procedures provided that effective smoothers, which have been identified in this investigation, are prescribed in the implicit operator.

Gibbs Energy of Formation of Cobalt Divanadium Tetroxide

The Gibbs energy of formation of V2O3-saturated spinel CoV2O4 has been measured in the temperature range 900–1700 K using a solid state galvanic cell, which can be represented as Pt, Co + CoV2O4 + V2O3/(CaO) ZrO2/Co + CoO, Pt. The standard free energy of formation of cobalt vanadite from component oxides can be represented as CoO (rs) + V2O3 (cor) → CoV2O4 (sp), ΔG° = −30,125 − 5.06T (± 150) J mole−1. Cation mixing on crystallographically nonequivalent sites of the spinel is responsible for the decrease in free energy with increasing temperature. A correlation between “second law” entropies of formation of cubic 2–3 spinels from component oxides with rock salt and corundum structures and cation distribution is presented. Based on the information obtained in this study and trends in the stability of aluminate and chromite spinels, it can be deduced that copper vanadite is unstable.

Practical Algorithms For Mean Velocity Estimation In Pulse Doppler Weather Radars Using A Small Number Of Samples

Doppler weather radars with fast scanning rates must estimate spectral moments based on a small number of echo samples. This paper concerns the estimation of mean Doppler velocity in a coherent radar using a short complex time series. Specific results are presented based on 16 samples. A wide range of signal-to-noise ratios are considered, and attention is given to ease of implementation. It is shown that FFT estimators fare poorly in low SNR and/or high spectrum-width situations. Several variants of a vector pulse-pair processor are postulated and an algorithm is developed for the resolution of phase angle ambiguity. This processor is found to be better than conventional processors at very low SNR values. A feasible approximation to the maximum entropy estimator is derived as well as a technique utilizing the maximization of the periodogram. It is found that a vector pulse-pair processor operating with four lags for clear air observation and a single lag (pulse-pair mode) for storm observation may be a good way to estimate Doppler velocities over the entire gamut of weather phenomena.

Ant Colony Optimization Algorithms for Shortest Path Problems

We propose four variants of recently proposed multi-timescale algorithm in [1] for ant colony optimization and study their application on a multi-stage shortest path problem. We study the performance of the various algorithms in this framework. We observe, that one of the variants consistently outperforms the algorithm [1].

Improved Algorithms for Reservoir Capacity Calculation Incorporating Storage-Dependent Losses and Reliability Norm

Two algorithms that improve upon the sequent-peak procedure for reservoir capacity calculation are presented. The first incorporates storage-dependent losses (like evaporation losses) exactly as the standard linear programming formulation does. The second extends the first so as to enable designing with less than maximum reliability even when allowable shortfall in any failure year is also specified. Together, the algorithms provide a more accurate, flexible and yet fast method of calculating the storage capacity requirement in preliminary screening and optimization models.

On the direct parallel solution of systems of linear equations: New algorithms and systolic structures

The paper presents two new algorithms for the direct parallel solution of systems of linear equations. The algorithms employ a novel recursive doubling technique to obtain solutions to an nth-order system in n steps with no more than 2n(n −1) processors. Comparing their performance with the Gaussian elimination algorithm (GE), we show that they are almost 100% faster than the latter. This speedup is achieved by dispensing with all the computation involved in the back-substitution phase of GE. It is also shown that the new algorithms exhibit error characteristics which are superior to GE. An n(n + 1) systolic array structure is proposed for the implementation of the new algorithms. We show that complete solutions can be obtained, through these single-phase solution methods, in 5n−log2n−4 computational steps, without the need for intermediate I/O operations.

A study of placement algorithms through trial interchange of logic modules

Based on trial interchanges, this paper develops three algorithms for the solution of the placement problem of logic modules in a circuit. A significant decrease in the computation time of such placement algorithms can be achieved by restricting the trial interchanges to only a subset of all the modules in a circuit. The three algorithms are simulated on a DEC 1090 system in Pascal and the performance of these algorithms in terms of total wirelength and computation time is compared with the results obtained by Steinberg, for the 34-module backboard wiring problem. Performance analysis of the first two algorithms reveals that algorithms based on pairwise trial interchanges (2 interchanges) achieve a desired placement faster than the algorithms based on trial N interchanges. The first two algorithms do not perform better than Steinberg's algorithm1, whereas the third algorithm based on trial pairwise interchange among unconnected pairs of modules (UPM) and connected pairs of modules (CPM) performs better than Steinberg's algorithm, both in terms of total wirelength (TWL) and computation time.

SHAMP: An experimental shared memory multimicroprocessor system for performance evaluation of parallel algorithms

In this paper, the design and implementation of a single shared bus, shared memory multiprocessing system using Intel's single board computers is presented. The hardware configuration and the operating system developed to execute the parallel algorithms are discussed. The performance evaluation studies carried out on Image are outlined.

Efficient algorithms for computing Reeb graphs

The Reeb graph tracks topology changes in level sets of a scalar function and finds applications in scientific visualization and geometric modeling. We describe an algorithm that constructs the Reeb graph of a Morse function defined on a 3-manifold. Our algorithm maintains connected components of the two dimensional levels sets as a dynamic graph and constructs the Reeb graph in O(nlogn+nlogg(loglogg)3) time, where n is the number of triangles in the tetrahedral mesh representing the 3-manifold and g is the maximum genus over all level sets of the function. We extend this algorithm to construct Reeb graphs of d-manifolds in O(nlogn(loglogn)3) time, where n is the number of triangles in the simplicial complex that represents the d-manifold. Our result is a significant improvement over the previously known O(n2) algorithm. Finally, we present experimental results of our implementation and demonstrate that our algorithm for 3-manifolds performs efficiently in practice.

Simplified algorithms based on Haar transforms for signal recognition in protective relays

This letter presents the development of simplified algorithms based on Haar functions for signal extraction in relaying signals. These algorithms, being computationally simple, are better suited for microprocessor-based power system protection relaying. They provide accurate estimates of the signal amplitude and phase.

Gibbs energies of formation of rare earth oxysulfides

The standard Gibbs energy change accompanying the conversion of rare earth oxides to oxysulfides by reaction of rare earth oxides with diatomic sulfur gas has been measured in the temperature range 870 to 1300 K using the solid state cell: Pt/Cu+Cu2S/R2O2S+R2O3‖(CaO)ZrO2‖Ni+NiO, Pt where R=La, Nd, Sm, Gd, Tb, and Dy. The partial pressure of diatomic sulfur over a mixture of rare earth oxide (R2O3) and oxysulfide (R2O2S) is fixed by the dissociation of Cu2S to Cu in a closed system. The buffer mixture of Cu+Cu2S is physically separated from the rare earth oxide and oxysulfide to avoid complications arising from interaction between them. The corresponding equilibrium oxygen partial pressure is measured with an oxide solid electrolyte cell. Gibbs energy change for the conversion of oxide to the corresponding oxysulfide increases monotonically with atomic number of the rare earth element. Second law enthalpy of formation also shows a similar trend. Based on this empirical trend Gibbs energies of formation of oxysulfides of Pr, Eu, Ho, and Er are estimated as a function of temperature.

Parallel polygon scan conversion algorithms: Performance evaluation on a shared bus architecture

In this paper, three parallel polygon scan conversion algorithms have been proposed, and their performance when executed on a shared bus architecture has been compared. It has been shown that the parallel algorithm that does not use edge coherence performs better than those that use edge coherence. Further, a multiprocessing architecture has been proposed to execute the parallel polygon scan conversion algorithms more efficiently than a single shared bus architecture.

Implementation of CSP-S for description of distributed algorithms

The implementation of CSP-S (a subset of CSP)—a high level language for distributed programming—is presented in this paper. The language CSP-S features a parallel command, communication by message passing and the use of guarded command. The implementation consists of a compiler translating the CSP-S constructs into intermediate language. The execution is carried out by a scheduler which creates an illusion of concurrency. Using the CSP-S language constructs, distributed algorithms are written, executed and tested with the compiler designed.