An improved approximation algorithm for the two-machine open shop scheduling problem with family setup times

We consider the problem of scheduling families of jobs in a two-machine open shop so as to minimize the makespan. The jobs of each family can be partitioned into batches and a family setup time on each machine is required before the first job is processed, and when a machine switches from processing a job of some family to a job of another family. For this NP-hard problem the literature contains (5/4)-approximation algorithms that cannot be improved on using the class of group technology algorithms in which each family is kept as a single batch. We demonstrate that there is no advantage in splitting a family more than once. We present an algorithm that splits one family at most once on a machine and delivers a worst-case performance ratio of 6/5.

Single machine scheduling models with deterioration and learning: handling precedence constraints via priority generation

We consider various single machine scheduling problems in which the processing time of a job depends either on its position in a processing sequence or on its start time. We focus on problems of minimizing the makespan or the sum of (weighted) completion times of the jobs. In many situations we show that the objective function is priority-generating, and therefore the corresponding scheduling problem under series-parallel precedence constraints is polynomially solvable. In other situations we provide counter-examples that show that the objective function is not priority-generating.

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.

Schedules with due-date assignment and position-dependent processing times

Single machine scheduling problems are considered, in which the processing of jobs depend on positions of the jobs in a schedule and the due-dates are assigned either according to the CON rule (a due-date common to all jobs is chosen) or according to the SLK rule (the due-dates are computed by increasing the actual processing times of each job by a slack, common to all jobs). Polynomial-time dynamic programming algorithms are proposed for the problems with the objective functions that include the cost of assigning the due-dates, the total cost of disgarded jobs (which are not scheduled) and, possibly, the total earliness of the scheduled jobs.

Optimization of an open-ended microwave oven for microelectronics packaging

A physically open, but electrically shielded, microwave open oven can be produced by virtue of the evanescent fields in a waveguide below cutoff. The below cutoff heating chamber is fed by a transverse magnetic resonance established in a dielectric-filled section of the waveguide exploiting continuity of normal electric flux. In order to optimize the fields and the performance of the oven, a thin layer of a dielectric material with higher permittivity is inserted at the interface. Analysis and synthesis of an optimized open oven predicts field enhancement in the heating chamber up to 9.4 dB. Results from experimental testing on two fabricated prototypes are in agreement with the simulated predictions, and demonstrate an up to tenfold improvement in the heating performance. The open-ended oven allows for simultaneous precision alignment, testing, and efficient curing of microelectronic devices, significantly increasing productivity gains.

Modelling technologies and applications

Numerical modelling technology and software is now being used to underwrite the design of many microelectronic and microsystems components. The demands for greater capability of these analysis tools are increasing dramatically, as the user community is faced with the challenge of producing reliable products in ever shorter lead times. This leads to the requirement for analysis tools to represent the interactions amongst the distinct phenomena and physics at multiple length and timescales. Multi-physics and Multi-scale technology is now becoming a reality with many code vendors. This chapter discusses the current status of modelling tools that assess the impact of nano-technology on the fabrication/packaging and testing of microsystems. The chapter is broken down into three sections: Modelling Technologies, Modelling Application to Fabrication, and Modelling Application to Assembly/Packing and Modelling Applied for Test and Metrology.

A sound and complete reified temporal logic

There are mainly two known approaches to the representation of temporal information in Computer Science: modal logic approaches (including tense logics and hybrid temporal logics) and predicate logic approaches (including temporal argument methods and reified temporal logics). On one hand, while tense logics, hybrid temporal logics and temporal argument methods enjoy formal theoretical foundations, their expressiveness has been criticised as not power enough for representing general temporal knowledge; on the other hand, although current reified temporal logics provide greater expressive power, most of them lack of complete and sound axiomatic theories. In this paper, we propose a new reified temporal logic with a clear syntax and semantics in terms of a sound and complete axiomatic formalism which retains all the expressive power of the approach of temporal reification.

Numerical modelling of electrodeposition phenomena

Electrodeposition is a widely used technique for the fabrication of high aspect ratio microstructure components. In recent years much research has been focused within this area with an aim to understanding the physics behind the filling of high-aspect ratio vias and trenches on PCB's and in particular how they can be made without the formation of voids in the deposited material. This paper describes some of the fundamental work towards the advancement of numerical models that can predict the electrodeposition process and addresses: i) A novel technique for interface motion based on a variation of a donor-acceptor technique ii) A methodology for the investigation of stress profiles in deposits iii) The implementation of acoustic forces to generate replenishing electrolytic flow circulation in recessed features.

Computer simulation of crack propagation in power electronics module solder joints

A numerical modelling method for the analysis of solder joint damage and crack propagation has been described in this paper. The method is based on the disturbed state concept. Under cyclic thermal-mechanical loading conditions, the level of damage that occurs in solder joints is assumed to be a simple monotonic scalar function of the accumulated equivalent plastic strain. The increase of damage leads to crack initiation and propagation. By tracking the evolution of the damage level in solder joints, crack propagation path and rate can be simulated using Finite Element Analysis method. The discussions are focused on issues in the implementation of the method. The technique of speeding up the simulation and the mesh dependency issues are analysed. As an example of the application of this method, crack propagation in solder joints of power electronics modules under cyclic thermal-mechanical loading conditions has been analyzed and the predicted cracked area size after 3000 loading cycles is consistent with experimental results.

