A new heuristic for three-machine flow shop scheduling

This paper considers the problem of sequencing n jobs in a three-machine flow shop with the objective of minimizing the makespan, which is the completion time of the last job. An O(n log n) time heuristic that is based on Johnson's algorithm is presented. It is shown to generate a schedule with length at most 5/3 times that of an optimal schedule, thereby reducing the previous best available worst-case performance ratio of 2. An application to the general flow shop is also discussed.

Scheduling batches with sequential job processing for two-machine flow and open shops

In this paper, we study a problem of scheduling and batching on two machines in a flow-shop and open-shop environment. Each machine processes operations in batches, and the processing time of a batch is the sum of the processing times of the operations in that batch. A setup time, which depends only on the machine, is required before a batch is processed on a machine, and all jobs in a batch remain at the machine until the entire batch is processed. The aim is to make batching and sequencing decisions, which specify a partition of the jobs into batches on each machine, and a processing order of the batches on each machine, respectively, so that the makespan is minimized. The flow-shop problem is shown to be strongly NP-hard. We demonstrate that there is an optimal solution with the same batches on the two machines; we refer to these as consistent batches. A heuristic is developed that selects the best schedule among several with one, two, or three consistent batches, and is shown to have a worst-case performance ratio of 4/3. For the open-shop, we show that the problem is NP-hard in the ordinary sense. By proving the existence of an optimal solution with one, two or three consistent batches, a close relationship is established with the problem of scheduling two or three identical parallel machines to minimize the makespan. This allows a pseudo-polynomial algorithm to be derived, and various heuristic methods to be suggested.

A multilevel approach to the travelling salesman problem

We motivate, derive, and implement a multilevel approach to the travelling salesman problem.The resulting algorithm progressively coarsens the problem, initialises a tour, and then employs either the Lin-Kernighan (LK) or the Chained Lin-Kernighan (CLK) algorithm to refine the solution on each of the coarsened problems in reverse order.In experiments on a well-established test suite of 80 problem instances we found multilevel configurations that either improved the tour quality by over 25% as compared to the standard CLK algorithm using the same amount of execution time, or that achieved approximately the same tour quality over seven times more rapidly. Moreover, the multilevel variants seem to optimise far better the more clustered instances with which the LK and CLK algorithms have the most difficulties.

A multilevel algorithm for force-directed graph-drawing

We describe a heuristic method for drawing graphs which uses a multilevel framework combined with a force-directed placement algorithm. The multilevel technique matches and coalesces pairs of adjacent vertices to define a new graph and is repeated recursively to create a hierarchy of increasingly coarse graphs, G0, G1, …, GL. The coarsest graph, GL, is then given an initial layout and the layout is refined and extended to all the graphs starting with the coarsest and ending with the original. At each successive change of level, l, the initial layout for Gl is taken from its coarser and smaller child graph, Gl+1, and refined using force-directed placement. In this way the multilevel framework both accelerates and appears to give a more global quality to the drawing. The algorithm can compute both 2 & 3 dimensional layouts and we demonstrate it on examples ranging in size from 10 to 225,000 vertices. It is also very fast and can compute a 2D layout of a sparse graph in around 12 seconds for a 10,000 vertex graph to around 5-7 minutes for the largest graphs. This is an order of magnitude faster than recent implementations of force-directed placement algorithms.

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

Investigation of the permeation of model formulations and a commercial ibuprofen formulation in Carbosil® and human skin using ATR-FTIR and multivariate spectral analysis

The purpose of the present study was to use attenuated total reflectance-Fourier transform infrared spectroscopy (ATR-FTIR) and target factor analysis (TFA) to investigate the permeation of model drugs and formulation components through Carbosil® membrane and human skin. Diffusion studies of saturated solutions in 50:50 water/ethanol of methyl paraben (MP), ibuprofen (IBU) and caffeine (CF) were performed on Carbosil® membrane. The spectroscopic data were analysed by target factor analysis, and evolution profiles of the signal for each component (i.e. the drug, water, ethanol and membrane) over time were obtained. Results showed that the data were successfully deconvoluted as correlations between factors from the data and reference spectra of the components, were above 0.8 in all cases. Good reproducibility over three runs for the evolution profiles was obtained. From the evolution profiles it was observed that water diffused better through the Carbosil® membrane than ethanol, confirming the hydrophilic properties of the Carbosil® membrane used. IBU diffused slower compared with MP and CF. The evolution profile of CF was very similar to that of water, probably because of the high solubility of CF in water, indicating that both compounds are diffusing concurrently. The second part of the work involved a study of the evolution profiles of the components of a commercial topical gel containing 5% (w/w) of ibuprofen as it permeated through human skin. Although the system was much more complex, data were still successfully deconvoluted and the different components of the formulation identified except for benzyl alcohol which might be attributed to the low concentrations of benzyl alcohol used in topical formulations. (C) 2009 Elsevier B.V. All rights reserved.

