A comparative study of algorithms for the flowshop scheduling problem

In this paper, we propose three meta-heuristic algorithms for the permutation flowshop (PFS) and the general flowshop (GFS) problems. Two different neighborhood structures are used for these two types of flowshop problem. For the PFS problem, an insertion neighborhood structure is used, while for the GFS problem, a critical-path neighborhood structure is adopted. To evaluate the performance of the proposed algorithms, two sets of problem instances are tested against the algorithms for both types of flowshop problems. The computational results show that the proposed meta-heuristic algorithms with insertion neighborhood for the PFS problem perform slightly better than the corresponding algorithms with critical-path neighborhood for the GFS problem. But in terms of computation time, the GFS algorithms are faster than the corresponding PFS algorithms.

Essays on Spatial Econometrics

Esta dissertação concentra-se nos processos estocásticos espaciais definidos em um reticulado, os chamados modelos do tipo Cliff & Ord. Minha contribuição nesta tese consiste em utilizar aproximações de Edgeworth e saddlepoint para investigar as propriedades em amostras finitas do teste para detectar a presença de dependência espacial em modelos SAR (autoregressivo espacial), e propor uma nova classe de modelos econométricos espaciais na qual os parâmetros que afetam a estrutura da média são distintos dos parâmetros presentes na estrutura da variância do processo. Isto permite uma interpretação mais clara dos parâmetros do modelo, além de generalizar uma proposta de taxonomia feita por Anselin (2003). Eu proponho um estimador para os parâmetros do modelo e derivo a distribuição assintótica do estimador. O modelo sugerido na dissertação fornece uma interpretação interessante ao modelo SARAR, bastante comum na literatura. A investigação das propriedades em amostras finitas dos testes expande com relação a literatura permitindo que a matriz de vizinhança do processo espacial seja uma função não-linear do parâmetro de dependência espacial. A utilização de aproximações ao invés de simulações (mais comum na literatura), permite uma maneira fácil de comparar as propriedades dos testes com diferentes matrizes de vizinhança e corrigir o tamanho ao comparar a potência dos testes. Eu obtenho teste invariante ótimo que é também localmente uniformemente mais potente (LUMPI). Construo o envelope de potência para o teste LUMPI e mostro que ele é virtualmente UMP, pois a potência do teste está muito próxima ao envelope (considerando as estruturas espaciais definidas na dissertação). Eu sugiro um procedimento prático para construir um teste que tem boa potência em uma gama de situações onde talvez o teste LUMPI não tenha boas propriedades. Eu concluo que a potência do teste aumenta com o tamanho da amostra e com o parâmetro de dependência espacial (o que está de acordo com a literatura). Entretanto, disputo a visão consensual que a potência do teste diminui a medida que a matriz de vizinhança fica mais densa. Isto reflete um erro de medida comum na literatura, pois a distância estatística entre a hipótese nula e a alternativa varia muito com a estrutura da matriz. Fazendo a correção, concluo que a potência do teste aumenta com a distância da alternativa à nula, como esperado.

Planning and Projects of Secondary Electric Power Distribution Systems

This paper proposes a methodology to achieve integrated planning and projects for secondary distribution circuits. The planning model is formulated as a mixed integer nonlinear programming problem (MINLP). In order to resolve this problem, a tabu search (TS) algorithm is used, with a neighborhood structure developed to explore the physical characteristics of specific geographies included in the planning and expansion of secondary networks, thus obtaining effective solutions as well as low operating costs and investments. The project stage of secondary circuits consists of calculating the mechanical efforts to determine the support structures of the primary and secondary distribution systems and determining the types of structures that should be used in the system according to topological and electrical parameters of the network and, therefore, accurately assessing the costs involved in the construction and/or reform of secondary systems. A constructive heuristic based on information of the electrical and topological conditions between the medium voltage and low voltage systems is used to connect the primary systems and secondary circuits. The results obtained from planning and design simulations of a real secondary system of electric energy distribution are presented.

