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.

Shape-optimized mesh partitioning and load balancing for parallel adaptive FEM

We present a dynamic distributed load balancing algorithm for parallel, adaptive Finite Element simulations in which we use preconditioned Conjugate Gradient solvers based on domain-decomposition. The load balancing is designed to maintain good partition aspect ratio and we show that cut size is not always the appropriate measure in load balancing. Furthermore, we attempt to answer the question why the aspect ratio of partitions plays an important role for certain solvers. We define and rate different kinds of aspect ratio and present a new center-based partitioning method of calculating the initial distribution which implicitly optimizes this measure. During the adaptive simulation, the load balancer calculates a balancing flow using different versions of the diffusion algorithm and a variant of breadth first search. Elements to be migrated are chosen according to a cost function aiming at the optimization of subdomain shapes. Experimental results for Bramble's preconditioner and comparisons to state-of-the-art load balancers show the benefits of the construction.

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

Precipitation of heavy metals from wastewater using simulated flue gas: sequent additions of fly ash, lime and carbon dioxide

Lime is a preferred precipitant for the removal of heavy metals from industrial wastewater due to its relatively low cost. To reduce heavy metal concentration to an acceptable level for discharge, in this work, fly ash was added as a seed material to enhance lime precipitation and the suspension was exposed to CO2 gas. The fly ash-lime-carbonation treatment increased the particle size of the precipitate and significantly improved sedimentation of sludge and the efficiency of heavy metal removal. The residual concentrations of chromium, copper, lead and zinc in effluents can be reduced to (mg L-1) 0.08, 0.14, 0.03 and 0.45, respectively. Examination of the precipitates by XRD and thermal analysis techniques showed that calcium-heavy metal double hydroxides and carbonates were present. The precipitate agglomerated and hardened naturally, facilitating disposal without the need for additional solidification/stabilization measures prior to landfill. It is suggested that fly ash, lime and CO2, captured directly from flue gas, may have potential as a method for wastewater treatment. This method could allow the ex-situ sequestration of CO2, particularly where flue-gas derived CO2 is available near wastewater treatment facilities. (C) 2009 Elsevier Ltd. 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.

Antioxidant principles of Tanacetum vulgare L. aerial parts

The methanolic extract of aerial parts of Tanacetum vulgare L. (Asteraceae) and its fractions were investigated for antioxidant activity. The crude extract displayed DPPH radical scavenging effects with an EC50 value of 37 +/- 1.2 microg/mL (n=3). Activity-guided fractionations of the crude extract resulted in the isolation of three antioxidant compounds; 3,5-O-dicaffeoylquinic acid (3,5-DCQA), axillarin and luteolin. 3,5-DCQA was the major constituent with antioxidant activity (IC50 = 9.7 microM) comparable with that of the standard quercetin (IC50 = 8.8 microM). Though the isolated compounds were previously known for their antioxidant effects, this is the first report on the identification of 3,5-DCQA from Tanacetum vulgare. The displayed potent antioxidant activity of the crude extract and isolated active principles is in support of the traditional medicinal uses of the plant for disease conditions such as wound healing, rheumatic arthritis and other inflammatory conditions.