A Constructive Genetic Algorithm for permutation flowshop scheduling

The general flowshop scheduling problem is a production problem where a set of n jobs have to be processed with identical flow pattern on in machines. In permutation flowshops the sequence of jobs is the same on all machines. A significant research effort has been devoted for sequencing jobs in a flowshop minimizing the makespan. This paper describes the application of a Constructive Genetic Algorithm (CGA) to makespan minimization on flowshop scheduling. The CGA was proposed recently as an alternative to traditional GA approaches, particularly, for evaluating schemata directly. The population initially formed only by schemata, evolves controlled by recombination to a population of well-adapted structures (schemata instantiation). The CGA implemented is based on the NEH classic heuristic and a local search heuristic used to define the fitness functions. The parameters of the CGA are calibrated using a Design of Experiments (DOE) approach. The computational results are compared against some other successful algorithms from the literature on Taillard`s well-known standard benchmark. The computational experience shows that this innovative CGA approach provides competitive results for flowshop scheduling; problems. (C) 2007 Elsevier Ltd. All rights reserved.

Reducing mean flow time in permutation flow shop

This paper deals with the traditional permutation flow shop scheduling problem with the objective of minimizing mean flowtime, therefore reducing in-process inventory. A new heuristic method is proposed for the scheduling problem solution. The proposed heuristic is compared with the best one considered in the literature. Experimental results show that the new heuristic provides better solutions regarding both the solution quality and computational effort.

Testing permutation properties through subpermutations

There has been great interest in deciding whether a combinatorial structure satisfies some property, or in estimating the value of some numerical function associated with this combinatorial structure, by considering only a randomly chosen substructure of sufficiently large, but constant size. These problems are called property testing and parameter testing, where a property or parameter is said to be testable if it can be estimated accurately in this way. The algorithmic appeal is evident, as, conditional on sampling, this leads to reliable constant-time randomized estimators. Our paper addresses property testing and parameter testing for permutations in a subpermutation perspective; more precisely, we investigate permutation properties and parameters that can be well approximated based on a randomly chosen subpermutation of much smaller size. In this context, we use a theory of convergence of permutation sequences developed by the present authors [C. Hoppen, Y. Kohayakawa, C.G. Moreira, R.M. Sampaio, Limits of permutation sequences through permutation regularity, Manuscript, 2010, 34pp.] to characterize testable permutation parameters along the lines of the work of Borgs et al. [C. Borgs, J. Chayes, L Lovasz, V.T. Sos, B. Szegedy, K. Vesztergombi, Graph limits and parameter testing, in: STOC`06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, ACM, New York, 2006, pp. 261-270.] in the case of graphs. Moreover, we obtain a permutation result in the direction of a famous result of Alon and Shapira [N. Alon, A. Shapira, A characterization of the (natural) graph properties testable with one-sided error, SIAM J. Comput. 37 (6) (2008) 1703-1727.] stating that every hereditary graph property is testable. (C) 2011 Elsevier B.V. All rights reserved.

Multiple classical limits in relativistic and nonrelativistic quantum mechanics

The existence of a classical limit describing the interacting particles in a second-quantized theory of identical particles with bosonic symmetry is proved. This limit exists in addition to the previously established classical limit with a classical field behavior, showing that the limit h -> 0 of the theory is not unique. An analogous result is valid for a free massive scalar field: two distinct classical limits are proved to exist, describing a system of particles or a classical field. The introduction of local operators in order to represent kinematical properties of interest is shown to break the permutation symmetry under some localizability conditions, allowing the study of individual particle properties.

On the resilience of long cycles in random graphs

In this paper we determine the local and global resilience of random graphs G(n,p) (p >> n(-1)) with respect to the property of containing a cycle of length at least (1 - alpha)n. Roughly speaking, given alpha > 0, we determine the smallest r(g) (G, alpha) with the property that almost surely every subgraph of G = G(n,p) having more than r(g) (G, alpha)vertical bar E(G)vertical bar edges contains a cycle of length at least (1 - alpha)n (global resilience). We also obtain, for alpha < 1/2, the smallest r(l) (G, alpha) such that any H subset of G having deg(H) (v) larger than r(l) (G, alpha) deg(G) (v) for all v is an element of V(G) contains a cycle of length at least (1 - alpha)n (local resilience). The results above are in fact proved in the more general setting of pseudorandom graphs.

Transcriptional responses of host peripheral blood cells to tuberculosis infection

