Pre-emptive scheduling problems with controllable processing times

We consider a range of single machine and identical parallel machine pre-emptive scheduling models with controllable processing times. For each model we study a single criterion problem to minimize the compression cost of the processing times subject to the constraint that all due dates should be met. We demonstrate that each single criterion problem can be formulated in terms of minimizing a linear function over a polymatroid, and this justifies the greedy approach to its solution. A unified technique allows us to develop fast algorithms for solving both single criterion problems and bicriteria counterparts.

Modelling the Performance of Flexible Substrates for Lead-Free Applications

In this paper, the performance of flexible substrates for lead-free applications was studied using finite element method (FEM). Firstly, the thermal induced stress in the flex substrate during the lead free solder reflow process was predicted. The shear stress at the interface between the copper track and flex was plotted. This shear stress increases with the thickness of the copper track. Secondly, an ACF flip chip was taken as a typical lead-free application of the flex substrate. The reflow effect on the reliability of ACF interconnections was analyzed. Higher stress was identified along the interface between the conductive particle and the metallization, and the interfacial stress increases with the reflow peak temperature and the coefficient of thermal expansion (CTE) of the adhesive. The moisture effect on the reliability of ACF joints were studied using a macro-micro modeling technique, the predominantly tensile stress found at the interface between the conductive particle and metallization could reduce the contact area and even cause the electrical failure. Modeling results are consistent with the findings in the experimental work

Optimising the wave soldering process for lead free solders

Nitrogen is now used in wave soldering machines to help lower the amount of dross that can be formed on the solder bath surface. The paper provides details on the use of computational fluid dynamics in helping understand the flow profiles of nitrogen in a wave soldering machine and to predict the concentration of nitrogen and oxygen around the solder bath.

On-line algorithms for single machine scheduling with family setup times

The paper considers an on-line single machine scheduling problem where the goal is to minimize the makespan. The jobs are partitioned into families and a setup is performed every time the machine starts processing a batch of jobs of the same family. The scheduler is aware of the number of families and knows the setup time of each family, although information about a job only becomes available when that job is released. We give a lower bound on the competitive ratio of any on-line algorithm. Moreover, for the case of two families, we provide an algorithm with a competitive ratio that achieves this lower bound. As the number of families increases, the lower bound approaches 2, and we give a simple algorithm with a competitive ratio of 2.

Modeling the effect of lead-free soldering on flexible substrates

Flexible Circuit Boards (FPCs) are now being widely used in the electronic industries especially in the areas of electronic packages. Due to European lead-free legislation which has been implemented since July 2006, electronic packaging industries have to switch to use in the lead-free soldering technology. This change has posed a number of challenges in terms of development of lead-free solders and compatible substrates. An increase of at least 20-50 degrees in the reflow temperature is a concern and substantial research is required to investigate a sustainable design of flexible circuit boards as carrier substrates. This paper investigates a number of design variables such as copper conductor width, type of substrate materials, effect of insulating materials, etc. Computer modeling has been used to investigate thermo-mechanical behavior, and reliability, of flexible substrates after they have been subjected to a lead- free solder processing. Results will show particular designs that behave better for a particular rise in peak reflow temperature. Also presented will be the types of failures that can occur in these substrates and what particular materials are more reliable.

Analyzing the performance of flexible substrates for lead-free applications

The performance of flexible substrates for lead-free applications was studied using finite element method (FEM). Firstly, the thermal induced stress in the flex substrate during the lead free solder reflow process was predicted. The shear stress at the interface between the copper track and flex was plotted. This shear stress increases with the thickness of the copper track and the thickness of the flex. Secondly, an anisotropic conductive film (ACF) flip chip was taken as a typical lead-free application of the flex substrate and the moisture effect on the reliability of ACF joints were studied using a 3D macro-micro modeling technique. It is found that the time to be saturated of an ACF flip chip is much dependent on the moisture diffusion rate in the polyimide substrate. The majority moisture diffuses into the ACF layer from the substrate side rather than the periphery of the ACF. The moisture induced stress was predicted and the predominant tensile stress was found at the interface between the conductive particle and metallization which could reduce the contact area and even cause the electrical failure