Computer simulation of aluminium wirebonds with globtop in power electronics modules

In this paper, computer modelling techniques are used to analyse the effects of globtops on the reliability of aluminium wirebonds in power electronics modules under cyclic thermal-mechanical loading conditions. The sensitivity of the wirehond reliability to the changes of the geometric and the material property parameters of wirebond globtop are evaluated and the optimal combination of the Young's modulus and the coefficient of thermal expansion have been predicted.

Flexible and robust run-time configuration for self-managing systems

This paper describes a methodology for deploying flexible dynamic configuration into embedded systems whilst preserving the reliability advantages of static systems. The methodology is based on the concept of decision points (DP) which are strategically placed to achieve fine-grained distribution of self-management logic to meet application-specific requirements. DP logic can be changed easily, and independently of the host component, enabling self-management behavior to be deferred beyond the point of system deployment. A transparent Dynamic Wrapper mechanism (DW) automatically detects and handles problems arising from the evaluation of self-management logic within each DP and ensures that the dynamic aspects of the system collapse down to statically defined default behavior to ensure safety and correctness despite failures. Dynamic context management contributes to flexibility, and removes the need for design-time binding of context providers and consumers, thus facilitating run-time composition and incremental component upgrade.

Scalable and efficient graph colouring in 3 dimensions using emergence engineering principles

This paper describes ways in which emergence engineering principles can be applied to the development of distributed applications. A distributed solution to the graph-colouring problem is used as a vehicle to illustrate some novel techniques. Each node acts autonomously to colour itself based only on its local view of its neighbourhood, and following a simple set of carefully tuned rules. Randomness breaks symmetry and thus enhances stability. The algorithm has been developed to enable self-configuration in wireless sensor networks, and to reflect real-world configurations the algorithm operates with 3 dimensional topologies (reflecting the propagation of radio waves and the placement of sensors in buildings, bridge structures etc.). The algorithm’s performance is evaluated and results presented. It is shown to be simultaneously highly stable and scalable whilst achieving low convergence times. The use of eavesdropping gives rise to low interaction complexity and high efficiency in terms of the communication overheads.

An architecture of multiple heterogeneous case-based reasoning employing agent technologies

This paper presents an investigation into applying Case-Based Reasoning to Multiple Heterogeneous Case Bases using agents. The adaptive CBR process and the architecture of the system are presented. A case study is presented to illustrate and evaluate the approach. The process of creating and maintaining the dynamic data structures is discussed. The similarity metrics employed by the system are used to support the process of optimisation of the collaboration between the agents which is based on the use of a blackboard architecture. The blackboard architecture is shown to support the efficient collaboration between the agents to achieve an efficient overall CBR solution, while using case-based reasoning methods to allow the overall system to adapt and “learn” new collaborative strategies for achieving the aims of the overall CBR problem solving process.

Numerical investigation of a source extraction technique based on an acoustic correction method

An aerodynamic sound source extraction from a general flow field is applied to a number of model problems and to a problem of engineering interest. The extraction technique is based on a variable decomposition, which results to an acoustic correction method, of each of the flow variables into a dominant flow component and a perturbation component. The dominant flow component is obtained with a general-purpose Computational Fluid Dynamics (CFD) code which uses a cell-centred finite volume method to solve the Reynolds-averaged Navier–Stokes equations. The perturbations are calculated from a set of acoustic perturbation equations with source terms extracted from unsteady CFD solutions at each time step via the use of a staggered dispersion-relation-preserving (DRP) finite-difference scheme. Numerical experiments include (1) propagation of a 1-D acoustic pulse without mean flow, (2) propagation of a 2-D acoustic pulse with/without mean flow, (3) reflection of an acoustic pulse from a flat plate with mean flow, and (4) flow-induced noise generated by the an unsteady laminar flow past a 2-D cavity. The computational results demonstrate the accuracy for model problems and illustrate the feasibility for more complex aeroacoustic problems of the source extraction technique.

An algorithm for total variation inpainting based on nonlinear multi-grid methods

Image inpainting refers to restoring a damaged image with missing information. The total variation (TV) inpainting model is one such method that simultaneously fills in the regions with available information from their surroundings and eliminates noises. The method works well with small narrow inpainting domains. However there remains an urgent need to develop fast iterative solvers, as the underlying problem sizes are large. In addition one needs to tackle the imbalance of results between inpainting and denoising. When the inpainting regions are thick and large, the procedure of inpainting works quite slowly and usually requires a significant number of iterations and leads inevitably to oversmoothing in the outside of the inpainting domain. To overcome these difficulties, we propose a solution for TV inpainting method based on the nonlinear multi-grid algorithm.