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.

Exponential Rates of Convergence in the Ergodic Theorem: A Constructive Approach

We prove that, once an algorithm of perfect simulation for a stationary and ergodic random field F taking values in S(Zd), S a bounded subset of R(n), is provided, the speed of convergence in the mean ergodic theorem occurs exponentially fast for F. Applications from (non-equilibrium) statistical mechanics and interacting particle systems are presented.

Children`s oral production of narratives and constructive memory using prior reading of pictures

With the purpose of approximating two issues, oral narrative and constructive memory, we assume that children, as well as adults, have a constructive memory. Accordingly, researchers of the constructive memory share with piagetians the vision that memory is an applied cognition. Under this perspective, understanding and coding into memory constitute a process which is considered similar to the piagetian assimilation of building an internal conceptual representation of the information (hence the term constructive memory. The objective of this study is to examine and illustrate, through examples drawn from a research about oral narrative with 5, 8 and 10 years old children, the extent to which the constructive memory is stimulated by the acquisition of the structures of knowledge or ""mental models"" (schemes of stories and scenes, scripts), and if they automatically employ them to process constructively the information in storage and rebuild them in the recovery. A sequence of five pictures from a book without text was transformed into computerized program, and the pictures were thus presented to the children. The story focuses on a misunderstanding of two characters on a different assessment about a key event. In data collection, the demands of memory were preserved, since children narrate their stories when the images were no longer viewed on the computer screen. Each narrative was produced as a monologue. The results show that this story can be told either in a descriptive level or in a more elaborated level, where intentions and beliefs are attributed to the characters. Although this study allows an assessment of the development of children`s capabilities (both cognitive and linguistic) to narrate a story, there are for sure other issues that could be exploited.

Interações entre evolução sedimentar e ocupação humana pré-histórica na costa centro-sul de Santa Catarina, Brasil

Desde o começo da ocupação humana no litoral centro-sul de Santa Catarina, Brasil, a articulação entre processos naturais e antrópicos modelou uma paisagem fortemente domesticada, marcada pela construção massiva de concheiros de dimensões monumentais e pela permanência milenar. Na planície costeira entre Passagem da Barra (município de Laguna) e lago Figueirinha (município de Jaguaruna), 76 sambaquis foram mapeados, dos quais 48 possuem datação. O levantamento sistemático de sítios e datações permitiu identificar padrões de distribuição espacial nos sambaquis da região, quanto a contexto sedimentar da época de construção, estratigrafia e idade. Desse modo, reconheceram-se nos sítios da região: cinco contextos geológico-geomorfológicos de localização; três padrões estratigráficos; e quatro fases de ocupação sambaquieira baseadas na quantidade de sítios e no tipo de padrão construtivo dominante. O modelo integrado de evolução sedimentar e distribuição tempo-espacial de sambaquis indica que estes sítios eram construídos em áreas já emersas e pouco alagáveis, e que sítios interiores, afastados dos corpos lagunares, podem não se ter preservado ou não estarem expostos devido ao processo de assoreamento contínuo que caracterizou a região após a máxima transgressão holocênica. O cruzamento de dados aqui proposto evidencia a importância de abordagens integradas entre arqueologia e geociências no estudo da evolução das paisagens.

Cross-national epidemiology of DSM-IV major depressive episode

Background: Major depression is one of the leading causes of disability worldwide, yet epidemiologic data are not available for many countries, particularly low- to middle-income countries. In this paper, we present data on the prevalence, impairment and demographic correlates of depression from 18 high and low-to middle-income countries in the World Mental Health Survey Initiative. Methods: Major depressive episodes (MDE) as defined by the Diagnostic and Statistical Manual of Mental Disorders, fourth edition (DMS-IV) were evaluated in face-to-face interviews using the World Health Organization Composite International Diagnostic Interview (CIDI). Data from 18 countries were analyzed in this report (n = 89,037). All countries surveyed representative, population-based samples of adults. Results: The average lifetime and 12-month prevalence estimates of DSM-IV MDE were 14.6% and 5.5% in the ten high-income and 11.1% and 5.9% in the eight low- to middle-income countries. The average age of onset ascertained retrospectively was 25.7 in the high-income and 24.0 in low- to middle-income countries. Functional impairment was associated with recency of MDE. The female: male ratio was about 2: 1. In high-income countries, younger age was associated with higher 12-month prevalence; by contrast, in several low-to middle-income countries, older age was associated with greater likelihood of MDE. The strongest demographic correlate in high-income countries was being separated from a partner, and in low- to middle-income countries, was being divorced or widowed. Conclusions: MDE is a significant public-health concern across all regions of the world and is strongly linked to social conditions. Future research is needed to investigate the combination of demographic risk factors that are most strongly associated with MDE in the specific countries included in the WMH.

An algorithmic Friedman-Pippenger theorem on tree embeddings and applications

