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.

Modelling meso-scale diffusion processes in stochastic fluid bio-membranes

The space–time dynamics of rigid inhomogeneities (inclusions) free to move in a randomly fluctuating fluid bio-membrane is derived and numerically simulated as a function of the membrane shape changes. Both vertically placed (embedded) inclusions and horizontally placed (surface) inclusions are considered. The energetics of the membrane, as a two-dimensional (2D) meso-scale continuum sheet, is described by the Canham–Helfrich Hamiltonian, with the membrane height function treated as a stochastic process. The diffusion parameter of this process acts as the link coupling the membrane shape fluctuations to the kinematics of the inclusions. The latter is described via Ito stochastic differential equation. In addition to stochastic forces, the inclusions also experience membrane-induced deterministic forces. Our aim is to simulate the diffusion-driven aggregation of inclusions and show how the external inclusions arrive at the sites of the embedded inclusions. The model has potential use in such emerging fields as designing a targeted drug delivery system.

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.

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

A hybrid Laplace transform/finite difference boundary element method for diffusion problems

The solution process for diffusion problems usually involves the time development separately from the space solution. A finite difference algorithm in time requires a sequential time development in which all previous values must be determined prior to the current value. The Stehfest Laplace transform algorithm, however, allows time solutions without the knowledge of prior values. It is of interest to be able to develop a time-domain decomposition suitable for implementation in a parallel environment. One such possibility is to use the Laplace transform to develop coarse-grained solutions which act as the initial values for a set of fine-grained solutions. The independence of the Laplace transform solutions means that we do indeed have a time-domain decomposition process. Any suitable time solver can be used for the fine-grained solution. To illustrate the technique we shall use an Euler solver in time together with the dual reciprocity boundary element method for the space solution

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.

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.

Modeling the diffusion of solid copper into liquid solder alloys

During the soldering process, the copper atoms diffuse into liquid solders. The diffusion process determines integrity and the reworking possibility of a solder joint. In order to capture the diffusion scenarios of solid copper into liquid Sn–Pb and Sn–Cu solders, a computer modeling has been performed for 10 s. An analytical model has also been proposed for calculating the diffusion coefficient of copper into liquid solders. It is found that the diffusion coefficient for Sn–Pb solder is 2.74 × 10− 10 m2/s and for Sn–Cu solder is 6.44 × 10−9 m2/s. The modeling results reveal that the diffusion coefficient is one of the major factors that govern the rate at which solid Cu dissolve in the molten solder. The predicted dissolved amounts of copper into solders have been validated with the help of scanning electron microscopic analysis.

Local examination of skin diffusion using FTIR spectroscopic imaging and multivariate target factor analysis

In the context of trans-dermal drug delivery it is very important to have mechanistic insight into the barrier function of the skin's stratum corneum and the diffusion mechanisms of topically applied drugs. Currently spectroscopic imaging techniques are evolving which enable a spatial examination of various types of samples in a dynamic way. ATR-FTIR imaging opens up the possibility to monitor spatial diffusion profiles across the stratum corneum of a skin sample. Multivariate data analyses methods based on factor analysis are able to provide insight into the large amount of spectroscopically complex and highly overlapping signals generated. Multivariate target factor analysis was used for spectral resolution and local diffusion profiles with time through stratum corneum. A model drug, 4-cyanophenol in polyethylene glycol 600 and water was studied. Results indicate that the average diffusion profiles between spatially different locations show similar profiles despite the heterogeneous nature of the biological sample and the challenging experimental set-up.

Simultaneous monitoring of drug and solvent diffusion across a model membrane using ATR-FTIR spectroscopy

Attenuated total reflectance Fourier transform infrared (ATR-FTIR) spectroscopy has been used to simultaneously follow the diffusion of model drugs and solvent across polydimethylsiloxane (silicone) membrane. Three model drugs, cyanophenol (CNP), methyl nicotinate (MN) and butyl paraben (BP) were selected to cover a range of lipophilicities. Isostearyl isostearate (ISIS) was chosen as the solvent because its large molecular weight should facilitate observation of whether the drug molecules are able to diffuse through the membrane independently of the solvent. The diffusion of the three drugs and the solvent was successfully described by a Fickian model. The effects of parameters such as the absorption wavelength used to follow diffusion on the calculated diffusion coefficient were investigated. Absorption wavelength which affects the depth of penetration of the infrared radiation into the membrane did not significantly affect the calculated diffusion coefficient over the wavelength range tested. Each of the model drugs was observed to diffuse independently of the solvent across the membrane. The diffusion of a CNP-ISIS hydrogen bonded complex across the membrane was also monitored. The relative diffusion rates of the solute and solvent across the membrane can largely be accounted for by the molecular size of the permeant.

ATR-FTIR spectroscopy and spectroscopic imaging of solvent and permeant diffusion across model membranes

The uptake and diffusion of solvents across polymer membranes is important in controlled drug delivery, effects on drug uptake into, for example, infusion bags and containers, as well as transport across protective clothing. Attenuated Total Reflectance Fourier Transform Infrared (ATR-FTIR) spectroscopy has been used to monitor the effects of different solvents on the diffusion of a model compound, 4-cyanophenol (CNP) across silicone membrane and on the equilibrium concentration of CNP obtained in the membrane following diffusion. ATR-FTIR spectroscopic imaging of membrane diffusion was used to gain an understanding of when the boundary conditions applied to Fick's second law, used to model the diffusion of permeants across the silicone membrane do not hold. The imaging experiments indicated that when the solvent was not taken up appreciably into the membrane, the presence of discrete solvent pools between the ATR crystal and the silicone membrane can affect the diffusion profile of the permeant. This effect is more significant if the permeant has a high solubility in the solvent. In contrast, solvents that are taken up into the membrane to a greater extent, or those where the solubility of the permeant in the vehicle is relatively low, were found to show a good fit to the diffusion model. As such these systems allow the ATR-FTIR spectroscopic approach to give mechanistic insight into how the particular solvents enhance permeation. The solubility of CNP in the solvent and the uptake of the solvent into the membrane were found to be important influences on the equilibrium concentration of the permeant obtained in the membrane following diffusion. In general, solvents which were taken up to a significant extent into the membrane and which caused the membrane to swell increased the diffusion coefficient of the permeant in the membrane though other factors such as solvent viscosity may also be important.