ILS-ESP An efficient, simple, and parameter-free algorithm for solving the permutation flow-shop problem

From a managerial point of view, the more effcient, simple, and parameter-free (ESP) an algorithm is, the more likely it will be used in practice for solving real-life problems. Following this principle, an ESP algorithm for solving the Permutation Flowshop Sequencing Problem (PFSP) is proposed in this article. Using an Iterated Local Search (ILS) framework, the so-called ILS-ESP algorithm is able to compete in performance with other well-known ILS-based approaches, which are considered among the most effcient algorithms for the PFSP. However, while other similar approaches still employ several parameters that can affect their performance if not properly chosen, our algorithm does not require any particular fine-tuning process since it uses basic "common sense" rules for the local search, perturbation, and acceptance criterion stages of the ILS metaheuristic. Our approach defines a new operator for the ILS perturbation process, a new acceptance criterion based on extremely simple and transparent rules, and a biased randomization process of the initial solution to randomly generate different alternative initial solutions of similar quality -which is attained by applying a biased randomization to a classical PFSP heuristic. This diversification of the initial solution aims at avoiding poorly designed starting points and, thus, allows the methodology to take advantage of current trends in parallel and distributed computing. A set of extensive tests, based on literature benchmarks, has been carried out in order to validate our algorithm and compare it against other approaches. These tests show that our parameter-free algorithm is able to compete with state-of-the-art metaheuristics for the PFSP. Also, the experiments show that, when using parallel computing, it is possible to improve the top ILS-based metaheuristic by just incorporating to it our biased randomization process with a high-quality pseudo-random number generator.

A simple permutation test for clusteredness

Hierarchical clustering is a popular method for finding structure in multivariate data,resulting in a binary tree constructed on the particular objects of the study, usually samplingunits. The user faces the decision where to cut the binary tree in order to determine the numberof clusters to interpret and there are various ad hoc rules for arriving at a decision. A simplepermutation test is presented that diagnoses whether non-random levels of clustering are presentin the set of objects and, if so, indicates the specific level at which the tree can be cut. The test isvalidated against random matrices to verify the type I error probability and a power study isperformed on data sets with known clusteredness to study the type II error.

Genetic algorithm for sequencing in midex model non-permutation flowshops using constrained buffers

Este trabajo presenta un Algoritmo Genético (GA) del problema de secuenciar unidades en una línea de producción. Se tiene en cuenta la posibilidad de cambiar la secuencia de piezas mediante estaciones con acceso a un almacén intermedio o centralizado. El acceso al almacén además está restringido, debido al tamaño de las piezas.AbstractThis paper presents a Genetic Algorithm (GA) for the problem of sequencing in a mixed model non-permutation flowshop. Resequencingis permitted where stations have access to intermittent or centralized resequencing buffers. The access to a buffer is restricted by the number of available buffer places and the physical size of the products.

Internship report: improving asymmetric term extraction from bilingual text

Estudi elaborat a partir d’una estada a Xerox Research Centre Europe a Grenoble, França,entre juny i desembre del 2006. El projecte tradueïx termes tècnics anglesos a noruec. És asimètric perquè no tenim recursos lingüístics per a la llengua noruega, però solament per a l'anglès. S’ha desenvolupat i posat en pràctica mètodes que comprovaven contigüitat ("local reordering" i permutació selectiva) per a millorar el funcionament d’una eina anterior. Contigüitat és quan una paraula es traduïx en paraules múltiples, aquestes paraules han de ser adjacents en l'oració. A més, s’ha construït una taula de les operacions de recerca per als termes tècnics i s’ha integrat aquesta taula en un programa de demostració.

Generating trees for permutations avoiding generalized patterns

We construct generating trees with with one, two, and three labels for some classes of permutations avoiding generalized patterns of length 3 and 4. These trees are built by adding at each level an entry to the right end of the permutation, which allows us to incorporate the adjacency condition about some entries in an occurrence of a generalized pattern. We use these trees to find functional equations for the generating functions enumerating these classes of permutations with respect to different parameters. In several cases we solve them using the kernel method and some ideas of Bousquet-Mélou [2]. We obtain refinements of known enumerative results and find new ones.

XIFRADOR 1.0

Aquest TFC pretén investigar en el concepte de generadors de seqüencies pseudoaleatories amb la finalitat d'implementar un generador amb qualitats òptimes per al xifratge de dades.

A variant in the gene FUT9 is associated with susceptibility to placental malaria infection