Hyperspace geography: Visualizing fitness landscapes beyond 4D

Human perception is finely tuned to extract structure about the 4D world of time and space as well as properties such as color and texture. Developing intuitions about spatial structure beyond 4D requires exploiting other perceptual and cognitive abilities. One of the most natural ways to explore complex spaces is for a user to actively navigate through them, using local explorations and global summaries to develop intuitions about structure, and then testing the developing ideas by further exploration. This article provides a brief overview of a technique for visualizing surfaces defined over moderate-dimensional binary spaces, by recursively unfolding them onto a 2D hypergraph. We briefly summarize the uses of a freely available Web-based visualization tool, Hyperspace Graph Paper (HSGP), for exploring fitness landscapes and search algorithms in evolutionary computation. HSGP provides a way for a user to actively explore a landscape, from simple tasks such as mapping the neighborhood structure of different points, to seeing global properties such as the size and distribution of basins of attraction or how different search algorithms interact with landscape structure. It has been most useful for exploring recursive and repetitive landscapes, and its strength is that it allows intuitions to be developed through active navigation by the user, and exploits the visual system's ability to detect pattern and texture. The technique is most effective when applied to continuous functions over Boolean variables using 4 to 16 dimensions.

Integrability and singularity structure of predator‐prey system

The ‘‘extended’’ ARS (Ablowitz, Ramani, and Segur) algorithm is introduced to characterize a dynamical system as Painlevé or otherwise; to that end, it is required that the formal series—the Laurent series, logarithmic, algebraic psi series about a movable singularity—are shown to converge in the deleted neighborhood of the singularity. The determinations thus obtained are compared with those following from the α method of Painlevé. An attempt is made to relate the structure of solutions about a movable singularity with that of first integrals (when they exist). All these ideas are illustrated by a comprehensive analysis of the general two‐dimensional predator‐prey system.

Singularity structure of third-order dynamical systems .2

The singularity structure of the solutions of a general third-order system, with polynomial right-hand sides of degree less than or equal to two, is studied about a movable singular point, An algorithm for transforming the given third-order system to a third-order Briot-Bouquet system is presented, The dominant behavior of a solution of the given system near a movable singularity is used to construct a transformation that changes the given system directly to a third-order Briot-Bouquet system. The results of Horn for the third-order Briot-Bouquet system are exploited to give the complete form of the series solutions of the given third-order system; convergence of these series in a deleted neighborhood of the singularity is ensured, This algorithm is used to study the singularity structure of the solutions of the Lorenz system, the Rikitake system, the three-wave interaction problem, the Rabinovich system, the Lotka-Volterra system, and the May-Leonard system for different sets of parameter values. The proposed approach goes far beyond the ARS algorithm.

NON-GLYCINE RESIDUES IN THE DISALLOWED REGIONS OF THE RAMACHANDRAN MAP AND THEIR NEIGHBORHOOD PREFERENCES

The allowed and the ``disallowed'' regions in the celebrated Ramachandran map (phi-psi] map) was elegantly deduced by Ramachandran, Ramakrishnan and Sasisekharan even before the protein crystal structures became available. This powerful map was derived based on rigid geometry of the peptide group and later several investigations on protein crystal structures reported the occurrence of a small fraction of the phi-psi] torsion angles in the disallowed region. The question is what factors make these residues adopt disallowed conformations? Is it driven by the necessity to maintain the overall topology or is it associated with function or is it just that the disallowed conformations are extreme limits of the allowed conformations? Today, with the availability of a large number of high resolution crystal structures, we have revisited this problem. Apart from validating some of the earlier findings such as residue propensities, preferred location in the secondary structure, we have explored their spatial neighborhood preferences using the protein structure network PSN] approach developed in our lab. Finally, the structural and functional implications of the disallowed conformations are examined.

