Shop-scheduling problems with fixed and non-fixed machine orders of the jobs

The paper deals with the determination of an optimal schedule for the so-called mixed shop problem when the makespan has to be minimized. In such a problem, some jobs have fixed machine orders (as in the job-shop), while the operations of the other jobs may be processed in arbitrary order (as in the open-shop). We prove binary NP-hardness of the preemptive problem with three machines and three jobs (two jobs have fixed machine orders and one may have an arbitrary machine order). We answer all other remaining open questions on the complexity status of mixed-shop problems with the makespan criterion by presenting different polynomial and pseudopolynomial algorithms.

Two fluid approach to high speed impact interaction amongst solid structures

The issues surrounding collision of projectiles with structures has gained a high profile since the events of 11th September 2001. In such collision problems, the projectile penetrates the stucture so that tracking the interface between one material and another becomes very complex, especially if the projectile is essentially a vessel containing a fluid, e.g. fuel load. The subsequent combustion, heat transfer and melting and re-solidification process in the structure render this a very challenging computational modelling problem. The conventional approaches to the analysis of collision processes involves a Lagrangian-Lagrangian contact driven methodology. This approach suffers from a number of disadvantages in its implementation, most of which are associated with the challenges of the contact analysis component of the calculations. This paper describes a 'two fluid' approach to high speed impact between solid structures, where the objective is to overcome the problems of penetration and re-meshing. The work has been carried out using the finite volume, unstructured mesh multi-physics code PHYSICA+, where the three dimensional fluid flow, free surface, heat transfer, combustion, melting and re-solidification algorithms are approximated using cell-centred finite volume, unstructured mesh techniques on a collocated mesh. The basic procedure is illustrated for two cases of Newtonian and non-Newtonian flow to test various of its component capabilities in the analysis of problems of industrial interest.

Two simple constant ratio approximation algorithms for minimizing the total weighted completion time on a single machine with a fixed non-availability interval

In this note, we consider the scheduling problem of minimizing the sum of the weighted completion times on a single machine with one non-availability interval on the machine under the non-resumable scenario. Together with a recent 2-approximation algorithm designed by Kacem [I. Kacem, Approximation algorithm for the weighted flow-time minimization on a single machine with a fixed non-availability interval, Computers & Industrial Engineering 54 (2008) 401–410], this paper is the first successful attempt to develop a constant ratio approximation algorithm for this problem. We present two approaches to designing such an algorithm. Our best algorithm guarantees a worst-case performance ratio of 2+ε. © 2008 Elsevier B.V. All rights reserved.

Evaluation of particle degradation due to high-speed impacts in a pneumatic handling system

Particle degradation can be a significant issue in particulate solids handling and processing, particularly in pneumatic conveying systems, in which high-speed impact is usually the main contributory factor leading to changes in particle size distribution (comparing the material to its virgin state). However, other factors may strongly influence particles breakage as well, such as particle concentrations, bend geometry,and hardness of pipe material. Because of such complex influences, it is often very difficult to predict particle degradation accurately and rapidly for industrial processes. In this article, a general method for evaluating particle degradation due to high-speed impacts is described, in which the breakage properties of particles are quantified using what are known as "breakage matrices". Rather than a pilot-size test facility, a bench-scale degradation tester has been used. Some advantages of using the bench-scale tester are briefly explored. Experimental determination of adipic acid has been carried out for a range of impact velocities in four particle size categories. Subsequently, particle breakage matrices of adipic acid have been established for these impact velocities. The experimental results show that the "breakage matrices" of particles is an effective and easy method for evaluation of particle degradation due to high-speed impacts. The possibility of the "breakage matrices" approach being applied to a pneumatic conveying system is also explored by a simulation example.