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.

A Distributed algorithm for 1-D non-linear heat conduction with an unknown point source

Abstract not available

Simulating the interaction of occupants with signage systems

This paper describes the introduction of chained signage systems into evacuation simulation models. Signage systems are widely used in buildings to provide information for wayfinding, thereby providing exiting information during emergencies and assisting in navigation during normal circulation of pedestrians. Recently a system was developed to introduce simple signs into egress models. The system, known as Visibility Catchment Area or VCA, allowed similated agents to interact with signs which point directly to an exit and signs which are located directly above the exit. However, this approach was not able to represent the more general situation of a sign netwokr within an arbitrarily complex building. In this paper we extend the method to include chained signage systems which provides simulated agents that are unfamiliar with the structure a means by which to navigate to an emergency exit. The model includes the associated navigation behaviours exhibited by occupants that rely on a signage system for navigation including: Searching behaviours, Backtracking behaviours, Lost behaviours and Communication behaviours. The new features are demonstrated through a series of demonstration cases and are shown to produce plausible results.

Scheduling parallel dedicated machines with the speeding-up resource

We consider a problem of scheduling jobs on m parallel machines. The machines are dedicated, i.e., for each job the processing machine is known in advance. We mainly concentrate on the model in which at any time there is one unit of an additional resource. Any job may be assigned the resource and this reduces its processing time. A job that is given the resource uses it at each time of its processing. No two jobs are allowed to use the resource simultaneously. The objective is to minimize the makespan. We prove that the two-machine problem is NP-hard in the ordinary sense, describe a pseudopolynomial dynamic programming algorithm and convert it into an FPTAS. For the problem with an arbitrary number of machines we present an algorithm with a worst-case ratio close to 3/2, and close to 3, if a job can be given several units of the resource. For the problem with a fixed number of machines we give a PTAS. Virtually all algorithms rely on a certain variant of the linear knapsack problem (maximization, minimization, multiple-choice, bicriteria). © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008

Maximum curves and isolated points of entire functions

Given M(r; f) =maxjzj=r (jf(z)j) , curves belonging to the set of points M = fz : jf(z)j = M(jzj; f)g were de�ned by Hardy to be maximum curves. Clunie asked the question as to whether the set M could also contain isolated points. This paper shows that maximum curves consist of analytic arcs and determines a necessary condition for such curves to intersect. Given two entire functions f1(z) and f2(z), if the maximum curve of f1(z) is the real axis, conditions are found so that the real axis is also a maximum curve for the product function f1(z)f2(z). By means of these results an entire function of in�nite order is constructed for which the set M has an in�nite number of isolated points. A polynomial is also constructed with an isolated point.

Complexity of mixed shop scheduling problems: A survey

We survey recent results on the computational complexity of mixed shop scheduling problems. In a mixed shop, some jobs have fixed machine orders (as in the job shop), while the operations of the other jobs may be processed in arbitrary order (as in the open shop). The main attention is devoted to establishing the boundary between polynomially solvable and NP-hard problems. When the number of operations per job is unlimited, we focus on problems with a fixed number of jobs.

Scheduling problems for parallel dedicated machines under multiple resource constraints

The paper considers scheduling problems for parallel dedicated machines subject to resource constraints. A fairly complete computational complexity classification is obtained, a number of polynomial-time algorithms are designed. For the problem with a fixed number of machines in which a job uses at most one resource of unit size a polynomial-time approximation scheme is offered.

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.