Probabilistic distribution of one-phase structure seminvariants for an isomorphous pair of structures: Theoretical basis and initial applications

Given a special type of triplet of reciprocal-lattice vectors in the monoclinic and orthorhombic systems, there exist eight three-phase structure seminvariants (3PSSs) for a pair of isomorphous structures. The first neighborhood of each of these 3PSSs is defined by the six magnitudes and the joint probability distribution of the corresponding six structure factors is derived according to Hauptman's neighborhood principle. This distribution leads to the conditional probability distribution of each of the 3PSSs, assuming as known the six magnitudes in its first neighborhood. The conditional probability distributions can be directly used to yield the reliable estimates (0 or pi) of the one-phase structure seminvariants (1PSSs) in the favorable case that the variances of the distributions happen to be small [Hauptman (1975). Acta Cryst. A31, 680-687]. The relevant parameters in the formulas for the monoclinic and orthorhombic systems are given in a tabular form. The applications suggest that the method is efficient for estimating the 1PSSs with values of 0 or pi.

La structure de Jordan des matrices de transfert des modèles de boucles et la relation avec les hamiltoniens XXZ

Les modèles sur réseau comme ceux de la percolation, d’Ising et de Potts servent à décrire les transitions de phase en deux dimensions. La recherche de leur solution analytique passe par le calcul de la fonction de partition et la diagonalisation de matrices de transfert. Au point critique, ces modèles statistiques bidimensionnels sont invariants sous les transformations conformes et la construction de théories des champs conformes rationnelles, limites continues des modèles statistiques, permet un calcul de la fonction de partition au point critique. Plusieurs chercheurs pensent cependant que le paradigme des théories des champs conformes rationnelles peut être élargi pour inclure les modèles statistiques avec des matrices de transfert non diagonalisables. Ces modèles seraient alors décrits, dans la limite d’échelle, par des théories des champs logarithmiques et les représentations de l’algèbre de Virasoro intervenant dans la description des observables physiques seraient indécomposables. La matrice de transfert de boucles D_N(λ, u), un élément de l’algèbre de Temperley- Lieb, se manifeste dans les théories physiques à l’aide des représentations de connectivités ρ (link modules). L’espace vectoriel sur lequel agit cette représentation se décompose en secteurs étiquetés par un paramètre physique, le nombre d de défauts. L’action de cette représentation ne peut que diminuer ce nombre ou le laisser constant. La thèse est consacrée à l’identification de la structure de Jordan de D_N(λ, u) dans ces représentations. Le paramètre β = 2 cos λ = −(q + 1/q) fixe la théorie : β = 1 pour la percolation et √2 pour le modèle d’Ising, par exemple. Sur la géométrie du ruban, nous montrons que D_N(λ, u) possède les mêmes blocs de Jordan que F_N, son plus haut coefficient de Fourier. Nous étudions la non diagonalisabilité de F_N à l’aide des divergences de certaines composantes de ses vecteurs propres, qui apparaissent aux valeurs critiques de λ. Nous prouvons dans ρ(D_N(λ, u)) l’existence de cellules de Jordan intersectorielles, de rang 2 et couplant des secteurs d, d′ lorsque certaines contraintes sur λ, d, d′ et N sont satisfaites. Pour le modèle de polymères denses critique (β = 0) sur le ruban, les valeurs propres de ρ(D_N(λ, u)) étaient connues, mais les dégénérescences conjecturées. En construisant un isomorphisme entre les modules de connectivités et un sous-espace des modules de spins du modèle XXZ en q = i, nous prouvons cette conjecture. Nous montrons aussi que la restriction de l’hamiltonien de boucles à un secteur donné est diagonalisable et trouvons la forme de Jordan exacte de l’hamiltonien XX, non triviale pour N pair seulement. Enfin nous étudions la structure de Jordan de la matrice de transfert T_N(λ, ν) pour des conditions aux frontières périodiques. La matrice T_N(λ, ν) a des blocs de Jordan intrasectoriels et intersectoriels lorsque λ = πa/b, et a, b ∈ Z×. L’approche par F_N admet une généralisation qui permet de diagnostiquer des cellules intersectorielles dont le rang excède 2 dans certains cas et peut croître indéfiniment avec N. Pour les blocs de Jordan intrasectoriels, nous montrons que les représentations de connectivités sur le cylindre et celles du modèle XXZ sont isomorphes sauf pour certaines valeurs précises de q et du paramètre de torsion v. En utilisant le comportement de la transformation i_N^d dans un voisinage des valeurs critiques (q_c, v_c), nous construisons explicitement des vecteurs généralisés de Jordan de rang 2 et discutons l’existence de blocs de Jordan intrasectoriels de plus haut rang.