Influence of a fed or fasted state on the s-IgA response to prolonged cycling in active men and women

This study investigated the effect of a fed or fasted state on the salivary immunoglobulin A (s-IgA) response to prolonged cycling. Using a randomized, crossover design, 16 active adults (8 men and 8 women) performed 2 hr of cycling on a stationary ergometer at 65% of maximal oxygen uptake on 1 occasion after an overnight fast (FAST) and on another occasion 2 hr after consuming a 2.2-MJ high-carbohydrate meal (FED). Timed, unstimulated whole saliva samples were collected immediately before ingestion of the meal, immediately preexercise, 5 min before cessation of exercise, immediately postexercise, and 1 hr postexercise. The samples were analyzed for s-IgA concentration, osmolality, and cortisol, and saliva flow rates were determined to calculate s-IgA secretion rate. Saliva flow rate decreased by 50% during exercise (p < .05), and s-IgA concentration increased by 42% (p < .05), but s-IgA secretion rate remained unchanged. There was a 37% reduction in s-IgA:osmolality postexercise (p < .05), and salivary cortisol increased by 68% (p < .05). There was no effect of FED vs. FAST on these salivary responses. The s-IgA concentration, secretion rate, and osmolality were found to be significantly lower in women than in men throughout the exercise protocol (p < .05); however, there was no difference between genders in saliva flow rate, s-IgA:osmolality ratio, or cortisol. These data demonstrate that a fed or fasted state 2 hr before exercise does not influence resting s-IgA or the response to prolonged cycling. Furthermore, these results show lower levels of s-IgA and osmolality in women than in men at rest.

Low temperature X-ray crystallographic structures of two lamotrigine analogues: (I) 2-methyl,3-amino, 5-imino-6-(2,3-dichlorophenyl)-1,2,4-triazine water solvate and (II) 2-methyl,3,5-diamino-6-(2,3-dichlorophenyl)-1,2,4-triazine isethionate, hemi-hydrate

The X-ray crystal structures of two lamotrigine derivatives (I) 2-methyl, 3-amino, 5-imino-6-(2, 3-dichlorophenyl)-1,2,4-triazine, C10H9Cl2N5, as the hemi hydrate and (II) 2-methyl,3,5-diamino-6-(2,3-dichlorophenyl)-1,2,4-triazine, C10H10Cl2N5, as the isethionate-water solvate, have been carried out at liquid nitrogen temperature. A detailed comparison of the two structures is given. Both are monoclinic and centrosymmetric, with (I) in space group C2/c, and (II) in space group P2(1)/n. For (I) the unit cell dimensions are a = 19.5466(10), b = 7.5483(4), c = 15.7861(8) angstrom, beta = 91.458(3)degrees, volume = 2328.4(2) angstrom(3), Z = 8, density = 1.590 Mg/m(3); for (II). For (II) the unit cell dimensions are a = 6.0566(2), b = 11.0084(4) c = 23.9973(9) angstrom, beta = 92.587(3)degrees, volume = 1598.35(10) angstrom(3), Z = 4, density = 1.597 Mg/m(3). For (I) final R indices [I > 2sigma(I)] are R1 = 0.0356, wR2 = 0.0782 and R indices (all data) are R1 = 0.0424, wR2 = 0.0817. For (II) final R indices [I > 2sigma(I)] are R1 = 0.0380, wR2 = 0.0871 and R indices (all data) R1 = 0.0558, wR2 = 0.0949. Both structures have a molecule of water of crystallization and (II) also includes a solvated CH3SO3. Comparisons are made between the two structures. Structure (I) is very unusual in having a = NH group at position C5' on the triazine ring. No other examples of this particular substitution, which is usually -NH2, have been reported.