Malaria in pregnancy forms a substantial part of the worldwide burden of malaria, with an estimated annual death toll of up to 200,000 infants, as well as increased maternal morbidity and mortality. Studies of genetic susceptibility to malaria have so far focused on infant malaria, with only a few studies investigating the genetic basis of placental malaria, focusing only on a limited number of candidate genes. The aim of this study therefore was to identify novel host genetic factors involved in placental malaria infection. To this end we carried out a nested case-control study on 180 Mozambican pregnant women with placental malaria infection, and 180 controls within an intervention trial of malaria prevention. We genotyped 880 SNPs in a set of 64 functionally related genes involved in glycosylation and innate immunity. A SNP located in the gene FUT9, rs3811070, was significantly associated with placental malaria infection (OR = 2.31, permutation p-value = 0.028). Haplotypic analysis revealed a similarly strong association of a common haplotype of four SNPs including rs3811070. FUT9 codes for a fucosyl-transferase that is catalyzing the last step in the biosynthesis of the Lewis-x antigen, which forms part of the Lewis blood group-related antigens. These results therefore suggest an involvement of this antigen in the pathogenesis of placental malaria infection.

Contrasting the form and use of reformulation markers

This paper deals with the form and use of reformulation markers in research papers written in English, Spanish and Catalan. Considering the form and frequency of themarkers, English papers tends to prefer simple fixed markers and includes less reformulators than Spanish and Catalan. On the contrary, formal Catalan and Spanish papers include more markers, some of which are complex and allow for some structural variability. As for use, reformulation markers establish dynamic relationships between portions of discourse which can be identified in our corpus with expansion, reduction, and permutation. The analysis of the corpus shows that English authors usually reformulate to add more information to the concept (expansion), whereas Catalan and Spanish authors reduce the contents or the implicatures of the previous formulation more frequently than English.

Generalized low-density codes with BCH constituents for full-diversity near-outage performance

A new graph-based construction of generalized low density codes (GLD-Tanner) with binary BCH constituents is described. The proposed family of GLD codes is optimal on block erasure channels and quasi-optimal on block fading channels. Optimality is considered in the outage probability sense. Aclassical GLD code for ergodic channels (e.g., the AWGN channel,the i.i.d. Rayleigh fading channel, and the i.i.d. binary erasure channel) is built by connecting bitnodes and subcode nodes via a unique random edge permutation. In the proposed construction of full-diversity GLD codes (referred to as root GLD), bitnodes are divided into 4 classes, subcodes are divided into 2 classes, and finally both sides of the Tanner graph are linked via 4 random edge permutations. The study focuses on non-ergodic channels with two states and can be easily extended to channels with 3 states or more.

Exact and approximate stepdown methods for multiple hypothesis testing

Consider the problem of testing k hypotheses simultaneously. In this paper,we discuss finite and large sample theory of stepdown methods that providecontrol of the familywise error rate (FWE). In order to improve upon theBonferroni method or Holm's (1979) stepdown method, Westfall and Young(1993) make eective use of resampling to construct stepdown methods thatimplicitly estimate the dependence structure of the test statistics. However,their methods depend on an assumption called subset pivotality. The goalof this paper is to construct general stepdown methods that do not requiresuch an assumption. In order to accomplish this, we take a close look atwhat makes stepdown procedures work, and a key component is a monotonicityrequirement of critical values. By imposing such monotonicity on estimatedcritical values (which is not an assumption on the model but an assumptionon the method), it is demonstrated that the problem of constructing a validmultiple test procedure which controls the FWE can be reduced to the problemof contructing a single test which controls the usual probability of a Type 1error. This reduction allows us to draw upon an enormous resamplingliterature as a general means of test contruction.

An Efficient Nominal Unification Algorithm

Nominal Unification is an extension of first-order unification where terms can contain binders and unification is performed modulo α equivalence. Here we prove that the existence of nominal unifiers can be decided in quadratic time. First, we linearly-reduce nominal unification problems to a sequence of freshness and equalities between atoms, modulo a permutation, using ideas as Paterson and Wegman for first-order unification. Second, we prove that solvability of these reduced problems may be checked in quadràtic time. Finally, we point out how using ideas of Brown and Tarjan for unbalanced merging, we could solve these reduced problems more efficiently

Generator of ultrashort optical pulses for time division multiplexing

The performance of a device based on modified injection-locking techniques is studied by means of numerical simulations. The device incorporates master and slave configurations, each one with a DFB laser and an electroabsortion modulator (EAM). This arrangement allows the generation of high peak power, narrow optical pulses according to a periodic or pseudorandom bit stream provided by a current signal generator. The device is able to considerably increase the modulation bandwidth of free-running gain-switched semiconductor lasers using multiplexing in the time domain. Opportunities for integration in small packages or single chips are discussed.

A comparison of rapid bioassessment protocols used in 2 regions with Mediterranean climates, the Iberian Peninsula and South Africa

