Minimizing total completion time on a batch processing machine with job families

We consider the problem of minimizing the total completion time on a single batch processing machine. The set of jobs to be scheduled can be partitioned into a number of families, where all jobs in the same family have the same processing time. The machine can process at most B jobs simultaneously as a batch, and the processing time of a batch is equal to the processing time of the longest job in the batch. We analyze that properties of an optimal schedule and develop a dynamic programming algorithm of polynomial time complexity when the number of job families is fixed. The research is motivated by the problem of scheduling burn-in ovens in the semiconductor industry

Minimizing total completion time on batch processing machines

We study the problem of minimizing total completion time on single and parallel batch processing machines. A batch processing machine is one which can process up to B jobs simultaneously. The processing time of a batch is equal to the largest processing time among all jobs in the batch. This problem is motivated by burn-in operations in the final testing stage of semiconductor manufacturing and is expected to occur in other production environments. We provide an exact solution procedure for the single-machine problem and heuristic algorithms for both single and parallel machine problems. While the exact algorithms have limited applicability due to high computational requirements, extensive experiments show that the heuristics are capable of consistently obtaining near-optimal solutions in very reasonable CPU times.

Bi-criteria single machine scheduling problem with a learning effect: Aneja-Nair method to obtain the set of optimal sequences

In this paper, we consider the bi-criteria single machine scheduling problem of n jobs with a learning effect. The two objectives considered are the total completion time (TC) and total absolute differences in completion times (TADC). The objective is to find a sequence that performs well with respect to both the objectives: the total completion time and the total absolute differences in completion times. In an earlier study, a method of solving bi-criteria transportation problem is presented. In this paper, we use the methodology of solvin bi-criteria transportation problem, to our bi-criteria single machine scheduling problem with a learning effect, and obtain the set of optimal sequences,. Numerical examples are presented for illustrating the applicability and ease of understanding.

Rise Time of a Surface-Acoustic-Wave Resonator

This paper presents the results of the rise time calculation of a SAW resonator. The total rise time is given by rise time = [(rise time of cavity)2 + (rise time of reflectors)2 + (rise time of IDT) 2 ]. 1/2 These rise times are calculated in terms of the effective length of the cavity , the characteristics of the reflector, and the number of finger pairs in the IDT. The rise time of a 38 MHz one-port resonator on Y-Z LiNb03 calculated using this approach is found to be in good agreement with experimental results .

Task assignment in a multiprocessor system

One of the key problems in the design of any incompletely connected multiprocessor system is to appropriately assign the set of tasks in a program to the Processing Elements (PEs) in the system. The task assignment problem has proven difficult both in theory and in practice. This paper presents a simple and efficient heuristic algorithm for assigning program tasks with precedence and communication constraints to the PEs in a Message-based Multiple-bus Multiprocessor System, M3, so that the total execution time for the program is minimized. The algorithm uses a cost function: “Minimum Distance and Parallel Transfer” to minimize the completion time. The effectiveness of the algorithm has been demonstrated by comparing the results with (i) the lower bound on the execution time of a program (task) graph and (ii) a random assignment.

Compiling Techniques for Coarse Grained Runtime Reconfigurable Architectures

In this paper we develop compilation techniques for the realization of applications described in a High Level Language (HLL) onto a Runtime Reconfigurable Architecture. The compiler determines Hyper Operations (HyperOps) that are subgraphs of a data flow graph (of an application) and comprise elementary operations that have strong producer-consumer relationship. These HyperOps are hosted on computation structures that are provisioned on demand at runtime. We also report compiler optimizations that collectively reduce the overheads of data-driven computations in runtime reconfigurable architectures. On an average, HyperOps offer a 44% reduction in total execution time and a 18% reduction in management overheads as compared to using basic blocks as coarse grained operations. We show that HyperOps formed using our compiler are suitable to support data flow software pipelining.

Dendritic structures produced on solidification of multicomponent aqueous solutions