An examination of the relationship between maternal and neighborhood-level characteristics and intrauterine growth retardation in Harris County, Texas, 1999--2001

The persistence of low birth weight and intrauterine growth retardation (IUGR) in the United States has puzzled researchers for decades. Much of the work that has been conducted on adverse birth outcomes has focused on low birth weight in general and not on IUGR. Studies that have examined IUGR specifically thus far have focused primarily on individual-level maternal risk factors. These risk factors have only been able to explain a small portion of the variance in IUGR. Therefore, recent work has begun to focus on community-level risk factors in addition to the individual-level maternal characteristics. This study uses Social Ecology to examine the relationship of individual and community-level risk factors and IUGR. Logistic regression was used to establish an individual-level model based on 155, 856 births recorded in Harris County, TX during 1999-2001. IUGR was characterized using a fetal growth ratio method with race/ethnic and sex specific mean birth weights calculated from national vital records. The spatial distributions of 114,460 birth records spatially located within the City of Houston were examined using choropleth, probability and density maps. Census tracts with higher than expected rates of IUGR and high levels of neighborhood disadvantage were highlighted. Neighborhood disadvantage was constructed using socioeconomic variables from the 2000 U.S. Census. Factor analysis was used to create a unified single measure. Lastly, a random coefficients model was used to examine the relationship between varying levels of community disadvantage, given the set of individual-level risk factors for 152,997 birth records spatially located within Harris County, TX. Neighborhood disadvantage was measured using three different indices adapted from previous work. The findings show that pregnancy-induced hypertension, previous preterm infant, tobacco use and insufficient weight gain have the highest association with IUGR. Neighborhood disadvantage only slightly further increases the risk of IUGR (OR 1.12 to 1.23). Although community level disadvantage only helped to explain a small proportion of the variance of IUGR, it did have a significant impact. This finding suggests that community level risk factors should be included in future work with IUGR and that more work needs to be conducted. ^

Governance Structure Choices in Supply Chain Management Evidence from Spanish and Chinese Pork Chain Cases