Abstract. The ability of 2 Rapid Bioassessment Protocols (RBPs) to assess stream water quality was compared in 2 Mediterranean-climate regions. The most commonly used RBPs in South Africa (SAprotocol) and the Iberian Peninsula (IB-protocol) are both multihabitat, field-based methods that use macroinvertebrates. Both methods use preassigned sensitivity weightings to calculate metrics and biotic indices. The SA- and IB-protocols differ with respect to sampling equipment (mesh size: 1000 lm vs 250 300 lm, respectively), segregation of habitats (substrate vs flow-type), and sampling and sorting procedures (variable time and intensity). Sampling was undertaken at 6 sites in South Africa and 5 sites in the Iberian Peninsula. Forty-four and 51 macroinvertebrate families were recorded in South Africa and the Iberian Peninsula, respectively; 77.3% of South African families and 74.5% of Iberian Peninsula families were found using both protocols. Estimates of community similarity compared between the 2 protocols were .60% similar among sites in South Africa and .54% similar among sites in the Iberian Peninsula (BrayCurtis similarity), and no significant differences were found between protocols (Multiresponse Permutation Procedure). Ordination based on Non-metric Multidimensional Scaling grouped macroinvertebrate samples on the basis of site rather than protocol. Biotic indices generated with the 2 protocols at each site did not differ. Thus, both RBPs produced equivalent results, and both were able to distinguish between biotic communities (mountain streams vs foothills) and detect water-quality impairment, regardless of differences in sampling equipment, segregation of habitats, and sampling and sorting procedures. Our results indicate that sampling a single habitat may be sufficient for assessing water quality, but a multihabitat approach to sampling is recommended where intrinsic variability of macroinvertebrate assemblages is high (e.g., in undisturbed sites in regions with Mediterranean climates). The RBP of choice should depend on whether the objective is routine biomonitoring of water quality or autecological or faunistic studies.

ML estimator and hybrid beamformer for multipath and interference mitigation in GNSS receivers

This paper addresses the estimation of the code-phase(pseudorange) and the carrier-phase of the direct signal received from a direct-sequence spread-spectrum satellite transmitter. Thesignal is received by an antenna array in a scenario with interferenceand multipath propagation. These two effects are generallythe limiting error sources in most high-precision positioning applications.A new estimator of the code- and carrier-phases is derivedby using a simplified signal model and the maximum likelihood(ML) principle. The simplified model consists essentially ofgathering all signals, except for the direct one, in a component withunknown spatial correlation. The estimator exploits the knowledgeof the direction-of-arrival of the direct signal and is much simplerthan other estimators derived under more detailed signal models.Moreover, we present an iterative algorithm, that is adequate for apractical implementation and explores an interesting link betweenthe ML estimator and a hybrid beamformer. The mean squarederror and bias of the new estimator are computed for a numberof scenarios and compared with those of other methods. The presentedestimator and the hybrid beamforming outperform the existingtechniques of comparable complexity and attains, in manysituations, the Cramér–Rao lower bound of the problem at hand.

Sherali-Adams Relaxations and Indistinguishability in Counting Logics

Two graphs with adjacency matrices $\mathbf{A}$ and $\mathbf{B}$ are isomorphic if there exists a permutation matrix $\mathbf{P}$ for which the identity $\mathbf{P}^{\mathrm{T}} \mathbf{A} \mathbf{P} = \mathbf{B}$ holds. Multiplying through by $\mathbf{P}$ and relaxing the permutation matrix to a doubly stochastic matrix leads to the linear programming relaxation known as fractional isomorphism. We show that the levels of the Sherali--Adams (SA) hierarchy of linear programming relaxations applied to fractional isomorphism interleave in power with the levels of a well-known color-refinement heuristic for graph isomorphism called the Weisfeiler--Lehman algorithm, or, equivalently, with the levels of indistinguishability in a logic with counting quantifiers and a bounded number of variables. This tight connection has quite striking consequences. For example, it follows immediately from a deep result of Grohe in the context of logics with counting quantifiers that a fixed number of levels of SA suffice to determine isomorphism of planar and minor-free graphs. We also offer applications in both finite model theory and polyhedral combinatorics. First, we show that certain properties of graphs, such as that of having a flow circulation of a prescribed value, are definable in the infinitary logic with counting with a bounded number of variables. Second, we exploit a lower bound construction due to Cai, Fürer, and Immerman in the context of counting logics to give simple explicit instances that show that the SA relaxations of the vertex-cover and cut polytopes do not reach their integer hulls for up to $\Omega(n)$ levels, where $n$ is the number of vertices in the graph.