Thermal-mechanical analysis of flexible substrates during lead-free solder reflow

This paper presents modeling results about the performance of flexible substrates when subjected to higher lead-free reflow temperatures. Both adhesiveless and adhesive types of polyimide substrates were studied. Finite element (FE) models of flex substrates were built, two copper tracks located in the centre of the substrate was considered. The thermal induced shear stress in the flex substrate during the lead-free reflow process was studied and the effect of the design changes including the track thickness, flex thickness, and copper width were studied. For both types of flexes, the one of most important variables for minimizing damage to the substrate is the height of the copper tracks. The height of flex and the width of copper track show less impact. Beside of the geometry effects, the increase in reflow peak temperature can also result in a significant increase in the interfacial stress between the copper track and flex. Higher stresses were identified within the adhesive flex due to the big CTE mismatch between the copper and adhesive/dielectric

Performance and reliability of flexible substrates when subjected to lead-free processing

The use of flexible substrates is growing in many applications such as computer peripherals, hand held devices, telecommunications, automotive, aerospace, etc. The drive to adopt flexible circuits is due to their ability to reduce size, weight, assembly time and cost of the final product.They also accommodate flexibility by allowing relative movement between component parts and provide a route for three dimensional packaging. This paper will describe some of the current research results from the Flex-No-Lead project, a European Commission sponsored research program. The principle aim of this project is to investigate the processing, performance, and reliability of flexible substrates when subjected to new environmentally friendly, lead-free soldering technologies. This paper will discuss the impact of specific design variables on performance and reliability. In particular the paper will focus on copper track designs, substrate material, dielectric material and solder-mask defined joints.

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.

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.

The UK WTC 9/11 evacuation study: an overview of the methodologies employed and some analysis relating to fatigue, stair travel speeds and occupant response times

This paper briefly describes the methodologies employed in the collection and storage of first-hand accounts of evacuation experiences derived from face-to-face interviews with evacuees from the World Trade Center (WTC) Twin Towers complex on 11 September 2001 and the development of the High-rise Evacuation Evaluation Database (HEED). The main focus of the paper is to present an overview of preliminary analysis of data derived from the evacuation of the North Tower.

Single machine scheduling and due date assignment with positionally dependent processing times

We consider single machine scheduling and due date assignment problems in which the processing time of a job depends on its position in a processing sequence. The objective functions include the cost of changing the due dates, the total cost of discarded jobs that cannot be completed by their due dates and, possibly, the total earliness of the scheduled jobs. We present polynomial-time dynamic programming algorithms in the case of two popular due date assignment methods: CON and SLK. The considered problems are related to mathematical models of cooperation between the manufacturer and the customer in supply chain scheduling.

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.

Effect of reflow profile and thermal cycle ageing on the intermetallic formation and growth in lead-free soldering

The formation and growth of intermetallic compound layer thickness is one of the important issues in search for reliable electronic and electrical connections. Intermetallic compounds (IMCs) are an essential part of solder joints. At low levels, they have a strengthening effect on the joint; but at higher levels, they tend to make solder joints more brittle. If the solder joint is subjected to long-standing exposure of high temperature, this could result in continuous growth of intermetallic compound layer. The brittle intermetallic compound layer formed in this way is very much prone to fracture and cold therefore lead to mechanical and electrical failure of the joint. Therefore, the primary aim of this study is to investigate the growth of intermetallic compound layer thickness subjected to five different reflow profiles. The study also looks at the effect of three different temperature cycles (with maximum cycle temperature of 25 0C, 40 0C and 60 0C) on intermetallic compound formation and their growth behaviour.. Two different Sn-Ag-Cu solder pastes (namely paste P1 and paste P2) which were different in flux medium, were used for the study. The result showed that the growth of intermetallic compound layer thickness was a function of ageing temperature. It was found that the rate of growth of intermetallic compound layer thickness of paste P1 was higher than paste P2 at the same temperature condition. This behaviour could be related to the differences in flux mediums of solder paste samples used.