Host responses following exposure to Mycobacterium tuberculosis (TB) are complex and can significantly affect clinical outcome. These responses, which are largely mediated by complex immune mechanisms involving peripheral blood cells (PBCs) such as T-lymphocytes, NK cells and monocyte-derived macrophages, have not been fully characterized. We hypothesize that different clinical outcome following TB exposure will be uniquely reflected in host gene expression profiles, and expression profiling of PBCs can be used to discriminate between different TB infectious outcomes. In this study, microarray analysis was performed on PBCs from three TB groups (BCG-vaccinated, latent TB infection, and active TB infection) and a control healthy group. Supervised learning algorithms were used to identify signature genomic responses that differentiate among group samples. Gene Set Enrichment Analysis was used to determine sets of genes that were co-regulated. Multivariate permutation analysis (p < 0.01) gave 645 genes differentially expressed among the four groups, with both distinct and common patterns of gene expression observed for each group. A 127-probeset, representing 77 known genes, capable of accurately classifying samples into their respective groups was identified. In addition, 13 insulin-sensitive genes were found to be differentially regulated in all three TB infected groups, underscoring the functional association between insulin signaling pathway and TB infection. Published by Elsevier Ltd.

Chronic obstructive pulmonary disease in Brazil: mortality and hospitalization trends and rates, 1996-2008

SETTING: Chronic obstructive pulmonary disease (COPD) is the third leading cause of death among adults in Brazil. OBJECTIVE: To evaluate the mortality and hospitalisation trends in Brazil caused by COPD during the period 1996-2008. DESIGN: We used the health official statistics system to obtain data about mortality (1996-2008) and morbidity (1998-2008) due to COPD and all respiratory diseases (tuberculosis: codes A15-16; lung cancer: code C34, and all diseases coded from J40 to 47 in the 10th Revision of the International Classification of Diseases) as the underlying cause, in persons aged 45-74 years. We used the Joinpoint Regression Program log-linear model using Poisson regression that creates a Monte Carlo permutation test to identify points where trend lines change significantly in magnitude/direction to verify peaks and trends. RESULTS: The annual per cent change in age-adjusted death rates due to COPD declined by 2.7% in men (95%CI -3.6 to -1.8) and -2.0% (95%CI -2.9 to -1.0) in women; and due to all respiratory causes it declined by -1.7% (95%CI 2.4 to -1.0) in men and -1.1% (95%CI -1.8 to -0.3) in women. Although hospitalisation rates for COPD are declining, the hospital admission fatality rate increased in both sexes. CONCLUSION: COPD is still a leading cause of mortality in Brazil despite the observed decline in the mortality/hospitalisation rates for both sexes.

Three-dimensional mapping of hippocampal anatomy in unmedicated and lithium-treated patients with bipolar disorder

Declarative memory impairments are common in patients with bipolar illness, suggesting underlying hippocampal pathology. However, hippocampal volume deficits are rarely observed in bipolar disorder. Here we used surface-based anatomic mapping to examine hippocampal anatomy in bipolar patients treated with lithium relative to matched control subjects and unmedicated patients with bipolar disorder. High-resolution brain magnetic resonance images were acquired from 33 patients with bipolar disorder ( 21 treated with lithium and 12 unmedicated), and 62 demographically matched healthy control subjects. Three-dimensional parametric mesh models were created from manual tracings of the hippocampal formation. Total hippocampal volume was significantly larger in lithium-treated bipolar patients compared with healthy controls (by 10.3%; p=0.001) and unmedicated bipolar patients ( by 13.9%; p=0.003). Statistical mapping results, confirmed by permutation testing, revealed localized deficits in the right hippocampus, in regions corresponding primarily to cornu ammonis vertical bar subfields, in unmedicated bipolar patients, as compared to both normal controls (p=0.01), and in lithium-treated bipolar patients (p=0.03). These findings demonstrate the sensitivity of these anatomic mapping methods for detecting subtle alterations in hippocampal structure in bipolar disorder. The observed reduction in subregions of the hippocampus in unmedicated bipolar patients suggests a possible neural correlate for memory deficits frequently reported in this illness. Moreover, increased hippocampal volume in lithium-treated bipolar patients may reflect postulated neurotrophic effects of this agent, a possibility warranting further study in longitudinal investigations.

Aging and stationary properties of non-equilibrium symmetrical three-state models