The author participated in the 6 th EU Framework Project ―Q-pork Chains (FP6-036245-2)‖ from 2007 to 2009. With understanding of work reports from China and other countries, it is found that compared with other countries, China has great problems in pork quality and safety. By comparing the pork chain management between China and Spain, It is found that the difference in governance structure is one of the main differences in pork chain management between Spain and China. In China, spot-market relationship still dominates governance structure of pork chain, especially between the numerous house-hold pig holders and the great number of small slaughters. While in Spain, chain agents commonly apply cooperatives or integrations to cooperate. It also has been proven by recent studies, that in quality management at the chain level that supply chain integration has a direct effect on quality management practices (Han, 2010). Therefore, the author started to investigate the governance structure choices in supply chain management. And it has been set as the first research objective, which is to explain the governance structure choices process and the influencing factors in supply chain management, analyzing the pork chains cases in Spain and in China. During the further investigation, the author noticed the international trade of pork between Spain and China is not smooth since the signature of bi-lateral agreement on pork trade in 2007. Thus, another objective of the research is to find and solve the problems exist in the international pork chain between Spain and China. For the first objective, to explain the governance structure choices in supply chain management, the thesis conducts research in three main sections. 10 First of all, the thesis gives a literature overview in chapter two on Supply Chain Management (SCM), agri-food chain management and pork chain management. It concludes that SCM is a systems approach to view the supply chains as a whole, and to manage the total flow of goods inventory from the supplier to the ultimate customer. It includes the bi-directional flow of products (materials and services) and information, and the associated managerial and operational activities. And it also is a customer focus to create unique and individual source of customer value with an appropriate use of resources, leading to customer satisfaction and building competitive chain advantages. Agri-food chain management and pork chain management are applications of SCM in agri-food sector and pork sector respectively. Then, the research gives a comparative study in chapter three in the pork chain and pork chain management between Spain and China. Many differences are found, while the main difference is governance structure in pork chain management. Furthermore, the author gives an empirical study on governance structure choice in chapter five. It is concluded that governance structure of supply chain consists of a collection of rules/institutions/constraints structuring the transactions between the various stakeholders. Based on the overview on literatures closely related with governance structure, such as transaction cost economics, transaction value analysis and resource-based view theories, seven hypotheses are proposed, which are: Hypothesis 1: Transaction cost has positive relationship with governance structure choice Hypothesis 2: Uncertainty has positive relationship with transaction cost; higher uncertainty exerts high transaction cost Hypothesis 3: The relationship between asset specificity and transaction cost is positive Hypothesis 4: Collaboration advantages and governance structure choice have positive relationship11 Hypothesis 5: Willingness to collaborate has positive relationship with collaboration advantages Hypothesis 6: Capability to collaborate has positive relationship with collaboration advantages Hypothesis 7: Uncertainty has negative effect on collaboration advantages It is noted that as transaction cost value is negative, the transaction cost mentioned in the hypotheses is its absolute value. To test the seven hypotheses, Structural Equation Model (SEM) is applied and data collected from 350 pork slaughtering and processing companies in Jiangsu, Shandong and Henan Provinces in China is used. Based on the empirical SEM model and its results, the seven hypotheses are proved. The author generates several conclusions accordingly. It is found that the governance structure choice of the chain not only depends on transaction cost, it also depends on collaboration advantages. Exchange partners establish more stable and more intense relationship to reduce transaction cost and to maximize collaboration advantages. ―Collaboration advantages‖ in this thesis is defined as the joint value achieved through transaction (mutual activities) of agents in supply chains. This value forms as improvements, mainly in mutual logistics systems, cash response, information exchange, technological improvements and innovative improvements and quality management improvements, etc. Governance structure choice is jointly decided by transaction cost and collaboration advantages. Chain agents take different governance structures to coordinate in order to decrease their transaction cost and to increase their collaboration advantages. In China´s pork chain case, spot market relationship dominates the governance structure among the numerous backyard pig farmer and small family slaughterhouse 12 as they are connected by acquaintance relationship and the transaction cost in turn is low. Their relationship is reliable as they know each other in the neighborhood; as a result, spot market relationship is suitable for their exchange. However, the transaction between large-scale slaughtering and processing industries and small-scale pig producers is becoming difficult. The information hold back behavior and hold-up behavior of small-scale pig producers increase transaction cost between them and large-scale slaughtering and processing industries. Thus, through the more intense and stable relationship between processing industries and pig producers, processing industries reduce the transaction cost and improve the collaboration advantages with their chain partners, in which quality and safety collaboration advantages be increased, meaning that processing industries are able to provide consumers products with better quality and higher safety. It is also drawn that transaction cost is influenced mainly by uncertainty and asset specificity, which is in line with new institutional economics theories developed by Williamson O. E. In China´s pork chain case, behavioral uncertainty is created by the hold-up behaviors of great numbers of small pig producers, while big slaughtering and processing industries having strong asset specificity. On the other hand, ―collaboration advantages‖ is influenced by chain agents´ willingness to collaborate and chain agents´ capabilities to cooperate. With the fast growth of big scale slaughtering and processing industries, they are more willing to know and make effort to cooperate with their chain members, and they are more capable to create joint value together with other chain agents. Therefore, they are now the main chain agents who drive more intense and stable governance structure in China‘s pork chain. For the other objective, to find and solve the problems in the international pork chain between Spain and China, the research gives an analysis in chapter four on the 13 international pork chain. This study gives explanations why the international trade of pork between Spain and China is not sufficient from the chain perspective. It is found that the first obstacle is the high quality and safety requirement set by Chinese government. It makes the Spanish companies difficult to get authorities to export. Other aspects, such as Spanish pork is not competitive in price compared with other countries such as Denmark, United States, Canada, etc., Chinese consumers do not have sufficient information on Spanish pork products, are also important reasons that Spain does not export great quantity of pork products to China. It is concluded that China´s government has too much concern on the quality and safety requirements to Spanish pork products, which makes trade difficult to complete. The two countries need to establish a more stable and intense trade relationship. They also should make the information exchange sufficient and efficient and try to break trade barriers. Spanish companies should consider proper price strategies to win the Chinese pork market

