Minimizing total completion time on batch processing machines

We study the problem of minimizing total completion time on single and parallel batch processing machines. A batch processing machine is one which can process up to B jobs simultaneously. The processing time of a batch is equal to the largest processing time among all jobs in the batch. This problem is motivated by burn-in operations in the final testing stage of semiconductor manufacturing and is expected to occur in other production environments. We provide an exact solution procedure for the single-machine problem and heuristic algorithms for both single and parallel machine problems. While the exact algorithms have limited applicability due to high computational requirements, extensive experiments show that the heuristics are capable of consistently obtaining near-optimal solutions in very reasonable CPU times.

Rectilinear Path Following in 3D Space

This paper addresses the problem of determining an optimal (shortest) path in three dimensional space for a constant speed and turn-rate constrained aerial vehicle, that would enable the vehicle to converge to a rectilinear path, starting from any arbitrary initial position and orientation. Based on 3D geometry, we propose an optimal and also a suboptimal path planning approach. Unlike the existing numerical methods which are computationally intensive, this optimal geometrical method generates an optimal solution in lesser time. The suboptimal solution approach is comparatively more efficient and gives a solution that is very close to the optimal one. Due to its simplicity and low computational requirements this approach can be implemented on an aerial vehicle with constrained turn radius to reach a straight line with a prescribed orientation as required in several applications. But, if the distance between the initial point and the straight line to be followed along the vertical axis is high, then the generated path may not be flyable for an aerial vehicle with limited range of flight path angle and we resort to a numerical method for obtaining the optimal solution. The numerical method used here for simulation is based on multiple shooting and is found to be comparatively more efficient than other methods for solving such two point boundary value problem.

Code Generation Paradigms On Optical Orthogonal And Other Codes In a Fiber Optic CDMA Lan

Code Division Multiple Access (CDMA) techniques, by far, had been applied to LAN problems by many investigators, An analytical study of well known algorithms for generation of Orthogonal codes used in FO-CDMA systems like those for prime, quasi-Prime, Optical Orthogonal and Matrix codes has been presented, Algorithms for OOCs like Greedy/Modified Greedy/Accelerated Greedy algorithms are implemented. Many speed-up enhancements. for these algorithms are suggested. A novel Synthetic Algorithm based on Difference Sets (SADS) is also proposed. Investigations are made to vectorise/parallelise SADS to implement the source code on parallel machines. A new matrix for code families of OOCs with different seed code-words but having the same (n,w,lambda) set is formulated.

Orientational disorder and other aspects of C70 and C60-C70 films deposited on single-crystal substrates

C-70 films deposited on highly oriented pyrolytic graphite (HOPG), Ag(110), Ag(111) and Pt(110) substrates have been investigated by scanning tunnelling microscopy. Interesting observations on novel molecular arrangements, as well as orientational disorder, are presented. Solid solutions of C-60 and C-70 show interesting packing of these molecules when deposited on HOPG.

Oriented films of LaNiO3 and other members of the Lan+1NinO3n+1 series, LaCuO3−δ and Pb(Zr0.52Ti0.48)O3, obtained by nebulized spray pyrolysis

The technique of nebulized spray pyrolysis has been explored to find out whether oriented films of certain important oxides can be produced on single-crystal substrates by this relatively gentle method. Starting with acetylacetonate precursors, oriented films of metallic LaNiO3 containing nearly spherical grains (30 nm) have been obtained. Films of near-stoichiometric La4Ni3O10 and La3Ni2O7 showing metallic conductivity have been obtained by this method. This is indeed gratifying since it is difficult to prepare monophasic and stoichiometric bulk samples of these materials. Films of La2NiO4 show the expected semiconducting behavior. In the La-Cu-O system, starting with acetylacetonates, we have obtained films mainly comprising semiconducting La2Cu2O5, which is generally difficult to prepare in bulk form. More interestingly, nebulized spray pyrolysis gives excellent stoichiometric films of Pb(Zr0.52Ti0.48)O-3 consisting of nearly spherical grains (30 nm) which show ferroelectric behavior. The present investigation demonstrates that nebulized spray pyrolysis provides a useful and desirable route to deposite oriented films of complex oxide materials on single-crystal substrates.

Queuing strategies for qos management of traffic between lans interconnected by low-speed wan links

