Approximation algorithms for two-machine flow shop scheduling with batch setup times

In many practical situations, batching of similar jobs to avoid setups is performed while constructing a schedule. This paper addresses the problem of non-preemptively scheduling independent jobs in a two-machine flow shop with the objective of minimizing the makespan. Jobs are grouped into batches. A sequence independent batch setup time on each machine is required before the first job is processed, and when a machine switches from processing a job in some batch to a job of another batch. Besides its practical interest, this problem is a direct generalization of the classical two-machine flow shop problem with no grouping of jobs, which can be solved optimally by Johnson's well-known algorithm. The problem under investigation is known to be NP-hard. We propose two O(n logn) time heuristic algorithms. The first heuristic, which creates a schedule with minimum total setup time by forcing all jobs in the same batch to be sequenced in adjacent positions, has a worst-case performance ratio of 3/2. By allowing each batch to be split into at most two sub-batches, a second heuristic is developed which has an improved worst-case performance ratio of 4/3. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.

The numerical simulation of enclosure fires using a Cfd fire field model coupled with a pyrolysis based solid fuel combustion submodel—a first approximation

In this paper, we present some early work concerned with the development of a simple solid fuel combustion model incorporated within a Computational Fluid Dynamics (CFD) framework. The model is intended for use in engineering applications of fire field modeling and represents an extension of this technique to situations involving the combustion of solid cellulosic fuels. A simple solid fuel combustion model consisting of a thermal pyrolysis model, a six flux radiation model and an eddy-dissipation model for gaseous combustion have been developed and implemented within the CFD code CFDS-FLOW3D. The model is briefly described and demonstrated through two applications involving fire spread in a compartment with a plywood lined ceiling. The two scenarios considered involve a fire in an open and closed compartment. The model is shown to be able to qualitatively predict behaviors similar to "flashover"—in the case of the open room—and "backdraft"— in the case of the initially closed room.

Magnetic levitation fluid dynamics

This work is concerned with the accurate computation of flow in a rapidly deforming liquid metal droplet, suspended in an AC magnetic field. Intense flow motion due to the induced electromagnetic force distorts dynamically the droplet envelope, which is initially spherical. The relative positional change between the liquid metal surface and the surrounding coil means that fluid flow and magnetic field computations need to be closely coupled. A spectral technique is used to solve this problem, which is assumed axisymmetric. The computed results are compared against a physical experiment and "ideal sphere" analytic solutions. A comparison between the "magnetic pressure" approximation and the full electromagnetic force solutions, shows fundamental differences; the full electromagnetic force solution is necessary for accurate results in most practical applications of this technique. The physical reason for the fundamental discrepancy is the difference in the electromagnetic force representation: only the gradient part of the full force is accounted for in the "magnetic pressure" approximation. Figs 9, Refs 13.

Fitting host-parasitoid models with CV² > 1 using hierarchical generalized linear models

The powerful general Pacala-Hassell host-parasitoid model for a patchy environment, which allows host density–dependent heterogeneity (HDD) to be distinguished from between-patch, host density–independent heterogeneity (HDI), is reformulated within the class of the generalized linear model (GLM) family. This improves accessibility through the provision of general software within well–known statistical systems, and allows a rich variety of models to be formulated. Covariates such as age class, host density and abiotic factors may be included easily. For the case where there is no HDI, the formulation is a simple GLM. When there is HDI in addition to HDD, the formulation is a hierarchical generalized linear model. Two forms of HDI model are considered, both with between-patch variability: one has binomial variation within patches and one has extra-binomial, overdispersed variation within patches. Examples are given demonstrating parameter estimation with standard errors, and hypothesis testing. For one example given, the extra-binomial component of the HDI heterogeneity in parasitism is itself shown to be strongly density dependent.

A class of generalized Lévy Laplacians in infinite dimensional calculus

A class of generalized Lévy Laplacians which contain as a special case the ordinary Lévy Laplacian are considered. Topics such as limit average of the second order functional derivative with respect to a certain equally dense (uniformly bounded) orthonormal base, the relations with Kuo’s Fourier transform and other infinite dimensional Laplacians are studied.

Generalized Markov branching processes

A generalized Markov Brnching Process (GMBP) is a Markov branching model where the infinitesimal branching rates are modified with an interaction index. It is proved that there always exists only one GMBP. An associated differential-integral equation is derived. The extinction probalility and the mean and conditional mean extinction times are obtained. Ergodicity and stability of GMBP with resurrection are also considered. Easy checking criteria are established for ordinary and strong ergodicty. The equilibrium distribution is given in an elegant closed form. The probability meaning of our results is clear and thus explained.

Dynamics of magnetically suspended fluid

