Two-machine open shop scheduling with an availability constraint

We study a two-machine open shop scheduling problem, in which one machine is not available for processing during a given time interval. The objective is to minimize the makespan. We show that the problem is NP-hard and present an approximation algorithm with a worst-case ratio of 4/3.

Two-machine flowshop scheduling problems with no-wait jobs

We study a two-machine flow shop scheduling problem with no-wait in process, in which one of the machines is not available during a specified time interval. We consider three scenarios of handing the operation affected by the nonavailability interval. Its processing may (i) start from scratch after the interval, or (ii) be resumed from the point of interruption, or (iii) be partially restarted after the interval. The objective is to minimize the makespan. We present an approximation algorithm that for all these scenarios delivers a worst-case ratio of 3/2. For the second scenario, we offer a 4/3-approximation algorithm.

The parallel solution of early-exercise Asian options with stochastic volatility

This paper describes an parallel semi-Lagrangian finite difference approach to the pricing of early exercise Asian Options on assets with a stochastic volatility. A multigrid procedure is described for the fast iterative solution of the discrete linear complementarity problems that result. The accuracy and performance of this approach is improved considerably by a strike-price related analytic transformation of asset prices. Asian options are contingent claims with payoffs that depend on the average price of an asset over some time interval. The payoff may depend on this average and a fixed strike price (Fixed Strike Asians) or it may depend on the average and the asset price (Floating Strike Asians). The option may also permit early exercise (American contract) or confine the holder to a fixed exercise date (European contract). The Fixed Strike Asian with early exercise is considered here where continuous arithmetic averaging has been used. Pricing such an option where the asset price has a stochastic volatility leads to the requirement to solve a tri-variate partial differential inequation in the three state variables of asset price, average price and volatility (or equivalently, variance). The similarity transformations [6] used with Floating Strike Asian options to reduce the dimensionality of the problem are not applicable to Fixed Strikes and so the numerical solution of a tri-variate problem is necessary. The computational challenge is to provide accurate solutions sufficiently quickly to support realtime trading activities at a reasonable cost in terms of hardware requirements.

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.

Exploring the conditional performance of UK unit trusts

We evaluate the conditional performance of U.K. equity unit trusts using the approach of Lynch and Wachter (2007, 2008) relative to three conditional linear factor models. We find significant time variation in the conditional performance of some trust portfolios and individual trusts using the lag term spread as the information variable. The conditional performance of the trusts is countercyclical and larger trusts have more countercyclical performance than smaller trusts within certain investment sectors. These patterns in conditional trust performance cannot be fully explained by the underlying securities that the trusts hold.

Communication system model for information rate evaluation of differential detection over time-varying channels

A communication system model for mutual information performance analysis of multiple-symbol differential M-phase shift keying over time-correlated, time-varying flat-fading communication channels is developed. This model is a finite-state Markov (FSM) equivalent channel representing the cascade of the differential encoder, FSM channel model and differential decoder. A state-space approach is used to model channel phase time correlations. The equivalent model falls in a class that facilitates the use of the forward backward algorithm, enabling the important information theoretic results to be evaluated. Using such a model, one is able to calculate mutual information for differential detection over time-varying fading channels with an essentially finite time set of correlations, including the Clarke fading channel. Using the equivalent channel, it is proved and corroborated by simulations that multiple-symbol differential detection preserves the channel information capacity when the observation interval approaches infinity.