Scheduling parallel batch processors with incompatible job families using ant colony optimization

The present work concerns with the static scheduling of jobs to parallel identical batch processors with incompatible job families for minimizing the total weighted tardiness. This scheduling problem is applicable in burn-in operations and wafer fabrication in semiconductor manufacturing. We decompose the problem into two stages: batch formation and batch scheduling, as in the literature. The Ant Colony Optimization (ACO) based algorithm called ATC-BACO algorithm is developed in which ACO is used to solve the batch scheduling problems. Our computational experimentation shows that the proposed ATC-BACO algorithm performs better than the available best traditional dispatching rule called ATC-BATC rule.

Effect of coordinated ions on structure and flexibility of parallel G-quadruplexes: A molecular dynamics study

ingle tract guanine residues can associate to form stable parallel quadruplex structures in the presence of certain cations. Nanosecond scale molecular dynamics simulations have been performed on fully solvated fibre model of parallel d(G(7)) quadruplex structures with Na+ or K+ ions coordinated in the cavity formed by the O6 atoms of the guanine bases. The AMBER 4.1 force field and Particle Mesh Ewald technique for electrostatic interactions have been used in all simulations. There quadruplex structures are stable during the simulation, with the middle four base tetrads showing root mean square deviation values between 0.5 to 0.8 Angstrom from the initial structure as well the high resolution crystal structure. Even in the absence of any coordinated ion in the initial structure, the G-quadruplex structure remains intact throughout the simulation. During the 1.1 ns MD simulation, one Nai counter ion from the solvent as well as several water molecules enter the central cavity to occupy the empty coordination sites within the parallel quadruplex and help stabilize the structure. Hydrogen bonding pattern depends on the nature of the coordinated ion, with the G-tetrad undergoing local structural variation to accommodate cations of different sizes. in the absence of any coordinated ion. due to strong mutual repulsion, O6 atoms within G-tetrad are forced farther apart from each other, which leads to a considerably different hydrogen bonding scheme within the G-tetrads and very favourable interaction energy between the guanine bases constituting a G-tetrad. However, a coordinated ion between G-tetrads provides extra stacking energy for the G-tetrads and makes the quadruplex structure more rigid. Na+ ions, within the quadruplex cavity, are more mobile than coordinated K+ ions. A number of hydrogen bonded water molecules are observed within the grooves of all quadruplex structures.

Parallel circuit partitioning on a reduced array architecture

The physical design of a VLSI circuit involves circuit partitioning as a subtask. Typically, it is necessary to partition a large electrical circuit into several smaller circuits such that the total cross-wiring is minimized. This problem is a variant of the more general graph partitioning problem, and it is known that there does not exist a polynomial time algorithm to obtain an optimal partition. The heuristic procedure proposed by Kernighan and Lin1,2 requires O(n2 log2n) time to obtain a near-optimal two-way partition of a circuit with n modules. In the VLSI context, due to the large problem size involved, this computational requirement is unacceptably high. This paper is concerned with the hardware acceleration of the Kernighan-Lin procedure on an SIMD architecture. The proposed parallel partitioning algorithm requires O(n) processors, and has a time complexity of O(n log2n). In the proposed scheme, the reduced array architecture is employed with due considerations towards cost effectiveness and VLSI realizability of the architecture.The authors are not aware of any earlier attempts to parallelize a circuit partitioning algorithm in general or the Kernighan-Lin algorithm in particular. The use of the reduced array architecture is novel and opens up the possibilities of using this computing structure for several other applications in electronic design automation.

Groove Binding Ligands for the Interaction with Parallel-Stranded ps-Duplex DNA and Triplex DNA

DNA adopts different conformations not only based on novel base pairs, but also with different chain polarities. Besides several duplex structures (A, B, Z, parallel stranded (ps)-DNA, etc.), DNA also forms higher-order structures like triplex, tetraplex, and i-motif. Each of these structures has its own biological significance. The ps-duplexes have been found to be resistant to certain nucleases and endonucleases. Molecules that promote triple-helix formation have significant potential. These investigations have many therapeutic advantages which may be useful in the regulation of the expression of genes responsible for certain diseases by locking either their transcription (antigene) or translation (antisense). Each DNA minor groove binding ligand (MGBL) interacts with DNA through helical minor groove recognition in a sequence-specific manner, and this interferes with several DNA-associated processes. Incidentally, these ligands interact with some non-B-DNA and with higher-order DNA structures including ps-DNA and triplexes. While the design and recognition of minor grooves of duplex DNA by specific MGBLs have been a topic of many reports, limited information is available on the binding behavior of MGBLs with nonduplex DNA. In this review, we summarize various attempts of the interaction of MGBLs with ps-DNA and DNA triplexes.

A Simple Five-Level Inverter Topology for Induction Motor Drive Using Conventional Two-Level Inverters and Flying Capacitor Technique

