Heuristic algorithms for scheduling of a batch processor in automobile gear manufacturing

In this paper we address a scheduling problem for minimising total weighted tardiness. The motivation for the paper comes from the automobile gear manufacturing process. We consider the bottleneck operation of heat treatment stage of gear manufacturing. Real life scenarios like unequal release times, incompatible job families, non-identical job sizes and allowance for job splitting have been considered. A mathematical model taking into account dynamic starting conditions has been developed. Due to the NP-hard nature of the problem, a few heuristic algorithms have been proposed. The performance of the proposed heuristic algorithms is evaluated: (a) in comparison with optimal solution for small size problem instances, and (b) in comparison with `estimated optimal solution' for large size problem instances. Extensive computational analyses reveal that the proposed heuristic algorithms are capable of consistently obtaining near-optimal solutions (that is, statistically estimated one) in very reasonable computational time.

Cooperative Spectrum Sensing Algorithms For OFDM Systems with Frequency Selective Channels

This paper considers the problem of spectrum sensing in cognitive radio networks when the primary user employs Orthogonal Frequency Division Multiplexing (OFDM). We specifically consider the scenario when the channel between the primary and a secondary user is frequency selective. We develop cooperative sequential detection algorithms based on energy detectors. We modify the detectors to mitigate the effects of some common model uncertainties such as timing and frequency offset, IQ-imbalance and uncertainty in noise and transmit power. The performance of the proposed algorithms are studied via simulations. We show that the performance of the energy detector is not affected by the frequency selective channel. We also provide a theoretical analysis for some of our algorithms.

Measurement of complex optical flow with use of an augmented generalized gradient scheme

We present a method for measuring the local velocities and first-order variations in velocities in a timevarying image. The scheme is an extension of the generalized gradient model that encompasses the local variation of velocity within a local patch of the image. Motion within a patch is analyzed in parallel by 42 different spatiotemporal filters derived from 6 linearly independent spatiotemporal kernels. No constraints are imposed on the image structure, and there is no need for smoothness constraints on the velocity field. The aperture problem does not arise so long as there is some two-dimensional structure in the patch being analyzed. Among the advantages of the scheme is that there is no requirement to calculate second or higher derivatives of the image function. This makes the scheme robust in the presence of noise. The spatiotemporal kernels are of simple form, involving Gaussian functions, and are biologically plausible receptive fields. The validity of the scheme is demonstrated by application to both synthetic and real video images sequences and by direct comparison with another recently published scheme Biol. Cybern. 63, 185 (1990)] for the measurement of complex optical flow.

Genetic algorithms: a survey

Genetic algorithms provide an alternative to traditional optimization techniques by using directed random searches to locate optimal solutions in complex landscapes. We introduce the art and science of genetic algorithms and survey current issues in GA theory and practice. We do not present a detailed study, instead, we offer a quick guide into the labyrinth of GA research. First, we draw the analogy between genetic algorithms and the search processes in nature. Then we describe the genetic algorithm that Holland introduced in 1975 and the workings of GAs. After a survey of techniques proposed as improvements to Holland's GA and of some radically different approaches, we survey the advances in GA theory related to modeling, dynamics, and deception

Gradient solid electrolytes for thermodynamic measurements: System Na2CO3-Na2SO4

The thermodynamic properties of Na2CO3-Na2SO4 solid solution with hexagonal structure have been measured in the temperature range of 873 to 1073 K, using a composite-gradient solid electrolyte. The cell used can be represented as The composite-gradient solid electrolyte consisted of pure Na2CO3 at one extremity and the solid solution under study at the other, with variation in composition across the electrolyte. A CO2 + O2 + Ar gas mixture was used to fix the chemical potential of sodium at each electrode. The Nernstian response of the cell to changes in partial pressures of CO2 and O2 at the electrodes has been demonstrated. The activity of Na2CO3 in the solid solution was measured by two techniques. In the first method, the electromotive force (emf) of the cell was measured with the same CO2 + O2 + Ar mixture at both electrodes. The resultant emf is directly related to the activity of Na2CO3 at the solid solution electrode. By the second approach, the activity was calculated from the difference in compositions Of CO2 + O2 + Ar mixtures at the two electrodes required to produce a null emf. Both methods gave identical results. The second method is more suitable for gradient solid electrolytes that exhibit significant electronic conduction. The activity of Na2CO3 exhibits positive deviation from Raoult's law. The excess Gibbs' energy of mixing of the solid solution can be represented using a subregular solution model such as the following: DELTAG(E) = X(1 - X)[6500(+/-200)X + 3320(+/-80)(1 - X)J mol-1 where X is the mole fraction of Na2CO3. By combining this information with the phase diagram, mixing properties of the liquid phase are obtained.

Managing interprocessor delays in distributed recursive algorithms

For a class of distributed recursive algorithms, it is shown that a stochastic approximation-like tapering stepsize routine suppresses the effects of interprocessor delays.

Measurement of complex optical flow with use of an augmented generalized gradient scheme

We present a method for measuring the local velocities and first-order variations in velocities in a time-varying image. The scheme is an extension of the generalized gradient model that encompasses the local variation of velocity within a local patch of the image. Motion within a patch is analyzed in parallel by 42 different spatiotemporal filters derived from 6 linearly independent spatiotemporal kernels. No constraints are imposed on the image structure, and there is no need for smoothness constraints on the velocity field. The aperture problem does not arise so long as there is some two-dimensional structure in the patch being analyzed. Among the advantages of the scheme is that there is no requirement to calculate second or higher derivatives of the image function. This makes the scheme robust in the presence of noise. The spatiotemporal kernels are of simple form, involving Gaussian functions, and are biologically plausible receptive fields. The validity of the scheme is demonstrated by application to both synthetic and real video images sequences and by direct comparison with another recently published scheme [Biol. Cybern. 63, 185 (1990)] for the measurement of complex optical flow.

Variable Sparsity Kernel Learning

This paper(1) presents novel algorithms and applications for a particular class of mixed-norm regularization based Multiple Kernel Learning (MKL) formulations. The formulations assume that the given kernels are grouped and employ l(1) norm regularization for promoting sparsity within RKHS norms of each group and l(s), s >= 2 norm regularization for promoting non-sparse combinations across groups. Various sparsity levels in combining the kernels can be achieved by varying the grouping of kernels-hence we name the formulations as Variable Sparsity Kernel Learning (VSKL) formulations. While previous attempts have a non-convex formulation, here we present a convex formulation which admits efficient Mirror-Descent (MD) based solving techniques. The proposed MD based algorithm optimizes over product of simplices and has a computational complexity of O (m(2)n(tot) log n(max)/epsilon(2)) where m is no. training data points, n(max), n(tot) are the maximum no. kernels in any group, total no. kernels respectively and epsilon is the error in approximating the objective. A detailed proof of convergence of the algorithm is also presented. Experimental results show that the VSKL formulations are well-suited for multi-modal learning tasks like object categorization. Results also show that the MD based algorithm outperforms state-of-the-art MKL solvers in terms of computational efficiency.

Line clipping revisited: Two efficient algorithms based on simple geometric observations

Two new line clipping algorithms, the opposite-corner algorithm and the perpendicular-distance algorithm, that are based on simple geometric observations are presented. These algorithms do not require computation of outcodes nor do they depend on the parametric representations of the lines. It is shown that the opposite-corner algorithm perform consistently better than an algorithm due to Nicholl, Lee, and Nicholl which is claimed to be better than the classic algorithm due to Cohen-Sutherland and the more recent Liang-Barsky algorithm. The pseudo-code of the opposite-corner algorithm is provided in the Appendix.

S-nets: A Petri net based model for performance evaluation of real-time scheduling algorithms

A new class of nets, called S-nets, is introduced for the performance analysis of scheduling algorithms used in real-time systems Deterministic timed Petri nets do not adequately model the scheduling of resources encountered in real-time systems, and need to be augmented with resource places and signal places, and a scheduler block, to facilitate the modeling of scheduling algorithms. The tokens are colored, and the transition firing rules are suitably modified. Further, the concept of transition folding is used, to get intuitively simple models of multiframe real-time systems. Two generic performance measures, called �load index� and �balance index,� which characterize the resource utilization and the uniformity of workload distribution, respectively, are defined. The utility of S-nets for evaluating heuristic-based scheduling schemes is illustrated by considering three heuristics for real-time scheduling. S-nets are useful in tuning the hardware configuration and the underlying scheduling policy, so that the system utilization is maximized, and the workload distribution among the computing resources is balanced.

Some Algorithms for Eigensubspace Estimation

An important tool in signal processing is the use of eigenvalue and singular value decompositions for extracting information from time-series/sensor array data. These tools are used in the so-called subspace methods that underlie solutions to the harmonic retrieval problem in time series and the directions-of-arrival (DOA) estimation problem in array processing. The subspace methods require the knowledge of eigenvectors of the underlying covariance matrix to estimate the parameters of interest. Eigenstructure estimation in signal processing has two important classes: (i) estimating the eigenstructure of the given covariance matrix and (ii) updating the eigenstructure estimates given the current estimate and new data. In this paper, we survey some algorithms for both these classes useful for harmonic retrieval and DOA estimation problems. We begin by surveying key results in the literature and then describe, in some detail, energy function minimization approaches that underlie a class of feedback neural networks. Our approaches estimate some or all of the eigenvectors corresponding to the repeated minimum eigenvalue and also multiple orthogonal eigenvectors corresponding to the ordered eigenvalues of the covariance matrix. Our presentation includes some supporting analysis and simulation results. We may point out here that eigensubspace estimation is a vast area and all aspects of this cannot be fully covered in a single paper. (C) 1995 Academic Press, Inc.

Theoretical Analysis of the Electromotive Force of a Cell Incorporating a Composition Gradient Solid Electrolyte

New composition gradient solid electrolytes have been designed for application in high temperature solid-state galvanic sensors and in thermodynamic measurements. The functionally gradient electrolyte consists of a solid solution between two or more ionic conductors with a common ion and gradual variation in composition of the other ionic species. Unequal rates of migration of the ions, caused by the presence of the concentration gradient, may result in the development of space charge, manifesting as diffusion potential. Presented is a theoretical analysis of the EMF of cells incorporating gradient solid electrolytes. An analytical expression is derived for diffusion potential, using the thermodynamics of irreversible processes, for different types of concentration gradients and boundary conditions at the electrode/electrolyte interfaces. The diffusion potential of an isothermal cell incorporating these gradient electrolytes becomes negligible if there is only one mobile ion and the transport numbers of the relatively immobile polyionic species and electrons approach zero. The analysis of the EMF of a nonisothermal cell incorporating a composition gradient solid electrolyte indicates that the cell EMF can be expressed in terms of the thermodynamic parameters at the electrodes and the Seebeck coefficient of the gradient electrolyte under standard conditions when the transport number of one of the ions approaches unity.

On an exact populationary model of genetic algorithms

Genetic algorithms (GAs) are search methods that are being employed in a multitude of applications with extremely large search spaces. Recently, there has been considerable interest among GA researchers in understanding and formalizing the working of GAs. In an earlier paper, we have introduced the notion of binomially distributed populations as the central idea behind an exact ''populationary'' model of the large-population dynamics of the GA operators for objective functions called ''functions of unitation.'' In this paper, we extend this populationary model of GA dynamics to a more general class of objective functions called functions of unitation variables. We generalize the notion of a binomially distributed population to a generalized binomially distributed population (GBDP). We show that the effects of selection, crossover, and mutation can be exactly modelled after decomposing the population into GBDPs. Based on this generalized model, we have implemented a GA simulator for functions of two unitation variables-GASIM 2, and the distributions predicted by GASIM 2 match with those obtained from actual GA runs. The generalized populationary model of GA dynamics not only presents a novel and natural way of interpreting the workings of GAs with large populations, but it also provides for an efficient implementation of the model as a GA simulator. (C) Elsevier Science Inc. 1997.

Some algorithms for discrete time queues with finite capacity

We consider a discrete time queue with finite capacity and i.i.d. and Markov modulated arrivals, Efficient algorithms are developed to calculate the moments and the distributions of the first time to overflow and the regeneration length, Results are extended to the multiserver queue. Some illustrative numerical examples are provided.

Synthesis of ASIPs for DSP algorithms

ASICs offer the best realization of DSP algorithms in terms of performance, but the cost is prohibitive, especially when the volumes involved are low. However, if the architecture synthesis trajectory for such algorithms is such that the target architecture can be identified as an interconnection of elementary parameterized computational structures, then it is possible to attain a close match, both in terms of performance and power with respect to an ASIC, for any algorithmic parameters of the given algorithm. Such an architecture is weakly programmable (configurable) and can be viewed as an application specific integrated processor (ASIP). In this work, we present a methodology to synthesize ASIPs for DSP algorithms. (C) 1999 Elsevier Science B.V. All rights reserved.