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

Temporal modelling of short-term rainfall using Cox processes

We study two marked point process models based on the Cox process. These models are used to describe the probabilistic structure of the rainfall intensity process. Mathematical formulation of the models is described and some second-moment characteristics of the rainfall depth, and aggregated processes are considered. The derived second-order properties of the accumulated rainfall amounts at different levels of aggregation are used in order to examine the model fit. A brief data analysis is presented. Copyright © 1998 John Wiley & Sons, Ltd.

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.

Numerical simulation of the mass loss process in pyrolizing char materials

We present here a decoupling technique to tackle the entanglement of the nonlinear boundary condition and the movement of the char/virgin front for a thermal pyrolysis model for charring materials. Standard numerical techniques to solve moving front problems — often referred to as Stefan problems — encounter difficulties when dealing with nonlinear boundaries. While special integral methods have been developed to solve this problem, they suffer from several limitations which the technique described here overcomes. The newly developed technique is compared with the exact analytical solutions for some simple ideal situations which demonstrate that the numerical method is capable of producing accurate numerical solutions. The pyrolysis model is also used to simulate the mass loss process from a white pine sample exposed to a constant radiative flux in a nitrogen atmosphere. Comparison with experimental results demonstrates that the predictions of mass loss rates and temperature profile within the solid material are in good agreement with the experiment.

Converting best manual practice into generic automatable strategies for unstructured mesh parallelisation

The manual effort required to convert sequential computational mechanics programs into a useful, scalable parallel form is considerable. Tools that can assist in the conversion process are clearly required. Computer aided parallelisation tools (CAPTools) have been developed to generate efficient parallel code for real world structured grid application codes such as Computational Fluid Dynamics. Automatable single-program multi-data (SPMD) overlapping domain decomposition (DD) techniques established for structured grid codes have been adapted by the authors to manually parallelise unstructured mesh applications. Inspector loops have been used to provide generic techniques for the run-time support necessary to extend the capabilities of CAPTools to automatic implementation of SPMD DD techniques in the parallelisation of unstructured mesh codes. Copyright © 1999 John Wiley & Sons, Ltd.

A review of the methodologies used in evacuation modelling

Computer based analysis of evacuation can be performed using one of three different approaches, namely optimization, simulation and risk assessment. Furthermore, within each approach different means of representing the enclosure, the population and the behaviour of the population are possible. The myriad of approaches that are available has led to the development of some 22 different evacuation models. This review attempts to describe each of the modelling approaches adopted and critically review the inherent capabilities of each approach. The review is based on available published literature.

An aircraft accident database of human experience in evacuation derived from aviation accident reports

Computer based mathematical models describing the aircraft evacuation process have a vital role to play in aviation safety. However, such models have a heavy dependency on real evacuation data. The Fire Safety Engineering Group of the University of Greenwich is undertaking a large data extraction exercise in order to address this issue. This paper describes the extraction and application of data from aviation accident reports. To aid in the storage and analysis of the raw data, a computer database known as AASK (Aircraft Accident Statistics and Knowledge) is under development. AASK is being developed to store human observational and anecdotal data contained in accident reports and interview transcripts. AASK currently contains information from 25 survivable aviation accidents covering the period 04/04/77 to 06/08/95, involving some 2415 passengers, 2210 survivors, 205 fatalities and accounts from 669 people. Copyright © 1999 John Wiley & Sons, Ltd.

Numerical modelling and validation of Marangoni and surface tension phenomena using the finite volume method

Surface tension induced flow is implemented into a numerical modelling framework and validated for a number of test cases. Finite volume unstructured mesh techniques are used to discretize the mass, momentum and energy conservation equations in three dimensions. An explicit approach is used to include the effect of surface tension forces on the flow profile and final shape of a liquid domain. Validation of this approach is made against both analytical and experimental data. Finally, the method is used to model the wetting balance test for solder alloy material, where model predictions are used to gain a greater insight into this process. Copyright © 2000 John Wiley & Sons, Ltd.

The implementation of an aeronautical CFD flow code onto distributed memory parallel systems

The parallelization of an industrially important in-house computational fluid dynamics (CFD) code for calculating the airflow over complex aircraft configurations using the Euler or Navier–Stokes equations is presented. The code discussed is the flow solver module of the SAUNA CFD suite. This suite uses a novel grid system that may include block-structured hexahedral or pyramidal grids, unstructured tetrahedral grids or a hybrid combination of both. To assist in the rapid convergence to a solution, a number of convergence acceleration techniques are employed including implicit residual smoothing and a multigrid full approximation storage scheme (FAS). Key features of the parallelization approach are the use of domain decomposition and encapsulated message passing to enable the execution in parallel using a single programme multiple data (SPMD) paradigm. In the case where a hybrid grid is used, a unified grid partitioning scheme is employed to define the decomposition of the mesh. The parallel code has been tested using both structured and hybrid grids on a number of different distributed memory parallel systems and is now routinely used to perform industrial scale aeronautical simulations. Copyright © 2000 John Wiley & Sons, Ltd.