Magnetic suspension is a technique for processing pure or reactive materials without contact to walls. This work is concerned with the flow in the rapidly deforming liquid volume, suspended in an AC magnetic field. Intense flow motion due to the induced electromagnetic force distorts dynamically the droplet envelope. The relative positional change between the liquid surface and the surrounding coil means that fluid flow and magnetic field computations need to be closely coupled. The computed results are compared against a physical experiment and nearly spherical analytic solutions. A comparison between the "magetic pressure" approximation and the full electromagnetic force solutions shows fundamental differences; the full electromagnetic force is necessary for accurate results in most practical applications of this technique. The physical reason for the fundamental discrepancy is the difference in the electromagnetic force representation: only the gradient part of the full force is accounted for in the "magnetic pressure" approximation.

Approximation Algorithms for a Symmetric Quadratic Knapsack Problem and its Scheduling Applications

We consider a knapsack problem to minimize a symmetric quadratic function. We demonstrate that this symmetric quadratic knapsack problem is relevant to two problems of single machine scheduling: the problem of minimizing the weighted sum of the completion times with a single machine non-availability interval under the non-resumable scenario; and the problem of minimizing the total weighted earliness and tardiness with respect to a common small due date. We develop a polynomial-time approximation algorithm that delivers a constant worst-case performance ratio for a special form of the symmetric quadratic knapsack problem. We adapt that algorithm to our scheduling problems and achieve a better performance. For the problems under consideration no fixed-ratio approximation algorithms have been previously known.

A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date

We develop a fully polynomial-time approximation scheme (FPTAS) for minimizing the weighted total tardiness on a single machine, provided that all due dates are equal. The FPTAS is obtained by converting an especially designed pseudopolynomial dynamic programming algorithm.

Thermal-mechanical modelling of power electronic module packaging

In this paper the reliability of the isolation substrate and chip mountdown solder interconnect of power modules under thermal-mechanical loading has been analysed using a numerical modelling approach. The damage indicators such as the peel stress and the accumulated plastic work density in solder interconnect are calculated for a range of geometrical design parameters, and the effects of these parameters on the reliability are studied by using a combination of the finite element analysis (FEA) method and optimisation techniques. The sensitivities of the reliability of the isolation substrate and solder interconnect to the changes of the design parameters are obtained and optimal designs are studied using response surface approximation and gradient optimization method

Droplet oscillations in high gradient magnetic field

In high intensity and high gradient magnetic fields the volumetric force on diamagnetic material, such as water, leads to conditions very similar to microgravity in a terrestrial laboratory. In principle, this opens the possibility to determine material properties of liquid samples without wall contact, even for electrically non-conducting materials. In contrast, AC field levitation is used for conductors, but then terrestrial conditions lead to turbulent flow driven by Lorentz forces. DC field damping of the flow is feasible and indeed practiced to allow property measurements. However, the AC/DC field combination acts preferentially on certain oscillation modes and leads to a shift in the droplet oscillation spectrum.What is the cause? A nonlinear spectral numerical model is presented, to address these problems

An improved approximation algorithm for the two-machine flow shop scheduling problem with an interstage transporter

We study the two-machine flow shop problem with an uncapacitated interstage transporter. The jobs have to be split into batches, and upon completion on the first machine, each batch has to be shipped to the second machine by a transporter. The best known heuristic for the problem is a –approximation algorithm that outputs a two-shipment schedule. We design a –approximation algorithm that finds schedules with at most three shipments, and this ratio cannot be improved, unless schedules with more shipments are created. This improvement is achieved due to a thorough analysis of schedules with two and three shipments by means of linear programming. We formulate problems of finding an optimal schedule with two or three shipments as integer linear programs and develop strongly polynomial algorithms that find solutions to their continuous relaxations with a small number of fractional variables

An approximation algorithm for the two-machine flow shop with a single transporter

We study the two-machine flow shop problem with an uncapacitated interstage transporter. The jobs have to be split into batches, and upon completion on the first machine, each batch has to be shipped to the second machine by a transporter. The best known heuristic for the problem is a –approximation algorithm that outputs a two-shipment schedule. We design a –approximation algorithm that finds schedules with at most three shipments, and this ratio cannot be improved, unless schedules with more shipments are created. This improvement is achieved due to a thorough analysis of schedules with two and three shipments by means of linear programming. We formulate problems of finding an optimal schedule with two or three shipments as integer linear programs and develop strongly polynomial algorithms that find solutions to their continuous relaxations with a small number of fractional variables.

Droplet oscillations in high gradient static magnetic field

In high intensity and high gradient magnetic fields the volumetric force on diamagnetic material, such as water, leads to conditions very similar to microgravity in a terrestrial laboratory. In principle, this opens the possibility to determine material properties of liquid samples without wall contact, even for electrically non-conducting materials. In contrast, AC field levitation is used for conductors, but then terrestrial conditions lead to turbulent flow driven by Lorentz forces. DC field damping of the flow is feasible and indeed practiced to allow property measurements. However, the AC/DC field combination acts preferentially on certain oscillation modes and leads to a shift in the droplet oscillation spectrum.What is the cause? A nonlinear spectral numerical model is presented, to address these problems.

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.