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.

O ciúme romântico e os relacionamentos amorosos heterossexuais contemporâneos

O presente estudo pretende discorrer a respeito do ciúme romântico heterossexual, na tentativa de compreender um dos sentimentos mais presentes na vida do ser humano. Mesmo que para muitos o ciúme possa representar uma manifestação de amor, ele é, na verdade, um sentimento que produz angústia em muitos parceiros e pode atingir formas doentias, e abalar a saúde mental. Mas também é inevitável, porque em maior ou menor grau, todos estão sujeitos a ele, o que nos obriga a ficar atentos para saber elaborá-lo em favor de nossa vida amorosa. É preciso conhecer profundamente esse sentimento para que se possa compreendê-lo, e elaborarmos estratégias profícuas de enfrentamento para lidarmos com esse fenômeno.

Acidentes de transporte em Cuiabá, Mato Grosso: morbi-mortalidade

Os acidentes de trânsito continuam a se constituir em um importante problema de saúde pública no Brasil. Objetivo : Analisar as características dos acidentes de transporte terrestre e suas vítimas no município de Cuiabá. Método: Para o estudo da mortalidade foram obtidos dados do Sistema de Informações sobre Mortalidade /Ministério da Saúde, disponíveis em CD-ROM referente aos anos de 1980-2005; para o de morbidade hospitalar foram utilizados os dados Sistemas de Informações Hospitalares no período de 1998-2006 e para o estudo da demanda das unidades de urgência e emergência foi utilizado um banco de dados construído especialmente para esse fim, referente aos meses de maio a junho de 2005. Adotaram-se os conceitos definições estabelecidos na Classificação Internacional de Doenças 10: acidentes de transporte (categ. V01-V99) e acidente de transporte terrestre (V01-V89). Resultados: Em todas as análises, as taxas de mortalidade/morbidade hospitalar se expressaram com valores maiores que a média brasileira. Apesar de apresentar aspectos distintos entre mortalidade, morbidade hospitalar e morbidade da demanda de unidades de urgência e emergência, destacam-se como principais vítimas os jovens do sexo masculino; a vítima qualificada como "ocupante" predomina nos acidentes fatais e os "motociclistas", nos não fatais.Conclusão: este estudo revela que Cuiabá é uma área onde os acidentes de transporte terrestre devem ser tratados como prioridade devido à sua magnitude, seja na mortalidade ou morbidade, trazendo subsídios para o seu enfrentamento

Mothers’ birth care experiences in a Brazilian birth centre

Objective: to explore the reasons why women with previous hospital experience seek care at a birth centre, and their perceptions related to the care received in both settings. Design, setting and participants in-depth interviews focusing on the care experiences of 18 women who received birth care in a birth centre of the Brazilian public health system. Findings: three key themes emerged from the analysis: ‘Confrontation with strong problems in the hospital setting’, ‘Reasons to seek the birth centre’ and ‘Satisfaction related to birth centre care’. The main aspects that the mothers mentioned in the first and third themes were related to the institutional structure and system of care. Key conclusions and implications for practice mothers’ narratives suggested that their previous experience of problems in the hospital setting was the main motive for seeking care at the birth centre. The most important components of birth care were attention, meeting personal care demands and establishment of an adequate interpersonal relationship. More sensitive birthing care in the hospital setting is necessary, and this can be promoted through continuing professional education

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.

Semantic memory impairment in temporal lobe epilepsy associated with hippociampal sclerosis

Episodic memory impairment is a well-recognized feature of mesial temporal lobe epilepsy. Semantic memory has received much less attention in this patient population. In this study, semantic memory aspects (word-picture matching, word definition, confrontation and responsive naming, and word list generation) in 19 patients with left and right temporal lobe epilepsy secondary to mesial temporal sclerosis (MTS) were compared with those of normal controls. Patients with LMTS showed impaired performance in word definition (compared to controls and RMTS) and in responsive naming (compared to controls). RMTS and LMTS patients performed worse than controls in word-picture matching. Both patients with left and right mesial temporal lobe epilepsy performed worse than controls in word list generation and in confrontation naming tests. Attentional-executive dysfunction may have contributed to these deficits. We conclude that patients with left and right NITS display impaired aspects of semantic knowledge. A better understanding of semantic processing difficulties in these patients will provide better insight into the difficulties with activities of daily living in this patient population. (C) 2007 Elsevier Inc. All rights reserved.