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.

Multiphysics modelling of the metals casting process

Metals casting is a process governed by the interaction of a range of physical phenomena. Most computational models of this process address only what are conventionally regarded as the primary phenomena-heat conduction and solidification. However, to predict the formation of porosity (a factor of key importance in cast quality) requires the modelling of the interaction of the fluid flow, heat transfer, solidification and the development of stress-deformation in the solidified part of a component. In this paper, a model of the casting process is described which addresses all the main continuum phenomena involved in a coupled manner. The model is solved numerically using novel finite volume unstructured mesh techniques, and then applied to both the prediction of shape deformation (plus the subsequent formation of a gap at the metal-mould interface and its impact on the heat transfer behaviour) and porosity formation in solidifying metal components. Although the porosity prediction model is phenomenologically simplistic it is based on the interaction of the continuum phenomena and yields good comparisons with available experimental results. This work represents the first of the next generation of casting simulation tools to predict aspects of the structure of cast components.

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.

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

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.