Dendrite structures of ice produced on undirectional solidification of ternary and quaternary aqueous solutions have been studied. Upon freezing, solutions containing more than one solute produce plate-shaped dendrites of ice. The spacing between dendrites increase linearly with the distance from the chill surface and the square root of local solidification time (or square root of inverse freezing rate) for any fixed composition. For fixed freezing conditions, the dendrite spacings from multicomponent aqueous solutions were a function of the concentrations and diffusion coefficients of the individual solutes. The dendrite spacing produced by freezing of a solution was changed by the addition of a solute different from those already present. If the main diffusion coefficient of the added solute is higher than that of solutes already present, the dendrite spacing is increased and vice versa. The dendrite spacing in multi-component systems increases with the total solute concentration if the constituent solutes are present in equal amounts. The dendrite spacing obtained on freezing of these dilute multicomponent solutions can be expressed by regression equations of the type Image Full-size image (2K) where L is the dendrite spacing in microns, C1, C2 and C3 are concentrations of individual solutes, Θf is the total freezing time and A1 −A8 are constants. A Yates analysis of the dendrite spacings in a factorial design of quaternary solutions indicates that there are strong interactions between individual solutes in regard to their effect on the dendrite spacings. A mass transport analysis has been used to calculate the interdendritic supersaturation ΔC of the individual solutes, the supercooling in the interdendritic liquid ΔT, and the transverse growth velocity of the dendrites, VT. In ternary solutions if two solutes are present in equal amount the supersaturation of the solute with higher main diffusion coefficient is lower, and vice versa. If a solute with higher main diffusion coefficient is added to a binary solution, the interface growth velocity, the interdendritic supersaturation of the base solute and the interdendritic supercooling increase with the quantity of solute added.

The problem of liquid droplet combustion-reexamination

The simple quasi-steady analysis of the combustion of a liquid fuel droplet in an oxidising atmosphere provides unsatisfactory explanations for several experimental observations. It's prediction of values for the burning constant (K), the flame-to-droplet diameter ratio ( ) and the flame temperature (Tf) have been found to be amgibuous if not completely inaccurate. A critical survey of the literature has led us to a detailed examination of the effects of unsteadiness and variable properties. The work published to date indicates that the gas-phase unsteadiness is relatively short and therefore quite insignificant.A new theoretical analysis based on heat transfer within the droplet is presented here. It shows that the condensed-phase unsteadiness lasts for about 20â??25% of the total burning time. It is concluded that the discrepancies between experimental observations and the predictions of the constant-property quasi-steady analysis cannot be attributed either to gas-phase or condensed-phase unsteadiness.An analytical model of quasi-steady droplet combustion with variable thermodynamic and transport properties and non-unity Lewis numbers will be examined. Further findings reveal a significant improvement in the prediction of combustion parameters, particularly of K, when consideration is given to variations of cp and λ with the temperature and concentrations of several species. Tf is accurately predicted when the required conditions of incomplete combustion or low ( ) at the flame are met. Further refinement through realistic Lewis numbers predicts ( ) meaningfully.

Control of transient thermal response during sequential open-die forging: A trajectory optimization approach

A trajectory optimization approach is applied to the design of a sequence of open-die forging operations in order to control the transient thermal response of a large titanium alloy billet. The amount of time tire billet is soaked in furnace prior to each successive forging operation is optimized to minimize the total process time while simultaneously satisfying constraints on the maximum and minimum values of the billet's temperature distribution to avoid microstructural defects during forging. The results indicate that a "differential" heating profile is the most effective at meeting these design goals.

Determination of solid fraction evolution during solidification of aluminum alloy in presence of linear electromagnetic stirring

In many industrial casting processes, knowledge of the solid fraction evolution during the solidification process is a key factor in determining the process parameters such as cooling rate, stirring intensity and in estimating the total solidification time. In the present work, a new method of estimating solid fraction is presented, which is based on calorimetric principles. In this method, the cooling curve data at each point in the melt, along with the thermal boundary conditions, are used to perform energy balance in the mould, from which solid fraction generation during any time interval can be estimated. This method is applied to the case of a rheocasting process, in which Al-Si alloy (A356 alloy) is solidified by stirring in a cylindrical mould placed in the annulus of a linear electromagnetic stirrer. The metal in the mould is simultaneously cooled and stirred to produce a cylindrical billet with non-dendritic globular microstructure. Temperature is measured at key locations in the mould to assess the various heat exchange processes prevalent in the mould and to monitor the solidification rate. The results obtained by energy balance method are compared with those by the conventional procedure of calculating solid fraction using the Schiel equation.

Scheduling a Burn-In Oven with Non-Agreeable Release Times and Due Dates

