A hybrid algorithm for the manufacturing cell formation problem

In this paper we compare different heuristic methods for the manufacturing cell formation problem considering part process sequence: a GRASP algorithm, a reactive GRASP algorithm and a hybrid algorithm which combines reactive GRASP and tabu search. All algorithms are tested with a set of instances from the literature. The results from the GRASP algorithm are compared to those of the reactive GRASP in order to evaluate the advantages of automatically adjusting the parameter value within the randomized greedy procedure. Also the reactive GRASP results are compared to those of the hybrid algorithm to evaluate the contribution to solution quality of replacing the local search phase of the GRASP algorithm with tabu search.     

Synthesis of cryptographic interleaved sequences by means of linear cellular automata

This work shows that a class of pseudorandom binary sequences, the so-called interleaved sequences, can be generated by means of linear multiplicative polynomial cellular automata. In fact, these linear automata generate all the solutions of a type of linear difference equations with binary coefficients. Interleaved sequences are just particular solutions of such equations. In this way, popular nonlinear sequence generators with cryptographic application can be linearized in terms of simple cellular automata.     

New distance measures for classifying X-ray astronomy data into stellar classes

Advances in Data Analysis and Classification - The classification of the X-ray sources into classes (such as extragalactic sources, background stars,...) is an essential task in astronomy....     

A simple Markov chain structure for the evolution of credit ratings

We focus on continuous Markov chains as a model to describe the evolution of credit ratings. In this work it is checked whether a simple, tridiagonal type of generator provides a good approximation to a general one. Three different tridiagonal approximations are proposed and their performance is checked against two generators, corresponding to a volatile and a stable period, respectively. Copyright © 2007 John Wiley & Sons, Ltd.     

A Comparison of Optimal Methods for Local Access Uncapacitated Network Design

We compare some optimal methods addressed to a problem of local access network design. We see this problem arising in telecommunication as a flow extension of the Steiner problem in directed graphs, thus including as particular cases some alternative approaches based on the spanning tree problem. We work with two equivalent flow formulations for the problem, the first referring to a single commodity and the second being a multicommodity flow model. The objective in both cases is the cost minimization of the sum of the fixed (structural) and variable (operational) costs of all the arcs composing an arborescence that links the origin node (switching center) to every demand node. The weak single commodity flow formulation is solved by a branch-and-bound strategy that applies Lagrangian relaxation for computing the bounds. The strong multicommodity flow model is solved by a branch-and-cut algorithm and by Benders decomposition. The use of a linear programming solver to address both the single commodity and the multicommodity models has also been investigated. Our experience suggests that a certain number of these modeling and solution strategies can be applied to the frequently occurring problems where basic optimal solutions to the linear program are automatically integral, so it also solves the combinatorial optimization problem right away. On the other hand, our main conclusion is that a well tailored Benders partitioning approach emerges as a robust method to cope with that fabricated cases where the linear programming relaxation exhibits a gap between the continuous and the integral optimal values.     

On nonoscillating integrals for computing inhomogeneous Airy functions

Integral representations are considered of solutions of the inhomogeneous Airy differential equation . The solutions of these equations are also known as Scorer functions. Certain functional relations for these functions are used to confine the discussion to one function and to a certain sector in the complex plane. By using steepest descent methods from asymptotics, the standard integral representations of the Scorer functions are modified in order to obtain nonoscillating integrals for complex values of . In this way stable representations for numerical evaluations of the functions are obtained. The methods are illustrated with numerical results.

     

New inequalities from classical Sturm theorems

Inequalities satisfied by the zeros of the solutions of second-order hypergeometric equations are derived through a systematic use of Liouville transformations together with the application of classical Sturm theorems. This systematic study allows us to improve previously known inequalities and to extend their range of validity as well as to discover inequalities which appear to be new. Among other properties obtained, Szegő's bounds on the zeros of Jacobi polynomials for , are completed with results for the rest of parameter values, Grosjean's inequality (J. Approx. Theory 50 (1987) 84) on the zeros of Legendre polynomials is shown to be valid for Jacobi polynomials with |β|1, bounds on ratios of consecutive zeros of Gauss and confluent hypergeometric functions are derived as well as an inequality involving the geometric mean of zeros of Bessel functions.     

Computing Complex Airy Functions by Numerical Quadrature

Integral representations are considered of solutions of the Airy differential equation w –zw=0 for computing Airy functions for complex values of z. In a first method contour integral representations of the Airy functions are written as non-oscillating integrals for obtaining stable representations, which are evaluated by the trapezoidal rule. In a second method an integral representation is evaluated by using generalized Gauss–Laguerre quadrature; this approach provides a fast method for computing Airy functions to a predetermined accuracy. Comparisons are made with well-known algorithms of Amos, designed for computing Bessel functions of complex argument. Several discrepancies with Amos' code are detected, and it is pointed out for which regions of the complex plane Amos' code is less accurate than the quadrature algorithms. Hints are given in order to build reliable software for complex Airy functions.     

Heuristics for Distribution Network Design in Telecommunication

A distribution network problem arises in a lower level of an hierarchical modeling approach for telecommunication network planning. This paper describes a model and proposes a lagrangian heuristic for designing a distribution network. Our model is a complex extension of a capacitated single commodity network design problem. We are given a network containing a set of sources with maximum available supply, a set of sinks with required demands, and a set of transshipment points. We need to install adequate capacities on the arcs to route the required flow to each sink, that may be an intermediate or a terminal node of an arborescence. Capacity can only be installed in discrete levels, i.e., cables are available only in certain standard capacities. Economies of scale induce the use of a unique higher capacity cable instead of an equivalent set of lower capacity cables to cover the flow requirements of any link. A path from a source to a terminal node requires a lower flow in the measure that we are closer to the terminal node, since many nodes in the path may be intermediate sinks. On the other hand, the reduction of cable capacity levels across any path is inhibited by splicing costs. The objective is to minimize the total cost of the network, given by the sum of the arc capacity (cables) costs plus the splicing costs along the nodes. In addition to the limited supply and the node demand requirements, the model incorporates constraints on the number of cables installed on each edge and the maximum number of splices at each node. The model is a NP-hard combinatorial optimization problem because it is an extension of the Steiner problem in graphs. Moreover, the discrete levels of cable capacity and the need to consider splicing costs increase the complexity of the problem. We include some computational results of the lagrangian heuristics that works well in the practice of computer aided distribution network design.