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.

Multilevel refinement for combinatorial optimisation: boosting metaheuristic performance

The multilevel paradigm as applied to combinatorial optimisation problems is a simple one, which at its most basic involves recursive coarsening to create a hierarchy of approximations to the original problem. An initial solution is found, usually at the coarsest level, and then iteratively refined at each level, coarsest to finest, typically by using some kind of heuristic optimisation algorithm (either a problem-specific local search scheme or a metaheuristic). Solution extension (or projection) operators can transfer the solution from one level to another. As a general solution strategy, the multilevel paradigm has been in use for many years and has been applied to many problem areas (for example multigrid techniques can be viewed as a prime example of the paradigm). Overview papers such as [] attest to its efficacy. However, with the exception of the graph partitioning problem, multilevel techniques have not been widely applied to combinatorial problems and in this chapter we discuss recent developments. In this chapter we survey the use of multilevel combinatorial techniques and consider their ability to boost the performance of (meta)heuristic optimisation algorithms.

Preface [Special Issue: International Symposium on Combinatorial Optimisation (CO2000)]

Preface [Special Issue containing a selection of papers presented at the International Symposium on Combinatorial Optimisation (CO2000) held at the University of Greenwich, London, from 12-14 July 2000.

Optimization and finite element analysis for reliable electronic packaging

This paper demonstrates a modeling and design approach that couples computational mechanics techniques with numerical optimisation and statistical models for virtual prototyping and testing in different application areas concerning reliability of eletronic packages. The integrated software modules provide a design engineer in the electronic manufacturing sector with fast design and process solutions by optimizing key parameters and taking into account complexity of certain operational conditions. The integrated modeling framework is obtained by coupling the multi-phsyics finite element framework - PHYSICA - with the numerical optimisation tool - VisualDOC into a fully automated design tool for solutions of electronic packaging problems. Response Surface Modeling Methodolgy and Design of Experiments statistical tools plus numerical optimisaiton techniques are demonstrated as a part of the modeling framework. Two different problems are discussed and solved using the integrated numerical FEM-Optimisation tool. First, an example of thermal management of an electronic package on a board is illustrated. Location of the device is optimized to ensure reduced junction temperature and stress in the die subject to certain cooling air profile and other heat dissipating active components. In the second example thermo-mechanical simulations of solder creep deformations are presented to predict flip-chip reliability and subsequently used to optimise the life-time of solder interconnects under thermal cycling.

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.

Fast divide-and-conquer algorithms for preemptive scheduling problems with controllable processing times - a polymatroid optimization approach

We consider a variety of preemptive scheduling problems with controllable processing times on a single machine and on identical/uniform parallel machines, where the objective is to minimize the total compression cost. In this paper, we propose fast divide-and-conquer algorithms for these scheduling problems. Our approach is based on the observation that each scheduling problem we discuss can be formulated as a polymatroid optimization problem. We develop a novel divide-and-conquer technique for the polymatroid optimization problem and then apply it to each scheduling problem. We show that each scheduling problem can be solved in $ \O({\rm T}_{\rm feas}(n) \times\log n)$ time by using our divide-and-conquer technique, where n is the number of jobs and Tfeas(n) denotes the time complexity of the corresponding feasible scheduling problem with n jobs. This approach yields faster algorithms for most of the scheduling problems discussed in this paper.

Optimization of an open-ended microwave oven for microelectronics packaging

A physically open, but electrically shielded, microwave open oven can be produced by virtue of the evanescent fields in a waveguide below cutoff. The below cutoff heating chamber is fed by a transverse magnetic resonance established in a dielectric-filled section of the waveguide exploiting continuity of normal electric flux. In order to optimize the fields and the performance of the oven, a thin layer of a dielectric material with higher permittivity is inserted at the interface. Analysis and synthesis of an optimized open oven predicts field enhancement in the heating chamber up to 9.4 dB. Results from experimental testing on two fabricated prototypes are in agreement with the simulated predictions, and demonstrate an up to tenfold improvement in the heating performance. The open-ended oven allows for simultaneous precision alignment, testing, and efficient curing of microelectronic devices, significantly increasing productivity gains.

Modelling and optimization of a pneumatic microfeeder system

This paper presents modelling and design optimization of a microfeeder which, as part of a microassembly system, is used for contactless object delivery. The microfeeder consists of an array of microactuators which are controlled by electrostatic actuation and used for maneuvering outcoming air jet for object hovering and delibery. The airflow behaviour in the microactuator is analysed by means of fluid mechanics and Computational Fluid Dynamics (CFD) simulation from three aspects, theoretical analysis, initial design assessment, and design modifications. The focus is put on the basic types of the microfeeder structure and the effects of structural details to the systematic performance. The structural pattern of the microactuator for forming airflow nozzle is identified and two design plans are proposed as basic structure patterns of pneumatic microactuators. The optimized design numerically shows the ability of delivering objects. This paper analyses the flow distribution pattern in microactuators and points out a way for effective design of pneumatic microfeeder systems. The optimization strategy provided by the present paper has close relevance to the design and manufacture of pneumatic microfeeder systems.

Parametrical modeling and design optimization of blood plasma separation device with microchannel mechanism

This paper presents an analysis of biofluid behavior in a T-shaped microchannel device and a design optimization for improved biofluid performance in terms of particle liquid separation. The biofluid is modeled with single phase shear rate non-Newtonian flow with blood property. The separation of red blood cell from plasma is evident based on biofluid distribution in the microchannels against various relevant effects and findings, including Zweifach-Fung bifurcation law, Fahraeus effect, Fahraeus-Lindqvist effect and cell free phenomenon. The modeling with the initial device shows that this T-microchannel device can separate red blood cell from plasma but the separation efficiency among different bifurcations varies largely. In accordance with the imbalanced performance, a design optimization is conducted. This includes implementing a series of simulations to investigate the effect of the lengths of the main and branch channels to biofluid behavior and searching an improved design with optimal separation performance. It is found that changing relative lengths of branch channels is effective to both uniformity of flow rate ratio among bifurcations and reduction of difference of the flow velocities between the branch channels, whereas extending the length of the main channel from bifurcation region is only effective for uniformity of flow rate ratio.

Using a modified shepards method for optimization of a nanoparticulate cyclosporine a formulation prepared by a static mixer technique

An innovative methodology has been used for the formulation development of Cyclosporine A (CyA) nanoparticles. In the present study the static mixer technique, which is a novel method for producing nanoparticles, was employed. The formulation optimum was calculated by the modified Shepard's method (MSM), an advanced data analysis technique not adopted so far in pharmaceutical applications. Controlled precipitation was achieved injecting the organic CyA solution rapidly into an aqueous protective solution by means of a static mixer. Furthermore the computer based MSM was implemented for data analysis, visualization, and application development. For the optimization studies, the gelatin/lipoid S75 amounts and the organic/aqueous phase were selected as independent variables while the obtained particle size as a dependent variable. The optimum predicted formulation was characterized by cryo-TEM microscopy, particle size measurements, stability, and in vitro release. The produced nanoparticles contain drug in amorphous state and decreased amounts of stabilizing agents. The dissolution rate of the lyophilized powder was significantly enhanced in the first 2 h. MSM was proved capable to interpret in detail and to predict with high accuracy the optimum formulation. The mixer technique was proved capable to develop CyA nanoparticulate formulations.