This paper proposes a new five-level inverter topology for open-end winding induction motor (IM) drive. The popular existing circuit configurations for five-level inverter include the NPC inverter and flying capacitor topologies. Compared to the NPC inverter, the proposed topology eliminates eighteen clamping diodes having different voltage ratings in the present circuit. Moreover it requires only one capacitor bank per phase, whereas flying capacitor schemes for five level topologies require six capacitor banks per phase. The proposed topology is realized by feeding the phase winding of an open-end induction motor with two-level inverters in series with flying capacitors. The flying capacitor voltages are balanced using the switching state redundancy for full modulation range. The proposed inverter scheme is capable of producing two-level to five-level pulse width modulated voltage across the phase winding depending on the modulation range. Additionally, in case of any switch failure in the flying capacitor connection, the proposed inverter topology can be operated as a three-level inverter for full modulation range. The proposed scheme is experimentally verified on a four pole, 5hp induction motor drive.

A parallel multistep predictor-corrector algorithm for solving ordinary differential equations

In this paper we give a generalized predictor-corrector algorithm for solving ordinary differential equations with specified initial values. The method uses multiple correction steps which can be carried out in parallel with a prediction step. The proposed method gives a larger stability interval compared to the existing parallel predictor-corrector methods. A method has been suggested to implement the algorithm in multiple processor systems with efficient utilization of all the processors.

A Computationally Efficient PWM Algorithm for Multilevel Inverters

Centred space vector PWM (CSVPWM) technique is popularly used for three level voltage source inverters. The reference voltage vector is synthesized by time-averaging of the three nearest voltage vectors produced by the inverter. Identifying the three voltage vectors, and calculation of the dwelling time for each vector are both computationally intensive. This paper analyses the process of PWM generation in CSVPWM. This analysis breaks up a three-level inverter into six different conceptual two level inverters in different regions of the fundamental cycle. Control of 3-level inverter is viewed as the control of the appropriate 2-level inverter. The analysis leads to a systematic simplification of the computations involved, finally resulting in a computationally efficient PWM algorithm. This algorithm exploits the equivalence between triangle comparison and space vector approaches to PWM generation. This algorithm does not involve any 3-phase/2-phase or 2-phase/3-phase transformation. This also does not involve any transformation from rectangular to polar coordinates, and vice versa. Further no evaluation of trigonometric functions is necessary. This algorithm also provides for the mitigation of DC neutral point unbalance, and is well suited to digital implementation. Simulation and experimental results are presented.

Flow And Heat-Transfer Over An Upstream Moving Wall With A Magnetic-Field And A Parallel Free Stream

The flow and heat transfer over an upstream moving non-isothermal wall with a parallel free stream have been considered. The magnetic field has been applied in the free stream parallel to the wall and the effect of induced magnetic field has been included in the analysis. The boundary layer equations governing the steady incompressible electrically conducting fluid flow have been solved numerically using a shooting method. This problem is interesting because a solution exists only when the ratio of the wall velocity does not exceed a certain critical value and this critical value depends on the magnetic field and magnetic Prandtl number. Also dual solutions exist for a certain range of wall velocity.

A Hybrid Multilevel Inverter Topology for an Open-End Winding Induction-Motor Drive Using Two-Level Inverters in Series With a Capacitor-Fed H-Bridge Cell

In this paper, a new five-level inverter topology for open-end winding induction-motor (IM) drive is proposed. The open-end winding IM is fed from one end with a two-level inverter in series with a capacitor-fed H-bridge cell, while the other end is connected to a conventional two-level inverter. The combined inverter system produces voltage space-vector locations identical to that of a conventional five-level inverter. A total of 2744 space-vector combinations are distributed over 61 space-vector locations in the proposed scheme. With such a high number of switching state redundancies, it is possible to balance the H-bridge capacitor voltages under all operating conditions including overmodulation region. In addition to that, the proposed topology eliminates 18 clamping diodes having different voltage ratings compared with the neutral point clamped inverter. On the other hand, it requires only one capacitor bank per phase, whereas the flying-capacitor scheme for a five-level topology requires more than one capacitor bank per phase. The proposed inverter topology can be operated as a three-level inverter for full modulation range, in case of any switch failure in the capacitor-fed H-bridge cell. This will increase the reliability of the system. The proposed scheme is experimentally verified on a four-pole 5-hp IM drive.

Parallel min-cut placement on reduced hardware SIMD architecture.

Massively parallel SIMD computing is applied to obtain an order of magnitude improvement in the executional speed of an important algorithm in VLSI design automation. The physical design of a VLSI circuit involves logic module placement as a subtask. The paper is concerned with accelerating the well known Min-cut placement technique for logic cell placement. The inherent parallelism of the Min-cut algorithm is identified, and it is shown that a parallel machine based on the efficient execution of the placement procedure.

Visualisation of a 2′-5′ parallel stranded double helix at atomic resolution: crystal structure of cytidylyl-2′,5′-adenosine

