An improved approximation algorithm for the two-machine open shop scheduling problem with family setup times

We consider the problem of scheduling families of jobs in a two-machine open shop so as to minimize the makespan. The jobs of each family can be partitioned into batches and a family setup time on each machine is required before the first job is processed, and when a machine switches from processing a job of some family to a job of another family. For this NP-hard problem the literature contains (5/4)-approximation algorithms that cannot be improved on using the class of group technology algorithms in which each family is kept as a single batch. We demonstrate that there is no advantage in splitting a family more than once. We present an algorithm that splits one family at most once on a machine and delivers a worst-case performance ratio of 6/5.

Approximation results for flow shop scheduling problems with machine availability constraints

This paper considers two-machine flow shop scheduling problems with machine availability constraints. When the processing of a job is interrupted by an unavailability period of a machine, we consider both the resumable scenario in which the processing can be resumed when the machine next becomes available, and the semi-resumable scenario in which some portion of the processing is repeated but the job is otherwise resumable. For the problem with several non-availability intervals on the first machine under the resumable scenario, we present a fast (3/2)-approximation algorithm. For the problem with one non-availability interval under the semi-resumable scenario, a polynomial-time approximation scheme is developed.

Two simple constant ratio approximation algorithms for minimizing the total weighted completion time on a single machine with a fixed non-availability interval

In this note, we consider the scheduling problem of minimizing the sum of the weighted completion times on a single machine with one non-availability interval on the machine under the non-resumable scenario. Together with a recent 2-approximation algorithm designed by Kacem [I. Kacem, Approximation algorithm for the weighted flow-time minimization on a single machine with a fixed non-availability interval, Computers & Industrial Engineering 54 (2008) 401–410], this paper is the first successful attempt to develop a constant ratio approximation algorithm for this problem. We present two approaches to designing such an algorithm. Our best algorithm guarantees a worst-case performance ratio of 2+ε. © 2008 Elsevier B.V. All rights reserved.

Positronium scattering by Ne, Ar, Kr and Xe in the frozen target approximation

A full-electron coupled-state treatment of positronium (Ps)- inert gas scattering is developed within the context of the frozen target approximation. Calculations are performed for Ps(Is) scattering by Ne and Ar in the impact energy range 0-40 eV using coupled pseudostate expansions consisting of nine and 22 Ps states. The purpose of the pseudostates is primarily to represent ionization of the Ps which is found to be a major process at the higher energies. First Born estimates of target excitation are used to complement the frozen target results. The available experimental data are discussed in detail. It is pointed out that the very low energy measurements (less than or equal to2 eV) correspond to the momentum transfer cross section sigma(mom) and not to the elastic cross section sigma(el). Calculation shows that sigma(mom), and sigma(el) diverge very rapidly with increasing energy and consequently comparisons of the low-energy data with ITel can be very misleading. Agreement between the calculations and the low-energy measurements of anion as well;as higher energy (greater than or equal to15 eV) beam measurements of the total cross section, is less than satisfactory. Results for Ps(1s) scattering by Kr and Xe in the static-exchange approximation are also presented.

Ionization energies of beryllium in strong magnetic fields: a frozen core approximation

An effective frozen core approximation has been developed and applied to the calculation of energy levels and ionization energies of the beryllium atom in magnetic field strengths up to 2.35 x 10(5) T. Systematic improvement over the existing results for the beryllium ground and low-lying states has been accomplished by taking into account most of the correlation effects in the four-electron system. To our knowledge, this is the first calculation of the electronic properties of the beryllium atom in a strong magnetic field carried out using a configuration interaction approximation and thus allowing a treatment beyond that of Hartree-Fock. Differing roles played by strong magnetic fields in intrashell correlation within different states are observed. In addition, possible ways to gain further improvement in the energies of the states of interest are proposed and discussed briefly.

Multi-state CDW approximation to electron capture during slow p-H collisions

The first complete multi-state CDW close coupling calculations which use a fully normalized basis set are performed. The results obtained at impact energies in the region of 10 keV for total and n = 2 capture cross sections are in reasonably good accord with experiment despite the fact that only the ground states of both species and the n = 2 states of the projectile are incorporated into the model. The theory has significant advantages over other atomic and molecular expansions which may require extensive bases to obtain similar accuracy.

Inelastic quantum transport in nanostructures: The self-consistent Born approximation and correlated electron-ion dynamics

A dynamical method for inelastic transport simulations in nanostructures is compared to a steady-state method based on nonequilibrium Green's functions. A simplified form of the dynamical method produces, in the steady state in the weak-coupling limit, effective self-energies analogous to those in the Born approximation due to electron-phonon coupling. The two methods are then compared numerically on a resonant system consisting of a linear trimer weakly embedded between metal electrodes. This system exhibits an enhanced heating at high biases and long phonon equilibration times. Despite the differences in their formulation, the static and dynamical methods capture local current-induced heating and inelastic corrections to the current with good agreement over a wide range of conditions, except in the limit of very high vibrational excitations where differences begin to emerge.

Modelling the mechanical response of the reed-mouthpiece-lip system of a clarinet. Part II: A lumped model approximation

A non-linear lumped model of the reed-mouthpiece-lip system of a clarinet is formulated, in which the lumped parameters are derived from numerical experiments with a finite-difference simulation based on a distributed reed model. The effective stiffness per unit area is formulated as a function of the pressure signal driving the reed, in order to simulate the effects of the reed bending against the lay, and mass and damping terms are added as a first approximation to the dynamic behaviour of the reed. A discrete-time formulation is presented, and its response is compared to that of the distributed model. In addition, the lumped model is applied in the simulation of clarinet tones, enabling the analysis of the effects of using a pressure-dependent stiffness per unit area on sustained oscillations. The analysed effects and features are in qualitative agreement with players' experiences and experimental results obtained in prior studies.