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 computational study of the characteristics of aircraft post-crash fires

Full-scale furnished cabin fires have been studied experimentally for the purpose of characterising the post-crash cabin fire environment by the US Federal Aviation Administration for many years. In this paper the Computational Fluid Dynamics fire field model SMARTFIRE is used to simulate one of these fires conducted in the C-133 test facility in order to provide further validation of the computational approach and the SMARTFIRE software. The experiment involves exposing the interior cabin materials to an external fuel fire, opening only one exit at the far end of the cabin (the same side as the rupture) for ventilation, and noting the subsequent spread of the external fire to the cabin interior and the onset of flashover at approximately 210 seconds. Through this analysis, the software is shown to be in good agreement with the experimental data, producing reasonable agreement with the fire dynamics prior to flashover and producing a reasonable prediction of the flashover time i.e. 225 seconds. The paper then proceeds to utilize the model to examine the impact on flashover time of the extent of cabin furnishings and cabin ventilation provided by available exits

JOSTLE: multilevel graph partitioning software: an overview

In this chapter we look at JOSTLE, the multilevel graph-partitioning software package, and highlight some of the key research issues that it addresses. We first outline the core algorithms and place it in the context of the multilevel refinement paradigm. We then look at issues relating to its use as a tool for parallel processing and, in particular, partitioning in parallel. Since its first release in 1995, JOSTLE has been used for many mesh-based parallel scientific computing applications and so we also outline some enhancements such as multiphase mesh-partitioning, heterogeneous mapping and partitioning to optimise subdomain shape

Multilevel refinement strategies for the capacity vehicle routing problem

We discuss the application of the multilevel (ML) refinement technique to the Vehicle Routing Problem (VRP), and compare it to its single-level (SL) counterpart. Multilevel refinement recursively coarsens to create a hierarchy of approximations to the problem and refines at each level. A SL algorithm, which uses a combination of standard VRP heuristics, is developed first to solve instances of the VRP. A ML version, which extends the global view of these heuristics, is then created, using variants of the construction and improvement heuristics at each level. Finally some multilevel enhancements are developed. Experimentation is used to find suitable parameter settings and the final version is tested on two well-known VRP benchmark suites. Results comparing both SL and ML algorithms are presented.

The application of multilevel refinement to the vehicle routing problem

We discuss the application of the multilevel (ML) refinement technique to the Vehicle Routing Problem (VRP), and compare it to its single-level (SL) counterpart. Multilevel refinement recursively coarsens to create a hierarchy of approximations to the problem and refines at each level. A SL heuristic, termed the combined node-exchange composite heuristic (CNCH), is developed first to solve instances of the VRP. A ML version (the ML-CNCH) is then created, using the construction and improvement heuristics of the CNCH at each level. Experimentation is used to find a suitable combination, which extends the global view of these heuristics. Results comparing both SL and ML are presented.

Design of parallel algorithms for fractal video compression

The intrinsic independent features of the optimal codebook cubes searching process in fractal video compression systems are examined and exploited. The design of a suitable parallel algorithm reflecting the concept is presented. The Message Passing Interface (MPI) is chosen to be the communication tool for the implementation of the parallel algorithm on distributed memory parallel computers. Experimental results show that the parallel algorithm is able to reduce the compression time and achieve a high speed-up without changing the compression ratio and the quality of the decompressed image. A scalability test was also performed, and the results show that this parallel algorithm is scalable.

Parallel genetic algorithms for the solution of inverse heat conduction problems

A parallel genetic algorithm (PGA) is proposed for the solution of two-dimensional inverse heat conduction problems involving unknown thermophysical material properties. Experimental results show that the proposed PGA is a feasible and effective optimization tool for inverse heat conduction problems

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

Grey video compression methods using fractals

The authors' experience in the treatment of grey video compression using fractals is summarized and compared with other research in the same field. Experience with parallel and distributed computing is also discussed.

Multi-physics modelling for microelectronics and microsystems - current capabilities and future challenges

At present the vast majority of Computer-Aided- Engineering (CAE) analysis calculations for microelectronic and microsystems technologies are undertaken using software tools that focus on single aspects of the physics taking place. For example, the design engineer may use one code to predict the airflow and thermal behavior of an electronic package, then another code to predict the stress in solder joints, and then yet another code to predict electromagnetic radiation throughout the system. The reason for this focus of mesh-based codes on separate parts of the governing physics is essentially due to the numerical technologies used to solve the partial differential equations, combined with the subsequent heritage structure in the software codes. Using different software tools, that each requires model build and meshing, leads to a large investment in time, and hence cost, to undertake each of the simulations. During the last ten years there has been significant developments in the modelling community around multi- physics analysis. These developments are being followed by many of the code vendors who are now providing multi-physics capabilities in their software tools. This paper illustrates current capabilities of multi-physics technology and highlights some of the future challenges

Interaction design for teaching visually impaired students

This paper reports on the findings for a study on improving interaction design for teaching visually impaired students. The crux of the problem is the ability to draw and understand diagrams. The cognitive issues are often underestimated with insufficient attention being given to the use of metaphors, etc. and "one size fits all solutions" are often the norm. The findings of the original seed funded project have led to design criteria and to an application for a large scale project, to produce generic tools and to enable multi-modal teaching and learning, with connotations for the mentally as well as physically impaired.

Semantic and conceptual structures in module design

This paper describes the employment of semantic and conceptual structures in module design, specifically course modules. Additionally, it suggests other uses of these structures in aiding teaching and learning.

Rapid solutions for application specific IGBT module design

The electric car, the all electric aircraft and requirements for renewable energy are prime examples of potential technologies needing to be addressed in the world problem of global warming/carbon emission etc. Power electronics are fundamental for the underpinning of these technologies and with the diverse requirements for electrical configurations and the range of environmental conditions, time to market is paramount for module manufacturers and systems designers alike. This paper presents a 'virtual' design methodology together with theoretical and experimental results that demonstrate enhanced product design with improved reliability, performance and cost value within competitive schemes.

Computational approach for reliable and robust system-in-package design

A computational modelling approach integrated with optimisation and statistical methods that can aid the development of reliable and robust electronic packages and systems is presented. The design for reliability methodology is demonstrated for the design of a SiP structure. In this study the focus is on the procedure for representing the uncertainties in the package design parameters, their impact on reliability and robustness of the package design and how these can be included in the design optimisation modelling framework. The analysis of thermo-mechanical behaviour of the package is conducted using non-linear transient finite element simulations. Key system responses of interest, the fatigue life-time of the lead-free solder interconnects and warpage of the package, are predicted and used subsequently for design purposes. The design tasks are to identify the optimal SiP designs by varying several package input parameters so that the reliability and the robustness of the package are improved and in the same time specified performance criteria are also satisfied

Reliability based design optimisation for system-in-package

This paper discusses a reliability based optimisation modelling approach demonstrated for the design of a SiP structure integrated by stacking dies one upon the other. In this investigation the focus is on the strategy for handling the uncertainties in the package design inputs and their implementation into the design optimisation modelling framework. The analysis of fhermo-mechanical behaviour of the package is utilised to predict the fatigue life-time of the lead-free board level solder interconnects and warpage of the package under thermal cycling. The SiP characterisation is obtained through the exploitation of Reduced Order Models (ROM) constructed using high fidelity analysis and Design of Experiments (DoE) methods. The design task is to identify the optimal SiP design specification by varying several package input parameters so that a specified target reliability of the solder joints is achieved and in the same time design requirements and package performance criteria are met