Fast divide-and-conquer algorithms for preemptive scheduling problems with controllable processing times - a polymatroid optimization approach

We consider a variety of preemptive scheduling problems with controllable processing times on a single machine and on identical/uniform parallel machines, where the objective is to minimize the total compression cost. In this paper, we propose fast divide-and-conquer algorithms for these scheduling problems. Our approach is based on the observation that each scheduling problem we discuss can be formulated as a polymatroid optimization problem. We develop a novel divide-and-conquer technique for the polymatroid optimization problem and then apply it to each scheduling problem. We show that each scheduling problem can be solved in $ \O({\rm T}_{\rm feas}(n) \times\log n)$ time by using our divide-and-conquer technique, where n is the number of jobs and Tfeas(n) denotes the time complexity of the corresponding feasible scheduling problem with n jobs. This approach yields faster algorithms for most of the scheduling problems discussed in this paper.

A finite volume approach to geometrically non-linear stress analysis

In this past decade finite volume (FV) methods have increasingly been used for the solution of solid mechanics problems. This contribution describes a cell vertex finite volume discretisation approach to the solution of geometrically nonlinear (GNL) problems. These problems, which may well have linear material properties, are subject to large deformation. This requires a distinct formulation, which is described in this paper together with the solution strategy for GNL problem. The competitive performance for this procedure against the conventional finite element (FE) formulation is illustrated for a three dimensional axially loaded column.

Group technology approach to the open shop scheduling problem with batch setup times

This paper studies the problem of scheduling jobs in a two-machine open shop to minimize the makespan. Jobs are grouped into batches and are processed without preemption. A batch setup time on each machine is required before the first job is processed, and when a machine switches from processing a job in some batch to a job of another batch. For this NP-hard problem, we propose a linear-time heuristic algorithm that creates a group technology schedule, in which no batch is split into sub-batches. We demonstrate that our heuristic is a -approximation algorithm. Moreover, we show that no group technology algorithm can guarantee a worst-case performance ratio less than 5/4.

Details of an integrated approach to three-dimensional dynamic fluid structure interaction

Fluid structure interaction, as applied to flexible structures, has wide application in diverse areas such as flutter in aircraft, wind response of buildings, flows in elastic pipes and blood vessels. Numerical modelling of dynamic fluid-structure interaction (DFSI) involves the coupling of fluid flow and structural mechanics, two fields that are conventionally modelled using two dissimilar methods, thus a single comprehensive computational model of both phenomena is a considerable challenge and until recently work in this area focused on one phenomenon and represented the behaviour of the other more simply. A single, finite volume unstructured mesh (FV-UM) spatial discretisation method has been employed on a single mesh for the entire domain. The Navier Stokes equations for fluid flow are solved using a SIMPLE type procedure and the Newmark b algorithm is employed for solving the dynamic equilibrium equations for linear elastic solid mechanics and mesh movement is achieved using a spring based mesh procedure for dynamic mesh movement. In the paper we describe a number of additional computation issues for the efficient and accurate modelling of three-dimensional, dynamic fluid-structure interaction problems.

Evaluation of distortions in laser welded shipbuilding parts using local-global finite element approach

In recognition of the differences of scale between the welding pool and the heat affected zone along the welding line on one hand, and the overall size of the components being welded on the other, a local-global finite element approach was developed for the evaluation of distortions in laser welded shipbuilding parts. The approach involves the tandem use of a 'local' and a 'global' step. The local step involves a three-dimensional finite element model for the simulation of the laser welding process using the Sysweld finite element code, which takes into account thermal, metallurgical, and mechanical aspects. The simulation of the laser welding process was performed using a non-linear heat transfer analysis, based on a keyhole formation model, and a coupled transient thermomechanical analysis, which takes into account metallurgical transformations using the temperature dependent material properties and the continuous cooling transformation diagram. The size and shape of the keyhole used in the local finite element analysis was evaluated using a keyhole formation model and the Physica finite volume code. The global step involves the transfer of residual plastic strains and the stiffness of the weld obtained from the local model to the global analysis, which then provides the predicted distortions for the whole part. This newly developed methodology was applied to the evaluation of global distortions due to laser welding of stiffeners on a shipbuilding part. The approach has been proved reliable in comparison with experiments and of practical industrial use in terms of computing time and storage.