Chromatin structure and gene expression.

It is now well understood that chromatin structure is perturbed in the neighborhood of expressed genes. This is most obvious in the neighborhood of promoters and enhancers, where hypersensitivity to nucleases marks sites that no longer carry canonical nucleosomes, and to which transcription factors bind. To study the relationship between transcription factor binding and the generation of these hypersensitive regions, we mutated individual cis-acting regulatory elements within the enhancer that lies between the chicken beta- and epsilon-globin genes. Constructions carrying the mutant enhancer were introduced by stable transformation into an avian erythroid cell line. We observed that weakening the enhancer resulted in creation of two classes of site: those still completely accessible to nuclease attack and those that were completely blocked. This all-or-none behavior suggests a mechanism by which chromatin structure can act to sharpen the response of developmental systems to changing concentrations of regulatory factors. Another problem raised by chromatin structure concerns the establishment of boundaries between active and inactive chromatin domains. We have identified a DNA element at the 5' end of the chicken beta-globin locus, near such a boundary, that has the properties of an insulator; in test constructions, it blocks the action of an enhancer on a promoter when it is placed between them. We describe the properties and partial dissection of this sequence. A third problem is posed by the continued presence of nucleosomes on transcribed genes, which might prevent the passage of RNA polymerase. We show, however, that a prokaryotic polymerase can transcribe through a histone octamer on a simple chromatin template. The analysis of this process reveals that an octamer is capable of transferring from a position in front of the polymerase to one behind, without ever losing its attachment to the DNA.

Global properties of the mapping between local amino acid sequence and local structure in proteins.

Local protein structure prediction efforts have consistently failed to exceed approximately 70% accuracy. We characterize the degeneracy of the mapping from local sequence to local structure responsible for this failure by investigating the extent to which similar sequence segments found in different proteins adopt similar three-dimensional structures. Sequence segments 3-15 residues in length from 154 different protein families are partitioned into neighborhoods containing segments with similar sequences using cluster analysis. The consistency of the sequence-to-structure mapping is assessed by comparing the local structures adopted by sequence segments in the same neighborhood in proteins of known structure. In the 154 families, 45% and 28% of the positions occur in neighborhoods in which one and two local structures predominate, respectively. The sequence patterns that characterize the neighborhoods in the first class probably include virtually all of the short sequence motifs in proteins that consistently occur in a particular local structure. These patterns, many of which occur in transitions between secondary structural elements, are an interesting combination of previously studied and novel motifs. The identification of sequence patterns that consistently occur in one or a small number of local structures in proteins should contribute to the prediction of protein structure from sequence.