Heuristics for short route job shop scheduling problems

We consider two “minimum”NP-hard job shop scheduling problems to minimize the makespan. In one of the problems every job has to be processed on at most two out of three available machines. In the other problem there are two machines, and a job may visit one of the machines twice. For each problem, we define a class of heuristic schedules in which certain subsets of operations are kept as blocks on the corresponding machines. We show that for each problem the value of the makespan of the best schedule in that class cannot be less than 3/2 times the optimal value, and present algorithms that guarantee a worst-case ratio of 3/2.

On the coupling of Navier–Stokes and linearised Euler equations for aeroacoustic simulation

Aerodynamic generation of sound is governed by the Navier–Stokes equations while acoustic propagation in a non-uniform medium is effectively described by the linearised Euler equations. Different numerical schemes are required for the efficient solution of these two sets of equations, and therefore, coupling techniques become an essential issue. Two types of one-way coupling between the flow solver and the acoustic solver are discussed: (a) for aerodynamic sound generated at solid surfaces, and (b) in the free stream. Test results indicate how the coupling achieves the necessary accuracy so that Computational Fluid Dynamics codes can be used in aeroacoustic simulations.

Maintenance of a case-base for the retrieval of rotationally symmetric shapes for the design of metal castings

In this paper, we discuss the problem of maintenance of a CBR system for retrieval of rotationally symmetric shapes. The special feature of this system is that similarity is derived primarily from graph matching algorithms. The special problem of such a system is that it does not operate on search indices that may be derived from single cases and then used for visualisation and principle component analyses. Rather, the system is built on a similarity metric defined directly over pairs of cases. The problems of efficiency, consistency, redundancy, completeness and correctness are discussed for such a system. Performance measures for the CBR system are given, and the results for trials of the system are presented. The competence of the current case-base is discussed, with reference to a representation of cases as points in an n-dimensional feature space, and a Gramian visualisation. A refinement of the case base is performed as a result of the competence analysis and the performance of the case-base before and after refinement is compared.

A domain decomposition algorithm for inverse welding problems

A mathematical model and a numerical scheme for the inverse determination of heat sources generated by means of a welding process is presented in this paper. The accuracy of the heat source retrieval is discussed.

Non-preemptive two-machine open shop scheduling with non-availability constraints

We study a two-machine open shop scheduling problem, in which the machines are not continuously available for processing. No preemption is allowed in the processing of any operation. The objective is to minimize the makespan. We consider approximability issues of the problem with more than one non-availability intervals and present an approximation algorithm with a worst-case ratio of 4/3 for the problem with a single non-availability interval.

Numerical simulation of flow-induced cavity noise in self-sustained oscillations

The generation and near-field radiation of aerodynamic sound from a low-speed unsteady flow over a two-dimensional automobile door cavity is simulated by using a source-extraction-based coupling method. In the coupling procedure, the unsteady cavity flow field is first computed solving the Reynolds averaged Navier–Stokes (RANS) equations. The radiated sound is then calculated by using a set of acoustic perturbation equations with acoustic source terms which are extracted from the time-dependent solutions of the unsteady flow. The aerodynamic and its resulting acoustic field are computed for the Reynolds number of 53,266 based on the base length of the cavity. The free stream flow velocity is taken to be 50.9m/s. As first stage of the numerical investigation of flow-induced cavity noise, laminar flow is assumed. The CFD solver is based on a cell-centered finite volume method. A dispersion-relation-preserving (DRP), optimized, fourth-order finite difference scheme with fully staggered-grid implementation is used in the acoustic solver

Preemptive scheduling on uniform parallel machines with controllable job processing times

In this paper, we provide a unified approach to solving preemptive scheduling problems with uniform parallel machines and controllable processing times. We demonstrate that a single criterion problem of minimizing total compression cost subject to the constraint that all due dates should be met can be formulated in terms of maximizing a linear function over a generalized polymatroid. This justifies applicability of the greedy approach and allows us to develop fast algorithms for solving the problem with arbitrary release and due dates as well as its special case with zero release dates and a common due date. For the bicriteria counterpart of the latter problem we develop an efficient algorithm that constructs the trade-off curve for minimizing the compression cost and the makespan.

The creative masses of digital Britain

