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.

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.

Thermal, mechanical and optical modelling of VCSEL packaging

Hybrid OECB (Opto-Electrical Circuit Boards) are expected to make a significant impact in the telecomm switches arena within the next five years, creating optical backplanes with high speed point-to-point optical interconnects. OECB's incorporate short range optical interconnects, and are based on VCSEL (Vertical Cavity Surface Emitting Diode) and PD (Photo Diode) pairs, connected to each other via embedded waveguides in the OECB. The VCSEL device is flip-chip assembled onto an organic substrate with embedded optical waveguides. The performance of the VCSEL device is governed by the thermal, mechanical and optical characteristics of this assembly. During operation, the VCSEL device will heat up and the thermal change together with the CTE mismatch in the materials, will result in potential misalignment between the VCSEL apertures and the waveguide openings in the substrate. Any degree of misalignment will affect the optical performance of the package. This paper will present results from a highly coupled modelling analysis involving thermal, mechanical and optical models. The paper will also present results from an optimisation analysis based on Design of Experiments (DOE).

Polymer waveguide and VCSEL array multi-physics modelling for OECB based optical backplanes [opto-electrical circuit boards]

The deployment of OECBs (opto-electrical circuit boards) is expected to make a significant impact in the telecomm switches arena within the next five years. This will create optical backplanes with high speed point-to-point optical interconnects. The crucial aspect in the manufacturing process of the optical backplane is the successful coupling between VCSEL (vertical cavity surface emitting laser) device and embedded waveguide in the OECB. The results from a thermo-mechanical analysis are being used in a purely optical model, which solves optical energy and attenuation from the VCSEL aperture into, and then through, the waveguide. Results from the modelling are being investigated using DOE analysis to identify packaging parameters that minimise misalignment. This is achieved via a specialist optimisation software package. Results from the thermomechanical and optical models are discussed as are experimental results from the DOE.

VCSEL to waveguide coupling for optical backplanes

Hybrid OECB (Opto-Electrical Circuit Boards) are expected to make a significant impact in the telecomm switches arena within the next five years, creating optical backplanes with high speed point-to-point optical interconnects. The critical aspect in the manufacture of the optical backplane is the successful coupling between VCSEL (Vertical Cavity Surface Emitting Laser) device and embedded waveguide in the OECB. Optical performance will be affected by CTE mismatch in the material properties, and manufacturing tolerances. This paper will discuss results from a multidisciplinary research project involving both experimentation and modelling. Key process parameters are being investigated using Design of Experiments and Finite Element Modelling. Simulations have been undertaken that predict the temperature in the VCSEL during normal operation, and the subsequent misalignment that this imposes. The results from the thermomechanical analysis are being used with optimisation software and the experimental DOE (Design of Experiments) to identify packaging parameters that minimise misalignment. These results are also imported into an optical model which solves optical energy and attenuation from the VCSEL aperture into, and then through, the waveguide. Results from the thermomechanical and optical models will be discussed as will the experimental results from the DOE.

Guided waves in a fluid-loaded transversely isotropic place

Dispersion relations are obtained for the propagation of symmetric and antisymmetric modes in a free transversely isotropic plate. Dispersion curves are plotted for the first four symmetric modes for a magnesium plate immersed in water. The first mode is highly damped and switches over to the second mode when the normalized frequency exceeds 12.

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.