Scheduling batches with sequential job processing for two-machine flow and open shops

In this paper, we study a problem of scheduling and batching on two machines in a flow-shop and open-shop environment. Each machine processes operations in batches, and the processing time of a batch is the sum of the processing times of the operations in that batch. A setup time, which depends only on the machine, is required before a batch is processed on a machine, and all jobs in a batch remain at the machine until the entire batch is processed. The aim is to make batching and sequencing decisions, which specify a partition of the jobs into batches on each machine, and a processing order of the batches on each machine, respectively, so that the makespan is minimized. The flow-shop problem is shown to be strongly NP-hard. We demonstrate that there is an optimal solution with the same batches on the two machines; we refer to these as consistent batches. A heuristic is developed that selects the best schedule among several with one, two, or three consistent batches, and is shown to have a worst-case performance ratio of 4/3. For the open-shop, we show that the problem is NP-hard in the ordinary sense. By proving the existence of an optimal solution with one, two or three consistent batches, a close relationship is established with the problem of scheduling two or three identical parallel machines to minimize the makespan. This allows a pseudo-polynomial algorithm to be derived, and various heuristic methods to be suggested.

Two-stage open shop scheduling with a bottleneck machine

It is known that for the open shop scheduling problem to minimize the makespan there exists no polynomial-time heuristic algorithm that guarantees a worst-case performance ratio better than 5/4, unless P6≠NP. However, this result holds only if the instance of the problem contains jobs consisting of at least three operations. This paper considers the open shop scheduling problem, provided that each job consists of at most two operations, one of which is to be processed on one of the m⩾2 machines, while the other operation must be performed on the bottleneck machine, the same for all jobs. For this NP-hard problem we present a heuristic algorithm and show that its worst-case performance ratio is 5/4.

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.

Three-machine shop scheduling with partially ordered processing routes

This paper considers the problem of sequencing n jobs in a three-machine shop with the objective of minimising the maximum completion time. The shop consists of three machines, M1,M2 and M_{3}. A job is first processed on M1 and then is assigned either the route (M2,M_{3}) or the route (M_{3},M2). Thus, for our model the processing route is given by a partial order of machines, as opposed to the linear order of machines for a job shop, or to an arbitrary sequence of machines for an open shop. The main result is on O(nlog n) time heuristic, which generates a schedule with the makespan that is at most 5/3 times the optimum value.

A multilevel approach to the travelling salesman problem

We motivate, derive, and implement a multilevel approach to the travelling salesman problem.The resulting algorithm progressively coarsens the problem, initialises a tour, and then employs either the Lin-Kernighan (LK) or the Chained Lin-Kernighan (CLK) algorithm to refine the solution on each of the coarsened problems in reverse order.In experiments on a well-established test suite of 80 problem instances we found multilevel configurations that either improved the tour quality by over 25% as compared to the standard CLK algorithm using the same amount of execution time, or that achieved approximately the same tour quality over seven times more rapidly. Moreover, the multilevel variants seem to optimise far better the more clustered instances with which the LK and CLK algorithms have the most difficulties.

The development and validation of computational MHD techniques for the modelling of metal production processes

Magnetic fields are used in a number of processes related to the extraction of metals, production of alloys and the shaping of metal components. Computational techniques have an increasingly important role to play in the simulation of such processes, since it is often difficult or very costly to conduct experiments in the high temperature conditions encountered and the complex interaction of fluid flow, heat transfer and magnetic fields means simple analytic models are often far removed from reality. In this paper an overview of the computational activity at the University of Greenwich is given in this area, covering the past ten years. The overview is given from the point of view of the modeller and within the space limitations imposed by the format it covers the numerical methods used, attempts at validation against experiments or analytic procedures; it highlights successes, but also some failures. A broad range of models is covered in the review (and accompanying lecture), used to simulate (a) A-C field applications: induction melting, magnetic confinement and levitation, casting and (b) D-C field applications such as: arc welding and aluminium electroloysis. Most of these processes involve phase change of the metal (melting or solidification), the presence of a dynamic free surface and turbulent flow. These issues affect accuracy and need to be address by the modeller.

Across the bridge: CLEF 2001 - Non-English monolingual retrieval. The French task.

This paper presents work on document retrieval based on first time participation in the CLEF 2001 monolingual retrieval task using French. The experiment findings indicated that Okapi, the text retrieval system in use, can successfully be used for non-English text retrieval. A lot of internal pre-processing is required in the basic search system for conversion into Okapi access formats. Various shell scripts were written to achieve the conversion in a UNIX environment, failure of which would significantly have impeded the overall performance. Based on the experiment findings using Okapi - originally designed for English - it was clear that, although most European languages share conventional word boundaries and variant word morphemes formed by the additon of suffixes, there is significant difference between French and English retrieval depending on the adaptation of indexing and search strategies in use. No sophisticated method for higher recall and precision such as stemming techniques, phrase translation or de-compounding was employed for the experiment and our results were suggestively poor. Future participation would include more refined query translation tools.

