A heuristic for the two-machine open-shop scheduling problem with transportation times

The paper considers a problem of scheduling n jobs in a two-machine open shop to minimize the makespan, provided that preemption is not allowed and the interstage transportation times are involved. This problem is known to be unary NP-hard. We present an algorithm that requires O (n log n) time and provides a worst-case performance ratio of 3/2.

Collector-metal behaviour in the recovery of platinum-group metals from catalytic converters

A commercial pyrometallurgical process for the extraction of platinum-group metals (PGM) from a feedstock slag was analysed with the use of a model based on computational fluid dynamics. The results of the modelling indicate that recovery depends on the behaviour of the collector phase. A possible method is proposed for estimation of the rate at which PGM particles in slag are absorbed into an iron collector droplet that falls through it. Nanoscale modelling techniques (for particle migration or capture) are combined with a diffusion-controlled mass-transfer model to determine the iron collector droplet size needed for >95% PGM recovery in a typical process bath (70 mm deep) in a realistic time-scale (<1 h). The results show that an iron droplet having a diameter in the range 0.1–0.3 mm gives good recovery (>90%) within a reasonable time. This finding is compatible with published experimental data. Pyrometallurgical processes similar to that investigated should be applicable to other types of waste that contain low levels of potentially valuable metals.

Multiphase mesh partitioning

We consider the load-balancing problems which arise from parallel scientific codes containing multiple computational phases, or loops over subsets of the data, which are separated by global synchronisation points. We motivate, derive and describe the implementation of an approach which we refer to as the multiphase mesh partitioning strategy to address such issues. The technique is tested on several examples of meshes, both real and artificial, containing multiple computational phases and it is demonstrated that our method can achieve high quality partitions where a standard mesh partitioning approach fails.

Dynamic load-balancing of finite element applications with the DRAMA library

The DRAMA library, developed within the European Commission funded (ESPRIT) project DRAMA, supports dynamic load-balancing for parallel (message-passing) mesh-based applications. The target applications are those with dynamic and solution-adaptive features. The focus within the DRAMA project was on finite element simulation codes for structural mechanics. An introduction to the DRAMA library will illustrate that the very general cost model and the interface designed specifically for application requirements provide simplified and effective access to a range of parallel partitioners. The main body of the paper will demonstrate the ability to provide dynamic load-balancing for parallel FEM problems that include: adaptive meshing, re-meshing, the need for multi-phase partitioning.

Guest editorial. [Computers and Artificial Intelligence. 1998. Vol. 17, No. 2-3]

Editorial

Distributed belief revision as applied within a descriptive model of jury deliberations

Belief revision is a well-research topic within AI. We argue that the new model of distributed belief revision as discussed here is suitable for general modelling of judicial decision making, along with extant approach as known from jury research. The new approach to belief revision is of general interest, whenever attitudes to information are to be simulated within a multi-agent environment with agents holding local beliefs yet by interaction with, and influencing, other agents who are deliberating collectively. In the approach proposed, it's the entire group of agents, not an external supervisor, who integrate the different opinions. This is achieved through an election mechanism, The principle of "priority to the incoming information" as known from AI models of belief revision are problematic, when applied to factfinding by a jury. The present approach incorporates a computable model for local belief revision, such that a principle of recoverability is adopted. By this principle, any previously held belief must belong to the current cognitive state if consistent with it. For the purposes of jury simulation such a model calls for refinement. Yet we claim, it constitutes a valid basis for an open system where other AI functionalities (or outer stiumuli) could attempt to handle other aspects of the deliberation which are more specifi to legal narrative, to argumentation in court, and then to the debate among the jurors.

[Book review] Philip E. Agre and Stanley J. Rosenschein (eds), Computational Theories of Interaction and Agency

Review of: Philip E. Agre and Stanley J. Rosenschein (eds), Computational Theories of Interaction and Agency, MIT Press (1996), ISBN: 978-0262510905

CAPLib - A 'thin layer' message passing library to support computational mechanics codes on distributed memory parallel systems

The Computer Aided Parallelisation Tools (CAPTools) [Ierotheou, C, Johnson SP, Cross M, Leggett PF, Computer aided parallelisation tools (CAPTools)-conceptual overview and performance on the parallelisation of structured mesh codes, Parallel Computing, 1996;22:163±195] is a set of interactive tools aimed to provide automatic parallelisation of serial FORTRAN Computational Mechanics (CM) programs. CAPTools analyses the user's serial code and then through stages of array partitioning, mask and communication calculation, generates parallel SPMD (Single Program Multiple Data) messages passing FORTRAN. The parallel code generated by CAPTools contains calls to a collection of routines that form the CAPTools communications Library (CAPLib). The library provides a portable layer and user friendly abstraction over the underlying parallel environment. CAPLib contains optimised message passing routines for data exchange between parallel processes and other utility routines for parallel execution control, initialisation and debugging. By compiling and linking with different implementations of the library, the user is able to run on many different parallel environments. Even with today's parallel systems the concept of a single version of a parallel application code is more of an aspiration than a reality. However for CM codes the data partitioning SPMD paradigm requires a relatively small set of message-passing communication calls. This set can be implemented as an intermediate `thin layer' library of message-passing calls that enables the parallel code (especially that generated automatically by a parallelisation tool such as CAPTools) to be as generic as possible. CAPLib is just such a `thin layer' message passing library that supports parallel CM codes, by mapping generic calls onto machine specific libraries (such as CRAY SHMEM) and portable general purpose libraries (such as PVM an MPI). This paper describe CAPLib together with its three perceived advantages over other routes: - as a high level abstraction, it is both easy to understand (especially when generated automatically by tools) and to implement by hand, for the CM community (who are not generally parallel computing specialists); - the one parallel version of the application code is truly generic and portable; - the parallel application can readily utilise whatever message passing libraries on a given machine yield optimum performance.

Magneto-hydro-dynamic analysis of an electrolysis cell for aluminum production

An electrolytic cell for Aluminum production contains molten metal subject to high currents and magnetic flux density. The interaction between these two fields creates electromagnetic forces within the liquid metal and can generate oscillations of the fluid similar to the waves at the free surface of oceans and rivers. The study of this phenomenon requires the simulation of the current density field, of the magnetic flux density field and the solution of the equations of motion of the liquid mass. An attempt to analyze the dynamical behavior of this problem is made by coupling different codes, based on different numerical techniques, in a single tool. The simulations are presented and discussed.

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.