An open shop scheduling problem with a non-bottleneck machine

This paper considers the problem of processing n jobs in a two-machine non-preemptive open shop to minimize the makespan, i.e., the maximum completion time. One of the machines is assumed to be non-bottleneck. It is shown that, unlike its flow shop counterpart, the problem is NP-hard in the ordinary sense. On the other hand, the problem is shown to be solvable by a dynamic programming algorithm that requires pseudopolynomial time. The latter algorithm can be converted into a fully polynomial approximation scheme that runs in time. An O(n log n) approximation algorithm is also designed whi finds a schedule with makespan at most 5/4 times the optimal value, and this bound is tight.

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.

Two simple constant ratio approximation algorithms for minimizing the total weighted completion time on a single machine with a fixed non-availability interval

In this note, we consider the scheduling problem of minimizing the sum of the weighted completion times on a single machine with one non-availability interval on the machine under the non-resumable scenario. Together with a recent 2-approximation algorithm designed by Kacem [I. Kacem, Approximation algorithm for the weighted flow-time minimization on a single machine with a fixed non-availability interval, Computers & Industrial Engineering 54 (2008) 401–410], this paper is the first successful attempt to develop a constant ratio approximation algorithm for this problem. We present two approaches to designing such an algorithm. Our best algorithm guarantees a worst-case performance ratio of 2+ε. © 2008 Elsevier B.V. All rights reserved.

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.