Modeling the dynamics of electromagnetically agitated metallurgical flows: levitation, cold crucible, aluminium electrolysis, etc.

We present practical modelling techniques for electromagnetically agitated liquid metal flows involving dynamic change of the fluid volume and shape during melting and the free surface oscillation. Typically the electromagnetic field is strongly coupled to the free surface dynamics and the heat-mass transfer. Accurate pseudo-spectral code and the k-omega turbulence model modified for complex and transitional flows with free surfaces are used for these simulations. The considered examples include magnetic suspension melting, induction scull remelting (cold crucible), levitation and aluminium electrolysis cells. The process control and the energy savings issues are analysed.

Investigation of the cold crucible melting process: experimental and numerical study

The dynamic process of melting different materials in a cold crucible is being studied experimentally with parallel numerical modelling work. The numerical simulation uses a variety of complementing models: finite volume, integral equation and pseudo-spectral methods combined to achieve the accurate description of the dynamic melting process. Results show the temperature history of the melting process with a comparison of the experimental and computed heat losses in the various parts of the equipment. The free surface visual observations are compared to the numerically predicted surface shapes.

On a flexible elimination algorithm with applications to panel element equations

A flexible elimination algorithm is presented and is applied to the solution of dense systems of linear equations. Properties of the algorithm are exploited in relation to panel element methods for potential flow and subsonic compressible flow. Further properties in relation to distributed computing are also discussed.

Performance evaluation of a distributed algorithm for an inverse heat conduction problem

Numerical solutions of realistic 2-D and 3-D inverse problems may require a very large amount of computation. A two-level concept on parallelism is often used to solve such problems. The primary level uses the problem partitioning concept which is a decomposition based on the mathematical/physical problem. The secondary level utilizes the widely used data partitioning concept. A theoretical performance model is built based on the two-level parallelism. The observed performance results obtained from a network of general purpose Sun Sparc stations are compared with the theoretical values. Restrictions of the theoretical model are also discussed.

Numerical experiments of some Krylov subspace methods for black oil model

This paper discusses preconditioned Krylov subspace methods for solving large scale linear systems that originate from oil reservoir numerical simulations. Two types of preconditioners, one being based on an incomplete LU decomposition and the other being based on iterative algorithms, are used together in a combination strategy in order to achieve an adaptive and efficient preconditioner. Numerical tests show that different Krylov subspace methods combining with appropriate preconditioners are able to achieve optimal performance.

Details of an integrated approach to three-dimensional dynamic fluid structure interaction

Fluid structure interaction, as applied to flexible structures, has wide application in diverse areas such as flutter in aircraft, wind response of buildings, flows in elastic pipes and blood vessels. Numerical modelling of dynamic fluid-structure interaction (DFSI) involves the coupling of fluid flow and structural mechanics, two fields that are conventionally modelled using two dissimilar methods, thus a single comprehensive computational model of both phenomena is a considerable challenge and until recently work in this area focused on one phenomenon and represented the behaviour of the other more simply. A single, finite volume unstructured mesh (FV-UM) spatial discretisation method has been employed on a single mesh for the entire domain. The Navier Stokes equations for fluid flow are solved using a SIMPLE type procedure and the Newmark b algorithm is employed for solving the dynamic equilibrium equations for linear elastic solid mechanics and mesh movement is achieved using a spring based mesh procedure for dynamic mesh movement. In the paper we describe a number of additional computation issues for the efficient and accurate modelling of three-dimensional, dynamic fluid-structure interaction problems.

A finite volume approach to geometrically non-linear stress analysis

In this past decade finite volume (FV) methods have increasingly been used for the solution of solid mechanics problems. This contribution describes a cell vertex finite volume discretisation approach to the solution of geometrically nonlinear (GNL) problems. These problems, which may well have linear material properties, are subject to large deformation. This requires a distinct formulation, which is described in this paper together with the solution strategy for GNL problem. The competitive performance for this procedure against the conventional finite element (FE) formulation is illustrated for a three dimensional axially loaded column.

A finite volume unstructured mesh approach to dynamic fluid-structure interaction: an assessment of the challenge of flutter analysis

Computational modelling of dynamic fluid-structure interaction (DFSI) is problematical since conventionally computational fluid dynamics (CFD) is solved using finite volume (FV) methods and computational structural mechanics (CSM) is based entirely on finite element (FE) methods. Hence, progress in modelling the emerging multi-physics problem of dynamic fluid-structure interaction in a consistent manner is frustrated and significant problems in computation convergence may be encountered in transferring and filtering data from one mesh and solution procedure to another, unless the fluid-structure coupling is either one way, very weak or both. This paper sets out the solution procedure for modelling the multi-physics dynamic fluid-structure interaction problem within a single software framework PHYSICA, using finite volume, unstructured mesh (FV-UM) procedures and will focus upon some of the problems and issues that have to be resolved for time accurate closely coupled dynamic fluid-structure flutter analysis.