Minimizing the number of tool switches on a flexible machine

This article analyzes a tool switching problem arising in certain flexible manufacturing environments. A batch of jobs have to be successively processed on a single flexible machine. Each job requires a subset of tools, which have to be placed in the tool magazine of the machine before the job can be processed. The tool magazine has a limited capacity, and, in general, the number of tools needed to produce all the jobs exceeds this capacity. Hence, it is sometimes necessary to change tools between two jobs in a sequence. The problem is then to determine a job sequence and an associated sequence of loadings for the tool magazine, such that the total number of tool switches is minimized. This problem has been previously considered by several authors; it is here revisited, both from a theoretical and from a computational viewpoint. Basic results concerning the computational complexity of the problem are established. Several heuristics are proposed for its solution, and their performance is computationally assessed.     

Local and global deadlock-detection in component-based systems are NP-hard

Interaction systems are a formal model for component-based systems. Combining components via connectors to form more complex systems may give rise to deadlock situations. We present here a polynomial time reduction from 3-SAT to the question whether an interaction system contains deadlocks.     

Optimal implementations of UPGMA and other common clustering algorithms

In this work we consider hierarchical clustering algorithms, such as UPGMA, which follow the closest-pair joining scheme. We survey optimal O(n²)-time implementations of such algorithms which use a ‘locally closest’ joining scheme, and specify conditions under which this relaxed joining scheme is equivalent to the original one (i.e. ‘globally closest’).     

Smaller superconcentrators of density 28

An N-superconcentrator is a directed, acyclic graph with N input nodes and N output nodes such that every subset of the inputs and every subset of the outputs of same cardinality can be connected by node-disjoint paths. It is known that linear-size and bounded-degree superconcentrators exist. Here it is proved that such superconcentrators exist (by a random construction of certain expander graphs as building blocks) having density 28 (where the density is the number of edges divided by N). The best known density before this paper was 34.2 [U. Schöning, Construction of expanders and superconcentrators using Kolmogorov complexity, J. Random Structures Algorithms 17 (2000) 64-77] or 33 [L.A. Bassalygo, Personal communication, 2004].     

Continued fraction for formal laurent series and the lattice structure of sequences

Besides equidistribution properties and statistical independence the lattice profile, a generalized version of Marsaglia's lattice test, provides another quality measure for pseudorandom sequences over a (finite) field. It turned out that the lattice profile is closely related with the linear complexity profile. In this article we give a survey of several features of the linear complexity profile and the lattice profile, and we utilize relationships to completely describe the lattice profile of a sequence over a finite field in terms of the continued fraction expansion of its generating function. Finally we describe and construct sequences with a certain lattice profile, and introduce a further complexity measure.     

气固流化床中非线性特性的多尺度分析

Deterministic chaos theory offers useful quantitative tools to characterize the non-linear dynamic behavior of a fluidized bed and the developed complexity theory presents a new approach to evaluate finite sequences. In this paper,the non-linear,hydrodynamic behavior of the pressure flutuation signals in a reactor was discussed by chaos parameters and complexity measures.Coherent results were achieved by our multi-scale analysis,which further exposed the behavior in a gas-solid two-phase system.     

Interference effects from grammatically unavailable constituents during sentence processing.

Evidence from 3 experiments reveals interference effects from structural relationships that are inconsistent with any grammatical parse of the perceived input. Processing disruption was observed when items occurring between a head and a dependent overlapped with either (or both) syntactic or semantic features of the dependent. Effects of syntactic interference occur in the earliest online measures in the region where the retrieval of a long-distance dependent occurs. Semantic interference effects occur in later online measures at the end of the sentence. Both effects endure in offline comprehension measures, suggesting that interfering items participate in incorrect interpretations that resist reanalysis. The data are discussed in terms of a cue-based retrieval account of parsing, which reconciles the fact that the parser must violate the grammar in order for these interference effects to occur. Broader implications of this research indicate a need for a precise specification of the interface between the parsing mechanism and the memory system that supports language comprehension. (PsycINFO Database Record (c) 2010 APA, all rights reserved)     

Increasing testing productivity and software quality: A comparison of software testing methodologies within NASA

Pressure to compress the development life cycle and reduce the duration and resources committed to testing lead to experimentation in testing at the NASA Goddard Space Flight Centerís Software Engineering Laboratory. This study investigates the trend to reduce developer testing and increasingly rely upon inspection techniques and independent functional testing to shorten the development life cycle, improve testing productivity, and improve software quality.An approach is developed to conduct this comparison. In particular, the problem faced by software researchers, having a comprehensive characterization of software projects so similar types may be identified for comparative studies, is addressed using expert opinion.     

网格计算机上的平行视图算法

文中给出了二维网络结构的计算机上求平面上一组不相交简单物体平行视图的算法，并分析了算法的正确性和时间复杂性。