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.

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.

On the modelling of the thermal interactions between a spray curtain and an impinging cold gas cloud

A mixed Lagrangian-Eulerian model of a Water Curtain barrier is presented. The heat, mass and momentum processes are modelled in a Lagrangian framework for the dispersed phase and in an Eulerian framework for the carrier phase. The derivation of the coupling source terms is illustrated with reference to a given carrier phase cell. The turbulent character of the flow is treated with a single equation model, modified to directly account for the influence of the particles on the flow. The model is implemented in the form of a 2 D incompressible Navier Stokes solver, coupled to an adaptive Rung Kutta method for the Lagrangian sub-system. Simulations of a free standing full cone water spray show satisfactory agreement with experiment. Predictions of a Water Curtain barrier impacted by a cold gas cloud point to markedly different flow fields for the upward and downward configurations, which could influence the effectiveness of chemical absorption in the liquid phase.

Discretisation procedures for multi-physics phenomena

Procedures are described for solving the equations governing a multi-physics process. Finite volume techniques are used to discretise, using the same unstructured mesh, the equations of fluid flow, heat transfer with solidification, and solid deformation. These discretised equations are then solved in an integrated manner. The computational mechanics environment, PHYSICA, which facilitates the building of multi-physics models, is described. Comparisons between model predictions and experimental data are presented for the casting of metal components.

Association of fever and severe clinical course in bronchiolitis

Little attention has been given to the relation between fever and the severity of bronchiolitis. Therefore, the relation between fever and the clinical course of 90 infants (59 boys, 31 girls) hospitalised during one season with bronchiolitis was studied prospectively. Fever (defined as a single recording > 38.0°C or two successive recording > 37.8°C) was present in 28 infants. These infants were older (mean age, 5.3 v 4.0 months), had a longer mean hospital stay (4.2 v2.7 days), and a more severe clinical course (71.0%v 29.0%) than those infants without fever. Radiological abnormalities (collapse/consolidation) were found in 60.7% of the febrile group compared with 14.8% of the afebrile infants. These results suggest that monitoring of body temperature is important in bronchiolitis and that fever is likely to be associated with a more severe clinical course and radiological abnormalities.

Structural and biological investigation of ferrocene-substituted 3-methylidene-1,3-dihydro-2H-indol-2-ones

The Knoevenagel condensation of 1,3-dihydro-2H-indol-2-one with ferrocene carboxaldehyde afforded an approximate 2:1 mixture of the geometrical isomers (E)- and (Z)-3-ferrocenylmethylidene-1,3-dihydro-2H-indol-2-one respectively in an overall 67% yield; the air and solution-stable isomers were readily separated by preparative thin layer chromatography and their structures were unequivocally elucidated in solution, by (1)H NMR spectroscopy, and in the solid phase, by X-ray crystallography; both isomers of displayed in vitro toxicity against B16 melanoma and Vero cell lines in the micromolar range and inhibited the kinase VEGFR-2 with IC(50) values of ca. 200 nM.