An (n, d)-expander is a graph G = (V, E) such that for every X subset of V with vertical bar X vertical bar <= 2n - 2 we have vertical bar Gamma(G)(X) vertical bar >= (d + 1) vertical bar X vertical bar. A tree T is small if it has at most n vertices and has maximum degree at most d. Friedman and Pippenger (1987) proved that any ( n; d)- expander contains every small tree. However, their elegant proof does not seem to yield an efficient algorithm for obtaining the tree. In this paper, we give an alternative result that does admit a polynomial time algorithm for finding the immersion of any small tree in subgraphs G of (N, D, lambda)-graphs Lambda, as long as G contains a positive fraction of the edges of Lambda and lambda/D is small enough. In several applications of the Friedman-Pippenger theorem, including the ones in the original paper of those authors, the (n, d)-expander G is a subgraph of an (N, D, lambda)-graph as above. Therefore, our result suffices to provide efficient algorithms for such previously non-constructive applications. As an example, we discuss a recent result of Alon, Krivelevich, and Sudakov (2007) concerning embedding nearly spanning bounded degree trees, the proof of which makes use of the Friedman-Pippenger theorem. We shall also show a construction inspired on Wigderson-Zuckerman expander graphs for which any sufficiently dense subgraph contains all trees of sizes and maximum degrees achieving essentially optimal parameters. Our algorithmic approach is based on a reduction of the tree embedding problem to a certain on-line matching problem for bipartite graphs, solved by Aggarwal et al. (1996).

Combined heuristic with fuzzy system to transmission system expansion planning

A heuristic algorithm that employs fuzzy logic is proposed to the power system transmission expansion planning problem. The algorithm is based on the divide to conquer strategy, which is controlled by the fuzzy system. The algorithm provides high quality solutions with the use of fuzzy decision making, which is based on nondeterministic criteria to guide the search. The fuzzy system provides a self-adjusting mechanism that eliminates the manual adjustment of parameters to each system being solved. (C) 2010 Elsevier B.V. All rights reserved.

An efficient heuristic for total flowtime minimisation in no-wait flowshops

In this paper, we address the problem of scheduling jobs in a no-wait flowshop with the objective of minimising the total completion time. This problem is well-known for being nondeterministic polynomial-time hard, and therefore, most contributions to the topic focus on developing algorithms able to obtain good approximate solutions for the problem in a short CPU time. More specifically, there are various constructive heuristics available for the problem [such as the ones by Rajendran and Chaudhuri (Nav Res Logist 37: 695-705, 1990); Bertolissi (J Mater Process Technol 107: 459-465, 2000), Aldowaisan and Allahverdi (Omega 32: 345-352, 2004) and the Chins heuristic by Fink and Voa (Eur J Operat Res 151: 400-414, 2003)], as well as a successful local search procedure (Pilot-1-Chins). We propose a new constructive heuristic based on an analogy with the two-machine problem in order to select the candidate to be appended in the partial schedule. The myopic behaviour of the heuristic is tempered by exploring the neighbourhood of the so-obtained partial schedules. The computational results indicate that the proposed heuristic outperforms existing ones in terms of quality of the solution obtained and equals the performance of the time-consuming Pilot-1-Chins.

Decision making in fuzzy environment and multicriteria power engineering problems

This paper presents results of research into the use of the Bellman-Zadeh approach to decision making in a fuzzy environment for solving multicriteria power engineering problems. The application of the approach conforms to the principle of guaranteed result and provides constructive lines in computationally effective obtaining harmonious solutions on the basis of solving associated maxmin problems. The presented results are universally applicable and are already being used to solve diverse classes of power engineering problems. It is illustrated by considering problems of power and energy shortage allocation, power system operation, optimization of network configuration in distribution systems, and energetically effective voltage control in distribution systems. (c) 2011 Elsevier Ltd. All rights reserved.

Multicriteria analysis in decision making under information uncertainty

This paper presents results of research related to multicriteria decision making under information uncertainty. The Bell-man-Zadeh approach to decision making in a fuzzy environment is utilized for analyzing multicriteria optimization models (< X, M > models) under deterministic information. Its application conforms to the principle of guaranteed result and provides constructive lines in obtaining harmonious solutions on the basis of analyzing associated maxmin problems. This circumstance permits one to generalize the classic approach to considering the uncertainty of quantitative information (based on constructing and analyzing payoff matrices reflecting effects which can be obtained for different combinations of solution alternatives and the so-called states of nature) in monocriteria decision making to multicriteria problems. Considering that the uncertainty of information can produce considerable decision uncertainty regions, the resolving capacity of this generalization does not always permit one to obtain unique solutions. Taking this into account, a proposed general scheme of multicriteria decision making under information uncertainty also includes the construction and analysis of the so-called < X, R > models (which contain fuzzy preference relations as criteria of optimality) as a means for the subsequent contraction of the decision uncertainty regions. The paper results are of a universal character and are illustrated by a simple example. (c) 2007 Elsevier Inc. All rights reserved.

Placement over containers with fixed dimensions solved with adaptive neighborhood simulated annealing