We consider the problem of scheduling semiconductor burn-in operations, where burn-in ovens are modelled as batch processing machines. Most of the studies assume that ready times and due dates of jobs are agreeable (i.e., ri < rj implies di ≤ dj). In many real world applications, the agreeable property assumption does not hold. Therefore, in this paper, scheduling of a single burn-in oven with non-agreeable release times and due dates along with non-identical job sizes as well as non-identical processing of time problem is formulated as a Non-Linear (0-1) Integer Programming optimisation problem. The objective measure of the problem is minimising the maximum completion time (makespan) of all jobs. Due to computational intractability, we have proposed four variants of a two-phase greedy heuristic algorithm. Computational experiments indicate that two out of four proposed algorithms have excellent average performance and also capable of solving any large-scale real life problems with a relatively low computational effort on a Pentium IV computer.

High temperature time-dependent low cycle fatigue behaviour of a type 316L(N) stainless steel

Total strain controlled low cycle fatigue tests on 316L(N) stainless steel have been conducted in air at various strain rates in the temperature range of 773-873 K to identify the operative time-dependent mechanisms and to understand their influence on the cyclic deformation and fracture behaviour of the alloy. The cyclic stress response at all the testing conditions was marked by an initial hardening followed by stress saturation. A negative strain rate stress response is observed under specific testing conditions which is attributed to dynamic strain ageing (DSA). Transmission electron microscopy studies reveal that there is an increase in the dislocation density and enhanced slip planarity in the DSA regime. Fatigue life is found to decrease with a decrease in strain rate. The degradation in fatigue resistance is attributed to the detrimental effects associated with DSA and oxidation. Quantitative measurement of secondary cracks indicate that both transgranular and intergranular cracking are accelerated predominantly under conditions conducive to DSA.

Time dependence of effective slip on textured hydrophobic surfaces

In this paper, we present results on water flow past randomly textured hydrophobic surfaces with relatively large surface features of the order of 50 µm. Direct shear stress measurements are made on these surfaces in a channel configuration. The measurements indicate that the flow rates required to maintain a shear stress value vary substantially with water immersion time. At small times after filling the channel with water, the flow rates are up to 30% higher compared with the reference hydrophilic surface. With time, the flow rate gradually decreases and in a few hours reaches a value that is nearly the same as the hydrophilic case. Calculations of the effective slip lengths indicate that it varies from about 50 µm at small times to nearly zero or “no slip” after a few hours. Large effective slip lengths on such hydrophobic surfaces are known to be caused by trapped air pockets in the crevices of the surface. In order to understand the time dependent effective slip length, direct visualization of trapped air pockets is made in stationary water using the principle of total internal reflection of light at the water-air interface of the air pockets. These visualizations indicate that the number of bright spots corresponding to the air pockets decreases with time. This type of gradual disappearance of the trapped air pockets is possibly the reason for the decrease in effective slip length with time in the flow experiments. From the practical point of usage of such surfaces to reduce pressure drop, say, in microchannels, this time scale of the order of 1 h for the reduction in slip length would be very crucial. It would ultimately decide the time over which the surface can usefully provide pressure drop reductions. ©2009 American Institute of Physics

Some Generalisations of the Time Minimising Assignment Problem

The time minimising assignment problem is the problem of finding an assignment of n jobs to n facilities, one to each, which minimises the total time for completing all the jobs. The usual assumption made in these problems is that all the jobs are commenced simultaneously. In this paper two generalisations of this assumption are considered, and algorithms are presented to solve these general problems. Numerical examples are worked out illustrating the algorithms.

Application of the Conjugate Gradient Method to a Problem on Minimum Time Orbit Transfer

This correspondence considers the problem of optimally controlling the thrust steering angle of an ion-propelled spaceship so as to effect a minimum time coplanar orbit transfer from the mean orbital distance of Earth to mean Martian and Venusian orbital distances. This problem has been modelled as a free terminal time-optimal control problem with unbounded control variable and with state variable equality constraints at the final time. The problem has been solved by the penalty function approach, using the conjugate gradient algorithm. In general, the optimal solution shows a significant departure from earlier work. In particular, the optimal control in the case of Earth-Mars orbit transfer, during the initial phase of the spaceship's flight, is found to be negative, resulting in the motion of the spaceship within the Earth's orbit for a significant fraction of the total optimized orbit transfer time. Such a feature exhibited by the optimal solution has not been reported at all by earlier investigators of this problem.