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.

Two-stage no-wait scheduling models with setup and removal times separated

This paper studies two models of two-stage processing with no-wait in process. The first model is the two-machine flow shop, and the other is the assembly model. For both models we consider the problem of minimizing the makespan, provided that the setup and removal times are separated from the processing times. Each of these scheduling problems is reduced to the Traveling Salesman Problem (TSP). We show that, in general, the assembly problem is NP-hard in the strong sense. On the other hand, the two-machine flow shop problem reduces to the Gilmore-Gomory TSP, and is solvable in polynomial time. The same holds for the assembly problem under some reasonable assumptions. Using these and existing results, we provide a complete complexity classification of the relevant two-stage no-wait scheduling models.

Approximation algorithms for two-machine flow shop scheduling with batch setup times

In many practical situations, batching of similar jobs to avoid setups is performed while constructing a schedule. This paper addresses the problem of non-preemptively scheduling independent jobs in a two-machine flow shop with the objective of minimizing the makespan. Jobs are grouped into batches. A sequence independent 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. Besides its practical interest, this problem is a direct generalization of the classical two-machine flow shop problem with no grouping of jobs, which can be solved optimally by Johnson's well-known algorithm. The problem under investigation is known to be NP-hard. We propose two O(n logn) time heuristic algorithms. The first heuristic, which creates a schedule with minimum total setup time by forcing all jobs in the same batch to be sequenced in adjacent positions, has a worst-case performance ratio of 3/2. By allowing each batch to be split into at most two sub-batches, a second heuristic is developed which has an improved worst-case performance ratio of 4/3. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.

A 3/2 algorithm for two-machine open shop with route-dependent processing times

This paper considers the problem of minimizing the schedule length of a two-machine shop in which not only can a job be assigned any of the two possible routes, but also the processing times depend on the chosen route. This problem is known to be NP-hard. We describe a simple approximation algorithm that guarantees a worst-case performance ratio of 2. We also present some modifications to this algorithm that improve its performance and guarantee a worst-case performance ratio of 3=2.

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.

Two-machine open shop scheduling with special transportation times

The paper considers a problem of scheduling n jobs in a two-machine open shop to minimise the makespan, provided that preemption is not allowed and the interstage transportation times are involved. In general, this problem is known to be NP-hard. We present a linear time algorithm that finds an optimal schedule if no transportation time exceeds the smallest of the processing times. We also describe an algorithm that creates a heuristic solution to the problem with job-independent transportation times. Our algorithm provides a worst-case performance ratio of 8/5 if the transportation time of a job depends on the assigned processing route. The ratio reduces to 3/2 if all transportation times are equal.

A heuristic for the two-machine open-shop scheduling problem with transportation times

The paper considers a problem of scheduling n jobs in a two-machine open shop to minimize the makespan, provided that preemption is not allowed and the interstage transportation times are involved. This problem is known to be unary NP-hard. We present an algorithm that requires O (n log n) time and provides a worst-case performance ratio of 3/2.

Proportionate flow shop with controllable processing times

This paper considers a special class of flow-shop problems, known as the proportionate flow shop. In such a shop, each job flows through the machines in the same order and has equal processing times on the machines. The processing times of different jobs may be different. It is assumed that all operations of a job may be compressed by the same amount which will incur an additional cost. The objective is to minimize the makespan of the schedule together with a compression cost function which is non-decreasing with respect to the amount of compression. For a bicriterion problem of minimizing the makespan and a linear cost function, an O(n log n) algorithm is developed to construct the Pareto optimal set. For a single criterion problem, an O(n2) algorithm is developed to minimize the sum of the makespan and compression cost. Copyright © 1999 John Wiley & Sons, Ltd.

The collection and analysis of pre-evacuation times derived from evacuation trials and their application to evacuation modelling

This paper presents data relating to occupant pre-evacuation times from university and hospital outpatient facilities. Although the two occupancies are entirely different, they do employ relatively similar procedures: members of staff sweep areas to encourage individuals to evacuate.However the manner in which the dependent population reacts to these procedures is quite different. In the hospital case, the patients only evacuated once a member of the nursing staff had instructed them to do so, while in the university evacuation, the students were less dependent upon the actions of the staff, with over 50% of them evacuating with no prior prompting. In addition, the student pre-evacuation time was found to be dependent on their level of engagement in various activities.

Modelling the performance of lead-Free solder interconnects for copper bumped flip-chip devices

