Scheduling batches with simultaneous job processing for two-machine shop problems

We consider the problem of scheduling independent jobs on two machines in an open shop, a job shop and a flow shop environment. Both machines are batching machines, which means that several operations can be combined into a batch and processed simultaneously on a machine. The batch processing time is the maximum processing time of operations in the batch, and all operations in a batch complete at the same time. Such a situation may occur, for instance, during the final testing stage of circuit board manufacturing, where burn-in operations are performed in ovens. We consider cases in which there is no restriction on the size of a batch on a machine, and in which a machine can process only a bounded number of operations in one batch. For most of the possible combinations of restrictions, we establish the complexity status of the problem.

Three-machine shop scheduling with partially ordered processing routes

This paper considers the problem of sequencing n jobs in a three-machine shop with the objective of minimising the maximum completion time. The shop consists of three machines, M1,M2 and M_{3}. A job is first processed on M1 and then is assigned either the route (M2,M_{3}) or the route (M_{3},M2). Thus, for our model the processing route is given by a partial order of machines, as opposed to the linear order of machines for a job shop, or to an arbitrary sequence of machines for an open shop. The main result is on O(nlog n) time heuristic, which generates a schedule with the makespan that is at most 5/3 times the optimum value.

Across the bridge: CLEF 2001 - Non-English monolingual retrieval. The French task.

This paper presents work on document retrieval based on first time participation in the CLEF 2001 monolingual retrieval task using French. The experiment findings indicated that Okapi, the text retrieval system in use, can successfully be used for non-English text retrieval. A lot of internal pre-processing is required in the basic search system for conversion into Okapi access formats. Various shell scripts were written to achieve the conversion in a UNIX environment, failure of which would significantly have impeded the overall performance. Based on the experiment findings using Okapi - originally designed for English - it was clear that, although most European languages share conventional word boundaries and variant word morphemes formed by the additon of suffixes, there is significant difference between French and English retrieval depending on the adaptation of indexing and search strategies in use. No sophisticated method for higher recall and precision such as stemming techniques, phrase translation or de-compounding was employed for the experiment and our results were suggestively poor. Future participation would include more refined query translation tools.

Computational modelling-a key component in materials processing

Computational analysis software is now widely accepted as a key industrial tool for plant design and process analysis. This is due in part to increased accuracy in the models, larger and faster computer systems and better graphical interfaces that allow easy use of the technology by engineers. The use of computational modelling to test new ideas and analyse current processes helps to take the guesswork out of industrial process design and offers attractive cost savings. An overview of computer-based modelling techniques as applied to the materials processing industry is presented and examples of their application are provided in the contexts of the mixing and refining of lead bullion and the manufacture of lead ingots.

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.

Numerical modelling for electromagnetic processing of materials

Electromagnetic processing of materials (EPM) is one of the most widely practiced and fast growing applications of magnetic and electric forces to fluid flow. EPM is encountered in both industrial processes and laboratory investigations. Applications range in scale from nano-particle manipulation to tonnes of liquid metal treated in the presence of various configurations of magnetic fields. Some of these processes are specifically designed and made possible by the use of the electromagnetic force, like the magnetic levitation of liquid droplets, whilst others involve electric currents essential for electrothermal or electrochemical reasons, for instance, in electrolytic metal production and in induction melting. An insight for the range of established and novel EPM applications can be found in the review presented by Asai [1] in the EPM-2003 conference proceedings.

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.

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.

Numerical simulation of encapsulant curing within a variable frequency microwave processing system

Curing of encapsulant material in a simplified microelectronics package using an open oven Variable Frequency Microwave (VFM) system is numerically simulated using a coupled solver approach. A numerical framework capable of simulating electromagnetic field distribution within the oven system, plus heat transfer, cure rate, degree of cure and thermally induced stresses within the encapsulant material is presented. The discrete physical processes have been integrated into a fully coupled solution, enabling usefully accurate results to be generated. Numerical results showing the heating and curing of the encapsulant material have been obtained and are presented in this contribution. The requirement to capture inter-process coupling and the variation in dielectric and thermophysical material properties is discussed and illustrated with simulation results.

Multiphysics simulation of microwave processing using a multidomain coupled solver approach

Microwave processing of materials is numerically simulated using a coupled solver approach. Microwave heating is a complex coupled process due to the variation in dielectric properties during heating. The effects of heating an object in a electromagnetic field directly influence the manner in which it interacts with the field. Simplifying assumptions and empirical solutions do not capture the fundamental physics involved and, in general, do not provide usefully accurate solutions in a number of practical problems. In order to capture the underlying processes involved in microwave heating, the problem must be looked at in a holistic manner rather than a number of discrete processes. This contribution outlines a coupled-solver multiphysics analysis approach to the solution of practical microwave heating problems.

Concise introduction to image processing using C++

A Concise Intro to Image Processing using C++ presents state-of-the-art image processing methodology, including current industrial practices for image compression, image de-noising methods based on partial differential equations, and new image compression methods such as fractal image compression and wavelet compression. It includes elementary concepts of image processing and related fundamental tools with coding examples as well as exercises. With a particular emphasis on illustrating fractal and wavelet compression algorithms, the text covers image segmentation, object recognition, and morphology. An accompanying CD-ROM contains code for all algorithms.

On the application of variable frequency microwave technology for processing of individual surface mount components

Dual-section variable frequency microwave systems enable rapid, controllable heating of materials within an individual surface mount component in a chip-on=board assembly. The ability to process devices individually allows components with disparate processing requirements to be mounted on the same assembly. The temperature profile induced by the microwave system can be specifically tailored to the needs of the component, allowing optimisation and degree of cure whilst minimising thermomechanical stresses. This paper presents a review of dual-section microwave technology and its application to curing of thermosetting polymer materials in microelectronics applications. Curing processes using both conventional and microwave technologies are assessed and compared. Results indicate that dual-section microwave systems are able to cure individual surface mount packages in a significantly shorter time, at the expense of an increase in thermomechanical stresses and a greater variation in degree of cure.