X-ray crystallographlc studies on 3′–5′ ollgomers have provided a great deal of information on the stereochemistry and conformational flexibility of nucleic acids and polynucleotides. In contrast, there is very little Information available on 2′–5′ polynucleotides. We have now obtained the crystal structure of Cytidylyl-2′,5′-Adenoslne (C2′p5′A) at atomic resolution to establish the conformational differences between these two classes of polymers. The dlnucleoside phosphate crystallises in the monocllnlc space group C2, with a = 33.912(4)Å, b =16.824(4)Å, c = 12.898(2)Å and 0 = 112.35(1) with two molecules in the asymmetric unit. Spectacularly, the two independent C2′p5′A molecules in the asymmetric unit form right handed miniature parallel stranded double helices with their respective crystallographic two fold (b axis) symmetry mates. Remarkably, the two mini duplexes are almost indistinguishable. The cytosines and adenines form self-pairs with three and two hydrogen bonds respectively. The conformation of the C and A residues about the glycosyl bond is anti same as in the 3′–5′ analog but contrasts the anti and syn geometry of C and A residues in A2′p5′C. The furanose ring conformation is C3′endo, C2′endo mixed puckering as in the C3′p5′A-proflavine complex. A comparison of the backbone torsion angles with other 2′–5′ dinucleoside structures reveals that the major deviations occur in the torsion angles about the C3′–C2′ and C4′-C3′ bonds. A right-handed 2′–5′ parallel stranded double helix having eight base pairs per turn and 45° turn angle between them has been constructed using this dinucleoside phosphate as repeat unit. A discussion on 2′–5′ parallel stranded double helix and its relevance to biological systems is presented.

Filter Optimization for Grid Interactive Voltage Source Inverters

Higher order LCL filters are essential in meeting the interconnection standard requirement for grid-connected voltage source converters. LCL filters offer better harmonic attenuation and better efficiency at a smaller size when compared to the traditional L filters. The focus of this paper is to analyze the LCL filter design procedure from the point of view of power loss and efficiency. The IEEE 1547-2008 specifications for high-frequency current ripple are used as a major constraint early in the design to ensure that all subsequent optimizations are still compliant with the standards. Power loss in each individual filter component is calculated on a per-phase basis. The total inductance per unit of the LCL filter is varied, and LCL parameter values which give the highest efficiency while simultaneously meeting the stringent standard requirements are identified. The power loss and harmonic output spectrum of the grid-connected LCL filter is experimentally verified, and measurements confirm the predicted trends.

Effect of coordinated ions on structure and flexiblity of parallel G-quandruplexes: a molecular dynamics study

Single tract guanine residues can associate to form stable parallel quadruplex structures in the presence of certain cations. Nanosecond scale molecular dynamics simulations have been performed on fully solvated fibre model of parallel d(G7) quadruplex structures with Na+ or K+ ions coordinated in the cavity formed by the 06 atoms of the guanine bases. The AMBER 4.1 force field and Particle Mesh Ewald technique for electrostatic interactions have been used in all simulations. These quadruplex structures are stable during the simulation, with the middle four base tetrads showing root mean square deviation values between 0.5 to 0.8 A from the initial structure as well the high resolution crystal structure. Even in the absence of any coordinated ion in the initial structure, the G-quadruplex structure remains intact throughout the simulation. During the 1.1 ns MD simulation, one Na+ counter ion from the solvent as well as several water molecules enter the central cavity to occupy the empty coordination sites within the parallel quadruplex and help stabilize the structure. Hydrogen bonding pattern depends on the nature of the coordinated ion, with the G-tetrad undergoing local structural variation to accommodate cations of different sizes. In the absence of any coordinated ion, due to strong mutual repulsion, 06 atoms within G-tetrad are forced farther apart from each other, which leads to a considerably different hydrogen bonding scheme within the G-tetrads and very favourable interaction energy between the guanine bases constituting a G-tetrad. However, a coordinated ion between G-tetrads provides extra stacking energy for the G-tetrads and makes the quadruplex structure more rigid. Na+ ions, within the quadruplex cavity, are more mobile than coordinated K+ ions. A number of hydrogen bonded water molecules are observed within the grooves of all quadruplex structures

An optimal parallel algorithm for sparse matrix bandwidth reduction on a linear array

A simple and efficient algorithm for the bandwidth reduction of sparse symmetric matrices is proposed. It involves column-row permutations and is well-suited to map onto the linear array topology of the SIMD architectures. The efficiency of the algorithm is compared with the other existing algorithms. The interconnectivity and the memory requirement of the linear array are discussed and the complexity of its layout area is derived. The parallel version of the algorithm mapped onto the linear array is then introduced and is explained with the help of an example. The optimality of the parallel algorithm is proved by deriving the time complexities of the algorithm on a single processor and the linear array.