We provide a comparative performance evaluation of packet queuing and link admission strategies for low-speed wide area network Links (e.g. 9600 bps, 64 kbps) that interconnect relatively highspeed, connectionless local area networks (e.g. 10 Mbps). In particular, we are concerned with the problem of providing differential quality of service to interLAN remote terminal and file transfer sessions, and throughput fairness between interLAN file transfer sessions. We use analytical and simulation models to study a variety of strategies. Our work also serves to address the performance comparison of connectionless vs. connection-oriented interconnection of CLNS LANS. When provision of priority at the physical transmission level is not feasible, we show, for low-speed WAN links (e.g. 9600 bps), the superiority of connection-oriented interconnection of connectionless LANs, with segregation of traffic streams with different QoS requirements into different window flow controlled connections. Such an implementation can easily be obtained by transporting IP packets over an X.25 WAN. For 64 kbps WAN links, there is a drop in file transfer throughputs, owing to connection overheads, but the other advantages are retained, The same solution also helps to provide throughput fairness between interLAN file transfer sessions. We also provide a corroboration of some of our modelling results with results from an experimental test-bed.

Study of Carbon Nanocapsules (Onions) and Spherulitic Graphite by Stm and Other Techniques

A scanning tunneling microscopy study of carbon nanocapsules (onions) is reported for the first time. Spherulitic graphite is shown to be purely crystalline graphite based on X-ray diffraction and electron microscopy studies.

Thermodynamic modeling to analyse composition of carbonaceous coatings of MnO and other oxides of manganese grown by MOCVD

Equilibrium thermodynamic analysis has been applied to the low-pressure MOCVD process using manganese acetylacetonate as the precursor. ``CVD phase stability diagrams'' have been constructed separately for the processes carried out in argon and oxygen ambient, depicting the compositions of the resulting films as functions of CVD parameters. For the process conduced in argon ambient, the analysis predicts the simultaneous deposition of MnO and elemental carbon in 1: 3 molar proportion, over a range of temperatures. The analysis predicts also that, if CVD is carried out in oxygen ambient, even a very low flow of oxygen leads to the complete absence of carbon in the film deposited oxygen, with greater oxygen flow resulting in the simultaneous deposition of two different manganese oxides under certain conditions. The results of thermodynamic modeling have been verified quantitatively for low-pressure CVD conducted in argon ambient. Indeed, the large excess of carbon in the deposit is found to constitute a MnO/C nanocomposite, the associated cauliflower-like morphology making it a promising candidate for electrode material in supercapacitors. CVD carried out in oxygen flow, under specific conditions, leads to the deposition of more than one manganese oxide, as expected from thermodynamic analysis ( and forming an oxide-oxide nanocomposite). These results together demonstrate that thermodynamic analysis of the MOCVD process can be employed to synthesize thin films in a predictive manner, thus avoiding the inefficient trial-and-error method usually associated with MOCVD process development. The prospect of developing thin films of novel compositions and characteristics in a predictive manner, through the appropriate choice of CVD precursors and process conditions, emerges from the present work.

Subquadratic quantum number dependence and other anomalies of vibrational dephasing in liquid nitrogen: Molecular dynamics simulation study from the triple point to the critical point and beyond

Vibrational phase relaxation near gas-liquid and liquid-solid phase coexistence has been studied by molecular dynamics simulations of N-N stretch in N-2. Experimentally observed pronounced insensitivity of phase relaxation from the triple point to beyond the boiling point is found to originate from a competition between density relaxation and resonant-energy transfer terms. The sharp rise in relaxation rate near the critical point (CP) can be attributed at least partly to the sharp, rise in vibration-rotation coupling contribution. Substantial subquadratic quantum number dependence of overtone dephasing rate is found near the CP and in supercritical fluids. [S0031-9007 (99)09318-7].

Structural investigation of combustion synthesized Cu/CeO2 catalysts by EXAFS and other physical techniques: Formation of a Ce1-xCuxO2-delta solid solution

The structure and chemical environment of Cu in Cu/CeO2 catalysts synthesized by the solution combustion method have been investigated by X-ray diffraction (XRD), transmission electron microscopy (TEM), electron paramagnetic resonance (EPR) spectroscopy, X-ray photoelectron spectroscopy (XPS), cyclic voltammetry (CV), and extended X-ray fine structure (EXAFS) spectroscopy. High-resolution XRD studies of 3 and 5 atom % Cu/CeO2 do not show CuO lines in their respective patterns. The structure could be refined for the composition Ce1-xCuxO2-delta (x = 0.03 and 0.05; delta similar to 0.13 and 0.16) in the fluorite structure with 5-8% oxide ion vacancy. High-resolution TEM did not show CuO particles in 5 atom % Cu/CeO2. EPR as well as XPS studies confirm the presence of Cu2+ species in the CeO2 matrix. Redox potentials of Cu species in the CeO2 matrix are lower than those in CuO. EXAFS investigations of these catalysts show an average coordination number of 3 around the Cu2+ ion in the first shell at a distance of 1.96 Angstrom, indicating the O2- ion vacancy around the Cu2+ ion. The Cu-O bond length also decreases compared to that in CuO. The second and third shell around the Cu2+ ion in the catalysts are attributed to -Cu2+-O2--Cu2+ - at 2.92 Angstrom and -Cu2+-O2--Ce4+- at the distance of 3.15 Angstrom, respectively. The present results provide direct evidence for the formation of a Ce1-xCuxO2-delta type of solid solution phase having -square-Cu2+-O-Ce4+- kind of linkages.

