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.

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.

In-situ non-destructive ultrasonic rheology technique for monitoring different lead-free solder pastes for surface mount applications

This paper investigates the application of a non-destructive ultrasonic technique for characterising the rheological properties of solder paste through the use of through-mode microsecond ultrasonic pulses for evaluation of viscoelastic properties of lead-free solder paste containing different types of flux. Ultrasonic techniques offer a robust and reliable form of non-destructive testing of materials where access to the sample is restricted or when sample handling can interfere with the monitoring or analysis process due to externally incorporated changes to the material’s physical state or accidental contamination during the removal or testing process. Ultrasonic based techniques are increasingly used for quality control and production monitoring functions which requires evaluation of changes in material properties for a wide range of industrial applications such as cement paste quality, plastic/polymer extrusion process, dough and even sugar content in beverage drinks. In addition, ultrasound techniques are of great interest for their capability to take rapid measurements in systems which are optically opaque. The conventional industry approach for characterising the rheological properties of suspensions during processing/packaging stage is mainly through the use of viscometer and some through the use of rheometer. One of the potential limitations of viscometer and rheometer based measurements is that the collection and preparation of the solder paste samples can irreversibly alter the structure and flow behaviour of the sample. Hence the measurement may not represent the actual quality of the whole production batch. Secondly, rheological measurements and the interpretation of rheological data is a very technical and time consuming process, which requires professionally trained R&D personnel. The ultrasound technique being proposed provides simple, yet accurate and easy to use solution for the in-situ rheological characterisation of solder pastes which will benefit the materials suppliers (who formulate and produce solder pastes) and solder paste consumers (especially, contract electronics manufacturers). The results from the work show that the technique can be used by R&D personnel involved in paste formulation and manufacture to monitor the batch-to-batch quality and consistency.