Portability, predictability and performance for parallel computing: BSP in practice

We report on practical experience using the Oxford BSP Library to parallelize a large electromagnetic code, the British Aerospace finite-difference time-domain code EMMA T:FD3D. The Oxford BS Library is one of the first realizations of the Bulk Synchronous Parallel computational model to be targeted at numerically intensive scientific (typically Fortran) computing. The BAe EMMA code is one of the first large-scale applications to be parallelized using this library, and it is an important demonstration of the cost effectiveness of the BSP approach. We illustrate how BSP cost-modelling techniques can be used to predict and optimize performance for single-source programs across different parallel platforms. We provide predicted and observed performance figures for an industrial-strength, single-source parallel code for a variety of real parallel architectures: shared memory multiprocessors, workstation clusters and massively parallel platforms.

Scheduling for parallel dedicated machines with a single server

This paper examines scheduling problems in which the setup phase of each operation needs to be attended by a single server, common for all jobs and different from the processing machines. The objective in each situation is to minimize the makespan. For the processing system consisting of two parallel dedicated machines we prove that the problem of finding an optimal schedule is NP-hard in the strong sense even if all setup times are equal or if all processing times are equal. For the case of m parallel dedicated machines, a simple greedy algorithm is shown to create a schedule with the makespan that is at most twice the optimum value. For the two machine case, an improved heuristic guarantees a tight worst-case ratio of 3/2. We also describe several polynomially solvable cases of the later problem. The two-machine flow shop and the open shop problems with a single server are also shown to be NP-hard in the strong sense. However, we reduce the two-machine flow shop no-wait problem with a single server to the Gilmore-Gomory traveling salesman problem and solve it in polynomial time. (c) 2000 John Wiley & Sons, Inc.

Estimating the flow rate capacity of an overturned rail carriage end exit in the presence of smoke

While incidents requiring the rapid egress of passengers from trains are infrequent, perhaps the most challenging scenario for passengers involves the evacuation from an overturned carriage subjected to fire. In this paper we attempt to estimate the flow rate capacity of an overturned rail carriage end exit. This was achieved through two full-scale evacuation experiments, in one of which the participants were subjected to non-toxic smoke. The experiments were conducted as part of a pilot study into evacuation from rail carriages. In reviewing the experimental results, it should be noted that only a single run of each trial was undertaken with a limited — though varied — population. As a result it is not possible to test the statistical significance of the evacuation times quoted and so the results should be treated as indicative rather than definitive. The carriage used in the experiments was a standard class Mark IID which, while an old carriage design, shares many features with those carriages commonly found on the British rail network. In the evacuation involving smoke, the carriage end exit was found to achieve an average flow rate capacity of approximately 5.0 persons/min. The average flow rate capacity of the exit without smoke was found to be approximately 9.2 persons/min. It was noted that the presence of smoke tended to reduce significantly the exit flow rate. Due to the nature of the experimental conditions, these flow rates are considered optimistic. Finally, the authors make several recommendations for improving survivability in rail accidents. Copyright © 2000 John Wiley & Sons, Ltd.

Minimizing total weighted completion time in a proportionate flow shop

We study the special case of the m machine flow shop problem in which the processing time of each operation of job j is equal to pj; this variant of the flow shop problem is known as the proportionate flow shop problem. We show that for any number of machines and for any regular performance criterion we can restrict our search for an optimal schedule to permutation schedules. Moreover, we show that the problem of minimizing total weighted completion time is solvable in O(n2) time. © 1998 John Wiley & Sons, Ltd.

Proportionate flow shop with controllable processing times

This paper considers a special class of flow-shop problems, known as the proportionate flow shop. In such a shop, each job flows through the machines in the same order and has equal processing times on the machines. The processing times of different jobs may be different. It is assumed that all operations of a job may be compressed by the same amount which will incur an additional cost. The objective is to minimize the makespan of the schedule together with a compression cost function which is non-decreasing with respect to the amount of compression. For a bicriterion problem of minimizing the makespan and a linear cost function, an O(n log n) algorithm is developed to construct the Pareto optimal set. For a single criterion problem, an O(n2) algorithm is developed to minimize the sum of the makespan and compression cost. Copyright © 1999 John Wiley & Sons, Ltd.

Scheduling batches with simultaneous job processing for two-machine shop problems

We consider the problem of scheduling independent jobs on two machines in an open shop, a job shop and a flow shop environment. Both machines are batching machines, which means that several operations can be combined into a batch and processed simultaneously on a machine. The batch processing time is the maximum processing time of operations in the batch, and all operations in a batch complete at the same time. Such a situation may occur, for instance, during the final testing stage of circuit board manufacturing, where burn-in operations are performed in ovens. We consider cases in which there is no restriction on the size of a batch on a machine, and in which a machine can process only a bounded number of operations in one batch. For most of the possible combinations of restrictions, we establish the complexity status of the problem.