The open shop scheduling problem with a given sequence of jobs on one machine

The paper considers the open shop scheduling problem to minimize the make-span, provided that one of the machines has to process the jobs according to a given sequence. We show that in the preemptive case the problem is polynomially solvable for an arbitrary number of machines. If preemption is not allowed, the problem is NP-hard in the strong sense if the number of machines is variable, and is NP-hard in the ordinary sense in the case of two machines. For the latter case we give a heuristic algorithm that runs in linear time and produces a schedule with the makespan that is at most 5/4 times the optimal value. We also show that the two-machine problem in the nonpreemptive case is solvable in pseudopolynomial time by a dynamic programming algorithm, and that the algorithm can be converted into a fully polynomial approximation scheme. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 705–731, 1998

Development of numerical techniques for near-field aeroacoustic computations

This work is concerned with the development of a numerical scheme capable of producing accurate simulations of sound propagation in the presence of a mean flow field. The method is based on the concept of variable decomposition, which leads to two separate sets of equations. These equations are the linearised Euler equations and the Reynolds-averaged Navier–Stokes equations. This paper concentrates on the development of numerical schemes for the linearised Euler equations that leads to a computational aeroacoustics (CAA) code. The resulting CAA code is a non-diffusive, time- and space-staggered finite volume code for the acoustic perturbation, and it is validated against analytic results for pure 1D sound propagation and 2D benchmark problems involving sound scattering from a cylindrical obstacle. Predictions are also given for the case of prescribed source sound propagation in a laminar boundary layer as an illustration of the effects of mean convection. Copyright © 1999 John Wiley & Sons, Ltd.