Scheduling problems for parallel dedicated machines under multiple resource constraints

The paper considers scheduling problems for parallel dedicated machines subject to resource constraints. A fairly complete computational complexity classification is obtained, a number of polynomial-time algorithms are designed. For the problem with a fixed number of machines in which a job uses at most one resource of unit size a polynomial-time approximation scheme is offered.

Scheduling three-operation jobs in a two-machine flow shop to minimize makespan

This paper considers a variant of the classical problem of minimizing makespan in a two-machine flow shop. In this variant, each job has three operations, where the first operation must be performed on the first machine, the second operation can be performed on either machine but cannot be preempted, and the third operation must be performed on the second machine. The NP-hard nature of the problem motivates the design and analysis of approximation algorithms. It is shown that a schedule in which the operations are sequenced arbitrarily, but without inserted machine idle time, has a worst-case performance ratio of 2. Also, an algorithm that constructs four schedules and selects the best is shown to have a worst-case performance ratio of 3/2. A polynomial time approximation scheme (PTAS) is also presented.

Two-machine flow shop scheduling problems with no-wait jobs

In this paper we provide a fairly complete complexity classification of various versions of the two-machine permutation flow shop scheduling problem to minimize the makespan in which some of the jobs have to be processed with no-wait in process. For some version, we offer a fully polynomial-time approximation scheme and a 43-approximation algorithm.

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.

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.

Positive dilations of piecewise monotonic Markov maps

We provide an explicit formula which gives natural extensions of piecewise monotonic Markov maps defined on an interval of the real line. These maps are exact endomorphisms and define chaotic discrete dynamical systems.