Traditionally, before flip chips can be assembled the dies have to be attached with solder bumps. This process involves the deposition of metal layers on the Al pads on the dies and this is called the under bump metallurgy (UBM). In an alternative process, however, Copper (Cu) columns can be used to replace solder bumps and the UBM process may be omitted altogether. After the bumping process, the bumped dies can be assembled on to the printed circuit board (PCB) by using either solder or conductive adhesives. In this work, the reliability issues of flip chips with Cu column bumped dies have been studied. The flip chip lifetime associated with the solder fatigue failure has been modeled for a range of geometric parameters. The relative importance of these parameters is given and solder volume has been identified as the most important design parameter for long-term reliability. Another important problem that has been studied in this work is the dissolution of protection metals on the pad and Cu column in the reflow process. For small solder joints the amount of Cu which dissolves into the molten solder after the protection layers have worn out may significantly affect solder joint properties.

The collection of pre-evacuation times from evacuation trials involving a Hospital Outpatient area and a University Library facility

This paper presents data relating to occupant pre-evacuation times from a university and a hospital outpatient facility. Although the two structures are entirely different they do employ relatively similar procedures: members of staff sweeping areas of the structure to encourage individuals to evacuate. However, the manner in which the dependent population reacts to these procedures is quite different. In the hospital case the patients only evacuated once a member of the nursing staff had instructed them to do so while in the university evacuation the students were less dependent upon the actions of the staff with over 50% of them evacuating with no prior prompting. Although this data may be useful in a variety of areas, it was collected primarily for use within evacuation models.

Numerical simulation of vacuum dezincing of lead alloy

Removing zinc by distillation can leave the lead bullion virtually free of zinc and also produces pure zinc crystals. Batch distillation is considered in a hemispherical kettle with water-cooled lid, under high vacuum (50 Pa or less). Sufficient zinc concentration at the evaporating surface is achieved by means of a mechanical stirrer. The numerical model is based on the multiphysics simulation package PHYSICA. The fluid flow module of the code is used to simulate the action of the stirring impeller and to determine the temperature and concentration fields throughout the liquid volume including the evaporating surface. The rate of zinc evaporation and condensation is then modelled using Langmuir’s equations. Diffusion of the zinc vapour through the residual air in the vacuum gap is also taken into account. Computed results show that the mixing is sufficient and the rate-limiting step of the process is the surface evaporation driven by the difference of the equilibrium vapour pressure and the actual partial pressure of zinc vapour. However, at higher zinc concentrations, the heat transfer through the growing zinc crystal crust towards the cold steel lid may become the limiting factor because the crystallization front may reach the melting point. The computational model can be very useful in optimising the process within its safe limits.

Mathematical modelling: a laser soldering process for an optoelectronics butterfly package

For sensitive optoelectronic components, traditional soldering techniques cannot be used because of their inherent sensitivity to thermal stresses. One such component is the Optoelectronic Butterfly Package which houses a laser diode chip aligned to a fibre-optic cable. Even sub-micron misalignment of the fibre optic and laser diode chip can significantly reduce the performance of the device. The high cost of each unit requires that the number of damaged components, via the laser soldering process, are kept to a minimum. Mathematical modelling is undertaken to better understand the laser soldering process and to optimize operational parameters such as solder paste volume, copper pad dimensions, laser solder times for each joint, laser intensity and absorption coefficient. Validation of the model against experimental data will be completed, and will lead to an optimization of the assembly process, through an iterative modelling cycle. This will ultimately reduce costs, improve the process development time and increase consistency in the laser soldering process.

Intermetallic phase detection in lead-free solders using synchrotron X-ray diffraction

The high-intensity, high-resolution x-ray source at the European Synchrotron Radiation Facility (ESRF) has been used in x-ray diffraction (XRD) experiments to detect intermetallic compounds (IMCs) in lead-free solder bumps. The IMCs found in 95.5Sn3.8Ag0.7Cu solder bumps on Cu pads with electroplated-nickel immersion-gold (ENIG) surface finish are consistent with results based on traditional destructive methods. Moreover, after positive identification of the IMCs from the diffraction data, spatial distribution plots over the entire bump were obtained. These spatial distributions for selected intermetallic phases display the layer thickness and confirm the locations of the IMCs. For isothermally aged solder samples, results have shown that much thicker layers of IMCs have grown from the pad interface into the bulk of the solder. Additionally, the XRD technique has also been used in a temperature-resolved mode to observe the formation of IMCs, in situ, during the solidification of the solder joint. The results demonstrate that the XRD technique is very attractive as it allows for nondestructive investigations to be performed on expensive state-of-the-art electronic components, thereby allowing new, lead-free materials to be fully characterized.