This work deals with the problem of minimizing the waste of space that occurs on a rotational placement of a set of irregular bi-dimensional items inside a bi-dimensional container. This problem is approached with a heuristic based on Simulated Annealing (SA) with adaptive neighborhood. The objective function is evaluated in a constructive approach, where the items are placed sequentially. The placement is governed by three different types of parameters: sequence of placement, the rotation angle and the translation. The rotation applied and the translation of the polygon are cyclic continuous parameters, and the sequence of placement defines a combinatorial problem. This way, it is necessary to control cyclic continuous and discrete parameters. The approaches described in the literature deal with only type of parameter (sequence of placement or translation). In the proposed SA algorithm, the sensibility of each continuous parameter is evaluated at each iteration increasing the number of accepted solutions. The sensibility of each parameter is associated to its probability distribution in the definition of the next candidate.

Some heuristic algorithms for total tardiness minimization in a flowshop with blocking

The flowshop scheduling problem with blocking in-process is addressed in this paper. In this environment, there are no buffers between successive machines: therefore intermediate queues of jobs waiting in the system for their next operations are not allowed. Heuristic approaches are proposed to minimize the total tardiness criterion. A constructive heuristic that explores specific characteristics of the problem is presented. Moreover, a GRASP-based heuristic is proposed and Coupled with a path relinking strategy to search for better outcomes. Computational tests are presented and the comparisons made with an adaptation of the NEH algorithm and with a branch-and-bound algorithm indicate that the new approaches are promising. (c) 2007 Elsevier Ltd. All rights reserved.

An integrated genomic analysis of human glioblastoma Multiforme

Glioblastoma multiforme ( GBM) is the most common and lethal type of brain cancer. To identify the genetic alterations in GBMs, we sequenced 20,661 protein coding genes, determined the presence of amplifications and deletions using high- density oligonucleotide arrays, and performed gene expression analyses using next- generation sequencing technologies in 22 human tumor samples. This comprehensive analysis led to the discovery of a variety of genes that were not known to be altered in GBMs. Most notably, we found recurrent mutations in the active site of isocitrate dehydrogenase 1 ( IDH1) in 12% of GBM patients. Mutations in IDH1 occurred in a large fraction of young patients and in most patients with secondary GBMs and were associated with an increase in overall survival. These studies demonstrate the value of unbiased genomic analyses in the characterization of human brain cancer and identify a potentially useful genetic alteration for the classification and targeted therapy of GBMs.

Cognitive impairment and dementia in neurocysticercosis A cross-sectional controlled study

Objectives: Neurocysticercosis (NCYST) is the most frequent CNS parasitic disease worldwide, affecting more than 50 million people. However, some of its clinical findings, such as cognitive impairment and dementia, remain poorly characterized, with no controlled studies conducted so far. We investigated the frequency and the clinical profile of cognitive impairment and dementia in a sample of patients with NCYST in comparison with cognitively healthy controls (HC) and patients with cryptogenic epilepsy (CE). Methods: Forty treatment-naive patients with NCYST, aged 39.25 +/- 10.50 years and fulfilling absolute criteria for definitive active NCYST on MRI, were submitted to a comprehensive cognitive and functional evaluation and were compared with 49 HC and 28 patients with CE of similar age, educational level, and seizure frequency. Results: Patients with NCYST displayed significant impairment in executive functions, verbal and nonverbal memory, constructive praxis, and verbal fluency when compared with HC (p < 0.05). Dementia was diagnosed in 12.5% patients with NCYST according to DSM-IV criteria. When compared with patients with CE, patients with NCYST presented altered working and episodic verbal memory, executive functions, naming, verbal fluency, constructive praxis, and visual-spatial orientation. No correlation emerged between cognitive scores and number, localization, or type of NCYST lesions on MRI. Conclusions: Cognitive impairment was ubiquitous in this sample of patients with active neurocysticercosis (NCYST). Antiepileptic drug use and seizure frequency could not account for these features. Dementia was present in a significant proportion of patients. These data broaden our knowledge on the clinical presentations of NCYST and its impact in world public health. Neurology (R) 2010;74:1288-1295

Comparing detection and location performance of perpendicular and parallel broadside GPR antenna orientations

GPR (Ground Penetrating Radar) results are shown for perpendicular broadside and parallel broadside antenna orientations. Performance in detection and localization of concrete tubes and steel tanks is compared as a function of acquisition configuration. The comparison is done using 100 MHz and 200 MHz center frequency antennas. All tubes and tanks are buried at the geophysical test site of IAG/USP in Sao Paulo city, Brazil. The results show that the long steel pipe with a 38-mm diameter was well detected with the perpendicular broadside configuration. The concrete tubes were better detected with the parallel broadside configuration, clearly showing hyperbolic diffraction events from all targets up to 2-m depth. Steel tanks were detected with the two configurations. However, the parallel broadside configuration was generated to a much lesser extent an apparent hyperbolic reflection corresponding to constructive interference of diffraction hyperbolas of adjacent targets placed at the same depth. Vertical concrete tubes and steel tanks were better contained with parallel broadside antennas, where the apexes of the diffraction hyperbolas better corresponded to the horizontal location of the buried target disposition. The two configurations provide details about buried targets emphasizing how GPR multi-component configurations have the potential to improve the subsurface image quality as well as to discriminate different buried targets. It is judged that they hold some applicability in geotechnical and geoscientific studies. (C) 2009 Elsevier B.V. All rights reserved.