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.     

基于Legendre多项式的随机连续系统的Markov参数估计

本文在讨论连续Ｗｉｓｅｎｒ过程的Ｌｅｇｅｎｄｒｅ多项式逼近值的相关性和Ｗｉｅｎｅｒ过程扰动下连续线性系统基于该正交多项的最小二乘估计有偏性后，提出了无偏一致的且数估计误差方差最小的Ｍａｒｋｏｖ估计（最小方差估计）算法，并给出本文方法的仿真结果。     

Determining the characteristics of systems with multiple inputs and multiple outputs

A simple and computationally efficient method of determining the transfer function and other characteristics of systems with multiple inputs and multiple outputs (MIMO systems) described by autoregression equations is proposed. The method is based on the use of the discrete Fourier transformation. The algorithm is highly suitable for computer implementation. The efficiency and simplicity of the method are illustrated using the example of a system with three inputs and three outputs. The proposed concept may be applied to systems described by the autoregression sliding mean.     

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)     

Isometric Piecewise Polynomial Curves

The main preoccupations of research in computer-aided geometric design have been on shape-specification techniques for polynomial curves and surfaces, and on the continuity between segments or patches. When modelling with such techniques, curves and surfaces can be compressed or expanded arbitrarily. There has been relatively little work on interacting with direct spatial properties of curves and surfaces, such as their arc length or surface area. As a first step, we derive families of parametric piecewise polynomial curves that satisfy various positional and tangential constraints together with arc-length constraints. We call these curves isometric curves. A space curve is defined as a sequence of polynomial curve segments, each of which is defined by the familiar Hermite or Bézier constraints for cubic polynomials; as well, each segment is constrained to have a specified arc length. We demonstrate that this class of curves is attractive and stable. We also describe the numerical techniques used that are sufficient for achieving real time interaction with these curves on low-end workstations.