Optimization and finite element analysis for reliable electronic packaging

This paper demonstrates a modeling and design approach that couples computational mechanics techniques with numerical optimisation and statistical models for virtual prototyping and testing in different application areas concerning reliability of eletronic packages. The integrated software modules provide a design engineer in the electronic manufacturing sector with fast design and process solutions by optimizing key parameters and taking into account complexity of certain operational conditions. The integrated modeling framework is obtained by coupling the multi-phsyics finite element framework - PHYSICA - with the numerical optimisation tool - VisualDOC into a fully automated design tool for solutions of electronic packaging problems. Response Surface Modeling Methodolgy and Design of Experiments statistical tools plus numerical optimisaiton techniques are demonstrated as a part of the modeling framework. Two different problems are discussed and solved using the integrated numerical FEM-Optimisation tool. First, an example of thermal management of an electronic package on a board is illustrated. Location of the device is optimized to ensure reduced junction temperature and stress in the die subject to certain cooling air profile and other heat dissipating active components. In the second example thermo-mechanical simulations of solder creep deformations are presented to predict flip-chip reliability and subsequently used to optimise the life-time of solder interconnects under thermal cycling.

A combined evolutionary search and multilevel optimisation approach to graph-partitioning

The graph-partitioning problem is to divide a graph into several pieces so that the number of vertices in each piece is the same within some defined tolerance and the number of cut edges is minimised. Important applications of the problem arise, for example, in parallel processing where data sets need to be distributed across the memory of a parallel machine. Very effective heuristic algorithms have been developed for this problem which run in real-time, but it is not known how good the partitions are since the problem is, in general, NP-complete. This paper reports an evolutionary search algorithm for finding benchmark partitions. A distinctive feature is the use of a multilevel heuristic algorithm to provide an effective crossover. The technique is tested on several example graphs and it is demonstrated that our method can achieve extremely high quality partitions significantly better than those found by the state-of-the-art graph-partitioning packages.

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

A modelling approach for coupling numerical analytical techniques applied in microsystems

In this paper, a method for the integration of several numerical analytical techniques that are used in microsystems design and failure analysis is presented. The analytical techniques are categorized into four groups in the discussion, namely the high-fidelity analytical tools, i.e. finite element (FE) method, the fast analytical tools referring to reduced order modeling (ROM); the optimization tools, and probability based analytical tools. The characteristics of these four tools are investigated. The interactions between the four tools are discussed and a methodology for the coupling of these four tools is offered. This methodology consists of three stages, namely reduced order modeling, deterministic optimization and probabilistic optimization. Using this methodology, a case study for optimization of a solder joint is conducted. It is shown that these analysis techniques have mutual relationship of interaction and complementation. Synthetic application of these techniques can fully utilize the advantages of these techniques and satisfy various design requirements. The case study shows that the coupling method of different tools provided by this paper is effective and efficient and it is highly relevant in the design and reliability analysis of microsystems

An architectural approach to autonomics and self-management of automotive embedded electronic systems

Embedded electronic systems in vehicles are of rapidly increasing commercial importance for the automotive industry. While current vehicular embedded systems are extremely limited and static, a more dynamic configurable system would greatly simplify the integration work and increase quality of vehicular systems. This brings in features like separation of concerns, customised software configuration for individual vehicles, seamless connectivity, and plug-and-play capability. Furthermore, such a system can also contribute to increased dependability and resource optimization due to its inherent ability to adjust itself dynamically to changes in software, hardware resources, and environment condition. This paper describes the architectural approach to achieving the goals of dynamically self-configuring automotive embedded electronic systems by the EU research project DySCAS. The architecture solution outlined in this paper captures the application and operational contexts, expected features, middleware services, functions and behaviours, as well as the basic mechanisms and technologies. The paper also covers the architecture conceptualization by presenting the rationale, concerning the architecture structuring, control principles, and deployment concept. In this paper, we also present the adopted architecture V&V strategy and discuss some open issues in regards to the industrial acceptance.