The requirements for Ca2+, protein phosphorylation and concurrent protein synthesis for zeatin signaling of acidic chitinase transcript accumulation in Cucumis sativus L

We have previously reported that both Ca2+ and staurosporine-sensitive protein kinase(s) are involved in the cytokinin zeatin induction of cucumber chitinase activity and its protein content (Barwe et al. 2001). To further characterize signal transduction events involved in this cytokinin induction of chitinase gene expression, Northern hybridizations of total RNAs prepared from excised, dark-grown cucumber cotyledons treated with cytokinins and/or various agonists and antagonists of signal transduction components, were carried out using a cucumber acidic chitinase (CACHT) cDNA probe (Metraux et al. 1989). CACHT mRNA increased by approximately 5- to 6-fold in response to exogenous zeatin (Z), zeatin riboside (ZR), and benzyladenine (BA) treatment, but failed to accumulate in response to kinetin (K). Among the cytokinins tested, Z was most effective. The Z-induced accumulation of CACHT mRNA was inhibited by a plasma membrane Ca2+ channel blocker verapamil. Treatment of cotyledons with exogenous CaCl2 and calcium ionophore A23187 in the presence and absence of cytokinin enhanced CACHT mRNA accumulation. These two observations suggest the participation of extracellular calcium in signaling Z-induction. Furthermore, the presence of staurosporine (an inhibitor of protein kinase) in Z treatment reduced CACHT mRNA, suggesting the involvement of phosphorylation of one or more cellular proteins. In addition, we provide evidence that the Z-induction of CACHT mRNA is blocked by protein synthesis inhibitor cycloheximide treatment. Taken together, these results suggest that Ca2+ influx from extracellular space, protein phosphorylation, and concurrent protein synthesis events participate in cytokinin signaling during Z-induced CACHT transcript accumulation.

A Convex Optimization Framework for Almost Budget Balanced Allocation of a Divisible Good

We address the problem of allocating a single divisible good to a number of agents. The agents have concave valuation functions parameterized by a scalar type. The agents report only the type. The goal is to find allocatively efficient, strategy proof, nearly budget balanced mechanisms within the Groves class. Near budget balance is attained by returning as much of the received payments as rebates to agents. Two performance criteria are of interest: the maximum ratio of budget surplus to efficient surplus, and the expected budget surplus, within the class of linear rebate functions. The goal is to minimize them. Assuming that the valuation functions are known, we show that both problems reduce to convex optimization problems, where the convex constraint sets are characterized by a continuum of half-plane constraints parameterized by the vector of reported types. We then propose a randomized relaxation of these problems by sampling constraints. The relaxed problem is a linear programming problem (LP). We then identify the number of samples needed for ``near-feasibility'' of the relaxed constraint set. Under some conditions on the valuation function, we show that value of the approximate LP is close to the optimal value. Simulation results show significant improvements of our proposed method over the Vickrey-Clarke-Groves (VCG) mechanism without rebates. In the special case of indivisible goods, the mechanisms in this paper fall back to those proposed by Moulin, by Guo and Conitzer, and by Gujar and Narahari, without any need for randomization. Extension of the proposed mechanisms to situations when the valuation functions are not known to the central planner are also discussed. Note to Practitioners-Our results will be useful in all resource allocation problems that involve gathering of information privately held by strategic users, where the utilities are any concave function of the allocations, and where the resource planner is not interested in maximizing revenue, but in efficient sharing of the resource. Such situations arise quite often in fair sharing of internet resources, fair sharing of funds across departments within the same parent organization, auctioning of public goods, etc. We study methods to achieve near budget balance by first collecting payments according to the celebrated VCG mechanism, and then returning as much of the collected money as rebates. Our focus on linear rebate functions allows for easy implementation. The resulting convex optimization problem is solved via relaxation to a randomized linear programming problem, for which several efficient solvers exist. This relaxation is enabled by constraint sampling. Keeping practitioners in mind, we identify the number of samples that assures a desired level of ``near-feasibility'' with the desired confidence level. Our methodology will occasionally require subsidy from outside the system. We however demonstrate via simulation that, if the mechanism is repeated several times over independent instances, then past surplus can support the subsidy requirements. We also extend our results to situations where the strategic users' utility functions are not known to the allocating entity, a common situation in the context of internet users and other problems.