The present recession has prompted scholarly and journalistic questioning of the contributions of the cultural industries to the economy. The talent-rich metropolitan clusters of London and New York are well-placed to ride out a thoroughgoing shakeup of the media markets if they manage their infrastructure, space and resources strategically, as Richard Florida has recently argued. This seems to be the assumption behind the recent Digital Britain interim report, and Gordon Brown's remarks that a digital revolution "lies at the heart" of Britain's economic recovery and that broadband and the media industry can play a leading role in pulling the UK out of the recession. Focusing on the Digital Britain report and consultation documents, this presentation seeks to unpack some of the fundamental assumptions behind this link between digital infrastructure, creativity and profitability. In particular the implicit notion of an engaged audience of users, generating "content" as well as shaping new media platforms calls into question long-held theoretical constructions of the mass audience of consumers as spectators; instead, the audience emerges as a potential economic powerhouse, an underused resource for tomorrow's cultural industries.

All change!: Romani studies through Romani eyes

The welcome emergence of a Gypsy/Roma/Traveller academic and intellectual community has stimulated new reflections on and reassessments of many of the established ideas surrounding Romani history and culture. New questions are being asked and, in turn, new critical challenges have arisen, in part because, for these individuals, Gypsy identity has never been something exotic and Other, but their own.

Megasonic agitation for enhanced electrodeposition of copper

In this paper we propose an agitation method based on megasonic acoustic streaming to overcome the limitations in plating rate and uniformity of the metal deposits during the electroplating process. Megasonic agitation at a frequency of 1 MHz allows the reduction of the thickness of the Nernst diffusion layer to less than 600 nm. Two applications that demonstrate the benefits of megasonic acoustic streaming are presented: the formation of uniform ultra-fine pitch flip-chip bumps and the metallisation of high aspect ratio microvias. For the latter application, a multi-physics based numerical simulation is implemented to describe the hydrodynamics introduced by the acoustic waves as they travel inside the deep microvias.

The ecology of Bacillus thuringiensis on the Phylloplane: colonization from soil, plasmid transfer, and interaction with larvae of Pieris brassicae

Seedlings of clover (Triflorium hybridum) were colonized by Bacillus thuringiensis when spores and seeds were co-inoculated into soil. Both a strain isolated in the vegetative form from the phylloplane of clover, 2810-S-4, and a laboratory strain, HD-1, were able to colonize clover to a density of about 1000 CFU/g leaf when seeds were sown in sterile soil and to a density of about 300 CFU/g leaf in nonsterile soil. A strain lacking the characteristic insecticidal crystal proteins produced a similar level of colonization over a 5-week period as the wild type strain, indicating that crystal production was not a mitigating factor during colonization. A small plasmid, pBC16, was transferred between strains of B. thuringiensis when donor and recipient strains were sprayed in vegetative form onto leaves of clover and pak choi (Brassica campestris var. chinensis). The rate of transfer was about 0.1 transconjugants/recipient and was dependent on the plant species. The levels of B. thuringiensis that naturally colonized leaves of pak choi produced negligible levels of mortality in third instar larvae of Pieris brassicae feeding on the plants. Considerable multiplication occurred in the excreted frass but not in the guts of living insects. Spores in the frass could be a source of recolonization from the soil and be transferred to other plants. These findings illustrate a possible cycle, not dependent on insect pathology, by which B. thuringiensis diversifies and maintains itself in nature.

Multiple-locus sequence typing analysis of Bacillus thuringiensis recovered from the phylloplane of clover (Trifolium hybridum) in vegetative form

The chromosomal genotype, as judged by multi locus sequence typing, and the episomal genotype, as judged by plasmid profile and cry gene content, were analyzed for a collection of strains of Bacillus thuringiensis. These had been recovered in vegetative form over a period of several months from the leaves of a small plot of clover (Trifolium hybridum). A clonal population structure was indicated, although greater variation in sequence types (STs) was discovered than in previous collections of B. cereus/B. thuringiensis. Isolates taken at the same time had quite different genotypes, whereas those of identical genotypes were recovered at different times. The profiles of plasmid content and cry genes generally bore no relation to each other nor to the STs. Evidently, although relatively little recombination was occurring in the seven chromosomal genes analyzed, a great deal of conjugal transfer, and perhaps recombination, was occurring involving plasmids. A clinical diarrheal isolate of B. cereus and the commercial biopesticide strain HD-1 of B. thuringiensis, both included as out-groups, were found to have very similar STs. This further emphasizes the role of episomal elements in the characteristics and differentiation of these two species.