We consider a non-equilibrium three-state model whose dynamics is Markovian and displays the same symmetry as the three-state Potts model, i.e. the transition rates are invariant under the cyclic permutation of the states. Unlike the Potts model, detailed balance is, in general, not satisfied. The aging and the stationary properties of the model defined on a square lattice are obtained by means of large-scale Monte Carlo simulations. We show that the phase diagram presents a critical line, belonging to the three-state Potts universality class, that ends at a point whose universality class is that of the Voter model. Aging is considered on the critical line, at the Voter point and in the ferromagnetic phase.

Sparse partition universal graphs for graphs of bounded degree

In 1983, Chvatal, Trotter and the two senior authors proved that for any Delta there exists a constant B such that, for any n, any 2-colouring of the edges of the complete graph K(N) with N >= Bn vertices yields a monochromatic copy of any graph H that has n vertices and maximum degree Delta. We prove that the complete graph may be replaced by a sparser graph G that has N vertices and O(N(2-1/Delta)log(1/Delta)N) edges, with N = [B`n] for some constant B` that depends only on Delta. Consequently, the so-called size-Ramsey number of any H with n vertices and maximum degree Delta is O(n(2-1/Delta)log(1/Delta)n) Our approach is based on random graphs; in fact, we show that the classical Erdos-Renyi random graph with the numerical parameters above satisfies a stronger partition property with high probability, namely, that any 2-colouring of its edges contains a monochromatic universal graph for the class of graphs on n vertices and maximum degree Delta. The main tool in our proof is the regularity method, adapted to a suitable sparse setting. The novel ingredient developed here is an embedding strategy that allows one to embed bounded degree graphs of linear order in certain pseudorandom graphs. Crucial to our proof is the fact that regularity is typically inherited at a scale that is much finer than the scale at which it is assumed. (C) 2011 Elsevier Inc. All rights reserved.

Performance of balanced two-stage empirical predictors of realized cluster latent values from finite populations: A simulation study

Predictors of random effects are usually based on the popular mixed effects (ME) model developed under the assumption that the sample is obtained from a conceptual infinite population; such predictors are employed even when the actual population is finite. Two alternatives that incorporate the finite nature of the population are obtained from the superpopulation model proposed by Scott and Smith (1969. Estimation in multi-stage surveys. J. Amer. Statist. Assoc. 64, 830-840) or from the finite population mixed model recently proposed by Stanek and Singer (2004. Predicting random effects from finite population clustered samples with response error. J. Amer. Statist. Assoc. 99, 1119-1130). Predictors derived under the latter model with the additional assumptions that all variance components are known and that within-cluster variances are equal have smaller mean squared error (MSE) than the competitors based on either the ME or Scott and Smith`s models. As population variances are rarely known, we propose method of moment estimators to obtain empirical predictors and conduct a simulation study to evaluate their performance. The results suggest that the finite population mixed model empirical predictor is more stable than its competitors since, in terms of MSE, it is either the best or the second best and when second best, its performance lies within acceptable limits. When both cluster and unit intra-class correlation coefficients are very high (e.g., 0.95 or more), the performance of the empirical predictors derived under the three models is similar. (c) 2007 Elsevier B.V. All rights reserved.

Predicting random effects with an expanded finite population mixed model

Prediction of random effects is an important problem with expanding applications. In the simplest context, the problem corresponds to prediction of the latent value (the mean) of a realized cluster selected via two-stage sampling. Recently, Stanek and Singer [Predicting random effects from finite population clustered samples with response error. J. Amer. Statist. Assoc. 99, 119-130] developed best linear unbiased predictors (BLUP) under a finite population mixed model that outperform BLUPs from mixed models and superpopulation models. Their setup, however, does not allow for unequally sized clusters. To overcome this drawback, we consider an expanded finite population mixed model based on a larger set of random variables that span a higher dimensional space than those typically applied to such problems. We show that BLUPs for linear combinations of the realized cluster means derived under such a model have considerably smaller mean squared error (MSE) than those obtained from mixed models, superpopulation models, and finite population mixed models. We motivate our general approach by an example developed for two-stage cluster sampling and show that it faithfully captures the stochastic aspects of sampling in the problem. We also consider simulation studies to illustrate the increased accuracy of the BLUP obtained under the expanded finite population mixed model. (C) 2007 Elsevier B.V. All rights reserved.

Decomposability problem on branched coverings

Given a branched covering of degree d between closed surfaces, it determines a collection of partitions of d, the branch data. In this work we show that any branch data are realized by an indecomposable primitive branched covering on a connected closed surface N with chi(N) <= 0. This shows that decomposable and indecomposable realizations may coexist. Moreover, we characterize the branch data of a decomposable primitive branched covering. Bibliography: 20 titles.