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.

A domain decomposition algorithm for inverse welding problems

A mathematical model and a numerical scheme for the inverse determination of heat sources generated by means of a welding process is presented in this paper. The accuracy of the heat source retrieval is discussed.

Scheduling problems for parallel dedicated machines under multiple resource constraints

The paper considers scheduling problems for parallel dedicated machines subject to resource constraints. A fairly complete computational complexity classification is obtained, a number of polynomial-time algorithms are designed. For the problem with a fixed number of machines in which a job uses at most one resource of unit size a polynomial-time approximation scheme is offered.

A vertex-based finite volume method applied to non-linear material problems in computational solid mechanics

A vertex-based finite volume (FV) method is presented for the computational solution of quasi-static solid mechanics problems involving material non-linearity and infinitesimal strains. The problems are analysed numerically with fully unstructured meshes that consist of a variety of two- and threedimensional element types. A detailed comparison between the vertex-based FV and the standard Galerkin FE methods is provided with regard to discretization, solution accuracy and computational efficiency. For some problem classes a direct equivalence of the two methods is demonstrated, both theoretically and numerically. However, for other problems some interesting advantages and disadvantages of the FV formulation over the Galerkin FE method are highlighted.

A generic time and space accurate numerical approach to closely coupled fluid-structure interaction problems

Fluid structure interaction, as applied to flexible structures, has wide application in diverse areas such as flutter in aircraft, flow in elastic pipes and blood vessels and extrusion of metals through dies. However a comprehensive computational model of these multi-physics phenomena is a considerable challenge. Until recently work in this area focused on one phenomenon and represented the behaviour of the other more simply even to the extent in metal forming, for example, that the deformation of the die is totally ignored. More recently, strategies for solving the full coupling between the fluid and soild mechanics behaviour have developed. Conventionally, the computational modelling of fluid structure interaction is problematical since computational fluid dynamics (CFD) is solved using finite volume (FV) methods and computational structural mechanics (CSM) is based entirely on finite element (FE) methods. In the past the concurrent, but rather disparate, development paths for the finite element and finite volume methods have resulted in numerical software tools for CFD and CSM that are different in almost every respect. Hence, progress is frustrated in modelling the emerging multi-physics problem of fluid structure interaction in a consistent manner. Unless the fluid-structure coupling is either one way, very weak or both, transferring and filtering data from one mesh and solution procedure to another may lead to significant problems in computational convergence. Using a novel three phase technique the full interaction between the fluid and the dynamic structural response are represented. The procedure is demonstrated on some challenging applications in complex three dimensional geometries involving aircraft flutter, metal forming and blood flow in arteries.

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.

Flow shop scheduling problems under machine–dependent precedence constraints

The paper considers the flow shop scheduling problems to minimize the makespan, provided that an individual precedence relation is specified on each machine. A fairly complete complexity classification of problems with two and three machines is obtained.

Domain decomposition methods for welding problems

This paper, a 2-D non-linear electric arc-welding problem is considered. It is assumed that the moving arc generates an unknown quantity of energy which makes the problem an inverse problem with an unknown source. Robust algorithms to solve such problems e#ciently, and in certain circumstances in real-time, are of great technological and industrial interest. There are other types of inverse problems which involve inverse determination of heat conductivity or material properties [CDJ63][TE98], inverse problems in material cutting [ILPP98], and retrieval of parameters containing discontinuities [IK90]. As in the metal cutting problem, the temperature of a very hot surface is required and it relies on the use of thermocouples. Here, the solution scheme requires temperature measurements lied in the neighbourhood of the weld line in order to retrieve the unknown heat source. The size of this neighbourhood is not considered in this paper, but rather a domain decomposition concept is presented and an examination of the accuracy of the retrieved source are presented. This paper is organised as follows. The inverse problem is formulated and a method for the source retrieval is presented in the second section. The source retrieval method is based on an extension of the 1-D source retrieval method as proposed in [ILP].

Multilevel refinement for combinatorial optimisation problems

We consider the multilevel paradigm and its potential to aid the solution of combinatorial optimisation problems. The multilevel paradigm is a simple one, which involves recursive coarsening to create a hierarchy of approximations to the original problem. An initial solution is found (sometimes for the original problem, sometimes the coarsest) and then iteratively refined at each level. As a general solution strategy, the multilevel paradigm has been in use for many years and has been applied to many problem areas (most notably in the form of multigrid techniques). However, with the exception of the graph partitioning problem, multilevel techniques have not been widely applied to combinatorial optimisation problems. In this paper we address the issue of multilevel refinement for such problems and, with the aid of examples and results in graph partitioning, graph colouring and the travelling salesman problem, make a case for its use as a metaheuristic. The results provide compelling evidence that, although the multilevel framework cannot be considered as a panacea for combinatorial problems, it can provide an extremely useful addition to the combinatorial optimisation toolkit. We also give a possible explanation for the underlying process and extract some generic guidelines for its future use on other combinatorial problems.

Two-machine flow shop scheduling problems with no-wait jobs

In this paper we provide a fairly complete complexity classification of various versions of the two-machine permutation flow shop scheduling problem to minimize the makespan in which some of the jobs have to be processed with no-wait in process. For some version, we offer a fully polynomial-time approximation scheme and a 43-approximation algorithm.

Pre-emptive scheduling problems with controllable processing times

We consider a range of single machine and identical parallel machine pre-emptive scheduling models with controllable processing times. For each model we study a single criterion problem to minimize the compression cost of the processing times subject to the constraint that all due dates should be met. We demonstrate that each single criterion problem can be formulated in terms of minimizing a linear function over a polymatroid, and this justifies the greedy approach to its solution. A unified technique allows us to develop fast algorithms for solving both single criterion problems and bicriteria counterparts.

Numerical simulation of incompressible flow problems using an unstructured staggered mesh method

A number of two dimensional staggered unstructured discretisation schemes for the solution of fluid flow and heat transfer problems have been developed. All schemes store and solve velocity vector components at cell faces with scalar variables solved at cell centres. The velocity is resolved into face-normal and face-parallel components and the various schemes investigated differ in the treatment of the parallel component. Steady-state and time-dependent fluid flow and thermal energy equations are solved with the well known pressure correction scheme, SIMPLE, employed to couple continuity and momentum. The numerical methods developed are tested on well known benchmark cases: the Lid-Driven Cavity, Natural Convection in a Cavity and Melting of Gallium in a rectangular domain. The results obtained are shown to be comparable to benchmark, but with accuracy dependent on scheme selection.

Parallel genetic algorithms for the solution of inverse heat conduction problems

A parallel genetic algorithm (PGA) is proposed for the solution of two-dimensional inverse heat conduction problems involving unknown thermophysical material properties. Experimental results show that the proposed PGA is a feasible and effective optimization tool for inverse heat conduction problems

A hybrid Laplace transform/finite difference boundary element method for diffusion problems

The solution process for diffusion problems usually involves the time development separately from the space solution. A finite difference algorithm in time requires a sequential time development in which all previous values must be determined prior to the current value. The Stehfest Laplace transform algorithm, however, allows time solutions without the knowledge of prior values. It is of interest to be able to develop a time-domain decomposition suitable for implementation in a parallel environment. One such possibility is to use the Laplace transform to develop coarse-grained solutions which act as the initial values for a set of fine-grained solutions. The independence of the Laplace transform solutions means that we do indeed have a time-domain decomposition process. Any suitable time solver can be used for the fine-grained solution. To illustrate the technique we shall use an Euler solver in time together with the dual reciprocity boundary element method for the space solution